/* List object implementation */ #include "Python.h" #ifdef STDC_HEADERS#include <stddef.h>#else#include <sys/types.h> /* For size_t */#endif /* Ensure ob_item has room for at least newsize elements, and set * ob_size to newsize. If newsize > ob_size on entry, the content * of the new slots at exit is undefined heap trash; it's the caller's * responsiblity to overwrite them with sane values. * The number of allocated elements may grow, shrink, or stay the same. * Failure is impossible if newsize <= self.allocated on entry, although * that partly relies on an assumption that the system realloc() never * fails when passed a number of bytes <= the number of bytes last * allocated (the C standard doesn't guarantee this, but it's hard to * imagine a realloc implementation where it wouldn't be true). * Note that self->ob_item may change, and even if newsize is less * than ob_size on entry. */static intlist_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); self->ob_size = 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) + 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; self->ob_size = newsize; self->allocated = new_allocated; return 0;} /* Empty list reuse scheme to save calls to malloc and free */#define MAXFREELISTS 80static PyListObject *free_lists[MAXFREELISTS];static int num_free_lists = 0; voidPyList_Fini(void){ PyListObject *op; while (num_free_lists) { num_free_lists--; op = free_lists[num_free_lists]; assert(PyList_CheckExact(op)); PyObject_GC_Del(op); }} PyObject *PyList_New(Py_ssize_t size){ PyListObject *op; size_t nbytes; if (size < 0) { PyErr_BadInternalCall(); return NULL; } nbytes = size * sizeof(PyObject *); /* Check for overflow */ if (nbytes / sizeof(PyObject *) != (size_t)size) return PyErr_NoMemory(); if (num_free_lists) { num_free_lists--; op = free_lists[num_free_lists]; _Py_NewReference((PyObject *)op); } else { op = PyObject_GC_New(PyListObject, &PyList_Type); if (op == NULL) return NULL; } 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); } op->ob_size = size; op->allocated = size; _PyObject_GC_TRACK(op); return (PyObject *) op;} Py_ssize_tPyList_Size(PyObject *op){ if (!PyList_Check(op)) { PyErr_BadInternalCall(); return -1; } else return ((PyListObject *)op) -> ob_size;} 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 >= ((PyListObject *)op) -> ob_size) { if (indexerr == NULL) indexerr = PyString_FromString( "list index out of range"); PyErr_SetObject(PyExc_IndexError, indexerr); return NULL; } return ((PyListObject *)op) -> ob_item[i];} intPyList_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 >= ((PyListObject *)op) -> ob_size) { 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 intins1(PyListObject *self, Py_ssize_t where, PyObject *v){ Py_ssize_t i, n = self->ob_size; 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;} intPyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem){ if (!PyList_Check(op)) { PyErr_BadInternalCall(); return -1; } return ins1((PyListObject *)op, where, newitem);} static intapp1(PyListObject *self, PyObject *v){ 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; } if (list_resize(self, n+1) == -1) return -1; Py_INCREF(v); PyList_SET_ITEM(self, n, v); return 0;} intPyList_Append(PyObject *op, PyObject *newitem){ if (PyList_Check(op) && (newitem != NULL)) return app1((PyListObject *)op, newitem); PyErr_BadInternalCall(); return -1;} /* Methods */ static voidlist_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 = op->ob_size; while (--i >= 0) { Py_XDECREF(op->ob_item[i]); } PyMem_FREE(op->ob_item); } if (num_free_lists < MAXFREELISTS && PyList_CheckExact(op)) free_lists[num_free_lists++] = op; else op->ob_type->tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op)} static intlist_print(PyListObject *op, FILE *fp, int flags){ int rc; Py_ssize_t i; rc = Py_ReprEnter((PyObject*)op); if (rc != 0) { if (rc < 0) return rc; fprintf(fp, "[...]"); return 0; } fprintf(fp, "["); for (i = 0; i < op->ob_size; i++) { if (i > 0) fprintf(fp, ", "); if (PyObject_Print(op->ob_item[i], fp, 0) != 0) { Py_ReprLeave((PyObject *)op); return -1; } } fprintf(fp, "]"); Py_ReprLeave((PyObject *)op); return 0;} 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 ? PyString_FromString("[...]") : NULL; } if (v->ob_size == 0) { result = PyString_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 < v->ob_size; ++i) { int status; s = PyObject_Repr(v->ob_item[i]); 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 = PyString_FromString("["); if (s == NULL) goto Done; temp = PyList_GET_ITEM(pieces, 0); PyString_ConcatAndDel(&s, temp); PyList_SET_ITEM(pieces, 0, s); if (s == NULL) goto Done; s = PyString_FromString("]"); if (s == NULL) goto Done; temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1); PyString_ConcatAndDel(&temp, s); PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp); if (temp == NULL) goto Done; /* Paste them all together with ", " between. */ s = PyString_FromString(", "); if (s == NULL) goto Done; result = _PyString_Join(s, pieces); Py_DECREF(s); Done: Py_XDECREF(pieces); Py_ReprLeave((PyObject *)v); return result;} static Py_ssize_tlist_length(PyListObject *a){ return a->ob_size;} static intlist_contains(PyListObject *a, PyObject *el){ Py_ssize_t i; int cmp; for (i = 0, cmp = 0 ; cmp == 0 && i < a->ob_size; ++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 >= a->ob_size) { if (indexerr == NULL) indexerr = PyString_FromString( "list index out of range"); 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 > a->ob_size) ilow = a->ob_size; if (ihigh < ilow) ihigh = ilow; else if (ihigh > a->ob_size) ihigh = a->ob_size; 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);} 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; }#define b ((PyListObject *)bb) size = a->ob_size + b->ob_size; 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 < a->ob_size; i++) { PyObject *v = src[i]; Py_INCREF(v); dest[i] = v; } src = b->ob_item; dest = np->ob_item + a->ob_size; for (i = 0; i < b->ob_size; 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 = a->ob_size * n; if (size == 0) return PyList_New(0); if (n && size/n != a->ob_size) return PyErr_NoMemory(); np = (PyListObject *) PyList_New(size); if (np == NULL) return NULL; items = np->ob_item; if (a->ob_size == 1) { elem = a->ob_item[0];Lines 1–500 of 2930. Load more
/* List object implementation */ #include "Python.h" #ifdef STDC_HEADERS #include <stddef.h> #else #include <sys/types.h> /* For size_t */ #endif /* Ensure ob_item has room for at least newsize elements, and set * ob_size to newsize. If newsize > ob_size on entry, the content * of the new slots at exit is undefined heap trash; it's the caller's * responsiblity to overwrite them with sane values. * The number of allocated elements may grow, shrink, or stay the same. * Failure is impossible if newsize <= self.allocated on entry, although * that partly relies on an assumption that the system realloc() never * fails when passed a number of bytes <= the number of bytes last * allocated (the C standard doesn't guarantee this, but it's hard to * imagine a realloc implementation where it wouldn't be true). * Note that self->ob_item may change, and even if newsize is less * than ob_size on entry. */ 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); self->ob_size = 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) + 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; self->ob_size = newsize; self->allocated = new_allocated; return 0; } /* Empty list reuse scheme to save calls to malloc and free */ #define MAXFREELISTS 80 static PyListObject *free_lists[MAXFREELISTS]; static int num_free_lists = 0; void PyList_Fini(void) { PyListObject *op; while (num_free_lists) { num_free_lists--; op = free_lists[num_free_lists]; assert(PyList_CheckExact(op)); PyObject_GC_Del(op); } } PyObject * PyList_New(Py_ssize_t size) { PyListObject *op; size_t nbytes; if (size < 0) { PyErr_BadInternalCall(); return NULL; } nbytes = size * sizeof(PyObject *); /* Check for overflow */ if (nbytes / sizeof(PyObject *) != (size_t)size) return PyErr_NoMemory(); if (num_free_lists) { num_free_lists--; op = free_lists[num_free_lists]; _Py_NewReference((PyObject *)op); } else { op = PyObject_GC_New(PyListObject, &PyList_Type); if (op == NULL) return NULL; } 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); } op->ob_size = 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 ((PyListObject *)op) -> ob_size; } 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 >= ((PyListObject *)op) -> ob_size) { if (indexerr == NULL) indexerr = PyString_FromString( "list index out of range"); 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 >= ((PyListObject *)op) -> ob_size) { 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 = self->ob_size; 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); } static int app1(PyListObject *self, PyObject *v) { 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; } if (list_resize(self, n+1) == -1) return -1; 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; } /* Methods */ 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 = op->ob_size; while (--i >= 0) { Py_XDECREF(op->ob_item[i]); } PyMem_FREE(op->ob_item); } if (num_free_lists < MAXFREELISTS && PyList_CheckExact(op)) free_lists[num_free_lists++] = op; else op->ob_type->tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op) } static int list_print(PyListObject *op, FILE *fp, int flags) { int rc; Py_ssize_t i; rc = Py_ReprEnter((PyObject*)op); if (rc != 0) { if (rc < 0) return rc; fprintf(fp, "[...]"); return 0; } fprintf(fp, "["); for (i = 0; i < op->ob_size; i++) { if (i > 0) fprintf(fp, ", "); if (PyObject_Print(op->ob_item[i], fp, 0) != 0) { Py_ReprLeave((PyObject *)op); return -1; } } fprintf(fp, "]"); Py_ReprLeave((PyObject *)op); return 0; } 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 ? PyString_FromString("[...]") : NULL; } if (v->ob_size == 0) { result = PyString_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 < v->ob_size; ++i) { int status; s = PyObject_Repr(v->ob_item[i]); 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 = PyString_FromString("["); if (s == NULL) goto Done; temp = PyList_GET_ITEM(pieces, 0); PyString_ConcatAndDel(&s, temp); PyList_SET_ITEM(pieces, 0, s); if (s == NULL) goto Done; s = PyString_FromString("]"); if (s == NULL) goto Done; temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1); PyString_ConcatAndDel(&temp, s); PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp); if (temp == NULL) goto Done; /* Paste them all together with ", " between. */ s = PyString_FromString(", "); if (s == NULL) goto Done; result = _PyString_Join(s, pieces); Py_DECREF(s); Done: Py_XDECREF(pieces); Py_ReprLeave((PyObject *)v); return result; } static Py_ssize_t list_length(PyListObject *a) { return a->ob_size; } static int list_contains(PyListObject *a, PyObject *el) { Py_ssize_t i; int cmp; for (i = 0, cmp = 0 ; cmp == 0 && i < a->ob_size; ++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 >= a->ob_size) { if (indexerr == NULL) indexerr = PyString_FromString( "list index out of range"); 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 > a->ob_size) ilow = a->ob_size; if (ihigh < ilow) ihigh = ilow; else if (ihigh > a->ob_size) ihigh = a->ob_size; 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); } 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; } #define b ((PyListObject *)bb) size = a->ob_size + b->ob_size; 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 < a->ob_size; i++) { PyObject *v = src[i]; Py_INCREF(v); dest[i] = v; } src = b->ob_item; dest = np->ob_item + a->ob_size; for (i = 0; i < b->ob_size; 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 = a->ob_size * n; if (size == 0) return PyList_New(0); if (n && size/n != a->ob_size) return PyErr_NoMemory(); np = (PyListObject *) PyList_New(size); if (np == NULL) return NULL; items = np->ob_item; if (a->ob_size == 1) { elem = a->ob_item[0];