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