Objects/listobject.c

/* List object implementation */

#include "Python.h"

#ifdef STDC_HEADERS
#include <stddef.h>
#else
#include <sys/types.h>		/* For size_t */
#endif

static int
roundupsize(int n)
{
	unsigned int nbits = 0;
	unsigned int n2 = (unsigned int)n >> 5;

	/* Round up:
	 * If n <       256, to a multiple of        8.
	 * If n <      2048, to a multiple of       64.
	 * If n <     16384, to a multiple of      512.
	 * If n <    131072, to a multiple of     4096.
	 * If n <   1048576, to a multiple of    32768.
	 * If n <   8388608, to a multiple of   262144.
	 * If n <  67108864, to a multiple of  2097152.
	 * If n < 536870912, to a multiple of 16777216.
	 * ...
	 * If n < 2**(5+3*i), to a multiple of 2**(3*i).
	 *
	 * 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() (which is a reality, e.g., across all flavors
	 * of Windows, with Win9x behavior being particularly bad -- and
	 * we've still got address space fragmentation problems on Win9x
	 * even with this scheme, although it requires much longer lists to
	 * provoke them than it used to).
	 */
	do {
		n2 >>= 3;
		nbits += 3;
	} while (n2);
	return ((n >> nbits) + 1) << nbits;
 }

#define NRESIZE(var, type, nitems)				\
do {								\
	size_t _new_size = roundupsize(nitems);			\
	if (_new_size <= ((~(size_t)0) / sizeof(type)))		\
		PyMem_RESIZE(var, type, _new_size);		\
	else							\
		var = NULL;					\
} while (0)

PyObject *
PyList_New(int size)
{
	PyListObject *op;
	size_t nbytes;
	if (size < 0) {
		PyErr_BadInternalCall();
		return NULL;
	}
	nbytes = size * sizeof(PyObject *);
	/* Check for overflow */
	if (nbytes / sizeof(PyObject *) != (size_t)size) {
		return PyErr_NoMemory();
	}
	op = PyObject_GC_New(PyListObject, &PyList_Type);
	if (op == NULL) {
		return NULL;
	}
	if (size <= 0) {
		op->ob_item = NULL;
	}
	else {
		op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
		if (op->ob_item == NULL) {
			return PyErr_NoMemory();
		}
		memset(op->ob_item, 0, sizeof(*op->ob_item) * size);
	}
	op->ob_size = size;
	_PyObject_GC_TRACK(op);
	return (PyObject *) op;
}

int
PyList_Size(PyObject *op)
{
	if (!PyList_Check(op)) {
		PyErr_BadInternalCall();
		return -1;
	}
	else
		return ((PyListObject *)op) -> ob_size;
}

static PyObject *indexerr;

PyObject *
PyList_GetItem(PyObject *op, int i)
{
	if (!PyList_Check(op)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
		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 int 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 >= ((PyListObject *)op) -> ob_size) {
		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, int where, PyObject *v)
{
	int i;
	PyObject **items;
	if (v == NULL) {
		PyErr_BadInternalCall();
		return -1;
	}
	if (self->ob_size == INT_MAX) {
		PyErr_SetString(PyExc_OverflowError,
			"cannot add more objects to list");
		return -1;
	}
	items = self->ob_item;
	NRESIZE(items, PyObject *, self->ob_size+1);
	if (items == NULL) {
		PyErr_NoMemory();
		return -1;
	}
	if (where < 0)
		where = 0;
	if (where > self->ob_size)
		where = self->ob_size;
	for (i = self->ob_size; --i >= where; )
		items[i+1] = items[i];
	Py_INCREF(v);
	items[where] = v;
	self->ob_item = items;
	self->ob_size++;
	return 0;
}

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

int
PyList_Append(PyObject *op, PyObject *newitem)
{
	if (!PyList_Check(op)) {
		PyErr_BadInternalCall();
		return -1;
	}
	return ins1((PyListObject *)op,
		(int) ((PyListObject *)op)->ob_size, newitem);
}

/* Methods */

static void
list_dealloc(PyListObject *op)
{
	int 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 = op->ob_size;
		while (--i >= 0) {
			Py_XDECREF(op->ob_item[i]);
		}
		PyMem_FREE(op->ob_item);
	}
	op->ob_type->tp_free((PyObject *)op);
	Py_TRASHCAN_SAFE_END(op)
}

static int
list_print(PyListObject *op, FILE *fp, int flags)
{
	int i;

	i = Py_ReprEnter((PyObject*)op);
	if (i != 0) {
		if (i < 0)
			return i;
		fprintf(fp, "[...]");
		return 0;
	}
	fprintf(fp, "[");
	for (i = 0; i < op->ob_size; i++) {
		if (i > 0)
			fprintf(fp, ", ");
		if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {
			Py_ReprLeave((PyObject *)op);
			return -1;
		}
	}
	fprintf(fp, "]");
	Py_ReprLeave((PyObject *)op);
	return 0;
}

static PyObject *
list_repr(PyListObject *v)
{
	int i;
	PyObject *s, *temp;
	PyObject *pieces = NULL, *result = NULL;

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

	if (v->ob_size == 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 < v->ob_size; ++i) {
		int status;
		s = PyObject_Repr(v->ob_item[i]);
		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 int
list_length(PyListObject *a)
{
	return a->ob_size;
}



static int
list_contains(PyListObject *a, PyObject *el)
{
	int i;

	for (i = 0; i < a->ob_size; ++i) {
		int cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
						   Py_EQ);
		if (cmp > 0)
			return 1;
		else if (cmp < 0)
			return -1;
	}
	return 0;
}


static PyObject *
list_item(PyListObject *a, int i)
{
	if (i < 0 || i >= a->ob_size) {
		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, int ilow, int ihigh)
{
	PyListObject *np;
	int i;
	if (ilow < 0)
		ilow = 0;
	else if (ilow > a->ob_size)
		ilow = a->ob_size;
	if (ihigh < ilow)
		ihigh = ilow;
	else if (ihigh > a->ob_size)
		ihigh = a->ob_size;
	np = (PyListObject *) PyList_New(ihigh - ilow);
	if (np == NULL)
		return NULL;
	for (i = ilow; i < ihigh; i++) {
		PyObject *v = a->ob_item[i];
		Py_INCREF(v);
		np->ob_item[i - ilow] = v;
	}
	return (PyObject *)np;
}

PyObject *
PyList_GetSlice(PyObject *a, int ilow, int ihigh)
{
	if (!PyList_Check(a)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	return list_slice((PyListObject *)a, ilow, ihigh);
}

static PyObject *
list_concat(PyListObject *a, PyObject *bb)
{
	int size;
	int i;
	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 = a->ob_size + b->ob_size;
	np = (PyListObject *) PyList_New(size);
	if (np == NULL) {
		return NULL;
	}
	for (i = 0; i < a->ob_size; i++) {
		PyObject *v = a->ob_item[i];
		Py_INCREF(v);
		np->ob_item[i] = v;
	}
	for (i = 0; i < b->ob_size; i++) {
		PyObject *v = b->ob_item[i];
		Py_INCREF(v);
		np->ob_item[i + a->ob_size] = v;
	}
	return (PyObject *)np;
#undef b
}

static PyObject *
list_repeat(PyListObject *a, int n)
{
	int i, j;
	int size;
	PyListObject *np;
	PyObject **p;
	if (n < 0)
		n = 0;
	size = a->ob_size * n;
	np = (PyListObject *) PyList_New(size);
	if (np == NULL)
		return NULL;
	p = np->ob_item;
	for (i = 0; i < n; i++) {
		for (j = 0; j < a->ob_size; j++) {
			*p = a->ob_item[j];
			Py_INCREF(*p);
			p++;
		}
	}
	return (PyObject *) np;
}

static int
list_ass_slice(PyListObject *a, int ilow, int 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, **p;
	PyObject **item;
	int n; /* Size of replacement list */
	int d; /* Change in size */
	int k; /* Loop index */
#define b ((PyListObject *)v)
	if (v == NULL)
		n = 0;
	else if (PyList_Check(v)) {
		n = b->ob_size;
		if (a == b) {
			/* Special case "a[i:j] = a" -- copy b first */
			int ret;
			v = list_slice(b, 0, n);
			ret = list_ass_slice(a, ilow, ihigh, v);
			Py_DECREF(v);
			return ret;
		}
	}
	else {
		PyErr_Format(PyExc_TypeError,
			     "must assign list (not \"%.200s\") to slice",
			     v->ob_type->tp_name);
		return -1;
	}
	if (ilow < 0)
		ilow = 0;
	else if (ilow > a->ob_size)
		ilow = a->ob_size;
	if (ihigh < ilow)
		ihigh = ilow;
	else if (ihigh > a->ob_size)
		ihigh = a->ob_size;
	item = a->ob_item;
	d = n - (ihigh-ilow);
	if (ihigh > ilow)
		p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
	else
		p = recycle = NULL;
	if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
		for (k = ilow; k < ihigh; k++)
			*p++ = item[k];
		if (d < 0) {
			for (/*k = ihigh*/; k < a->ob_size; k++)
				item[k+d] = item[k];
			a->ob_size += d;
			NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
			a->ob_item = item;
		}
	}
	else { /* Insert d items; recycle ihigh-ilow items */
		NRESIZE(item, PyObject *, a->ob_size + d);
		if (item == NULL) {
			if (recycle != NULL)
				PyMem_DEL(recycle);
			PyErr_NoMemory();
			return -1;
		}
		for (k = a->ob_size; --k >= ihigh; )
			item[k+d] = item[k];
		for (/*k = ihigh-1*/; k >= ilow; --k)
			*p++ = item[k];
		a->ob_item = item;
		a->ob_size += d;
	}
	for (k = 0; k < n; k++, ilow++) {
		PyObject *w = b->ob_item[k];
		Py_XINCREF(w);
		item[ilow] = w;
	}
	if (recycle) {
		while (--p >= recycle)
			Py_XDECREF(*p);
		PyMem_DEL(recycle);
	}
	if (a->ob_size == 0 && a->ob_item != NULL) {
		PyMem_FREE(a->ob_item);
		a->ob_item = NULL;
	}
	return 0;
#undef b
}

int
PyList_SetSlice(PyObject *a, int ilow, int 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, int n)
{
	PyObject **items;
	int size, i, j;


	size = PyList_GET_SIZE(self);
	if (size == 0) {
		Py_INCREF(self);
		return (PyObject *)self;
	}

	items = self->ob_item;

	if (n < 1) {
		self->ob_item = NULL;
		self->ob_size = 0;
		for (i = 0; i < size; i++)
			Py_XDECREF(items[i]);
		PyMem_DEL(items);
		Py_INCREF(self);
		return (PyObject *)self;
	}

	NRESIZE(items, PyObject*, size*n);
	if (items == NULL) {
		PyErr_NoMemory();
		goto finally;
	}
	self->ob_item = items;
	for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
		for (j = 0; j < size; j++) {
			PyObject *o = PyList_GET_ITEM(self, j);
			Py_INCREF(o);
			PyList_SET_ITEM(self, self->ob_size++, o);
		}
	}
	Py_INCREF(self);
	return (PyObject *)self;
  finally:
  	return NULL;
}

static int
list_ass_item(PyListObject *a, int i, PyObject *v)
{
	PyObject *old_value;
	if (i < 0 || i >= a->ob_size) {
		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 *
ins(PyListObject *self, int where, PyObject *v)
{
	if (ins1(self, where, v) != 0)
		return NULL;
	Py_INCREF(Py_None);
	return Py_None;
}

static PyObject *
listinsert(PyListObject *self, PyObject *args)
{
	int i;
	PyObject *v;
	if (!PyArg_ParseTuple(args, "iO:insert", &i, &v))
		return NULL;
	return ins(self, i, v);
}

static PyObject *
listappend(PyListObject *self, PyObject *v)
{
	return ins(self, (int) self->ob_size, v);
}

static int
listextend_internal(PyListObject *self, PyObject *b)
{
	PyObject **items;
	int selflen = PyList_GET_SIZE(self);
	int blen;
	register int i;

	if (PyObject_Size(b) == 0) {
		/* short circuit when b is empty */
		Py_DECREF(b);
		return 0;
	}

	if (self == (PyListObject*)b) {
		/* as in list_ass_slice() we must special case the
		 * situation: a.extend(a)
		 *
		 * XXX: I think this way ought to be faster than using
		 * list_slice() the way list_ass_slice() does.
		 */
		Py_DECREF(b);
		b = PyList_New(selflen);
		if (!b)
			return -1;
		for (i = 0; i < selflen; i++) {
			PyObject *o = PyList_GET_ITEM(self, i);
			Py_INCREF(o);
			PyList_SET_ITEM(b, i, o);
		}
	}

	blen = PyObject_Size(b);

	/* resize a using idiom */
	items = self->ob_item;
	NRESIZE(items, PyObject*, selflen + blen);
	if (items == NULL) {
		PyErr_NoMemory();
		Py_DECREF(b);
		return -1;
	}

	self->ob_item = items;

	/* populate the end of self with b's items */
	for (i = 0; i < blen; i++) {
		PyObject *o = PySequence_Fast_GET_ITEM(b, i);
		Py_INCREF(o);
		PyList_SET_ITEM(self, self->ob_size++, o);
	}
	Py_DECREF(b);
	return 0;
}


static PyObject *
list_inplace_concat(PyListObject *self, PyObject *other)
{
	other = PySequence_Fast(other, "argument to += must be iterable");
	if (!other)
		return NULL;

	if (listextend_internal(self, other) < 0)
		return NULL;

	Py_INCREF(self);
	return (PyObject *)self;
}

static PyObject *
listextend(PyListObject *self, PyObject *b)
{

	b = PySequence_Fast(b, "list.extend() argument must be iterable");
	if (!b)
		return NULL;

	if (listextend_internal(self, b) < 0)
		return NULL;

	Py_INCREF(Py_None);
	return Py_None;
}

static PyObject *
listpop(PyListObject *self, PyObject *args)
{
	int i = -1;
	PyObject *v;
	if (!PyArg_ParseTuple(args, "|i:pop", &i))
		return NULL;
	if (self->ob_size == 0) {
		/* Special-case most common failure cause */
		PyErr_SetString(PyExc_IndexError, "pop from empty list");
		return NULL;
	}
	if (i < 0)
		i += self->ob_size;
	if (i < 0 || i >= self->ob_size) {
		PyErr_SetString(PyExc_IndexError, "pop index out of range");
		return NULL;
	}
	v = self->ob_item[i];
	Py_INCREF(v);
	if (list_ass_slice(self, i, i+1, (PyObject *)NULL) != 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;
	}
}

/* New quicksort implementation for arrays of object pointers.
   Thanks to discussions with Tim Peters. */

/* Comparison function.  Takes care of calling a user-supplied
   comparison function (any callable Python object).  Calls the
   standard comparison function, PyObject_RichCompareBool(), if the user-
   supplied function is NULL.
   Returns <0 on error, >0 if x < y, 0 if x >= y. */

static int
islt(PyObject *x, PyObject *y, PyObject *compare)
{
	PyObject *res;
	PyObject *args;
	int i;

	if (compare == NULL)
		return PyObject_RichCompareBool(x, y, Py_LT);

	/* 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)) {
		Py_DECREF(res);
		PyErr_SetString(PyExc_TypeError,
				"comparison function must return int");
		return -1;
	}
	i = PyInt_AsLong(res);
	Py_DECREF(res);
	return i < 0;
}

/* MINSIZE is the smallest array that will get a full-blown samplesort
   treatment; smaller arrays are sorted using binary insertion.  It must
   be at least 7 for the samplesort implementation to work.  Binary
   insertion does fewer compares, but can suffer O(N**2) data movement.
   The more expensive compares, the larger MINSIZE should be. */
#define MINSIZE 100

/* MINPARTITIONSIZE is the smallest array slice samplesort will bother to
   partition; smaller slices are passed to binarysort.  It must be at
   least 2, and no larger than MINSIZE.  Setting it higher reduces the #
   of compares slowly, but increases the amount of data movement quickly.
   The value here was chosen assuming a compare costs ~25x more than
   swapping a pair of memory-resident pointers -- but under that assumption,
   changing the value by a few dozen more or less has aggregate effect
   under 1%.  So the value is crucial, but not touchy <wink>. */
#define MINPARTITIONSIZE 40

/* MAXMERGE is the largest number of elements we'll always merge into
   a known-to-be sorted chunk via binary insertion, regardless of the
   size of that chunk.  Given a chunk of N sorted elements, and a group
   of K unknowns, the largest K for which it's better to do insertion
   (than a full-blown sort) is a complicated function of N and K mostly
   involving the expected number of compares and data moves under each
   approach, and the relative cost of those operations on a specific
   architecure.  The fixed value here is conservative, and should be a
   clear win regardless of architecture or N. */
#define MAXMERGE 15

/* STACKSIZE is the size of our work stack.  A rough estimate is that
   this allows us to sort arrays of size N where
   N / ln(N) = MINPARTITIONSIZE * 2**STACKSIZE, so 60 is more than enough
   for arrays of size 2**64.  Because we push the biggest partition
   first, the worst case occurs when all subarrays are always partitioned
   exactly in two. */
#define STACKSIZE 60

/* Compare X to Y via islt().  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, compare)) < 0) goto fail;  \
		   if (k)

/* binarysort is the best method for sorting small arrays: it does
   few compares, but can do data movement quadratic in the number of
   elements.
   [lo, hi) is a contiguous slice of a list, and is sorted via
   binary insertion.  This sort is stable.
   On entry, must have lo <= start <= hi, and that [lo, start) is already
   sorted (pass start == lo if you don't know!).
   If islt() complains return -1, else 0.
   Even in case of error, the output slice will be some permutation of
   the input (nothing is lost or duplicated).
*/

static int
binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
     /* compare -- comparison function object, or NULL for default */
{
	register int 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:
		 * pivot >= all in [lo, l).
		 * pivot  < all in [r, start).
		 * The second is vacuously true at the start.
		 */
		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
		   pivot < all in [l, start), so pivot belongs at l.  Note
		   that if there are elements equal to pivot, l points to the
		   first slot after them -- that's why this sort is stable.
		   Slide over to make room.
		   Caution: using memmove is much slower under MSVC 5;
		   we're not usually moving many slots. */
		for (p = start; p > l; --p)
			*p = *(p-1);
		*l = pivot;
	}
	return 0;

 fail:
	return -1;
}

/* samplesortslice is the sorting workhorse.
   [lo, hi) is a contiguous slice of a list, to be sorted in place.
   On entry, must have lo <= hi,
   If islt() complains return -1, else 0.
   Even in case of error, the output slice will be some permutation of
   the input (nothing is lost or duplicated).

   samplesort is basically quicksort on steroids:  a power of 2 close
   to n/ln(n) is computed, and that many elements (less 1) are picked at
   random from the array and sorted.  These 2**k - 1 elements are then
   used as preselected pivots for an equal number of quicksort
   partitioning steps, partitioning the slice into 2**k chunks each of
   size about ln(n).  These small final chunks are then usually handled
   by binarysort.  Note that when k=1, this is roughly the same as an
   ordinary quicksort using a random pivot, and when k=2 this is roughly
   a median-of-3 quicksort.  From that view, using k ~= lg(n/ln(n)) makes
   this a "median of n/ln(n)" quicksort.  You can also view it as a kind
   of bucket sort, where 2**k-1 bucket boundaries are picked dynamically.

   The large number of samples makes a quadratic-time case almost
   impossible, and asymptotically drives the average-case number of
   compares from quicksort's 2 N ln N (or 12/7 N ln N for the median-of-
   3 variant) down to N lg N.

   We also play lots of low-level tricks to cut the number of compares.

   Very obscure:  To avoid using extra memory, the PPs are stored in the
   array and shuffled around as partitioning proceeds.  At the start of a
   partitioning step, we'll have 2**m-1 (for some m) PPs in sorted order,
   adjacent (either on the left or the right!) to a chunk of X elements
   that are to be partitioned: P X or X P.  In either case we need to
   shuffle things *in place* so that the 2**(m-1) smaller PPs are on the
   left, followed by the PP to be used for this step (that's the middle
   of the PPs), followed by X, followed by the 2**(m-1) larger PPs:
       P X or X P -> Psmall pivot X Plarge
   and the order of the PPs must not be altered.  It can take a while
   to realize this isn't trivial!  It can take even longer <wink> to
   understand why the simple code below works, using only 2**(m-1) swaps.
   The key is that the order of the X elements isn't necessarily
   preserved:  X can end up as some cyclic permutation of its original
   order.  That's OK, because X is unsorted anyway.  If the order of X
   had to be preserved too, the simplest method I know of using O(1)
   scratch storage requires len(X) + 2**(m-1) swaps, spread over 2 passes.
   Since len(X) is typically several times larger than 2**(m-1), that
   would slow things down.
*/

struct SamplesortStackNode {
	/* Represents a slice of the array, from (& including) lo up
	   to (but excluding) hi.  "extra" additional & adjacent elements
	   are pre-selected pivots (PPs), spanning [lo-extra, lo) if
	   extra > 0, or [hi, hi-extra) if extra < 0.  The PPs are
	   already sorted, but nothing is known about the other elements
	   in [lo, hi). |extra| is always one less than a power of 2.
	   When extra is 0, we're out of PPs, and the slice must be
	   sorted by some other means. */
	PyObject **lo;
	PyObject **hi;
	int extra;
};

/* The number of PPs we want is 2**k - 1, where 2**k is as close to
   N / ln(N) as possible.  So k ~= lg(N / ln(N)).  Calling libm routines
   is undesirable, so cutoff values are canned in the "cutoff" table
   below:  cutoff[i] is the smallest N such that k == CUTOFFBASE + i. */
#define CUTOFFBASE 4
static long cutoff[] = {
	43,        /* smallest N such that k == 4 */
	106,       /* etc */
	250,
	576,
	1298,
	2885,
	6339,
	13805,
	29843,
	64116,
	137030,
	291554,
	617916,
	1305130,
	2748295,
	5771662,
	12091672,
	25276798,
	52734615,
	109820537,
	228324027,
	473977813,
	982548444,   /* smallest N such that k == 26 */
	2034159050   /* largest N that fits in signed 32-bit; k == 27 */
};

static int
samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare)
     /* compare -- comparison function object, or NULL for default */
{
	register PyObject **l, **r;
	register PyObject *tmp, *pivot;
	register int k;
	int n, extra, top, extraOnRight;
	struct SamplesortStackNode stack[STACKSIZE];

	assert(lo <= hi);
	n = hi - lo;
	if (n < MINSIZE)
		return binarysort(lo, hi, lo, compare);

	/* ----------------------------------------------------------
	 * Normal case setup: a large array without obvious pattern.
	 * --------------------------------------------------------*/

	/* extra := a power of 2 ~= n/ln(n), less 1.
	   First find the smallest extra s.t. n < cutoff[extra] */
	for (extra = 0;
	     extra < sizeof(cutoff) / sizeof(cutoff[0]);
	     ++extra) {
		if (n < cutoff[extra])
			break;
		/* note that if we fall out of the loop, the value of
		   extra still makes *sense*, but may be smaller than
		   we would like (but the array has more than ~= 2**31
		   elements in this case!) */
	}
	/* Now k == extra - 1 + CUTOFFBASE.  The smallest value k can
	   have is CUTOFFBASE-1, so
	   assert MINSIZE >= 2**(CUTOFFBASE-1) - 1 */
	extra = (1 << (extra - 1 + CUTOFFBASE)) - 1;
	/* assert extra > 0 and n >= extra */

	/* Swap that many values to the start of the array.  The
	   selection of elements is pseudo-random, but the same on
	   every run (this is intentional! timing algorithm changes is
	   a pain if timing varies across runs).  */
	{
		unsigned int seed = n / extra;  /* arbitrary */
		unsigned int i;
		for (i = 0; i < (unsigned)extra; ++i) {
			/* j := random int in [i, n) */
			unsigned int j;
			seed = seed * 69069 + 7;
			j = i + seed % (n - i);
			tmp = lo[i]; lo[i] = lo[j]; lo[j] = tmp;
		}
	}

	/* Recursively sort the preselected pivots. */
	if (samplesortslice(lo, lo + extra, compare) < 0)
		goto fail;

	top = 0;          /* index of available stack slot */
	lo += extra;      /* point to first unknown */
	extraOnRight = 0; /* the PPs are at the left end */

	/* ----------------------------------------------------------
	 * Partition [lo, hi), and repeat until out of work.
	 * --------------------------------------------------------*/
	for (;;) {
		assert(lo <= hi);
		n = hi - lo;

		/* We may not want, or may not be able, to partition:
		   If n is small, it's quicker to insert.
		   If extra is 0, we're out of pivots, and *must* use
		   another method.
		*/
		if (n < MINPARTITIONSIZE || extra == 0) {
			if (n >= MINSIZE) {
				assert(extra == 0);
				/* This is rare, since the average size
				   of a final block is only about
				   ln(original n). */
				if (samplesortslice(lo, hi, compare) < 0)
					goto fail;
			}
			else {
				/* Binary insertion should be quicker,
				   and we can take advantage of the PPs
				   already being sorted. */
				if (extraOnRight && extra) {
					/* swap the PPs to the left end */
					k = extra;
					do {
						tmp = *lo;
						*lo = *hi;
						*hi = tmp;
						++lo; ++hi;
					} while (--k);
				}
				if (binarysort(lo - extra, hi, lo,
					       compare) < 0)
					goto fail;
			}

			/* Find another slice to work on. */
			if (--top < 0)
				break;   /* no more -- done! */
			lo = stack[top].lo;
			hi = stack[top].hi;
			extra = stack[top].extra;
			extraOnRight = 0;
			if (extra < 0) {
				extraOnRight = 1;
				extra = -extra;
			}
			continue;
		}

		/* Pretend the PPs are indexed 0, 1, ..., extra-1.
		   Then our preselected pivot is at (extra-1)/2, and we
		   want to move the PPs before that to the left end of
		   the slice, and the PPs after that to the right end.
		   The following section changes extra, lo, hi, and the
		   slice such that:
		   [lo-extra, lo) contains the smaller PPs.
		   *lo == our PP.
		   (lo, hi) contains the unknown elements.
		   [hi, hi+extra) contains the larger PPs.
		*/
		k = extra >>= 1;  /* num PPs to move */
		if (extraOnRight) {
			/* Swap the smaller PPs to the left end.
			   Note that this loop actually moves k+1 items:
			   the last is our PP */
			do {
				tmp = *lo; *lo = *hi; *hi = tmp;
				++lo; ++hi;
			} while (k--);
		}
		else {
			/* Swap the larger PPs to the right end. */
			while (k--) {
				--lo; --hi;
				tmp = *lo; *lo = *hi; *hi = tmp;
			}
		}
		--lo;   /* *lo is now our PP */
		pivot = *lo;

		/* Now an almost-ordinary quicksort partition step.
		   Note that most of the time is spent here!
		   Only odd thing is that we partition into < and >=,
		   instead of the usual <= and >=.  This helps when
		   there are lots of duplicates of different values,
		   because it eventually tends to make subfiles
		   "pure" (all duplicates), and we special-case for
		   duplicates later. */
		l = lo + 1;
		r = hi - 1;
		assert(lo < l && l < r && r < hi);

		do {
			/* slide l right, looking for key >= pivot */
			do {
				IFLT(*l, pivot)
					++l;
				else
					break;
			} while (l < r);

			/* slide r left, looking for key < pivot */
			while (l < r) {
				register PyObject *rval = *r--;
				IFLT(rval, pivot) {
					/* swap and advance */
					r[1] = *l;
					*l++ = rval;
					break;
				}
			}

		} while (l < r);

		assert(lo < r && r <= l && l < hi);
		/* everything to the left of l is < pivot, and
		   everything to the right of r is >= pivot */

		if (l == r) {
			IFLT(*r, pivot)
				++l;
			else
				--r;
		}
		assert(lo <= r && r+1 == l && l <= hi);
		/* assert r == lo or a[r] < pivot */
		assert(*lo == pivot);
		/* assert l == hi or a[l] >= pivot */
		/* Swap the pivot into "the middle", so we can henceforth
		   ignore it. */
		*lo = *r;
		*r = pivot;

		/* The following is true now, & will be preserved:
		   All in [lo,r) are < pivot
		   All in [r,l) == pivot (& so can be ignored)
		   All in [l,hi) are >= pivot */

		/* Check for duplicates of the pivot.  One compare is
		   wasted if there are no duplicates, but can win big
		   when there are.
		   Tricky: we're sticking to "<" compares, so deduce
		   equality indirectly.  We know pivot <= *l, so they're
		   equal iff not pivot < *l.
		*/
		while (l < hi) {
			/* pivot <= *l known */
			IFLT(pivot, *l)
				break;
			else
				/* <= and not < implies == */
				++l;
		}

		assert(lo <= r && r < l && l <= hi);
		/* Partitions are [lo, r) and [l, hi)
		   :ush fattest first; remember we still have extra PPs
		   to the left of the left chunk and to the right of
		   the right chunk! */
		assert(top < STACKSIZE);
		if (r - lo <= hi - l) {
			/* second is bigger */
			stack[top].lo = l;
			stack[top].hi = hi;
			stack[top].extra = -extra;
			hi = r;
			extraOnRight = 0;
		}
		else {
			/* first is bigger */
			stack[top].lo = lo;
			stack[top].hi = r;
			stack[top].extra = extra;
			lo = l;
			extraOnRight = 1;
		}
		++top;

	}   /* end of partitioning loop */

	return 0;

 fail:
	return -1;
}

static PyTypeObject immutable_list_type;

static PyObject *
listsort(PyListObject *self, PyObject *args)
{
	int k;
	PyObject *compare = NULL;
	PyObject **hi, **p;
	PyTypeObject *savetype;

	if (args != NULL) {
		if (!PyArg_ParseTuple(args, "|O:sort", &compare))
			return NULL;
	}

	savetype = self->ob_type;
	if (self->ob_size < 2) {
		k = 0;
		goto done;
	}

	self->ob_type = &immutable_list_type;
	hi = self->ob_item + self->ob_size;

	/* Set p to the largest value such that [lo, p) is sorted.
	   This catches the already-sorted case, the all-the-same
	   case, and the appended-a-few-elements-to-a-sorted-list case.
	   If the array is unsorted, we're very likely to get out of
	   the loop fast, so the test is cheap if it doesn't pay off.
	*/
	for (p = self->ob_item + 1; p < hi; ++p) {
		IFLT(*p, *(p-1))
			break;
	}
	/* [lo, p) is sorted, [p, hi) unknown.  Get out cheap if there are
	   few unknowns, or few elements in total. */
	if (hi - p <= MAXMERGE || self->ob_size < MINSIZE) {
		k = binarysort(self->ob_item, hi, p, compare);
		goto done;
	}

	/* Check for the array already being reverse-sorted, or that with
	   a few elements tacked on to the end. */
	for (p = self->ob_item + 1; p < hi; ++p) {
		IFLT(*(p-1), *p)
			break;
	}
	/* [lo, p) is reverse-sorted, [p, hi) unknown. */
	if (hi - p <= MAXMERGE) {
		/* Reverse the reversed prefix, then insert the tail */
		reverse_slice(self->ob_item, p);
		k = binarysort(self->ob_item, hi, p, compare);
		goto done;
	}

	/* A large array without obvious pattern. */
	k = samplesortslice(self->ob_item, hi, compare);

done: /* The IFLT macro requires a label named "fail". */;
fail:
 	self->ob_type = savetype;
	if (k >= 0) {
		Py_INCREF(Py_None);
		return Py_None;
	}
	else
		return NULL;
}

#undef IFLT

int
PyList_Sort(PyObject *v)
{
	if (v == NULL || !PyList_Check(v)) {
		PyErr_BadInternalCall();
		return -1;
	}
	v = listsort((PyListObject *)v, (PyObject *)NULL);
	if (v == NULL)
		return -1;
	Py_DECREF(v);
	return 0;
}

static PyObject *
listreverse(PyListObject *self)
{
	if (self->ob_size > 1)
		reverse_slice(self->ob_item, self->ob_item + self->ob_size);
	Py_INCREF(Py_None);
	return Py_None;
}

int
PyList_Reverse(PyObject *v)
{
	if (v == NULL || !PyList_Check(v)) {
		PyErr_BadInternalCall();
		return -1;
	}
	listreverse((PyListObject *)v);
	return 0;
}

PyObject *
PyList_AsTuple(PyObject *v)
{
	PyObject *w;
	PyObject **p;
	int n;
	if (v == NULL || !PyList_Check(v)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	n = ((PyListObject *)v)->ob_size;
	w = PyTuple_New(n);
	if (w == NULL)
		return NULL;
	p = ((PyTupleObject *)w)->ob_item;
	memcpy((void *)p,
	       (void *)((PyListObject *)v)->ob_item,
	       n*sizeof(PyObject *));
	while (--n >= 0) {
		Py_INCREF(*p);
		p++;
	}
	return w;
}

static PyObject *
listindex(PyListObject *self, PyObject *v)
{
	int i;

	for (i = 0; i < self->ob_size; i++) {
		int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
		if (cmp > 0)
			return PyInt_FromLong((long)i);
		else if (cmp < 0)
			return NULL;
	}
	PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
	return NULL;
}

static PyObject *
listcount(PyListObject *self, PyObject *v)
{
	int count = 0;
	int i;

	for (i = 0; i < self->ob_size; i++) {
		int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
		if (cmp > 0)
			count++;
		else if (cmp < 0)
			return NULL;
	}
	return PyInt_FromLong((long)count);
}

static PyObject *
listremove(PyListObject *self, PyObject *v)
{
	int i;

	for (i = 0; i < self->ob_size; i++) {
		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)
				return NULL;
			Py_INCREF(Py_None);
			return Py_None;
		}
		else if (cmp < 0)
			return NULL;
	}
	PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
	return NULL;
}

static int
list_traverse(PyListObject *o, visitproc visit, void *arg)
{
	int i, err;
	PyObject *x;

	for (i = o->ob_size; --i >= 0; ) {
		x = o->ob_item[i];
		if (x != NULL) {
			err = visit(x, arg);
			if (err)
				return err;
		}
	}
	return 0;
}

static int
list_clear(PyListObject *lp)
{
	(void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
	return 0;
}

static PyObject *
list_richcompare(PyObject *v, PyObject *w, int op)
{
	PyListObject *vl, *wl;
	int i;

	if (!PyList_Check(v) || !PyList_Check(w)) {
		Py_INCREF(Py_NotImplemented);
		return Py_NotImplemented;
	}

	vl = (PyListObject *)v;
	wl = (PyListObject *)w;

	if (vl->ob_size != wl->ob_size && (op == Py_EQ || op == Py_NE)) {
		/* Shortcut: if the lengths differ, the lists differ */
		PyObject *res;
		if (op == Py_EQ)
			res = Py_False;
		else
			res = Py_True;
		Py_INCREF(res);
		return res;
	}

	/* Search for the first index where items are different */
	for (i = 0; i < vl->ob_size && i < wl->ob_size; i++) {
		int k = PyObject_RichCompareBool(vl->ob_item[i],
						 wl->ob_item[i], Py_EQ);
		if (k < 0)
			return NULL;
		if (!k)
			break;
	}

	if (i >= vl->ob_size || i >= wl->ob_size) {
		/* No more items to compare -- compare sizes */
		int vs = vl->ob_size;
		int ws = wl->ob_size;
		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_INCREF(Py_False);
		return Py_False;
	}
	if (op == Py_NE) {
		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);
}

/* Adapted from newer code by Tim */
static int
list_fill(PyListObject *result, PyObject *v)
{
	PyObject *it;      /* iter(v) */
	int n;		   /* guess for result list size */
	int i;

	n = result->ob_size;

	/* Special-case list(a_list), for speed. */
	if (PyList_Check(v)) {
		if (v == (PyObject *)result)
			return 0; /* source is destination, we're done */
		return list_ass_slice(result, 0, n, v);
	}

	/* Empty previous contents */
	if (n != 0) {
		if (list_ass_slice(result, 0, n, (PyObject *)NULL) != 0)
			return -1;
	}

	/* Get iterator.  There may be some low-level efficiency to be gained
	 * by caching the tp_iternext slot instead of using PyIter_Next()
	 * later, but premature optimization is the root etc.
	 */
	it = PyObject_GetIter(v);
	if (it == NULL)
		return -1;

	/* Guess a result list size. */
	n = -1;	 /* unknown */
	if (PySequence_Check(v) &&
	    v->ob_type->tp_as_sequence->sq_length) {
		n = PySequence_Size(v);
		if (n < 0)
			PyErr_Clear();
	}
	if (n < 0)
		n = 8;	/* arbitrary */
	NRESIZE(result->ob_item, PyObject*, n);
	if (result->ob_item == NULL) {
		PyErr_NoMemory();
		goto error;
	}
	memset(result->ob_item, 0, sizeof(*result->ob_item) * n);
	result->ob_size = n;

	/* Run iterator to exhaustion. */
	for (i = 0; ; i++) {
		PyObject *item = PyIter_Next(it);
		if (item == NULL) {
			if (PyErr_Occurred())
				goto error;
			break;
		}
		if (i < n)
			PyList_SET_ITEM(result, i, item); /* steals ref */
		else {
			int status = ins1(result, result->ob_size, 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 (i < n && result != NULL) {
		if (list_ass_slice(result, i, n, (PyObject *)NULL) != 0)
			goto error;
	}
	Py_DECREF(it);
	return 0;

  error:
	Py_DECREF(it);
	return -1;
}

static int
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;
	if (arg != NULL)
		return list_fill(self, arg);
	if (self->ob_size > 0)
		return list_ass_slice(self, 0, self->ob_size, (PyObject*)NULL);
	return 0;
}

static long
list_nohash(PyObject *self)
{
	PyErr_SetString(PyExc_TypeError, "list objects are unhashable");
	return -1;
}

PyDoc_STRVAR(append_doc,
"L.append(object) -- append object to end");
PyDoc_STRVAR(extend_doc,
"L.extend(list) -- extend list by appending list elements");
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)");
PyDoc_STRVAR(remove_doc,
"L.remove(value) -- remove first occurrence of value");
PyDoc_STRVAR(index_doc,
"L.index(value) -> integer -- return index of first occurrence of value");
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([cmpfunc]) -- sort *IN PLACE*; if given, cmpfunc(x, y) -> -1, 0, 1");

static PyMethodDef list_methods[] = {
	{"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_O, index_doc},
	{"count",	(PyCFunction)listcount,   METH_O, count_doc},
	{"reverse",	(PyCFunction)listreverse, METH_NOARGS, reverse_doc},
	{"sort",	(PyCFunction)listsort, 	  METH_VARARGS, sort_doc},
	{NULL,		NULL}		/* sentinel */
};

static PySequenceMethods list_as_sequence = {
	(inquiry)list_length,			/* sq_length */
	(binaryfunc)list_concat,		/* sq_concat */
	(intargfunc)list_repeat,		/* sq_repeat */
	(intargfunc)list_item,			/* sq_item */
	(intintargfunc)list_slice,		/* sq_slice */
	(intobjargproc)list_ass_item,		/* sq_ass_item */
	(intintobjargproc)list_ass_slice,	/* sq_ass_slice */
	(objobjproc)list_contains,		/* sq_contains */
	(binaryfunc)list_inplace_concat,	/* sq_inplace_concat */
	(intargfunc)list_inplace_repeat,	/* sq_inplace_repeat */
};

PyDoc_STRVAR(list_doc,
"list() -> new list\n"
"list(sequence) -> new list initialized from sequence's items");

static PyObject *list_iter(PyObject *seq);

static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{
	if (PyInt_Check(item)) {
		long i = PyInt_AS_LONG(item);
		if (i < 0)
			i += PyList_GET_SIZE(self);
		return list_item(self, i);
	}
	else if (PyLong_Check(item)) {
		long i = PyLong_AsLong(item);
		if (i == -1 && PyErr_Occurred())
			return NULL;
		if (i < 0)
			i += PyList_GET_SIZE(self);
		return list_item(self, i);
	}
	else if (PySlice_Check(item)) {
		int start, stop, step, slicelength, cur, i;
		PyObject* result;
		PyObject* it;

		if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
				 &start, &stop, &step, &slicelength) < 0) {
			return NULL;
		}

		if (slicelength <= 0) {
			return PyList_New(0);
		}
		else {
			result = PyList_New(slicelength);
			if (!result) return NULL;

			for (cur = start, i = 0; i < slicelength;
			     cur += step, i++) {
				it = PyList_GET_ITEM(self, cur);
				Py_INCREF(it);
				PyList_SET_ITEM(result, i, it);
			}

			return result;
		}
	}
	else {
		PyErr_SetString(PyExc_TypeError,
				"list indices must be integers");
		return NULL;
	}
}

static int
list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
{
	if (PyInt_Check(item)) {
		long i = PyInt_AS_LONG(item);
		if (i < 0)
			i += PyList_GET_SIZE(self);
		return list_ass_item(self, i, value);
	}
	else if (PyLong_Check(item)) {
		long i = PyLong_AsLong(item);
		if (i == -1 && PyErr_Occurred())
			return -1;
		if (i < 0)
			i += PyList_GET_SIZE(self);
		return list_ass_item(self, i, value);
	}
	else if (PySlice_Check(item)) {
		int start, stop, step, slicelength;

		if (PySlice_GetIndicesEx((PySliceObject*)item, self->ob_size,
				 &start, &stop, &step, &slicelength) < 0) {
			return -1;
		}

		/* treat L[slice(a,b)] = v _exactly_ like L[a:b] = v */
		if (step == 1 && ((PySliceObject*)item)->step == Py_None)
			return list_ass_slice(self, start, stop, value);

		if (value == NULL) {
			/* delete slice */
			PyObject **garbage, **it;
			int cur, i, j;

			if (slicelength <= 0)
				return 0;

			if (step < 0) {
				stop = start + 1;
				start = stop + step*(slicelength - 1) - 1;
				step = -step;
			}

			garbage = (PyObject**)
				PyMem_MALLOC(slicelength*sizeof(PyObject*));

			/* drawing pictures might help
			   understand these for loops */
			for (cur = start, i = 0;
			     cur < stop;
			     cur += step, i++)
			{
				garbage[i] = PyList_GET_ITEM(self, cur);

				for (j = 0; j < step; j++) {
					PyList_SET_ITEM(self, cur + j - i,
						PyList_GET_ITEM(self,
								cur + j + 1));
				}
			}
			for (cur = start + slicelength*step + 1;
			     cur < self->ob_size; cur++) {
				PyList_SET_ITEM(self, cur - slicelength,
						PyList_GET_ITEM(self, cur));
			}
			self->ob_size -= slicelength;
			it = self->ob_item;
			NRESIZE(it, PyObject*, self->ob_size);
			self->ob_item = it;

			for (i = 0; i < slicelength; i++) {
				Py_DECREF(garbage[i]);
			}
			PyMem_FREE(garbage);

			return 0;
		}
		else {
			/* assign slice */
			PyObject **garbage, *ins;
			int cur, i;

			if (!PyList_Check(value)) {
				PyErr_Format(PyExc_TypeError,
			     "must assign list (not \"%.200s\") to slice",
					     value->ob_type->tp_name);
				return -1;
			}

			if (PyList_GET_SIZE(value) != slicelength) {
				PyErr_Format(PyExc_ValueError,
            "attempt to assign list of size %d to extended slice of size %d",
					     PyList_Size(value), slicelength);
				return -1;
			}

			if (!slicelength)
				return 0;

			/* protect against a[::-1] = a */
			if (self == (PyListObject*)value) {
				value = list_slice((PyListObject*)value, 0,
						   PyList_GET_SIZE(value));
			}
			else {
				Py_INCREF(value);
			}

			garbage = (PyObject**)
				PyMem_MALLOC(slicelength*sizeof(PyObject*));

			for (cur = start, i = 0; i < slicelength;
			     cur += step, i++) {
				garbage[i] = PyList_GET_ITEM(self, cur);

				ins = PyList_GET_ITEM(value, i);
				Py_INCREF(ins);
				PyList_SET_ITEM(self, cur, ins);
			}

			for (i = 0; i < slicelength; i++) {
				Py_DECREF(garbage[i]);
			}

			PyMem_FREE(garbage);
			Py_DECREF(value);

			return 0;
		}
	}
	else {
		PyErr_SetString(PyExc_TypeError,
				"list indices must be integers");
		return -1;
	}
}

static PyMappingMethods list_as_mapping = {
	(inquiry)list_length,
	(binaryfunc)list_subscript,
	(objobjargproc)list_ass_subscript
};

PyTypeObject PyList_Type = {
	PyObject_HEAD_INIT(&PyType_Type)
	0,
	"list",
	sizeof(PyListObject),
	0,
	(destructor)list_dealloc,		/* tp_dealloc */
	(printfunc)list_print,			/* tp_print */
	0,					/* tp_getattr */
	0,					/* tp_setattr */
	0,					/* tp_compare */
	(reprfunc)list_repr,			/* tp_repr */
	0,					/* tp_as_number */
	&list_as_sequence,			/* tp_as_sequence */
	&list_as_mapping,			/* tp_as_mapping */
	list_nohash,				/* 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,		/* tp_flags */
 	list_doc,				/* tp_doc */
 	(traverseproc)list_traverse,		/* tp_traverse */
 	(inquiry)list_clear,			/* tp_clear */
	list_richcompare,			/* tp_richcompare */
	0,					/* tp_weaklistoffset */
	list_iter,				/* tp_iter */
	0,					/* tp_iternext */
	list_methods,				/* tp_methods */
	0,					/* tp_members */
	0,					/* tp_getset */
	0,					/* tp_base */
	0,					/* tp_dict */
	0,					/* tp_descr_get */
	0,					/* tp_descr_set */
	0,					/* tp_dictoffset */
	(initproc)list_init,			/* tp_init */
	PyType_GenericAlloc,			/* tp_alloc */
	PyType_GenericNew,			/* tp_new */
	PyObject_GC_Del,			/* tp_free */
};


/* During a sort, we really can't have anyone modifying the list; it could
   cause core dumps.  Thus, we substitute a dummy type that raises an
   explanatory exception when a modifying operation is used.  Caveat:
   comparisons may behave differently; but I guess it's a bad idea anyway to
   compare a list that's being sorted... */

static PyObject *
immutable_list_op(void)
{
	PyErr_SetString(PyExc_TypeError,
			"a list cannot be modified while it is being sorted");
	return NULL;
}

static PyMethodDef immutable_list_methods[] = {
	{"append",	(PyCFunction)immutable_list_op, METH_VARARGS},
	{"insert",	(PyCFunction)immutable_list_op, METH_VARARGS},
	{"extend",      (PyCFunction)immutable_list_op,  METH_O},
	{"pop",		(PyCFunction)immutable_list_op, METH_VARARGS},
	{"remove",	(PyCFunction)immutable_list_op, METH_VARARGS},
	{"index",	(PyCFunction)listindex,         METH_O},
	{"count",	(PyCFunction)listcount,         METH_O},
	{"reverse",	(PyCFunction)immutable_list_op, METH_VARARGS},
	{"sort",	(PyCFunction)immutable_list_op, METH_VARARGS},
	{NULL,		NULL}		/* sentinel */
};

static int
immutable_list_ass(void)
{
	immutable_list_op();
	return -1;
}

static PySequenceMethods immutable_list_as_sequence = {
	(inquiry)list_length,			/* sq_length */
	(binaryfunc)list_concat,		/* sq_concat */
	(intargfunc)list_repeat,		/* sq_repeat */
	(intargfunc)list_item,			/* sq_item */
	(intintargfunc)list_slice,		/* sq_slice */
	(intobjargproc)immutable_list_ass,	/* sq_ass_item */
	(intintobjargproc)immutable_list_ass,	/* sq_ass_slice */
	(objobjproc)list_contains,		/* sq_contains */
};

static PyTypeObject immutable_list_type = {
	PyObject_HEAD_INIT(&PyType_Type)
	0,
	"list (immutable, during sort)",
	sizeof(PyListObject),
	0,
	0, /* Cannot happen */			/* tp_dealloc */
	(printfunc)list_print,			/* tp_print */
	0,					/* tp_getattr */
	0,					/* tp_setattr */
	0, /* Won't be called */		/* tp_compare */
	(reprfunc)list_repr,			/* tp_repr */
	0,					/* tp_as_number */
	&immutable_list_as_sequence,		/* tp_as_sequence */
	0,					/* tp_as_mapping */
	list_nohash,				/* 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,/* tp_flags */
 	list_doc,				/* tp_doc */
 	(traverseproc)list_traverse,		/* tp_traverse */
	0,					/* tp_clear */
	list_richcompare,			/* tp_richcompare */
	0,					/* tp_weaklistoffset */
	0,					/* tp_iter */
	0,					/* tp_iternext */
	immutable_list_methods,			/* tp_methods */
	0,					/* tp_members */
	0,					/* tp_getset */
	0,					/* tp_base */
	0,					/* tp_dict */
	0,					/* tp_descr_get */
	0,					/* tp_descr_set */
	0,					/* tp_init */
	/* NOTE: This is *not* the standard list_type struct! */
};


/*********************** List Iterator **************************/

typedef struct {
	PyObject_HEAD
	long it_index;
	PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
} listiterobject;

PyTypeObject PyListIter_Type;

static PyObject *
list_iter(PyObject *seq)
{
	listiterobject *it;

	if (!PyList_Check(seq)) {
		PyErr_BadInternalCall();
		return NULL;
	}
	it = PyObject_GC_New(listiterobject, &PyListIter_Type);
	if (it == NULL)
		return NULL;
	it->it_index = 0;
	Py_INCREF(seq);
	it->it_seq = (PyListObject *)seq;
	_PyObject_GC_TRACK(it);
	return (PyObject *)it;
}

static void
listiter_dealloc(listiterobject *it)
{
	_PyObject_GC_UNTRACK(it);
	Py_XDECREF(it->it_seq);
	PyObject_GC_Del(it);
}

static int
listiter_traverse(listiterobject *it, visitproc visit, void *arg)
{
	if (it->it_seq == NULL)
		return 0;
	return visit((PyObject *)it->it_seq, arg);
}


static PyObject *
listiter_getiter(PyObject *it)
{
	Py_INCREF(it);
	return it;
}

static PyObject *
listiter_next(listiterobject *it)
{
	PyListObject *seq;
	PyObject *item;

	assert(it != NULL);
	seq = it->it_seq;
	if (seq == NULL)
		return NULL;
	assert(PyList_Check(seq));

	if (it->it_index < PyList_GET_SIZE(seq)) {
		item = PyList_GET_ITEM(seq, it->it_index);
		++it->it_index;
		Py_INCREF(item);
		return item;
	}

	Py_DECREF(seq);
	it->it_seq = NULL;
	return NULL;
}

PyTypeObject PyListIter_Type = {
	PyObject_HEAD_INIT(&PyType_Type)
	0,					/* ob_size */
	"listiterator",				/* tp_name */
	sizeof(listiterobject),			/* tp_basicsize */
	0,					/* tp_itemsize */
	/* methods */
	(destructor)listiter_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_GC,/* tp_flags */
	0,					/* tp_doc */
	(traverseproc)listiter_traverse,	/* tp_traverse */
	0,					/* tp_clear */
	0,					/* tp_richcompare */
	0,					/* tp_weaklistoffset */
	(getiterfunc)listiter_getiter,		/* tp_iter */
	(iternextfunc)listiter_next,		/* tp_iternext */
	0,					/* tp_methods */
	0,					/* tp_members */
	0,					/* tp_getset */
	0,					/* tp_base */
	0,					/* tp_dict */
	0,					/* tp_descr_get */
	0,					/* tp_descr_set */
};