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