/* List object implementation */

#include "Python.h"

#ifdef STDC_HEADERS

#include <stddef.h>

#else

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

#endif

/* Ensure ob_item has room for at least newsize elements, and set

 * ob_size to newsize.  If newsize > ob_size on entry, the content

 * of the new slots at exit is undefined heap trash; it's the caller's

 * responsiblity to overwrite them with sane values.

 * The number of allocated elements may grow, shrink, or stay the same.

 * Failure is impossible if newsize <= self.allocated on entry, although

 * that partly relies on an assumption that the system realloc() never

 * fails when passed a number of bytes <= the number of bytes last

 * allocated (the C standard doesn't guarantee this, but it's hard to

 * imagine a realloc implementation where it wouldn't be true).

 * Note that self->ob_item may change, and even if newsize is less

 * than ob_size on entry.

 */

static int

list_resize(PyListObject *self, Py_ssize_t newsize)

{

	PyObject **items;

	size_t new_allocated;

	Py_ssize_t allocated = self->allocated;

	/* Bypass realloc() when a previous overallocation is large enough

	   to accommodate the newsize.  If the newsize falls lower than half

	   the allocated size, then proceed with the realloc() to shrink the list.

	*/

	if (allocated >= newsize && newsize >= (allocated >> 1)) {

		assert(self->ob_item != NULL || newsize == 0);

		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 <= ((~(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;

}

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

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

	}

	nbytes = size * sizeof(PyObject *);

	/* Check for overflow without an actual overflow,

	 *  which can cause compiler to optimise out */

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

#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 = PyString_FromString(

				"list index out of range");

		PyErr_SetObject(PyExc_IndexError, indexerr);

		return NULL;

	}

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

}

int

PyList_SetItem(register PyObject *op, register Py_ssize_t i,

               register PyObject *newitem)

{

	register PyObject *olditem;

	register PyObject **p;

	if (!PyList_Check(op)) {

		Py_XDECREF(newitem);

		PyErr_BadInternalCall();

		return -1;

	}

	if (i < 0 || i >= 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 int

list_print(PyListObject *op, FILE *fp, int flags)

{

	int rc;

	Py_ssize_t i;

	rc = Py_ReprEnter((PyObject*)op);

	if (rc != 0) {

		if (rc < 0)

			return rc;

		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++) {

		if (i > 0) {

			Py_BEGIN_ALLOW_THREADS

			fprintf(fp, ", ");

			Py_END_ALLOW_THREADS

		}

		if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {

			Py_ReprLeave((PyObject *)op);

			return -1;

		}

	}

	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 ? PyString_FromString("[...]") : NULL;

	}

	if (Py_SIZE(v) == 0) {

		result = PyString_FromString("[]");

		goto Done;

	}

	pieces = PyList_New(0);

	if (pieces == NULL)

		goto Done;

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

	   so must refetch the list size on each iteration. */

	for (i = 0; i < 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 = PyString_FromString("[");

	if (s == NULL)

		goto Done;

	temp = PyList_GET_ITEM(pieces, 0);

	PyString_ConcatAndDel(&s, temp);

	PyList_SET_ITEM(pieces, 0, s);

	if (s == NULL)

		goto Done;

	s = PyString_FromString("]");

	if (s == NULL)

		goto Done;

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

	PyString_ConcatAndDel(&temp, s);

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

	if (temp == NULL)

		goto Done;

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

	s = PyString_FromString(", ");

	if (s == NULL)

		goto Done;

	result = _PyString_Join(s, pieces);

	Py_DECREF(s);

Done:

	Py_XDECREF(pieces);

	Py_ReprLeave((PyObject *)v);

	return result;

}

static Py_ssize_t

list_length(PyListObject *a)

{

	return 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 = PyString_FromString(

				"list index out of range");

		PyErr_SetObject(PyExc_IndexError, indexerr);

		return NULL;

	}

	Py_INCREF(a->ob_item[i]);

	return a->ob_item[i];

}

static PyObject *

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

{

	PyListObject *np;

	PyObject **src, **dest;

	Py_ssize_t i, len;

	if (ilow < 0)

		ilow = 0;

	else if (ilow > 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;