/* List object implementation */

#include "Python.h"

#include "accu.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

* responsibility 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);

Py_SIZE(self) = newsize;

return 0;

}

/* This over-allocates proportional to the list size, making room

* for additional growth. The over-allocation is mild, but is

* enough to give linear-time amortized behavior over a long

* sequence of appends() in the presence of a poorly-performing

* system realloc().

* The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

*/

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */

if (new_allocated > PY_SIZE_MAX - newsize) {

PyErr_NoMemory();

return -1;

} else {

new_allocated += newsize;

}

if (newsize == 0)

new_allocated = 0;

items = self->ob_item;

if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))

PyMem_RESIZE(items, PyObject *, new_allocated);

else

items = NULL;

if (items == NULL) {

PyErr_NoMemory();

return -1;

}

self->ob_item = items;

Py_SIZE(self) = newsize;

self->allocated = new_allocated;

return 0;

}

/* Debug statistic to compare allocations with reuse through the free list */

#undef SHOW_ALLOC_COUNT

#ifdef SHOW_ALLOC_COUNT

static size_t count_alloc = 0;

static size_t count_reuse = 0;

static void

show_alloc(void)

{

fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n",

count_alloc);

fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T

"d\n", count_reuse);

fprintf(stderr, "%.2f%% reuse rate\n\n",

(100.0*count_reuse/(count_alloc+count_reuse)));

}

#endif

/* Empty list reuse scheme to save calls to malloc and free */

#ifndef PyList_MAXFREELIST

#define PyList_MAXFREELIST 80

#endif

static PyListObject *free_list[PyList_MAXFREELIST];

static int numfree = 0;

int

PyList_ClearFreeList(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) {

Py_AtExit(show_alloc);

initialized = 1;

}

#endif

if (size < 0) {

PyErr_BadInternalCall();

return NULL;

}

/* Check for overflow without an actual overflow,

* which can cause compiler to optimise out */

if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))

return PyErr_NoMemory();

nbytes = size * sizeof(PyObject *);

if (numfree) {

numfree--;

op = free_list[numfree];

_Py_NewReference((PyObject *)op);

#ifdef SHOW_ALLOC_COUNT

count_reuse++;

#endif

} else {

op = PyObject_GC_New(PyListObject, &PyList_Type);

if (op == NULL)

return NULL;

#ifdef SHOW_ALLOC_COUNT

count_alloc++;

#endif

}

if (size <= 0)

op->ob_item = NULL;

else {

op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);

if (op->ob_item == NULL) {

Py_DECREF(op);

return PyErr_NoMemory();

}

memset(op->ob_item, 0, nbytes);

}

Py_SIZE(op) = size;

op->allocated = size;

_PyObject_GC_TRACK(op);

return (PyObject *) op;

}

Py_ssize_t

PyList_Size(PyObject *op)

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return -1;

}

else

return Py_SIZE(op);

}

static PyObject *indexerr = NULL;

PyObject *

PyList_GetItem(PyObject *op, Py_ssize_t i)

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return NULL;

}

if (i < 0 || i >= Py_SIZE(op)) {

if (indexerr == NULL) {

indexerr = PyUnicode_FromString(

"list index out of range");

if (indexerr == NULL)

return NULL;

}

PyErr_SetObject(PyExc_IndexError, indexerr);

return NULL;

}

return ((PyListObject *)op) -> ob_item[i];

}

int

PyList_SetItem(PyObject *op, Py_ssize_t i,

PyObject *newitem)

{

PyObject *olditem;

PyObject **p;

if (!PyList_Check(op)) {

Py_XDECREF(newitem);

PyErr_BadInternalCall();

return -1;

}

if (i < 0 || i >= Py_SIZE(op)) {

Py_XDECREF(newitem);

PyErr_SetString(PyExc_IndexError,

"list assignment index out of range");

return -1;

}

p = ((PyListObject *)op) -> ob_item + i;

olditem = *p;

*p = newitem;

Py_XDECREF(olditem);

return 0;

}

static int

ins1(PyListObject *self, Py_ssize_t where, PyObject *v)

{

Py_ssize_t i, n = Py_SIZE(self);

PyObject **items;

if (v == NULL) {

PyErr_BadInternalCall();

return -1;

}

if (n == PY_SSIZE_T_MAX) {

PyErr_SetString(PyExc_OverflowError,

"cannot add more objects to list");

return -1;

}

if (list_resize(self, n+1) == -1)

return -1;

if (where < 0) {

where += n;

if (where < 0)

where = 0;

}

if (where > n)

where = n;

items = self->ob_item;

for (i = n; --i >= where; )

items[i+1] = items[i];

Py_INCREF(v);

items[where] = v;

return 0;

}

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 = Py_SIZE(op);

while (--i >= 0) {

Py_XDECREF(op->ob_item[i]);

}

PyMem_FREE(op->ob_item);

}

if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))

free_list[numfree++] = op;

else

Py_TYPE(op)->tp_free((PyObject *)op);

Py_TRASHCAN_SAFE_END(op)

}

static PyObject *

list_repr(PyListObject *v)

{

Py_ssize_t i;

PyObject *s;

_PyUnicodeWriter writer;

if (Py_SIZE(v) == 0) {

return PyUnicode_FromString("[]");

}

i = Py_ReprEnter((PyObject*)v);

if (i != 0) {

return i > 0 ? PyUnicode_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 (_PyUnicodeWriter_WriteChar(&writer, '[') < 0)

goto error;

/* 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;

}

if (Py_EnterRecursiveCall(" while getting the repr of a list"))

goto error;

s = PyObject_Repr(v->ob_item[i]);

Py_LeaveRecursiveCall();

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);

Py_ReprLeave((PyObject *)v);

return NULL;

}

static Py_ssize_t

list_length(PyListObject *a)

{

return Py_SIZE(a);

}

static int

list_contains(PyListObject *a, PyObject *el)

{

Py_ssize_t i;

int cmp;

for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)

cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),

Py_EQ);

return cmp;

}

static PyObject *

list_item(PyListObject *a, Py_ssize_t i)

{

if (i < 0 || i >= Py_SIZE(a)) {

if (indexerr == NULL) {

indexerr = PyUnicode_FromString(

"list index out of range");

if (indexerr == NULL)

return NULL;

}

PyErr_SetObject(PyExc_IndexError, indexerr);

return NULL;

}

Py_INCREF(a->ob_item[i]);

return a->ob_item[i];

}

static PyObject *

list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)

{

PyListObject *np;

PyObject **src, **dest;

Py_ssize_t i, len;

if (ilow < 0)

ilow = 0;

else if (ilow > Py_SIZE(a))

ilow = Py_SIZE(a);

if (ihigh < ilow)

ihigh = ilow;

else if (ihigh > Py_SIZE(a))

ihigh = Py_SIZE(a);

len = ihigh - ilow;

np = (PyListObject *) PyList_New(len);

if (np == NULL)

return NULL;

src = a->ob_item + ilow;

dest = np->ob_item;

for (i = 0; i < len; i++) {

PyObject *v = src[i];

Py_INCREF(v);

dest[i] = v;

}

return (PyObject *)np;

}

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 = Py_SIZE(a) + Py_SIZE(b);

if (size < 0)

return PyErr_NoMemory();

np = (PyListObject *) PyList_New(size);

if (np == NULL) {

return NULL;

}

src = a->ob_item;

dest = np->ob_item;

for (i = 0; i < Py_SIZE(a); i++) {

PyObject *v = src[i];

Py_INCREF(v);

dest[i] = v;

}

src = b->ob_item;

dest = np->ob_item + Py_SIZE(a);

for (i = 0; i < Py_SIZE(b); i++) {

PyObject *v = src[i];

Py_INCREF(v);

dest[i] = v;

}

return (PyObject *)np;

#undef b

}

static PyObject *

list_repeat(PyListObject *a, Py_ssize_t n)

{

Py_ssize_t i, j;

Py_ssize_t size;

PyListObject *np;

PyObject **p, **items;

PyObject *elem;

if (n < 0)

n = 0;

if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)

return PyErr_NoMemory();

size = Py_SIZE(a) * n;

if (size == 0)

return PyList_New(0);

np = (PyListObject *) PyList_New(size);

if (np == NULL)

return NULL;

items = np->ob_item;

if (Py_SIZE(a) == 1) {

elem = a->ob_item[0];

for (i = 0; i < n; i++) {

items[i] = elem;

Py_INCREF(elem);

}

return (PyObject *) np;

}

p = np->ob_item;

items = a->ob_item;

for (i = 0; i < n; i++) {

for (j = 0; j < Py_SIZE(a); j++) {

*p = items[j];

Py_INCREF(*p);

p++;

}

}

return (PyObject *) np;

}

static int

list_clear(PyListObject *a)

{

Py_ssize_t i;

PyObject **item = a->ob_item;

if (item != NULL) {

/* Because XDECREF can recursively invoke operations on

this list, we make it empty first. */

i = Py_SIZE(a);

Py_SIZE(a) = 0;

a->ob_item = NULL;

a->allocated = 0;

while (--i >= 0) {

Py_XDECREF(item[i]);

}

PyMem_FREE(item);

}

/* Never fails; the return value can be ignored.

Note that there is no guarantee that the list is actually empty

at this point, because XDECREF may have populated it again! */

return 0;

}

/* a[ilow:ihigh] = v if v != NULL.

* del a[ilow:ihigh] if v == NULL.

*

* Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's

* guaranteed the call cannot fail.

*/

static int

list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)

{

/* Because [X]DECREF can recursively invoke list operations on

this list, we must postpone all [X]DECREF activity until

after the list is back in its canonical shape. Therefore

we must allocate an additional array, 'recycle', into which

we temporarily copy the items that are deleted from the

list. :-( */

PyObject *recycle_on_stack[8];

PyObject **recycle = recycle_on_stack; /* will allocate more if needed */

PyObject **item;

PyObject **vitem = NULL;

PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */

Py_ssize_t n; /* # of elements in replacement list */

Py_ssize_t norig; /* # of elements in list getting replaced */

Py_ssize_t d; /* Change in size */

Py_ssize_t k;

size_t s;

int result = -1; /* guilty until proved innocent */

#define b ((PyListObject *)v)

if (v == NULL)

n = 0;

else {

if (a == b) {

/* Special case "a[i:j] = a" -- copy b first */

v = list_slice(b, 0, Py_SIZE(b));

if (v == NULL)

return result;

result = list_ass_slice(a, ilow, ihigh, v);

Py_DECREF(v);

return result;

}

v_as_SF = PySequence_Fast(v, "can only assign an iterable");

if(v_as_SF == NULL)

goto Error;

n = PySequence_Fast_GET_SIZE(v_as_SF);

vitem = PySequence_Fast_ITEMS(v_as_SF);

}

if (ilow < 0)

ilow = 0;

else if (ilow > Py_SIZE(a))

ilow = Py_SIZE(a);

if (ihigh < ilow)

ihigh = ilow;

else if (ihigh > Py_SIZE(a))

ihigh = Py_SIZE(a);

norig = ihigh - ilow;

assert(norig >= 0);

d = n - norig;

if (Py_SIZE(a) + d == 0) {

Py_XDECREF(v_as_SF);

return list_clear(a);

}

item = a->ob_item;

/* recycle the items that we are about to remove */

s = norig * sizeof(PyObject *);

/* If norig == 0, item might be NULL, in which case we may not memcpy from it. */

if (s) {

if (s > sizeof(recycle_on_stack)) {

recycle = (PyObject **)PyMem_MALLOC(s);

if (recycle == NULL) {

PyErr_NoMemory();

goto Error;

}

}

memcpy(recycle, &item[ilow], s);

}

if (d < 0) { /* Delete -d items */

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;

}

item = a->ob_item;

}

else if (d > 0) { /* Insert d items */

k = Py_SIZE(a);

if (list_resize(a, k+d) < 0)

goto Error;

item = a->ob_item;

memmove(&item[ihigh+d], &item[ihigh],

(k - ihigh)*sizeof(PyObject *));

}

for (k = 0; k < n; k++, ilow++) {

PyObject *w = vitem[k];

Py_XINCREF(w);

item[ilow] = w;

}

for (k = norig - 1; k >= 0; --k)

Py_XDECREF(recycle[k]);

result = 0;

Error:

if (recycle != recycle_on_stack)

PyMem_FREE(recycle);

Py_XDECREF(v_as_SF);

return result;

#undef b

}

int

PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)

{

if (!PyList_Check(a)) {

PyErr_BadInternalCall();

return -1;

}

return list_ass_slice((PyListObject *)a, ilow, ihigh, v);

}

static PyObject *

list_inplace_repeat(PyListObject *self, Py_ssize_t n)

{

PyObject **items;

Py_ssize_t size, i, j, p;

size = PyList_GET_SIZE(self);

if (size == 0 || n == 1) {

Py_INCREF(self);

return (PyObject *)self;

}

if (n < 1) {

(void)list_clear(self);

Py_INCREF(self);

return (PyObject *)self;

}

if (size > PY_SSIZE_T_MAX / n) {

return PyErr_NoMemory();

}

if (list_resize(self, size*n) == -1)

return NULL;

p = size;

items = self->ob_item;

for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */

for (j = 0; j < size; j++) {

PyObject *o = items[j];

Py_INCREF(o);

items[p++] = o;

}

}

Py_INCREF(self);

return (PyObject *)self;

}

static int

list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)

{

PyObject *old_value;

if (i < 0 || i >= Py_SIZE(a)) {

PyErr_SetString(PyExc_IndexError,

"list assignment index out of range");

return -1;

}

if (v == NULL)

return list_ass_slice(a, i, i+1, v);

Py_INCREF(v);

old_value = a->ob_item[i];

a->ob_item[i] = v;

Py_DECREF(old_value);

return 0;

}

static PyObject *

listinsert(PyListObject *self, PyObject *args)

{

Py_ssize_t i;

PyObject *v;

if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))

return NULL;

if (ins1(self, i, v) == 0)

Py_RETURN_NONE;

return NULL;

}

static PyObject *

listclear(PyListObject *self)

{

list_clear(self);

Py_RETURN_NONE;

}

static PyObject *

listcopy(PyListObject *self)

{

return list_slice(self, 0, Py_SIZE(self));

}

static PyObject *

listappend(PyListObject *self, PyObject *v)

{

if (app1(self, v) == 0)

Py_RETURN_NONE;

return NULL;

}

static PyObject *

listextend(PyListObject *self, PyObject *b)

{

PyObject *it; /* iter(v) */

Py_ssize_t m; /* size of self */

Py_ssize_t n; /* guess for size of b */

Py_ssize_t mn; /* m + n */

Py_ssize_t i;

PyObject *(*iternext)(PyObject *);

/* Special cases:

1) lists and tuples which can use PySequence_Fast ops

2) extending self to self requires making a copy first

*/

if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {

PyObject **src, **dest;

b = PySequence_Fast(b, "argument must be iterable");

if (!b)

return NULL;

n = PySequence_Fast_GET_SIZE(b);

if (n == 0) {

/* short circuit when b is empty */

Py_DECREF(b);

Py_RETURN_NONE;

}

m = Py_SIZE(self);

if (list_resize(self, m + n) == -1) {

Py_DECREF(b);

return NULL;

}

/* note that we may still have self == b here for the

* situation a.extend(a), but the following code works

* in that case too. Just make sure to resize self

* before calling PySequence_Fast_ITEMS.

*/

/* populate the end of self with b's items */

src = PySequence_Fast_ITEMS(b);

dest = self->ob_item + m;

for (i = 0; i < n; i++) {

PyObject *o = src[i];

Py_INCREF(o);

dest[i] = o;

}

Py_DECREF(b);

Py_RETURN_NONE;

}

it = PyObject_GetIter(b);

if (it == NULL)

return NULL;

iternext = *it->ob_type->tp_iternext;

/* Guess a result list size. */

n = PyObject_LengthHint(b, 8);

if (n == -1) {

Py_DECREF(it);

return NULL;

}

m = Py_SIZE(self);

mn = m + n;

if (mn >= m) {

/* Make room. */

if (list_resize(self, mn) == -1)

goto error;

/* Make the list sane again. */

Py_SIZE(self) = m;

}

/* Else m + n overflowed; on the chance that n lied, and there really

* is enough room, ignore it. If n was telling the truth, we'll

* eventually run out of memory during the loop.

*/

/* Run iterator to exhaustion. */

for (;;) {

PyObject *item = iternext(it);

if (item == NULL) {

if (PyErr_Occurred()) {

if (PyErr_ExceptionMatches(PyExc_StopIteration))

PyErr_Clear();

else

goto error;

}

break;

}

if (Py_SIZE(self) < self->allocated) {

/* steals ref */

PyList_SET_ITEM(self, Py_SIZE(self), item);

++Py_SIZE(self);

}

else {

int status = app1(self, item);

Py_DECREF(item); /* append creates a new ref */

if (status < 0)

goto error;

}

}

/* Cut back result list if initial guess was too large. */

if (Py_SIZE(self) < self->allocated) {

if (list_resize(self, Py_SIZE(self)) < 0)

goto error;

}

Py_DECREF(it);

Py_RETURN_NONE;

error:

Py_DECREF(it);

return NULL;

}

PyObject *

_PyList_Extend(PyListObject *self, PyObject *b)

{

return listextend(self, b);

}

static PyObject *

list_inplace_concat(PyListObject *self, PyObject *other)

{

PyObject *result;

result = listextend(self, other);

if (result == NULL)

return result;

Py_DECREF(result);

Py_INCREF(self);

return (PyObject *)self;

}

static PyObject *

listpop(PyListObject *self, PyObject *args)

{

Py_ssize_t i = -1;

PyObject *v;

int status;

if (!PyArg_ParseTuple(args, "|n:pop", &i))

return NULL;

if (Py_SIZE(self) == 0) {

/* Special-case most common failure cause */

PyErr_SetString(PyExc_IndexError, "pop from empty list");

return NULL;

}

if (i < 0)

i += Py_SIZE(self);

if (i < 0 || i >= Py_SIZE(self)) {

PyErr_SetString(PyExc_IndexError, "pop index out of range");

return NULL;

}

v = self->ob_item[i];

if (i == Py_SIZE(self) - 1) {

status = list_resize(self, Py_SIZE(self) - 1);

if (status >= 0)

return v; /* and v now owns the reference the list had */

else

return NULL;

}

Py_INCREF(v);

status = list_ass_slice(self, i, i+1, (PyObject *)NULL);

if (status < 0) {

Py_DECREF(v);

return NULL;

}

return v;

}

/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */

static void

reverse_slice(PyObject **lo, PyObject **hi)

{

assert(lo && hi);

--hi;

while (lo < hi) {

PyObject *t = *lo;

*lo = *hi;

*hi = t;

++lo;

--hi;

}

}

/* Lots of code for an adaptive, stable, natural mergesort. There are many

* 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.

*/

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++;

}