summaryrefslogtreecommitdiffstats
path: root/Objects/listobject.c
diff options
context:
space:
mode:
Diffstat (limited to 'Objects/listobject.c')
-rw-r--r--Objects/listobject.c1977
1 files changed, 827 insertions, 1150 deletions
diff --git a/Objects/listobject.c b/Objects/listobject.c
index 645742b..24eff76 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -1,10 +1,6 @@
/* List object implementation */
#include "Python.h"
-#include "pycore_object.h"
-#include "pycore_pystate.h"
-#include "pycore_tupleobject.h"
-#include "pycore_accu.h"
#ifdef STDC_HEADERS
#include <stddef.h>
@@ -12,13 +8,6 @@
#include <sys/types.h> /* For size_t */
#endif
-/*[clinic input]
-class list "PyListObject *" "&PyList_Type"
-[clinic start generated code]*/
-/*[clinic end generated code: output=da39a3ee5e6b4b0d input=f9b222678f9f71e0]*/
-
-#include "clinic/listobject.c.h"
-
/* 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
@@ -36,7 +25,7 @@ static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
- size_t new_allocated, num_allocated_bytes;
+ size_t new_allocated;
Py_ssize_t allocated = self->allocated;
/* Bypass realloc() when a previous overallocation is large enough
@@ -55,19 +44,24 @@ list_resize(PyListObject *self, Py_ssize_t newsize)
* 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, ...
- * Note: new_allocated won't overflow because the largest possible value
- * is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
*/
- new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);
- if (new_allocated > (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
+ 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;
- num_allocated_bytes = new_allocated * sizeof(PyObject *);
- items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
+ items = self->ob_item;
+ if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
+ PyMem_RESIZE(items, PyObject *, new_allocated);
+ else
+ items = NULL;
if (items == NULL) {
PyErr_NoMemory();
return -1;
@@ -78,22 +72,6 @@ list_resize(PyListObject *self, Py_ssize_t newsize)
return 0;
}
-static int
-list_preallocate_exact(PyListObject *self, Py_ssize_t size)
-{
- assert(self->ob_item == NULL);
- assert(size > 0);
-
- PyObject **items = PyMem_New(PyObject*, size);
- if (items == NULL) {
- PyErr_NoMemory();
- return -1;
- }
- self->ob_item = items;
- self->allocated = size;
- return 0;
-}
-
/* Debug statistic to compare allocations with reuse through the free list */
#undef SHOW_ALLOC_COUNT
#ifdef SHOW_ALLOC_COUNT
@@ -103,11 +81,6 @@ static size_t count_reuse = 0;
static void
show_alloc(void)
{
- PyInterpreterState *interp = _PyInterpreterState_Get();
- if (!interp->config.show_alloc_count) {
- return;
- }
-
fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n",
count_alloc);
fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T
@@ -124,38 +97,23 @@ show_alloc(void)
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;
-int
-PyList_ClearFreeList(void)
+void
+PyList_Fini(void)
{
PyListObject *op;
- int ret = numfree;
+
while (numfree) {
op = free_list[--numfree];
assert(PyList_CheckExact(op));
PyObject_GC_Del(op);
}
- return ret;
-}
-
-void
-_PyList_Fini(void)
-{
- PyList_ClearFreeList();
-}
-
-/* Print summary info about the state of the optimized allocator */
-void
-_PyList_DebugMallocStats(FILE *out)
-{
- _PyDebugAllocatorStats(out,
- "free PyListObject",
- numfree, sizeof(PyListObject));
}
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
+ size_t nbytes;
#ifdef SHOW_ALLOC_COUNT
static int initialized = 0;
if (!initialized) {
@@ -168,6 +126,11 @@ PyList_New(Py_ssize_t size)
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];
@@ -186,11 +149,12 @@ PyList_New(Py_ssize_t size)
if (size <= 0)
op->ob_item = NULL;
else {
- op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
+ 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;
@@ -198,23 +162,6 @@ PyList_New(Py_ssize_t size)
return (PyObject *) op;
}
-static PyObject *
-list_new_prealloc(Py_ssize_t size)
-{
- PyListObject *op = (PyListObject *) PyList_New(0);
- if (size == 0 || op == NULL) {
- return (PyObject *) op;
- }
- assert(op->ob_item == NULL);
- op->ob_item = PyMem_New(PyObject *, size);
- if (op->ob_item == NULL) {
- Py_DECREF(op);
- return PyErr_NoMemory();
- }
- op->allocated = size;
- return (PyObject *) op;
-}
-
Py_ssize_t
PyList_Size(PyObject *op)
{
@@ -226,19 +173,6 @@ PyList_Size(PyObject *op)
return Py_SIZE(op);
}
-static inline int
-valid_index(Py_ssize_t i, Py_ssize_t limit)
-{
- /* The cast to size_t lets us use just a single comparison
- to check whether i is in the range: 0 <= i < limit.
-
- See: Section 14.2 "Bounds Checking" in the Agner Fog
- optimization manual found at:
- https://www.agner.org/optimize/optimizing_cpp.pdf
- */
- return (size_t) i < (size_t) limit;
-}
-
static PyObject *indexerr = NULL;
PyObject *
@@ -248,9 +182,9 @@ PyList_GetItem(PyObject *op, Py_ssize_t i)
PyErr_BadInternalCall();
return NULL;
}
- if (!valid_index(i, Py_SIZE(op))) {
+ if (i < 0 || i >= Py_SIZE(op)) {
if (indexerr == NULL) {
- indexerr = PyUnicode_FromString(
+ indexerr = PyString_FromString(
"list index out of range");
if (indexerr == NULL)
return NULL;
@@ -262,23 +196,26 @@ PyList_GetItem(PyObject *op, Py_ssize_t i)
}
int
-PyList_SetItem(PyObject *op, Py_ssize_t i,
- PyObject *newitem)
+PyList_SetItem(register PyObject *op, register Py_ssize_t i,
+ register PyObject *newitem)
{
- PyObject **p;
+ register PyObject *olditem;
+ register PyObject **p;
if (!PyList_Check(op)) {
Py_XDECREF(newitem);
PyErr_BadInternalCall();
return -1;
}
- if (!valid_index(i, Py_SIZE(op))) {
+ 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;
- Py_XSETREF(*p, newitem);
+ olditem = *p;
+ *p = newitem;
+ Py_XDECREF(olditem);
return 0;
}
@@ -297,7 +234,7 @@ ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
return -1;
}
- if (list_resize(self, n+1) < 0)
+ if (list_resize(self, n+1) == -1)
return -1;
if (where < 0) {
@@ -337,7 +274,7 @@ app1(PyListObject *self, PyObject *v)
return -1;
}
- if (list_resize(self, n+1) < 0)
+ if (list_resize(self, n+1) == -1)
return -1;
Py_INCREF(v);
@@ -361,7 +298,7 @@ list_dealloc(PyListObject *op)
{
Py_ssize_t i;
PyObject_GC_UnTrack(op);
- Py_TRASHCAN_BEGIN(op, list_dealloc)
+ 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
@@ -377,63 +314,115 @@ list_dealloc(PyListObject *op)
free_list[numfree++] = op;
else
Py_TYPE(op)->tp_free((PyObject *)op);
- Py_TRASHCAN_END
+ Py_TRASHCAN_SAFE_END(op)
}
-static PyObject *
-list_repr(PyListObject *v)
+static int
+list_print(PyListObject *op, FILE *fp, int flags)
{
+ int rc;
Py_ssize_t i;
- PyObject *s;
- _PyUnicodeWriter writer;
+ PyObject *item;
- if (Py_SIZE(v) == 0) {
- return PyUnicode_FromString("[]");
+ rc = Py_ReprEnter((PyObject*)op);
+ if (rc != 0) {
+ if (rc < 0)
+ return rc;
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, "[...]");
+ Py_END_ALLOW_THREADS
+ return 0;
}
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, "[");
+ Py_END_ALLOW_THREADS
+ for (i = 0; i < Py_SIZE(op); i++) {
+ item = op->ob_item[i];
+ Py_INCREF(item);
+ if (i > 0) {
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, ", ");
+ Py_END_ALLOW_THREADS
+ }
+ if (PyObject_Print(item, fp, 0) != 0) {
+ Py_DECREF(item);
+ Py_ReprLeave((PyObject *)op);
+ return -1;
+ }
+ Py_DECREF(item);
+ }
+ Py_BEGIN_ALLOW_THREADS
+ fprintf(fp, "]");
+ Py_END_ALLOW_THREADS
+ 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 ? PyUnicode_FromString("[...]") : NULL;
+ return i > 0 ? PyString_FromString("[...]") : NULL;
}
- _PyUnicodeWriter_Init(&writer);
- writer.overallocate = 1;
- /* "[" + "1" + ", 2" * (len - 1) + "]" */
- writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
+ if (Py_SIZE(v) == 0) {
+ result = PyString_FromString("[]");
+ goto Done;
+ }
- if (_PyUnicodeWriter_WriteChar(&writer, '[') < 0)
- goto error;
+ 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) {
- if (i > 0) {
- if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
- goto error;
- }
-
+ int status;
s = PyObject_Repr(v->ob_item[i]);
if (s == NULL)
- goto error;
-
- if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
- Py_DECREF(s);
- goto error;
- }
- Py_DECREF(s);
- }
-
- writer.overallocate = 0;
- if (_PyUnicodeWriter_WriteChar(&writer, ']') < 0)
- goto error;
-
- Py_ReprLeave((PyObject *)v);
- return _PyUnicodeWriter_Finish(&writer);
-
-error:
- _PyUnicodeWriter_Dealloc(&writer);
+ 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 NULL;
+ return result;
}
static Py_ssize_t
@@ -449,16 +438,17 @@ list_contains(PyListObject *a, PyObject *el)
int cmp;
for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
- cmp = PyObject_RichCompareBool(PyList_GET_ITEM(a, i), el, Py_EQ);
+ cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
+ Py_EQ);
return cmp;
}
static PyObject *
list_item(PyListObject *a, Py_ssize_t i)
{
- if (!valid_index(i, Py_SIZE(a))) {
+ if (i < 0 || i >= Py_SIZE(a)) {
if (indexerr == NULL) {
- indexerr = PyUnicode_FromString(
+ indexerr = PyString_FromString(
"list index out of range");
if (indexerr == NULL)
return NULL;
@@ -476,8 +466,16 @@ 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 *) list_new_prealloc(len);
+ np = (PyListObject *) PyList_New(len);
if (np == NULL)
return NULL;
@@ -488,7 +486,6 @@ list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
Py_INCREF(v);
dest[i] = v;
}
- Py_SIZE(np) = len;
return (PyObject *)np;
}
@@ -499,18 +496,6 @@ PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
PyErr_BadInternalCall();
return NULL;
}
- 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);
- }
return list_slice((PyListObject *)a, ilow, ihigh);
}
@@ -528,10 +513,10 @@ list_concat(PyListObject *a, PyObject *bb)
return NULL;
}
#define b ((PyListObject *)bb)
- if (Py_SIZE(a) > PY_SSIZE_T_MAX - Py_SIZE(b))
- return PyErr_NoMemory();
size = Py_SIZE(a) + Py_SIZE(b);
- np = (PyListObject *) list_new_prealloc(size);
+ if (size < 0)
+ return PyErr_NoMemory();
+ np = (PyListObject *) PyList_New(size);
if (np == NULL) {
return NULL;
}
@@ -549,7 +534,6 @@ list_concat(PyListObject *a, PyObject *bb)
Py_INCREF(v);
dest[i] = v;
}
- Py_SIZE(np) = size;
return (PyObject *)np;
#undef b
}
@@ -569,35 +553,33 @@ list_repeat(PyListObject *a, Py_ssize_t n)
size = Py_SIZE(a) * n;
if (size == 0)
return PyList_New(0);
- np = (PyListObject *) list_new_prealloc(size);
+ np = (PyListObject *) PyList_New(size);
if (np == NULL)
return NULL;
+ items = np->ob_item;
if (Py_SIZE(a) == 1) {
- items = np->ob_item;
elem = a->ob_item[0];
for (i = 0; i < n; i++) {
items[i] = elem;
Py_INCREF(elem);
}
- }
- else {
- 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;
+ }
+ 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++;
}
}
- Py_SIZE(np) = size;
return (PyObject *) np;
}
static int
-_list_clear(PyListObject *a)
+list_clear(PyListObject *a)
{
Py_ssize_t i;
PyObject **item = a->ob_item;
@@ -679,7 +661,7 @@ list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
d = n - norig;
if (Py_SIZE(a) + d == 0) {
Py_XDECREF(v_as_SF);
- return _list_clear(a);
+ return list_clear(a);
}
item = a->ob_item;
/* recycle the items that we are about to remove */
@@ -697,14 +679,9 @@ list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
}
if (d < 0) { /* Delete -d items */
- Py_ssize_t tail;
- tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *);
- memmove(&item[ihigh+d], &item[ihigh], tail);
- if (list_resize(a, Py_SIZE(a) + d) < 0) {
- memmove(&item[ihigh], &item[ihigh+d], tail);
- memcpy(&item[ilow], recycle, s);
- goto Error;
- }
+ 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 */
@@ -755,7 +732,7 @@ list_inplace_repeat(PyListObject *self, Py_ssize_t n)
}
if (n < 1) {
- (void)_list_clear(self);
+ (void)list_clear(self);
Py_INCREF(self);
return (PyObject *)self;
}
@@ -764,7 +741,7 @@ list_inplace_repeat(PyListObject *self, Py_ssize_t n)
return PyErr_NoMemory();
}
- if (list_resize(self, size*n) < 0)
+ if (list_resize(self, size*n) == -1)
return NULL;
p = size;
@@ -783,7 +760,8 @@ list_inplace_repeat(PyListObject *self, Py_ssize_t n)
static int
list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
{
- if (!valid_index(i, Py_SIZE(a))) {
+ PyObject *old_value;
+ if (i < 0 || i >= Py_SIZE(a)) {
PyErr_SetString(PyExc_IndexError,
"list assignment index out of range");
return -1;
@@ -791,90 +769,38 @@ list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
if (v == NULL)
return list_ass_slice(a, i, i+1, v);
Py_INCREF(v);
- Py_SETREF(a->ob_item[i], v);
+ old_value = a->ob_item[i];
+ a->ob_item[i] = v;
+ Py_DECREF(old_value);
return 0;
}
-/*[clinic input]
-list.insert
-
- index: Py_ssize_t
- object: object
- /
-
-Insert object before index.
-[clinic start generated code]*/
-
static PyObject *
-list_insert_impl(PyListObject *self, Py_ssize_t index, PyObject *object)
-/*[clinic end generated code: output=7f35e32f60c8cb78 input=858514cf894c7eab]*/
+listinsert(PyListObject *self, PyObject *args)
{
- if (ins1(self, index, object) == 0)
+ 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;
}
-/*[clinic input]
-list.clear
-
-Remove all items from list.
-[clinic start generated code]*/
-
static PyObject *
-list_clear_impl(PyListObject *self)
-/*[clinic end generated code: output=67a1896c01f74362 input=ca3c1646856742f6]*/
+listappend(PyListObject *self, PyObject *v)
{
- _list_clear(self);
- Py_RETURN_NONE;
-}
-
-/*[clinic input]
-list.copy
-
-Return a shallow copy of the list.
-[clinic start generated code]*/
-
-static PyObject *
-list_copy_impl(PyListObject *self)
-/*[clinic end generated code: output=ec6b72d6209d418e input=6453ab159e84771f]*/
-{
- return list_slice(self, 0, Py_SIZE(self));
-}
-
-/*[clinic input]
-list.append
-
- object: object
- /
-
-Append object to the end of the list.
-[clinic start generated code]*/
-
-static PyObject *
-list_append(PyListObject *self, PyObject *object)
-/*[clinic end generated code: output=7c096003a29c0eae input=43a3fe48a7066e91]*/
-{
- if (app1(self, object) == 0)
+ if (app1(self, v) == 0)
Py_RETURN_NONE;
return NULL;
}
-/*[clinic input]
-list.extend
-
- iterable: object
- /
-
-Extend list by appending elements from the iterable.
-[clinic start generated code]*/
-
static PyObject *
-list_extend(PyListObject *self, PyObject *iterable)
-/*[clinic end generated code: output=630fb3bca0c8e789 input=9ec5ba3a81be3a4d]*/
+listextend(PyListObject *self, PyObject *b)
{
PyObject *it; /* iter(v) */
Py_ssize_t m; /* size of self */
- Py_ssize_t n; /* guess for size of iterable */
+ Py_ssize_t n; /* guess for size of b */
Py_ssize_t mn; /* m + n */
Py_ssize_t i;
PyObject *(*iternext)(PyObject *);
@@ -883,69 +809,63 @@ list_extend(PyListObject *self, PyObject *iterable)
1) lists and tuples which can use PySequence_Fast ops
2) extending self to self requires making a copy first
*/
- if (PyList_CheckExact(iterable) || PyTuple_CheckExact(iterable) ||
- (PyObject *)self == iterable) {
+ if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {
PyObject **src, **dest;
- iterable = PySequence_Fast(iterable, "argument must be iterable");
- if (!iterable)
+ b = PySequence_Fast(b, "argument must be iterable");
+ if (!b)
return NULL;
- n = PySequence_Fast_GET_SIZE(iterable);
+ n = PySequence_Fast_GET_SIZE(b);
if (n == 0) {
- /* short circuit when iterable is empty */
- Py_DECREF(iterable);
+ /* short circuit when b is empty */
+ Py_DECREF(b);
Py_RETURN_NONE;
}
m = Py_SIZE(self);
- /* It should not be possible to allocate a list large enough to cause
- an overflow on any relevant platform */
- assert(m < PY_SSIZE_T_MAX - n);
- if (list_resize(self, m + n) < 0) {
- Py_DECREF(iterable);
+ if (list_resize(self, m + n) == -1) {
+ Py_DECREF(b);
return NULL;
}
- /* note that we may still have self == iterable here for the
+ /* 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 iterable's items */
- src = PySequence_Fast_ITEMS(iterable);
+ /* 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(iterable);
+ Py_DECREF(b);
Py_RETURN_NONE;
}
- it = PyObject_GetIter(iterable);
+ it = PyObject_GetIter(b);
if (it == NULL)
return NULL;
iternext = *it->ob_type->tp_iternext;
/* Guess a result list size. */
- n = PyObject_LengthHint(iterable, 8);
- if (n < 0) {
+ n = _PyObject_LengthHint(b, 8);
+ if (n == -1) {
Py_DECREF(it);
return NULL;
}
m = Py_SIZE(self);
- if (m > PY_SSIZE_T_MAX - n) {
- /* 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.
- */
- }
- else {
- mn = m + n;
+ mn = m + n;
+ if (mn >= m) {
/* Make room. */
- if (list_resize(self, mn) < 0)
+ 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 (;;) {
@@ -973,10 +893,8 @@ list_extend(PyListObject *self, PyObject *iterable)
}
/* Cut back result list if initial guess was too large. */
- if (Py_SIZE(self) < self->allocated) {
- if (list_resize(self, Py_SIZE(self)) < 0)
- goto error;
- }
+ if (Py_SIZE(self) < self->allocated)
+ list_resize(self, Py_SIZE(self)); /* shrinking can't fail */
Py_DECREF(it);
Py_RETURN_NONE;
@@ -987,9 +905,9 @@ list_extend(PyListObject *self, PyObject *iterable)
}
PyObject *
-_PyList_Extend(PyListObject *self, PyObject *iterable)
+_PyList_Extend(PyListObject *self, PyObject *b)
{
- return list_extend(self, iterable);
+ return listextend(self, b);
}
static PyObject *
@@ -997,7 +915,7 @@ list_inplace_concat(PyListObject *self, PyObject *other)
{
PyObject *result;
- result = list_extend(self, other);
+ result = listextend(self, other);
if (result == NULL)
return result;
Py_DECREF(result);
@@ -1005,49 +923,41 @@ list_inplace_concat(PyListObject *self, PyObject *other)
return (PyObject *)self;
}
-/*[clinic input]
-list.pop
-
- index: Py_ssize_t = -1
- /
-
-Remove and return item at index (default last).
-
-Raises IndexError if list is empty or index is out of range.
-[clinic start generated code]*/
-
static PyObject *
-list_pop_impl(PyListObject *self, Py_ssize_t index)
-/*[clinic end generated code: output=6bd69dcb3f17eca8 input=b83675976f329e6f]*/
+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 (index < 0)
- index += Py_SIZE(self);
- if (!valid_index(index, Py_SIZE(self))) {
+ 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[index];
- if (index == Py_SIZE(self) - 1) {
+ v = self->ob_item[i];
+ if (i == Py_SIZE(self) - 1) {
status = list_resize(self, Py_SIZE(self) - 1);
- if (status >= 0)
- return v; /* and v now owns the reference the list had */
- else
- return NULL;
+ assert(status >= 0);
+ return v; /* and v now owns the reference the list had */
}
Py_INCREF(v);
- status = list_ass_slice(self, index, index+1, (PyObject *)NULL);
- if (status < 0) {
- Py_DECREF(v);
- return NULL;
- }
+ 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;
}
@@ -1071,154 +981,62 @@ reverse_slice(PyObject **lo, PyObject **hi)
* pieces to this algorithm; read listsort.txt for overviews and details.
*/
-/* A sortslice contains a pointer to an array of keys and a pointer to
- * an array of corresponding values. In other words, keys[i]
- * corresponds with values[i]. If values == NULL, then the keys are
- * also the values.
- *
- * Several convenience routines are provided here, so that keys and
- * values are always moved in sync.
+/* Comparison function. Takes care of calling a user-supplied
+ * comparison function (any callable Python object), which must not be
+ * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
+ * with Py_LT if you know it's NULL).
+ * Returns -1 on error, 1 if x < y, 0 if x >= y.
*/
-
-typedef struct {
- PyObject **keys;
- PyObject **values;
-} sortslice;
-
-Py_LOCAL_INLINE(void)
-sortslice_copy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j)
-{
- s1->keys[i] = s2->keys[j];
- if (s1->values != NULL)
- s1->values[i] = s2->values[j];
-}
-
-Py_LOCAL_INLINE(void)
-sortslice_copy_incr(sortslice *dst, sortslice *src)
-{
- *dst->keys++ = *src->keys++;
- if (dst->values != NULL)
- *dst->values++ = *src->values++;
-}
-
-Py_LOCAL_INLINE(void)
-sortslice_copy_decr(sortslice *dst, sortslice *src)
-{
- *dst->keys-- = *src->keys--;
- if (dst->values != NULL)
- *dst->values-- = *src->values--;
-}
-
-
-Py_LOCAL_INLINE(void)
-sortslice_memcpy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
- Py_ssize_t n)
-{
- memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
- if (s1->values != NULL)
- memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
-}
-
-Py_LOCAL_INLINE(void)
-sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
- Py_ssize_t n)
+static int
+islt(PyObject *x, PyObject *y, PyObject *compare)
{
- memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
- if (s1->values != NULL)
- memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
-}
+ PyObject *res;
+ PyObject *args;
+ Py_ssize_t i;
-Py_LOCAL_INLINE(void)
-sortslice_advance(sortslice *slice, Py_ssize_t n)
-{
- slice->keys += n;
- if (slice->values != NULL)
- slice->values += n;
+ assert(compare != NULL);
+ /* Call the user's comparison function and translate the 3-way
+ * result into true or false (or error).
+ */
+ args = PyTuple_New(2);
+ if (args == NULL)
+ return -1;
+ Py_INCREF(x);
+ Py_INCREF(y);
+ PyTuple_SET_ITEM(args, 0, x);
+ PyTuple_SET_ITEM(args, 1, y);
+ res = PyObject_Call(compare, args, NULL);
+ Py_DECREF(args);
+ if (res == NULL)
+ return -1;
+ if (!PyInt_Check(res)) {
+ PyErr_Format(PyExc_TypeError,
+ "comparison function must return int, not %.200s",
+ res->ob_type->tp_name);
+ Py_DECREF(res);
+ return -1;
+ }
+ i = PyInt_AsLong(res);
+ Py_DECREF(res);
+ return i < 0;
}
-/* Comparison function: ms->key_compare, which is set at run-time in
- * listsort_impl to optimize for various special cases.
+/* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
+ * islt. This avoids a layer of function call in the usual case, and
+ * sorting does many comparisons.
* Returns -1 on error, 1 if x < y, 0 if x >= y.
*/
-
-#define ISLT(X, Y) (*(ms->key_compare))(X, Y, ms)
+#define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \
+ PyObject_RichCompareBool(X, Y, Py_LT) : \
+ islt(X, Y, COMPARE))
/* Compare X to Y via "<". Goto "fail" if the comparison raises an
error. Else "k" is set to true iff X<Y, and an "if (k)" block is
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; \
+#define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail; \
if (k)
-/* The maximum number of entries in a MergeState's pending-runs stack.
- * This is enough to sort arrays of size up to about
- * 32 * phi ** MAX_MERGE_PENDING
- * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
- * with 2**64 elements.
- */
-#define MAX_MERGE_PENDING 85
-
-/* When we get into galloping mode, we stay there until both runs win less
- * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
- */
-#define MIN_GALLOP 7
-
-/* Avoid malloc for small temp arrays. */
-#define MERGESTATE_TEMP_SIZE 256
-
-/* One MergeState exists on the stack per invocation of mergesort. It's just
- * a convenient way to pass state around among the helper functions.
- */
-struct s_slice {
- sortslice base;
- Py_ssize_t len;
-};
-
-typedef struct s_MergeState MergeState;
-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.
- */
- sortslice 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 is the function we will use to compare two keys,
- * even when none of our special cases apply and we have to use
- * safe_object_compare. */
- int (*key_compare)(PyObject *, PyObject *, MergeState *);
-
- /* This function is used by unsafe_object_compare to optimize comparisons
- * when we know our list is type-homogeneous but we can't assume anything else.
- * In the pre-sort check it is set equal to key->ob_type->tp_richcompare */
- PyObject *(*key_richcompare)(PyObject *, PyObject *, int);
-
- /* This function is used by unsafe_tuple_compare to compare the first elements
- * of tuples. It may be set to safe_object_compare, but the idea is that hopefully
- * we can assume more, and use one of the special-case compares. */
- int (*tuple_elem_compare)(PyObject *, PyObject *, MergeState *);
-};
-
/* binarysort is the best method for sorting small arrays: it does
few compares, but can do data movement quadratic in the number of
elements.
@@ -1231,19 +1049,20 @@ struct s_MergeState {
the input (nothing is lost or duplicated).
*/
static int
-binarysort(MergeState *ms, sortslice lo, PyObject **hi, PyObject **start)
+binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
+ /* compare -- comparison function object, or NULL for default */
{
- Py_ssize_t k;
- PyObject **l, **p, **r;
- PyObject *pivot;
+ register Py_ssize_t k;
+ register PyObject **l, **p, **r;
+ register PyObject *pivot;
- assert(lo.keys <= start && start <= hi);
+ assert(lo <= start && start <= hi);
/* assert [lo, start) is sorted */
- if (lo.keys == start)
+ if (lo == start)
++start;
for (; start < hi; ++start) {
/* set l to where *start belongs */
- l = lo.keys;
+ l = lo;
r = start;
pivot = *r;
/* Invariants:
@@ -1270,15 +1089,6 @@ binarysort(MergeState *ms, sortslice lo, PyObject **hi, PyObject **start)
for (p = start; p > l; --p)
*p = *(p-1);
*l = pivot;
- if (lo.values != NULL) {
- Py_ssize_t offset = lo.values - lo.keys;
- p = start + offset;
- pivot = *p;
- l += offset;
- for (p = start + offset; p > l; --p)
- *p = *(p-1);
- *l = pivot;
- }
}
return 0;
@@ -1305,7 +1115,7 @@ elements to get out of order).
Returns -1 in case of error.
*/
static Py_ssize_t
-count_run(MergeState *ms, PyObject **lo, PyObject **hi, int *descending)
+count_run(PyObject **lo, PyObject **hi, PyObject *compare, int *descending)
{
Py_ssize_t k;
Py_ssize_t n;
@@ -1360,7 +1170,7 @@ key, and the last n-k should follow key.
Returns -1 on error. See listsort.txt for info on the method.
*/
static Py_ssize_t
-gallop_left(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
+gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare)
{
Py_ssize_t ofs;
Py_ssize_t lastofs;
@@ -1379,8 +1189,9 @@ gallop_left(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_
while (ofs < maxofs) {
IFLT(a[ofs], key) {
lastofs = ofs;
- assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
ofs = (ofs << 1) + 1;
+ if (ofs <= 0) /* int overflow */
+ ofs = maxofs;
}
else /* key <= a[hint + ofs] */
break;
@@ -1401,8 +1212,9 @@ gallop_left(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_
break;
/* key <= a[hint - ofs] */
lastofs = ofs;
- assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
ofs = (ofs << 1) + 1;
+ if (ofs <= 0) /* int overflow */
+ ofs = maxofs;
}
if (ofs > maxofs)
ofs = maxofs;
@@ -1449,7 +1261,7 @@ we're sticking to "<" comparisons that it's much harder to follow if
written as one routine with yet another "left or right?" flag.
*/
static Py_ssize_t
-gallop_right(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
+gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare)
{
Py_ssize_t ofs;
Py_ssize_t lastofs;
@@ -1468,8 +1280,9 @@ gallop_right(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize
while (ofs < maxofs) {
IFLT(key, *(a-ofs)) {
lastofs = ofs;
- assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
ofs = (ofs << 1) + 1;
+ if (ofs <= 0) /* int overflow */
+ ofs = maxofs;
}
else /* a[hint - ofs] <= key */
break;
@@ -1491,8 +1304,9 @@ gallop_right(MergeState *ms, PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize
break;
/* a[hint + ofs] <= key */
lastofs = ofs;
- assert(ofs <= (PY_SSIZE_T_MAX - 1) / 2);
ofs = (ofs << 1) + 1;
+ if (ofs <= 0) /* int overflow */
+ ofs = maxofs;
}
if (ofs > maxofs)
ofs = maxofs;
@@ -1523,31 +1337,70 @@ fail:
return -1;
}
+/* The maximum number of entries in a MergeState's pending-runs stack.
+ * This is enough to sort arrays of size up to about
+ * 32 * phi ** MAX_MERGE_PENDING
+ * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
+ * with 2**64 elements.
+ */
+#define MAX_MERGE_PENDING 85
+
+/* When we get into galloping mode, we stay there until both runs win less
+ * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
+ */
+#define MIN_GALLOP 7
+
+/* Avoid malloc for small temp arrays. */
+#define MERGESTATE_TEMP_SIZE 256
+
+/* One MergeState exists on the stack per invocation of mergesort. It's just
+ * a convenient way to pass state around among the helper functions.
+ */
+struct s_slice {
+ PyObject **base;
+ Py_ssize_t len;
+};
+
+typedef struct s_MergeState {
+ /* The user-supplied comparison function. or NULL if none given. */
+ PyObject *compare;
+
+ /* 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, Py_ssize_t list_size, int has_keyfunc)
+merge_init(MergeState *ms, PyObject *compare)
{
assert(ms != NULL);
- if (has_keyfunc) {
- /* The temporary space for merging will need at most half the list
- * size rounded up. Use the minimum possible space so we can use the
- * rest of temparray for other things. In particular, if there is
- * enough extra space, listsort() will use it to store the keys.
- */
- ms->alloced = (list_size + 1) / 2;
-
- /* ms->alloced describes how many keys will be stored at
- ms->temparray, but we also need to store the values. Hence,
- ms->alloced is capped at half of MERGESTATE_TEMP_SIZE. */
- if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)
- ms->alloced = MERGESTATE_TEMP_SIZE / 2;
- ms->a.values = &ms->temparray[ms->alloced];
- }
- else {
- ms->alloced = MERGESTATE_TEMP_SIZE;
- ms->a.values = NULL;
- }
- ms->a.keys = ms->temparray;
+ ms->compare = compare;
+ ms->a = ms->temparray;
+ ms->alloced = MERGESTATE_TEMP_SIZE;
ms->n = 0;
ms->min_gallop = MIN_GALLOP;
}
@@ -1560,8 +1413,10 @@ static void
merge_freemem(MergeState *ms)
{
assert(ms != NULL);
- if (ms->a.keys != ms->temparray)
- PyMem_Free(ms->a.keys);
+ 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.
@@ -1570,60 +1425,53 @@ merge_freemem(MergeState *ms)
static int
merge_getmem(MergeState *ms, Py_ssize_t need)
{
- int multiplier;
-
assert(ms != NULL);
if (need <= ms->alloced)
return 0;
-
- multiplier = ms->a.values != NULL ? 2 : 1;
-
/* 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 *) / multiplier) {
+ if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) {
PyErr_NoMemory();
return -1;
}
- ms->a.keys = (PyObject **)PyMem_Malloc(multiplier * need
- * sizeof(PyObject *));
- if (ms->a.keys != NULL) {
+ ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*));
+ if (ms->a) {
ms->alloced = need;
- if (ms->a.values != NULL)
- ms->a.values = &ms->a.keys[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 ssa with the nb elements starting at
- * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
- * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
- * should have na <= nb. See listsort.txt for more info. Return 0 if
- * successful, -1 if error.
+/* 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.
+ * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
+ * merge, and should have na <= nb. See listsort.txt for more info.
+ * Return 0 if successful, -1 if error.
*/
static Py_ssize_t
-merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
- sortslice ssb, Py_ssize_t nb)
+merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,
+ PyObject **pb, Py_ssize_t nb)
{
Py_ssize_t k;
- sortslice dest;
+ PyObject *compare;
+ PyObject **dest;
int result = -1; /* guilty until proved innocent */
Py_ssize_t min_gallop;
- assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
- assert(ssa.keys + na == ssb.keys);
+ assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
if (MERGE_GETMEM(ms, na) < 0)
return -1;
- sortslice_memcpy(&ms->a, 0, &ssa, 0, na);
- dest = ssa;
- ssa = ms->a;
+ memcpy(ms->a, pa, na * sizeof(PyObject*));
+ dest = pa;
+ pa = ms->a;
- sortslice_copy_incr(&dest, &ssb);
+ *dest++ = *pb++;
--nb;
if (nb == 0)
goto Succeed;
@@ -1631,6 +1479,7 @@ merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
goto CopyB;
min_gallop = ms->min_gallop;
+ compare = ms->compare;
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 */
@@ -1640,11 +1489,11 @@ merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
*/
for (;;) {
assert(na > 1 && nb > 0);
- k = ISLT(ssb.keys[0], ssa.keys[0]);
+ k = ISLT(*pb, *pa, compare);
if (k) {
if (k < 0)
goto Fail;
- sortslice_copy_incr(&dest, &ssb);
+ *dest++ = *pb++;
++bcount;
acount = 0;
--nb;
@@ -1654,7 +1503,7 @@ merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
break;
}
else {
- sortslice_copy_incr(&dest, &ssa);
+ *dest++ = *pa++;
++acount;
bcount = 0;
--na;
@@ -1675,14 +1524,14 @@ merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
assert(na > 1 && nb > 0);
min_gallop -= min_gallop > 1;
ms->min_gallop = min_gallop;
- k = gallop_right(ms, ssb.keys[0], ssa.keys, na, 0);
+ k = gallop_right(*pb, pa, na, 0, compare);
acount = k;
if (k) {
if (k < 0)
goto Fail;
- sortslice_memcpy(&dest, 0, &ssa, 0, k);
- sortslice_advance(&dest, k);
- sortslice_advance(&ssa, k);
+ memcpy(dest, pa, k * sizeof(PyObject *));
+ dest += k;
+ pa += k;
na -= k;
if (na == 1)
goto CopyB;
@@ -1693,24 +1542,24 @@ merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
if (na == 0)
goto Succeed;
}
- sortslice_copy_incr(&dest, &ssb);
+ *dest++ = *pb++;
--nb;
if (nb == 0)
goto Succeed;
- k = gallop_left(ms, ssa.keys[0], ssb.keys, nb, 0);
+ k = gallop_left(*pa, pb, nb, 0, compare);
bcount = k;
if (k) {
if (k < 0)
goto Fail;
- sortslice_memmove(&dest, 0, &ssb, 0, k);
- sortslice_advance(&dest, k);
- sortslice_advance(&ssb, k);
+ memmove(dest, pb, k * sizeof(PyObject *));
+ dest += k;
+ pb += k;
nb -= k;
if (nb == 0)
goto Succeed;
}
- sortslice_copy_incr(&dest, &ssa);
+ *dest++ = *pa++;
--na;
if (na == 1)
goto CopyB;
@@ -1722,46 +1571,44 @@ Succeed:
result = 0;
Fail:
if (na)
- sortslice_memcpy(&dest, 0, &ssa, 0, na);
+ memcpy(dest, pa, na * sizeof(PyObject*));
return result;
CopyB:
assert(na == 1 && nb > 0);
- /* The last element of ssa belongs at the end of the merge. */
- sortslice_memmove(&dest, 0, &ssb, 0, nb);
- sortslice_copy(&dest, nb, &ssa, 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
- * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
- * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
- * should have na >= nb. See listsort.txt for more info. Return 0 if
- * successful, -1 if error.
+/* 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.
+ * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the
+ * merge, and should have na >= nb. See listsort.txt for more info.
+ * Return 0 if successful, -1 if error.
*/
static Py_ssize_t
-merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
- sortslice ssb, Py_ssize_t nb)
+merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb)
{
Py_ssize_t k;
- sortslice dest, basea, baseb;
+ PyObject *compare;
+ PyObject **dest;
int result = -1; /* guilty until proved innocent */
+ PyObject **basea;
+ PyObject **baseb;
Py_ssize_t min_gallop;
- assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
- assert(ssa.keys + na == ssb.keys);
+ assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);
if (MERGE_GETMEM(ms, nb) < 0)
return -1;
- dest = ssb;
- sortslice_advance(&dest, nb-1);
- sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
- basea = ssa;
+ dest = pb + nb - 1;
+ memcpy(ms->a, pb, nb * sizeof(PyObject*));
+ basea = pa;
baseb = ms->a;
- ssb.keys = ms->a.keys + nb - 1;
- if (ssb.values != NULL)
- ssb.values = ms->a.values + nb - 1;
- sortslice_advance(&ssa, na - 1);
+ pb = ms->a + nb - 1;
+ pa += na - 1;
- sortslice_copy_decr(&dest, &ssa);
+ *dest-- = *pa--;
--na;
if (na == 0)
goto Succeed;
@@ -1769,6 +1616,7 @@ merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
goto CopyA;
min_gallop = ms->min_gallop;
+ compare = ms->compare;
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 */
@@ -1778,11 +1626,11 @@ merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
*/
for (;;) {
assert(na > 0 && nb > 1);
- k = ISLT(ssb.keys[0], ssa.keys[0]);
+ k = ISLT(*pb, *pa, compare);
if (k) {
if (k < 0)
goto Fail;
- sortslice_copy_decr(&dest, &ssa);
+ *dest-- = *pa--;
++acount;
bcount = 0;
--na;
@@ -1792,7 +1640,7 @@ merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
break;
}
else {
- sortslice_copy_decr(&dest, &ssb);
+ *dest-- = *pb--;
++bcount;
acount = 0;
--nb;
@@ -1813,33 +1661,33 @@ merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
assert(na > 0 && nb > 1);
min_gallop -= min_gallop > 1;
ms->min_gallop = min_gallop;
- k = gallop_right(ms, ssb.keys[0], basea.keys, na, na-1);
+ k = gallop_right(*pb, basea, na, na-1, compare);
if (k < 0)
goto Fail;
k = na - k;
acount = k;
if (k) {
- sortslice_advance(&dest, -k);
- sortslice_advance(&ssa, -k);
- sortslice_memmove(&dest, 1, &ssa, 1, k);
+ dest -= k;
+ pa -= k;
+ memmove(dest+1, pa+1, k * sizeof(PyObject *));
na -= k;
if (na == 0)
goto Succeed;
}
- sortslice_copy_decr(&dest, &ssb);
+ *dest-- = *pb--;
--nb;
if (nb == 1)
goto CopyA;
- k = gallop_left(ms, ssa.keys[0], baseb.keys, nb, nb-1);
+ k = gallop_left(*pa, baseb, nb, nb-1, compare);
if (k < 0)
goto Fail;
k = nb - k;
bcount = k;
if (k) {
- sortslice_advance(&dest, -k);
- sortslice_advance(&ssb, -k);
- sortslice_memcpy(&dest, 1, &ssb, 1, k);
+ dest -= k;
+ pb -= k;
+ memcpy(dest+1, pb+1, k * sizeof(PyObject *));
nb -= k;
if (nb == 1)
goto CopyA;
@@ -1850,7 +1698,7 @@ merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
if (nb == 0)
goto Succeed;
}
- sortslice_copy_decr(&dest, &ssa);
+ *dest-- = *pa--;
--na;
if (na == 0)
goto Succeed;
@@ -1862,15 +1710,15 @@ Succeed:
result = 0;
Fail:
if (nb)
- sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb);
+ memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*));
return result;
CopyA:
assert(nb == 1 && na > 0);
- /* The first element of ssb belongs at the front of the merge. */
- sortslice_memmove(&dest, 1-na, &ssa, 1-na, na);
- sortslice_advance(&dest, -na);
- sortslice_advance(&ssa, -na);
- sortslice_copy(&dest, 0, &ssb, 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;
}
@@ -1880,21 +1728,22 @@ CopyA:
static Py_ssize_t
merge_at(MergeState *ms, Py_ssize_t i)
{
- sortslice ssa, ssb;
+ PyObject **pa, **pb;
Py_ssize_t na, nb;
Py_ssize_t k;
+ PyObject *compare;
assert(ms != NULL);
assert(ms->n >= 2);
assert(i >= 0);
assert(i == ms->n - 2 || i == ms->n - 3);
- ssa = ms->pending[i].base;
+ pa = ms->pending[i].base;
na = ms->pending[i].len;
- ssb = ms->pending[i+1].base;
+ pb = ms->pending[i+1].base;
nb = ms->pending[i+1].len;
assert(na > 0 && nb > 0);
- assert(ssa.keys + na == ssb.keys);
+ 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
@@ -1908,10 +1757,11 @@ merge_at(MergeState *ms, Py_ssize_t i)
/* Where does b start in a? Elements in a before that can be
* ignored (already in place).
*/
- k = gallop_right(ms, *ssb.keys, ssa.keys, na, 0);
+ compare = ms->compare;
+ k = gallop_right(*pb, pa, na, 0, compare);
if (k < 0)
return -1;
- sortslice_advance(&ssa, k);
+ pa += k;
na -= k;
if (na == 0)
return 0;
@@ -1919,7 +1769,7 @@ merge_at(MergeState *ms, Py_ssize_t i)
/* Where does a end in b? Elements in b after that can be
* ignored (already in place).
*/
- nb = gallop_left(ms, ssa.keys[na-1], ssb.keys, nb, nb-1);
+ nb = gallop_left(pa[na-1], pb, nb, nb-1, compare);
if (nb <= 0)
return nb;
@@ -1927,9 +1777,9 @@ merge_at(MergeState *ms, Py_ssize_t i)
* min(na, nb) elements.
*/
if (na <= nb)
- return merge_lo(ms, ssa, na, ssb, nb);
+ return merge_lo(ms, pa, na, pb, nb);
else
- return merge_hi(ms, ssa, na, ssb, nb);
+ return merge_hi(ms, pa, na, pb, nb);
}
/* Examine the stack of runs waiting to be merged, merging adjacent runs
@@ -1958,8 +1808,8 @@ merge_collapse(MergeState *ms)
return -1;
}
else if (p[n].len <= p[n+1].len) {
- if (merge_at(ms, n) < 0)
- return -1;
+ if (merge_at(ms, n) < 0)
+ return -1;
}
else
break;
@@ -2011,177 +1861,178 @@ merge_compute_minrun(Py_ssize_t n)
return n + r;
}
-static void
-reverse_sortslice(sortslice *s, Py_ssize_t n)
-{
- reverse_slice(s->keys, &s->keys[n]);
- if (s->values != NULL)
- reverse_slice(s->values, &s->values[n]);
-}
+/* Special wrapper to support stable sorting using the decorate-sort-undecorate
+ pattern. Holds a key which is used for comparisons and the original record
+ which is returned during the undecorate phase. By exposing only the key
+ during comparisons, the underlying sort stability characteristics are left
+ unchanged. Also, if a custom comparison function is used, it will only see
+ the key instead of a full record. */
-/* Here we define custom comparison functions to optimize for the cases one commonly
- * encounters in practice: homogeneous lists, often of one of the basic types. */
+typedef struct {
+ PyObject_HEAD
+ PyObject *key;
+ PyObject *value;
+} sortwrapperobject;
-/* This struct holds the comparison function and helper functions
- * selected in the pre-sort check. */
+PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key.");
+static PyObject *
+sortwrapper_richcompare(sortwrapperobject *, sortwrapperobject *, int);
+static void
+sortwrapper_dealloc(sortwrapperobject *);
-/* These are the special case compare functions.
- * ms->key_compare will always point to one of these: */
+static PyTypeObject sortwrapper_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_compare */
+ 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_RICHCOMPARE, /* tp_flags */
+ sortwrapper_doc, /* tp_doc */
+ 0, /* tp_traverse */
+ 0, /* tp_clear */
+ (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */
+};
-/* Heterogeneous compare: default, always safe to fall back on. */
-static int
-safe_object_compare(PyObject *v, PyObject *w, MergeState *ms)
-{
- /* No assumptions necessary! */
- return PyObject_RichCompareBool(v, w, Py_LT);
-}
-/* Homogeneous compare: safe for any two compareable objects of the same type.
- * (ms->key_richcompare is set to ob_type->tp_richcompare in the
- * pre-sort check.)
- */
-static int
-unsafe_object_compare(PyObject *v, PyObject *w, MergeState *ms)
+static PyObject *
+sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op)
{
- PyObject *res_obj; int res;
-
- /* No assumptions, because we check first: */
- if (v->ob_type->tp_richcompare != ms->key_richcompare)
- return PyObject_RichCompareBool(v, w, Py_LT);
-
- assert(ms->key_richcompare != NULL);
- res_obj = (*(ms->key_richcompare))(v, w, Py_LT);
-
- if (res_obj == Py_NotImplemented) {
- Py_DECREF(res_obj);
- return PyObject_RichCompareBool(v, w, Py_LT);
- }
- if (res_obj == NULL)
- return -1;
-
- if (PyBool_Check(res_obj)) {
- res = (res_obj == Py_True);
- }
- else {
- res = PyObject_IsTrue(res_obj);
+ if (!PyObject_TypeCheck(b, &sortwrapper_type)) {
+ PyErr_SetString(PyExc_TypeError,
+ "expected a sortwrapperobject");
+ return NULL;
}
- Py_DECREF(res_obj);
-
- /* Note that we can't assert
- * res == PyObject_RichCompareBool(v, w, Py_LT);
- * because of evil compare functions like this:
- * lambda a, b: int(random.random() * 3) - 1)
- * (which is actually in test_sort.py) */
- return res;
+ return PyObject_RichCompare(a->key, b->key, op);
}
-/* Latin string compare: safe for any two latin (one byte per char) strings. */
-static int
-unsafe_latin_compare(PyObject *v, PyObject *w, MergeState *ms)
+static void
+sortwrapper_dealloc(sortwrapperobject *so)
{
- Py_ssize_t len;
- int res;
-
- /* Modified from Objects/unicodeobject.c:unicode_compare, assuming: */
- assert(v->ob_type == w->ob_type);
- assert(v->ob_type == &PyUnicode_Type);
- assert(PyUnicode_KIND(v) == PyUnicode_KIND(w));
- assert(PyUnicode_KIND(v) == PyUnicode_1BYTE_KIND);
+ Py_XDECREF(so->key);
+ Py_XDECREF(so->value);
+ PyObject_Del(so);
+}
- len = Py_MIN(PyUnicode_GET_LENGTH(v), PyUnicode_GET_LENGTH(w));
- res = memcmp(PyUnicode_DATA(v), PyUnicode_DATA(w), len);
+/* Returns a new reference to a sortwrapper.
+ Consumes the references to the two underlying objects. */
- res = (res != 0 ?
- res < 0 :
- PyUnicode_GET_LENGTH(v) < PyUnicode_GET_LENGTH(w));
+static PyObject *
+build_sortwrapper(PyObject *key, PyObject *value)
+{
+ sortwrapperobject *so;
- assert(res == PyObject_RichCompareBool(v, w, Py_LT));;
- return res;
+ so = PyObject_New(sortwrapperobject, &sortwrapper_type);
+ if (so == NULL)
+ return NULL;
+ so->key = key;
+ so->value = value;
+ return (PyObject *)so;
}
-/* Bounded int compare: compare any two longs that fit in a single machine word. */
-static int
-unsafe_long_compare(PyObject *v, PyObject *w, MergeState *ms)
+/* Returns a new reference to the value underlying the wrapper. */
+static PyObject *
+sortwrapper_getvalue(PyObject *so)
{
- PyLongObject *vl, *wl; sdigit v0, w0; int res;
-
- /* Modified from Objects/longobject.c:long_compare, assuming: */
- assert(v->ob_type == w->ob_type);
- assert(v->ob_type == &PyLong_Type);
- assert(Py_ABS(Py_SIZE(v)) <= 1);
- assert(Py_ABS(Py_SIZE(w)) <= 1);
+ PyObject *value;
- vl = (PyLongObject*)v;
- wl = (PyLongObject*)w;
-
- v0 = Py_SIZE(vl) == 0 ? 0 : (sdigit)vl->ob_digit[0];
- w0 = Py_SIZE(wl) == 0 ? 0 : (sdigit)wl->ob_digit[0];
-
- if (Py_SIZE(vl) < 0)
- v0 = -v0;
- if (Py_SIZE(wl) < 0)
- w0 = -w0;
-
- res = v0 < w0;
- assert(res == PyObject_RichCompareBool(v, w, Py_LT));
- return res;
+ if (!PyObject_TypeCheck(so, &sortwrapper_type)) {
+ PyErr_SetString(PyExc_TypeError,
+ "expected a sortwrapperobject");
+ return NULL;
+ }
+ value = ((sortwrapperobject *)so)->value;
+ Py_INCREF(value);
+ return value;
}
-/* Float compare: compare any two floats. */
-static int
-unsafe_float_compare(PyObject *v, PyObject *w, MergeState *ms)
-{
- int res;
+/* Wrapper for user specified cmp functions in combination with a
+ specified key function. Makes sure the cmp function is presented
+ with the actual key instead of the sortwrapper */
- /* Modified from Objects/floatobject.c:float_richcompare, assuming: */
- assert(v->ob_type == w->ob_type);
- assert(v->ob_type == &PyFloat_Type);
+typedef struct {
+ PyObject_HEAD
+ PyObject *func;
+} cmpwrapperobject;
- res = PyFloat_AS_DOUBLE(v) < PyFloat_AS_DOUBLE(w);
- assert(res == PyObject_RichCompareBool(v, w, Py_LT));
- return res;
+static void
+cmpwrapper_dealloc(cmpwrapperobject *co)
+{
+ Py_XDECREF(co->func);
+ PyObject_Del(co);
}
-/* Tuple compare: compare *any* two tuples, using
- * ms->tuple_elem_compare to compare the first elements, which is set
- * using the same pre-sort check as we use for ms->key_compare,
- * but run on the list [x[0] for x in L]. This allows us to optimize compares
- * on two levels (as long as [x[0] for x in L] is type-homogeneous.) The idea is
- * that most tuple compares don't involve x[1:]. */
-static int
-unsafe_tuple_compare(PyObject *v, PyObject *w, MergeState *ms)
+static PyObject *
+cmpwrapper_call(cmpwrapperobject *co, PyObject *args, PyObject *kwds)
{
- PyTupleObject *vt, *wt;
- Py_ssize_t i, vlen, wlen;
- int k;
+ PyObject *x, *y, *xx, *yy;
- /* Modified from Objects/tupleobject.c:tuplerichcompare, assuming: */
- assert(v->ob_type == w->ob_type);
- assert(v->ob_type == &PyTuple_Type);
- assert(Py_SIZE(v) > 0);
- assert(Py_SIZE(w) > 0);
-
- vt = (PyTupleObject *)v;
- wt = (PyTupleObject *)w;
+ if (!PyArg_UnpackTuple(args, "", 2, 2, &x, &y))
+ return NULL;
+ if (!PyObject_TypeCheck(x, &sortwrapper_type) ||
+ !PyObject_TypeCheck(y, &sortwrapper_type)) {
+ PyErr_SetString(PyExc_TypeError,
+ "expected a sortwrapperobject");
+ return NULL;
+ }
+ xx = ((sortwrapperobject *)x)->key;
+ yy = ((sortwrapperobject *)y)->key;
+ return PyObject_CallFunctionObjArgs(co->func, xx, yy, NULL);
+}
- vlen = Py_SIZE(vt);
- wlen = Py_SIZE(wt);
+PyDoc_STRVAR(cmpwrapper_doc, "cmp() wrapper for sort with custom keys.");
- for (i = 0; i < vlen && i < wlen; i++) {
- k = PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i], Py_EQ);
- if (k < 0)
- return -1;
- if (!k)
- break;
- }
+static PyTypeObject cmpwrapper_type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "cmpwrapper", /* tp_name */
+ sizeof(cmpwrapperobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)cmpwrapper_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ (ternaryfunc)cmpwrapper_call, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT, /* tp_flags */
+ cmpwrapper_doc, /* tp_doc */
+};
- if (i >= vlen || i >= wlen)
- return vlen < wlen;
+static PyObject *
+build_cmpwrapper(PyObject *cmpfunc)
+{
+ cmpwrapperobject *co;
- if (i == 0)
- return ms->tuple_elem_compare(vt->ob_item[i], wt->ob_item[i], ms);
- else
- return PyObject_RichCompareBool(vt->ob_item[i], wt->ob_item[i], Py_LT);
+ co = PyObject_New(cmpwrapperobject, &cmpwrapper_type);
+ if (co == NULL)
+ return NULL;
+ Py_INCREF(cmpfunc);
+ co->func = cmpfunc;
+ return (PyObject *)co;
}
/* An adaptive, stable, natural mergesort. See listsort.txt.
@@ -2189,43 +2040,44 @@ unsafe_tuple_compare(PyObject *v, PyObject *w, MergeState *ms)
* list will be some permutation of its input state (nothing is lost or
* duplicated).
*/
-/*[clinic input]
-list.sort
-
- *
- key as keyfunc: object = None
- reverse: bool(accept={int}) = False
-
-Sort the list in ascending order and return None.
-
-The sort is in-place (i.e. the list itself is modified) and stable (i.e. the
-order of two equal elements is maintained).
-
-If a key function is given, apply it once to each list item and sort them,
-ascending or descending, according to their function values.
-
-The reverse flag can be set to sort in descending order.
-[clinic start generated code]*/
-
static PyObject *
-list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
-/*[clinic end generated code: output=57b9f9c5e23fbe42 input=cb56cd179a713060]*/
+listsort(PyListObject *self, PyObject *args, PyObject *kwds)
{
MergeState ms;
+ PyObject **lo, **hi;
Py_ssize_t nremaining;
Py_ssize_t minrun;
- sortslice lo;
Py_ssize_t saved_ob_size, saved_allocated;
PyObject **saved_ob_item;
PyObject **final_ob_item;
+ PyObject *compare = NULL;
PyObject *result = NULL; /* guilty until proved innocent */
+ int reverse = 0;
+ PyObject *keyfunc = NULL;
Py_ssize_t i;
- PyObject **keys;
+ PyObject *key, *value, *kvpair;
+ static char *kwlist[] = {"cmp", "key", "reverse", 0};
assert(self != NULL);
- assert(PyList_Check(self));
+ assert (PyList_Check(self));
+ if (args != NULL) {
+ if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OOi:sort",
+ kwlist, &compare, &keyfunc, &reverse))
+ return NULL;
+ }
+ if (compare == Py_None)
+ compare = NULL;
+ if (compare != NULL &&
+ PyErr_WarnPy3k("the cmp argument is not supported in 3.x", 1) < 0)
+ return NULL;
if (keyfunc == Py_None)
keyfunc = NULL;
+ if (compare != NULL && keyfunc != NULL) {
+ compare = build_cmpwrapper(compare);
+ if (compare == NULL)
+ return NULL;
+ } else
+ Py_XINCREF(compare);
/* The list is temporarily made empty, so that mutations performed
* by comparison functions can't affect the slice of memory we're
@@ -2239,169 +2091,59 @@ list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
self->ob_item = NULL;
self->allocated = -1; /* any operation will reset it to >= 0 */
- if (keyfunc == NULL) {
- keys = NULL;
- lo.keys = saved_ob_item;
- lo.values = NULL;
- }
- else {
- if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
- /* Leverage stack space we allocated but won't otherwise use */
- keys = &ms.temparray[saved_ob_size+1];
- else {
- keys = PyMem_MALLOC(sizeof(PyObject *) * saved_ob_size);
- if (keys == NULL) {
- PyErr_NoMemory();
- goto keyfunc_fail;
- }
- }
-
- for (i = 0; i < saved_ob_size ; i++) {
- keys[i] = _PyObject_CallOneArg(keyfunc, saved_ob_item[i]);
- if (keys[i] == NULL) {
- for (i=i-1 ; i>=0 ; i--)
- Py_DECREF(keys[i]);
- if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
- PyMem_FREE(keys);
- goto keyfunc_fail;
- }
- }
-
- lo.keys = keys;
- lo.values = saved_ob_item;
- }
-
-
- /* The pre-sort check: here's where we decide which compare function to use.
- * How much optimization is safe? We test for homogeneity with respect to
- * several properties that are expensive to check at compare-time, and
- * set ms appropriately. */
- if (saved_ob_size > 1) {
- /* Assume the first element is representative of the whole list. */
- int keys_are_in_tuples = (lo.keys[0]->ob_type == &PyTuple_Type &&
- Py_SIZE(lo.keys[0]) > 0);
-
- PyTypeObject* key_type = (keys_are_in_tuples ?
- PyTuple_GET_ITEM(lo.keys[0], 0)->ob_type :
- lo.keys[0]->ob_type);
-
- int keys_are_all_same_type = 1;
- int strings_are_latin = 1;
- int ints_are_bounded = 1;
-
- /* Prove that assumption by checking every key. */
- for (i=0; i < saved_ob_size; i++) {
-
- if (keys_are_in_tuples &&
- !(lo.keys[i]->ob_type == &PyTuple_Type && Py_SIZE(lo.keys[i]) != 0)) {
- keys_are_in_tuples = 0;
- keys_are_all_same_type = 0;
- break;
- }
-
- /* Note: for lists of tuples, key is the first element of the tuple
- * lo.keys[i], not lo.keys[i] itself! We verify type-homogeneity
- * for lists of tuples in the if-statement directly above. */
- PyObject *key = (keys_are_in_tuples ?
- PyTuple_GET_ITEM(lo.keys[i], 0) :
- lo.keys[i]);
-
- if (key->ob_type != key_type) {
- keys_are_all_same_type = 0;
- /* If keys are in tuple we must loop over the whole list to make
- sure all items are tuples */
- if (!keys_are_in_tuples) {
- break;
- }
- }
-
- if (keys_are_all_same_type) {
- if (key_type == &PyLong_Type &&
- ints_are_bounded &&
- Py_ABS(Py_SIZE(key)) > 1) {
-
- ints_are_bounded = 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);
}
- else if (key_type == &PyUnicode_Type &&
- strings_are_latin &&
- PyUnicode_KIND(key) != PyUnicode_1BYTE_KIND) {
-
- strings_are_latin = 0;
- }
- }
- }
-
- /* Choose the best compare, given what we now know about the keys. */
- if (keys_are_all_same_type) {
-
- if (key_type == &PyUnicode_Type && strings_are_latin) {
- ms.key_compare = unsafe_latin_compare;
- }
- else if (key_type == &PyLong_Type && ints_are_bounded) {
- ms.key_compare = unsafe_long_compare;
- }
- else if (key_type == &PyFloat_Type) {
- ms.key_compare = unsafe_float_compare;
+ goto dsu_fail;
}
- else if ((ms.key_richcompare = key_type->tp_richcompare) != NULL) {
- ms.key_compare = unsafe_object_compare;
- }
- else {
- ms.key_compare = safe_object_compare;
- }
- }
- else {
- ms.key_compare = safe_object_compare;
- }
-
- if (keys_are_in_tuples) {
- /* Make sure we're not dealing with tuples of tuples
- * (remember: here, key_type refers list [key[0] for key in keys]) */
- if (key_type == &PyTuple_Type) {
- ms.tuple_elem_compare = safe_object_compare;
- }
- else {
- ms.tuple_elem_compare = ms.key_compare;
- }
-
- ms.key_compare = unsafe_tuple_compare;
+ kvpair = build_sortwrapper(key, value);
+ if (kvpair == NULL)
+ goto dsu_fail;
+ saved_ob_item[i] = kvpair;
}
}
- /* End of pre-sort check: ms is now set properly! */
- merge_init(&ms, saved_ob_size, keys != NULL);
+ /* 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, compare);
nremaining = saved_ob_size;
if (nremaining < 2)
goto succeed;
- /* Reverse sort stability achieved by initially reversing the list,
- applying a stable forward sort, then reversing the final result. */
- if (reverse) {
- if (keys != NULL)
- reverse_slice(&keys[0], &keys[saved_ob_size]);
- reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
- }
-
/* 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(&ms, lo.keys, lo.keys + nremaining, &descending);
+ n = count_run(lo, hi, compare, &descending);
if (n < 0)
goto fail;
if (descending)
- reverse_sortslice(&lo, n);
+ 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(&ms, lo, lo.keys + force, lo.keys + n) < 0)
+ if (binarysort(lo, lo + force, lo + n, compare) < 0)
goto fail;
n = force;
}
@@ -2413,27 +2155,27 @@ list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
if (merge_collapse(&ms) < 0)
goto fail;
/* Advance to find next run. */
- sortslice_advance(&lo, n);
+ lo += n;
nremaining -= n;
} while (nremaining);
+ assert(lo == hi);
if (merge_force_collapse(&ms) < 0)
goto fail;
assert(ms.n == 1);
- assert(keys == NULL
- ? ms.pending[0].base.keys == saved_ob_item
- : ms.pending[0].base.keys == &keys[0]);
+ assert(ms.pending[0].base == saved_ob_item);
assert(ms.pending[0].len == saved_ob_size);
- lo = ms.pending[0].base;
succeed:
result = Py_None;
fail:
- if (keys != NULL) {
- for (i = 0; i < saved_ob_size; i++)
- Py_DECREF(keys[i]);
- if (saved_ob_size >= MERGESTATE_TEMP_SIZE/2)
- PyMem_FREE(keys);
+ 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) {
@@ -2449,20 +2191,21 @@ fail:
merge_freemem(&ms);
-keyfunc_fail:
+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
+ /* 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_XDECREF(compare);
Py_XINCREF(result);
return result;
}
@@ -2476,22 +2219,15 @@ PyList_Sort(PyObject *v)
PyErr_BadInternalCall();
return -1;
}
- v = list_sort_impl((PyListObject *)v, NULL, 0);
+ v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL);
if (v == NULL)
return -1;
Py_DECREF(v);
return 0;
}
-/*[clinic input]
-list.reverse
-
-Reverse *IN PLACE*.
-[clinic start generated code]*/
-
static PyObject *
-list_reverse_impl(PyListObject *self)
-/*[clinic end generated code: output=482544fc451abea9 input=eefd4c3ae1bc9887]*/
+listreverse(PyListObject *self)
{
if (Py_SIZE(self) > 1)
reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
@@ -2515,33 +2251,39 @@ PyList_Reverse(PyObject *v)
PyObject *
PyList_AsTuple(PyObject *v)
{
+ PyObject *w;
+ PyObject **p, **q;
+ Py_ssize_t n;
if (v == NULL || !PyList_Check(v)) {
PyErr_BadInternalCall();
return NULL;
}
- return _PyTuple_FromArray(((PyListObject *)v)->ob_item, Py_SIZE(v));
+ 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;
}
-/*[clinic input]
-list.index
-
- value: object
- start: slice_index(accept={int}) = 0
- stop: slice_index(accept={int}, c_default="PY_SSIZE_T_MAX") = sys.maxsize
- /
-
-Return first index of value.
-
-Raises ValueError if the value is not present.
-[clinic start generated code]*/
-
static PyObject *
-list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
- Py_ssize_t stop)
-/*[clinic end generated code: output=ec51b88787e4e481 input=40ec5826303a0eb1]*/
+listindex(PyListObject *self, PyObject *args)
{
- Py_ssize_t i;
+ Py_ssize_t i, start=0, stop=Py_SIZE(self);
+ PyObject *v, *format_tuple, *err_string;
+ static PyObject *err_format = NULL;
+ if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
+ _PyEval_SliceIndexNotNone, &start,
+ _PyEval_SliceIndexNotNone, &stop))
+ return NULL;
if (start < 0) {
start += Py_SIZE(self);
if (start < 0)
@@ -2553,61 +2295,52 @@ list_index_impl(PyListObject *self, PyObject *value, Py_ssize_t start,
stop = 0;
}
for (i = start; i < stop && i < Py_SIZE(self); i++) {
- int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
+ int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
if (cmp > 0)
- return PyLong_FromSsize_t(i);
+ return PyInt_FromSsize_t(i);
else if (cmp < 0)
return NULL;
}
- PyErr_Format(PyExc_ValueError, "%R is not in list", value);
+ if (err_format == NULL) {
+ err_format = PyString_FromString("%r is not in list");
+ if (err_format == NULL)
+ return NULL;
+ }
+ format_tuple = PyTuple_Pack(1, v);
+ if (format_tuple == NULL)
+ return NULL;
+ err_string = PyString_Format(err_format, format_tuple);
+ Py_DECREF(format_tuple);
+ if (err_string == NULL)
+ return NULL;
+ PyErr_SetObject(PyExc_ValueError, err_string);
+ Py_DECREF(err_string);
return NULL;
}
-/*[clinic input]
-list.count
-
- value: object
- /
-
-Return number of occurrences of value.
-[clinic start generated code]*/
-
static PyObject *
-list_count(PyListObject *self, PyObject *value)
-/*[clinic end generated code: output=b1f5d284205ae714 input=3bdc3a5e6f749565]*/
+listcount(PyListObject *self, PyObject *v)
{
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], value, Py_EQ);
+ 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);
+ return PyInt_FromSsize_t(count);
}
-/*[clinic input]
-list.remove
-
- value: object
- /
-
-Remove first occurrence of value.
-
-Raises ValueError if the value is not present.
-[clinic start generated code]*/
-
static PyObject *
-list_remove(PyListObject *self, PyObject *value)
-/*[clinic end generated code: output=f087e1951a5e30d1 input=2dc2ba5bb2fb1f82]*/
+listremove(PyListObject *self, PyObject *v)
{
Py_ssize_t i;
for (i = 0; i < Py_SIZE(self); i++) {
- int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
+ 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)
@@ -2637,18 +2370,23 @@ list_richcompare(PyObject *v, PyObject *w, int op)
PyListObject *vl, *wl;
Py_ssize_t i;
- if (!PyList_Check(v) || !PyList_Check(w))
- Py_RETURN_NOTIMPLEMENTED;
+ 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)
- Py_RETURN_FALSE;
+ res = Py_False;
else
- Py_RETURN_TRUE;
+ res = Py_True;
+ Py_INCREF(res);
+ return res;
}
/* Search for the first index where items are different */
@@ -2663,37 +2401,50 @@ list_richcompare(PyObject *v, PyObject *w, int op)
if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
/* No more items to compare -- compare sizes */
- Py_RETURN_RICHCOMPARE(Py_SIZE(vl), Py_SIZE(wl), op);
+ 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_RETURN_FALSE;
+ Py_INCREF(Py_False);
+ return Py_False;
}
if (op == Py_NE) {
- Py_RETURN_TRUE;
+ 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);
}
-/*[clinic input]
-list.__init__
-
- iterable: object(c_default="NULL") = ()
- /
-
-Built-in mutable sequence.
-
-If no argument is given, the constructor creates a new empty list.
-The argument must be an iterable if specified.
-[clinic start generated code]*/
-
static int
-list___init___impl(PyListObject *self, PyObject *iterable)
-/*[clinic end generated code: output=0f3c21379d01de48 input=b3f3fe7206af8f6b]*/
+list_init(PyListObject *self, PyObject *args, PyObject *kw)
{
+ PyObject *arg = NULL;
+ static char *kwlist[] = {"sequence", 0};
+
+ 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);
@@ -2702,23 +2453,10 @@ list___init___impl(PyListObject *self, PyObject *iterable)
/* Empty previous contents */
if (self->ob_item != NULL) {
- (void)_list_clear(self);
- }
- if (iterable != NULL) {
- if (_PyObject_HasLen(iterable)) {
- Py_ssize_t iter_len = PyObject_Size(iterable);
- if (iter_len == -1) {
- if (!PyErr_ExceptionMatches(PyExc_TypeError)) {
- return -1;
- }
- PyErr_Clear();
- }
- if (iter_len > 0 && self->ob_item == NULL
- && list_preallocate_exact(self, iter_len)) {
- return -1;
- }
- }
- PyObject *rv = list_extend(self, iterable);
+ (void)list_clear(self);
+ }
+ if (arg != NULL) {
+ PyObject *rv = listextend(self, arg);
if (rv == NULL)
return -1;
Py_DECREF(rv);
@@ -2726,40 +2464,62 @@ list___init___impl(PyListObject *self, PyObject *iterable)
return 0;
}
-/*[clinic input]
-list.__sizeof__
-
-Return the size of the list in memory, in bytes.
-[clinic start generated code]*/
-
static PyObject *
-list___sizeof___impl(PyListObject *self)
-/*[clinic end generated code: output=3417541f95f9a53e input=b8030a5d5ce8a187]*/
+list_sizeof(PyListObject *self)
{
Py_ssize_t res;
res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*);
- return PyLong_FromSsize_t(res);
+ return PyInt_FromSsize_t(res);
}
static PyObject *list_iter(PyObject *seq);
+static PyObject *list_reversed(PyListObject* seq, PyObject* unused);
+
+PyDoc_STRVAR(getitem_doc,
+"x.__getitem__(y) <==> x[y]");
+PyDoc_STRVAR(reversed_doc,
+"L.__reversed__() -- return a reverse iterator over the list");
+PyDoc_STRVAR(sizeof_doc,
+"L.__sizeof__() -- size of L in memory, in bytes");
+PyDoc_STRVAR(append_doc,
+"L.append(object) -- append object to end");
+PyDoc_STRVAR(extend_doc,
+"L.extend(iterable) -- extend list by appending elements from the iterable");
+PyDoc_STRVAR(insert_doc,
+"L.insert(index, object) -- insert object before index");
+PyDoc_STRVAR(pop_doc,
+"L.pop([index]) -> item -- remove and return item at index (default last).\n"
+"Raises IndexError if list is empty or index is out of range.");
+PyDoc_STRVAR(remove_doc,
+"L.remove(value) -- remove first occurrence of value.\n"
+"Raises ValueError if the value is not present.");
+PyDoc_STRVAR(index_doc,
+"L.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
+"Raises ValueError if the value is not present.");
+PyDoc_STRVAR(count_doc,
+"L.count(value) -> integer -- return number of occurrences of value");
+PyDoc_STRVAR(reverse_doc,
+"L.reverse() -- reverse *IN PLACE*");
+PyDoc_STRVAR(sort_doc,
+"L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
+cmp(x, y) -> -1, 0, 1");
+
static PyObject *list_subscript(PyListObject*, PyObject*);
static PyMethodDef list_methods[] = {
- {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, "x.__getitem__(y) <==> x[y]"},
- LIST___REVERSED___METHODDEF
- LIST___SIZEOF___METHODDEF
- LIST_CLEAR_METHODDEF
- LIST_COPY_METHODDEF
- LIST_APPEND_METHODDEF
- LIST_INSERT_METHODDEF
- LIST_EXTEND_METHODDEF
- LIST_POP_METHODDEF
- LIST_REMOVE_METHODDEF
- LIST_INDEX_METHODDEF
- LIST_COUNT_METHODDEF
- LIST_REVERSE_METHODDEF
- LIST_SORT_METHODDEF
+ {"__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 */
};
@@ -2768,14 +2528,19 @@ static PySequenceMethods list_as_sequence = {
(binaryfunc)list_concat, /* sq_concat */
(ssizeargfunc)list_repeat, /* sq_repeat */
(ssizeargfunc)list_item, /* sq_item */
- 0, /* sq_slice */
+ (ssizessizeargfunc)list_slice, /* sq_slice */
(ssizeobjargproc)list_ass_item, /* sq_ass_item */
- 0, /* sq_ass_slice */
+ (ssizessizeobjargproc)list_ass_slice, /* 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,
+"list() -> new empty list\n"
+"list(iterable) -> new list initialized from iterable's items");
+
+
static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{
@@ -2789,16 +2554,15 @@ list_subscript(PyListObject* self, PyObject* item)
return list_item(self, i);
}
else if (PySlice_Check(item)) {
- Py_ssize_t start, stop, step, slicelength, i;
- size_t cur;
+ Py_ssize_t start, stop, step, slicelength, cur, i;
PyObject* result;
PyObject* it;
PyObject **src, **dest;
- if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
+ if (_PySlice_Unpack(item, &start, &stop, &step) < 0) {
return NULL;
}
- slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
+ slicelength = _PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
step);
if (slicelength <= 0) {
@@ -2808,24 +2572,24 @@ list_subscript(PyListObject* self, PyObject* item)
return list_slice(self, start, stop);
}
else {
- result = list_new_prealloc(slicelength);
+ 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 += (size_t)step, i++) {
+ cur += step, i++) {
it = src[cur];
Py_INCREF(it);
dest[i] = it;
}
- Py_SIZE(result) = slicelength;
+
return result;
}
}
else {
PyErr_Format(PyExc_TypeError,
- "list indices must be integers or slices, not %.200s",
+ "list indices must be integers, not %.200s",
item->ob_type->tp_name);
return NULL;
}
@@ -2845,10 +2609,10 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
else if (PySlice_Check(item)) {
Py_ssize_t start, stop, step, slicelength;
- if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
+ if (_PySlice_Unpack(item, &start, &stop, &step) < 0) {
return -1;
}
- slicelength = PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
+ slicelength = _PySlice_AdjustIndices(Py_SIZE(self), &start, &stop,
step);
if (step == 1)
@@ -2865,7 +2629,6 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
PyObject **garbage;
size_t cur;
Py_ssize_t i;
- int res;
if (slicelength <= 0)
return 0;
@@ -2876,6 +2639,9 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
step = -step;
}
+ assert((size_t)slicelength <=
+ PY_SIZE_MAX / sizeof(PyObject*));
+
garbage = (PyObject**)
PyMem_MALLOC(slicelength*sizeof(PyObject*));
if (!garbage) {
@@ -2904,7 +2670,7 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
self->ob_item + cur + 1,
lim * sizeof(PyObject *));
}
- cur = start + (size_t)slicelength * step;
+ cur = start + slicelength*step;
if (cur < (size_t)Py_SIZE(self)) {
memmove(self->ob_item + cur - slicelength,
self->ob_item + cur,
@@ -2913,21 +2679,20 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
}
Py_SIZE(self) -= slicelength;
- res = list_resize(self, Py_SIZE(self));
+ list_resize(self, Py_SIZE(self));
for (i = 0; i < slicelength; i++) {
Py_DECREF(garbage[i]);
}
PyMem_FREE(garbage);
- return res;
+ return 0;
}
else {
/* assign slice */
PyObject *ins, *seq;
PyObject **garbage, **seqitems, **selfitems;
- Py_ssize_t i;
- size_t cur;
+ Py_ssize_t cur, i;
/* protect against a[::-1] = a */
if (self == (PyListObject*)value) {
@@ -2969,7 +2734,7 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
selfitems = self->ob_item;
seqitems = PySequence_Fast_ITEMS(seq);
for (cur = start, i = 0; i < slicelength;
- cur += (size_t)step, i++) {
+ cur += step, i++) {
garbage[i] = selfitems[cur];
ins = seqitems[i];
Py_INCREF(ins);
@@ -2988,7 +2753,7 @@ list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
}
else {
PyErr_Format(PyExc_TypeError,
- "list indices must be integers or slices, not %.200s",
+ "list indices must be integers, not %.200s",
item->ob_type->tp_name);
return -1;
}
@@ -3006,25 +2771,25 @@ PyTypeObject PyList_Type = {
sizeof(PyListObject),
0,
(destructor)list_dealloc, /* tp_dealloc */
- 0, /* tp_vectorcall_offset */
+ (printfunc)list_print, /* tp_print */
0, /* tp_getattr */
0, /* tp_setattr */
- 0, /* tp_as_async */
+ 0, /* tp_compare */
(reprfunc)list_repr, /* tp_repr */
0, /* tp_as_number */
&list_as_sequence, /* tp_as_sequence */
&list_as_mapping, /* tp_as_mapping */
- PyObject_HashNotImplemented, /* tp_hash */
+ (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___init____doc__, /* tp_doc */
+ Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */
+ list_doc, /* tp_doc */
(traverseproc)list_traverse, /* tp_traverse */
- (inquiry)_list_clear, /* tp_clear */
+ (inquiry)list_clear, /* tp_clear */
list_richcompare, /* tp_richcompare */
0, /* tp_weaklistoffset */
list_iter, /* tp_iter */
@@ -3037,50 +2802,45 @@ PyTypeObject PyList_Type = {
0, /* tp_descr_get */
0, /* tp_descr_set */
0, /* tp_dictoffset */
- (initproc)list___init__, /* tp_init */
+ (initproc)list_init, /* tp_init */
PyType_GenericAlloc, /* tp_alloc */
PyType_GenericNew, /* tp_new */
PyObject_GC_Del, /* tp_free */
};
+
/*********************** List Iterator **************************/
typedef struct {
PyObject_HEAD
- Py_ssize_t it_index;
+ long it_index;
PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
} listiterobject;
+static PyObject *list_iter(PyObject *);
static void listiter_dealloc(listiterobject *);
static int listiter_traverse(listiterobject *, visitproc, void *);
static PyObject *listiter_next(listiterobject *);
-static PyObject *listiter_len(listiterobject *, PyObject *);
-static PyObject *listiter_reduce_general(void *_it, int forward);
-static PyObject *listiter_reduce(listiterobject *, PyObject *);
-static PyObject *listiter_setstate(listiterobject *, PyObject *state);
+static PyObject *listiter_len(listiterobject *);
PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
-PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
-PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
static PyMethodDef listiter_methods[] = {
{"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
- {"__reduce__", (PyCFunction)listiter_reduce, METH_NOARGS, reduce_doc},
- {"__setstate__", (PyCFunction)listiter_setstate, METH_O, setstate_doc},
{NULL, NULL} /* sentinel */
};
PyTypeObject PyListIter_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
- "list_iterator", /* tp_name */
+ "listiterator", /* tp_name */
sizeof(listiterobject), /* tp_basicsize */
0, /* tp_itemsize */
/* methods */
(destructor)listiter_dealloc, /* tp_dealloc */
- 0, /* tp_vectorcall_offset */
+ 0, /* tp_print */
0, /* tp_getattr */
0, /* tp_setattr */
- 0, /* tp_as_async */
+ 0, /* tp_compare */
0, /* tp_repr */
0, /* tp_as_number */
0, /* tp_as_sequence */
@@ -3163,39 +2923,16 @@ listiter_next(listiterobject *it)
}
static PyObject *
-listiter_len(listiterobject *it, PyObject *Py_UNUSED(ignored))
+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);
-}
-
-static PyObject *
-listiter_reduce(listiterobject *it, PyObject *Py_UNUSED(ignored))
-{
- return listiter_reduce_general(it, 1);
-}
-
-static PyObject *
-listiter_setstate(listiterobject *it, PyObject *state)
-{
- Py_ssize_t index = PyLong_AsSsize_t(state);
- if (index == -1 && PyErr_Occurred())
- return NULL;
- if (it->it_seq != NULL) {
- if (index < 0)
- index = 0;
- else if (index > PyList_GET_SIZE(it->it_seq))
- index = PyList_GET_SIZE(it->it_seq); /* iterator exhausted */
- it->it_index = index;
+ return PyInt_FromSsize_t(len);
}
- Py_RETURN_NONE;
+ return PyInt_FromLong(0);
}
-
/*********************** List Reverse Iterator **************************/
typedef struct {
@@ -3204,31 +2941,28 @@ typedef struct {
PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
} listreviterobject;
+static PyObject *list_reversed(PyListObject *, PyObject *);
static void listreviter_dealloc(listreviterobject *);
static int listreviter_traverse(listreviterobject *, visitproc, void *);
static PyObject *listreviter_next(listreviterobject *);
-static PyObject *listreviter_len(listreviterobject *, PyObject *);
-static PyObject *listreviter_reduce(listreviterobject *, PyObject *);
-static PyObject *listreviter_setstate(listreviterobject *, PyObject *);
+static PyObject *listreviter_len(listreviterobject *);
static PyMethodDef listreviter_methods[] = {
{"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
- {"__reduce__", (PyCFunction)listreviter_reduce, METH_NOARGS, reduce_doc},
- {"__setstate__", (PyCFunction)listreviter_setstate, METH_O, setstate_doc},
{NULL, NULL} /* sentinel */
};
PyTypeObject PyListRevIter_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
- "list_reverseiterator", /* tp_name */
+ "listreverseiterator", /* tp_name */
sizeof(listreviterobject), /* tp_basicsize */
0, /* tp_itemsize */
/* methods */
(destructor)listreviter_dealloc, /* tp_dealloc */
- 0, /* tp_vectorcall_offset */
+ 0, /* tp_print */
0, /* tp_getattr */
0, /* tp_setattr */
- 0, /* tp_as_async */
+ 0, /* tp_compare */
0, /* tp_repr */
0, /* tp_as_number */
0, /* tp_as_sequence */
@@ -3251,25 +2985,18 @@ PyTypeObject PyListRevIter_Type = {
0,
};
-/*[clinic input]
-list.__reversed__
-
-Return a reverse iterator over the list.
-[clinic start generated code]*/
-
static PyObject *
-list___reversed___impl(PyListObject *self)
-/*[clinic end generated code: output=b166f073208c888c input=eadb6e17f8a6a280]*/
+list_reversed(PyListObject *seq, PyObject *unused)
{
listreviterobject *it;
it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
if (it == NULL)
return NULL;
- assert(PyList_Check(self));
- it->it_index = PyList_GET_SIZE(self) - 1;
- Py_INCREF(self);
- it->it_seq = self;
+ 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;
}
@@ -3317,60 +3044,10 @@ listreviter_next(listreviterobject *it)
}
static PyObject *
-listreviter_len(listreviterobject *it, PyObject *Py_UNUSED(ignored))
+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);
}
-
-static PyObject *
-listreviter_reduce(listreviterobject *it, PyObject *Py_UNUSED(ignored))
-{
- return listiter_reduce_general(it, 0);
-}
-
-static PyObject *
-listreviter_setstate(listreviterobject *it, PyObject *state)
-{
- Py_ssize_t index = PyLong_AsSsize_t(state);
- if (index == -1 && PyErr_Occurred())
- return NULL;
- if (it->it_seq != NULL) {
- if (index < -1)
- index = -1;
- else if (index > PyList_GET_SIZE(it->it_seq) - 1)
- index = PyList_GET_SIZE(it->it_seq) - 1;
- it->it_index = index;
- }
- Py_RETURN_NONE;
-}
-
-/* common pickling support */
-
-static PyObject *
-listiter_reduce_general(void *_it, int forward)
-{
- _Py_IDENTIFIER(iter);
- _Py_IDENTIFIER(reversed);
- PyObject *list;
-
- /* the objects are not the same, index is of different types! */
- if (forward) {
- listiterobject *it = (listiterobject *)_it;
- if (it->it_seq)
- return Py_BuildValue("N(O)n", _PyEval_GetBuiltinId(&PyId_iter),
- it->it_seq, it->it_index);
- } else {
- listreviterobject *it = (listreviterobject *)_it;
- if (it->it_seq)
- return Py_BuildValue("N(O)n", _PyEval_GetBuiltinId(&PyId_reversed),
- it->it_seq, it->it_index);
- }
- /* empty iterator, create an empty list */
- list = PyList_New(0);
- if (list == NULL)
- return NULL;
- return Py_BuildValue("N(N)", _PyEval_GetBuiltinId(&PyId_iter), list);
-}