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