-/* List object implementation */\r
-\r
-#include "Python.h"\r
-\r
-#ifdef STDC_HEADERS\r
-#include <stddef.h>\r
-#else\r
-#include <sys/types.h> /* For size_t */\r
-#endif\r
-\r
-/* Ensure ob_item has room for at least newsize elements, and set\r
- * ob_size to newsize. If newsize > ob_size on entry, the content\r
- * of the new slots at exit is undefined heap trash; it's the caller's\r
- * responsibility to overwrite them with sane values.\r
- * The number of allocated elements may grow, shrink, or stay the same.\r
- * Failure is impossible if newsize <= self.allocated on entry, although\r
- * that partly relies on an assumption that the system realloc() never\r
- * fails when passed a number of bytes <= the number of bytes last\r
- * allocated (the C standard doesn't guarantee this, but it's hard to\r
- * imagine a realloc implementation where it wouldn't be true).\r
- * Note that self->ob_item may change, and even if newsize is less\r
- * than ob_size on entry.\r
- */\r
-static int\r
-list_resize(PyListObject *self, Py_ssize_t newsize)\r
-{\r
- PyObject **items;\r
- size_t new_allocated;\r
- Py_ssize_t allocated = self->allocated;\r
-\r
- /* Bypass realloc() when a previous overallocation is large enough\r
- to accommodate the newsize. If the newsize falls lower than half\r
- the allocated size, then proceed with the realloc() to shrink the list.\r
- */\r
- if (allocated >= newsize && newsize >= (allocated >> 1)) {\r
- assert(self->ob_item != NULL || newsize == 0);\r
- Py_SIZE(self) = newsize;\r
- return 0;\r
- }\r
-\r
- /* This over-allocates proportional to the list size, making room\r
- * for additional growth. The over-allocation is mild, but is\r
- * enough to give linear-time amortized behavior over a long\r
- * sequence of appends() in the presence of a poorly-performing\r
- * system realloc().\r
- * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...\r
- */\r
- new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);\r
-\r
- /* check for integer overflow */\r
- if (new_allocated > PY_SIZE_MAX - newsize) {\r
- PyErr_NoMemory();\r
- return -1;\r
- } else {\r
- new_allocated += newsize;\r
- }\r
-\r
- if (newsize == 0)\r
- new_allocated = 0;\r
- items = self->ob_item;\r
- if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))\r
- PyMem_RESIZE(items, PyObject *, new_allocated);\r
- else\r
- items = NULL;\r
- if (items == NULL) {\r
- PyErr_NoMemory();\r
- return -1;\r
- }\r
- self->ob_item = items;\r
- Py_SIZE(self) = newsize;\r
- self->allocated = new_allocated;\r
- return 0;\r
-}\r
-\r
-/* Debug statistic to compare allocations with reuse through the free list */\r
-#undef SHOW_ALLOC_COUNT\r
-#ifdef SHOW_ALLOC_COUNT\r
-static size_t count_alloc = 0;\r
-static size_t count_reuse = 0;\r
-\r
-static void\r
-show_alloc(void)\r
-{\r
- fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n",\r
- count_alloc);\r
- fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T\r
- "d\n", count_reuse);\r
- fprintf(stderr, "%.2f%% reuse rate\n\n",\r
- (100.0*count_reuse/(count_alloc+count_reuse)));\r
-}\r
-#endif\r
-\r
-/* Empty list reuse scheme to save calls to malloc and free */\r
-#ifndef PyList_MAXFREELIST\r
-#define PyList_MAXFREELIST 80\r
-#endif\r
-static PyListObject *free_list[PyList_MAXFREELIST];\r
-static int numfree = 0;\r
-\r
-void\r
-PyList_Fini(void)\r
-{\r
- PyListObject *op;\r
-\r
- while (numfree) {\r
- op = free_list[--numfree];\r
- assert(PyList_CheckExact(op));\r
- PyObject_GC_Del(op);\r
- }\r
-}\r
-\r
-PyObject *\r
-PyList_New(Py_ssize_t size)\r
-{\r
- PyListObject *op;\r
- size_t nbytes;\r
-#ifdef SHOW_ALLOC_COUNT\r
- static int initialized = 0;\r
- if (!initialized) {\r
- Py_AtExit(show_alloc);\r
- initialized = 1;\r
- }\r
-#endif\r
-\r
- if (size < 0) {\r
- PyErr_BadInternalCall();\r
- return NULL;\r
- }\r
- /* Check for overflow without an actual overflow,\r
- * which can cause compiler to optimise out */\r
- if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))\r
- return PyErr_NoMemory();\r
- nbytes = size * sizeof(PyObject *);\r
- if (numfree) {\r
- numfree--;\r
- op = free_list[numfree];\r
- _Py_NewReference((PyObject *)op);\r
-#ifdef SHOW_ALLOC_COUNT\r
- count_reuse++;\r
-#endif\r
- } else {\r
- op = PyObject_GC_New(PyListObject, &PyList_Type);\r
- if (op == NULL)\r
- return NULL;\r
-#ifdef SHOW_ALLOC_COUNT\r
- count_alloc++;\r
-#endif\r
- }\r
- if (size <= 0)\r
- op->ob_item = NULL;\r
- else {\r
- op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);\r
- if (op->ob_item == NULL) {\r
- Py_DECREF(op);\r
- return PyErr_NoMemory();\r
- }\r
- memset(op->ob_item, 0, nbytes);\r
- }\r
- Py_SIZE(op) = size;\r
- op->allocated = size;\r
- _PyObject_GC_TRACK(op);\r
- return (PyObject *) op;\r
-}\r
-\r
-Py_ssize_t\r
-PyList_Size(PyObject *op)\r
-{\r
- if (!PyList_Check(op)) {\r
- PyErr_BadInternalCall();\r
- return -1;\r
- }\r
- else\r
- return Py_SIZE(op);\r
-}\r
-\r
-static PyObject *indexerr = NULL;\r
-\r
-PyObject *\r
-PyList_GetItem(PyObject *op, Py_ssize_t i)\r
-{\r
- if (!PyList_Check(op)) {\r
- PyErr_BadInternalCall();\r
- return NULL;\r
- }\r
- if (i < 0 || i >= Py_SIZE(op)) {\r
- if (indexerr == NULL) {\r
- indexerr = PyString_FromString(\r
- "list index out of range");\r
- if (indexerr == NULL)\r
- return NULL;\r
- }\r
- PyErr_SetObject(PyExc_IndexError, indexerr);\r
- return NULL;\r
- }\r
- return ((PyListObject *)op) -> ob_item[i];\r
-}\r
-\r
-int\r
-PyList_SetItem(register PyObject *op, register Py_ssize_t i,\r
- register PyObject *newitem)\r
-{\r
- register PyObject *olditem;\r
- register PyObject **p;\r
- if (!PyList_Check(op)) {\r
- Py_XDECREF(newitem);\r
- PyErr_BadInternalCall();\r
- return -1;\r
- }\r
- if (i < 0 || i >= Py_SIZE(op)) {\r
- Py_XDECREF(newitem);\r
- PyErr_SetString(PyExc_IndexError,\r
- "list assignment index out of range");\r
- return -1;\r
- }\r
- p = ((PyListObject *)op) -> ob_item + i;\r
- olditem = *p;\r
- *p = newitem;\r
- Py_XDECREF(olditem);\r
- return 0;\r
-}\r
-\r
-static int\r
-ins1(PyListObject *self, Py_ssize_t where, PyObject *v)\r
-{\r
- Py_ssize_t i, n = Py_SIZE(self);\r
- PyObject **items;\r
- if (v == NULL) {\r
- PyErr_BadInternalCall();\r
- return -1;\r
- }\r
- if (n == PY_SSIZE_T_MAX) {\r
- PyErr_SetString(PyExc_OverflowError,\r
- "cannot add more objects to list");\r
- return -1;\r
- }\r
-\r
- if (list_resize(self, n+1) == -1)\r
- return -1;\r
-\r
- if (where < 0) {\r
- where += n;\r
- if (where < 0)\r
- where = 0;\r
- }\r
- if (where > n)\r
- where = n;\r
- items = self->ob_item;\r
- for (i = n; --i >= where; )\r
- items[i+1] = items[i];\r
- Py_INCREF(v);\r
- items[where] = v;\r
- return 0;\r
-}\r
-\r
-int\r
-PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)\r
-{\r
- if (!PyList_Check(op)) {\r
- PyErr_BadInternalCall();\r
- return -1;\r
- }\r
- return ins1((PyListObject *)op, where, newitem);\r
-}\r
-\r
-static int\r
-app1(PyListObject *self, PyObject *v)\r
-{\r
- Py_ssize_t n = PyList_GET_SIZE(self);\r
-\r
- assert (v != NULL);\r
- if (n == PY_SSIZE_T_MAX) {\r
- PyErr_SetString(PyExc_OverflowError,\r
- "cannot add more objects to list");\r
- return -1;\r
- }\r
-\r
- if (list_resize(self, n+1) == -1)\r
- return -1;\r
-\r
- Py_INCREF(v);\r
- PyList_SET_ITEM(self, n, v);\r
- return 0;\r
-}\r
-\r
-int\r
-PyList_Append(PyObject *op, PyObject *newitem)\r
-{\r
- if (PyList_Check(op) && (newitem != NULL))\r
- return app1((PyListObject *)op, newitem);\r
- PyErr_BadInternalCall();\r
- return -1;\r
-}\r
-\r
-/* Methods */\r
-\r
-static void\r
-list_dealloc(PyListObject *op)\r
-{\r
- Py_ssize_t i;\r
- PyObject_GC_UnTrack(op);\r
- Py_TRASHCAN_SAFE_BEGIN(op)\r
- if (op->ob_item != NULL) {\r
- /* Do it backwards, for Christian Tismer.\r
- There's a simple test case where somehow this reduces\r
- thrashing when a *very* large list is created and\r
- immediately deleted. */\r
- i = Py_SIZE(op);\r
- while (--i >= 0) {\r
- Py_XDECREF(op->ob_item[i]);\r
- }\r
- PyMem_FREE(op->ob_item);\r
- }\r
- if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))\r
- free_list[numfree++] = op;\r
- else\r
- Py_TYPE(op)->tp_free((PyObject *)op);\r
- Py_TRASHCAN_SAFE_END(op)\r
-}\r
-\r
-static int\r
-list_print(PyListObject *op, FILE *fp, int flags)\r
-{\r
- int rc;\r
- Py_ssize_t i;\r
- PyObject *item;\r
-\r
- rc = Py_ReprEnter((PyObject*)op);\r
- if (rc != 0) {\r
- if (rc < 0)\r
- return rc;\r
- Py_BEGIN_ALLOW_THREADS\r
- fprintf(fp, "[...]");\r
- Py_END_ALLOW_THREADS\r
- return 0;\r
- }\r
- Py_BEGIN_ALLOW_THREADS\r
- fprintf(fp, "[");\r
- Py_END_ALLOW_THREADS\r
- for (i = 0; i < Py_SIZE(op); i++) {\r
- item = op->ob_item[i];\r
- Py_INCREF(item);\r
- if (i > 0) {\r
- Py_BEGIN_ALLOW_THREADS\r
- fprintf(fp, ", ");\r
- Py_END_ALLOW_THREADS\r
- }\r
- if (PyObject_Print(item, fp, 0) != 0) {\r
- Py_DECREF(item);\r
- Py_ReprLeave((PyObject *)op);\r
- return -1;\r
- }\r
- Py_DECREF(item);\r
- }\r
- Py_BEGIN_ALLOW_THREADS\r
- fprintf(fp, "]");\r
- Py_END_ALLOW_THREADS\r
- Py_ReprLeave((PyObject *)op);\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-list_repr(PyListObject *v)\r
-{\r
- Py_ssize_t i;\r
- PyObject *s, *temp;\r
- PyObject *pieces = NULL, *result = NULL;\r
-\r
- i = Py_ReprEnter((PyObject*)v);\r
- if (i != 0) {\r
- return i > 0 ? PyString_FromString("[...]") : NULL;\r
- }\r
-\r
- if (Py_SIZE(v) == 0) {\r
- result = PyString_FromString("[]");\r
- goto Done;\r
- }\r
-\r
- pieces = PyList_New(0);\r
- if (pieces == NULL)\r
- goto Done;\r
-\r
- /* Do repr() on each element. Note that this may mutate the list,\r
- so must refetch the list size on each iteration. */\r
- for (i = 0; i < Py_SIZE(v); ++i) {\r
- int status;\r
- if (Py_EnterRecursiveCall(" while getting the repr of a list"))\r
- goto Done;\r
- s = PyObject_Repr(v->ob_item[i]);\r
- Py_LeaveRecursiveCall();\r
- if (s == NULL)\r
- goto Done;\r
- status = PyList_Append(pieces, s);\r
- Py_DECREF(s); /* append created a new ref */\r
- if (status < 0)\r
- goto Done;\r
- }\r
-\r
- /* Add "[]" decorations to the first and last items. */\r
- assert(PyList_GET_SIZE(pieces) > 0);\r
- s = PyString_FromString("[");\r
- if (s == NULL)\r
- goto Done;\r
- temp = PyList_GET_ITEM(pieces, 0);\r
- PyString_ConcatAndDel(&s, temp);\r
- PyList_SET_ITEM(pieces, 0, s);\r
- if (s == NULL)\r
- goto Done;\r
-\r
- s = PyString_FromString("]");\r
- if (s == NULL)\r
- goto Done;\r
- temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);\r
- PyString_ConcatAndDel(&temp, s);\r
- PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);\r
- if (temp == NULL)\r
- goto Done;\r
-\r
- /* Paste them all together with ", " between. */\r
- s = PyString_FromString(", ");\r
- if (s == NULL)\r
- goto Done;\r
- result = _PyString_Join(s, pieces);\r
- Py_DECREF(s);\r
-\r
-Done:\r
- Py_XDECREF(pieces);\r
- Py_ReprLeave((PyObject *)v);\r
- return result;\r
-}\r
-\r
-static Py_ssize_t\r
-list_length(PyListObject *a)\r
-{\r
- return Py_SIZE(a);\r
-}\r
-\r
-static int\r
-list_contains(PyListObject *a, PyObject *el)\r
-{\r
- Py_ssize_t i;\r
- int cmp;\r
-\r
- for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)\r
- cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),\r
- Py_EQ);\r
- return cmp;\r
-}\r
-\r
-static PyObject *\r
-list_item(PyListObject *a, Py_ssize_t i)\r
-{\r
- if (i < 0 || i >= Py_SIZE(a)) {\r
- if (indexerr == NULL) {\r
- indexerr = PyString_FromString(\r
- "list index out of range");\r
- if (indexerr == NULL)\r
- return NULL;\r
- }\r
- PyErr_SetObject(PyExc_IndexError, indexerr);\r
- return NULL;\r
- }\r
- Py_INCREF(a->ob_item[i]);\r
- return a->ob_item[i];\r
-}\r
-\r
-static PyObject *\r
-list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)\r
-{\r
- PyListObject *np;\r
- PyObject **src, **dest;\r
- Py_ssize_t i, len;\r
- if (ilow < 0)\r
- ilow = 0;\r
- else if (ilow > Py_SIZE(a))\r
- ilow = Py_SIZE(a);\r
- if (ihigh < ilow)\r
- ihigh = ilow;\r
- else if (ihigh > Py_SIZE(a))\r
- ihigh = Py_SIZE(a);\r
- len = ihigh - ilow;\r
- np = (PyListObject *) PyList_New(len);\r
- if (np == NULL)\r
- return NULL;\r
-\r
- src = a->ob_item + ilow;\r
- dest = np->ob_item;\r
- for (i = 0; i < len; i++) {\r
- PyObject *v = src[i];\r
- Py_INCREF(v);\r
- dest[i] = v;\r
- }\r
- return (PyObject *)np;\r
-}\r
-\r
-PyObject *\r
-PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)\r
-{\r
- if (!PyList_Check(a)) {\r
- PyErr_BadInternalCall();\r
- return NULL;\r
- }\r
- return list_slice((PyListObject *)a, ilow, ihigh);\r
-}\r
-\r
-static PyObject *\r
-list_concat(PyListObject *a, PyObject *bb)\r
-{\r
- Py_ssize_t size;\r
- Py_ssize_t i;\r
- PyObject **src, **dest;\r
- PyListObject *np;\r
- if (!PyList_Check(bb)) {\r
- PyErr_Format(PyExc_TypeError,\r
- "can only concatenate list (not \"%.200s\") to list",\r
- bb->ob_type->tp_name);\r
- return NULL;\r
- }\r
-#define b ((PyListObject *)bb)\r
- size = Py_SIZE(a) + Py_SIZE(b);\r
- if (size < 0)\r
- return PyErr_NoMemory();\r
- np = (PyListObject *) PyList_New(size);\r
- if (np == NULL) {\r
- return NULL;\r
- }\r
- src = a->ob_item;\r
- dest = np->ob_item;\r
- for (i = 0; i < Py_SIZE(a); i++) {\r
- PyObject *v = src[i];\r
- Py_INCREF(v);\r
- dest[i] = v;\r
- }\r
- src = b->ob_item;\r
- dest = np->ob_item + Py_SIZE(a);\r
- for (i = 0; i < Py_SIZE(b); i++) {\r
- PyObject *v = src[i];\r
- Py_INCREF(v);\r
- dest[i] = v;\r
- }\r
- return (PyObject *)np;\r
-#undef b\r
-}\r
-\r
-static PyObject *\r
-list_repeat(PyListObject *a, Py_ssize_t n)\r
-{\r
- Py_ssize_t i, j;\r
- Py_ssize_t size;\r
- PyListObject *np;\r
- PyObject **p, **items;\r
- PyObject *elem;\r
- if (n < 0)\r
- n = 0;\r
- if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)\r
- return PyErr_NoMemory();\r
- size = Py_SIZE(a) * n;\r
- if (size == 0)\r
- return PyList_New(0);\r
- np = (PyListObject *) PyList_New(size);\r
- if (np == NULL)\r
- return NULL;\r
-\r
- items = np->ob_item;\r
- if (Py_SIZE(a) == 1) {\r
- elem = a->ob_item[0];\r
- for (i = 0; i < n; i++) {\r
- items[i] = elem;\r
- Py_INCREF(elem);\r
- }\r
- return (PyObject *) np;\r
- }\r
- p = np->ob_item;\r
- items = a->ob_item;\r
- for (i = 0; i < n; i++) {\r
- for (j = 0; j < Py_SIZE(a); j++) {\r
- *p = items[j];\r
- Py_INCREF(*p);\r
- p++;\r
- }\r
- }\r
- return (PyObject *) np;\r
-}\r
-\r
-static int\r
-list_clear(PyListObject *a)\r
-{\r
- Py_ssize_t i;\r
- PyObject **item = a->ob_item;\r
- if (item != NULL) {\r
- /* Because XDECREF can recursively invoke operations on\r
- this list, we make it empty first. */\r
- i = Py_SIZE(a);\r
- Py_SIZE(a) = 0;\r
- a->ob_item = NULL;\r
- a->allocated = 0;\r
- while (--i >= 0) {\r
- Py_XDECREF(item[i]);\r
- }\r
- PyMem_FREE(item);\r
- }\r
- /* Never fails; the return value can be ignored.\r
- Note that there is no guarantee that the list is actually empty\r
- at this point, because XDECREF may have populated it again! */\r
- return 0;\r
-}\r
-\r
-/* a[ilow:ihigh] = v if v != NULL.\r
- * del a[ilow:ihigh] if v == NULL.\r
- *\r
- * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's\r
- * guaranteed the call cannot fail.\r
- */\r
-static int\r
-list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)\r
-{\r
- /* Because [X]DECREF can recursively invoke list operations on\r
- this list, we must postpone all [X]DECREF activity until\r
- after the list is back in its canonical shape. Therefore\r
- we must allocate an additional array, 'recycle', into which\r
- we temporarily copy the items that are deleted from the\r
- list. :-( */\r
- PyObject *recycle_on_stack[8];\r
- PyObject **recycle = recycle_on_stack; /* will allocate more if needed */\r
- PyObject **item;\r
- PyObject **vitem = NULL;\r
- PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */\r
- Py_ssize_t n; /* # of elements in replacement list */\r
- Py_ssize_t norig; /* # of elements in list getting replaced */\r
- Py_ssize_t d; /* Change in size */\r
- Py_ssize_t k;\r
- size_t s;\r
- int result = -1; /* guilty until proved innocent */\r
-#define b ((PyListObject *)v)\r
- if (v == NULL)\r
- n = 0;\r
- else {\r
- if (a == b) {\r
- /* Special case "a[i:j] = a" -- copy b first */\r
- v = list_slice(b, 0, Py_SIZE(b));\r
- if (v == NULL)\r
- return result;\r
- result = list_ass_slice(a, ilow, ihigh, v);\r
- Py_DECREF(v);\r
- return result;\r
- }\r
- v_as_SF = PySequence_Fast(v, "can only assign an iterable");\r
- if(v_as_SF == NULL)\r
- goto Error;\r
- n = PySequence_Fast_GET_SIZE(v_as_SF);\r
- vitem = PySequence_Fast_ITEMS(v_as_SF);\r
- }\r
- if (ilow < 0)\r
- ilow = 0;\r
- else if (ilow > Py_SIZE(a))\r
- ilow = Py_SIZE(a);\r
-\r
- if (ihigh < ilow)\r
- ihigh = ilow;\r
- else if (ihigh > Py_SIZE(a))\r
- ihigh = Py_SIZE(a);\r
-\r
- norig = ihigh - ilow;\r
- assert(norig >= 0);\r
- d = n - norig;\r
- if (Py_SIZE(a) + d == 0) {\r
- Py_XDECREF(v_as_SF);\r
- return list_clear(a);\r
- }\r
- item = a->ob_item;\r
- /* recycle the items that we are about to remove */\r
- s = norig * sizeof(PyObject *);\r
- if (s > sizeof(recycle_on_stack)) {\r
- recycle = (PyObject **)PyMem_MALLOC(s);\r
- if (recycle == NULL) {\r
- PyErr_NoMemory();\r
- goto Error;\r
- }\r
- }\r
- memcpy(recycle, &item[ilow], s);\r
-\r
- if (d < 0) { /* Delete -d items */\r
- memmove(&item[ihigh+d], &item[ihigh],\r
- (Py_SIZE(a) - ihigh)*sizeof(PyObject *));\r
- list_resize(a, Py_SIZE(a) + d);\r
- item = a->ob_item;\r
- }\r
- else if (d > 0) { /* Insert d items */\r
- k = Py_SIZE(a);\r
- if (list_resize(a, k+d) < 0)\r
- goto Error;\r
- item = a->ob_item;\r
- memmove(&item[ihigh+d], &item[ihigh],\r
- (k - ihigh)*sizeof(PyObject *));\r
- }\r
- for (k = 0; k < n; k++, ilow++) {\r
- PyObject *w = vitem[k];\r
- Py_XINCREF(w);\r
- item[ilow] = w;\r
- }\r
- for (k = norig - 1; k >= 0; --k)\r
- Py_XDECREF(recycle[k]);\r
- result = 0;\r
- Error:\r
- if (recycle != recycle_on_stack)\r
- PyMem_FREE(recycle);\r
- Py_XDECREF(v_as_SF);\r
- return result;\r
-#undef b\r
-}\r
-\r
-int\r
-PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)\r
-{\r
- if (!PyList_Check(a)) {\r
- PyErr_BadInternalCall();\r
- return -1;\r
- }\r
- return list_ass_slice((PyListObject *)a, ilow, ihigh, v);\r
-}\r
-\r
-static PyObject *\r
-list_inplace_repeat(PyListObject *self, Py_ssize_t n)\r
-{\r
- PyObject **items;\r
- Py_ssize_t size, i, j, p;\r
-\r
-\r
- size = PyList_GET_SIZE(self);\r
- if (size == 0 || n == 1) {\r
- Py_INCREF(self);\r
- return (PyObject *)self;\r
- }\r
-\r
- if (n < 1) {\r
- (void)list_clear(self);\r
- Py_INCREF(self);\r
- return (PyObject *)self;\r
- }\r
-\r
- if (size > PY_SSIZE_T_MAX / n) {\r
- return PyErr_NoMemory();\r
- }\r
-\r
- if (list_resize(self, size*n) == -1)\r
- return NULL;\r
-\r
- p = size;\r
- items = self->ob_item;\r
- for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */\r
- for (j = 0; j < size; j++) {\r
- PyObject *o = items[j];\r
- Py_INCREF(o);\r
- items[p++] = o;\r
- }\r
- }\r
- Py_INCREF(self);\r
- return (PyObject *)self;\r
-}\r
-\r
-static int\r
-list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)\r
-{\r
- PyObject *old_value;\r
- if (i < 0 || i >= Py_SIZE(a)) {\r
- PyErr_SetString(PyExc_IndexError,\r
- "list assignment index out of range");\r
- return -1;\r
- }\r
- if (v == NULL)\r
- return list_ass_slice(a, i, i+1, v);\r
- Py_INCREF(v);\r
- old_value = a->ob_item[i];\r
- a->ob_item[i] = v;\r
- Py_DECREF(old_value);\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-listinsert(PyListObject *self, PyObject *args)\r
-{\r
- Py_ssize_t i;\r
- PyObject *v;\r
- if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))\r
- return NULL;\r
- if (ins1(self, i, v) == 0)\r
- Py_RETURN_NONE;\r
- return NULL;\r
-}\r
-\r
-static PyObject *\r
-listappend(PyListObject *self, PyObject *v)\r
-{\r
- if (app1(self, v) == 0)\r
- Py_RETURN_NONE;\r
- return NULL;\r
-}\r
-\r
-static PyObject *\r
-listextend(PyListObject *self, PyObject *b)\r
-{\r
- PyObject *it; /* iter(v) */\r
- Py_ssize_t m; /* size of self */\r
- Py_ssize_t n; /* guess for size of b */\r
- Py_ssize_t mn; /* m + n */\r
- Py_ssize_t i;\r
- PyObject *(*iternext)(PyObject *);\r
-\r
- /* Special cases:\r
- 1) lists and tuples which can use PySequence_Fast ops\r
- 2) extending self to self requires making a copy first\r
- */\r
- if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {\r
- PyObject **src, **dest;\r
- b = PySequence_Fast(b, "argument must be iterable");\r
- if (!b)\r
- return NULL;\r
- n = PySequence_Fast_GET_SIZE(b);\r
- if (n == 0) {\r
- /* short circuit when b is empty */\r
- Py_DECREF(b);\r
- Py_RETURN_NONE;\r
- }\r
- m = Py_SIZE(self);\r
- if (list_resize(self, m + n) == -1) {\r
- Py_DECREF(b);\r
- return NULL;\r
- }\r
- /* note that we may still have self == b here for the\r
- * situation a.extend(a), but the following code works\r
- * in that case too. Just make sure to resize self\r
- * before calling PySequence_Fast_ITEMS.\r
- */\r
- /* populate the end of self with b's items */\r
- src = PySequence_Fast_ITEMS(b);\r
- dest = self->ob_item + m;\r
- for (i = 0; i < n; i++) {\r
- PyObject *o = src[i];\r
- Py_INCREF(o);\r
- dest[i] = o;\r
- }\r
- Py_DECREF(b);\r
- Py_RETURN_NONE;\r
- }\r
-\r
- it = PyObject_GetIter(b);\r
- if (it == NULL)\r
- return NULL;\r
- iternext = *it->ob_type->tp_iternext;\r
-\r
- /* Guess a result list size. */\r
- n = _PyObject_LengthHint(b, 8);\r
- if (n == -1) {\r
- Py_DECREF(it);\r
- return NULL;\r
- }\r
- m = Py_SIZE(self);\r
- mn = m + n;\r
- if (mn >= m) {\r
- /* Make room. */\r
- if (list_resize(self, mn) == -1)\r
- goto error;\r
- /* Make the list sane again. */\r
- Py_SIZE(self) = m;\r
- }\r
- /* Else m + n overflowed; on the chance that n lied, and there really\r
- * is enough room, ignore it. If n was telling the truth, we'll\r
- * eventually run out of memory during the loop.\r
- */\r
-\r
- /* Run iterator to exhaustion. */\r
- for (;;) {\r
- PyObject *item = iternext(it);\r
- if (item == NULL) {\r
- if (PyErr_Occurred()) {\r
- if (PyErr_ExceptionMatches(PyExc_StopIteration))\r
- PyErr_Clear();\r
- else\r
- goto error;\r
- }\r
- break;\r
- }\r
- if (Py_SIZE(self) < self->allocated) {\r
- /* steals ref */\r
- PyList_SET_ITEM(self, Py_SIZE(self), item);\r
- ++Py_SIZE(self);\r
- }\r
- else {\r
- int status = app1(self, item);\r
- Py_DECREF(item); /* append creates a new ref */\r
- if (status < 0)\r
- goto error;\r
- }\r
- }\r
-\r
- /* Cut back result list if initial guess was too large. */\r
- if (Py_SIZE(self) < self->allocated)\r
- list_resize(self, Py_SIZE(self)); /* shrinking can't fail */\r
-\r
- Py_DECREF(it);\r
- Py_RETURN_NONE;\r
-\r
- error:\r
- Py_DECREF(it);\r
- return NULL;\r
-}\r
-\r
-PyObject *\r
-_PyList_Extend(PyListObject *self, PyObject *b)\r
-{\r
- return listextend(self, b);\r
-}\r
-\r
-static PyObject *\r
-list_inplace_concat(PyListObject *self, PyObject *other)\r
-{\r
- PyObject *result;\r
-\r
- result = listextend(self, other);\r
- if (result == NULL)\r
- return result;\r
- Py_DECREF(result);\r
- Py_INCREF(self);\r
- return (PyObject *)self;\r
-}\r
-\r
-static PyObject *\r
-listpop(PyListObject *self, PyObject *args)\r
-{\r
- Py_ssize_t i = -1;\r
- PyObject *v;\r
- int status;\r
-\r
- if (!PyArg_ParseTuple(args, "|n:pop", &i))\r
- return NULL;\r
-\r
- if (Py_SIZE(self) == 0) {\r
- /* Special-case most common failure cause */\r
- PyErr_SetString(PyExc_IndexError, "pop from empty list");\r
- return NULL;\r
- }\r
- if (i < 0)\r
- i += Py_SIZE(self);\r
- if (i < 0 || i >= Py_SIZE(self)) {\r
- PyErr_SetString(PyExc_IndexError, "pop index out of range");\r
- return NULL;\r
- }\r
- v = self->ob_item[i];\r
- if (i == Py_SIZE(self) - 1) {\r
- status = list_resize(self, Py_SIZE(self) - 1);\r
- assert(status >= 0);\r
- return v; /* and v now owns the reference the list had */\r
- }\r
- Py_INCREF(v);\r
- status = list_ass_slice(self, i, i+1, (PyObject *)NULL);\r
- assert(status >= 0);\r
- /* Use status, so that in a release build compilers don't\r
- * complain about the unused name.\r
- */\r
- (void) status;\r
-\r
- return v;\r
-}\r
-\r
-/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */\r
-static void\r
-reverse_slice(PyObject **lo, PyObject **hi)\r
-{\r
- assert(lo && hi);\r
-\r
- --hi;\r
- while (lo < hi) {\r
- PyObject *t = *lo;\r
- *lo = *hi;\r
- *hi = t;\r
- ++lo;\r
- --hi;\r
- }\r
-}\r
-\r
-/* Lots of code for an adaptive, stable, natural mergesort. There are many\r
- * pieces to this algorithm; read listsort.txt for overviews and details.\r
- */\r
-\r
-/* Comparison function. Takes care of calling a user-supplied\r
- * comparison function (any callable Python object), which must not be\r
- * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool\r
- * with Py_LT if you know it's NULL).\r
- * Returns -1 on error, 1 if x < y, 0 if x >= y.\r
- */\r
-static int\r
-islt(PyObject *x, PyObject *y, PyObject *compare)\r
-{\r
- PyObject *res;\r
- PyObject *args;\r
- Py_ssize_t i;\r
-\r
- assert(compare != NULL);\r
- /* Call the user's comparison function and translate the 3-way\r
- * result into true or false (or error).\r
- */\r
- args = PyTuple_New(2);\r
- if (args == NULL)\r
- return -1;\r
- Py_INCREF(x);\r
- Py_INCREF(y);\r
- PyTuple_SET_ITEM(args, 0, x);\r
- PyTuple_SET_ITEM(args, 1, y);\r
- res = PyObject_Call(compare, args, NULL);\r
- Py_DECREF(args);\r
- if (res == NULL)\r
- return -1;\r
- if (!PyInt_Check(res)) {\r
- PyErr_Format(PyExc_TypeError,\r
- "comparison function must return int, not %.200s",\r
- res->ob_type->tp_name);\r
- Py_DECREF(res);\r
- return -1;\r
- }\r
- i = PyInt_AsLong(res);\r
- Py_DECREF(res);\r
- return i < 0;\r
-}\r
-\r
-/* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls\r
- * islt. This avoids a layer of function call in the usual case, and\r
- * sorting does many comparisons.\r
- * Returns -1 on error, 1 if x < y, 0 if x >= y.\r
- */\r
-#define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \\r
- PyObject_RichCompareBool(X, Y, Py_LT) : \\r
- islt(X, Y, COMPARE))\r
-\r
-/* Compare X to Y via "<". Goto "fail" if the comparison raises an\r
- error. Else "k" is set to true iff X<Y, and an "if (k)" block is\r
- started. It makes more sense in context <wink>. X and Y are PyObject*s.\r
-*/\r
-#define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail; \\r
- if (k)\r
-\r
-/* binarysort is the best method for sorting small arrays: it does\r
- few compares, but can do data movement quadratic in the number of\r
- elements.\r
- [lo, hi) is a contiguous slice of a list, and is sorted via\r
- binary insertion. This sort is stable.\r
- On entry, must have lo <= start <= hi, and that [lo, start) is already\r
- sorted (pass start == lo if you don't know!).\r
- If islt() complains return -1, else 0.\r
- Even in case of error, the output slice will be some permutation of\r
- the input (nothing is lost or duplicated).\r
-*/\r
-static int\r
-binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)\r
- /* compare -- comparison function object, or NULL for default */\r
-{\r
- register Py_ssize_t k;\r
- register PyObject **l, **p, **r;\r
- register PyObject *pivot;\r
-\r
- assert(lo <= start && start <= hi);\r
- /* assert [lo, start) is sorted */\r
- if (lo == start)\r
- ++start;\r
- for (; start < hi; ++start) {\r
- /* set l to where *start belongs */\r
- l = lo;\r
- r = start;\r
- pivot = *r;\r
- /* Invariants:\r
- * pivot >= all in [lo, l).\r
- * pivot < all in [r, start).\r
- * The second is vacuously true at the start.\r
- */\r
- assert(l < r);\r
- do {\r
- p = l + ((r - l) >> 1);\r
- IFLT(pivot, *p)\r
- r = p;\r
- else\r
- l = p+1;\r
- } while (l < r);\r
- assert(l == r);\r
- /* The invariants still hold, so pivot >= all in [lo, l) and\r
- pivot < all in [l, start), so pivot belongs at l. Note\r
- that if there are elements equal to pivot, l points to the\r
- first slot after them -- that's why this sort is stable.\r
- Slide over to make room.\r
- Caution: using memmove is much slower under MSVC 5;\r
- we're not usually moving many slots. */\r
- for (p = start; p > l; --p)\r
- *p = *(p-1);\r
- *l = pivot;\r
- }\r
- return 0;\r
-\r
- fail:\r
- return -1;\r
-}\r
-\r
-/*\r
-Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi\r
-is required on entry. "A run" is the longest ascending sequence, with\r
-\r
- lo[0] <= lo[1] <= lo[2] <= ...\r
-\r
-or the longest descending sequence, with\r
-\r
- lo[0] > lo[1] > lo[2] > ...\r
-\r
-Boolean *descending is set to 0 in the former case, or to 1 in the latter.\r
-For its intended use in a stable mergesort, the strictness of the defn of\r
-"descending" is needed so that the caller can safely reverse a descending\r
-sequence without violating stability (strict > ensures there are no equal\r
-elements to get out of order).\r
-\r
-Returns -1 in case of error.\r
-*/\r
-static Py_ssize_t\r
-count_run(PyObject **lo, PyObject **hi, PyObject *compare, int *descending)\r
-{\r
- Py_ssize_t k;\r
- Py_ssize_t n;\r
-\r
- assert(lo < hi);\r
- *descending = 0;\r
- ++lo;\r
- if (lo == hi)\r
- return 1;\r
-\r
- n = 2;\r
- IFLT(*lo, *(lo-1)) {\r
- *descending = 1;\r
- for (lo = lo+1; lo < hi; ++lo, ++n) {\r
- IFLT(*lo, *(lo-1))\r
- ;\r
- else\r
- break;\r
- }\r
- }\r
- else {\r
- for (lo = lo+1; lo < hi; ++lo, ++n) {\r
- IFLT(*lo, *(lo-1))\r
- break;\r
- }\r
- }\r
-\r
- return n;\r
-fail:\r
- return -1;\r
-}\r
-\r
-/*\r
-Locate the proper position of key in a sorted vector; if the vector contains\r
-an element equal to key, return the position immediately to the left of\r
-the leftmost equal element. [gallop_right() does the same except returns\r
-the position to the right of the rightmost equal element (if any).]\r
-\r
-"a" is a sorted vector with n elements, starting at a[0]. n must be > 0.\r
-\r
-"hint" is an index at which to begin the search, 0 <= hint < n. The closer\r
-hint is to the final result, the faster this runs.\r
-\r
-The return value is the int k in 0..n such that\r
-\r
- a[k-1] < key <= a[k]\r
-\r
-pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,\r
-key belongs at index k; or, IOW, the first k elements of a should precede\r
-key, and the last n-k should follow key.\r
-\r
-Returns -1 on error. See listsort.txt for info on the method.\r
-*/\r
-static Py_ssize_t\r
-gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare)\r
-{\r
- Py_ssize_t ofs;\r
- Py_ssize_t lastofs;\r
- Py_ssize_t k;\r
-\r
- assert(key && a && n > 0 && hint >= 0 && hint < n);\r
-\r
- a += hint;\r
- lastofs = 0;\r
- ofs = 1;\r
- IFLT(*a, key) {\r
- /* a[hint] < key -- gallop right, until\r
- * a[hint + lastofs] < key <= a[hint + ofs]\r
- */\r
- const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */\r
- while (ofs < maxofs) {\r
- IFLT(a[ofs], key) {\r
- lastofs = ofs;\r
- ofs = (ofs << 1) + 1;\r
- if (ofs <= 0) /* int overflow */\r
- ofs = maxofs;\r
- }\r
- else /* key <= a[hint + ofs] */\r
- break;\r
- }\r
- if (ofs > maxofs)\r
- ofs = maxofs;\r
- /* Translate back to offsets relative to &a[0]. */\r
- lastofs += hint;\r
- ofs += hint;\r
- }\r
- else {\r
- /* key <= a[hint] -- gallop left, until\r
- * a[hint - ofs] < key <= a[hint - lastofs]\r
- */\r
- const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */\r
- while (ofs < maxofs) {\r
- IFLT(*(a-ofs), key)\r
- break;\r
- /* key <= a[hint - ofs] */\r
- lastofs = ofs;\r
- ofs = (ofs << 1) + 1;\r
- if (ofs <= 0) /* int overflow */\r
- ofs = maxofs;\r
- }\r
- if (ofs > maxofs)\r
- ofs = maxofs;\r
- /* Translate back to positive offsets relative to &a[0]. */\r
- k = lastofs;\r
- lastofs = hint - ofs;\r
- ofs = hint - k;\r
- }\r
- a -= hint;\r
-\r
- assert(-1 <= lastofs && lastofs < ofs && ofs <= n);\r
- /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the\r
- * right of lastofs but no farther right than ofs. Do a binary\r
- * search, with invariant a[lastofs-1] < key <= a[ofs].\r
- */\r
- ++lastofs;\r
- while (lastofs < ofs) {\r
- Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);\r
-\r
- IFLT(a[m], key)\r
- lastofs = m+1; /* a[m] < key */\r
- else\r
- ofs = m; /* key <= a[m] */\r
- }\r
- assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */\r
- return ofs;\r
-\r
-fail:\r
- return -1;\r
-}\r
-\r
-/*\r
-Exactly like gallop_left(), except that if key already exists in a[0:n],\r
-finds the position immediately to the right of the rightmost equal value.\r
-\r
-The return value is the int k in 0..n such that\r
-\r
- a[k-1] <= key < a[k]\r
-\r
-or -1 if error.\r
-\r
-The code duplication is massive, but this is enough different given that\r
-we're sticking to "<" comparisons that it's much harder to follow if\r
-written as one routine with yet another "left or right?" flag.\r
-*/\r
-static Py_ssize_t\r
-gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare)\r
-{\r
- Py_ssize_t ofs;\r
- Py_ssize_t lastofs;\r
- Py_ssize_t k;\r
-\r
- assert(key && a && n > 0 && hint >= 0 && hint < n);\r
-\r
- a += hint;\r
- lastofs = 0;\r
- ofs = 1;\r
- IFLT(key, *a) {\r
- /* key < a[hint] -- gallop left, until\r
- * a[hint - ofs] <= key < a[hint - lastofs]\r
- */\r
- const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */\r
- while (ofs < maxofs) {\r
- IFLT(key, *(a-ofs)) {\r
- lastofs = ofs;\r
- ofs = (ofs << 1) + 1;\r
- if (ofs <= 0) /* int overflow */\r
- ofs = maxofs;\r
- }\r
- else /* a[hint - ofs] <= key */\r
- break;\r
- }\r
- if (ofs > maxofs)\r
- ofs = maxofs;\r
- /* Translate back to positive offsets relative to &a[0]. */\r
- k = lastofs;\r
- lastofs = hint - ofs;\r
- ofs = hint - k;\r
- }\r
- else {\r
- /* a[hint] <= key -- gallop right, until\r
- * a[hint + lastofs] <= key < a[hint + ofs]\r
- */\r
- const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */\r
- while (ofs < maxofs) {\r
- IFLT(key, a[ofs])\r
- break;\r
- /* a[hint + ofs] <= key */\r
- lastofs = ofs;\r
- ofs = (ofs << 1) + 1;\r
- if (ofs <= 0) /* int overflow */\r
- ofs = maxofs;\r
- }\r
- if (ofs > maxofs)\r
- ofs = maxofs;\r
- /* Translate back to offsets relative to &a[0]. */\r
- lastofs += hint;\r
- ofs += hint;\r
- }\r
- a -= hint;\r
-\r
- assert(-1 <= lastofs && lastofs < ofs && ofs <= n);\r
- /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the\r
- * right of lastofs but no farther right than ofs. Do a binary\r
- * search, with invariant a[lastofs-1] <= key < a[ofs].\r
- */\r
- ++lastofs;\r
- while (lastofs < ofs) {\r
- Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);\r
-\r
- IFLT(key, a[m])\r
- ofs = m; /* key < a[m] */\r
- else\r
- lastofs = m+1; /* a[m] <= key */\r
- }\r
- assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */\r
- return ofs;\r
-\r
-fail:\r
- return -1;\r
-}\r
-\r
-/* The maximum number of entries in a MergeState's pending-runs stack.\r
- * This is enough to sort arrays of size up to about\r
- * 32 * phi ** MAX_MERGE_PENDING\r
- * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array\r
- * with 2**64 elements.\r
- */\r
-#define MAX_MERGE_PENDING 85\r
-\r
-/* When we get into galloping mode, we stay there until both runs win less\r
- * often than MIN_GALLOP consecutive times. See listsort.txt for more info.\r
- */\r
-#define MIN_GALLOP 7\r
-\r
-/* Avoid malloc for small temp arrays. */\r
-#define MERGESTATE_TEMP_SIZE 256\r
-\r
-/* One MergeState exists on the stack per invocation of mergesort. It's just\r
- * a convenient way to pass state around among the helper functions.\r
- */\r
-struct s_slice {\r
- PyObject **base;\r
- Py_ssize_t len;\r
-};\r
-\r
-typedef struct s_MergeState {\r
- /* The user-supplied comparison function. or NULL if none given. */\r
- PyObject *compare;\r
-\r
- /* This controls when we get *into* galloping mode. It's initialized\r
- * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for\r
- * random data, and lower for highly structured data.\r
- */\r
- Py_ssize_t min_gallop;\r
-\r
- /* 'a' is temp storage to help with merges. It contains room for\r
- * alloced entries.\r
- */\r
- PyObject **a; /* may point to temparray below */\r
- Py_ssize_t alloced;\r
-\r
- /* A stack of n pending runs yet to be merged. Run #i starts at\r
- * address base[i] and extends for len[i] elements. It's always\r
- * true (so long as the indices are in bounds) that\r
- *\r
- * pending[i].base + pending[i].len == pending[i+1].base\r
- *\r
- * so we could cut the storage for this, but it's a minor amount,\r
- * and keeping all the info explicit simplifies the code.\r
- */\r
- int n;\r
- struct s_slice pending[MAX_MERGE_PENDING];\r
-\r
- /* 'a' points to this when possible, rather than muck with malloc. */\r
- PyObject *temparray[MERGESTATE_TEMP_SIZE];\r
-} MergeState;\r
-\r
-/* Conceptually a MergeState's constructor. */\r
-static void\r
-merge_init(MergeState *ms, PyObject *compare)\r
-{\r
- assert(ms != NULL);\r
- ms->compare = compare;\r
- ms->a = ms->temparray;\r
- ms->alloced = MERGESTATE_TEMP_SIZE;\r
- ms->n = 0;\r
- ms->min_gallop = MIN_GALLOP;\r
-}\r
-\r
-/* Free all the temp memory owned by the MergeState. This must be called\r
- * when you're done with a MergeState, and may be called before then if\r
- * you want to free the temp memory early.\r
- */\r
-static void\r
-merge_freemem(MergeState *ms)\r
-{\r
- assert(ms != NULL);\r
- if (ms->a != ms->temparray)\r
- PyMem_Free(ms->a);\r
- ms->a = ms->temparray;\r
- ms->alloced = MERGESTATE_TEMP_SIZE;\r
-}\r
-\r
-/* Ensure enough temp memory for 'need' array slots is available.\r
- * Returns 0 on success and -1 if the memory can't be gotten.\r
- */\r
-static int\r
-merge_getmem(MergeState *ms, Py_ssize_t need)\r
-{\r
- assert(ms != NULL);\r
- if (need <= ms->alloced)\r
- return 0;\r
- /* Don't realloc! That can cost cycles to copy the old data, but\r
- * we don't care what's in the block.\r
- */\r
- merge_freemem(ms);\r
- if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) {\r
- PyErr_NoMemory();\r
- return -1;\r
- }\r
- ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*));\r
- if (ms->a) {\r
- ms->alloced = need;\r
- return 0;\r
- }\r
- PyErr_NoMemory();\r
- merge_freemem(ms); /* reset to sane state */\r
- return -1;\r
-}\r
-#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \\r
- merge_getmem(MS, NEED))\r
-\r
-/* Merge the na elements starting at pa with the nb elements starting at pb\r
- * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.\r
- * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the\r
- * merge, and should have na <= nb. See listsort.txt for more info.\r
- * Return 0 if successful, -1 if error.\r
- */\r
-static Py_ssize_t\r
-merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,\r
- PyObject **pb, Py_ssize_t nb)\r
-{\r
- Py_ssize_t k;\r
- PyObject *compare;\r
- PyObject **dest;\r
- int result = -1; /* guilty until proved innocent */\r
- Py_ssize_t min_gallop;\r
-\r
- assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);\r
- if (MERGE_GETMEM(ms, na) < 0)\r
- return -1;\r
- memcpy(ms->a, pa, na * sizeof(PyObject*));\r
- dest = pa;\r
- pa = ms->a;\r
-\r
- *dest++ = *pb++;\r
- --nb;\r
- if (nb == 0)\r
- goto Succeed;\r
- if (na == 1)\r
- goto CopyB;\r
-\r
- min_gallop = ms->min_gallop;\r
- compare = ms->compare;\r
- for (;;) {\r
- Py_ssize_t acount = 0; /* # of times A won in a row */\r
- Py_ssize_t bcount = 0; /* # of times B won in a row */\r
-\r
- /* Do the straightforward thing until (if ever) one run\r
- * appears to win consistently.\r
- */\r
- for (;;) {\r
- assert(na > 1 && nb > 0);\r
- k = ISLT(*pb, *pa, compare);\r
- if (k) {\r
- if (k < 0)\r
- goto Fail;\r
- *dest++ = *pb++;\r
- ++bcount;\r
- acount = 0;\r
- --nb;\r
- if (nb == 0)\r
- goto Succeed;\r
- if (bcount >= min_gallop)\r
- break;\r
- }\r
- else {\r
- *dest++ = *pa++;\r
- ++acount;\r
- bcount = 0;\r
- --na;\r
- if (na == 1)\r
- goto CopyB;\r
- if (acount >= min_gallop)\r
- break;\r
- }\r
- }\r
-\r
- /* One run is winning so consistently that galloping may\r
- * be a huge win. So try that, and continue galloping until\r
- * (if ever) neither run appears to be winning consistently\r
- * anymore.\r
- */\r
- ++min_gallop;\r
- do {\r
- assert(na > 1 && nb > 0);\r
- min_gallop -= min_gallop > 1;\r
- ms->min_gallop = min_gallop;\r
- k = gallop_right(*pb, pa, na, 0, compare);\r
- acount = k;\r
- if (k) {\r
- if (k < 0)\r
- goto Fail;\r
- memcpy(dest, pa, k * sizeof(PyObject *));\r
- dest += k;\r
- pa += k;\r
- na -= k;\r
- if (na == 1)\r
- goto CopyB;\r
- /* na==0 is impossible now if the comparison\r
- * function is consistent, but we can't assume\r
- * that it is.\r
- */\r
- if (na == 0)\r
- goto Succeed;\r
- }\r
- *dest++ = *pb++;\r
- --nb;\r
- if (nb == 0)\r
- goto Succeed;\r
-\r
- k = gallop_left(*pa, pb, nb, 0, compare);\r
- bcount = k;\r
- if (k) {\r
- if (k < 0)\r
- goto Fail;\r
- memmove(dest, pb, k * sizeof(PyObject *));\r
- dest += k;\r
- pb += k;\r
- nb -= k;\r
- if (nb == 0)\r
- goto Succeed;\r
- }\r
- *dest++ = *pa++;\r
- --na;\r
- if (na == 1)\r
- goto CopyB;\r
- } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);\r
- ++min_gallop; /* penalize it for leaving galloping mode */\r
- ms->min_gallop = min_gallop;\r
- }\r
-Succeed:\r
- result = 0;\r
-Fail:\r
- if (na)\r
- memcpy(dest, pa, na * sizeof(PyObject*));\r
- return result;\r
-CopyB:\r
- assert(na == 1 && nb > 0);\r
- /* The last element of pa belongs at the end of the merge. */\r
- memmove(dest, pb, nb * sizeof(PyObject *));\r
- dest[nb] = *pa;\r
- return 0;\r
-}\r
-\r
-/* Merge the na elements starting at pa with the nb elements starting at pb\r
- * in a stable way, in-place. na and nb must be > 0, and pa + na == pb.\r
- * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the\r
- * merge, and should have na >= nb. See listsort.txt for more info.\r
- * Return 0 if successful, -1 if error.\r
- */\r
-static Py_ssize_t\r
-merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb)\r
-{\r
- Py_ssize_t k;\r
- PyObject *compare;\r
- PyObject **dest;\r
- int result = -1; /* guilty until proved innocent */\r
- PyObject **basea;\r
- PyObject **baseb;\r
- Py_ssize_t min_gallop;\r
-\r
- assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);\r
- if (MERGE_GETMEM(ms, nb) < 0)\r
- return -1;\r
- dest = pb + nb - 1;\r
- memcpy(ms->a, pb, nb * sizeof(PyObject*));\r
- basea = pa;\r
- baseb = ms->a;\r
- pb = ms->a + nb - 1;\r
- pa += na - 1;\r
-\r
- *dest-- = *pa--;\r
- --na;\r
- if (na == 0)\r
- goto Succeed;\r
- if (nb == 1)\r
- goto CopyA;\r
-\r
- min_gallop = ms->min_gallop;\r
- compare = ms->compare;\r
- for (;;) {\r
- Py_ssize_t acount = 0; /* # of times A won in a row */\r
- Py_ssize_t bcount = 0; /* # of times B won in a row */\r
-\r
- /* Do the straightforward thing until (if ever) one run\r
- * appears to win consistently.\r
- */\r
- for (;;) {\r
- assert(na > 0 && nb > 1);\r
- k = ISLT(*pb, *pa, compare);\r
- if (k) {\r
- if (k < 0)\r
- goto Fail;\r
- *dest-- = *pa--;\r
- ++acount;\r
- bcount = 0;\r
- --na;\r
- if (na == 0)\r
- goto Succeed;\r
- if (acount >= min_gallop)\r
- break;\r
- }\r
- else {\r
- *dest-- = *pb--;\r
- ++bcount;\r
- acount = 0;\r
- --nb;\r
- if (nb == 1)\r
- goto CopyA;\r
- if (bcount >= min_gallop)\r
- break;\r
- }\r
- }\r
-\r
- /* One run is winning so consistently that galloping may\r
- * be a huge win. So try that, and continue galloping until\r
- * (if ever) neither run appears to be winning consistently\r
- * anymore.\r
- */\r
- ++min_gallop;\r
- do {\r
- assert(na > 0 && nb > 1);\r
- min_gallop -= min_gallop > 1;\r
- ms->min_gallop = min_gallop;\r
- k = gallop_right(*pb, basea, na, na-1, compare);\r
- if (k < 0)\r
- goto Fail;\r
- k = na - k;\r
- acount = k;\r
- if (k) {\r
- dest -= k;\r
- pa -= k;\r
- memmove(dest+1, pa+1, k * sizeof(PyObject *));\r
- na -= k;\r
- if (na == 0)\r
- goto Succeed;\r
- }\r
- *dest-- = *pb--;\r
- --nb;\r
- if (nb == 1)\r
- goto CopyA;\r
-\r
- k = gallop_left(*pa, baseb, nb, nb-1, compare);\r
- if (k < 0)\r
- goto Fail;\r
- k = nb - k;\r
- bcount = k;\r
- if (k) {\r
- dest -= k;\r
- pb -= k;\r
- memcpy(dest+1, pb+1, k * sizeof(PyObject *));\r
- nb -= k;\r
- if (nb == 1)\r
- goto CopyA;\r
- /* nb==0 is impossible now if the comparison\r
- * function is consistent, but we can't assume\r
- * that it is.\r
- */\r
- if (nb == 0)\r
- goto Succeed;\r
- }\r
- *dest-- = *pa--;\r
- --na;\r
- if (na == 0)\r
- goto Succeed;\r
- } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);\r
- ++min_gallop; /* penalize it for leaving galloping mode */\r
- ms->min_gallop = min_gallop;\r
- }\r
-Succeed:\r
- result = 0;\r
-Fail:\r
- if (nb)\r
- memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*));\r
- return result;\r
-CopyA:\r
- assert(nb == 1 && na > 0);\r
- /* The first element of pb belongs at the front of the merge. */\r
- dest -= na;\r
- pa -= na;\r
- memmove(dest+1, pa+1, na * sizeof(PyObject *));\r
- *dest = *pb;\r
- return 0;\r
-}\r
-\r
-/* Merge the two runs at stack indices i and i+1.\r
- * Returns 0 on success, -1 on error.\r
- */\r
-static Py_ssize_t\r
-merge_at(MergeState *ms, Py_ssize_t i)\r
-{\r
- PyObject **pa, **pb;\r
- Py_ssize_t na, nb;\r
- Py_ssize_t k;\r
- PyObject *compare;\r
-\r
- assert(ms != NULL);\r
- assert(ms->n >= 2);\r
- assert(i >= 0);\r
- assert(i == ms->n - 2 || i == ms->n - 3);\r
-\r
- pa = ms->pending[i].base;\r
- na = ms->pending[i].len;\r
- pb = ms->pending[i+1].base;\r
- nb = ms->pending[i+1].len;\r
- assert(na > 0 && nb > 0);\r
- assert(pa + na == pb);\r
-\r
- /* Record the length of the combined runs; if i is the 3rd-last\r
- * run now, also slide over the last run (which isn't involved\r
- * in this merge). The current run i+1 goes away in any case.\r
- */\r
- ms->pending[i].len = na + nb;\r
- if (i == ms->n - 3)\r
- ms->pending[i+1] = ms->pending[i+2];\r
- --ms->n;\r
-\r
- /* Where does b start in a? Elements in a before that can be\r
- * ignored (already in place).\r
- */\r
- compare = ms->compare;\r
- k = gallop_right(*pb, pa, na, 0, compare);\r
- if (k < 0)\r
- return -1;\r
- pa += k;\r
- na -= k;\r
- if (na == 0)\r
- return 0;\r
-\r
- /* Where does a end in b? Elements in b after that can be\r
- * ignored (already in place).\r
- */\r
- nb = gallop_left(pa[na-1], pb, nb, nb-1, compare);\r
- if (nb <= 0)\r
- return nb;\r
-\r
- /* Merge what remains of the runs, using a temp array with\r
- * min(na, nb) elements.\r
- */\r
- if (na <= nb)\r
- return merge_lo(ms, pa, na, pb, nb);\r
- else\r
- return merge_hi(ms, pa, na, pb, nb);\r
-}\r
-\r
-/* Examine the stack of runs waiting to be merged, merging adjacent runs\r
- * until the stack invariants are re-established:\r
- *\r
- * 1. len[-3] > len[-2] + len[-1]\r
- * 2. len[-2] > len[-1]\r
- *\r
- * See listsort.txt for more info.\r
- *\r
- * Returns 0 on success, -1 on error.\r
- */\r
-static int\r
-merge_collapse(MergeState *ms)\r
-{\r
- struct s_slice *p = ms->pending;\r
-\r
- assert(ms);\r
- while (ms->n > 1) {\r
- Py_ssize_t n = ms->n - 2;\r
- if ((n > 0 && p[n-1].len <= p[n].len + p[n+1].len) ||\r
- (n > 1 && p[n-2].len <= p[n-1].len + p[n].len)) {\r
- if (p[n-1].len < p[n+1].len)\r
- --n;\r
- if (merge_at(ms, n) < 0)\r
- return -1;\r
- }\r
- else if (p[n].len <= p[n+1].len) {\r
- if (merge_at(ms, n) < 0)\r
- return -1;\r
- }\r
- else\r
- break;\r
- }\r
- return 0;\r
-}\r
-\r
-/* Regardless of invariants, merge all runs on the stack until only one\r
- * remains. This is used at the end of the mergesort.\r
- *\r
- * Returns 0 on success, -1 on error.\r
- */\r
-static int\r
-merge_force_collapse(MergeState *ms)\r
-{\r
- struct s_slice *p = ms->pending;\r
-\r
- assert(ms);\r
- while (ms->n > 1) {\r
- Py_ssize_t n = ms->n - 2;\r
- if (n > 0 && p[n-1].len < p[n+1].len)\r
- --n;\r
- if (merge_at(ms, n) < 0)\r
- return -1;\r
- }\r
- return 0;\r
-}\r
-\r
-/* Compute a good value for the minimum run length; natural runs shorter\r
- * than this are boosted artificially via binary insertion.\r
- *\r
- * If n < 64, return n (it's too small to bother with fancy stuff).\r
- * Else if n is an exact power of 2, return 32.\r
- * Else return an int k, 32 <= k <= 64, such that n/k is close to, but\r
- * strictly less than, an exact power of 2.\r
- *\r
- * See listsort.txt for more info.\r
- */\r
-static Py_ssize_t\r
-merge_compute_minrun(Py_ssize_t n)\r
-{\r
- Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */\r
-\r
- assert(n >= 0);\r
- while (n >= 64) {\r
- r |= n & 1;\r
- n >>= 1;\r
- }\r
- return n + r;\r
-}\r
-\r
-/* Special wrapper to support stable sorting using the decorate-sort-undecorate\r
- pattern. Holds a key which is used for comparisons and the original record\r
- which is returned during the undecorate phase. By exposing only the key\r
- during comparisons, the underlying sort stability characteristics are left\r
- unchanged. Also, if a custom comparison function is used, it will only see\r
- the key instead of a full record. */\r
-\r
-typedef struct {\r
- PyObject_HEAD\r
- PyObject *key;\r
- PyObject *value;\r
-} sortwrapperobject;\r
-\r
-PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key.");\r
-static PyObject *\r
-sortwrapper_richcompare(sortwrapperobject *, sortwrapperobject *, int);\r
-static void\r
-sortwrapper_dealloc(sortwrapperobject *);\r
-\r
-static PyTypeObject sortwrapper_type = {\r
- PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
- "sortwrapper", /* tp_name */\r
- sizeof(sortwrapperobject), /* tp_basicsize */\r
- 0, /* tp_itemsize */\r
- /* methods */\r
- (destructor)sortwrapper_dealloc, /* tp_dealloc */\r
- 0, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- 0, /* tp_repr */\r
- 0, /* tp_as_number */\r
- 0, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- 0, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT |\r
- Py_TPFLAGS_HAVE_RICHCOMPARE, /* tp_flags */\r
- sortwrapper_doc, /* tp_doc */\r
- 0, /* tp_traverse */\r
- 0, /* tp_clear */\r
- (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */\r
-};\r
-\r
-\r
-static PyObject *\r
-sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op)\r
-{\r
- if (!PyObject_TypeCheck(b, &sortwrapper_type)) {\r
- PyErr_SetString(PyExc_TypeError,\r
- "expected a sortwrapperobject");\r
- return NULL;\r
- }\r
- return PyObject_RichCompare(a->key, b->key, op);\r
-}\r
-\r
-static void\r
-sortwrapper_dealloc(sortwrapperobject *so)\r
-{\r
- Py_XDECREF(so->key);\r
- Py_XDECREF(so->value);\r
- PyObject_Del(so);\r
-}\r
-\r
-/* Returns a new reference to a sortwrapper.\r
- Consumes the references to the two underlying objects. */\r
-\r
-static PyObject *\r
-build_sortwrapper(PyObject *key, PyObject *value)\r
-{\r
- sortwrapperobject *so;\r
-\r
- so = PyObject_New(sortwrapperobject, &sortwrapper_type);\r
- if (so == NULL)\r
- return NULL;\r
- so->key = key;\r
- so->value = value;\r
- return (PyObject *)so;\r
-}\r
-\r
-/* Returns a new reference to the value underlying the wrapper. */\r
-static PyObject *\r
-sortwrapper_getvalue(PyObject *so)\r
-{\r
- PyObject *value;\r
-\r
- if (!PyObject_TypeCheck(so, &sortwrapper_type)) {\r
- PyErr_SetString(PyExc_TypeError,\r
- "expected a sortwrapperobject");\r
- return NULL;\r
- }\r
- value = ((sortwrapperobject *)so)->value;\r
- Py_INCREF(value);\r
- return value;\r
-}\r
-\r
-/* Wrapper for user specified cmp functions in combination with a\r
- specified key function. Makes sure the cmp function is presented\r
- with the actual key instead of the sortwrapper */\r
-\r
-typedef struct {\r
- PyObject_HEAD\r
- PyObject *func;\r
-} cmpwrapperobject;\r
-\r
-static void\r
-cmpwrapper_dealloc(cmpwrapperobject *co)\r
-{\r
- Py_XDECREF(co->func);\r
- PyObject_Del(co);\r
-}\r
-\r
-static PyObject *\r
-cmpwrapper_call(cmpwrapperobject *co, PyObject *args, PyObject *kwds)\r
-{\r
- PyObject *x, *y, *xx, *yy;\r
-\r
- if (!PyArg_UnpackTuple(args, "", 2, 2, &x, &y))\r
- return NULL;\r
- if (!PyObject_TypeCheck(x, &sortwrapper_type) ||\r
- !PyObject_TypeCheck(y, &sortwrapper_type)) {\r
- PyErr_SetString(PyExc_TypeError,\r
- "expected a sortwrapperobject");\r
- return NULL;\r
- }\r
- xx = ((sortwrapperobject *)x)->key;\r
- yy = ((sortwrapperobject *)y)->key;\r
- return PyObject_CallFunctionObjArgs(co->func, xx, yy, NULL);\r
-}\r
-\r
-PyDoc_STRVAR(cmpwrapper_doc, "cmp() wrapper for sort with custom keys.");\r
-\r
-static PyTypeObject cmpwrapper_type = {\r
- PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
- "cmpwrapper", /* tp_name */\r
- sizeof(cmpwrapperobject), /* tp_basicsize */\r
- 0, /* tp_itemsize */\r
- /* methods */\r
- (destructor)cmpwrapper_dealloc, /* tp_dealloc */\r
- 0, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- 0, /* tp_repr */\r
- 0, /* tp_as_number */\r
- 0, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- 0, /* tp_hash */\r
- (ternaryfunc)cmpwrapper_call, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT, /* tp_flags */\r
- cmpwrapper_doc, /* tp_doc */\r
-};\r
-\r
-static PyObject *\r
-build_cmpwrapper(PyObject *cmpfunc)\r
-{\r
- cmpwrapperobject *co;\r
-\r
- co = PyObject_New(cmpwrapperobject, &cmpwrapper_type);\r
- if (co == NULL)\r
- return NULL;\r
- Py_INCREF(cmpfunc);\r
- co->func = cmpfunc;\r
- return (PyObject *)co;\r
-}\r
-\r
-/* An adaptive, stable, natural mergesort. See listsort.txt.\r
- * Returns Py_None on success, NULL on error. Even in case of error, the\r
- * list will be some permutation of its input state (nothing is lost or\r
- * duplicated).\r
- */\r
-static PyObject *\r
-listsort(PyListObject *self, PyObject *args, PyObject *kwds)\r
-{\r
- MergeState ms;\r
- PyObject **lo, **hi;\r
- Py_ssize_t nremaining;\r
- Py_ssize_t minrun;\r
- Py_ssize_t saved_ob_size, saved_allocated;\r
- PyObject **saved_ob_item;\r
- PyObject **final_ob_item;\r
- PyObject *compare = NULL;\r
- PyObject *result = NULL; /* guilty until proved innocent */\r
- int reverse = 0;\r
- PyObject *keyfunc = NULL;\r
- Py_ssize_t i;\r
- PyObject *key, *value, *kvpair;\r
- static char *kwlist[] = {"cmp", "key", "reverse", 0};\r
-\r
- assert(self != NULL);\r
- assert (PyList_Check(self));\r
- if (args != NULL) {\r
- if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OOi:sort",\r
- kwlist, &compare, &keyfunc, &reverse))\r
- return NULL;\r
- }\r
- if (compare == Py_None)\r
- compare = NULL;\r
- if (compare != NULL &&\r
- PyErr_WarnPy3k("the cmp argument is not supported in 3.x", 1) < 0)\r
- return NULL;\r
- if (keyfunc == Py_None)\r
- keyfunc = NULL;\r
- if (compare != NULL && keyfunc != NULL) {\r
- compare = build_cmpwrapper(compare);\r
- if (compare == NULL)\r
- return NULL;\r
- } else\r
- Py_XINCREF(compare);\r
-\r
- /* The list is temporarily made empty, so that mutations performed\r
- * by comparison functions can't affect the slice of memory we're\r
- * sorting (allowing mutations during sorting is a core-dump\r
- * factory, since ob_item may change).\r
- */\r
- saved_ob_size = Py_SIZE(self);\r
- saved_ob_item = self->ob_item;\r
- saved_allocated = self->allocated;\r
- Py_SIZE(self) = 0;\r
- self->ob_item = NULL;\r
- self->allocated = -1; /* any operation will reset it to >= 0 */\r
-\r
- if (keyfunc != NULL) {\r
- for (i=0 ; i < saved_ob_size ; i++) {\r
- value = saved_ob_item[i];\r
- key = PyObject_CallFunctionObjArgs(keyfunc, value,\r
- NULL);\r
- if (key == NULL) {\r
- for (i=i-1 ; i>=0 ; i--) {\r
- kvpair = saved_ob_item[i];\r
- value = sortwrapper_getvalue(kvpair);\r
- saved_ob_item[i] = value;\r
- Py_DECREF(kvpair);\r
- }\r
- goto dsu_fail;\r
- }\r
- kvpair = build_sortwrapper(key, value);\r
- if (kvpair == NULL)\r
- goto dsu_fail;\r
- saved_ob_item[i] = kvpair;\r
- }\r
- }\r
-\r
- /* Reverse sort stability achieved by initially reversing the list,\r
- applying a stable forward sort, then reversing the final result. */\r
- if (reverse && saved_ob_size > 1)\r
- reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);\r
-\r
- merge_init(&ms, compare);\r
-\r
- nremaining = saved_ob_size;\r
- if (nremaining < 2)\r
- goto succeed;\r
-\r
- /* March over the array once, left to right, finding natural runs,\r
- * and extending short natural runs to minrun elements.\r
- */\r
- lo = saved_ob_item;\r
- hi = lo + nremaining;\r
- minrun = merge_compute_minrun(nremaining);\r
- do {\r
- int descending;\r
- Py_ssize_t n;\r
-\r
- /* Identify next run. */\r
- n = count_run(lo, hi, compare, &descending);\r
- if (n < 0)\r
- goto fail;\r
- if (descending)\r
- reverse_slice(lo, lo + n);\r
- /* If short, extend to min(minrun, nremaining). */\r
- if (n < minrun) {\r
- const Py_ssize_t force = nremaining <= minrun ?\r
- nremaining : minrun;\r
- if (binarysort(lo, lo + force, lo + n, compare) < 0)\r
- goto fail;\r
- n = force;\r
- }\r
- /* Push run onto pending-runs stack, and maybe merge. */\r
- assert(ms.n < MAX_MERGE_PENDING);\r
- ms.pending[ms.n].base = lo;\r
- ms.pending[ms.n].len = n;\r
- ++ms.n;\r
- if (merge_collapse(&ms) < 0)\r
- goto fail;\r
- /* Advance to find next run. */\r
- lo += n;\r
- nremaining -= n;\r
- } while (nremaining);\r
- assert(lo == hi);\r
-\r
- if (merge_force_collapse(&ms) < 0)\r
- goto fail;\r
- assert(ms.n == 1);\r
- assert(ms.pending[0].base == saved_ob_item);\r
- assert(ms.pending[0].len == saved_ob_size);\r
-\r
-succeed:\r
- result = Py_None;\r
-fail:\r
- if (keyfunc != NULL) {\r
- for (i=0 ; i < saved_ob_size ; i++) {\r
- kvpair = saved_ob_item[i];\r
- value = sortwrapper_getvalue(kvpair);\r
- saved_ob_item[i] = value;\r
- Py_DECREF(kvpair);\r
- }\r
- }\r
-\r
- if (self->allocated != -1 && result != NULL) {\r
- /* The user mucked with the list during the sort,\r
- * and we don't already have another error to report.\r
- */\r
- PyErr_SetString(PyExc_ValueError, "list modified during sort");\r
- result = NULL;\r
- }\r
-\r
- if (reverse && saved_ob_size > 1)\r
- reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);\r
-\r
- merge_freemem(&ms);\r
-\r
-dsu_fail:\r
- final_ob_item = self->ob_item;\r
- i = Py_SIZE(self);\r
- Py_SIZE(self) = saved_ob_size;\r
- self->ob_item = saved_ob_item;\r
- self->allocated = saved_allocated;\r
- if (final_ob_item != NULL) {\r
- /* we cannot use list_clear() for this because it does not\r
- guarantee that the list is really empty when it returns */\r
- while (--i >= 0) {\r
- Py_XDECREF(final_ob_item[i]);\r
- }\r
- PyMem_FREE(final_ob_item);\r
- }\r
- Py_XDECREF(compare);\r
- Py_XINCREF(result);\r
- return result;\r
-}\r
-#undef IFLT\r
-#undef ISLT\r
-\r
-int\r
-PyList_Sort(PyObject *v)\r
-{\r
- if (v == NULL || !PyList_Check(v)) {\r
- PyErr_BadInternalCall();\r
- return -1;\r
- }\r
- v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL);\r
- if (v == NULL)\r
- return -1;\r
- Py_DECREF(v);\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-listreverse(PyListObject *self)\r
-{\r
- if (Py_SIZE(self) > 1)\r
- reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));\r
- Py_RETURN_NONE;\r
-}\r
-\r
-int\r
-PyList_Reverse(PyObject *v)\r
-{\r
- PyListObject *self = (PyListObject *)v;\r
-\r
- if (v == NULL || !PyList_Check(v)) {\r
- PyErr_BadInternalCall();\r
- return -1;\r
- }\r
- if (Py_SIZE(self) > 1)\r
- reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));\r
- return 0;\r
-}\r
-\r
-PyObject *\r
-PyList_AsTuple(PyObject *v)\r
-{\r
- PyObject *w;\r
- PyObject **p, **q;\r
- Py_ssize_t n;\r
- if (v == NULL || !PyList_Check(v)) {\r
- PyErr_BadInternalCall();\r
- return NULL;\r
- }\r
- n = Py_SIZE(v);\r
- w = PyTuple_New(n);\r
- if (w == NULL)\r
- return NULL;\r
- p = ((PyTupleObject *)w)->ob_item;\r
- q = ((PyListObject *)v)->ob_item;\r
- while (--n >= 0) {\r
- Py_INCREF(*q);\r
- *p = *q;\r
- p++;\r
- q++;\r
- }\r
- return w;\r
-}\r
-\r
-static PyObject *\r
-listindex(PyListObject *self, PyObject *args)\r
-{\r
- Py_ssize_t i, start=0, stop=Py_SIZE(self);\r
- PyObject *v, *format_tuple, *err_string;\r
- static PyObject *err_format = NULL;\r
-\r
- if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,\r
- _PyEval_SliceIndex, &start,\r
- _PyEval_SliceIndex, &stop))\r
- return NULL;\r
- if (start < 0) {\r
- start += Py_SIZE(self);\r
- if (start < 0)\r
- start = 0;\r
- }\r
- if (stop < 0) {\r
- stop += Py_SIZE(self);\r
- if (stop < 0)\r
- stop = 0;\r
- }\r
- for (i = start; i < stop && i < Py_SIZE(self); i++) {\r
- int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);\r
- if (cmp > 0)\r
- return PyInt_FromSsize_t(i);\r
- else if (cmp < 0)\r
- return NULL;\r
- }\r
- if (err_format == NULL) {\r
- err_format = PyString_FromString("%r is not in list");\r
- if (err_format == NULL)\r
- return NULL;\r
- }\r
- format_tuple = PyTuple_Pack(1, v);\r
- if (format_tuple == NULL)\r
- return NULL;\r
- err_string = PyString_Format(err_format, format_tuple);\r
- Py_DECREF(format_tuple);\r
- if (err_string == NULL)\r
- return NULL;\r
- PyErr_SetObject(PyExc_ValueError, err_string);\r
- Py_DECREF(err_string);\r
- return NULL;\r
-}\r
-\r
-static PyObject *\r
-listcount(PyListObject *self, PyObject *v)\r
-{\r
- Py_ssize_t count = 0;\r
- Py_ssize_t i;\r
-\r
- for (i = 0; i < Py_SIZE(self); i++) {\r
- int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);\r
- if (cmp > 0)\r
- count++;\r
- else if (cmp < 0)\r
- return NULL;\r
- }\r
- return PyInt_FromSsize_t(count);\r
-}\r
-\r
-static PyObject *\r
-listremove(PyListObject *self, PyObject *v)\r
-{\r
- Py_ssize_t i;\r
-\r
- for (i = 0; i < Py_SIZE(self); i++) {\r
- int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);\r
- if (cmp > 0) {\r
- if (list_ass_slice(self, i, i+1,\r
- (PyObject *)NULL) == 0)\r
- Py_RETURN_NONE;\r
- return NULL;\r
- }\r
- else if (cmp < 0)\r
- return NULL;\r
- }\r
- PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");\r
- return NULL;\r
-}\r
-\r
-static int\r
-list_traverse(PyListObject *o, visitproc visit, void *arg)\r
-{\r
- Py_ssize_t i;\r
-\r
- for (i = Py_SIZE(o); --i >= 0; )\r
- Py_VISIT(o->ob_item[i]);\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-list_richcompare(PyObject *v, PyObject *w, int op)\r
-{\r
- PyListObject *vl, *wl;\r
- Py_ssize_t i;\r
-\r
- if (!PyList_Check(v) || !PyList_Check(w)) {\r
- Py_INCREF(Py_NotImplemented);\r
- return Py_NotImplemented;\r
- }\r
-\r
- vl = (PyListObject *)v;\r
- wl = (PyListObject *)w;\r
-\r
- if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {\r
- /* Shortcut: if the lengths differ, the lists differ */\r
- PyObject *res;\r
- if (op == Py_EQ)\r
- res = Py_False;\r
- else\r
- res = Py_True;\r
- Py_INCREF(res);\r
- return res;\r
- }\r
-\r
- /* Search for the first index where items are different */\r
- for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {\r
- int k = PyObject_RichCompareBool(vl->ob_item[i],\r
- wl->ob_item[i], Py_EQ);\r
- if (k < 0)\r
- return NULL;\r
- if (!k)\r
- break;\r
- }\r
-\r
- if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {\r
- /* No more items to compare -- compare sizes */\r
- Py_ssize_t vs = Py_SIZE(vl);\r
- Py_ssize_t ws = Py_SIZE(wl);\r
- int cmp;\r
- PyObject *res;\r
- switch (op) {\r
- case Py_LT: cmp = vs < ws; break;\r
- case Py_LE: cmp = vs <= ws; break;\r
- case Py_EQ: cmp = vs == ws; break;\r
- case Py_NE: cmp = vs != ws; break;\r
- case Py_GT: cmp = vs > ws; break;\r
- case Py_GE: cmp = vs >= ws; break;\r
- default: return NULL; /* cannot happen */\r
- }\r
- if (cmp)\r
- res = Py_True;\r
- else\r
- res = Py_False;\r
- Py_INCREF(res);\r
- return res;\r
- }\r
-\r
- /* We have an item that differs -- shortcuts for EQ/NE */\r
- if (op == Py_EQ) {\r
- Py_INCREF(Py_False);\r
- return Py_False;\r
- }\r
- if (op == Py_NE) {\r
- Py_INCREF(Py_True);\r
- return Py_True;\r
- }\r
-\r
- /* Compare the final item again using the proper operator */\r
- return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);\r
-}\r
-\r
-static int\r
-list_init(PyListObject *self, PyObject *args, PyObject *kw)\r
-{\r
- PyObject *arg = NULL;\r
- static char *kwlist[] = {"sequence", 0};\r
-\r
- if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))\r
- return -1;\r
-\r
- /* Verify list invariants established by PyType_GenericAlloc() */\r
- assert(0 <= Py_SIZE(self));\r
- assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);\r
- assert(self->ob_item != NULL ||\r
- self->allocated == 0 || self->allocated == -1);\r
-\r
- /* Empty previous contents */\r
- if (self->ob_item != NULL) {\r
- (void)list_clear(self);\r
- }\r
- if (arg != NULL) {\r
- PyObject *rv = listextend(self, arg);\r
- if (rv == NULL)\r
- return -1;\r
- Py_DECREF(rv);\r
- }\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-list_sizeof(PyListObject *self)\r
-{\r
- Py_ssize_t res;\r
-\r
- res = sizeof(PyListObject) + self->allocated * sizeof(void*);\r
- return PyInt_FromSsize_t(res);\r
-}\r
-\r
-static PyObject *list_iter(PyObject *seq);\r
-static PyObject *list_reversed(PyListObject* seq, PyObject* unused);\r
-\r
-PyDoc_STRVAR(getitem_doc,\r
-"x.__getitem__(y) <==> x[y]");\r
-PyDoc_STRVAR(reversed_doc,\r
-"L.__reversed__() -- return a reverse iterator over the list");\r
-PyDoc_STRVAR(sizeof_doc,\r
-"L.__sizeof__() -- size of L in memory, in bytes");\r
-PyDoc_STRVAR(append_doc,\r
-"L.append(object) -- append object to end");\r
-PyDoc_STRVAR(extend_doc,\r
-"L.extend(iterable) -- extend list by appending elements from the iterable");\r
-PyDoc_STRVAR(insert_doc,\r
-"L.insert(index, object) -- insert object before index");\r
-PyDoc_STRVAR(pop_doc,\r
-"L.pop([index]) -> item -- remove and return item at index (default last).\n"\r
-"Raises IndexError if list is empty or index is out of range.");\r
-PyDoc_STRVAR(remove_doc,\r
-"L.remove(value) -- remove first occurrence of value.\n"\r
-"Raises ValueError if the value is not present.");\r
-PyDoc_STRVAR(index_doc,\r
-"L.index(value, [start, [stop]]) -> integer -- return first index of value.\n"\r
-"Raises ValueError if the value is not present.");\r
-PyDoc_STRVAR(count_doc,\r
-"L.count(value) -> integer -- return number of occurrences of value");\r
-PyDoc_STRVAR(reverse_doc,\r
-"L.reverse() -- reverse *IN PLACE*");\r
-PyDoc_STRVAR(sort_doc,\r
-"L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\\r
-cmp(x, y) -> -1, 0, 1");\r
-\r
-static PyObject *list_subscript(PyListObject*, PyObject*);\r
-\r
-static PyMethodDef list_methods[] = {\r
- {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},\r
- {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},\r
- {"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc},\r
- {"append", (PyCFunction)listappend, METH_O, append_doc},\r
- {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},\r
- {"extend", (PyCFunction)listextend, METH_O, extend_doc},\r
- {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},\r
- {"remove", (PyCFunction)listremove, METH_O, remove_doc},\r
- {"index", (PyCFunction)listindex, METH_VARARGS, index_doc},\r
- {"count", (PyCFunction)listcount, METH_O, count_doc},\r
- {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},\r
- {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},\r
- {NULL, NULL} /* sentinel */\r
-};\r
-\r
-static PySequenceMethods list_as_sequence = {\r
- (lenfunc)list_length, /* sq_length */\r
- (binaryfunc)list_concat, /* sq_concat */\r
- (ssizeargfunc)list_repeat, /* sq_repeat */\r
- (ssizeargfunc)list_item, /* sq_item */\r
- (ssizessizeargfunc)list_slice, /* sq_slice */\r
- (ssizeobjargproc)list_ass_item, /* sq_ass_item */\r
- (ssizessizeobjargproc)list_ass_slice, /* sq_ass_slice */\r
- (objobjproc)list_contains, /* sq_contains */\r
- (binaryfunc)list_inplace_concat, /* sq_inplace_concat */\r
- (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */\r
-};\r
-\r
-PyDoc_STRVAR(list_doc,\r
-"list() -> new empty list\n"\r
-"list(iterable) -> new list initialized from iterable's items");\r
-\r
-\r
-static PyObject *\r
-list_subscript(PyListObject* self, PyObject* item)\r
-{\r
- if (PyIndex_Check(item)) {\r
- Py_ssize_t i;\r
- i = PyNumber_AsSsize_t(item, PyExc_IndexError);\r
- if (i == -1 && PyErr_Occurred())\r
- return NULL;\r
- if (i < 0)\r
- i += PyList_GET_SIZE(self);\r
- return list_item(self, i);\r
- }\r
- else if (PySlice_Check(item)) {\r
- Py_ssize_t start, stop, step, slicelength, cur, i;\r
- PyObject* result;\r
- PyObject* it;\r
- PyObject **src, **dest;\r
-\r
- if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),\r
- &start, &stop, &step, &slicelength) < 0) {\r
- return NULL;\r
- }\r
-\r
- if (slicelength <= 0) {\r
- return PyList_New(0);\r
- }\r
- else if (step == 1) {\r
- return list_slice(self, start, stop);\r
- }\r
- else {\r
- result = PyList_New(slicelength);\r
- if (!result) return NULL;\r
-\r
- src = self->ob_item;\r
- dest = ((PyListObject *)result)->ob_item;\r
- for (cur = start, i = 0; i < slicelength;\r
- cur += step, i++) {\r
- it = src[cur];\r
- Py_INCREF(it);\r
- dest[i] = it;\r
- }\r
-\r
- return result;\r
- }\r
- }\r
- else {\r
- PyErr_Format(PyExc_TypeError,\r
- "list indices must be integers, not %.200s",\r
- item->ob_type->tp_name);\r
- return NULL;\r
- }\r
-}\r
-\r
-static int\r
-list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)\r
-{\r
- if (PyIndex_Check(item)) {\r
- Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);\r
- if (i == -1 && PyErr_Occurred())\r
- return -1;\r
- if (i < 0)\r
- i += PyList_GET_SIZE(self);\r
- return list_ass_item(self, i, value);\r
- }\r
- else if (PySlice_Check(item)) {\r
- Py_ssize_t start, stop, step, slicelength;\r
-\r
- if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),\r
- &start, &stop, &step, &slicelength) < 0) {\r
- return -1;\r
- }\r
-\r
- if (step == 1)\r
- return list_ass_slice(self, start, stop, value);\r
-\r
- /* Make sure s[5:2] = [..] inserts at the right place:\r
- before 5, not before 2. */\r
- if ((step < 0 && start < stop) ||\r
- (step > 0 && start > stop))\r
- stop = start;\r
-\r
- if (value == NULL) {\r
- /* delete slice */\r
- PyObject **garbage;\r
- size_t cur;\r
- Py_ssize_t i;\r
-\r
- if (slicelength <= 0)\r
- return 0;\r
-\r
- if (step < 0) {\r
- stop = start + 1;\r
- start = stop + step*(slicelength - 1) - 1;\r
- step = -step;\r
- }\r
-\r
- assert((size_t)slicelength <=\r
- PY_SIZE_MAX / sizeof(PyObject*));\r
-\r
- garbage = (PyObject**)\r
- PyMem_MALLOC(slicelength*sizeof(PyObject*));\r
- if (!garbage) {\r
- PyErr_NoMemory();\r
- return -1;\r
- }\r
-\r
- /* drawing pictures might help understand these for\r
- loops. Basically, we memmove the parts of the\r
- list that are *not* part of the slice: step-1\r
- items for each item that is part of the slice,\r
- and then tail end of the list that was not\r
- covered by the slice */\r
- for (cur = start, i = 0;\r
- cur < (size_t)stop;\r
- cur += step, i++) {\r
- Py_ssize_t lim = step - 1;\r
-\r
- garbage[i] = PyList_GET_ITEM(self, cur);\r
-\r
- if (cur + step >= (size_t)Py_SIZE(self)) {\r
- lim = Py_SIZE(self) - cur - 1;\r
- }\r
-\r
- memmove(self->ob_item + cur - i,\r
- self->ob_item + cur + 1,\r
- lim * sizeof(PyObject *));\r
- }\r
- cur = start + slicelength*step;\r
- if (cur < (size_t)Py_SIZE(self)) {\r
- memmove(self->ob_item + cur - slicelength,\r
- self->ob_item + cur,\r
- (Py_SIZE(self) - cur) *\r
- sizeof(PyObject *));\r
- }\r
-\r
- Py_SIZE(self) -= slicelength;\r
- list_resize(self, Py_SIZE(self));\r
-\r
- for (i = 0; i < slicelength; i++) {\r
- Py_DECREF(garbage[i]);\r
- }\r
- PyMem_FREE(garbage);\r
-\r
- return 0;\r
- }\r
- else {\r
- /* assign slice */\r
- PyObject *ins, *seq;\r
- PyObject **garbage, **seqitems, **selfitems;\r
- Py_ssize_t cur, i;\r
-\r
- /* protect against a[::-1] = a */\r
- if (self == (PyListObject*)value) {\r
- seq = list_slice((PyListObject*)value, 0,\r
- PyList_GET_SIZE(value));\r
- }\r
- else {\r
- seq = PySequence_Fast(value,\r
- "must assign iterable "\r
- "to extended slice");\r
- }\r
- if (!seq)\r
- return -1;\r
-\r
- if (PySequence_Fast_GET_SIZE(seq) != slicelength) {\r
- PyErr_Format(PyExc_ValueError,\r
- "attempt to assign sequence of "\r
- "size %zd to extended slice of "\r
- "size %zd",\r
- PySequence_Fast_GET_SIZE(seq),\r
- slicelength);\r
- Py_DECREF(seq);\r
- return -1;\r
- }\r
-\r
- if (!slicelength) {\r
- Py_DECREF(seq);\r
- return 0;\r
- }\r
-\r
- garbage = (PyObject**)\r
- PyMem_MALLOC(slicelength*sizeof(PyObject*));\r
- if (!garbage) {\r
- Py_DECREF(seq);\r
- PyErr_NoMemory();\r
- return -1;\r
- }\r
-\r
- selfitems = self->ob_item;\r
- seqitems = PySequence_Fast_ITEMS(seq);\r
- for (cur = start, i = 0; i < slicelength;\r
- cur += step, i++) {\r
- garbage[i] = selfitems[cur];\r
- ins = seqitems[i];\r
- Py_INCREF(ins);\r
- selfitems[cur] = ins;\r
- }\r
-\r
- for (i = 0; i < slicelength; i++) {\r
- Py_DECREF(garbage[i]);\r
- }\r
-\r
- PyMem_FREE(garbage);\r
- Py_DECREF(seq);\r
-\r
- return 0;\r
- }\r
- }\r
- else {\r
- PyErr_Format(PyExc_TypeError,\r
- "list indices must be integers, not %.200s",\r
- item->ob_type->tp_name);\r
- return -1;\r
- }\r
-}\r
-\r
-static PyMappingMethods list_as_mapping = {\r
- (lenfunc)list_length,\r
- (binaryfunc)list_subscript,\r
- (objobjargproc)list_ass_subscript\r
-};\r
-\r
-PyTypeObject PyList_Type = {\r
- PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
- "list",\r
- sizeof(PyListObject),\r
- 0,\r
- (destructor)list_dealloc, /* tp_dealloc */\r
- (printfunc)list_print, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- (reprfunc)list_repr, /* tp_repr */\r
- 0, /* tp_as_number */\r
- &list_as_sequence, /* tp_as_sequence */\r
- &list_as_mapping, /* tp_as_mapping */\r
- (hashfunc)PyObject_HashNotImplemented, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |\r
- Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */\r
- list_doc, /* tp_doc */\r
- (traverseproc)list_traverse, /* tp_traverse */\r
- (inquiry)list_clear, /* tp_clear */\r
- list_richcompare, /* tp_richcompare */\r
- 0, /* tp_weaklistoffset */\r
- list_iter, /* tp_iter */\r
- 0, /* tp_iternext */\r
- list_methods, /* tp_methods */\r
- 0, /* tp_members */\r
- 0, /* tp_getset */\r
- 0, /* tp_base */\r
- 0, /* tp_dict */\r
- 0, /* tp_descr_get */\r
- 0, /* tp_descr_set */\r
- 0, /* tp_dictoffset */\r
- (initproc)list_init, /* tp_init */\r
- PyType_GenericAlloc, /* tp_alloc */\r
- PyType_GenericNew, /* tp_new */\r
- PyObject_GC_Del, /* tp_free */\r
-};\r
-\r
-\r
-/*********************** List Iterator **************************/\r
-\r
-typedef struct {\r
- PyObject_HEAD\r
- long it_index;\r
- PyListObject *it_seq; /* Set to NULL when iterator is exhausted */\r
-} listiterobject;\r
-\r
-static PyObject *list_iter(PyObject *);\r
-static void listiter_dealloc(listiterobject *);\r
-static int listiter_traverse(listiterobject *, visitproc, void *);\r
-static PyObject *listiter_next(listiterobject *);\r
-static PyObject *listiter_len(listiterobject *);\r
-\r
-PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");\r
-\r
-static PyMethodDef listiter_methods[] = {\r
- {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},\r
- {NULL, NULL} /* sentinel */\r
-};\r
-\r
-PyTypeObject PyListIter_Type = {\r
- PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
- "listiterator", /* tp_name */\r
- sizeof(listiterobject), /* tp_basicsize */\r
- 0, /* tp_itemsize */\r
- /* methods */\r
- (destructor)listiter_dealloc, /* tp_dealloc */\r
- 0, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- 0, /* tp_repr */\r
- 0, /* tp_as_number */\r
- 0, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- 0, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r
- 0, /* tp_doc */\r
- (traverseproc)listiter_traverse, /* tp_traverse */\r
- 0, /* tp_clear */\r
- 0, /* tp_richcompare */\r
- 0, /* tp_weaklistoffset */\r
- PyObject_SelfIter, /* tp_iter */\r
- (iternextfunc)listiter_next, /* tp_iternext */\r
- listiter_methods, /* tp_methods */\r
- 0, /* tp_members */\r
-};\r
-\r
-\r
-static PyObject *\r
-list_iter(PyObject *seq)\r
-{\r
- listiterobject *it;\r
-\r
- if (!PyList_Check(seq)) {\r
- PyErr_BadInternalCall();\r
- return NULL;\r
- }\r
- it = PyObject_GC_New(listiterobject, &PyListIter_Type);\r
- if (it == NULL)\r
- return NULL;\r
- it->it_index = 0;\r
- Py_INCREF(seq);\r
- it->it_seq = (PyListObject *)seq;\r
- _PyObject_GC_TRACK(it);\r
- return (PyObject *)it;\r
-}\r
-\r
-static void\r
-listiter_dealloc(listiterobject *it)\r
-{\r
- _PyObject_GC_UNTRACK(it);\r
- Py_XDECREF(it->it_seq);\r
- PyObject_GC_Del(it);\r
-}\r
-\r
-static int\r
-listiter_traverse(listiterobject *it, visitproc visit, void *arg)\r
-{\r
- Py_VISIT(it->it_seq);\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-listiter_next(listiterobject *it)\r
-{\r
- PyListObject *seq;\r
- PyObject *item;\r
-\r
- assert(it != NULL);\r
- seq = it->it_seq;\r
- if (seq == NULL)\r
- return NULL;\r
- assert(PyList_Check(seq));\r
-\r
- if (it->it_index < PyList_GET_SIZE(seq)) {\r
- item = PyList_GET_ITEM(seq, it->it_index);\r
- ++it->it_index;\r
- Py_INCREF(item);\r
- return item;\r
- }\r
-\r
- Py_DECREF(seq);\r
- it->it_seq = NULL;\r
- return NULL;\r
-}\r
-\r
-static PyObject *\r
-listiter_len(listiterobject *it)\r
-{\r
- Py_ssize_t len;\r
- if (it->it_seq) {\r
- len = PyList_GET_SIZE(it->it_seq) - it->it_index;\r
- if (len >= 0)\r
- return PyInt_FromSsize_t(len);\r
- }\r
- return PyInt_FromLong(0);\r
-}\r
-/*********************** List Reverse Iterator **************************/\r
-\r
-typedef struct {\r
- PyObject_HEAD\r
- Py_ssize_t it_index;\r
- PyListObject *it_seq; /* Set to NULL when iterator is exhausted */\r
-} listreviterobject;\r
-\r
-static PyObject *list_reversed(PyListObject *, PyObject *);\r
-static void listreviter_dealloc(listreviterobject *);\r
-static int listreviter_traverse(listreviterobject *, visitproc, void *);\r
-static PyObject *listreviter_next(listreviterobject *);\r
-static PyObject *listreviter_len(listreviterobject *);\r
-\r
-static PyMethodDef listreviter_methods[] = {\r
- {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},\r
- {NULL, NULL} /* sentinel */\r
-};\r
-\r
-PyTypeObject PyListRevIter_Type = {\r
- PyVarObject_HEAD_INIT(&PyType_Type, 0)\r
- "listreverseiterator", /* tp_name */\r
- sizeof(listreviterobject), /* tp_basicsize */\r
- 0, /* tp_itemsize */\r
- /* methods */\r
- (destructor)listreviter_dealloc, /* tp_dealloc */\r
- 0, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- 0, /* tp_repr */\r
- 0, /* tp_as_number */\r
- 0, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- 0, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r
- 0, /* tp_doc */\r
- (traverseproc)listreviter_traverse, /* tp_traverse */\r
- 0, /* tp_clear */\r
- 0, /* tp_richcompare */\r
- 0, /* tp_weaklistoffset */\r
- PyObject_SelfIter, /* tp_iter */\r
- (iternextfunc)listreviter_next, /* tp_iternext */\r
- listreviter_methods, /* tp_methods */\r
- 0,\r
-};\r
-\r
-static PyObject *\r
-list_reversed(PyListObject *seq, PyObject *unused)\r
-{\r
- listreviterobject *it;\r
-\r
- it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);\r
- if (it == NULL)\r
- return NULL;\r
- assert(PyList_Check(seq));\r
- it->it_index = PyList_GET_SIZE(seq) - 1;\r
- Py_INCREF(seq);\r
- it->it_seq = seq;\r
- PyObject_GC_Track(it);\r
- return (PyObject *)it;\r
-}\r
-\r
-static void\r
-listreviter_dealloc(listreviterobject *it)\r
-{\r
- PyObject_GC_UnTrack(it);\r
- Py_XDECREF(it->it_seq);\r
- PyObject_GC_Del(it);\r
-}\r
-\r
-static int\r
-listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)\r
-{\r
- Py_VISIT(it->it_seq);\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-listreviter_next(listreviterobject *it)\r
-{\r
- PyObject *item;\r
- Py_ssize_t index = it->it_index;\r
- PyListObject *seq = it->it_seq;\r
-\r
- if (index>=0 && index < PyList_GET_SIZE(seq)) {\r
- item = PyList_GET_ITEM(seq, index);\r
- it->it_index--;\r
- Py_INCREF(item);\r
- return item;\r
- }\r
- it->it_index = -1;\r
- if (seq != NULL) {\r
- it->it_seq = NULL;\r
- Py_DECREF(seq);\r
- }\r
- return NULL;\r
-}\r
-\r
-static PyObject *\r
-listreviter_len(listreviterobject *it)\r
-{\r
- Py_ssize_t len = it->it_index + 1;\r
- if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)\r
- len = 0;\r
- return PyLong_FromSsize_t(len);\r
-}\r
projects / mirror_edk2.git / blobdiff