#include "Python.h"

#ifdef STDC_HEADERS

#include <stddef.h>

#include <sys/types.h> /* For size_t */

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

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

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

/* check for integer overflow */

if (new_allocated > PY_SIZE_MAX - newsize) {

PyErr_NoMemory();

return -1;

} else {

new_allocated += newsize;

}

if (newsize == 0)

new_allocated = 0;

items = self->ob_item;

if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *)))

PyMem_RESIZE(items, PyObject *, new_allocated);

else

items = NULL;

if (items == NULL) {

PyErr_NoMemory();

return -1;

}

self->ob_item = items;

Py_SIZE(self) = newsize;

self->allocated = new_allocated;

return 0;

}

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

}

#ifndef PyList_MAXFREELIST

#define PyList_MAXFREELIST 80

static PyListObject *free_list[PyList_MAXFREELIST];

static int numfree = 0;

PyList_Fini(void)

{

PyListObject *op;

while (numfree) {

op = free_list[--numfree];

assert(PyList_CheckExact(op));

PyObject_GC_Del(op);

}

}

PyObject *

PyList_New(Py_ssize_t size)

{

PyListObject *op;

size_t nbytes;

#ifdef SHOW_ALLOC_COUNT

static int initialized = 0;

if (!initialized) {

Py_AtExit(show_alloc);

initialized = 1;

}

if (size < 0) {

PyErr_BadInternalCall();

return NULL;

}

nbytes = size * sizeof(PyObject *);

/* Check for overflow without an actual overflow,

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

return PyErr_NoMemory();

if (numfree) {

numfree--;

op = free_list[numfree];

_Py_NewReference((PyObject *)op);

#ifdef SHOW_ALLOC_COUNT

count_reuse++;

} else {

op = PyObject_GC_New(PyListObject, &PyList_Type);

if (op == NULL)

return NULL;

#ifdef SHOW_ALLOC_COUNT

count_alloc++;

}

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;

}

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

PyErr_SetObject(PyExc_IndexError, indexerr);

return NULL;

}

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

}

PyList_SetItem(register PyObject *op, register Py_ssize_t i,

register PyObject *newitem)

{

register PyObject *olditem;

register PyObject **p;

if (!PyList_Check(op)) {

Py_XDECREF(newitem);

PyErr_BadInternalCall();

return -1;

}

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

Py_XDECREF(newitem);

PyErr_SetString(PyExc_IndexError,

"list assignment index out of range");

return -1;

}

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

olditem = *p;

*p = newitem;

Py_XDECREF(olditem);

return 0;

}

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;

}

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;

}

PyList_Append(PyObject *op, PyObject *newitem)

{

if (PyList_Check(op) && (newitem != NULL))

return app1((PyListObject *)op, newitem);

PyErr_BadInternalCall();

return -1;

}

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.

i = Py_SIZE(op);

while (--i >= 0) {

Py_XDECREF(op->ob_item[i]);

}

PyMem_FREE(op->ob_item);

}

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

free_list[numfree++] = op;

else

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

Py_TRASHCAN_SAFE_END(op)

}

static PyObject *

list_repr(PyListObject *v)

{

Py_ssize_t i;

PyObject *s, *temp;

PyObject *pieces = NULL, *result = NULL;

i = Py_ReprEnter((PyObject*)v);

if (i != 0) {

return i > 0 ? PyUnicode_FromString("[...]") : NULL;

}

if (Py_SIZE(v) == 0) {

result = PyUnicode_FromString("[]");

goto Done;

}

pieces = PyList_New(0);

if (pieces == NULL)

goto Done;

/* Do repr() on each element. Note that this may mutate the list,

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

int status;

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

goto Done;

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

Py_LeaveRecursiveCall();

if (s == NULL)

goto Done;

status = PyList_Append(pieces, s);

Py_DECREF(s); /* append created a new ref */

if (status < 0)

goto Done;

}

/* Add "[]" decorations to the first and last items. */

assert(PyList_GET_SIZE(pieces) > 0);

s = PyUnicode_FromString("[");

if (s == NULL)

goto Done;

temp = PyList_GET_ITEM(pieces, 0);

PyUnicode_AppendAndDel(&s, temp);

PyList_SET_ITEM(pieces, 0, s);

if (s == NULL)

goto Done;

s = PyUnicode_FromString("]");

if (s == NULL)

goto Done;

temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);

PyUnicode_AppendAndDel(&temp, s);

PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);

if (temp == NULL)

goto Done;

/* Paste them all together with ", " between. */

s = PyUnicode_FromString(", ");

if (s == NULL)

goto Done;

result = PyUnicode_Join(s, pieces);

Py_DECREF(s);

Done:

Py_XDECREF(pieces);

Py_ReprLeave((PyObject *)v);

return result;

}

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

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;

size = Py_SIZE(a) * n;

if (n && size/n != Py_SIZE(a))

return PyErr_NoMemory();

if (size == 0)

return PyList_New(0);

np = (PyListObject *) PyList_New(size);

if (np == NULL)

return NULL;

items = np->ob_item;

if (Py_SIZE(a) == 1) {

elem = a->ob_item[0];

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

items[i] = elem;

Py_INCREF(elem);

}

return (PyObject *) np;

}

p = np->ob_item;

items = a->ob_item;

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

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

*p = items[j];

Py_INCREF(*p);

p++;

}

}

return (PyObject *) np;

}

static int

list_clear(PyListObject *a)

{

Py_ssize_t i;

PyObject **item = a->ob_item;

if (item != NULL) {

/* Because XDECREF can recursively invoke operations on

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.

return 0;

}

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

PyObject *recycle_on_stack[8];

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

PyObject **item;

PyObject **vitem = NULL;

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

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

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

Py_ssize_t d; /* Change in size */

Py_ssize_t k;

size_t s;

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

#define b ((PyListObject *)v)

if (v == NULL)

n = 0;

else {

if (a == b) {

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

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

if (v == NULL)

return result;

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

Py_DECREF(v);

return result;

}

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

if(v_as_SF == NULL)

goto Error;

n = PySequence_Fast_GET_SIZE(v_as_SF);

vitem = PySequence_Fast_ITEMS(v_as_SF);

}

if (ilow < 0)

ilow = 0;

else if (ilow > Py_SIZE(a))

ilow = Py_SIZE(a);

if (ihigh < ilow)

ihigh = ilow;

else if (ihigh > Py_SIZE(a))

ihigh = Py_SIZE(a);

norig = ihigh - ilow;

assert(norig >= 0);

d = n - norig;

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

Py_XDECREF(v_as_SF);

return list_clear(a);

}

item = a->ob_item;

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

s = norig * sizeof(PyObject *);

if (s > sizeof(recycle_on_stack)) {

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

if (recycle == NULL) {

PyErr_NoMemory();

goto Error;

}

}

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

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

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

(Py_SIZE(a) - ihigh)*sizeof(PyObject *));

list_resize(a, Py_SIZE(a) + d);

item = a->ob_item;

}

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

k = Py_SIZE(a);

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

goto Error;

item = a->ob_item;

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

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

}

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

PyObject *w = vitem[k];

Py_XINCREF(w);

item[ilow] = w;

}

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

Py_XDECREF(recycle[k]);

result = 0;

Error:

if (recycle != recycle_on_stack)

PyMem_FREE(recycle);

Py_XDECREF(v_as_SF);

return result;

#undef b

}

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 *

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:

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

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

/* Run iterator to exhaustion. */

for (;;) {

PyObject *item = iternext(it);

if (item == NULL) {

if (PyErr_Occurred()) {

if (PyErr_ExceptionMatches(PyExc_StopIteration))

PyErr_Clear();

else

goto error;

}

break;

}

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

/* steals ref */

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

++Py_SIZE(self);

}

else {

int status = app1(self, item);

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

if (status < 0)

goto error;

}

}

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

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

list_resize(self, Py_SIZE(self)); /* shrinking can't fail */

Py_DECREF(it);

Py_RETURN_NONE;

error:

Py_DECREF(it);

return NULL;

}

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

assert(status >= 0);

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

}

Py_INCREF(v);

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

assert(status >= 0);

/* Use status, so that in a release build compilers don't

(void) status;

return v;

}

static void

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

{

assert(lo && hi);

--hi;

while (lo < hi) {

PyObject *t = *lo;

*lo = *hi;

*hi = t;

++lo;

--hi;

}

}

#define ISLT(X, Y) (PyObject_RichCompareBool(X, Y, Py_LT))

#define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail; \

if (k)

static int

binarysort(PyObject **lo, PyObject **hi, PyObject **start)

{

register Py_ssize_t k;

register PyObject **l, **p, **r;

register PyObject *pivot;

assert(lo <= start && start <= hi);

/* assert [lo, start) is sorted */

if (lo == start)

++start;

for (; start < hi; ++start) {

/* set l to where *start belongs */

l = lo;

r = start;

pivot = *r;

/* Invariants:

assert(l < r);

do {

p = l + ((r - l) >> 1);

IFLT(pivot, *p)

r = p;

else

l = p+1;

} while (l < r);

assert(l == r);

/* The invariants still hold, so pivot >= all in [lo, l) and

for (p = start; p > l; --p)

*p = *(p-1);

*l = pivot;