diff options
Diffstat (limited to 'Objects/listobject.c')
| -rw-r--r-- | Objects/listobject.c | 4206 |
1 files changed, 2103 insertions, 2103 deletions
diff --git a/Objects/listobject.c b/Objects/listobject.c index d3c997a..e8b21f1 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -5,7 +5,7 @@ #ifdef STDC_HEADERS #include <stddef.h> #else -#include <sys/types.h> /* For size_t */ +#include <sys/types.h> /* For size_t */ #endif /* Ensure ob_item has room for at least newsize elements, and set @@ -24,52 +24,52 @@ static int list_resize(PyListObject *self, Py_ssize_t newsize) { - PyObject **items; - size_t new_allocated; - Py_ssize_t allocated = self->allocated; - - /* Bypass realloc() when a previous overallocation is large enough - to accommodate the newsize. If the newsize falls lower than half - the allocated size, then proceed with the realloc() to shrink the list. - */ - if (allocated >= newsize && newsize >= (allocated >> 1)) { - assert(self->ob_item != NULL || newsize == 0); - Py_SIZE(self) = newsize; - return 0; - } - - /* This over-allocates proportional to the list size, making room - * for additional growth. The over-allocation is mild, but is - * enough to give linear-time amortized behavior over a long - * sequence of appends() in the presence of a poorly-performing - * system realloc(). - * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... - */ - new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); - - /* check for integer overflow */ - if (new_allocated > PY_SIZE_MAX - newsize) { - PyErr_NoMemory(); - return -1; - } else { - new_allocated += newsize; - } - - if (newsize == 0) - new_allocated = 0; - items = self->ob_item; - if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *))) - PyMem_RESIZE(items, PyObject *, new_allocated); - else - items = NULL; - if (items == NULL) { - PyErr_NoMemory(); - return -1; - } - self->ob_item = items; - Py_SIZE(self) = newsize; - self->allocated = new_allocated; - return 0; + PyObject **items; + size_t new_allocated; + Py_ssize_t allocated = self->allocated; + + /* Bypass realloc() when a previous overallocation is large enough + to accommodate the newsize. If the newsize falls lower than half + the allocated size, then proceed with the realloc() to shrink the list. + */ + if (allocated >= newsize && newsize >= (allocated >> 1)) { + assert(self->ob_item != NULL || newsize == 0); + Py_SIZE(self) = newsize; + return 0; + } + + /* This over-allocates proportional to the list size, making room + * for additional growth. The over-allocation is mild, but is + * enough to give linear-time amortized behavior over a long + * sequence of appends() in the presence of a poorly-performing + * system realloc(). + * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... + */ + new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); + + /* check for integer overflow */ + if (new_allocated > PY_SIZE_MAX - newsize) { + PyErr_NoMemory(); + return -1; + } else { + new_allocated += newsize; + } + + if (newsize == 0) + new_allocated = 0; + items = self->ob_item; + if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *))) + PyMem_RESIZE(items, PyObject *, new_allocated); + else + items = NULL; + if (items == NULL) { + PyErr_NoMemory(); + return -1; + } + self->ob_item = items; + Py_SIZE(self) = newsize; + self->allocated = new_allocated; + return 0; } /* Debug statistic to compare allocations with reuse through the free list */ @@ -81,12 +81,12 @@ static size_t count_reuse = 0; static void show_alloc(void) { - fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n", - count_alloc); - fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T - "d\n", count_reuse); - fprintf(stderr, "%.2f%% reuse rate\n\n", - (100.0*count_reuse/(count_alloc+count_reuse))); + fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n", + count_alloc); + fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T + "d\n", count_reuse); + fprintf(stderr, "%.2f%% reuse rate\n\n", + (100.0*count_reuse/(count_alloc+count_reuse))); } #endif @@ -100,77 +100,77 @@ static int numfree = 0; void PyList_Fini(void) { - PyListObject *op; + PyListObject *op; - while (numfree) { - op = free_list[--numfree]; - assert(PyList_CheckExact(op)); - PyObject_GC_Del(op); - } + while (numfree) { + op = free_list[--numfree]; + assert(PyList_CheckExact(op)); + PyObject_GC_Del(op); + } } PyObject * PyList_New(Py_ssize_t size) { - PyListObject *op; - size_t nbytes; + PyListObject *op; + size_t nbytes; #ifdef SHOW_ALLOC_COUNT - static int initialized = 0; - if (!initialized) { - Py_AtExit(show_alloc); - initialized = 1; - } + static int initialized = 0; + if (!initialized) { + Py_AtExit(show_alloc); + initialized = 1; + } #endif - if (size < 0) { - PyErr_BadInternalCall(); - return NULL; - } - /* Check for overflow without an actual overflow, - * which can cause compiler to optimise out */ - if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *)) - return PyErr_NoMemory(); - nbytes = size * sizeof(PyObject *); - if (numfree) { - numfree--; - op = free_list[numfree]; - _Py_NewReference((PyObject *)op); + if (size < 0) { + PyErr_BadInternalCall(); + return NULL; + } + /* Check for overflow without an actual overflow, + * which can cause compiler to optimise out */ + if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *)) + return PyErr_NoMemory(); + nbytes = size * sizeof(PyObject *); + if (numfree) { + numfree--; + op = free_list[numfree]; + _Py_NewReference((PyObject *)op); #ifdef SHOW_ALLOC_COUNT - count_reuse++; + count_reuse++; #endif - } else { - op = PyObject_GC_New(PyListObject, &PyList_Type); - if (op == NULL) - return NULL; + } else { + op = PyObject_GC_New(PyListObject, &PyList_Type); + if (op == NULL) + return NULL; #ifdef SHOW_ALLOC_COUNT - count_alloc++; + count_alloc++; #endif - } - if (size <= 0) - op->ob_item = NULL; - else { - op->ob_item = (PyObject **) PyMem_MALLOC(nbytes); - if (op->ob_item == NULL) { - Py_DECREF(op); - return PyErr_NoMemory(); - } - memset(op->ob_item, 0, nbytes); - } - Py_SIZE(op) = size; - op->allocated = size; - _PyObject_GC_TRACK(op); - return (PyObject *) op; + } + if (size <= 0) + op->ob_item = NULL; + else { + op->ob_item = (PyObject **) PyMem_MALLOC(nbytes); + if (op->ob_item == NULL) { + Py_DECREF(op); + return PyErr_NoMemory(); + } + memset(op->ob_item, 0, nbytes); + } + Py_SIZE(op) = size; + op->allocated = size; + _PyObject_GC_TRACK(op); + return (PyObject *) op; } Py_ssize_t PyList_Size(PyObject *op) { - if (!PyList_Check(op)) { - PyErr_BadInternalCall(); - return -1; - } - else - return Py_SIZE(op); + if (!PyList_Check(op)) { + PyErr_BadInternalCall(); + return -1; + } + else + return Py_SIZE(op); } static PyObject *indexerr = NULL; @@ -178,117 +178,117 @@ static PyObject *indexerr = NULL; PyObject * PyList_GetItem(PyObject *op, Py_ssize_t i) { - if (!PyList_Check(op)) { - PyErr_BadInternalCall(); - return NULL; - } - if (i < 0 || i >= Py_SIZE(op)) { - if (indexerr == NULL) { - indexerr = PyUnicode_FromString( - "list index out of range"); - if (indexerr == NULL) - return NULL; - } - PyErr_SetObject(PyExc_IndexError, indexerr); - return NULL; - } - return ((PyListObject *)op) -> ob_item[i]; + if (!PyList_Check(op)) { + PyErr_BadInternalCall(); + return NULL; + } + if (i < 0 || i >= Py_SIZE(op)) { + if (indexerr == NULL) { + indexerr = PyUnicode_FromString( + "list index out of range"); + if (indexerr == NULL) + return NULL; + } + PyErr_SetObject(PyExc_IndexError, indexerr); + return NULL; + } + return ((PyListObject *)op) -> ob_item[i]; } int PyList_SetItem(register PyObject *op, register Py_ssize_t i, register PyObject *newitem) { - register PyObject *olditem; - register PyObject **p; - if (!PyList_Check(op)) { - Py_XDECREF(newitem); - PyErr_BadInternalCall(); - return -1; - } - if (i < 0 || i >= Py_SIZE(op)) { - Py_XDECREF(newitem); - PyErr_SetString(PyExc_IndexError, - "list assignment index out of range"); - return -1; - } - p = ((PyListObject *)op) -> ob_item + i; - olditem = *p; - *p = newitem; - Py_XDECREF(olditem); - return 0; + register PyObject *olditem; + register PyObject **p; + if (!PyList_Check(op)) { + Py_XDECREF(newitem); + PyErr_BadInternalCall(); + return -1; + } + if (i < 0 || i >= Py_SIZE(op)) { + Py_XDECREF(newitem); + PyErr_SetString(PyExc_IndexError, + "list assignment index out of range"); + return -1; + } + p = ((PyListObject *)op) -> ob_item + i; + olditem = *p; + *p = newitem; + Py_XDECREF(olditem); + return 0; } static int ins1(PyListObject *self, Py_ssize_t where, PyObject *v) { - Py_ssize_t i, n = Py_SIZE(self); - PyObject **items; - if (v == NULL) { - PyErr_BadInternalCall(); - return -1; - } - if (n == PY_SSIZE_T_MAX) { - PyErr_SetString(PyExc_OverflowError, - "cannot add more objects to list"); - return -1; - } - - if (list_resize(self, n+1) == -1) - return -1; - - if (where < 0) { - where += n; - if (where < 0) - where = 0; - } - if (where > n) - where = n; - items = self->ob_item; - for (i = n; --i >= where; ) - items[i+1] = items[i]; - Py_INCREF(v); - items[where] = v; - return 0; + Py_ssize_t i, n = Py_SIZE(self); + PyObject **items; + if (v == NULL) { + PyErr_BadInternalCall(); + return -1; + } + if (n == PY_SSIZE_T_MAX) { + PyErr_SetString(PyExc_OverflowError, + "cannot add more objects to list"); + return -1; + } + + if (list_resize(self, n+1) == -1) + return -1; + + if (where < 0) { + where += n; + if (where < 0) + where = 0; + } + if (where > n) + where = n; + items = self->ob_item; + for (i = n; --i >= where; ) + items[i+1] = items[i]; + Py_INCREF(v); + items[where] = v; + return 0; } int PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem) { - if (!PyList_Check(op)) { - PyErr_BadInternalCall(); - return -1; - } - return ins1((PyListObject *)op, where, newitem); + if (!PyList_Check(op)) { + PyErr_BadInternalCall(); + return -1; + } + return ins1((PyListObject *)op, where, newitem); } static int app1(PyListObject *self, PyObject *v) { - Py_ssize_t n = PyList_GET_SIZE(self); + Py_ssize_t n = PyList_GET_SIZE(self); - assert (v != NULL); - if (n == PY_SSIZE_T_MAX) { - PyErr_SetString(PyExc_OverflowError, - "cannot add more objects to list"); - return -1; - } + assert (v != NULL); + if (n == PY_SSIZE_T_MAX) { + PyErr_SetString(PyExc_OverflowError, + "cannot add more objects to list"); + return -1; + } - if (list_resize(self, n+1) == -1) - return -1; + if (list_resize(self, n+1) == -1) + return -1; - Py_INCREF(v); - PyList_SET_ITEM(self, n, v); - return 0; + Py_INCREF(v); + PyList_SET_ITEM(self, n, v); + return 0; } int PyList_Append(PyObject *op, PyObject *newitem) { - if (PyList_Check(op) && (newitem != NULL)) - return app1((PyListObject *)op, newitem); - PyErr_BadInternalCall(); - return -1; + if (PyList_Check(op) && (newitem != NULL)) + return app1((PyListObject *)op, newitem); + PyErr_BadInternalCall(); + return -1; } /* Methods */ @@ -296,271 +296,271 @@ PyList_Append(PyObject *op, PyObject *newitem) static void list_dealloc(PyListObject *op) { - Py_ssize_t i; - PyObject_GC_UnTrack(op); - Py_TRASHCAN_SAFE_BEGIN(op) - if (op->ob_item != NULL) { - /* Do it backwards, for Christian Tismer. - There's a simple test case where somehow this reduces - thrashing when a *very* large list is created and - immediately deleted. */ - i = Py_SIZE(op); - while (--i >= 0) { - Py_XDECREF(op->ob_item[i]); - } - PyMem_FREE(op->ob_item); - } - if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) - free_list[numfree++] = op; - else - Py_TYPE(op)->tp_free((PyObject *)op); - Py_TRASHCAN_SAFE_END(op) + Py_ssize_t i; + PyObject_GC_UnTrack(op); + Py_TRASHCAN_SAFE_BEGIN(op) + if (op->ob_item != NULL) { + /* Do it backwards, for Christian Tismer. + There's a simple test case where somehow this reduces + thrashing when a *very* large list is created and + immediately deleted. */ + i = Py_SIZE(op); + while (--i >= 0) { + Py_XDECREF(op->ob_item[i]); + } + PyMem_FREE(op->ob_item); + } + if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) + free_list[numfree++] = op; + else + Py_TYPE(op)->tp_free((PyObject *)op); + Py_TRASHCAN_SAFE_END(op) } static PyObject * list_repr(PyListObject *v) { - Py_ssize_t i; - PyObject *s, *temp; - PyObject *pieces = NULL, *result = NULL; - - i = Py_ReprEnter((PyObject*)v); - if (i != 0) { - return i > 0 ? PyUnicode_FromString("[...]") : NULL; - } - - if (Py_SIZE(v) == 0) { - result = PyUnicode_FromString("[]"); - goto Done; - } - - pieces = PyList_New(0); - if (pieces == NULL) - goto Done; - - /* Do repr() on each element. Note that this may mutate the list, - so must refetch the list size on each iteration. */ - for (i = 0; i < Py_SIZE(v); ++i) { - int status; - if (Py_EnterRecursiveCall(" while getting the repr of a list")) - goto Done; - s = PyObject_Repr(v->ob_item[i]); - Py_LeaveRecursiveCall(); - if (s == NULL) - goto Done; - status = PyList_Append(pieces, s); - Py_DECREF(s); /* append created a new ref */ - if (status < 0) - goto Done; - } - - /* Add "[]" decorations to the first and last items. */ - assert(PyList_GET_SIZE(pieces) > 0); - s = PyUnicode_FromString("["); - if (s == NULL) - goto Done; - temp = PyList_GET_ITEM(pieces, 0); - PyUnicode_AppendAndDel(&s, temp); - PyList_SET_ITEM(pieces, 0, s); - if (s == NULL) - goto Done; - - s = PyUnicode_FromString("]"); - if (s == NULL) - goto Done; - temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1); - PyUnicode_AppendAndDel(&temp, s); - PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp); - if (temp == NULL) - goto Done; - - /* Paste them all together with ", " between. */ - s = PyUnicode_FromString(", "); - if (s == NULL) - goto Done; - result = PyUnicode_Join(s, pieces); - Py_DECREF(s); + Py_ssize_t i; + PyObject *s, *temp; + PyObject *pieces = NULL, *result = NULL; + + i = Py_ReprEnter((PyObject*)v); + if (i != 0) { + return i > 0 ? PyUnicode_FromString("[...]") : NULL; + } + + if (Py_SIZE(v) == 0) { + result = PyUnicode_FromString("[]"); + goto Done; + } + + pieces = PyList_New(0); + if (pieces == NULL) + goto Done; + + /* Do repr() on each element. Note that this may mutate the list, + so must refetch the list size on each iteration. */ + for (i = 0; i < Py_SIZE(v); ++i) { + int status; + if (Py_EnterRecursiveCall(" while getting the repr of a list")) + goto Done; + s = PyObject_Repr(v->ob_item[i]); + Py_LeaveRecursiveCall(); + if (s == NULL) + goto Done; + status = PyList_Append(pieces, s); + Py_DECREF(s); /* append created a new ref */ + if (status < 0) + goto Done; + } + + /* Add "[]" decorations to the first and last items. */ + assert(PyList_GET_SIZE(pieces) > 0); + s = PyUnicode_FromString("["); + if (s == NULL) + goto Done; + temp = PyList_GET_ITEM(pieces, 0); + PyUnicode_AppendAndDel(&s, temp); + PyList_SET_ITEM(pieces, 0, s); + if (s == NULL) + goto Done; + + s = PyUnicode_FromString("]"); + if (s == NULL) + goto Done; + temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1); + PyUnicode_AppendAndDel(&temp, s); + PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp); + if (temp == NULL) + goto Done; + + /* Paste them all together with ", " between. */ + s = PyUnicode_FromString(", "); + if (s == NULL) + goto Done; + result = PyUnicode_Join(s, pieces); + Py_DECREF(s); Done: - Py_XDECREF(pieces); - Py_ReprLeave((PyObject *)v); - return result; + Py_XDECREF(pieces); + Py_ReprLeave((PyObject *)v); + return result; } static Py_ssize_t list_length(PyListObject *a) { - return Py_SIZE(a); + return Py_SIZE(a); } static int list_contains(PyListObject *a, PyObject *el) { - Py_ssize_t i; - int cmp; + Py_ssize_t i; + int cmp; - for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) - cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i), - Py_EQ); - return cmp; + for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) + cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i), + Py_EQ); + return cmp; } static PyObject * list_item(PyListObject *a, Py_ssize_t i) { - if (i < 0 || i >= Py_SIZE(a)) { - if (indexerr == NULL) { - indexerr = PyUnicode_FromString( - "list index out of range"); - if (indexerr == NULL) - return NULL; - } - PyErr_SetObject(PyExc_IndexError, indexerr); - return NULL; - } - Py_INCREF(a->ob_item[i]); - return a->ob_item[i]; + if (i < 0 || i >= Py_SIZE(a)) { + if (indexerr == NULL) { + indexerr = PyUnicode_FromString( + "list index out of range"); + if (indexerr == NULL) + return NULL; + } + PyErr_SetObject(PyExc_IndexError, indexerr); + return NULL; + } + Py_INCREF(a->ob_item[i]); + return a->ob_item[i]; } static PyObject * list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh) { - PyListObject *np; - PyObject **src, **dest; - Py_ssize_t i, len; - if (ilow < 0) - ilow = 0; - else if (ilow > Py_SIZE(a)) - ilow = Py_SIZE(a); - if (ihigh < ilow) - ihigh = ilow; - else if (ihigh > Py_SIZE(a)) - ihigh = Py_SIZE(a); - len = ihigh - ilow; - np = (PyListObject *) PyList_New(len); - if (np == NULL) - return NULL; - - src = a->ob_item + ilow; - dest = np->ob_item; - for (i = 0; i < len; i++) { - PyObject *v = src[i]; - Py_INCREF(v); - dest[i] = v; - } - return (PyObject *)np; + PyListObject *np; + PyObject **src, **dest; + Py_ssize_t i, len; + if (ilow < 0) + ilow = 0; + else if (ilow > Py_SIZE(a)) + ilow = Py_SIZE(a); + if (ihigh < ilow) + ihigh = ilow; + else if (ihigh > Py_SIZE(a)) + ihigh = Py_SIZE(a); + len = ihigh - ilow; + np = (PyListObject *) PyList_New(len); + if (np == NULL) + return NULL; + + src = a->ob_item + ilow; + dest = np->ob_item; + for (i = 0; i < len; i++) { + PyObject *v = src[i]; + Py_INCREF(v); + dest[i] = v; + } + return (PyObject *)np; } PyObject * PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh) { - if (!PyList_Check(a)) { - PyErr_BadInternalCall(); - return NULL; - } - return list_slice((PyListObject *)a, ilow, ihigh); + if (!PyList_Check(a)) { + PyErr_BadInternalCall(); + return NULL; + } + return list_slice((PyListObject *)a, ilow, ihigh); } static PyObject * list_concat(PyListObject *a, PyObject *bb) { - Py_ssize_t size; - Py_ssize_t i; - PyObject **src, **dest; - PyListObject *np; - if (!PyList_Check(bb)) { - PyErr_Format(PyExc_TypeError, - "can only concatenate list (not \"%.200s\") to list", - bb->ob_type->tp_name); - return NULL; - } + Py_ssize_t size; + Py_ssize_t i; + PyObject **src, **dest; + PyListObject *np; + if (!PyList_Check(bb)) { + PyErr_Format(PyExc_TypeError, + "can only concatenate list (not \"%.200s\") to list", + bb->ob_type->tp_name); + return NULL; + } #define b ((PyListObject *)bb) - size = Py_SIZE(a) + Py_SIZE(b); - if (size < 0) - return PyErr_NoMemory(); - np = (PyListObject *) PyList_New(size); - if (np == NULL) { - return NULL; - } - src = a->ob_item; - dest = np->ob_item; - for (i = 0; i < Py_SIZE(a); i++) { - PyObject *v = src[i]; - Py_INCREF(v); - dest[i] = v; - } - src = b->ob_item; - dest = np->ob_item + Py_SIZE(a); - for (i = 0; i < Py_SIZE(b); i++) { - PyObject *v = src[i]; - Py_INCREF(v); - dest[i] = v; - } - return (PyObject *)np; + size = Py_SIZE(a) + Py_SIZE(b); + if (size < 0) + return PyErr_NoMemory(); + np = (PyListObject *) PyList_New(size); + if (np == NULL) { + return NULL; + } + src = a->ob_item; + dest = np->ob_item; + for (i = 0; i < Py_SIZE(a); i++) { + PyObject *v = src[i]; + Py_INCREF(v); + dest[i] = v; + } + src = b->ob_item; + dest = np->ob_item + Py_SIZE(a); + for (i = 0; i < Py_SIZE(b); i++) { + PyObject *v = src[i]; + Py_INCREF(v); + dest[i] = v; + } + return (PyObject *)np; #undef b } static PyObject * list_repeat(PyListObject *a, Py_ssize_t n) { - Py_ssize_t i, j; - Py_ssize_t size; - PyListObject *np; - PyObject **p, **items; - PyObject *elem; - if (n < 0) - n = 0; - size = Py_SIZE(a) * n; - if (n && size/n != Py_SIZE(a)) - return PyErr_NoMemory(); - if (size == 0) - return PyList_New(0); - np = (PyListObject *) PyList_New(size); - if (np == NULL) - return NULL; - - items = np->ob_item; - if (Py_SIZE(a) == 1) { - elem = a->ob_item[0]; - for (i = 0; i < n; i++) { - items[i] = elem; - Py_INCREF(elem); - } - return (PyObject *) np; - } - p = np->ob_item; - items = a->ob_item; - for (i = 0; i < n; i++) { - for (j = 0; j < Py_SIZE(a); j++) { - *p = items[j]; - Py_INCREF(*p); - p++; - } - } - return (PyObject *) np; + Py_ssize_t i, j; + Py_ssize_t size; + PyListObject *np; + PyObject **p, **items; + PyObject *elem; + if (n < 0) + n = 0; + size = Py_SIZE(a) * n; + if (n && size/n != Py_SIZE(a)) + return PyErr_NoMemory(); + if (size == 0) + return PyList_New(0); + np = (PyListObject *) PyList_New(size); + if (np == NULL) + return NULL; + + items = np->ob_item; + if (Py_SIZE(a) == 1) { + elem = a->ob_item[0]; + for (i = 0; i < n; i++) { + items[i] = elem; + Py_INCREF(elem); + } + return (PyObject *) np; + } + p = np->ob_item; + items = a->ob_item; + for (i = 0; i < n; i++) { + for (j = 0; j < Py_SIZE(a); j++) { + *p = items[j]; + Py_INCREF(*p); + p++; + } + } + return (PyObject *) np; } static int list_clear(PyListObject *a) { - Py_ssize_t i; - PyObject **item = a->ob_item; - if (item != NULL) { - /* Because XDECREF can recursively invoke operations on - this list, we make it empty first. */ - i = Py_SIZE(a); - Py_SIZE(a) = 0; - a->ob_item = NULL; - a->allocated = 0; - while (--i >= 0) { - Py_XDECREF(item[i]); - } - PyMem_FREE(item); - } - /* Never fails; the return value can be ignored. - Note that there is no guarantee that the list is actually empty - at this point, because XDECREF may have populated it again! */ - return 0; + Py_ssize_t i; + PyObject **item = a->ob_item; + if (item != NULL) { + /* Because XDECREF can recursively invoke operations on + this list, we make it empty first. */ + i = Py_SIZE(a); + Py_SIZE(a) = 0; + a->ob_item = NULL; + a->allocated = 0; + while (--i >= 0) { + Py_XDECREF(item[i]); + } + PyMem_FREE(item); + } + /* Never fails; the return value can be ignored. + Note that there is no guarantee that the list is actually empty + at this point, because XDECREF may have populated it again! */ + return 0; } /* a[ilow:ihigh] = v if v != NULL. @@ -572,368 +572,368 @@ list_clear(PyListObject *a) static int list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v) { - /* Because [X]DECREF can recursively invoke list operations on - this list, we must postpone all [X]DECREF activity until - after the list is back in its canonical shape. Therefore - we must allocate an additional array, 'recycle', into which - we temporarily copy the items that are deleted from the - list. :-( */ - PyObject *recycle_on_stack[8]; - PyObject **recycle = recycle_on_stack; /* will allocate more if needed */ - PyObject **item; - PyObject **vitem = NULL; - PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */ - Py_ssize_t n; /* # of elements in replacement list */ - Py_ssize_t norig; /* # of elements in list getting replaced */ - Py_ssize_t d; /* Change in size */ - Py_ssize_t k; - size_t s; - int result = -1; /* guilty until proved innocent */ + /* Because [X]DECREF can recursively invoke list operations on + this list, we must postpone all [X]DECREF activity until + after the list is back in its canonical shape. Therefore + we must allocate an additional array, 'recycle', into which + we temporarily copy the items that are deleted from the + list. :-( */ + PyObject *recycle_on_stack[8]; + PyObject **recycle = recycle_on_stack; /* will allocate more if needed */ + PyObject **item; + PyObject **vitem = NULL; + PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */ + Py_ssize_t n; /* # of elements in replacement list */ + Py_ssize_t norig; /* # of elements in list getting replaced */ + Py_ssize_t d; /* Change in size */ + Py_ssize_t k; + size_t s; + int result = -1; /* guilty until proved innocent */ #define b ((PyListObject *)v) - if (v == NULL) - n = 0; - else { - if (a == b) { - /* Special case "a[i:j] = a" -- copy b first */ - v = list_slice(b, 0, Py_SIZE(b)); - if (v == NULL) - return result; - result = list_ass_slice(a, ilow, ihigh, v); - Py_DECREF(v); - return result; - } - v_as_SF = PySequence_Fast(v, "can only assign an iterable"); - if(v_as_SF == NULL) - goto Error; - n = PySequence_Fast_GET_SIZE(v_as_SF); - vitem = PySequence_Fast_ITEMS(v_as_SF); - } - if (ilow < 0) - ilow = 0; - else if (ilow > Py_SIZE(a)) - ilow = Py_SIZE(a); - - if (ihigh < ilow) - ihigh = ilow; - else if (ihigh > Py_SIZE(a)) - ihigh = Py_SIZE(a); - - norig = ihigh - ilow; - assert(norig >= 0); - d = n - norig; - if (Py_SIZE(a) + d == 0) { - Py_XDECREF(v_as_SF); - return list_clear(a); - } - item = a->ob_item; - /* recycle the items that we are about to remove */ - s = norig * sizeof(PyObject *); - if (s > sizeof(recycle_on_stack)) { - recycle = (PyObject **)PyMem_MALLOC(s); - if (recycle == NULL) { - PyErr_NoMemory(); - goto Error; - } - } - memcpy(recycle, &item[ilow], s); - - if (d < 0) { /* Delete -d items */ - memmove(&item[ihigh+d], &item[ihigh], - (Py_SIZE(a) - ihigh)*sizeof(PyObject *)); - list_resize(a, Py_SIZE(a) + d); - item = a->ob_item; - } - else if (d > 0) { /* Insert d items */ - k = Py_SIZE(a); - if (list_resize(a, k+d) < 0) - goto Error; - item = a->ob_item; - memmove(&item[ihigh+d], &item[ihigh], - (k - ihigh)*sizeof(PyObject *)); - } - for (k = 0; k < n; k++, ilow++) { - PyObject *w = vitem[k]; - Py_XINCREF(w); - item[ilow] = w; - } - for (k = norig - 1; k >= 0; --k) - Py_XDECREF(recycle[k]); - result = 0; + if (v == NULL) + n = 0; + else { + if (a == b) { + /* Special case "a[i:j] = a" -- copy b first */ + v = list_slice(b, 0, Py_SIZE(b)); + if (v == NULL) + return result; + result = list_ass_slice(a, ilow, ihigh, v); + Py_DECREF(v); + return result; + } + v_as_SF = PySequence_Fast(v, "can only assign an iterable"); + if(v_as_SF == NULL) + goto Error; + n = PySequence_Fast_GET_SIZE(v_as_SF); + vitem = PySequence_Fast_ITEMS(v_as_SF); + } + if (ilow < 0) + ilow = 0; + else if (ilow > Py_SIZE(a)) + ilow = Py_SIZE(a); + + if (ihigh < ilow) + ihigh = ilow; + else if (ihigh > Py_SIZE(a)) + ihigh = Py_SIZE(a); + + norig = ihigh - ilow; + assert(norig >= 0); + d = n - norig; + if (Py_SIZE(a) + d == 0) { + Py_XDECREF(v_as_SF); + return list_clear(a); + } + item = a->ob_item; + /* recycle the items that we are about to remove */ + s = norig * sizeof(PyObject *); + if (s > sizeof(recycle_on_stack)) { + recycle = (PyObject **)PyMem_MALLOC(s); + if (recycle == NULL) { + PyErr_NoMemory(); + goto Error; + } + } + memcpy(recycle, &item[ilow], s); + + if (d < 0) { /* Delete -d items */ + memmove(&item[ihigh+d], &item[ihigh], + (Py_SIZE(a) - ihigh)*sizeof(PyObject *)); + list_resize(a, Py_SIZE(a) + d); + item = a->ob_item; + } + else if (d > 0) { /* Insert d items */ + k = Py_SIZE(a); + if (list_resize(a, k+d) < 0) + goto Error; + item = a->ob_item; + memmove(&item[ihigh+d], &item[ihigh], + (k - ihigh)*sizeof(PyObject *)); + } + for (k = 0; k < n; k++, ilow++) { + PyObject *w = vitem[k]; + Py_XINCREF(w); + item[ilow] = w; + } + for (k = norig - 1; k >= 0; --k) + Py_XDECREF(recycle[k]); + result = 0; Error: - if (recycle != recycle_on_stack) - PyMem_FREE(recycle); - Py_XDECREF(v_as_SF); - return result; + if (recycle != recycle_on_stack) + PyMem_FREE(recycle); + Py_XDECREF(v_as_SF); + return result; #undef b } int PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v) { - if (!PyList_Check(a)) { - PyErr_BadInternalCall(); - return -1; - } - return list_ass_slice((PyListObject *)a, ilow, ihigh, v); + if (!PyList_Check(a)) { + PyErr_BadInternalCall(); + return -1; + } + return list_ass_slice((PyListObject *)a, ilow, ihigh, v); } static PyObject * list_inplace_repeat(PyListObject *self, Py_ssize_t n) { - PyObject **items; - Py_ssize_t size, i, j, p; + PyObject **items; + Py_ssize_t size, i, j, p; - size = PyList_GET_SIZE(self); - if (size == 0 || n == 1) { - Py_INCREF(self); - return (PyObject *)self; - } + size = PyList_GET_SIZE(self); + if (size == 0 || n == 1) { + Py_INCREF(self); + return (PyObject *)self; + } - if (n < 1) { - (void)list_clear(self); - Py_INCREF(self); - return (PyObject *)self; - } + if (n < 1) { + (void)list_clear(self); + Py_INCREF(self); + return (PyObject *)self; + } - if (size > PY_SSIZE_T_MAX / n) { - return PyErr_NoMemory(); - } + if (size > PY_SSIZE_T_MAX / n) { + return PyErr_NoMemory(); + } - if (list_resize(self, size*n) == -1) - return NULL; + if (list_resize(self, size*n) == -1) + return NULL; - p = size; - items = self->ob_item; - for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */ - for (j = 0; j < size; j++) { - PyObject *o = items[j]; - Py_INCREF(o); - items[p++] = o; - } - } - Py_INCREF(self); - return (PyObject *)self; + p = size; + items = self->ob_item; + for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */ + for (j = 0; j < size; j++) { + PyObject *o = items[j]; + Py_INCREF(o); + items[p++] = o; + } + } + Py_INCREF(self); + return (PyObject *)self; } static int list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v) { - PyObject *old_value; - if (i < 0 || i >= Py_SIZE(a)) { - PyErr_SetString(PyExc_IndexError, - "list assignment index out of range"); - return -1; - } - if (v == NULL) - return list_ass_slice(a, i, i+1, v); - Py_INCREF(v); - old_value = a->ob_item[i]; - a->ob_item[i] = v; - Py_DECREF(old_value); - return 0; + PyObject *old_value; + if (i < 0 || i >= Py_SIZE(a)) { + PyErr_SetString(PyExc_IndexError, + "list assignment index out of range"); + return -1; + } + if (v == NULL) + return list_ass_slice(a, i, i+1, v); + Py_INCREF(v); + old_value = a->ob_item[i]; + a->ob_item[i] = v; + Py_DECREF(old_value); + return 0; } static PyObject * listinsert(PyListObject *self, PyObject *args) { - Py_ssize_t i; - PyObject *v; - if (!PyArg_ParseTuple(args, "nO:insert", &i, &v)) - return NULL; - if (ins1(self, i, v) == 0) - Py_RETURN_NONE; - return NULL; + Py_ssize_t i; + PyObject *v; + if (!PyArg_ParseTuple(args, "nO:insert", &i, &v)) + return NULL; + if (ins1(self, i, v) == 0) + Py_RETURN_NONE; + return NULL; } static PyObject * listappend(PyListObject *self, PyObject *v) { - if (app1(self, v) == 0) - Py_RETURN_NONE; - return NULL; + if (app1(self, v) == 0) + Py_RETURN_NONE; + return NULL; } static PyObject * listextend(PyListObject *self, PyObject *b) { - PyObject *it; /* iter(v) */ - Py_ssize_t m; /* size of self */ - Py_ssize_t n; /* guess for size of b */ - Py_ssize_t mn; /* m + n */ - Py_ssize_t i; - PyObject *(*iternext)(PyObject *); - - /* Special cases: - 1) lists and tuples which can use PySequence_Fast ops - 2) extending self to self requires making a copy first - */ - if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) { - PyObject **src, **dest; - b = PySequence_Fast(b, "argument must be iterable"); - if (!b) - return NULL; - n = PySequence_Fast_GET_SIZE(b); - if (n == 0) { - /* short circuit when b is empty */ - Py_DECREF(b); - Py_RETURN_NONE; - } - m = Py_SIZE(self); - if (list_resize(self, m + n) == -1) { - Py_DECREF(b); - return NULL; - } - /* note that we may still have self == b here for the - * situation a.extend(a), but the following code works - * in that case too. Just make sure to resize self - * before calling PySequence_Fast_ITEMS. - */ - /* populate the end of self with b's items */ - src = PySequence_Fast_ITEMS(b); - dest = self->ob_item + m; - for (i = 0; i < n; i++) { - PyObject *o = src[i]; - Py_INCREF(o); - dest[i] = o; - } - Py_DECREF(b); - Py_RETURN_NONE; - } - - it = PyObject_GetIter(b); - if (it == NULL) - return NULL; - iternext = *it->ob_type->tp_iternext; - - /* Guess a result list size. */ - n = _PyObject_LengthHint(b, 8); - if (n == -1) { - Py_DECREF(it); - return NULL; - } - m = Py_SIZE(self); - mn = m + n; - if (mn >= m) { - /* Make room. */ - if (list_resize(self, mn) == -1) - goto error; - /* Make the list sane again. */ - Py_SIZE(self) = m; - } - /* Else m + n overflowed; on the chance that n lied, and there really - * is enough room, ignore it. If n was telling the truth, we'll - * eventually run out of memory during the loop. - */ - - /* Run iterator to exhaustion. */ - for (;;) { - PyObject *item = iternext(it); - if (item == NULL) { - if (PyErr_Occurred()) { - if (PyErr_ExceptionMatches(PyExc_StopIteration)) - PyErr_Clear(); - else - goto error; - } - break; - } - if (Py_SIZE(self) < self->allocated) { - /* steals ref */ - PyList_SET_ITEM(self, Py_SIZE(self), item); - ++Py_SIZE(self); - } - else { - int status = app1(self, item); - Py_DECREF(item); /* append creates a new ref */ - if (status < 0) - goto error; - } - } - - /* Cut back result list if initial guess was too large. */ - if (Py_SIZE(self) < self->allocated) - list_resize(self, Py_SIZE(self)); /* shrinking can't fail */ - - Py_DECREF(it); - Py_RETURN_NONE; + PyObject *it; /* iter(v) */ + Py_ssize_t m; /* size of self */ + Py_ssize_t n; /* guess for size of b */ + Py_ssize_t mn; /* m + n */ + Py_ssize_t i; + PyObject *(*iternext)(PyObject *); + + /* Special cases: + 1) lists and tuples which can use PySequence_Fast ops + 2) extending self to self requires making a copy first + */ + if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) { + PyObject **src, **dest; + b = PySequence_Fast(b, "argument must be iterable"); + if (!b) + return NULL; + n = PySequence_Fast_GET_SIZE(b); + if (n == 0) { + /* short circuit when b is empty */ + Py_DECREF(b); + Py_RETURN_NONE; + } + m = Py_SIZE(self); + if (list_resize(self, m + n) == -1) { + Py_DECREF(b); + return NULL; + } + /* note that we may still have self == b here for the + * situation a.extend(a), but the following code works + * in that case too. Just make sure to resize self + * before calling PySequence_Fast_ITEMS. + */ + /* populate the end of self with b's items */ + src = PySequence_Fast_ITEMS(b); + dest = self->ob_item + m; + for (i = 0; i < n; i++) { + PyObject *o = src[i]; + Py_INCREF(o); + dest[i] = o; + } + Py_DECREF(b); + Py_RETURN_NONE; + } + + it = PyObject_GetIter(b); + if (it == NULL) + return NULL; + iternext = *it->ob_type->tp_iternext; + + /* Guess a result list size. */ + n = _PyObject_LengthHint(b, 8); + if (n == -1) { + Py_DECREF(it); + return NULL; + } + m = Py_SIZE(self); + mn = m + n; + if (mn >= m) { + /* Make room. */ + if (list_resize(self, mn) == -1) + goto error; + /* Make the list sane again. */ + Py_SIZE(self) = m; + } + /* Else m + n overflowed; on the chance that n lied, and there really + * is enough room, ignore it. If n was telling the truth, we'll + * eventually run out of memory during the loop. + */ + + /* Run iterator to exhaustion. */ + for (;;) { + PyObject *item = iternext(it); + if (item == NULL) { + if (PyErr_Occurred()) { + if (PyErr_ExceptionMatches(PyExc_StopIteration)) + PyErr_Clear(); + else + goto error; + } + break; + } + if (Py_SIZE(self) < self->allocated) { + /* steals ref */ + PyList_SET_ITEM(self, Py_SIZE(self), item); + ++Py_SIZE(self); + } + else { + int status = app1(self, item); + Py_DECREF(item); /* append creates a new ref */ + if (status < 0) + goto error; + } + } + + /* Cut back result list if initial guess was too large. */ + if (Py_SIZE(self) < self->allocated) + list_resize(self, Py_SIZE(self)); /* shrinking can't fail */ + + Py_DECREF(it); + Py_RETURN_NONE; error: - Py_DECREF(it); - return NULL; + Py_DECREF(it); + return NULL; } PyObject * _PyList_Extend(PyListObject *self, PyObject *b) { - return listextend(self, b); + return listextend(self, b); } static PyObject * list_inplace_concat(PyListObject *self, PyObject *other) { - PyObject *result; + PyObject *result; - result = listextend(self, other); - if (result == NULL) - return result; - Py_DECREF(result); - Py_INCREF(self); - return (PyObject *)self; + result = listextend(self, other); + if (result == NULL) + return result; + Py_DECREF(result); + Py_INCREF(self); + return (PyObject *)self; } static PyObject * listpop(PyListObject *self, PyObject *args) { - Py_ssize_t i = -1; - PyObject *v; - int status; - - if (!PyArg_ParseTuple(args, "|n:pop", &i)) - return NULL; - - if (Py_SIZE(self) == 0) { - /* Special-case most common failure cause */ - PyErr_SetString(PyExc_IndexError, "pop from empty list"); - return NULL; - } - if (i < 0) - i += Py_SIZE(self); - if (i < 0 || i >= Py_SIZE(self)) { - PyErr_SetString(PyExc_IndexError, "pop index out of range"); - return NULL; - } - v = self->ob_item[i]; - if (i == Py_SIZE(self) - 1) { - status = list_resize(self, Py_SIZE(self) - 1); - assert(status >= 0); - return v; /* and v now owns the reference the list had */ - } - Py_INCREF(v); - status = list_ass_slice(self, i, i+1, (PyObject *)NULL); - assert(status >= 0); - /* Use status, so that in a release build compilers don't - * complain about the unused name. - */ - (void) status; - - return v; + Py_ssize_t i = -1; + PyObject *v; + int status; + + if (!PyArg_ParseTuple(args, "|n:pop", &i)) + return NULL; + + if (Py_SIZE(self) == 0) { + /* Special-case most common failure cause */ + PyErr_SetString(PyExc_IndexError, "pop from empty list"); + return NULL; + } + if (i < 0) + i += Py_SIZE(self); + if (i < 0 || i >= Py_SIZE(self)) { + PyErr_SetString(PyExc_IndexError, "pop index out of range"); + return NULL; + } + v = self->ob_item[i]; + if (i == Py_SIZE(self) - 1) { + status = list_resize(self, Py_SIZE(self) - 1); + assert(status >= 0); + return v; /* and v now owns the reference the list had */ + } + Py_INCREF(v); + status = list_ass_slice(self, i, i+1, (PyObject *)NULL); + assert(status >= 0); + /* Use status, so that in a release build compilers don't + * complain about the unused name. + */ + (void) status; + + return v; } /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */ static void reverse_slice(PyObject **lo, PyObject **hi) { - assert(lo && hi); + assert(lo && hi); - --hi; - while (lo < hi) { - PyObject *t = *lo; - *lo = *hi; - *hi = t; - ++lo; - --hi; - } + --hi; + while (lo < hi) { + PyObject *t = *lo; + *lo = *hi; + *hi = t; + ++lo; + --hi; + } } /* Lots of code for an adaptive, stable, natural mergesort. There are many @@ -951,7 +951,7 @@ reverse_slice(PyObject **lo, PyObject **hi) started. It makes more sense in context <wink>. X and Y are PyObject*s. */ #define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail; \ - if (k) + if (k) /* binarysort is the best method for sorting small arrays: it does few compares, but can do data movement quadratic in the number of @@ -967,48 +967,48 @@ reverse_slice(PyObject **lo, PyObject **hi) static int binarysort(PyObject **lo, PyObject **hi, PyObject **start) { - register Py_ssize_t k; - register PyObject **l, **p, **r; - register PyObject *pivot; - - assert(lo <= start && start <= hi); - /* assert [lo, start) is sorted */ - if (lo == start) - ++start; - for (; start < hi; ++start) { - /* set l to where *start belongs */ - l = lo; - r = start; - pivot = *r; - /* Invariants: - * pivot >= all in [lo, l). - * pivot < all in [r, start). - * The second is vacuously true at the start. - */ - assert(l < r); - do { - p = l + ((r - l) >> 1); - IFLT(pivot, *p) - r = p; - else - l = p+1; - } while (l < r); - assert(l == r); - /* The invariants still hold, so pivot >= all in [lo, l) and - pivot < all in [l, start), so pivot belongs at l. Note - that if there are elements equal to pivot, l points to the - first slot after them -- that's why this sort is stable. - Slide over to make room. - Caution: using memmove is much slower under MSVC 5; - we're not usually moving many slots. */ - for (p = start; p > l; --p) - *p = *(p-1); - *l = pivot; - } - return 0; + register Py_ssize_t k; + register PyObject **l, **p, **r; + register PyObject *pivot; + + assert(lo <= start && start <= hi); + /* assert [lo, start) is sorted */ + if (lo == start) + ++start; + for (; start < hi; ++start) { + /* set l to where *start belongs */ + l = lo; + r = start; + pivot = *r; + /* Invariants: + * pivot >= all in [lo, l). + * pivot < all in [r, start). + * The second is vacuously true at the start. + */ + assert(l < r); + do { + p = l + ((r - l) >> 1); + IFLT(pivot, *p) + r = p; + else + l = p+1; + } while (l < r); + assert(l == r); + /* The invariants still hold, so pivot >= all in [lo, l) and + pivot < all in [l, start), so pivot belongs at l. Note + that if there are elements equal to pivot, l points to the + first slot after them -- that's why this sort is stable. + Slide over to make room. + Caution: using memmove is much slower under MSVC 5; + we're not usually moving many slots. */ + for (p = start; p > l; --p) + *p = *(p-1); + *l = pivot; + } + return 0; fail: - return -1; + return -1; } /* @@ -1032,35 +1032,35 @@ Returns -1 in case of error. static Py_ssize_t count_run(PyObject **lo, PyObject **hi, int *descending) { - Py_ssize_t k; - Py_ssize_t n; - - assert(lo < hi); - *descending = 0; - ++lo; - if (lo == hi) - return 1; - - n = 2; - IFLT(*lo, *(lo-1)) { - *descending = 1; - for (lo = lo+1; lo < hi; ++lo, ++n) { - IFLT(*lo, *(lo-1)) - ; - else - break; - } - } - else { - for (lo = lo+1; lo < hi; ++lo, ++n) { - IFLT(*lo, *(lo-1)) - break; - } - } - - return n; + Py_ssize_t k; + Py_ssize_t n; + + assert(lo < hi); + *descending = 0; + ++lo; + if (lo == hi) + return 1; + + n = 2; + IFLT(*lo, *(lo-1)) { + *descending = 1; + for (lo = lo+1; lo < hi; ++lo, ++n) { + IFLT(*lo, *(lo-1)) + ; + else + break; + } + } + else { + for (lo = lo+1; lo < hi; ++lo, ++n) { + IFLT(*lo, *(lo-1)) + break; + } + } + + return n; fail: - return -1; + return -1; } /* @@ -1087,78 +1087,78 @@ Returns -1 on error. See listsort.txt for info on the method. static Py_ssize_t gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint) { - Py_ssize_t ofs; - Py_ssize_t lastofs; - Py_ssize_t k; - - assert(key && a && n > 0 && hint >= 0 && hint < n); - - a += hint; - lastofs = 0; - ofs = 1; - IFLT(*a, key) { - /* a[hint] < key -- gallop right, until - * a[hint + lastofs] < key <= a[hint + ofs] - */ - const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */ - while (ofs < maxofs) { - IFLT(a[ofs], key) { - lastofs = ofs; - ofs = (ofs << 1) + 1; - if (ofs <= 0) /* int overflow */ - ofs = maxofs; - } - else /* key <= a[hint + ofs] */ - break; - } - if (ofs > maxofs) - ofs = maxofs; - /* Translate back to offsets relative to &a[0]. */ - lastofs += hint; - ofs += hint; - } - else { - /* key <= a[hint] -- gallop left, until - * a[hint - ofs] < key <= a[hint - lastofs] - */ - const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */ - while (ofs < maxofs) { - IFLT(*(a-ofs), key) - break; - /* key <= a[hint - ofs] */ - lastofs = ofs; - ofs = (ofs << 1) + 1; - if (ofs <= 0) /* int overflow */ - ofs = maxofs; - } - if (ofs > maxofs) - ofs = maxofs; - /* Translate back to positive offsets relative to &a[0]. */ - k = lastofs; - lastofs = hint - ofs; - ofs = hint - k; - } - a -= hint; - - assert(-1 <= lastofs && lastofs < ofs && ofs <= n); - /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the - * right of lastofs but no farther right than ofs. Do a binary - * search, with invariant a[lastofs-1] < key <= a[ofs]. - */ - ++lastofs; - while (lastofs < ofs) { - Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1); - - IFLT(a[m], key) - lastofs = m+1; /* a[m] < key */ - else - ofs = m; /* key <= a[m] */ - } - assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */ - return ofs; + Py_ssize_t ofs; + Py_ssize_t lastofs; + Py_ssize_t k; + + assert(key && a && n > 0 && hint >= 0 && hint < n); + + a += hint; + lastofs = 0; + ofs = 1; + IFLT(*a, key) { + /* a[hint] < key -- gallop right, until + * a[hint + lastofs] < key <= a[hint + ofs] + */ + const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */ + while (ofs < maxofs) { + IFLT(a[ofs], key) { + lastofs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) /* int overflow */ + ofs = maxofs; + } + else /* key <= a[hint + ofs] */ + break; + } + if (ofs > maxofs) + ofs = maxofs; + /* Translate back to offsets relative to &a[0]. */ + lastofs += hint; + ofs += hint; + } + else { + /* key <= a[hint] -- gallop left, until + * a[hint - ofs] < key <= a[hint - lastofs] + */ + const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */ + while (ofs < maxofs) { + IFLT(*(a-ofs), key) + break; + /* key <= a[hint - ofs] */ + lastofs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) /* int overflow */ + ofs = maxofs; + } + if (ofs > maxofs) + ofs = maxofs; + /* Translate back to positive offsets relative to &a[0]. */ + k = lastofs; + lastofs = hint - ofs; + ofs = hint - k; + } + a -= hint; + + assert(-1 <= lastofs && lastofs < ofs && ofs <= n); + /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the + * right of lastofs but no farther right than ofs. Do a binary + * search, with invariant a[lastofs-1] < key <= a[ofs]. + */ + ++lastofs; + while (lastofs < ofs) { + Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1); + + IFLT(a[m], key) + lastofs = m+1; /* a[m] < key */ + else + ofs = m; /* key <= a[m] */ + } + assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */ + return ofs; fail: - return -1; + return -1; } /* @@ -1178,78 +1178,78 @@ written as one routine with yet another "left or right?" flag. static Py_ssize_t gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint) { - Py_ssize_t ofs; - Py_ssize_t lastofs; - Py_ssize_t k; - - assert(key && a && n > 0 && hint >= 0 && hint < n); - - a += hint; - lastofs = 0; - ofs = 1; - IFLT(key, *a) { - /* key < a[hint] -- gallop left, until - * a[hint - ofs] <= key < a[hint - lastofs] - */ - const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */ - while (ofs < maxofs) { - IFLT(key, *(a-ofs)) { - lastofs = ofs; - ofs = (ofs << 1) + 1; - if (ofs <= 0) /* int overflow */ - ofs = maxofs; - } - else /* a[hint - ofs] <= key */ - break; - } - if (ofs > maxofs) - ofs = maxofs; - /* Translate back to positive offsets relative to &a[0]. */ - k = lastofs; - lastofs = hint - ofs; - ofs = hint - k; - } - else { - /* a[hint] <= key -- gallop right, until - * a[hint + lastofs] <= key < a[hint + ofs] - */ - const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */ - while (ofs < maxofs) { - IFLT(key, a[ofs]) - break; - /* a[hint + ofs] <= key */ - lastofs = ofs; - ofs = (ofs << 1) + 1; - if (ofs <= 0) /* int overflow */ - ofs = maxofs; - } - if (ofs > maxofs) - ofs = maxofs; - /* Translate back to offsets relative to &a[0]. */ - lastofs += hint; - ofs += hint; - } - a -= hint; - - assert(-1 <= lastofs && lastofs < ofs && ofs <= n); - /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the - * right of lastofs but no farther right than ofs. Do a binary - * search, with invariant a[lastofs-1] <= key < a[ofs]. - */ - ++lastofs; - while (lastofs < ofs) { - Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1); - - IFLT(key, a[m]) - ofs = m; /* key < a[m] */ - else - lastofs = m+1; /* a[m] <= key */ - } - assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */ - return ofs; + Py_ssize_t ofs; + Py_ssize_t lastofs; + Py_ssize_t k; + + assert(key && a && n > 0 && hint >= 0 && hint < n); + + a += hint; + lastofs = 0; + ofs = 1; + IFLT(key, *a) { + /* key < a[hint] -- gallop left, until + * a[hint - ofs] <= key < a[hint - lastofs] + */ + const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */ + while (ofs < maxofs) { + IFLT(key, *(a-ofs)) { + lastofs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) /* int overflow */ + ofs = maxofs; + } + else /* a[hint - ofs] <= key */ + break; + } + if (ofs > maxofs) + ofs = maxofs; + /* Translate back to positive offsets relative to &a[0]. */ + k = lastofs; + lastofs = hint - ofs; + ofs = hint - k; + } + else { + /* a[hint] <= key -- gallop right, until + * a[hint + lastofs] <= key < a[hint + ofs] + */ + const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */ + while (ofs < maxofs) { + IFLT(key, a[ofs]) + break; + /* a[hint + ofs] <= key */ + lastofs = ofs; + ofs = (ofs << 1) + 1; + if (ofs <= 0) /* int overflow */ + ofs = maxofs; + } + if (ofs > maxofs) + ofs = maxofs; + /* Translate back to offsets relative to &a[0]. */ + lastofs += hint; + ofs += hint; + } + a -= hint; + + assert(-1 <= lastofs && lastofs < ofs && ofs <= n); + /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the + * right of lastofs but no farther right than ofs. Do a binary + * search, with invariant a[lastofs-1] <= key < a[ofs]. + */ + ++lastofs; + while (lastofs < ofs) { + Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1); + + IFLT(key, a[m]) + ofs = m; /* key < a[m] */ + else + lastofs = m+1; /* a[m] <= key */ + } + assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */ + return ofs; fail: - return -1; + return -1; } /* The maximum number of entries in a MergeState's pending-runs stack. @@ -1272,48 +1272,48 @@ fail: * a convenient way to pass state around among the helper functions. */ struct s_slice { - PyObject **base; - Py_ssize_t len; + PyObject **base; + Py_ssize_t len; }; typedef struct s_MergeState { - /* This controls when we get *into* galloping mode. It's initialized - * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for - * random data, and lower for highly structured data. - */ - Py_ssize_t min_gallop; - - /* 'a' is temp storage to help with merges. It contains room for - * alloced entries. - */ - PyObject **a; /* may point to temparray below */ - Py_ssize_t alloced; - - /* A stack of n pending runs yet to be merged. Run #i starts at - * address base[i] and extends for len[i] elements. It's always - * true (so long as the indices are in bounds) that - * - * pending[i].base + pending[i].len == pending[i+1].base - * - * so we could cut the storage for this, but it's a minor amount, - * and keeping all the info explicit simplifies the code. - */ - int n; - struct s_slice pending[MAX_MERGE_PENDING]; - - /* 'a' points to this when possible, rather than muck with malloc. */ - PyObject *temparray[MERGESTATE_TEMP_SIZE]; + /* This controls when we get *into* galloping mode. It's initialized + * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for + * random data, and lower for highly structured data. + */ + Py_ssize_t min_gallop; + + /* 'a' is temp storage to help with merges. It contains room for + * alloced entries. + */ + PyObject **a; /* may point to temparray below */ + Py_ssize_t alloced; + + /* A stack of n pending runs yet to be merged. Run #i starts at + * address base[i] and extends for len[i] elements. It's always + * true (so long as the indices are in bounds) that + * + * pending[i].base + pending[i].len == pending[i+1].base + * + * so we could cut the storage for this, but it's a minor amount, + * and keeping all the info explicit simplifies the code. + */ + int n; + struct s_slice pending[MAX_MERGE_PENDING]; + + /* 'a' points to this when possible, rather than muck with malloc. */ + PyObject *temparray[MERGESTATE_TEMP_SIZE]; } MergeState; /* Conceptually a MergeState's constructor. */ static void merge_init(MergeState *ms) { - assert(ms != NULL); - ms->a = ms->temparray; - ms->alloced = MERGESTATE_TEMP_SIZE; - ms->n = 0; - ms->min_gallop = MIN_GALLOP; + assert(ms != NULL); + ms->a = ms->temparray; + ms->alloced = MERGESTATE_TEMP_SIZE; + ms->n = 0; + ms->min_gallop = MIN_GALLOP; } /* Free all the temp memory owned by the MergeState. This must be called @@ -1323,11 +1323,11 @@ merge_init(MergeState *ms) static void merge_freemem(MergeState *ms) { - assert(ms != NULL); - if (ms->a != ms->temparray) - PyMem_Free(ms->a); - ms->a = ms->temparray; - ms->alloced = MERGESTATE_TEMP_SIZE; + assert(ms != NULL); + if (ms->a != ms->temparray) + PyMem_Free(ms->a); + ms->a = ms->temparray; + ms->alloced = MERGESTATE_TEMP_SIZE; } /* Ensure enough temp memory for 'need' array slots is available. @@ -1336,28 +1336,28 @@ merge_freemem(MergeState *ms) static int merge_getmem(MergeState *ms, Py_ssize_t need) { - assert(ms != NULL); - if (need <= ms->alloced) - return 0; - /* Don't realloc! That can cost cycles to copy the old data, but - * we don't care what's in the block. - */ - merge_freemem(ms); - if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) { - PyErr_NoMemory(); - return -1; - } - ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*)); - if (ms->a) { - ms->alloced = need; - return 0; - } - PyErr_NoMemory(); - merge_freemem(ms); /* reset to sane state */ - return -1; -} -#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ - merge_getmem(MS, NEED)) + assert(ms != NULL); + if (need <= ms->alloced) + return 0; + /* Don't realloc! That can cost cycles to copy the old data, but + * we don't care what's in the block. + */ + merge_freemem(ms); + if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) { + PyErr_NoMemory(); + return -1; + } + ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*)); + if (ms->a) { + ms->alloced = need; + return 0; + } + PyErr_NoMemory(); + merge_freemem(ms); /* reset to sane state */ + return -1; +} +#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ + merge_getmem(MS, NEED)) /* Merge the na elements starting at pa with the nb elements starting at pb * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. @@ -1369,125 +1369,125 @@ static Py_ssize_t merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb) { - Py_ssize_t k; - PyObject **dest; - int result = -1; /* guilty until proved innocent */ - Py_ssize_t min_gallop; - - assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); - if (MERGE_GETMEM(ms, na) < 0) - return -1; - memcpy(ms->a, pa, na * sizeof(PyObject*)); - dest = pa; - pa = ms->a; - - *dest++ = *pb++; - --nb; - if (nb == 0) - goto Succeed; - if (na == 1) - goto CopyB; - - min_gallop = ms->min_gallop; - for (;;) { - Py_ssize_t acount = 0; /* # of times A won in a row */ - Py_ssize_t bcount = 0; /* # of times B won in a row */ - - /* Do the straightforward thing until (if ever) one run - * appears to win consistently. - */ - for (;;) { - assert(na > 1 && nb > 0); - k = ISLT(*pb, *pa); - if (k) { - if (k < 0) - goto Fail; - *dest++ = *pb++; - ++bcount; - acount = 0; - --nb; - if (nb == 0) - goto Succeed; - if (bcount >= min_gallop) - break; - } - else { - *dest++ = *pa++; - ++acount; - bcount = 0; - --na; - if (na == 1) - goto CopyB; - if (acount >= min_gallop) - break; - } - } - - /* One run is winning so consistently that galloping may - * be a huge win. So try that, and continue galloping until - * (if ever) neither run appears to be winning consistently - * anymore. - */ - ++min_gallop; - do { - assert(na > 1 && nb > 0); - min_gallop -= min_gallop > 1; - ms->min_gallop = min_gallop; - k = gallop_right(*pb, pa, na, 0); - acount = k; - if (k) { - if (k < 0) - goto Fail; - memcpy(dest, pa, k * sizeof(PyObject *)); - dest += k; - pa += k; - na -= k; - if (na == 1) - goto CopyB; - /* na==0 is impossible now if the comparison - * function is consistent, but we can't assume - * that it is. - */ - if (na == 0) - goto Succeed; - } - *dest++ = *pb++; - --nb; - if (nb == 0) - goto Succeed; - - k = gallop_left(*pa, pb, nb, 0); - bcount = k; - if (k) { - if (k < 0) - goto Fail; - memmove(dest, pb, k * sizeof(PyObject *)); - dest += k; - pb += k; - nb -= k; - if (nb == 0) - goto Succeed; - } - *dest++ = *pa++; - --na; - if (na == 1) - goto CopyB; - } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); - ++min_gallop; /* penalize it for leaving galloping mode */ - ms->min_gallop = min_gallop; - } + Py_ssize_t k; + PyObject **dest; + int result = -1; /* guilty until proved innocent */ + Py_ssize_t min_gallop; + + assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); + if (MERGE_GETMEM(ms, na) < 0) + return -1; + memcpy(ms->a, pa, na * sizeof(PyObject*)); + dest = pa; + pa = ms->a; + + *dest++ = *pb++; + --nb; + if (nb == 0) + goto Succeed; + if (na == 1) + goto CopyB; + + min_gallop = ms->min_gallop; + for (;;) { + Py_ssize_t acount = 0; /* # of times A won in a row */ + Py_ssize_t bcount = 0; /* # of times B won in a row */ + + /* Do the straightforward thing until (if ever) one run + * appears to win consistently. + */ + for (;;) { + assert(na > 1 && nb > 0); + k = ISLT(*pb, *pa); + if (k) { + if (k < 0) + goto Fail; + *dest++ = *pb++; + ++bcount; + acount = 0; + --nb; + if (nb == 0) + goto Succeed; + if (bcount >= min_gallop) + break; + } + else { + *dest++ = *pa++; + ++acount; + bcount = 0; + --na; + if (na == 1) + goto CopyB; + if (acount >= min_gallop) + break; + } + } + + /* One run is winning so consistently that galloping may + * be a huge win. So try that, and continue galloping until + * (if ever) neither run appears to be winning consistently + * anymore. + */ + ++min_gallop; + do { + assert(na > 1 && nb > 0); + min_gallop -= min_gallop > 1; + ms->min_gallop = min_gallop; + k = gallop_right(*pb, pa, na, 0); + acount = k; + if (k) { + if (k < 0) + goto Fail; + memcpy(dest, pa, k * sizeof(PyObject *)); + dest += k; + pa += k; + na -= k; + if (na == 1) + goto CopyB; + /* na==0 is impossible now if the comparison + * function is consistent, but we can't assume + * that it is. + */ + if (na == 0) + goto Succeed; + } + *dest++ = *pb++; + --nb; + if (nb == 0) + goto Succeed; + + k = gallop_left(*pa, pb, nb, 0); + bcount = k; + if (k) { + if (k < 0) + goto Fail; + memmove(dest, pb, k * sizeof(PyObject *)); + dest += k; + pb += k; + nb -= k; + if (nb == 0) + goto Succeed; + } + *dest++ = *pa++; + --na; + if (na == 1) + goto CopyB; + } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); + ++min_gallop; /* penalize it for leaving galloping mode */ + ms->min_gallop = min_gallop; + } Succeed: - result = 0; + result = 0; Fail: - if (na) - memcpy(dest, pa, na * sizeof(PyObject*)); - return result; + if (na) + memcpy(dest, pa, na * sizeof(PyObject*)); + return result; CopyB: - assert(na == 1 && nb > 0); - /* The last element of pa belongs at the end of the merge. */ - memmove(dest, pb, nb * sizeof(PyObject *)); - dest[nb] = *pa; - return 0; + assert(na == 1 && nb > 0); + /* The last element of pa belongs at the end of the merge. */ + memmove(dest, pb, nb * sizeof(PyObject *)); + dest[nb] = *pa; + return 0; } /* Merge the na elements starting at pa with the nb elements starting at pb @@ -1499,134 +1499,134 @@ CopyB: static Py_ssize_t merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb) { - Py_ssize_t k; - PyObject **dest; - int result = -1; /* guilty until proved innocent */ - PyObject **basea; - PyObject **baseb; - Py_ssize_t min_gallop; - - assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); - if (MERGE_GETMEM(ms, nb) < 0) - return -1; - dest = pb + nb - 1; - memcpy(ms->a, pb, nb * sizeof(PyObject*)); - basea = pa; - baseb = ms->a; - pb = ms->a + nb - 1; - pa += na - 1; - - *dest-- = *pa--; - --na; - if (na == 0) - goto Succeed; - if (nb == 1) - goto CopyA; - - min_gallop = ms->min_gallop; - for (;;) { - Py_ssize_t acount = 0; /* # of times A won in a row */ - Py_ssize_t bcount = 0; /* # of times B won in a row */ - - /* Do the straightforward thing until (if ever) one run - * appears to win consistently. - */ - for (;;) { - assert(na > 0 && nb > 1); - k = ISLT(*pb, *pa); - if (k) { - if (k < 0) - goto Fail; - *dest-- = *pa--; - ++acount; - bcount = 0; - --na; - if (na == 0) - goto Succeed; - if (acount >= min_gallop) - break; - } - else { - *dest-- = *pb--; - ++bcount; - acount = 0; - --nb; - if (nb == 1) - goto CopyA; - if (bcount >= min_gallop) - break; - } - } - - /* One run is winning so consistently that galloping may - * be a huge win. So try that, and continue galloping until - * (if ever) neither run appears to be winning consistently - * anymore. - */ - ++min_gallop; - do { - assert(na > 0 && nb > 1); - min_gallop -= min_gallop > 1; - ms->min_gallop = min_gallop; - k = gallop_right(*pb, basea, na, na-1); - if (k < 0) - goto Fail; - k = na - k; - acount = k; - if (k) { - dest -= k; - pa -= k; - memmove(dest+1, pa+1, k * sizeof(PyObject *)); - na -= k; - if (na == 0) - goto Succeed; - } - *dest-- = *pb--; - --nb; - if (nb == 1) - goto CopyA; - - k = gallop_left(*pa, baseb, nb, nb-1); - if (k < 0) - goto Fail; - k = nb - k; - bcount = k; - if (k) { - dest -= k; - pb -= k; - memcpy(dest+1, pb+1, k * sizeof(PyObject *)); - nb -= k; - if (nb == 1) - goto CopyA; - /* nb==0 is impossible now if the comparison - * function is consistent, but we can't assume - * that it is. - */ - if (nb == 0) - goto Succeed; - } - *dest-- = *pa--; - --na; - if (na == 0) - goto Succeed; - } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); - ++min_gallop; /* penalize it for leaving galloping mode */ - ms->min_gallop = min_gallop; - } + Py_ssize_t k; + PyObject **dest; + int result = -1; /* guilty until proved innocent */ + PyObject **basea; + PyObject **baseb; + Py_ssize_t min_gallop; + + assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); + if (MERGE_GETMEM(ms, nb) < 0) + return -1; + dest = pb + nb - 1; + memcpy(ms->a, pb, nb * sizeof(PyObject*)); + basea = pa; + baseb = ms->a; + pb = ms->a + nb - 1; + pa += na - 1; + + *dest-- = *pa--; + --na; + if (na == 0) + goto Succeed; + if (nb == 1) + goto CopyA; + + min_gallop = ms->min_gallop; + for (;;) { + Py_ssize_t acount = 0; /* # of times A won in a row */ + Py_ssize_t bcount = 0; /* # of times B won in a row */ + + /* Do the straightforward thing until (if ever) one run + * appears to win consistently. + */ + for (;;) { + assert(na > 0 && nb > 1); + k = ISLT(*pb, *pa); + if (k) { + if (k < 0) + goto Fail; + *dest-- = *pa--; + ++acount; + bcount = 0; + --na; + if (na == 0) + goto Succeed; + if (acount >= min_gallop) + break; + } + else { + *dest-- = *pb--; + ++bcount; + acount = 0; + --nb; + if (nb == 1) + goto CopyA; + if (bcount >= min_gallop) + break; + } + } + + /* One run is winning so consistently that galloping may + * be a huge win. So try that, and continue galloping until + * (if ever) neither run appears to be winning consistently + * anymore. + */ + ++min_gallop; + do { + assert(na > 0 && nb > 1); + min_gallop -= min_gallop > 1; + ms->min_gallop = min_gallop; + k = gallop_right(*pb, basea, na, na-1); + if (k < 0) + goto Fail; + k = na - k; + acount = k; + if (k) { + dest -= k; + pa -= k; + memmove(dest+1, pa+1, k * sizeof(PyObject *)); + na -= k; + if (na == 0) + goto Succeed; + } + *dest-- = *pb--; + --nb; + if (nb == 1) + goto CopyA; + + k = gallop_left(*pa, baseb, nb, nb-1); + if (k < 0) + goto Fail; + k = nb - k; + bcount = k; + if (k) { + dest -= k; + pb -= k; + memcpy(dest+1, pb+1, k * sizeof(PyObject *)); + nb -= k; + if (nb == 1) + goto CopyA; + /* nb==0 is impossible now if the comparison + * function is consistent, but we can't assume + * that it is. + */ + if (nb == 0) + goto Succeed; + } + *dest-- = *pa--; + --na; + if (na == 0) + goto Succeed; + } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); + ++min_gallop; /* penalize it for leaving galloping mode */ + ms->min_gallop = min_gallop; + } Succeed: - result = 0; + result = 0; Fail: - if (nb) - memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*)); - return result; + if (nb) + memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*)); + return result; CopyA: - assert(nb == 1 && na > 0); - /* The first element of pb belongs at the front of the merge. */ - dest -= na; - pa -= na; - memmove(dest+1, pa+1, na * sizeof(PyObject *)); - *dest = *pb; - return 0; + assert(nb == 1 && na > 0); + /* The first element of pb belongs at the front of the merge. */ + dest -= na; + pa -= na; + memmove(dest+1, pa+1, na * sizeof(PyObject *)); + *dest = *pb; + return 0; } /* Merge the two runs at stack indices i and i+1. @@ -1635,56 +1635,56 @@ CopyA: static Py_ssize_t merge_at(MergeState *ms, Py_ssize_t i) { - PyObject **pa, **pb; - Py_ssize_t na, nb; - Py_ssize_t k; - - assert(ms != NULL); - assert(ms->n >= 2); - assert(i >= 0); - assert(i == ms->n - 2 || i == ms->n - 3); - - pa = ms->pending[i].base; - na = ms->pending[i].len; - pb = ms->pending[i+1].base; - nb = ms->pending[i+1].len; - assert(na > 0 && nb > 0); - assert(pa + na == pb); - - /* Record the length of the combined runs; if i is the 3rd-last - * run now, also slide over the last run (which isn't involved - * in this merge). The current run i+1 goes away in any case. - */ - ms->pending[i].len = na + nb; - if (i == ms->n - 3) - ms->pending[i+1] = ms->pending[i+2]; - --ms->n; - - /* Where does b start in a? Elements in a before that can be - * ignored (already in place). - */ - k = gallop_right(*pb, pa, na, 0); - if (k < 0) - return -1; - pa += k; - na -= k; - if (na == 0) - return 0; - - /* Where does a end in b? Elements in b after that can be - * ignored (already in place). - */ - nb = gallop_left(pa[na-1], pb, nb, nb-1); - if (nb <= 0) - return nb; - - /* Merge what remains of the runs, using a temp array with - * min(na, nb) elements. - */ - if (na <= nb) - return merge_lo(ms, pa, na, pb, nb); - else - return merge_hi(ms, pa, na, pb, nb); + PyObject **pa, **pb; + Py_ssize_t na, nb; + Py_ssize_t k; + + assert(ms != NULL); + assert(ms->n >= 2); + assert(i >= 0); + assert(i == ms->n - 2 || i == ms->n - 3); + + pa = ms->pending[i].base; + na = ms->pending[i].len; + pb = ms->pending[i+1].base; + nb = ms->pending[i+1].len; + assert(na > 0 && nb > 0); + assert(pa + na == pb); + + /* Record the length of the combined runs; if i is the 3rd-last + * run now, also slide over the last run (which isn't involved + * in this merge). The current run i+1 goes away in any case. + */ + ms->pending[i].len = na + nb; + if (i == ms->n - 3) + ms->pending[i+1] = ms->pending[i+2]; + --ms->n; + + /* Where does b start in a? Elements in a before that can be + * ignored (already in place). + */ + k = gallop_right(*pb, pa, na, 0); + if (k < 0) + return -1; + pa += k; + na -= k; + if (na == 0) + return 0; + + /* Where does a end in b? Elements in b after that can be + * ignored (already in place). + */ + nb = gallop_left(pa[na-1], pb, nb, nb-1); + if (nb <= 0) + return nb; + + /* Merge what remains of the runs, using a temp array with + * min(na, nb) elements. + */ + if (na <= nb) + return merge_lo(ms, pa, na, pb, nb); + else + return merge_hi(ms, pa, na, pb, nb); } /* Examine the stack of runs waiting to be merged, merging adjacent runs @@ -1700,25 +1700,25 @@ merge_at(MergeState *ms, Py_ssize_t i) static int merge_collapse(MergeState *ms) { - struct s_slice *p = ms->pending; - - assert(ms); - while (ms->n > 1) { - Py_ssize_t n = ms->n - 2; - if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) { - if (p[n-1].len < p[n+1].len) - --n; - if (merge_at(ms, n) < 0) - return -1; - } - else if (p[n].len <= p[n+1].len) { - if (merge_at(ms, n) < 0) - return -1; - } - else - break; - } - return 0; + struct s_slice *p = ms->pending; + + assert(ms); + while (ms->n > 1) { + Py_ssize_t n = ms->n - 2; + if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) { + if (p[n-1].len < p[n+1].len) + --n; + if (merge_at(ms, n) < 0) + return -1; + } + else if (p[n].len <= p[n+1].len) { + if (merge_at(ms, n) < 0) + return -1; + } + else + break; + } + return 0; } /* Regardless of invariants, merge all runs on the stack until only one @@ -1729,17 +1729,17 @@ merge_collapse(MergeState *ms) static int merge_force_collapse(MergeState *ms) { - struct s_slice *p = ms->pending; + struct s_slice *p = ms->pending; - assert(ms); - while (ms->n > 1) { - Py_ssize_t n = ms->n - 2; - if (n > 0 && p[n-1].len < p[n+1].len) - --n; - if (merge_at(ms, n) < 0) - return -1; - } - return 0; + assert(ms); + while (ms->n > 1) { + Py_ssize_t n = ms->n - 2; + if (n > 0 && p[n-1].len < p[n+1].len) + --n; + if (merge_at(ms, n) < 0) + return -1; + } + return 0; } /* Compute a good value for the minimum run length; natural runs shorter @@ -1755,14 +1755,14 @@ merge_force_collapse(MergeState *ms) static Py_ssize_t merge_compute_minrun(Py_ssize_t n) { - Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */ + Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */ - assert(n >= 0); - while (n >= 64) { - r |= n & 1; - n >>= 1; - } - return n + r; + assert(n >= 0); + while (n >= 64) { + r |= n & 1; + n >>= 1; + } + return n + r; } /* Special wrapper to support stable sorting using the decorate-sort-undecorate @@ -1773,9 +1773,9 @@ merge_compute_minrun(Py_ssize_t n) a full record. */ typedef struct { - PyObject_HEAD - PyObject *key; - PyObject *value; + PyObject_HEAD + PyObject *key; + PyObject *value; } sortwrapperobject; PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key."); @@ -1785,51 +1785,51 @@ static void sortwrapper_dealloc(sortwrapperobject *); PyTypeObject PySortWrapper_Type = { - PyVarObject_HEAD_INIT(&PyType_Type, 0) - "sortwrapper", /* tp_name */ - sizeof(sortwrapperobject), /* tp_basicsize */ - 0, /* tp_itemsize */ - /* methods */ - (destructor)sortwrapper_dealloc, /* tp_dealloc */ - 0, /* tp_print */ - 0, /* tp_getattr */ - 0, /* tp_setattr */ - 0, /* tp_reserved */ - 0, /* tp_repr */ - 0, /* tp_as_number */ - 0, /* tp_as_sequence */ - 0, /* tp_as_mapping */ - 0, /* tp_hash */ - 0, /* tp_call */ - 0, /* tp_str */ - PyObject_GenericGetAttr, /* tp_getattro */ - 0, /* tp_setattro */ - 0, /* tp_as_buffer */ - Py_TPFLAGS_DEFAULT, /* tp_flags */ - sortwrapper_doc, /* tp_doc */ - 0, /* tp_traverse */ - 0, /* tp_clear */ - (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */ + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "sortwrapper", /* tp_name */ + sizeof(sortwrapperobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)sortwrapper_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT, /* tp_flags */ + sortwrapper_doc, /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */ }; static PyObject * sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op) { - if (!PyObject_TypeCheck(b, &PySortWrapper_Type)) { - PyErr_SetString(PyExc_TypeError, - "expected a sortwrapperobject"); - return NULL; - } - return PyObject_RichCompare(a->key, b->key, op); + if (!PyObject_TypeCheck(b, &PySortWrapper_Type)) { + PyErr_SetString(PyExc_TypeError, + "expected a sortwrapperobject"); + return NULL; + } + return PyObject_RichCompare(a->key, b->key, op); } static void sortwrapper_dealloc(sortwrapperobject *so) { - Py_XDECREF(so->key); - Py_XDECREF(so->value); - PyObject_Del(so); + Py_XDECREF(so->key); + Py_XDECREF(so->value); + PyObject_Del(so); } /* Returns a new reference to a sortwrapper. @@ -1838,30 +1838,30 @@ sortwrapper_dealloc(sortwrapperobject *so) static PyObject * build_sortwrapper(PyObject *key, PyObject *value) { - sortwrapperobject *so; + sortwrapperobject *so; - so = PyObject_New(sortwrapperobject, &PySortWrapper_Type); - if (so == NULL) - return NULL; - so->key = key; - so->value = value; - return (PyObject *)so; + so = PyObject_New(sortwrapperobject, &PySortWrapper_Type); + if (so == NULL) + return NULL; + so->key = key; + so->value = value; + return (PyObject *)so; } /* Returns a new reference to the value underlying the wrapper. */ static PyObject * sortwrapper_getvalue(PyObject *so) { - PyObject *value; + PyObject *value; - if (!PyObject_TypeCheck(so, &PySortWrapper_Type)) { - PyErr_SetString(PyExc_TypeError, - "expected a sortwrapperobject"); - return NULL; - } - value = ((sortwrapperobject *)so)->value; - Py_INCREF(value); - return value; + if (!PyObject_TypeCheck(so, &PySortWrapper_Type)) { + PyErr_SetString(PyExc_TypeError, + "expected a sortwrapperobject"); + return NULL; + } + value = ((sortwrapperobject *)so)->value; + Py_INCREF(value); + return value; } /* An adaptive, stable, natural mergesort. See listsort.txt. @@ -1872,163 +1872,163 @@ sortwrapper_getvalue(PyObject *so) static PyObject * listsort(PyListObject *self, PyObject *args, PyObject *kwds) { - MergeState ms; - PyObject **lo, **hi; - Py_ssize_t nremaining; - Py_ssize_t minrun; - Py_ssize_t saved_ob_size, saved_allocated; - PyObject **saved_ob_item; - PyObject **final_ob_item; - PyObject *result = NULL; /* guilty until proved innocent */ - int reverse = 0; - PyObject *keyfunc = NULL; - Py_ssize_t i; - PyObject *key, *value, *kvpair; - static char *kwlist[] = {"key", "reverse", 0}; - - assert(self != NULL); - assert (PyList_Check(self)); - if (args != NULL) { - if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort", - kwlist, &keyfunc, &reverse)) - return NULL; - if (Py_SIZE(args) > 0) { - PyErr_SetString(PyExc_TypeError, - "must use keyword argument for key function"); - return NULL; - } - } - if (keyfunc == Py_None) - keyfunc = NULL; - - /* The list is temporarily made empty, so that mutations performed - * by comparison functions can't affect the slice of memory we're - * sorting (allowing mutations during sorting is a core-dump - * factory, since ob_item may change). - */ - saved_ob_size = Py_SIZE(self); - saved_ob_item = self->ob_item; - saved_allocated = self->allocated; - Py_SIZE(self) = 0; - self->ob_item = NULL; - self->allocated = -1; /* any operation will reset it to >= 0 */ - - if (keyfunc != NULL) { - for (i=0 ; i < saved_ob_size ; i++) { - value = saved_ob_item[i]; - key = PyObject_CallFunctionObjArgs(keyfunc, value, - NULL); - if (key == NULL) { - for (i=i-1 ; i>=0 ; i--) { - kvpair = saved_ob_item[i]; - value = sortwrapper_getvalue(kvpair); - saved_ob_item[i] = value; - Py_DECREF(kvpair); - } - goto dsu_fail; - } - kvpair = build_sortwrapper(key, value); - if (kvpair == NULL) - goto dsu_fail; - saved_ob_item[i] = kvpair; - } - } - - /* Reverse sort stability achieved by initially reversing the list, - applying a stable forward sort, then reversing the final result. */ - if (reverse && saved_ob_size > 1) - reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); - - merge_init(&ms); - - nremaining = saved_ob_size; - if (nremaining < 2) - goto succeed; - - /* March over the array once, left to right, finding natural runs, - * and extending short natural runs to minrun elements. - */ - lo = saved_ob_item; - hi = lo + nremaining; - minrun = merge_compute_minrun(nremaining); - do { - int descending; - Py_ssize_t n; - - /* Identify next run. */ - n = count_run(lo, hi, &descending); - if (n < 0) - goto fail; - if (descending) - reverse_slice(lo, lo + n); - /* If short, extend to min(minrun, nremaining). */ - if (n < minrun) { - const Py_ssize_t force = nremaining <= minrun ? - nremaining : minrun; - if (binarysort(lo, lo + force, lo + n) < 0) - goto fail; - n = force; - } - /* Push run onto pending-runs stack, and maybe merge. */ - assert(ms.n < MAX_MERGE_PENDING); - ms.pending[ms.n].base = lo; - ms.pending[ms.n].len = n; - ++ms.n; - if (merge_collapse(&ms) < 0) - goto fail; - /* Advance to find next run. */ - lo += n; - nremaining -= n; - } while (nremaining); - assert(lo == hi); - - if (merge_force_collapse(&ms) < 0) - goto fail; - assert(ms.n == 1); - assert(ms.pending[0].base == saved_ob_item); - assert(ms.pending[0].len == saved_ob_size); + MergeState ms; + PyObject **lo, **hi; + Py_ssize_t nremaining; + Py_ssize_t minrun; + Py_ssize_t saved_ob_size, saved_allocated; + PyObject **saved_ob_item; + PyObject **final_ob_item; + PyObject *result = NULL; /* guilty until proved innocent */ + int reverse = 0; + PyObject *keyfunc = NULL; + Py_ssize_t i; + PyObject *key, *value, *kvpair; + static char *kwlist[] = {"key", "reverse", 0}; + + assert(self != NULL); + assert (PyList_Check(self)); + if (args != NULL) { + if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort", + kwlist, &keyfunc, &reverse)) + return NULL; + if (Py_SIZE(args) > 0) { + PyErr_SetString(PyExc_TypeError, + "must use keyword argument for key function"); + return NULL; + } + } + if (keyfunc == Py_None) + keyfunc = NULL; + + /* The list is temporarily made empty, so that mutations performed + * by comparison functions can't affect the slice of memory we're + * sorting (allowing mutations during sorting is a core-dump + * factory, since ob_item may change). + */ + saved_ob_size = Py_SIZE(self); + saved_ob_item = self->ob_item; + saved_allocated = self->allocated; + Py_SIZE(self) = 0; + self->ob_item = NULL; + self->allocated = -1; /* any operation will reset it to >= 0 */ + + if (keyfunc != NULL) { + for (i=0 ; i < saved_ob_size ; i++) { + value = saved_ob_item[i]; + key = PyObject_CallFunctionObjArgs(keyfunc, value, + NULL); + if (key == NULL) { + for (i=i-1 ; i>=0 ; i--) { + kvpair = saved_ob_item[i]; + value = sortwrapper_getvalue(kvpair); + saved_ob_item[i] = value; + Py_DECREF(kvpair); + } + goto dsu_fail; + } + kvpair = build_sortwrapper(key, value); + if (kvpair == NULL) + goto dsu_fail; + saved_ob_item[i] = kvpair; + } + } + + /* Reverse sort stability achieved by initially reversing the list, + applying a stable forward sort, then reversing the final result. */ + if (reverse && saved_ob_size > 1) + reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); + + merge_init(&ms); + + nremaining = saved_ob_size; + if (nremaining < 2) + goto succeed; + + /* March over the array once, left to right, finding natural runs, + * and extending short natural runs to minrun elements. + */ + lo = saved_ob_item; + hi = lo + nremaining; + minrun = merge_compute_minrun(nremaining); + do { + int descending; + Py_ssize_t n; + + /* Identify next run. */ + n = count_run(lo, hi, &descending); + if (n < 0) + goto fail; + if (descending) + reverse_slice(lo, lo + n); + /* If short, extend to min(minrun, nremaining). */ + if (n < minrun) { + const Py_ssize_t force = nremaining <= minrun ? + nremaining : minrun; + if (binarysort(lo, lo + force, lo + n) < 0) + goto fail; + n = force; + } + /* Push run onto pending-runs stack, and maybe merge. */ + assert(ms.n < MAX_MERGE_PENDING); + ms.pending[ms.n].base = lo; + ms.pending[ms.n].len = n; + ++ms.n; + if (merge_collapse(&ms) < 0) + goto fail; + /* Advance to find next run. */ + lo += n; + nremaining -= n; + } while (nremaining); + assert(lo == hi); + + if (merge_force_collapse(&ms) < 0) + goto fail; + assert(ms.n == 1); + assert(ms.pending[0].base == saved_ob_item); + assert(ms.pending[0].len == saved_ob_size); succeed: - result = Py_None; + result = Py_None; fail: - if (keyfunc != NULL) { - for (i=0 ; i < saved_ob_size ; i++) { - kvpair = saved_ob_item[i]; - value = sortwrapper_getvalue(kvpair); - saved_ob_item[i] = value; - Py_DECREF(kvpair); - } - } - - if (self->allocated != -1 && result != NULL) { - /* The user mucked with the list during the sort, - * and we don't already have another error to report. - */ - PyErr_SetString(PyExc_ValueError, "list modified during sort"); - result = NULL; - } - - if (reverse && saved_ob_size > 1) - reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); - - merge_freemem(&ms); + if (keyfunc != NULL) { + for (i=0 ; i < saved_ob_size ; i++) { + kvpair = saved_ob_item[i]; + value = sortwrapper_getvalue(kvpair); + saved_ob_item[i] = value; + Py_DECREF(kvpair); + } + } + + if (self->allocated != -1 && result != NULL) { + /* The user mucked with the list during the sort, + * and we don't already have another error to report. + */ + PyErr_SetString(PyExc_ValueError, "list modified during sort"); + result = NULL; + } + + if (reverse && saved_ob_size > 1) + reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); + + merge_freemem(&ms); dsu_fail: - final_ob_item = self->ob_item; - i = Py_SIZE(self); - Py_SIZE(self) = saved_ob_size; - self->ob_item = saved_ob_item; - self->allocated = saved_allocated; - if (final_ob_item != NULL) { - /* we cannot use list_clear() for this because it does not - guarantee that the list is really empty when it returns */ - while (--i >= 0) { - Py_XDECREF(final_ob_item[i]); - } - PyMem_FREE(final_ob_item); - } - Py_XINCREF(result); - return result; + final_ob_item = self->ob_item; + i = Py_SIZE(self); + Py_SIZE(self) = saved_ob_size; + self->ob_item = saved_ob_item; + self->allocated = saved_allocated; + if (final_ob_item != NULL) { + /* we cannot use list_clear() for this because it does not + guarantee that the list is really empty when it returns */ + while (--i >= 0) { + Py_XDECREF(final_ob_item[i]); + } + PyMem_FREE(final_ob_item); + } + Py_XINCREF(result); + return result; } #undef IFLT #undef ISLT @@ -2036,248 +2036,248 @@ dsu_fail: int PyList_Sort(PyObject *v) { - if (v == NULL || !PyList_Check(v)) { - PyErr_BadInternalCall(); - return -1; - } - v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL); - if (v == NULL) - return -1; - Py_DECREF(v); - return 0; + if (v == NULL || !PyList_Check(v)) { + PyErr_BadInternalCall(); + return -1; + } + v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL); + if (v == NULL) + return -1; + Py_DECREF(v); + return 0; } static PyObject * listreverse(PyListObject *self) { - if (Py_SIZE(self) > 1) - reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self)); - Py_RETURN_NONE; + if (Py_SIZE(self) > 1) + reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self)); + Py_RETURN_NONE; } int PyList_Reverse(PyObject *v) { - PyListObject *self = (PyListObject *)v; + PyListObject *self = (PyListObject *)v; - if (v == NULL || !PyList_Check(v)) { - PyErr_BadInternalCall(); - return -1; - } - if (Py_SIZE(self) > 1) - reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self)); - return 0; + if (v == NULL || !PyList_Check(v)) { + PyErr_BadInternalCall(); + return -1; + } + if (Py_SIZE(self) > 1) + reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self)); + return 0; } PyObject * PyList_AsTuple(PyObject *v) { - PyObject *w; - PyObject **p, **q; - Py_ssize_t n; - if (v == NULL || !PyList_Check(v)) { - PyErr_BadInternalCall(); - return NULL; - } - n = Py_SIZE(v); - w = PyTuple_New(n); - if (w == NULL) - return NULL; - p = ((PyTupleObject *)w)->ob_item; - q = ((PyListObject *)v)->ob_item; - while (--n >= 0) { - Py_INCREF(*q); - *p = *q; - p++; - q++; - } - return w; + PyObject *w; + PyObject **p, **q; + Py_ssize_t n; + if (v == NULL || !PyList_Check(v)) { + PyErr_BadInternalCall(); + return NULL; + } + n = Py_SIZE(v); + w = PyTuple_New(n); + if (w == NULL) + return NULL; + p = ((PyTupleObject *)w)->ob_item; + q = ((PyListObject *)v)->ob_item; + while (--n >= 0) { + Py_INCREF(*q); + *p = *q; + p++; + q++; + } + return w; } static PyObject * listindex(PyListObject *self, PyObject *args) { - Py_ssize_t i, start=0, stop=Py_SIZE(self); - PyObject *v; - - if (!PyArg_ParseTuple(args, "O|O&O&:index", &v, - _PyEval_SliceIndex, &start, - _PyEval_SliceIndex, &stop)) - return NULL; - if (start < 0) { - start += Py_SIZE(self); - if (start < 0) - start = 0; - } - if (stop < 0) { - stop += Py_SIZE(self); - if (stop < 0) - stop = 0; - } - for (i = start; i < stop && i < Py_SIZE(self); i++) { - int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); - if (cmp > 0) - return PyLong_FromSsize_t(i); - else if (cmp < 0) - return NULL; - } - PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list"); - return NULL; + Py_ssize_t i, start=0, stop=Py_SIZE(self); + PyObject *v; + + if (!PyArg_ParseTuple(args, "O|O&O&:index", &v, + _PyEval_SliceIndex, &start, + _PyEval_SliceIndex, &stop)) + return NULL; + if (start < 0) { + start += Py_SIZE(self); + if (start < 0) + start = 0; + } + if (stop < 0) { + stop += Py_SIZE(self); + if (stop < 0) + stop = 0; + } + for (i = start; i < stop && i < Py_SIZE(self); i++) { + int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); + if (cmp > 0) + return PyLong_FromSsize_t(i); + else if (cmp < 0) + return NULL; + } + PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list"); + return NULL; } static PyObject * listcount(PyListObject *self, PyObject *v) { - Py_ssize_t count = 0; - Py_ssize_t i; + Py_ssize_t count = 0; + Py_ssize_t i; - for (i = 0; i < Py_SIZE(self); i++) { - int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); - if (cmp > 0) - count++; - else if (cmp < 0) - return NULL; - } - return PyLong_FromSsize_t(count); + for (i = 0; i < Py_SIZE(self); i++) { + int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); + if (cmp > 0) + count++; + else if (cmp < 0) + return NULL; + } + return PyLong_FromSsize_t(count); } static PyObject * listremove(PyListObject *self, PyObject *v) { - Py_ssize_t i; + Py_ssize_t i; - for (i = 0; i < Py_SIZE(self); i++) { - int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); - if (cmp > 0) { - if (list_ass_slice(self, i, i+1, - (PyObject *)NULL) == 0) - Py_RETURN_NONE; - return NULL; - } - else if (cmp < 0) - return NULL; - } - PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list"); - return NULL; + for (i = 0; i < Py_SIZE(self); i++) { + int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); + if (cmp > 0) { + if (list_ass_slice(self, i, i+1, + (PyObject *)NULL) == 0) + Py_RETURN_NONE; + return NULL; + } + else if (cmp < 0) + return NULL; + } + PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list"); + return NULL; } static int list_traverse(PyListObject *o, visitproc visit, void *arg) { - Py_ssize_t i; + Py_ssize_t i; - for (i = Py_SIZE(o); --i >= 0; ) - Py_VISIT(o->ob_item[i]); - return 0; + for (i = Py_SIZE(o); --i >= 0; ) + Py_VISIT(o->ob_item[i]); + return 0; } static PyObject * list_richcompare(PyObject *v, PyObject *w, int op) { - PyListObject *vl, *wl; - Py_ssize_t i; - - if (!PyList_Check(v) || !PyList_Check(w)) { - Py_INCREF(Py_NotImplemented); - return Py_NotImplemented; - } - - vl = (PyListObject *)v; - wl = (PyListObject *)w; - - if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) { - /* Shortcut: if the lengths differ, the lists differ */ - PyObject *res; - if (op == Py_EQ) - res = Py_False; - else - res = Py_True; - Py_INCREF(res); - return res; - } - - /* Search for the first index where items are different */ - for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) { - int k = PyObject_RichCompareBool(vl->ob_item[i], - wl->ob_item[i], Py_EQ); - if (k < 0) - return NULL; - if (!k) - break; - } - - if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) { - /* No more items to compare -- compare sizes */ - Py_ssize_t vs = Py_SIZE(vl); - Py_ssize_t ws = Py_SIZE(wl); - int cmp; - PyObject *res; - switch (op) { - case Py_LT: cmp = vs < ws; break; - case Py_LE: cmp = vs <= ws; break; - case Py_EQ: cmp = vs == ws; break; - case Py_NE: cmp = vs != ws; break; - case Py_GT: cmp = vs > ws; break; - case Py_GE: cmp = vs >= ws; break; - default: return NULL; /* cannot happen */ - } - if (cmp) - res = Py_True; - else - res = Py_False; - Py_INCREF(res); - return res; - } - - /* We have an item that differs -- shortcuts for EQ/NE */ - if (op == Py_EQ) { - Py_INCREF(Py_False); - return Py_False; - } - if (op == Py_NE) { - Py_INCREF(Py_True); - return Py_True; - } - - /* Compare the final item again using the proper operator */ - return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op); + PyListObject *vl, *wl; + Py_ssize_t i; + + if (!PyList_Check(v) || !PyList_Check(w)) { + Py_INCREF(Py_NotImplemented); + return Py_NotImplemented; + } + + vl = (PyListObject *)v; + wl = (PyListObject *)w; + + if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) { + /* Shortcut: if the lengths differ, the lists differ */ + PyObject *res; + if (op == Py_EQ) + res = Py_False; + else + res = Py_True; + Py_INCREF(res); + return res; + } + + /* Search for the first index where items are different */ + for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) { + int k = PyObject_RichCompareBool(vl->ob_item[i], + wl->ob_item[i], Py_EQ); + if (k < 0) + return NULL; + if (!k) + break; + } + + if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) { + /* No more items to compare -- compare sizes */ + Py_ssize_t vs = Py_SIZE(vl); + Py_ssize_t ws = Py_SIZE(wl); + int cmp; + PyObject *res; + switch (op) { + case Py_LT: cmp = vs < ws; break; + case Py_LE: cmp = vs <= ws; break; + case Py_EQ: cmp = vs == ws; break; + case Py_NE: cmp = vs != ws; break; + case Py_GT: cmp = vs > ws; break; + case Py_GE: cmp = vs >= ws; break; + default: return NULL; /* cannot happen */ + } + if (cmp) + res = Py_True; + else + res = Py_False; + Py_INCREF(res); + return res; + } + + /* We have an item that differs -- shortcuts for EQ/NE */ + if (op == Py_EQ) { + Py_INCREF(Py_False); + return Py_False; + } + if (op == Py_NE) { + Py_INCREF(Py_True); + return Py_True; + } + + /* Compare the final item again using the proper operator */ + return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op); } static int list_init(PyListObject *self, PyObject *args, PyObject *kw) { - PyObject *arg = NULL; - static char *kwlist[] = {"sequence", 0}; + PyObject *arg = NULL; + static char *kwlist[] = {"sequence", 0}; - if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg)) - return -1; + if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg)) + return -1; - /* Verify list invariants established by PyType_GenericAlloc() */ - assert(0 <= Py_SIZE(self)); - assert(Py_SIZE(self) <= self->allocated || self->allocated == -1); - assert(self->ob_item != NULL || - self->allocated == 0 || self->allocated == -1); + /* Verify list invariants established by PyType_GenericAlloc() */ + assert(0 <= Py_SIZE(self)); + assert(Py_SIZE(self) <= self->allocated || self->allocated == -1); + assert(self->ob_item != NULL || + self->allocated == 0 || self->allocated == -1); - /* Empty previous contents */ - if (self->ob_item != NULL) { - (void)list_clear(self); - } - if (arg != NULL) { - PyObject *rv = listextend(self, arg); - if (rv == NULL) - return -1; - Py_DECREF(rv); - } - return 0; + /* Empty previous contents */ + if (self->ob_item != NULL) { + (void)list_clear(self); + } + if (arg != NULL) { + PyObject *rv = listextend(self, arg); + if (rv == NULL) + return -1; + Py_DECREF(rv); + } + return 0; } static PyObject * list_sizeof(PyListObject *self) { - Py_ssize_t res; + Py_ssize_t res; - res = sizeof(PyListObject) + self->allocated * sizeof(void*); - return PyLong_FromSsize_t(res); + res = sizeof(PyListObject) + self->allocated * sizeof(void*); + return PyLong_FromSsize_t(res); } static PyObject *list_iter(PyObject *seq); @@ -2314,32 +2314,32 @@ PyDoc_STRVAR(sort_doc, static PyObject *list_subscript(PyListObject*, PyObject*); static PyMethodDef list_methods[] = { - {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc}, - {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc}, - {"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc}, - {"append", (PyCFunction)listappend, METH_O, append_doc}, - {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc}, - {"extend", (PyCFunction)listextend, METH_O, extend_doc}, - {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc}, - {"remove", (PyCFunction)listremove, METH_O, remove_doc}, - {"index", (PyCFunction)listindex, METH_VARARGS, index_doc}, - {"count", (PyCFunction)listcount, METH_O, count_doc}, - {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc}, - {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc}, - {NULL, NULL} /* sentinel */ + {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc}, + {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc}, + {"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc}, + {"append", (PyCFunction)listappend, METH_O, append_doc}, + {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc}, + {"extend", (PyCFunction)listextend, METH_O, extend_doc}, + {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc}, + {"remove", (PyCFunction)listremove, METH_O, remove_doc}, + {"index", (PyCFunction)listindex, METH_VARARGS, index_doc}, + {"count", (PyCFunction)listcount, METH_O, count_doc}, + {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc}, + {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc}, + {NULL, NULL} /* sentinel */ }; static PySequenceMethods list_as_sequence = { - (lenfunc)list_length, /* sq_length */ - (binaryfunc)list_concat, /* sq_concat */ - (ssizeargfunc)list_repeat, /* sq_repeat */ - (ssizeargfunc)list_item, /* sq_item */ - 0, /* sq_slice */ - (ssizeobjargproc)list_ass_item, /* sq_ass_item */ - 0, /* sq_ass_slice */ - (objobjproc)list_contains, /* sq_contains */ - (binaryfunc)list_inplace_concat, /* sq_inplace_concat */ - (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */ + (lenfunc)list_length, /* sq_length */ + (binaryfunc)list_concat, /* sq_concat */ + (ssizeargfunc)list_repeat, /* sq_repeat */ + (ssizeargfunc)list_item, /* sq_item */ + 0, /* sq_slice */ + (ssizeobjargproc)list_ass_item, /* sq_ass_item */ + 0, /* sq_ass_slice */ + (objobjproc)list_contains, /* sq_contains */ + (binaryfunc)list_inplace_concat, /* sq_inplace_concat */ + (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */ }; PyDoc_STRVAR(list_doc, @@ -2349,275 +2349,275 @@ PyDoc_STRVAR(list_doc, static PyObject * list_subscript(PyListObject* self, PyObject* item) { - if (PyIndex_Check(item)) { - Py_ssize_t i; - i = PyNumber_AsSsize_t(item, PyExc_IndexError); - if (i == -1 && PyErr_Occurred()) - return NULL; - if (i < 0) - i += PyList_GET_SIZE(self); - return list_item(self, i); - } - else if (PySlice_Check(item)) { - Py_ssize_t start, stop, step, slicelength, cur, i; - PyObject* result; - PyObject* it; - PyObject **src, **dest; - - if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self), - &start, &stop, &step, &slicelength) < 0) { - return NULL; - } - - if (slicelength <= 0) { - return PyList_New(0); - } - else if (step == 1) { - return list_slice(self, start, stop); - } - else { - result = PyList_New(slicelength); - if (!result) return NULL; - - src = self->ob_item; - dest = ((PyListObject *)result)->ob_item; - for (cur = start, i = 0; i < slicelength; - cur += step, i++) { - it = src[cur]; - Py_INCREF(it); - dest[i] = it; - } - - return result; - } - } - else { - PyErr_Format(PyExc_TypeError, - "list indices must be integers, not %.200s", - item->ob_type->tp_name); - return NULL; - } + if (PyIndex_Check(item)) { + Py_ssize_t i; + i = PyNumber_AsSsize_t(item, PyExc_IndexError); + if (i == -1 && PyErr_Occurred()) + return NULL; + if (i < 0) + i += PyList_GET_SIZE(self); + return list_item(self, i); + } + else if (PySlice_Check(item)) { + Py_ssize_t start, stop, step, slicelength, cur, i; + PyObject* result; + PyObject* it; + PyObject **src, **dest; + + if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self), + &start, &stop, &step, &slicelength) < 0) { + return NULL; + } + + if (slicelength <= 0) { + return PyList_New(0); + } + else if (step == 1) { + return list_slice(self, start, stop); + } + else { + result = PyList_New(slicelength); + if (!result) return NULL; + + src = self->ob_item; + dest = ((PyListObject *)result)->ob_item; + for (cur = start, i = 0; i < slicelength; + cur += step, i++) { + it = src[cur]; + Py_INCREF(it); + dest[i] = it; + } + + return result; + } + } + else { + PyErr_Format(PyExc_TypeError, + "list indices must be integers, not %.200s", + item->ob_type->tp_name); + return NULL; + } } static int list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value) { - if (PyIndex_Check(item)) { - Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError); - if (i == -1 && PyErr_Occurred()) - return -1; - if (i < 0) - i += PyList_GET_SIZE(self); - return list_ass_item(self, i, value); - } - else if (PySlice_Check(item)) { - Py_ssize_t start, stop, step, slicelength; - - if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self), - &start, &stop, &step, &slicelength) < 0) { - return -1; - } - - if (step == 1) - return list_ass_slice(self, start, stop, value); - - /* Make sure s[5:2] = [..] inserts at the right place: - before 5, not before 2. */ - if ((step < 0 && start < stop) || - (step > 0 && start > stop)) - stop = start; - - if (value == NULL) { - /* delete slice */ - PyObject **garbage; - size_t cur; - Py_ssize_t i; - - if (slicelength <= 0) - return 0; - - if (step < 0) { - stop = start + 1; - start = stop + step*(slicelength - 1) - 1; - step = -step; - } - - assert((size_t)slicelength <= - PY_SIZE_MAX / sizeof(PyObject*)); - - garbage = (PyObject**) - PyMem_MALLOC(slicelength*sizeof(PyObject*)); - if (!garbage) { - PyErr_NoMemory(); - return -1; - } - - /* drawing pictures might help understand these for - loops. Basically, we memmove the parts of the - list that are *not* part of the slice: step-1 - items for each item that is part of the slice, - and then tail end of the list that was not - covered by the slice */ - for (cur = start, i = 0; - cur < (size_t)stop; - cur += step, i++) { - Py_ssize_t lim = step - 1; - - garbage[i] = PyList_GET_ITEM(self, cur); - - if (cur + step >= (size_t)Py_SIZE(self)) { - lim = Py_SIZE(self) - cur - 1; - } - - memmove(self->ob_item + cur - i, - self->ob_item + cur + 1, - lim * sizeof(PyObject *)); - } - cur = start + slicelength*step; - if (cur < (size_t)Py_SIZE(self)) { - memmove(self->ob_item + cur - slicelength, - self->ob_item + cur, - (Py_SIZE(self) - cur) * - sizeof(PyObject *)); - } - - Py_SIZE(self) -= slicelength; - list_resize(self, Py_SIZE(self)); - - for (i = 0; i < slicelength; i++) { - Py_DECREF(garbage[i]); - } - PyMem_FREE(garbage); - - return 0; - } - else { - /* assign slice */ - PyObject *ins, *seq; - PyObject **garbage, **seqitems, **selfitems; - Py_ssize_t cur, i; - - /* protect against a[::-1] = a */ - if (self == (PyListObject*)value) { - seq = list_slice((PyListObject*)value, 0, - PyList_GET_SIZE(value)); - } - else { - seq = PySequence_Fast(value, - "must assign iterable " - "to extended slice"); - } - if (!seq) - return -1; - - if (PySequence_Fast_GET_SIZE(seq) != slicelength) { - PyErr_Format(PyExc_ValueError, - "attempt to assign sequence of " - "size %zd to extended slice of " - "size %zd", - PySequence_Fast_GET_SIZE(seq), - slicelength); - Py_DECREF(seq); - return -1; - } - - if (!slicelength) { - Py_DECREF(seq); - return 0; - } - - garbage = (PyObject**) - PyMem_MALLOC(slicelength*sizeof(PyObject*)); - if (!garbage) { - Py_DECREF(seq); - PyErr_NoMemory(); - return -1; - } - - selfitems = self->ob_item; - seqitems = PySequence_Fast_ITEMS(seq); - for (cur = start, i = 0; i < slicelength; - cur += step, i++) { - garbage[i] = selfitems[cur]; - ins = seqitems[i]; - Py_INCREF(ins); - selfitems[cur] = ins; - } - - for (i = 0; i < slicelength; i++) { - Py_DECREF(garbage[i]); - } - - PyMem_FREE(garbage); - Py_DECREF(seq); - - return 0; - } - } - else { - PyErr_Format(PyExc_TypeError, - "list indices must be integers, not %.200s", - item->ob_type->tp_name); - return -1; - } + if (PyIndex_Check(item)) { + Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError); + if (i == -1 && PyErr_Occurred()) + return -1; + if (i < 0) + i += PyList_GET_SIZE(self); + return list_ass_item(self, i, value); + } + else if (PySlice_Check(item)) { + Py_ssize_t start, stop, step, slicelength; + + if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self), + &start, &stop, &step, &slicelength) < 0) { + return -1; + } + + if (step == 1) + return list_ass_slice(self, start, stop, value); + + /* Make sure s[5:2] = [..] inserts at the right place: + before 5, not before 2. */ + if ((step < 0 && start < stop) || + (step > 0 && start > stop)) + stop = start; + + if (value == NULL) { + /* delete slice */ + PyObject **garbage; + size_t cur; + Py_ssize_t i; + + if (slicelength <= 0) + return 0; + + if (step < 0) { + stop = start + 1; + start = stop + step*(slicelength - 1) - 1; + step = -step; + } + + assert((size_t)slicelength <= + PY_SIZE_MAX / sizeof(PyObject*)); + + garbage = (PyObject**) + PyMem_MALLOC(slicelength*sizeof(PyObject*)); + if (!garbage) { + PyErr_NoMemory(); + return -1; + } + + /* drawing pictures might help understand these for + loops. Basically, we memmove the parts of the + list that are *not* part of the slice: step-1 + items for each item that is part of the slice, + and then tail end of the list that was not + covered by the slice */ + for (cur = start, i = 0; + cur < (size_t)stop; + cur += step, i++) { + Py_ssize_t lim = step - 1; + + garbage[i] = PyList_GET_ITEM(self, cur); + + if (cur + step >= (size_t)Py_SIZE(self)) { + lim = Py_SIZE(self) - cur - 1; + } + + memmove(self->ob_item + cur - i, + self->ob_item + cur + 1, + lim * sizeof(PyObject *)); + } + cur = start + slicelength*step; + if (cur < (size_t)Py_SIZE(self)) { + memmove(self->ob_item + cur - slicelength, + self->ob_item + cur, + (Py_SIZE(self) - cur) * + sizeof(PyObject *)); + } + + Py_SIZE(self) -= slicelength; + list_resize(self, Py_SIZE(self)); + + for (i = 0; i < slicelength; i++) { + Py_DECREF(garbage[i]); + } + PyMem_FREE(garbage); + + return 0; + } + else { + /* assign slice */ + PyObject *ins, *seq; + PyObject **garbage, **seqitems, **selfitems; + Py_ssize_t cur, i; + + /* protect against a[::-1] = a */ + if (self == (PyListObject*)value) { + seq = list_slice((PyListObject*)value, 0, + PyList_GET_SIZE(value)); + } + else { + seq = PySequence_Fast(value, + "must assign iterable " + "to extended slice"); + } + if (!seq) + return -1; + + if (PySequence_Fast_GET_SIZE(seq) != slicelength) { + PyErr_Format(PyExc_ValueError, + "attempt to assign sequence of " + "size %zd to extended slice of " + "size %zd", + PySequence_Fast_GET_SIZE(seq), + slicelength); + Py_DECREF(seq); + return -1; + } + + if (!slicelength) { + Py_DECREF(seq); + return 0; + } + + garbage = (PyObject**) + PyMem_MALLOC(slicelength*sizeof(PyObject*)); + if (!garbage) { + Py_DECREF(seq); + PyErr_NoMemory(); + return -1; + } + + selfitems = self->ob_item; + seqitems = PySequence_Fast_ITEMS(seq); + for (cur = start, i = 0; i < slicelength; + cur += step, i++) { + garbage[i] = selfitems[cur]; + ins = seqitems[i]; + Py_INCREF(ins); + selfitems[cur] = ins; + } + + for (i = 0; i < slicelength; i++) { + Py_DECREF(garbage[i]); + } + + PyMem_FREE(garbage); + Py_DECREF(seq); + + return 0; + } + } + else { + PyErr_Format(PyExc_TypeError, + "list indices must be integers, not %.200s", + item->ob_type->tp_name); + return -1; + } } static PyMappingMethods list_as_mapping = { - (lenfunc)list_length, - (binaryfunc)list_subscript, - (objobjargproc)list_ass_subscript + (lenfunc)list_length, + (binaryfunc)list_subscript, + (objobjargproc)list_ass_subscript }; PyTypeObject PyList_Type = { - PyVarObject_HEAD_INIT(&PyType_Type, 0) - "list", - sizeof(PyListObject), - 0, - (destructor)list_dealloc, /* tp_dealloc */ - 0, /* tp_print */ - 0, /* tp_getattr */ - 0, /* tp_setattr */ - 0, /* tp_reserved */ - (reprfunc)list_repr, /* tp_repr */ - 0, /* tp_as_number */ - &list_as_sequence, /* tp_as_sequence */ - &list_as_mapping, /* tp_as_mapping */ - (hashfunc)PyObject_HashNotImplemented, /* tp_hash */ - 0, /* tp_call */ - 0, /* tp_str */ - PyObject_GenericGetAttr, /* tp_getattro */ - 0, /* tp_setattro */ - 0, /* tp_as_buffer */ - Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | - Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */ - list_doc, /* tp_doc */ - (traverseproc)list_traverse, /* tp_traverse */ - (inquiry)list_clear, /* tp_clear */ - list_richcompare, /* tp_richcompare */ - 0, /* tp_weaklistoffset */ - list_iter, /* tp_iter */ - 0, /* tp_iternext */ - list_methods, /* tp_methods */ - 0, /* tp_members */ - 0, /* tp_getset */ - 0, /* tp_base */ - 0, /* tp_dict */ - 0, /* tp_descr_get */ - 0, /* tp_descr_set */ - 0, /* tp_dictoffset */ - (initproc)list_init, /* tp_init */ - PyType_GenericAlloc, /* tp_alloc */ - PyType_GenericNew, /* tp_new */ - PyObject_GC_Del, /* tp_free */ + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "list", + sizeof(PyListObject), + 0, + (destructor)list_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + (reprfunc)list_repr, /* tp_repr */ + 0, /* tp_as_number */ + &list_as_sequence, /* tp_as_sequence */ + &list_as_mapping, /* tp_as_mapping */ + (hashfunc)PyObject_HashNotImplemented, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | + Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */ + list_doc, /* tp_doc */ + (traverseproc)list_traverse, /* tp_traverse */ + (inquiry)list_clear, /* tp_clear */ + list_richcompare, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + list_iter, /* tp_iter */ + 0, /* tp_iternext */ + list_methods, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + 0, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + 0, /* tp_dictoffset */ + (initproc)list_init, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + PyType_GenericNew, /* tp_new */ + PyObject_GC_Del, /* tp_free */ }; /*********************** List Iterator **************************/ typedef struct { - PyObject_HEAD - long it_index; - PyListObject *it_seq; /* Set to NULL when iterator is exhausted */ + PyObject_HEAD + long it_index; + PyListObject *it_seq; /* Set to NULL when iterator is exhausted */ } listiterobject; static PyObject *list_iter(PyObject *); @@ -2629,119 +2629,119 @@ static PyObject *listiter_len(listiterobject *); PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); static PyMethodDef listiter_methods[] = { - {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc}, - {NULL, NULL} /* sentinel */ + {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc}, + {NULL, NULL} /* sentinel */ }; PyTypeObject PyListIter_Type = { - PyVarObject_HEAD_INIT(&PyType_Type, 0) - "list_iterator", /* tp_name */ - sizeof(listiterobject), /* tp_basicsize */ - 0, /* tp_itemsize */ - /* methods */ - (destructor)listiter_dealloc, /* tp_dealloc */ - 0, /* tp_print */ - 0, /* tp_getattr */ - 0, /* tp_setattr */ - 0, /* tp_reserved */ - 0, /* tp_repr */ - 0, /* tp_as_number */ - 0, /* tp_as_sequence */ - 0, /* tp_as_mapping */ - 0, /* tp_hash */ - 0, /* tp_call */ - 0, /* tp_str */ - PyObject_GenericGetAttr, /* tp_getattro */ - 0, /* tp_setattro */ - 0, /* tp_as_buffer */ - Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ - 0, /* tp_doc */ - (traverseproc)listiter_traverse, /* tp_traverse */ - 0, /* tp_clear */ - 0, /* tp_richcompare */ - 0, /* tp_weaklistoffset */ - PyObject_SelfIter, /* tp_iter */ - (iternextfunc)listiter_next, /* tp_iternext */ - listiter_methods, /* tp_methods */ - 0, /* tp_members */ + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "list_iterator", /* tp_name */ + sizeof(listiterobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)listiter_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ + 0, /* tp_doc */ + (traverseproc)listiter_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + PyObject_SelfIter, /* tp_iter */ + (iternextfunc)listiter_next, /* tp_iternext */ + listiter_methods, /* tp_methods */ + 0, /* tp_members */ }; static PyObject * list_iter(PyObject *seq) { - listiterobject *it; + listiterobject *it; - if (!PyList_Check(seq)) { - PyErr_BadInternalCall(); - return NULL; - } - it = PyObject_GC_New(listiterobject, &PyListIter_Type); - if (it == NULL) - return NULL; - it->it_index = 0; - Py_INCREF(seq); - it->it_seq = (PyListObject *)seq; - _PyObject_GC_TRACK(it); - return (PyObject *)it; + if (!PyList_Check(seq)) { + PyErr_BadInternalCall(); + return NULL; + } + it = PyObject_GC_New(listiterobject, &PyListIter_Type); + if (it == NULL) + return NULL; + it->it_index = 0; + Py_INCREF(seq); + it->it_seq = (PyListObject *)seq; + _PyObject_GC_TRACK(it); + return (PyObject *)it; } static void listiter_dealloc(listiterobject *it) { - _PyObject_GC_UNTRACK(it); - Py_XDECREF(it->it_seq); - PyObject_GC_Del(it); + _PyObject_GC_UNTRACK(it); + Py_XDECREF(it->it_seq); + PyObject_GC_Del(it); } static int listiter_traverse(listiterobject *it, visitproc visit, void *arg) { - Py_VISIT(it->it_seq); - return 0; + Py_VISIT(it->it_seq); + return 0; } static PyObject * listiter_next(listiterobject *it) { - PyListObject *seq; - PyObject *item; + PyListObject *seq; + PyObject *item; - assert(it != NULL); - seq = it->it_seq; - if (seq == NULL) - return NULL; - assert(PyList_Check(seq)); + assert(it != NULL); + seq = it->it_seq; + if (seq == NULL) + return NULL; + assert(PyList_Check(seq)); - if (it->it_index < PyList_GET_SIZE(seq)) { - item = PyList_GET_ITEM(seq, it->it_index); - ++it->it_index; - Py_INCREF(item); - return item; - } + if (it->it_index < PyList_GET_SIZE(seq)) { + item = PyList_GET_ITEM(seq, it->it_index); + ++it->it_index; + Py_INCREF(item); + return item; + } - Py_DECREF(seq); - it->it_seq = NULL; - return NULL; + Py_DECREF(seq); + it->it_seq = NULL; + return NULL; } static PyObject * listiter_len(listiterobject *it) { - Py_ssize_t len; - if (it->it_seq) { - len = PyList_GET_SIZE(it->it_seq) - it->it_index; - if (len >= 0) - return PyLong_FromSsize_t(len); - } - return PyLong_FromLong(0); + Py_ssize_t len; + if (it->it_seq) { + len = PyList_GET_SIZE(it->it_seq) - it->it_index; + if (len >= 0) + return PyLong_FromSsize_t(len); + } + return PyLong_FromLong(0); } /*********************** List Reverse Iterator **************************/ typedef struct { - PyObject_HEAD - Py_ssize_t it_index; - PyListObject *it_seq; /* Set to NULL when iterator is exhausted */ + PyObject_HEAD + Py_ssize_t it_index; + PyListObject *it_seq; /* Set to NULL when iterator is exhausted */ } listreviterobject; static PyObject *list_reversed(PyListObject *, PyObject *); @@ -2751,101 +2751,101 @@ static PyObject *listreviter_next(listreviterobject *); static PyObject *listreviter_len(listreviterobject *); static PyMethodDef listreviter_methods[] = { - {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc}, - {NULL, NULL} /* sentinel */ + {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc}, + {NULL, NULL} /* sentinel */ }; PyTypeObject PyListRevIter_Type = { - PyVarObject_HEAD_INIT(&PyType_Type, 0) - "list_reverseiterator", /* tp_name */ - sizeof(listreviterobject), /* tp_basicsize */ - 0, /* tp_itemsize */ - /* methods */ - (destructor)listreviter_dealloc, /* tp_dealloc */ - 0, /* tp_print */ - 0, /* tp_getattr */ - 0, /* tp_setattr */ - 0, /* tp_reserved */ - 0, /* tp_repr */ - 0, /* tp_as_number */ - 0, /* tp_as_sequence */ - 0, /* tp_as_mapping */ - 0, /* tp_hash */ - 0, /* tp_call */ - 0, /* tp_str */ - PyObject_GenericGetAttr, /* tp_getattro */ - 0, /* tp_setattro */ - 0, /* tp_as_buffer */ - Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ - 0, /* tp_doc */ - (traverseproc)listreviter_traverse, /* tp_traverse */ - 0, /* tp_clear */ - 0, /* tp_richcompare */ - 0, /* tp_weaklistoffset */ - PyObject_SelfIter, /* tp_iter */ - (iternextfunc)listreviter_next, /* tp_iternext */ - listreviter_methods, /* tp_methods */ - 0, + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "list_reverseiterator", /* tp_name */ + sizeof(listreviterobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)listreviter_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ + 0, /* tp_doc */ + (traverseproc)listreviter_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + PyObject_SelfIter, /* tp_iter */ + (iternextfunc)listreviter_next, /* tp_iternext */ + listreviter_methods, /* tp_methods */ + 0, }; static PyObject * list_reversed(PyListObject *seq, PyObject *unused) { - listreviterobject *it; + listreviterobject *it; - it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type); - if (it == NULL) - return NULL; - assert(PyList_Check(seq)); - it->it_index = PyList_GET_SIZE(seq) - 1; - Py_INCREF(seq); - it->it_seq = seq; - PyObject_GC_Track(it); - return (PyObject *)it; + it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type); + if (it == NULL) + return NULL; + assert(PyList_Check(seq)); + it->it_index = PyList_GET_SIZE(seq) - 1; + Py_INCREF(seq); + it->it_seq = seq; + PyObject_GC_Track(it); + return (PyObject *)it; } static void listreviter_dealloc(listreviterobject *it) { - PyObject_GC_UnTrack(it); - Py_XDECREF(it->it_seq); - PyObject_GC_Del(it); + PyObject_GC_UnTrack(it); + Py_XDECREF(it->it_seq); + PyObject_GC_Del(it); } static int listreviter_traverse(listreviterobject *it, visitproc visit, void *arg) { - Py_VISIT(it->it_seq); - return 0; + Py_VISIT(it->it_seq); + return 0; } static PyObject * listreviter_next(listreviterobject *it) { - PyObject *item; - Py_ssize_t index = it->it_index; - PyListObject *seq = it->it_seq; + PyObject *item; + Py_ssize_t index = it->it_index; + PyListObject *seq = it->it_seq; - if (index>=0 && index < PyList_GET_SIZE(seq)) { - item = PyList_GET_ITEM(seq, index); - it->it_index--; - Py_INCREF(item); - return item; - } - it->it_index = -1; - if (seq != NULL) { - it->it_seq = NULL; - Py_DECREF(seq); - } - return NULL; + if (index>=0 && index < PyList_GET_SIZE(seq)) { + item = PyList_GET_ITEM(seq, index); + it->it_index--; + Py_INCREF(item); + return item; + } + it->it_index = -1; + if (seq != NULL) { + it->it_seq = NULL; + Py_DECREF(seq); + } + return NULL; } static PyObject * listreviter_len(listreviterobject *it) { - Py_ssize_t len = it->it_index + 1; - if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len) - len = 0; - return PyLong_FromSsize_t(len); + Py_ssize_t len = it->it_index + 1; + if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len) + len = 0; + return PyLong_FromSsize_t(len); } |