/* Tuple object implementation */

#include "Python.h"

/* Speed optimization to avoid frequent malloc/free of small tuples */

#ifndef PyTuple_MAXSAVESIZE

#define PyTuple_MAXSAVESIZE	20  /* Largest tuple to save on free list */

#endif

#ifndef PyTuple_MAXFREELIST 

#define PyTuple_MAXFREELIST  2000  /* Maximum number of tuples of each size to save */

#endif

#if PyTuple_MAXSAVESIZE > 0

/* Entries 1 up to PyTuple_MAXSAVESIZE are free lists, entry 0 is the empty

   tuple () of which at most one instance will be allocated.

*/

static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];

static int numfree[PyTuple_MAXSAVESIZE];

#endif

#ifdef COUNT_ALLOCS

int fast_tuple_allocs;

int tuple_zero_allocs;

#endif

PyObject *

PyTuple_New(register Py_ssize_t size)

{

	register PyTupleObject *op;

	Py_ssize_t i;

	if (size < 0) {

		PyErr_BadInternalCall();

		return NULL;

	}

#if PyTuple_MAXSAVESIZE > 0

	if (size == 0 && free_list[0]) {

		op = free_list[0];

		Py_INCREF(op);

#ifdef COUNT_ALLOCS

		tuple_zero_allocs++;

#endif

		return (PyObject *) op;

	}

	if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {

		free_list[size] = (PyTupleObject *) op->ob_item[0];

		numfree[size]--;

#ifdef COUNT_ALLOCS

		fast_tuple_allocs++;

#endif

		/* Inline PyObject_InitVar */

#ifdef Py_TRACE_REFS

		Py_SIZE(op) = size;

		Py_TYPE(op) = &PyTuple_Type;

#endif

		_Py_NewReference((PyObject *)op);

	}

	else

#endif

	{

		Py_ssize_t nbytes = size * sizeof(PyObject *);

		/* Check for overflow */

		if (nbytes / sizeof(PyObject *) != (size_t)size ||

		    (nbytes > PY_SSIZE_T_MAX - sizeof(PyTupleObject) - sizeof(PyObject *)))

		{

			return PyErr_NoMemory();

		}

		nbytes += sizeof(PyTupleObject) - sizeof(PyObject *);

		op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);

		if (op == NULL)

			return NULL;

	}

	for (i=0; i < size; i++)

		op->ob_item[i] = NULL;

#if PyTuple_MAXSAVESIZE > 0

	if (size == 0) {

		free_list[0] = op;

		++numfree[0];

		Py_INCREF(op);	/* extra INCREF so that this is never freed */

	}

#endif

	_PyObject_GC_TRACK(op);

	return (PyObject *) op;

}

Py_ssize_t

PyTuple_Size(register PyObject *op)

{

	if (!PyTuple_Check(op)) {

		PyErr_BadInternalCall();

		return -1;

	}

	else

		return Py_SIZE(op);

}

PyObject *

PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)

{

	if (!PyTuple_Check(op)) {

		PyErr_BadInternalCall();

		return NULL;

	}

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

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

		return NULL;

	}

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

}

int

PyTuple_SetItem(register PyObject *op, register Py_ssize_t i, PyObject *newitem)

{

	register PyObject *olditem;

	register PyObject **p;

	if (!PyTuple_Check(op) || op->ob_refcnt != 1) {

		Py_XDECREF(newitem);

		PyErr_BadInternalCall();

		return -1;

	}

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

		Py_XDECREF(newitem);

		PyErr_SetString(PyExc_IndexError,

				"tuple assignment index out of range");

		return -1;

	}

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

	olditem = *p;

	*p = newitem;

	Py_XDECREF(olditem);

	return 0;

}

PyObject *

PyTuple_Pack(Py_ssize_t n, ...)

{

	Py_ssize_t i;

	PyObject *o;

	PyObject *result;

	PyObject **items;

	va_list vargs;

	va_start(vargs, n);

	result = PyTuple_New(n);

	if (result == NULL)

		return NULL;

	items = ((PyTupleObject *)result)->ob_item;

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

		o = va_arg(vargs, PyObject *);

		Py_INCREF(o);

		items[i] = o;

	}

	va_end(vargs);

	return result;

}

/* Methods */

static void

tupledealloc(register PyTupleObject *op)

{

	register Py_ssize_t i;

	register Py_ssize_t len =  Py_SIZE(op);

	PyObject_GC_UnTrack(op);

	Py_TRASHCAN_SAFE_BEGIN(op)

	if (len > 0) {

		i = len;

		while (--i >= 0)

			Py_XDECREF(op->ob_item[i]);

#if PyTuple_MAXSAVESIZE > 0

		if (len < PyTuple_MAXSAVESIZE &&

		    numfree[len] < PyTuple_MAXFREELIST &&

		    Py_TYPE(op) == &PyTuple_Type)

		{

			op->ob_item[0] = (PyObject *) free_list[len];

			numfree[len]++;

			free_list[len] = op;

			goto done; /* return */

		}

#endif

	}

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

done:

	Py_TRASHCAN_SAFE_END(op)

}

static int

tupleprint(PyTupleObject *op, FILE *fp, int flags)

{

	Py_ssize_t i;

	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)

			return -1;

	}

	i = Py_SIZE(op);

	Py_BEGIN_ALLOW_THREADS

	if (i == 1)

		fprintf(fp, ",");

	fprintf(fp, ")");

	Py_END_ALLOW_THREADS

	return 0;

}

static PyObject *

tuplerepr(PyTupleObject *v)

{

	Py_ssize_t i, n;

	PyObject *s, *temp;

	PyObject *pieces, *result = NULL;

	n = Py_SIZE(v);

	if (n == 0)

		return PyString_FromString("()");

	/* While not mutable, it is still possible to end up with a cycle in a

	   tuple through an object that stores itself within a tuple (and thus

	   infinitely asks for the repr of itself). This should only be

	   possible within a type. */

	i = Py_ReprEnter((PyObject *)v);

	if (i != 0) {

		return i > 0 ? PyString_FromString("(...)") : NULL;

	}

	pieces = PyTuple_New(n);

	if (pieces == NULL)

		return NULL;

	/* Do repr() on each element. */

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

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

			goto Done;

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

		Py_LeaveRecursiveCall();

		if (s == NULL)

			goto Done;

		PyTuple_SET_ITEM(pieces, i, s);

	}

	/* Add "()" decorations to the first and last items. */

	assert(n > 0);

	s = PyString_FromString("(");

	if (s == NULL)

		goto Done;

	temp = PyTuple_GET_ITEM(pieces, 0);

	PyString_ConcatAndDel(&s, temp);

	PyTuple_SET_ITEM(pieces, 0, s);

	if (s == NULL)

		goto Done;

	s = PyString_FromString(n == 1 ? ",)" : ")");

	if (s == NULL)

		goto Done;

	temp = PyTuple_GET_ITEM(pieces, n-1);

	PyString_ConcatAndDel(&temp, s);

	PyTuple_SET_ITEM(pieces, n-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_DECREF(pieces);

	Py_ReprLeave((PyObject *)v);

	return result;

}

/* The addend 82520, was selected from the range(0, 1000000) for 

   generating the greatest number of prime multipliers for tuples 

   upto length eight:

     1082527, 1165049, 1082531, 1165057, 1247581, 1330103, 1082533, 

     1330111, 1412633, 1165069, 1247599, 1495177, 1577699

*/

static long

tuplehash(PyTupleObject *v)

{

	register long x, y;

	register Py_ssize_t len = Py_SIZE(v);

	register PyObject **p;

	long mult = 1000003L;

	x = 0x345678L;

	p = v->ob_item;

	while (--len >= 0) {

		y = PyObject_Hash(*p++);

		if (y == -1)

			return -1;

		x = (x ^ y) * mult;

		/* the cast might truncate len; that doesn't change hash stability */

		mult += (long)(82520L + len + len);

	}

	x += 97531L;

	if (x == -1)

		x = -2;

	return x;

}

static Py_ssize_t

tuplelength(PyTupleObject *a)

{

	return Py_SIZE(a);

}

static int

tuplecontains(PyTupleObject *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, PyTuple_GET_ITEM(a, i),

						   Py_EQ);

	return cmp;

}

static PyObject *

tupleitem(register PyTupleObject *a, register Py_ssize_t i)

{

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

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

		return NULL;

	}

	Py_INCREF(a->ob_item[i]);

	return a->ob_item[i];

}

static PyObject *

tupleslice(register PyTupleObject *a, register Py_ssize_t ilow, 

	   register Py_ssize_t ihigh)

{

	register PyTupleObject *np;

	PyObject **src, **dest;

	register Py_ssize_t i;

	Py_ssize_t len;

	if (ilow < 0)

		ilow = 0;

	if (ihigh > Py_SIZE(a))

		ihigh = Py_SIZE(a);

	if (ihigh < ilow)

		ihigh = ilow;

	if (ilow == 0 && ihigh == Py_SIZE(a) && PyTuple_CheckExact(a)) {

		Py_INCREF(a);

		return (PyObject *)a;

	}

	len = ihigh - ilow;

	np = (PyTupleObject *)PyTuple_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 *

PyTuple_GetSlice(PyObject *op, Py_ssize_t i, Py_ssize_t j)

{

	if (op == NULL || !PyTuple_Check(op)) {

		PyErr_BadInternalCall();

		return NULL;

	}

	return tupleslice((PyTupleObject *)op, i, j);

}

static PyObject *

tupleconcat(register PyTupleObject *a, register PyObject *bb)

{

	register Py_ssize_t size;

	register Py_ssize_t i;

	PyObject **src, **dest;

	PyTupleObject *np;

	if (!PyTuple_Check(bb)) {

		PyErr_Format(PyExc_TypeError,

       		     "can only concatenate tuple (not \"%.200s\") to tuple",

			     Py_TYPE(bb)->tp_name);

		return NULL;

	}

#define b ((PyTupleObject *)bb)

	size = Py_SIZE(a) + Py_SIZE(b);

	if (size < 0)

		return PyErr_NoMemory();

	np = (PyTupleObject *) PyTuple_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 *

tuplerepeat(PyTupleObject *a, Py_ssize_t n)

{

	Py_ssize_t i, j;

	Py_ssize_t size;

	PyTupleObject *np;

	PyObject **p, **items;

	if (n < 0)

		n = 0;

	if (Py_SIZE(a) == 0 || n == 1) {

		if (PyTuple_CheckExact(a)) {

			/* Since tuples are immutable, we can return a shared

			   copy in this case */

			Py_INCREF(a);

			return (PyObject *)a;

		}

		if (Py_SIZE(a) == 0)

			return PyTuple_New(0);

	}

	size = Py_SIZE(a) * n;

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

		return PyErr_NoMemory();

	np = (PyTupleObject *) PyTuple_New(size);

	if (np == NULL)

		return NULL;

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

tupleindex(PyTupleObject *self, PyObject *args)

{

	Py_ssize_t i, start=0, stop=Py_SIZE(self);

	PyObject *v;

	if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,

	                            _PyEval_SliceIndex, &start,

	                            _PyEval_SliceIndex, &stop))

		return NULL;

	if (start < 0) {

		start += Py_SIZE(self);

		if (start < 0)

			start = 0;

	}

	if (stop < 0) {

		stop += Py_SIZE(self);

		if (stop < 0)

			stop = 0;

	}

	for (i = start; i < stop && i < Py_SIZE(self); i++) {

		int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);

		if (cmp > 0)

			return PyInt_FromSsize_t(i);

		else if (cmp < 0)

			return NULL;

	}

	PyErr_SetString(PyExc_ValueError, "tuple.index(x): x not in list");

	return NULL;

}

static PyObject *

tuplecount(PyTupleObject *self, PyObject *v)

{

	Py_ssize_t count = 0;

	Py_ssize_t i;

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

		int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);

		if (cmp > 0)

			count++;

		else if (cmp < 0)

			return NULL;

	}

	return PyInt_FromSsize_t(count);

}

static int

tupletraverse(PyTupleObject *o, visitproc visit, void *arg)

{

	Py_ssize_t i;

	for (i = Py_SIZE(o); --i >= 0; )

		Py_VISIT(o->ob_item[i]);

	return 0;

}

static PyObject *

tuplerichcompare(PyObject *v, PyObject *w, int op)

{

	PyTupleObject *vt, *wt;

	Py_ssize_t i;

	Py_ssize_t vlen, wlen;

	if (!PyTuple_Check(v) || !PyTuple_Check(w)) {

		Py_INCREF(Py_NotImplemented);

		return Py_NotImplemented;

	}

	vt = (PyTupleObject *)v;