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 Py_ssize_t fast_tuple_allocs;
23 Py_ssize_t tuple_zero_allocs;
24 #endif
25
26 /* Debug statistic to count GC tracking of tuples.
27 Please note that tuples are only untracked when considered by the GC, and
28 many of them will be dead before. Therefore, a tracking rate close to 100%
29 does not necessarily prove that the heuristic is inefficient.
30 */
31 #ifdef SHOW_TRACK_COUNT
32 static Py_ssize_t count_untracked = 0;
33 static Py_ssize_t count_tracked = 0;
34
35 static void
show_track(void)36 show_track(void)
37 {
38 fprintf(stderr, "Tuples created: %" PY_FORMAT_SIZE_T "d\n",
39 count_tracked + count_untracked);
40 fprintf(stderr, "Tuples tracked by the GC: %" PY_FORMAT_SIZE_T
41 "d\n", count_tracked);
42 fprintf(stderr, "%.2f%% tuple tracking rate\n\n",
43 (100.0*count_tracked/(count_untracked+count_tracked)));
44 }
45 #endif
46
47
48 PyObject *
PyTuple_New(register Py_ssize_t size)49 PyTuple_New(register Py_ssize_t size)
50 {
51 register PyTupleObject *op;
52 Py_ssize_t i;
53 if (size < 0) {
54 PyErr_BadInternalCall();
55 return NULL;
56 }
57 #if PyTuple_MAXSAVESIZE > 0
58 if (size == 0 && free_list[0]) {
59 op = free_list[0];
60 Py_INCREF(op);
61 #ifdef COUNT_ALLOCS
62 tuple_zero_allocs++;
63 #endif
64 return (PyObject *) op;
65 }
66 if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
67 free_list[size] = (PyTupleObject *) op->ob_item[0];
68 numfree[size]--;
69 #ifdef COUNT_ALLOCS
70 fast_tuple_allocs++;
71 #endif
72 /* Inline PyObject_InitVar */
73 #ifdef Py_TRACE_REFS
74 Py_SIZE(op) = size;
75 Py_TYPE(op) = &PyTuple_Type;
76 #endif
77 _Py_NewReference((PyObject *)op);
78 }
79 else
80 #endif
81 {
82 Py_ssize_t nbytes = size * sizeof(PyObject *);
83 /* Check for overflow */
84 if (nbytes / sizeof(PyObject *) != (size_t)size ||
85 (nbytes > PY_SSIZE_T_MAX - sizeof(PyTupleObject) - sizeof(PyObject *)))
86 {
87 return PyErr_NoMemory();
88 }
89
90 op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
91 if (op == NULL)
92 return NULL;
93 }
94 for (i=0; i < size; i++)
95 op->ob_item[i] = NULL;
96 #if PyTuple_MAXSAVESIZE > 0
97 if (size == 0) {
98 free_list[0] = op;
99 ++numfree[0];
100 Py_INCREF(op); /* extra INCREF so that this is never freed */
101 }
102 #endif
103 #ifdef SHOW_TRACK_COUNT
104 count_tracked++;
105 #endif
106 _PyObject_GC_TRACK(op);
107 return (PyObject *) op;
108 }
109
110 Py_ssize_t
PyTuple_Size(register PyObject * op)111 PyTuple_Size(register PyObject *op)
112 {
113 if (!PyTuple_Check(op)) {
114 PyErr_BadInternalCall();
115 return -1;
116 }
117 else
118 return Py_SIZE(op);
119 }
120
121 PyObject *
PyTuple_GetItem(register PyObject * op,register Py_ssize_t i)122 PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)
123 {
124 if (!PyTuple_Check(op)) {
125 PyErr_BadInternalCall();
126 return NULL;
127 }
128 if (i < 0 || i >= Py_SIZE(op)) {
129 PyErr_SetString(PyExc_IndexError, "tuple index out of range");
130 return NULL;
131 }
132 return ((PyTupleObject *)op) -> ob_item[i];
133 }
134
135 int
PyTuple_SetItem(register PyObject * op,register Py_ssize_t i,PyObject * newitem)136 PyTuple_SetItem(register PyObject *op, register Py_ssize_t i, PyObject *newitem)
137 {
138 register PyObject *olditem;
139 register PyObject **p;
140 if (!PyTuple_Check(op) || op->ob_refcnt != 1) {
141 Py_XDECREF(newitem);
142 PyErr_BadInternalCall();
143 return -1;
144 }
145 if (i < 0 || i >= Py_SIZE(op)) {
146 Py_XDECREF(newitem);
147 PyErr_SetString(PyExc_IndexError,
148 "tuple assignment index out of range");
149 return -1;
150 }
151 p = ((PyTupleObject *)op) -> ob_item + i;
152 olditem = *p;
153 *p = newitem;
154 Py_XDECREF(olditem);
155 return 0;
156 }
157
158 void
_PyTuple_MaybeUntrack(PyObject * op)159 _PyTuple_MaybeUntrack(PyObject *op)
160 {
161 PyTupleObject *t;
162 Py_ssize_t i, n;
163
164 if (!PyTuple_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
165 return;
166 t = (PyTupleObject *) op;
167 n = Py_SIZE(t);
168 for (i = 0; i < n; i++) {
169 PyObject *elt = PyTuple_GET_ITEM(t, i);
170 /* Tuple with NULL elements aren't
171 fully constructed, don't untrack
172 them yet. */
173 if (!elt ||
174 _PyObject_GC_MAY_BE_TRACKED(elt))
175 return;
176 }
177 #ifdef SHOW_TRACK_COUNT
178 count_tracked--;
179 count_untracked++;
180 #endif
181 _PyObject_GC_UNTRACK(op);
182 }
183
184 PyObject *
PyTuple_Pack(Py_ssize_t n,...)185 PyTuple_Pack(Py_ssize_t n, ...)
186 {
187 Py_ssize_t i;
188 PyObject *o;
189 PyObject *result;
190 PyObject **items;
191 va_list vargs;
192
193 va_start(vargs, n);
194 result = PyTuple_New(n);
195 if (result == NULL)
196 return NULL;
197 items = ((PyTupleObject *)result)->ob_item;
198 for (i = 0; i < n; i++) {
199 o = va_arg(vargs, PyObject *);
200 Py_INCREF(o);
201 items[i] = o;
202 }
203 va_end(vargs);
204 return result;
205 }
206
207
208 /* Methods */
209
210 static void
tupledealloc(register PyTupleObject * op)211 tupledealloc(register PyTupleObject *op)
212 {
213 register Py_ssize_t i;
214 register Py_ssize_t len = Py_SIZE(op);
215 PyObject_GC_UnTrack(op);
216 Py_TRASHCAN_SAFE_BEGIN(op)
217 if (len > 0) {
218 i = len;
219 while (--i >= 0)
220 Py_XDECREF(op->ob_item[i]);
221 #if PyTuple_MAXSAVESIZE > 0
222 if (len < PyTuple_MAXSAVESIZE &&
223 numfree[len] < PyTuple_MAXFREELIST &&
224 Py_TYPE(op) == &PyTuple_Type)
225 {
226 op->ob_item[0] = (PyObject *) free_list[len];
227 numfree[len]++;
228 free_list[len] = op;
229 goto done; /* return */
230 }
231 #endif
232 }
233 Py_TYPE(op)->tp_free((PyObject *)op);
234 done:
235 Py_TRASHCAN_SAFE_END(op)
236 }
237
238 static int
tupleprint(PyTupleObject * op,FILE * fp,int flags)239 tupleprint(PyTupleObject *op, FILE *fp, int flags)
240 {
241 Py_ssize_t i;
242 Py_BEGIN_ALLOW_THREADS
243 fprintf(fp, "(");
244 Py_END_ALLOW_THREADS
245 for (i = 0; i < Py_SIZE(op); i++) {
246 if (i > 0) {
247 Py_BEGIN_ALLOW_THREADS
248 fprintf(fp, ", ");
249 Py_END_ALLOW_THREADS
250 }
251 if (PyObject_Print(op->ob_item[i], fp, 0) != 0)
252 return -1;
253 }
254 i = Py_SIZE(op);
255 Py_BEGIN_ALLOW_THREADS
256 if (i == 1)
257 fprintf(fp, ",");
258 fprintf(fp, ")");
259 Py_END_ALLOW_THREADS
260 return 0;
261 }
262
263 static PyObject *
tuplerepr(PyTupleObject * v)264 tuplerepr(PyTupleObject *v)
265 {
266 Py_ssize_t i, n;
267 PyObject *s, *temp;
268 PyObject *pieces, *result = NULL;
269
270 n = Py_SIZE(v);
271 if (n == 0)
272 return PyString_FromString("()");
273
274 /* While not mutable, it is still possible to end up with a cycle in a
275 tuple through an object that stores itself within a tuple (and thus
276 infinitely asks for the repr of itself). This should only be
277 possible within a type. */
278 i = Py_ReprEnter((PyObject *)v);
279 if (i != 0) {
280 return i > 0 ? PyString_FromString("(...)") : NULL;
281 }
282
283 pieces = PyTuple_New(n);
284 if (pieces == NULL)
285 return NULL;
286
287 /* Do repr() on each element. */
288 for (i = 0; i < n; ++i) {
289 if (Py_EnterRecursiveCall(" while getting the repr of a tuple"))
290 goto Done;
291 s = PyObject_Repr(v->ob_item[i]);
292 Py_LeaveRecursiveCall();
293 if (s == NULL)
294 goto Done;
295 PyTuple_SET_ITEM(pieces, i, s);
296 }
297
298 /* Add "()" decorations to the first and last items. */
299 assert(n > 0);
300 s = PyString_FromString("(");
301 if (s == NULL)
302 goto Done;
303 temp = PyTuple_GET_ITEM(pieces, 0);
304 PyString_ConcatAndDel(&s, temp);
305 PyTuple_SET_ITEM(pieces, 0, s);
306 if (s == NULL)
307 goto Done;
308
309 s = PyString_FromString(n == 1 ? ",)" : ")");
310 if (s == NULL)
311 goto Done;
312 temp = PyTuple_GET_ITEM(pieces, n-1);
313 PyString_ConcatAndDel(&temp, s);
314 PyTuple_SET_ITEM(pieces, n-1, temp);
315 if (temp == NULL)
316 goto Done;
317
318 /* Paste them all together with ", " between. */
319 s = PyString_FromString(", ");
320 if (s == NULL)
321 goto Done;
322 result = _PyString_Join(s, pieces);
323 Py_DECREF(s);
324
325 Done:
326 Py_DECREF(pieces);
327 Py_ReprLeave((PyObject *)v);
328 return result;
329 }
330
331 /* The addend 82520, was selected from the range(0, 1000000) for
332 generating the greatest number of prime multipliers for tuples
333 upto length eight:
334
335 1082527, 1165049, 1082531, 1165057, 1247581, 1330103, 1082533,
336 1330111, 1412633, 1165069, 1247599, 1495177, 1577699
337 */
338
339 static long
tuplehash(PyTupleObject * v)340 tuplehash(PyTupleObject *v)
341 {
342 register long x, y;
343 register Py_ssize_t len = Py_SIZE(v);
344 register PyObject **p;
345 long mult = 1000003L;
346 x = 0x345678L;
347 p = v->ob_item;
348 while (--len >= 0) {
349 y = PyObject_Hash(*p++);
350 if (y == -1)
351 return -1;
352 x = (x ^ y) * mult;
353 /* the cast might truncate len; that doesn't change hash stability */
354 mult += (long)(82520L + len + len);
355 }
356 x += 97531L;
357 if (x == -1)
358 x = -2;
359 return x;
360 }
361
362 static Py_ssize_t
tuplelength(PyTupleObject * a)363 tuplelength(PyTupleObject *a)
364 {
365 return Py_SIZE(a);
366 }
367
368 static int
tuplecontains(PyTupleObject * a,PyObject * el)369 tuplecontains(PyTupleObject *a, PyObject *el)
370 {
371 Py_ssize_t i;
372 int cmp;
373
374 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
375 cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),
376 Py_EQ);
377 return cmp;
378 }
379
380 static PyObject *
tupleitem(register PyTupleObject * a,register Py_ssize_t i)381 tupleitem(register PyTupleObject *a, register Py_ssize_t i)
382 {
383 if (i < 0 || i >= Py_SIZE(a)) {
384 PyErr_SetString(PyExc_IndexError, "tuple index out of range");
385 return NULL;
386 }
387 Py_INCREF(a->ob_item[i]);
388 return a->ob_item[i];
389 }
390
391 static PyObject *
tupleslice(register PyTupleObject * a,register Py_ssize_t ilow,register Py_ssize_t ihigh)392 tupleslice(register PyTupleObject *a, register Py_ssize_t ilow,
393 register Py_ssize_t ihigh)
394 {
395 register PyTupleObject *np;
396 PyObject **src, **dest;
397 register Py_ssize_t i;
398 Py_ssize_t len;
399 if (ilow < 0)
400 ilow = 0;
401 if (ihigh > Py_SIZE(a))
402 ihigh = Py_SIZE(a);
403 if (ihigh < ilow)
404 ihigh = ilow;
405 if (ilow == 0 && ihigh == Py_SIZE(a) && PyTuple_CheckExact(a)) {
406 Py_INCREF(a);
407 return (PyObject *)a;
408 }
409 len = ihigh - ilow;
410 np = (PyTupleObject *)PyTuple_New(len);
411 if (np == NULL)
412 return NULL;
413 src = a->ob_item + ilow;
414 dest = np->ob_item;
415 for (i = 0; i < len; i++) {
416 PyObject *v = src[i];
417 Py_INCREF(v);
418 dest[i] = v;
419 }
420 return (PyObject *)np;
421 }
422
423 PyObject *
PyTuple_GetSlice(PyObject * op,Py_ssize_t i,Py_ssize_t j)424 PyTuple_GetSlice(PyObject *op, Py_ssize_t i, Py_ssize_t j)
425 {
426 if (op == NULL || !PyTuple_Check(op)) {
427 PyErr_BadInternalCall();
428 return NULL;
429 }
430 return tupleslice((PyTupleObject *)op, i, j);
431 }
432
433 static PyObject *
tupleconcat(register PyTupleObject * a,register PyObject * bb)434 tupleconcat(register PyTupleObject *a, register PyObject *bb)
435 {
436 register Py_ssize_t size;
437 register Py_ssize_t i;
438 PyObject **src, **dest;
439 PyTupleObject *np;
440 if (!PyTuple_Check(bb)) {
441 PyErr_Format(PyExc_TypeError,
442 "can only concatenate tuple (not \"%.200s\") to tuple",
443 Py_TYPE(bb)->tp_name);
444 return NULL;
445 }
446 #define b ((PyTupleObject *)bb)
447 size = Py_SIZE(a) + Py_SIZE(b);
448 if (size < 0)
449 return PyErr_NoMemory();
450 np = (PyTupleObject *) PyTuple_New(size);
451 if (np == NULL) {
452 return NULL;
453 }
454 src = a->ob_item;
455 dest = np->ob_item;
456 for (i = 0; i < Py_SIZE(a); i++) {
457 PyObject *v = src[i];
458 Py_INCREF(v);
459 dest[i] = v;
460 }
461 src = b->ob_item;
462 dest = np->ob_item + Py_SIZE(a);
463 for (i = 0; i < Py_SIZE(b); i++) {
464 PyObject *v = src[i];
465 Py_INCREF(v);
466 dest[i] = v;
467 }
468 return (PyObject *)np;
469 #undef b
470 }
471
472 static PyObject *
tuplerepeat(PyTupleObject * a,Py_ssize_t n)473 tuplerepeat(PyTupleObject *a, Py_ssize_t n)
474 {
475 Py_ssize_t i, j;
476 Py_ssize_t size;
477 PyTupleObject *np;
478 PyObject **p, **items;
479 if (n < 0)
480 n = 0;
481 if (Py_SIZE(a) == 0 || n == 1) {
482 if (PyTuple_CheckExact(a)) {
483 /* Since tuples are immutable, we can return a shared
484 copy in this case */
485 Py_INCREF(a);
486 return (PyObject *)a;
487 }
488 if (Py_SIZE(a) == 0)
489 return PyTuple_New(0);
490 }
491 size = Py_SIZE(a) * n;
492 if (size/Py_SIZE(a) != n)
493 return PyErr_NoMemory();
494 np = (PyTupleObject *) PyTuple_New(size);
495 if (np == NULL)
496 return NULL;
497 p = np->ob_item;
498 items = a->ob_item;
499 for (i = 0; i < n; i++) {
500 for (j = 0; j < Py_SIZE(a); j++) {
501 *p = items[j];
502 Py_INCREF(*p);
503 p++;
504 }
505 }
506 return (PyObject *) np;
507 }
508
509 static PyObject *
tupleindex(PyTupleObject * self,PyObject * args)510 tupleindex(PyTupleObject *self, PyObject *args)
511 {
512 Py_ssize_t i, start=0, stop=Py_SIZE(self);
513 PyObject *v;
514
515 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
516 _PyEval_SliceIndex, &start,
517 _PyEval_SliceIndex, &stop))
518 return NULL;
519 if (start < 0) {
520 start += Py_SIZE(self);
521 if (start < 0)
522 start = 0;
523 }
524 if (stop < 0) {
525 stop += Py_SIZE(self);
526 if (stop < 0)
527 stop = 0;
528 }
529 for (i = start; i < stop && i < Py_SIZE(self); i++) {
530 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
531 if (cmp > 0)
532 return PyInt_FromSsize_t(i);
533 else if (cmp < 0)
534 return NULL;
535 }
536 PyErr_SetString(PyExc_ValueError, "tuple.index(x): x not in tuple");
537 return NULL;
538 }
539
540 static PyObject *
tuplecount(PyTupleObject * self,PyObject * v)541 tuplecount(PyTupleObject *self, PyObject *v)
542 {
543 Py_ssize_t count = 0;
544 Py_ssize_t i;
545
546 for (i = 0; i < Py_SIZE(self); i++) {
547 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
548 if (cmp > 0)
549 count++;
550 else if (cmp < 0)
551 return NULL;
552 }
553 return PyInt_FromSsize_t(count);
554 }
555
556 static int
tupletraverse(PyTupleObject * o,visitproc visit,void * arg)557 tupletraverse(PyTupleObject *o, visitproc visit, void *arg)
558 {
559 Py_ssize_t i;
560
561 for (i = Py_SIZE(o); --i >= 0; )
562 Py_VISIT(o->ob_item[i]);
563 return 0;
564 }
565
566 static PyObject *
tuplerichcompare(PyObject * v,PyObject * w,int op)567 tuplerichcompare(PyObject *v, PyObject *w, int op)
568 {
569 PyTupleObject *vt, *wt;
570 Py_ssize_t i;
571 Py_ssize_t vlen, wlen;
572
573 if (!PyTuple_Check(v) || !PyTuple_Check(w)) {
574 Py_INCREF(Py_NotImplemented);
575 return Py_NotImplemented;
576 }
577
578 vt = (PyTupleObject *)v;
579 wt = (PyTupleObject *)w;
580
581 vlen = Py_SIZE(vt);
582 wlen = Py_SIZE(wt);
583
584 /* Note: the corresponding code for lists has an "early out" test
585 * here when op is EQ or NE and the lengths differ. That pays there,
586 * but Tim was unable to find any real code where EQ/NE tuple
587 * compares don't have the same length, so testing for it here would
588 * have cost without benefit.
589 */
590
591 /* Search for the first index where items are different.
592 * Note that because tuples are immutable, it's safe to reuse
593 * vlen and wlen across the comparison calls.
594 */
595 for (i = 0; i < vlen && i < wlen; i++) {
596 int k = PyObject_RichCompareBool(vt->ob_item[i],
597 wt->ob_item[i], Py_EQ);
598 if (k < 0)
599 return NULL;
600 if (!k)
601 break;
602 }
603
604 if (i >= vlen || i >= wlen) {
605 /* No more items to compare -- compare sizes */
606 int cmp;
607 PyObject *res;
608 switch (op) {
609 case Py_LT: cmp = vlen < wlen; break;
610 case Py_LE: cmp = vlen <= wlen; break;
611 case Py_EQ: cmp = vlen == wlen; break;
612 case Py_NE: cmp = vlen != wlen; break;
613 case Py_GT: cmp = vlen > wlen; break;
614 case Py_GE: cmp = vlen >= wlen; break;
615 default: return NULL; /* cannot happen */
616 }
617 if (cmp)
618 res = Py_True;
619 else
620 res = Py_False;
621 Py_INCREF(res);
622 return res;
623 }
624
625 /* We have an item that differs -- shortcuts for EQ/NE */
626 if (op == Py_EQ) {
627 Py_INCREF(Py_False);
628 return Py_False;
629 }
630 if (op == Py_NE) {
631 Py_INCREF(Py_True);
632 return Py_True;
633 }
634
635 /* Compare the final item again using the proper operator */
636 return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);
637 }
638
639 static PyObject *
640 tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
641
642 static PyObject *
tuple_new(PyTypeObject * type,PyObject * args,PyObject * kwds)643 tuple_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
644 {
645 PyObject *arg = NULL;
646 static char *kwlist[] = {"sequence", 0};
647
648 if (type != &PyTuple_Type)
649 return tuple_subtype_new(type, args, kwds);
650 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|O:tuple", kwlist, &arg))
651 return NULL;
652
653 if (arg == NULL)
654 return PyTuple_New(0);
655 else
656 return PySequence_Tuple(arg);
657 }
658
659 static PyObject *
tuple_subtype_new(PyTypeObject * type,PyObject * args,PyObject * kwds)660 tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
661 {
662 PyObject *tmp, *newobj, *item;
663 Py_ssize_t i, n;
664
665 assert(PyType_IsSubtype(type, &PyTuple_Type));
666 tmp = tuple_new(&PyTuple_Type, args, kwds);
667 if (tmp == NULL)
668 return NULL;
669 assert(PyTuple_Check(tmp));
670 newobj = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));
671 if (newobj == NULL)
672 return NULL;
673 for (i = 0; i < n; i++) {
674 item = PyTuple_GET_ITEM(tmp, i);
675 Py_INCREF(item);
676 PyTuple_SET_ITEM(newobj, i, item);
677 }
678 Py_DECREF(tmp);
679 return newobj;
680 }
681
682 PyDoc_STRVAR(tuple_doc,
683 "tuple() -> empty tuple\n\
684 tuple(iterable) -> tuple initialized from iterable's items\n\
685 \n\
686 If the argument is a tuple, the return value is the same object.");
687
688 static PySequenceMethods tuple_as_sequence = {
689 (lenfunc)tuplelength, /* sq_length */
690 (binaryfunc)tupleconcat, /* sq_concat */
691 (ssizeargfunc)tuplerepeat, /* sq_repeat */
692 (ssizeargfunc)tupleitem, /* sq_item */
693 (ssizessizeargfunc)tupleslice, /* sq_slice */
694 0, /* sq_ass_item */
695 0, /* sq_ass_slice */
696 (objobjproc)tuplecontains, /* sq_contains */
697 };
698
699 static PyObject*
tuplesubscript(PyTupleObject * self,PyObject * item)700 tuplesubscript(PyTupleObject* self, PyObject* item)
701 {
702 if (PyIndex_Check(item)) {
703 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
704 if (i == -1 && PyErr_Occurred())
705 return NULL;
706 if (i < 0)
707 i += PyTuple_GET_SIZE(self);
708 return tupleitem(self, i);
709 }
710 else if (PySlice_Check(item)) {
711 Py_ssize_t start, stop, step, slicelength, cur, i;
712 PyObject* result;
713 PyObject* it;
714 PyObject **src, **dest;
715
716 if (PySlice_GetIndicesEx((PySliceObject*)item,
717 PyTuple_GET_SIZE(self),
718 &start, &stop, &step, &slicelength) < 0) {
719 return NULL;
720 }
721
722 if (slicelength <= 0) {
723 return PyTuple_New(0);
724 }
725 else if (start == 0 && step == 1 &&
726 slicelength == PyTuple_GET_SIZE(self) &&
727 PyTuple_CheckExact(self)) {
728 Py_INCREF(self);
729 return (PyObject *)self;
730 }
731 else {
732 result = PyTuple_New(slicelength);
733 if (!result) return NULL;
734
735 src = self->ob_item;
736 dest = ((PyTupleObject *)result)->ob_item;
737 for (cur = start, i = 0; i < slicelength;
738 cur += step, i++) {
739 it = src[cur];
740 Py_INCREF(it);
741 dest[i] = it;
742 }
743
744 return result;
745 }
746 }
747 else {
748 PyErr_Format(PyExc_TypeError,
749 "tuple indices must be integers, not %.200s",
750 Py_TYPE(item)->tp_name);
751 return NULL;
752 }
753 }
754
755 static PyObject *
tuple_getnewargs(PyTupleObject * v)756 tuple_getnewargs(PyTupleObject *v)
757 {
758 return Py_BuildValue("(N)", tupleslice(v, 0, Py_SIZE(v)));
759
760 }
761
762 static PyObject *
tuple_sizeof(PyTupleObject * self)763 tuple_sizeof(PyTupleObject *self)
764 {
765 Py_ssize_t res;
766
767 res = PyTuple_Type.tp_basicsize + Py_SIZE(self) * sizeof(PyObject *);
768 return PyInt_FromSsize_t(res);
769 }
770
771 PyDoc_STRVAR(index_doc,
772 "T.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
773 "Raises ValueError if the value is not present."
774 );
775 PyDoc_STRVAR(count_doc,
776 "T.count(value) -> integer -- return number of occurrences of value");
777 PyDoc_STRVAR(sizeof_doc,
778 "T.__sizeof__() -- size of T in memory, in bytes");
779
780 static PyMethodDef tuple_methods[] = {
781 {"__getnewargs__", (PyCFunction)tuple_getnewargs, METH_NOARGS},
782 {"__sizeof__", (PyCFunction)tuple_sizeof, METH_NOARGS, sizeof_doc},
783 {"index", (PyCFunction)tupleindex, METH_VARARGS, index_doc},
784 {"count", (PyCFunction)tuplecount, METH_O, count_doc},
785 {NULL, NULL} /* sentinel */
786 };
787
788 static PyMappingMethods tuple_as_mapping = {
789 (lenfunc)tuplelength,
790 (binaryfunc)tuplesubscript,
791 0
792 };
793
794 static PyObject *tuple_iter(PyObject *seq);
795
796 PyTypeObject PyTuple_Type = {
797 PyVarObject_HEAD_INIT(&PyType_Type, 0)
798 "tuple",
799 sizeof(PyTupleObject) - sizeof(PyObject *),
800 sizeof(PyObject *),
801 (destructor)tupledealloc, /* tp_dealloc */
802 (printfunc)tupleprint, /* tp_print */
803 0, /* tp_getattr */
804 0, /* tp_setattr */
805 0, /* tp_compare */
806 (reprfunc)tuplerepr, /* tp_repr */
807 0, /* tp_as_number */
808 &tuple_as_sequence, /* tp_as_sequence */
809 &tuple_as_mapping, /* tp_as_mapping */
810 (hashfunc)tuplehash, /* tp_hash */
811 0, /* tp_call */
812 0, /* tp_str */
813 PyObject_GenericGetAttr, /* tp_getattro */
814 0, /* tp_setattro */
815 0, /* tp_as_buffer */
816 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
817 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS, /* tp_flags */
818 tuple_doc, /* tp_doc */
819 (traverseproc)tupletraverse, /* tp_traverse */
820 0, /* tp_clear */
821 tuplerichcompare, /* tp_richcompare */
822 0, /* tp_weaklistoffset */
823 tuple_iter, /* tp_iter */
824 0, /* tp_iternext */
825 tuple_methods, /* tp_methods */
826 0, /* tp_members */
827 0, /* tp_getset */
828 0, /* tp_base */
829 0, /* tp_dict */
830 0, /* tp_descr_get */
831 0, /* tp_descr_set */
832 0, /* tp_dictoffset */
833 0, /* tp_init */
834 0, /* tp_alloc */
835 tuple_new, /* tp_new */
836 PyObject_GC_Del, /* tp_free */
837 };
838
839 /* The following function breaks the notion that tuples are immutable:
840 it changes the size of a tuple. We get away with this only if there
841 is only one module referencing the object. You can also think of it
842 as creating a new tuple object and destroying the old one, only more
843 efficiently. In any case, don't use this if the tuple may already be
844 known to some other part of the code. */
845
846 int
_PyTuple_Resize(PyObject ** pv,Py_ssize_t newsize)847 _PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
848 {
849 register PyTupleObject *v;
850 register PyTupleObject *sv;
851 Py_ssize_t i;
852 Py_ssize_t oldsize;
853
854 v = (PyTupleObject *) *pv;
855 if (v == NULL || Py_TYPE(v) != &PyTuple_Type ||
856 (Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {
857 *pv = 0;
858 Py_XDECREF(v);
859 PyErr_BadInternalCall();
860 return -1;
861 }
862 oldsize = Py_SIZE(v);
863 if (oldsize == newsize)
864 return 0;
865
866 if (oldsize == 0) {
867 /* Empty tuples are often shared, so we should never
868 resize them in-place even if we do own the only
869 (current) reference */
870 Py_DECREF(v);
871 *pv = PyTuple_New(newsize);
872 return *pv == NULL ? -1 : 0;
873 }
874
875 /* XXX UNREF/NEWREF interface should be more symmetrical */
876 _Py_DEC_REFTOTAL;
877 if (_PyObject_GC_IS_TRACKED(v))
878 _PyObject_GC_UNTRACK(v);
879 _Py_ForgetReference((PyObject *) v);
880 /* DECREF items deleted by shrinkage */
881 for (i = newsize; i < oldsize; i++) {
882 Py_XDECREF(v->ob_item[i]);
883 v->ob_item[i] = NULL;
884 }
885 sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
886 if (sv == NULL) {
887 *pv = NULL;
888 PyObject_GC_Del(v);
889 return -1;
890 }
891 _Py_NewReference((PyObject *) sv);
892 /* Zero out items added by growing */
893 if (newsize > oldsize)
894 memset(&sv->ob_item[oldsize], 0,
895 sizeof(*sv->ob_item) * (newsize - oldsize));
896 *pv = (PyObject *) sv;
897 _PyObject_GC_TRACK(sv);
898 return 0;
899 }
900
901 int
PyTuple_ClearFreeList(void)902 PyTuple_ClearFreeList(void)
903 {
904 int freelist_size = 0;
905 #if PyTuple_MAXSAVESIZE > 0
906 int i;
907 for (i = 1; i < PyTuple_MAXSAVESIZE; i++) {
908 PyTupleObject *p, *q;
909 p = free_list[i];
910 freelist_size += numfree[i];
911 free_list[i] = NULL;
912 numfree[i] = 0;
913 while (p) {
914 q = p;
915 p = (PyTupleObject *)(p->ob_item[0]);
916 PyObject_GC_Del(q);
917 }
918 }
919 #endif
920 return freelist_size;
921 }
922
923 void
PyTuple_Fini(void)924 PyTuple_Fini(void)
925 {
926 #if PyTuple_MAXSAVESIZE > 0
927 /* empty tuples are used all over the place and applications may
928 * rely on the fact that an empty tuple is a singleton. */
929 Py_XDECREF(free_list[0]);
930 free_list[0] = NULL;
931
932 (void)PyTuple_ClearFreeList();
933 #endif
934 #ifdef SHOW_TRACK_COUNT
935 show_track();
936 #endif
937 }
938
939 /*********************** Tuple Iterator **************************/
940
941 typedef struct {
942 PyObject_HEAD
943 long it_index;
944 PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */
945 } tupleiterobject;
946
947 static void
tupleiter_dealloc(tupleiterobject * it)948 tupleiter_dealloc(tupleiterobject *it)
949 {
950 _PyObject_GC_UNTRACK(it);
951 Py_XDECREF(it->it_seq);
952 PyObject_GC_Del(it);
953 }
954
955 static int
tupleiter_traverse(tupleiterobject * it,visitproc visit,void * arg)956 tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)
957 {
958 Py_VISIT(it->it_seq);
959 return 0;
960 }
961
962 static PyObject *
tupleiter_next(tupleiterobject * it)963 tupleiter_next(tupleiterobject *it)
964 {
965 PyTupleObject *seq;
966 PyObject *item;
967
968 assert(it != NULL);
969 seq = it->it_seq;
970 if (seq == NULL)
971 return NULL;
972 assert(PyTuple_Check(seq));
973
974 if (it->it_index < PyTuple_GET_SIZE(seq)) {
975 item = PyTuple_GET_ITEM(seq, it->it_index);
976 ++it->it_index;
977 Py_INCREF(item);
978 return item;
979 }
980
981 Py_DECREF(seq);
982 it->it_seq = NULL;
983 return NULL;
984 }
985
986 static PyObject *
tupleiter_len(tupleiterobject * it)987 tupleiter_len(tupleiterobject *it)
988 {
989 Py_ssize_t len = 0;
990 if (it->it_seq)
991 len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
992 return PyInt_FromSsize_t(len);
993 }
994
995 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
996
997 static PyMethodDef tupleiter_methods[] = {
998 {"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},
999 {NULL, NULL} /* sentinel */
1000 };
1001
1002 PyTypeObject PyTupleIter_Type = {
1003 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1004 "tupleiterator", /* tp_name */
1005 sizeof(tupleiterobject), /* tp_basicsize */
1006 0, /* tp_itemsize */
1007 /* methods */
1008 (destructor)tupleiter_dealloc, /* tp_dealloc */
1009 0, /* tp_print */
1010 0, /* tp_getattr */
1011 0, /* tp_setattr */
1012 0, /* tp_compare */
1013 0, /* tp_repr */
1014 0, /* tp_as_number */
1015 0, /* tp_as_sequence */
1016 0, /* tp_as_mapping */
1017 0, /* tp_hash */
1018 0, /* tp_call */
1019 0, /* tp_str */
1020 PyObject_GenericGetAttr, /* tp_getattro */
1021 0, /* tp_setattro */
1022 0, /* tp_as_buffer */
1023 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1024 0, /* tp_doc */
1025 (traverseproc)tupleiter_traverse, /* tp_traverse */
1026 0, /* tp_clear */
1027 0, /* tp_richcompare */
1028 0, /* tp_weaklistoffset */
1029 PyObject_SelfIter, /* tp_iter */
1030 (iternextfunc)tupleiter_next, /* tp_iternext */
1031 tupleiter_methods, /* tp_methods */
1032 0,
1033 };
1034
1035 static PyObject *
tuple_iter(PyObject * seq)1036 tuple_iter(PyObject *seq)
1037 {
1038 tupleiterobject *it;
1039
1040 if (!PyTuple_Check(seq)) {
1041 PyErr_BadInternalCall();
1042 return NULL;
1043 }
1044 it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
1045 if (it == NULL)
1046 return NULL;
1047 it->it_index = 0;
1048 Py_INCREF(seq);
1049 it->it_seq = (PyTupleObject *)seq;
1050 _PyObject_GC_TRACK(it);
1051 return (PyObject *)it;
1052 }
1053