1 

     2 /* Tuple object implementation */

     3 

     4 #include "Python.h"

     5 

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

     7 #ifndef PyTuple_MAXSAVESIZE

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

     9 #endif

    10 #ifndef PyTuple_MAXFREELIST 

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

    12 #endif

    13 

    14 #if PyTuple_MAXSAVESIZE > 0

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

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

    17 */

    18 static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];

    19 static int numfree[PyTuple_MAXSAVESIZE];

    20 #endif

    21 #ifdef COUNT_ALLOCS

    22 int fast_tuple_allocs;

    23 int tuple_zero_allocs;

    24 #endif

    25 

    26 PyObject *

    27 PyTuple_New(register Py_ssize_t size)

    28 {

    29 	register PyTupleObject *op;

    30 	Py_ssize_t i;

    31 	if (size < 0) {

    32 		PyErr_BadInternalCall();

    33 		return NULL;

    34 	}

    35 #if PyTuple_MAXSAVESIZE > 0

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

    37 		op = free_list[0];

    38 		Py_INCREF(op);

    39 #ifdef COUNT_ALLOCS

    40 		tuple_zero_allocs++;

    41 #endif

    42 		return (PyObject *) op;

    43 	}

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

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

    46 		numfree[size]--;

    47 #ifdef COUNT_ALLOCS

    48 		fast_tuple_allocs++;

    49 #endif

    50 		/* Inline PyObject_InitVar */

    51 #ifdef Py_TRACE_REFS

    52 		Py_SIZE(op) = size;

    53 		Py_TYPE(op) = &PyTuple_Type;

    54 #endif

    55 		_Py_NewReference((PyObject *)op);

    56 	}

    57 	else

    58 #endif

    59 	{

    60 		Py_ssize_t nbytes = size * sizeof(PyObject *);

    61 		/* Check for overflow */

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

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

    64 		{

    65 			return PyErr_NoMemory();

    66 		}

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

    68 

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

    70 		if (op == NULL)

    71 			return NULL;

    72 	}

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

    74 		op->ob_item[i] = NULL;

    75 #if PyTuple_MAXSAVESIZE > 0

    76 	if (size == 0) {

    77 		free_list[0] = op;

    78 		++numfree[0];

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

    80 	}

    81 #endif

    82 	_PyObject_GC_TRACK(op);

    83 	return (PyObject *) op;

    84 }

    85 

    86 Py_ssize_t

    87 PyTuple_Size(register PyObject *op)

    88 {

    89 	if (!PyTuple_Check(op)) {

    90 		PyErr_BadInternalCall();

    91 		return -1;

    92 	}

    93 	else

    94 		return Py_SIZE(op);

    95 }

    96 

    97 PyObject *

    98 PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)

    99 {

   100 	if (!PyTuple_Check(op)) {

   101 		PyErr_BadInternalCall();

   102 		return NULL;

   103 	}

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

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

   106 		return NULL;

   107 	}

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

   109 }

   110 

   111 int

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

   113 {

   114 	register PyObject *olditem;

   115 	register PyObject **p;

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

   117 		Py_XDECREF(newitem);

   118 		PyErr_BadInternalCall();

   119 		return -1;

   120 	}

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

   122 		Py_XDECREF(newitem);

   123 		PyErr_SetString(PyExc_IndexError,

   124 				"tuple assignment index out of range");

   125 		return -1;

   126 	}

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

   128 	olditem = *p;

   129 	*p = newitem;

   130 	Py_XDECREF(olditem);

   131 	return 0;

   132 }

   133 

   134 PyObject *

   135 PyTuple_Pack(Py_ssize_t n, ...)

   136 {

   137 	Py_ssize_t i;

   138 	PyObject *o;

   139 	PyObject *result;

   140 	PyObject **items;

   141 	va_list vargs;

   142 

   143 	va_start(vargs, n);

   144 	result = PyTuple_New(n);

   145 	if (result == NULL)

   146 		return NULL;

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

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

   149 		o = va_arg(vargs, PyObject *);

   150 		Py_INCREF(o);

   151 		items[i] = o;

   152 	}

   153 	va_end(vargs);

   154 	return result;

   155 }

   156 

   157 

   158 /* Methods */

   159 

   160 static void

   161 tupledealloc(register PyTupleObject *op)

   162 {

   163 	register Py_ssize_t i;

   164 	register Py_ssize_t len =  Py_SIZE(op);

   165 	PyObject_GC_UnTrack(op);

   166 	Py_TRASHCAN_SAFE_BEGIN(op)

   167 	if (len > 0) {

   168 		i = len;

   169 		while (--i >= 0)

   170 			Py_XDECREF(op->ob_item[i]);

   171 #if PyTuple_MAXSAVESIZE > 0

   172 		if (len < PyTuple_MAXSAVESIZE &&

   173 		    numfree[len] < PyTuple_MAXFREELIST &&

   174 		    Py_TYPE(op) == &PyTuple_Type)

   175 		{

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

   177 			numfree[len]++;

   178 			free_list[len] = op;

   179 			goto done; /* return */

   180 		}

   181 #endif

   182 	}

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

   184 done:

   185 	Py_TRASHCAN_SAFE_END(op)

   186 }

   187 

   188 static int

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

   190 {

   191 	Py_ssize_t i;

   192 	Py_BEGIN_ALLOW_THREADS

   193 	fprintf(fp, "(");

   194 	Py_END_ALLOW_THREADS

   195 	for (i = 0; i < Py_SIZE(op); i++) {

   196 		if (i > 0) {

   197 			Py_BEGIN_ALLOW_THREADS

   198 			fprintf(fp, ", ");

   199 			Py_END_ALLOW_THREADS

   200 		}

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

   202 			return -1;

   203 	}

   204 	i = Py_SIZE(op);

   205 	Py_BEGIN_ALLOW_THREADS

   206 	if (i == 1)

   207 		fprintf(fp, ",");

   208 	fprintf(fp, ")");

   209 	Py_END_ALLOW_THREADS

   210 	return 0;

   211 }

   212 

   213 static PyObject *

   214 tuplerepr(PyTupleObject *v)

   215 {

   216 	Py_ssize_t i, n;

   217 	PyObject *s, *temp;

   218 	PyObject *pieces, *result = NULL;

   219 

   220 	n = Py_SIZE(v);

   221 	if (n == 0)

   222 		return PyString_FromString("()");

   223 

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

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

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

   227 	   possible within a type. */

   228 	i = Py_ReprEnter((PyObject *)v);

   229 	if (i != 0) {

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

   231 	}

   232 

   233 	pieces = PyTuple_New(n);

   234 	if (pieces == NULL)

   235 		return NULL;

   236 

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

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

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

   240 			goto Done;

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

   242 		Py_LeaveRecursiveCall();

   243 		if (s == NULL)

   244 			goto Done;

   245 		PyTuple_SET_ITEM(pieces, i, s);

   246 	}

   247 

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

   249 	assert(n > 0);

   250 	s = PyString_FromString("(");

   251 	if (s == NULL)

   252 		goto Done;

   253 	temp = PyTuple_GET_ITEM(pieces, 0);

   254 	PyString_ConcatAndDel(&s, temp);

   255 	PyTuple_SET_ITEM(pieces, 0, s);

   256 	if (s == NULL)

   257 		goto Done;

   258 

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

   260 	if (s == NULL)

   261 		goto Done;

   262 	temp = PyTuple_GET_ITEM(pieces, n-1);

   263 	PyString_ConcatAndDel(&temp, s);

   264 	PyTuple_SET_ITEM(pieces, n-1, temp);

   265 	if (temp == NULL)

   266 		goto Done;

   267 

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

   269 	s = PyString_FromString(", ");

   270 	if (s == NULL)

   271 		goto Done;

   272 	result = _PyString_Join(s, pieces);

   273 	Py_DECREF(s);	

   274 

   275 Done:

   276 	Py_DECREF(pieces);

   277 	Py_ReprLeave((PyObject *)v);

   278 	return result;

   279 }

   280 

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

   282    generating the greatest number of prime multipliers for tuples 

   283    upto length eight:

   284 

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

   286      1330111, 1412633, 1165069, 1247599, 1495177, 1577699

   287 */

   288 

   289 static long

   290 tuplehash(PyTupleObject *v)

   291 {

   292 	register long x, y;

   293 	register Py_ssize_t len = Py_SIZE(v);

   294 	register PyObject **p;

   295 	long mult = 1000003L;

   296 	x = 0x345678L;

   297 	p = v->ob_item;

   298 	while (--len >= 0) {

   299 		y = PyObject_Hash(*p++);

   300 		if (y == -1)

   301 			return -1;

   302 		x = (x ^ y) * mult;

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

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

   305 	}

   306 	x += 97531L;

   307 	if (x == -1)

   308 		x = -2;

   309 	return x;

   310 }

   311 

   312 static Py_ssize_t

   313 tuplelength(PyTupleObject *a)

   314 {

   315 	return Py_SIZE(a);

   316 }

   317 

   318 static int

   319 tuplecontains(PyTupleObject *a, PyObject *el)

   320 {

   321 	Py_ssize_t i;

   322 	int cmp;

   323 

   324 	for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)

   325 		cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),

   326 						   Py_EQ);

   327 	return cmp;

   328 }

   329 

   330 static PyObject *

   331 tupleitem(register PyTupleObject *a, register Py_ssize_t i)

   332 {

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

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

   335 		return NULL;

   336 	}

   337 	Py_INCREF(a->ob_item[i]);

   338 	return a->ob_item[i];

   339 }

   340 

   341 static PyObject *

   342 tupleslice(register PyTupleObject *a, register Py_ssize_t ilow, 

   343 	   register Py_ssize_t ihigh)

   344 {

   345 	register PyTupleObject *np;

   346 	PyObject **src, **dest;

   347 	register Py_ssize_t i;

   348 	Py_ssize_t len;

   349 	if (ilow < 0)

   350 		ilow = 0;

   351 	if (ihigh > Py_SIZE(a))

   352 		ihigh = Py_SIZE(a);

   353 	if (ihigh < ilow)

   354 		ihigh = ilow;

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

   356 		Py_INCREF(a);

   357 		return (PyObject *)a;

   358 	}

   359 	len = ihigh - ilow;

   360 	np = (PyTupleObject *)PyTuple_New(len);

   361 	if (np == NULL)

   362 		return NULL;

   363 	src = a->ob_item + ilow;

   364 	dest = np->ob_item;

   365 	for (i = 0; i < len; i++) {

   366 		PyObject *v = src[i];

   367 		Py_INCREF(v);

   368 		dest[i] = v;

   369 	}

   370 	return (PyObject *)np;

   371 }

   372 

   373 PyObject *

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

   375 {

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

   377 		PyErr_BadInternalCall();

   378 		return NULL;

   379 	}

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

   381 }

   382 

   383 static PyObject *

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

   385 {

   386 	register Py_ssize_t size;

   387 	register Py_ssize_t i;

   388 	PyObject **src, **dest;

   389 	PyTupleObject *np;

   390 	if (!PyTuple_Check(bb)) {

   391 		PyErr_Format(PyExc_TypeError,

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

   393 			     Py_TYPE(bb)->tp_name);

   394 		return NULL;

   395 	}

   396 #define b ((PyTupleObject *)bb)

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

   398 	if (size < 0)

   399 		return PyErr_NoMemory();

   400 	np = (PyTupleObject *) PyTuple_New(size);

   401 	if (np == NULL) {

   402 		return NULL;

   403 	}

   404 	src = a->ob_item;

   405 	dest = np->ob_item;

   406 	for (i = 0; i < Py_SIZE(a); i++) {

   407 		PyObject *v = src[i];

   408 		Py_INCREF(v);

   409 		dest[i] = v;

   410 	}

   411 	src = b->ob_item;

   412 	dest = np->ob_item + Py_SIZE(a);

   413 	for (i = 0; i < Py_SIZE(b); i++) {

   414 		PyObject *v = src[i];

   415 		Py_INCREF(v);

   416 		dest[i] = v;

   417 	}

   418 	return (PyObject *)np;

   419 #undef b

   420 }

   421 

   422 static PyObject *

   423 tuplerepeat(PyTupleObject *a, Py_ssize_t n)

   424 {

   425 	Py_ssize_t i, j;

   426 	Py_ssize_t size;

   427 	PyTupleObject *np;

   428 	PyObject **p, **items;

   429 	if (n < 0)

   430 		n = 0;

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

   432 		if (PyTuple_CheckExact(a)) {

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

   434 			   copy in this case */

   435 			Py_INCREF(a);

   436 			return (PyObject *)a;

   437 		}

   438 		if (Py_SIZE(a) == 0)

   439 			return PyTuple_New(0);

   440 	}

   441 	size = Py_SIZE(a) * n;

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

   443 		return PyErr_NoMemory();

   444 	np = (PyTupleObject *) PyTuple_New(size);

   445 	if (np == NULL)

   446 		return NULL;

   447 	p = np->ob_item;

   448 	items = a->ob_item;

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

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

   451 			*p = items[j];

   452 			Py_INCREF(*p);

   453 			p++;

   454 		}

   455 	}

   456 	return (PyObject *) np;

   457 }

   458 

   459 static PyObject *

   460 tupleindex(PyTupleObject *self, PyObject *args)

   461 {

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

   463 	PyObject *v;

   464 

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

   466 	                            _PyEval_SliceIndex, &start,

   467 	                            _PyEval_SliceIndex, &stop))

   468 		return NULL;

   469 	if (start < 0) {

   470 		start += Py_SIZE(self);

   471 		if (start < 0)

   472 			start = 0;

   473 	}

   474 	if (stop < 0) {

   475 		stop += Py_SIZE(self);

   476 		if (stop < 0)

   477 			stop = 0;

   478 	}

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

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

   481 		if (cmp > 0)

   482 			return PyInt_FromSsize_t(i);

   483 		else if (cmp < 0)

   484 			return NULL;

   485 	}

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

   487 	return NULL;

   488 }

   489 

   490 static PyObject *

   491 tuplecount(PyTupleObject *self, PyObject *v)

   492 {

   493 	Py_ssize_t count = 0;

   494 	Py_ssize_t i;

   495 

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

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

   498 		if (cmp > 0)

   499 			count++;

   500 		else if (cmp < 0)

   501 			return NULL;

   502 	}

   503 	return PyInt_FromSsize_t(count);

   504 }

   505 

   506 static int

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

   508 {

   509 	Py_ssize_t i;

   510 

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

   512 		Py_VISIT(o->ob_item[i]);

   513 	return 0;

   514 }

   515 

   516 static PyObject *

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

   518 {

   519 	PyTupleObject *vt, *wt;

   520 	Py_ssize_t i;

   521 	Py_ssize_t vlen, wlen;

   522 

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

   524 		Py_INCREF(Py_NotImplemented);

   525 		return Py_NotImplemented;

   526 	}

   527 

   528 	vt = (PyTupleObject *)v;

   529 	wt = (PyTupleObject *)w;

   530 

   531 	vlen = Py_SIZE(vt);

   532 	wlen = Py_SIZE(wt);

   533 

   534 	/* Note:  the corresponding code for lists has an "early out" test

   535 	 * here when op is EQ or NE and the lengths differ.  That pays there,

   536 	 * but Tim was unable to find any real code where EQ/NE tuple

   537 	 * compares don't have the same length, so testing for it here would

   538 	 * have cost without benefit.

   539 	 */

   540 

   541 	/* Search for the first index where items are different.

   542 	 * Note that because tuples are immutable, it's safe to reuse

   543 	 * vlen and wlen across the comparison calls.

   544 	 */

   545 	for (i = 0; i < vlen && i < wlen; i++) {

   546 		int k = PyObject_RichCompareBool(vt->ob_item[i],

   547 						 wt->ob_item[i], Py_EQ);

   548 		if (k < 0)

   549 			return NULL;

   550 		if (!k)

   551 			break;

   552 	}

   553 

   554 	if (i >= vlen || i >= wlen) {

   555 		/* No more items to compare -- compare sizes */

   556 		int cmp;

   557 		PyObject *res;

   558 		switch (op) {

   559 		case Py_LT: cmp = vlen <  wlen; break;

   560 		case Py_LE: cmp = vlen <= wlen; break;

   561 		case Py_EQ: cmp = vlen == wlen; break;

   562 		case Py_NE: cmp = vlen != wlen; break;

   563 		case Py_GT: cmp = vlen >  wlen; break;

   564 		case Py_GE: cmp = vlen >= wlen; break;

   565 		default: return NULL; /* cannot happen */

   566 		}

   567 		if (cmp)

   568 			res = Py_True;

   569 		else

   570 			res = Py_False;

   571 		Py_INCREF(res);

   572 		return res;

   573 	}

   574 

   575 	/* We have an item that differs -- shortcuts for EQ/NE */

   576 	if (op == Py_EQ) {

   577 		Py_INCREF(Py_False);

   578 		return Py_False;

   579 	}

   580 	if (op == Py_NE) {

   581 		Py_INCREF(Py_True);

   582 		return Py_True;

   583 	}

   584 

   585 	/* Compare the final item again using the proper operator */

   586 	return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);

   587 }

   588 

   589 static PyObject *

   590 tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);

   591 

   592 static PyObject *

   593 tuple_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

   594 {

   595 	PyObject *arg = NULL;

   596 	static char *kwlist[] = {"sequence", 0};

   597 

   598 	if (type != &PyTuple_Type)

   599 		return tuple_subtype_new(type, args, kwds);

   600 	if (!PyArg_ParseTupleAndKeywords(args, kwds, "|O:tuple", kwlist, &arg))

   601 		return NULL;

   602 

   603 	if (arg == NULL)

   604 		return PyTuple_New(0);

   605 	else

   606 		return PySequence_Tuple(arg);

   607 }

   608 

   609 static PyObject *

   610 tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

   611 {

   612 	PyObject *tmp, *newobj, *item;

   613 	Py_ssize_t i, n;

   614 

   615 	assert(PyType_IsSubtype(type, &PyTuple_Type));

   616 	tmp = tuple_new(&PyTuple_Type, args, kwds);

   617 	if (tmp == NULL)

   618 		return NULL;

   619 	assert(PyTuple_Check(tmp));

   620 	newobj = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));

   621 	if (newobj == NULL)

   622 		return NULL;

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

   624 		item = PyTuple_GET_ITEM(tmp, i);

   625 		Py_INCREF(item);

   626 		PyTuple_SET_ITEM(newobj, i, item);

   627 	}

   628 	Py_DECREF(tmp);

   629 	return newobj;

   630 }

   631 

   632 PyDoc_STRVAR(tuple_doc,

   633 "tuple() -> an empty tuple\n"

   634 "tuple(sequence) -> tuple initialized from sequence's items\n"

   635 "\n"

   636 "If the argument is a tuple, the return value is the same object.");

   637 

   638 static PySequenceMethods tuple_as_sequence = {

   639 	(lenfunc)tuplelength,			/* sq_length */

   640 	(binaryfunc)tupleconcat,		/* sq_concat */

   641 	(ssizeargfunc)tuplerepeat,		/* sq_repeat */

   642 	(ssizeargfunc)tupleitem,		/* sq_item */

   643 	(ssizessizeargfunc)tupleslice,		/* sq_slice */

   644 	0,					/* sq_ass_item */

   645 	0,					/* sq_ass_slice */

   646 	(objobjproc)tuplecontains,		/* sq_contains */

   647 };

   648 

   649 static PyObject*

   650 tuplesubscript(PyTupleObject* self, PyObject* item)

   651 {

   652 	if (PyIndex_Check(item)) {

   653 		Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);

   654 		if (i == -1 && PyErr_Occurred())

   655 			return NULL;

   656 		if (i < 0)

   657 			i += PyTuple_GET_SIZE(self);

   658 		return tupleitem(self, i);

   659 	}

   660 	else if (PySlice_Check(item)) {

   661 		Py_ssize_t start, stop, step, slicelength, cur, i;

   662 		PyObject* result;

   663 		PyObject* it;

   664 		PyObject **src, **dest;

   665 

   666 		if (PySlice_GetIndicesEx((PySliceObject*)item,

   667 				 PyTuple_GET_SIZE(self),

   668 				 &start, &stop, &step, &slicelength) < 0) {

   669 			return NULL;

   670 		}

   671 

   672 		if (slicelength <= 0) {

   673 			return PyTuple_New(0);

   674 		}

   675 		else if (start == 0 && step == 1 &&

   676 			 slicelength == PyTuple_GET_SIZE(self) &&

   677 			 PyTuple_CheckExact(self)) {

   678 			Py_INCREF(self);

   679 			return (PyObject *)self;

   680 		}

   681 		else {

   682 			result = PyTuple_New(slicelength);

   683 			if (!result) return NULL;

   684 

   685 			src = self->ob_item;

   686 			dest = ((PyTupleObject *)result)->ob_item;

   687 			for (cur = start, i = 0; i < slicelength; 

   688 			     cur += step, i++) {

   689 				it = src[cur];

   690 				Py_INCREF(it);

   691 				dest[i] = it;

   692 			}

   693 			

   694 			return result;

   695 		}

   696 	}

   697 	else {

   698 		PyErr_Format(PyExc_TypeError, 

   699 			     "tuple indices must be integers, not %.200s",

   700 			     Py_TYPE(item)->tp_name);

   701 		return NULL;

   702 	}

   703 }

   704 

   705 static PyObject *

   706 tuple_getnewargs(PyTupleObject *v)

   707 {

   708 	return Py_BuildValue("(N)", tupleslice(v, 0, Py_SIZE(v)));

   709 	

   710 }

   711 

   712 static PyObject *

   713 tuple_sizeof(PyTupleObject *self)

   714 {

   715 	Py_ssize_t res;

   716 

   717 	res = PyTuple_Type.tp_basicsize + Py_SIZE(self) * sizeof(PyObject *);

   718 	return PyInt_FromSsize_t(res);

   719 }

   720 

   721 PyDoc_STRVAR(index_doc,

   722 "T.index(value, [start, [stop]]) -> integer -- return first index of value.\n"

   723 "Raises ValueError if the value is not present."

   724 );

   725 PyDoc_STRVAR(count_doc,

   726 "T.count(value) -> integer -- return number of occurrences of value");

   727 PyDoc_STRVAR(sizeof_doc,

   728 "T.__sizeof__() -- size of T in memory, in bytes");

   729 

   730 static PyMethodDef tuple_methods[] = {

   731 	{"__getnewargs__",	(PyCFunction)tuple_getnewargs,	METH_NOARGS},

   732 	{"__sizeof__",	(PyCFunction)tuple_sizeof, METH_NOARGS, sizeof_doc},

   733 	{"index",	(PyCFunction)tupleindex,  METH_VARARGS, index_doc},

   734 	{"count",	(PyCFunction)tuplecount,  METH_O, count_doc},

   735 	{NULL,		NULL}		/* sentinel */

   736 };

   737 

   738 static PyMappingMethods tuple_as_mapping = {

   739 	(lenfunc)tuplelength,

   740 	(binaryfunc)tuplesubscript,

   741 	0

   742 };

   743 

   744 static PyObject *tuple_iter(PyObject *seq);

   745 

   746 PyTypeObject PyTuple_Type = {

   747 	PyVarObject_HEAD_INIT(&PyType_Type, 0)

   748 	"tuple",

   749 	sizeof(PyTupleObject) - sizeof(PyObject *),

   750 	sizeof(PyObject *),

   751 	(destructor)tupledealloc,		/* tp_dealloc */

   752 	(printfunc)tupleprint,			/* tp_print */

   753 	0,					/* tp_getattr */

   754 	0,					/* tp_setattr */

   755 	0,					/* tp_compare */

   756 	(reprfunc)tuplerepr,			/* tp_repr */

   757 	0,					/* tp_as_number */

   758 	&tuple_as_sequence,			/* tp_as_sequence */

   759 	&tuple_as_mapping,			/* tp_as_mapping */

   760 	(hashfunc)tuplehash,			/* tp_hash */

   761 	0,					/* tp_call */

   762 	0,					/* tp_str */

   763 	PyObject_GenericGetAttr,		/* tp_getattro */

   764 	0,					/* tp_setattro */

   765 	0,					/* tp_as_buffer */

   766 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |

   767 		Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS, /* tp_flags */

   768 	tuple_doc,				/* tp_doc */

   769  	(traverseproc)tupletraverse,		/* tp_traverse */

   770 	0,					/* tp_clear */

   771 	tuplerichcompare,			/* tp_richcompare */

   772 	0,					/* tp_weaklistoffset */

   773 	tuple_iter,	    			/* tp_iter */

   774 	0,					/* tp_iternext */

   775 	tuple_methods,				/* tp_methods */

   776 	0,					/* tp_members */

   777 	0,					/* tp_getset */

   778 	0,					/* tp_base */

   779 	0,					/* tp_dict */

   780 	0,					/* tp_descr_get */

   781 	0,					/* tp_descr_set */

   782 	0,					/* tp_dictoffset */

   783 	0,					/* tp_init */

   784 	0,					/* tp_alloc */

   785 	tuple_new,				/* tp_new */

   786 	PyObject_GC_Del,        		/* tp_free */

   787 };

   788 

   789 /* The following function breaks the notion that tuples are immutable:

   790    it changes the size of a tuple.  We get away with this only if there

   791    is only one module referencing the object.  You can also think of it

   792    as creating a new tuple object and destroying the old one, only more

   793    efficiently.  In any case, don't use this if the tuple may already be

   794    known to some other part of the code. */

   795 

   796 int

   797 _PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)

   798 {

   799 	register PyTupleObject *v;

   800 	register PyTupleObject *sv;

   801 	Py_ssize_t i;

   802 	Py_ssize_t oldsize;

   803 

   804 	v = (PyTupleObject *) *pv;

   805 	if (v == NULL || Py_TYPE(v) != &PyTuple_Type ||

   806 	    (Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {

   807 		*pv = 0;

   808 		Py_XDECREF(v);

   809 		PyErr_BadInternalCall();

   810 		return -1;

   811 	}

   812 	oldsize = Py_SIZE(v);

   813 	if (oldsize == newsize)

   814 		return 0;

   815 

   816 	if (oldsize == 0) {

   817 		/* Empty tuples are often shared, so we should never 

   818 		   resize them in-place even if we do own the only

   819 		   (current) reference */

   820 		Py_DECREF(v);

   821 		*pv = PyTuple_New(newsize);

   822 		return *pv == NULL ? -1 : 0;

   823 	}

   824 

   825 	/* XXX UNREF/NEWREF interface should be more symmetrical */

   826 	_Py_DEC_REFTOTAL;

   827 	_PyObject_GC_UNTRACK(v);

   828 	_Py_ForgetReference((PyObject *) v);

   829 	/* DECREF items deleted by shrinkage */

   830 	for (i = newsize; i < oldsize; i++) {

   831 		Py_XDECREF(v->ob_item[i]);

   832 		v->ob_item[i] = NULL;

   833 	}

   834 	sv = PyObject_GC_Resize(PyTupleObject, v, newsize);

   835 	if (sv == NULL) {

   836 		*pv = NULL;

   837 		PyObject_GC_Del(v);

   838 		return -1;

   839 	}

   840 	_Py_NewReference((PyObject *) sv);

   841 	/* Zero out items added by growing */

   842 	if (newsize > oldsize)

   843 		memset(&sv->ob_item[oldsize], 0,

   844 		       sizeof(*sv->ob_item) * (newsize - oldsize));

   845 	*pv = (PyObject *) sv;

   846 	_PyObject_GC_TRACK(sv);

   847 	return 0;

   848 }

   849 

   850 int

   851 PyTuple_ClearFreeList(void)

   852 {

   853 	int freelist_size = 0;

   854 #if PyTuple_MAXSAVESIZE > 0

   855 	int i;

   856 	for (i = 1; i < PyTuple_MAXSAVESIZE; i++) {

   857 		PyTupleObject *p, *q;

   858 		p = free_list[i];

   859 		freelist_size += numfree[i];

   860 		free_list[i] = NULL;

   861 		numfree[i] = 0;

   862 		while (p) {

   863 			q = p;

   864 			p = (PyTupleObject *)(p->ob_item[0]);

   865 			PyObject_GC_Del(q);

   866 		}

   867 	}

   868 #endif

   869 	return freelist_size;

   870 }

   871 	

   872 void

   873 PyTuple_Fini(void)

   874 {

   875 #if PyTuple_MAXSAVESIZE > 0

   876 	/* empty tuples are used all over the place and applications may

   877 	 * rely on the fact that an empty tuple is a singleton. */

   878 	Py_XDECREF(free_list[0]);

   879 	free_list[0] = NULL;

   880 

   881 	(void)PyTuple_ClearFreeList();

   882 #endif

   883 }

   884 

   885 /*********************** Tuple Iterator **************************/

   886 

   887 typedef struct {

   888 	PyObject_HEAD

   889 	long it_index;

   890 	PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */

   891 } tupleiterobject;

   892 

   893 static void

   894 tupleiter_dealloc(tupleiterobject *it)

   895 {

   896 	_PyObject_GC_UNTRACK(it);

   897 	Py_XDECREF(it->it_seq);

   898 	PyObject_GC_Del(it);

   899 }

   900 

   901 static int

   902 tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)

   903 {

   904 	Py_VISIT(it->it_seq);

   905 	return 0;

   906 }

   907 

   908 static PyObject *

   909 tupleiter_next(tupleiterobject *it)

   910 {

   911 	PyTupleObject *seq;

   912 	PyObject *item;

   913 

   914 	assert(it != NULL);

   915 	seq = it->it_seq;

   916 	if (seq == NULL)

   917 		return NULL;

   918 	assert(PyTuple_Check(seq));

   919 

   920 	if (it->it_index < PyTuple_GET_SIZE(seq)) {

   921 		item = PyTuple_GET_ITEM(seq, it->it_index);

   922 		++it->it_index;

   923 		Py_INCREF(item);

   924 		return item;

   925 	}

   926 

   927 	Py_DECREF(seq);

   928 	it->it_seq = NULL;

   929 	return NULL;

   930 }

   931 

   932 static PyObject *

   933 tupleiter_len(tupleiterobject *it)

   934 {

   935 	Py_ssize_t len = 0;

   936 	if (it->it_seq)

   937 		len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;

   938 	return PyInt_FromSsize_t(len);

   939 }

   940 

   941 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");

   942 

   943 static PyMethodDef tupleiter_methods[] = {

   944 	{"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},

   945  	{NULL,		NULL}		/* sentinel */

   946 };

   947 

   948 PyTypeObject PyTupleIter_Type = {

   949 	PyVarObject_HEAD_INIT(&PyType_Type, 0)

   950 	"tupleiterator",			/* tp_name */

   951 	sizeof(tupleiterobject),		/* tp_basicsize */

   952 	0,					/* tp_itemsize */

   953 	/* methods */

   954 	(destructor)tupleiter_dealloc,		/* tp_dealloc */

   955 	0,					/* tp_print */

   956 	0,					/* tp_getattr */

   957 	0,					/* tp_setattr */

   958 	0,					/* tp_compare */

   959 	0,					/* tp_repr */

   960 	0,					/* tp_as_number */

   961 	0,					/* tp_as_sequence */

   962 	0,					/* tp_as_mapping */

   963 	0,					/* tp_hash */

   964 	0,					/* tp_call */

   965 	0,					/* tp_str */

   966 	PyObject_GenericGetAttr,		/* tp_getattro */

   967 	0,					/* tp_setattro */

   968 	0,					/* tp_as_buffer */

   969 	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */

   970 	0,					/* tp_doc */

   971 	(traverseproc)tupleiter_traverse,	/* tp_traverse */

   972 	0,					/* tp_clear */

   973 	0,					/* tp_richcompare */

   974 	0,					/* tp_weaklistoffset */

   975 	PyObject_SelfIter,			/* tp_iter */

   976 	(iternextfunc)tupleiter_next,		/* tp_iternext */

   977 	tupleiter_methods,			/* tp_methods */

   978 	0,

   979 };

   980 

   981 static PyObject *

   982 tuple_iter(PyObject *seq)

   983 {

   984 	tupleiterobject *it;

   985 

   986 	if (!PyTuple_Check(seq)) {

   987 		PyErr_BadInternalCall();

   988 		return NULL;

   989 	}

   990 	it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);

   991 	if (it == NULL)

   992 		return NULL;

   993 	it->it_index = 0;

   994 	Py_INCREF(seq);

   995 	it->it_seq = (PyTupleObject *)seq;

   996 	_PyObject_GC_TRACK(it);

   997 	return (PyObject *)it;

   998 }