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