listobject.c

/* List object implementation */

#include"Python.h"

#ifdefSTDC_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.
 */
staticint
list_resize(PyListObject*self, Py_ssize_tnewsize)
{
PyObject**items;
size_tnew_allocated;
Py_ssize_tallocated=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;
return0;
 }

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

/* Debug statistic to compare allocations with reuse through the free list */
#undef SHOW_ALLOC_COUNT
#ifdefSHOW_ALLOC_COUNT
staticsize_tcount_alloc=0;
staticsize_tcount_reuse=0;

staticvoid
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 */
#ifndefPyList_MAXFREELIST
#definePyList_MAXFREELIST 80
#endif
staticPyListObject*free_list[PyList_MAXFREELIST];
staticintnumfree=0;

void
PyList_Fini(void)
{
PyListObject*op;

while (numfree) {
op=free_list[--numfree];
assert(PyList_CheckExact(op));
PyObject_GC_Del(op);
 }
}

PyObject*
PyList_New(Py_ssize_tsize)
{
PyListObject*op;
size_tnbytes;
#ifdefSHOW_ALLOC_COUNT
staticintinitialized=0;
if (!initialized) {
Py_AtExit(show_alloc);
initialized=1;
 }
#endif

if (size<0) {
PyErr_BadInternalCall();
returnNULL;
 }
/* Check for overflow without an actual overflow,
 * which can cause compiler to optimise out */
if ((size_t)size>PY_SIZE_MAX / sizeof(PyObject*))
returnPyErr_NoMemory();
nbytes=size*sizeof(PyObject*);
if (numfree) {
numfree--;
op=free_list[numfree];
_Py_NewReference((PyObject*)op);
#ifdefSHOW_ALLOC_COUNT
count_reuse++;
#endif
 } else {
op=PyObject_GC_New(PyListObject, &PyList_Type);
if (op==NULL)
returnNULL;
#ifdefSHOW_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);
returnPyErr_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
returnPy_SIZE(op);
}

staticPyObject*indexerr=NULL;

PyObject*
PyList_GetItem(PyObject*op, Py_ssize_ti)
{
if (!PyList_Check(op)) {
PyErr_BadInternalCall();
returnNULL;
 }
if (i<0||i >= Py_SIZE(op)) {
if (indexerr==NULL) {
indexerr=PyString_FromString(
"list index out of range");
if (indexerr==NULL)
returnNULL;
 }
PyErr_SetObject(PyExc_IndexError, indexerr);
returnNULL;
 }
return ((PyListObject*)op) ->ob_item[i];
}

int
PyList_SetItem(register PyObject*op, register Py_ssize_ti,
 register PyObject*newitem)
{
 register PyObject*olditem;
 register PyObject**p;
if (!PyList_Check(op)) {
Py_XDECREF(newitem);
PyErr_BadInternalCall();
return-1;
 }
if (i<0||i >= Py_SIZE(op)) {
Py_XDECREF(newitem);
PyErr_SetString(PyExc_IndexError,
"list assignment index out of range");
return-1;
 }
p= ((PyListObject*)op) ->ob_item+i;
olditem=*p;
*p=newitem;
Py_XDECREF(olditem);
return0;
}

staticint
ins1(PyListObject*self, Py_ssize_twhere, PyObject*v)
{
Py_ssize_ti, 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;
return0;
}

int
PyList_Insert(PyObject*op, Py_ssize_twhere, PyObject*newitem)
{
if (!PyList_Check(op)) {
PyErr_BadInternalCall();
return-1;
 }
returnins1((PyListObject*)op, where, newitem);
}

staticint
app1(PyListObject*self, PyObject*v)
{
Py_ssize_tn=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);
return0;
}

int
PyList_Append(PyObject*op, PyObject*newitem)
{
if (PyList_Check(op) && (newitem!=NULL))
returnapp1((PyListObject*)op, newitem);
PyErr_BadInternalCall();
return-1;
}

/* Methods */

staticvoid
list_dealloc(PyListObject*op)
{
Py_ssize_ti;
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)
}

staticint
list_print(PyListObject*op, FILE*fp, intflags)
{
intrc;
Py_ssize_ti;
PyObject*item;

rc=Py_ReprEnter((PyObject*)op);
if (rc!=0) {
if (rc<0)
returnrc;
Py_BEGIN_ALLOW_THREADS
fprintf(fp, "[...]");
Py_END_ALLOW_THREADS
return0;
 }
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);
return0;
}

staticPyObject*
list_repr(PyListObject*v)
{
Py_ssize_ti;
PyObject*s, *temp;
PyObject*pieces= NULL, *result= NULL;

i=Py_ReprEnter((PyObject*)v);
if (i!=0) {
returni>0 ? PyString_FromString("[...]") : NULL;
 }

if (Py_SIZE(v) ==0) {
result=PyString_FromString("[]");
 goto Done;
 }

pieces=PyList_New(0);
if (pieces==NULL)
gotoDone;

/* 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) {
intstatus;
s=PyObject_Repr(v->ob_item[i]);
if (s==NULL)
gotoDone;
status=PyList_Append(pieces, s);
Py_DECREF(s); /* append created a new ref */
if (status<0)
gotoDone;
 }

/* Add "[]" decorations to the first and last items. */
assert(PyList_GET_SIZE(pieces) >0);
s=PyString_FromString("[");
if (s==NULL)
gotoDone;
temp=PyList_GET_ITEM(pieces, 0);
PyString_ConcatAndDel(&s, temp);
PyList_SET_ITEM(pieces, 0, s);
if (s==NULL)
gotoDone;

s=PyString_FromString("]");
if (s==NULL)
gotoDone;
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)
gotoDone;

/* Paste them all together with ", " between. */
s=PyString_FromString(", ");
if (s==NULL)
gotoDone;
result=_PyString_Join(s, pieces);
Py_DECREF(s);

Done:
Py_XDECREF(pieces);
Py_ReprLeave((PyObject*)v);
returnresult;
}

staticPy_ssize_t
list_length(PyListObject*a)
{
returnPy_SIZE(a);
}

staticint
list_contains(PyListObject*a, PyObject*el)
{
Py_ssize_ti;
intcmp;

for (i=0, cmp=0 ; cmp==0&&i<Py_SIZE(a); ++i)
cmp=PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
Py_EQ);
returncmp;
}

staticPyObject*
list_item(PyListObject*a, Py_ssize_ti)
{
if (i<0||i >= Py_SIZE(a)) {
if (indexerr==NULL) {
indexerr=PyString_FromString(
 "listindexoutofrange");
if (indexerr==NULL)
return NULL;
 }
PyErr_SetObject(PyExc_IndexError, indexerr);
return NULL;
 }
Py_INCREF(a->ob_item[i]);
returna->ob_item[i];
}

staticPyObject*
list_slice(PyListObject*a, Py_ssize_tilow, Py_ssize_tihigh)
{
PyListObject*np;
PyObject**src, **dest;
Py_ssize_ti, len;
if (ilow<0)
ilow=0;
elseif (ilow>Py_SIZE(a))
ilow=Py_SIZE(a);
if (ihigh<ilow)
ihigh=ilow;
elseif (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_tilow, Py_ssize_tihigh)
{
if (!PyList_Check(a)) {
PyErr_BadInternalCall();
return NULL;
 }
returnlist_slice((PyListObject*)a, ilow, ihigh);
}

staticPyObject*
list_concat(PyListObject*a, PyObject*bb)
{
Py_ssize_tsize;
Py_ssize_ti;
PyObject**src, **dest;
PyListObject*np;
if (!PyList_Check(bb)) {
PyErr_Format(PyExc_TypeError,
 "canonlyconcatenatelist (not \"%.200s\") tolist",
bb->ob_type->tp_name);
return NULL;
 }
#defineb ((PyListObject*)bb)
size=Py_SIZE(a) +Py_SIZE(b);
if (size<0)
returnPyErr_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;
#undefb
}

staticPyObject*
list_repeat(PyListObject*a, Py_ssize_tn)
{
Py_ssize_ti, j;
Py_ssize_tsize;
PyListObject*np;
PyObject**p, **items;
PyObject*elem;
if (n<0)
n=0;
if (n>0&&Py_SIZE(a) >PY_SSIZE_T_MAX / n)
returnPyErr_NoMemory();
size=Py_SIZE(a) *n;
if (size==0)
returnPyList_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;
}

staticint
list_clear(PyListObject*a)
{
Py_ssize_ti;
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! */
return0;
}

/* 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.
 */
staticint
list_ass_slice(PyListObject*a, Py_ssize_tilow, Py_ssize_tihigh, 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_tn; /* # of elements in replacement list */
Py_ssize_tnorig; /* # of elements in list getting replaced */
Py_ssize_td; /* Change in size */
Py_ssize_tk;
size_ts;
intresult=-1; /* guilty until proved innocent */
#defineb ((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)
returnresult;
result=list_ass_slice(a, ilow, ihigh, v);
Py_DECREF(v);
returnresult;
 }
v_as_SF=PySequence_Fast(v, "canonlyassignaniterable");
if(v_as_SF==NULL)
gotoError;
n=PySequence_Fast_GET_SIZE(v_as_SF);
vitem=PySequence_Fast_ITEMS(v_as_SF);
 }
if (ilow<0)
ilow=0;
elseif (ilow>Py_SIZE(a))
ilow=Py_SIZE(a);

if (ihigh<ilow)
ihigh=ilow;
elseif (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);
returnlist_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 */
memmove(&item[ihigh+d], &item[ihigh],
 (Py_SIZE(a) -ihigh)*sizeof(PyObject*));
list_resize(a, Py_SIZE(a) +d);
item=a->ob_item;
 }
elseif (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);
returnresult;
#undef b
}

int
PyList_SetSlice(PyObject*a, Py_ssize_tilow, Py_ssize_tihigh, PyObject*v)
{
if (!PyList_Check(a)) {
PyErr_BadInternalCall();
return-1;
 }
returnlist_ass_slice((PyListObject*)a, ilow, ihigh, v);
}

staticPyObject*
list_inplace_repeat(PyListObject*self, Py_ssize_tn)
{
PyObject**items;
Py_ssize_tsize, 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) {
returnPyErr_NoMemory();
 }

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

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

staticint
list_ass_item(PyListObject*a, Py_ssize_ti, 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)
returnlist_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);
return0;
}

staticPyObject*
listinsert(PyListObject*self, PyObject*args)
{
Py_ssize_ti;
PyObject*v;
if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))
returnNULL;
if (ins1(self, i, v) ==0)
Py_RETURN_NONE;
returnNULL;
}

staticPyObject*
listappend(PyListObject*self, PyObject*v)
{
if (app1(self, v) ==0)
Py_RETURN_NONE;
returnNULL;
}

staticPyObject*
listextend(PyListObject*self, PyObject*b)
{
PyObject*it; /* iter(v) */
Py_ssize_tm; /* size of self */
Py_ssize_tn; /* guess for size of b */
Py_ssize_tmn; /* m + n */
Py_ssize_ti;
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)
returnNULL;
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);
returnNULL;
 }
/* 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)
returnNULL;
iternext=*it->ob_type->tp_iternext;

/* Guess a result list size. */
n=_PyObject_LengthHint(b, 8);
if (n==-1) {
Py_DECREF(it);
returnNULL;
 }
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 {
intstatus=app1(self, item);
Py_DECREF(item); /* append creates a new ref */
if (status<0)
 goto error;
 }
 }

/* Cut back result list if initial guess was too large. */
if (Py_SIZE(self) <self->allocated)
list_resize(self, Py_SIZE(self)); /* shrinking can't fail */

Py_DECREF(it);
Py_RETURN_NONE;

error:
Py_DECREF(it);
returnNULL;
}

PyObject*
_PyList_Extend(PyListObject*self, PyObject*b)
{
returnlistextend(self, b);
}

staticPyObject*
list_inplace_concat(PyListObject*self, PyObject*other)
{
PyObject*result;

result=listextend(self, other);
if (result==NULL)
returnresult;
Py_DECREF(result);
Py_INCREF(self);
return (PyObject*)self;
}

staticPyObject*
listpop(PyListObject*self, PyObject*args)
{
Py_ssize_ti=-1;
PyObject*v;
intstatus;

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

if (Py_SIZE(self) ==0) {
/* Special-case most common failure cause */
PyErr_SetString(PyExc_IndexError, "pop from empty list");
returnNULL;
 }
if (i<0)
i+=Py_SIZE(self);
if (i<0||i >= Py_SIZE(self)) {
PyErr_SetString(PyExc_IndexError, "pop index out of range");
returnNULL;
 }
v=self->ob_item[i];
if (i==Py_SIZE(self) -1) {
status=list_resize(self, Py_SIZE(self) -1);
assert(status >= 0);
returnv; /* and v now owns the reference the list had */
 }
Py_INCREF(v);
status=list_ass_slice(self, i, i+1, (PyObject*)NULL);
assert(status >= 0);
/* Use status, so that in a release build compilers don't
 * complain about the unused name.
 */
 (void) status;

returnv;
}

/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
staticvoid
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.
 */

/* 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.
 */
staticint
islt(PyObject*x, PyObject*y, PyObject*compare)
{
PyObject*res;
PyObject*args;
Py_ssize_ti;

assert(compare!=NULL);
/* Call the user's comparison function and translate the 3-way
 * result into true or false (or error).
 */