source: python/trunk/Objects/tupleobject.c@ 394

Last change on this file since 394 was 391, checked in by dmik, 11 years ago

python: Merge vendor 2.7.6 to trunk.
  • Property svn:eol-style set to native
File size: 29.2 KB
Line 
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*/
18static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
19static int numfree[PyTuple_MAXSAVESIZE];
20#endif
21#ifdef COUNT_ALLOCS
22Py_ssize_t fast_tuple_allocs;
23Py_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
32static Py_ssize_t count_untracked = 0;
33static Py_ssize_t count_tracked = 0;
34
35static void
36show_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
48PyObject *
49PyTuple_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
110Py_ssize_t
111PyTuple_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
121PyObject *
122PyTuple_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
135int
136PyTuple_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
158void
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
184PyObject *
185PyTuple_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
212static void
213tupledealloc(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);
236done:
237 Py_TRASHCAN_SAFE_END(op)
238}
239
240static int
241tupleprint(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
265static PyObject *
266tuplerepr(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
327Done:
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
341static long
342tuplehash(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
364static Py_ssize_t
365tuplelength(PyTupleObject *a)
366{
367 return Py_SIZE(a);
368}
369
370static int
371tuplecontains(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
382static PyObject *
383tupleitem(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
393static PyObject *
394tupleslice(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
425PyObject *
426PyTuple_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
435static PyObject *
436tupleconcat(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
474static PyObject *
475tuplerepeat(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
511static PyObject *
512tupleindex(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
542static PyObject *
543tuplecount(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
558static int
559tupletraverse(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
568static PyObject *
569tuplerichcompare(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
641static PyObject *
642tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
643
644static PyObject *
645tuple_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
661static PyObject *
662tuple_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
684PyDoc_STRVAR(tuple_doc,
685"tuple() -> empty tuple\n\
686tuple(iterable) -> tuple initialized from iterable's items\n\
687\n\
688If the argument is a tuple, the return value is the same object.");
689
690static 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
701static PyObject*
702tuplesubscript(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
757static PyObject *
758tuple_getnewargs(PyTupleObject *v)
759{
760 return Py_BuildValue("(N)", tupleslice(v, 0, Py_SIZE(v)));
761
762}
763
764static PyObject *
765tuple_sizeof(PyTupleObject *self)
766{
767 Py_ssize_t res;
768
769 res = PyTuple_Type.tp_basicsize + Py_SIZE(self) * sizeof(PyObject *);
770 return PyInt_FromSsize_t(res);
771}
772
773PyDoc_STRVAR(index_doc,
774"T.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
775"Raises ValueError if the value is not present."
776);
777PyDoc_STRVAR(count_doc,
778"T.count(value) -> integer -- return number of occurrences of value");
779PyDoc_STRVAR(sizeof_doc,
780"T.__sizeof__() -- size of T in memory, in bytes");
781
782static PyMethodDef tuple_methods[] = {
783 {"__getnewargs__", (PyCFunction)tuple_getnewargs, METH_NOARGS},
784 {"__sizeof__", (PyCFunction)tuple_sizeof, METH_NOARGS, sizeof_doc},
785 {"index", (PyCFunction)tupleindex, METH_VARARGS, index_doc},
786 {"count", (PyCFunction)tuplecount, METH_O, count_doc},
787 {NULL, NULL} /* sentinel */
788};
789
790static PyMappingMethods tuple_as_mapping = {
791 (lenfunc)tuplelength,
792 (binaryfunc)tuplesubscript,
793 0
794};
795
796static PyObject *tuple_iter(PyObject *seq);
797
798PyTypeObject PyTuple_Type = {
799 PyVarObject_HEAD_INIT(&PyType_Type, 0)
800 "tuple",
801 sizeof(PyTupleObject) - sizeof(PyObject *),
802 sizeof(PyObject *),
803 (destructor)tupledealloc, /* tp_dealloc */
804 (printfunc)tupleprint, /* tp_print */
805 0, /* tp_getattr */
806 0, /* tp_setattr */
807 0, /* tp_compare */
808 (reprfunc)tuplerepr, /* tp_repr */
809 0, /* tp_as_number */
810 &tuple_as_sequence, /* tp_as_sequence */
811 &tuple_as_mapping, /* tp_as_mapping */
812 (hashfunc)tuplehash, /* tp_hash */
813 0, /* tp_call */
814 0, /* tp_str */
815 PyObject_GenericGetAttr, /* tp_getattro */
816 0, /* tp_setattro */
817 0, /* tp_as_buffer */
818 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
819 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS, /* tp_flags */
820 tuple_doc, /* tp_doc */
821 (traverseproc)tupletraverse, /* tp_traverse */
822 0, /* tp_clear */
823 tuplerichcompare, /* tp_richcompare */
824 0, /* tp_weaklistoffset */
825 tuple_iter, /* tp_iter */
826 0, /* tp_iternext */
827 tuple_methods, /* tp_methods */
828 0, /* tp_members */
829 0, /* tp_getset */
830 0, /* tp_base */
831 0, /* tp_dict */
832 0, /* tp_descr_get */
833 0, /* tp_descr_set */
834 0, /* tp_dictoffset */
835 0, /* tp_init */
836 0, /* tp_alloc */
837 tuple_new, /* tp_new */
838 PyObject_GC_Del, /* tp_free */
839};
840
841/* The following function breaks the notion that tuples are immutable:
842 it changes the size of a tuple. We get away with this only if there
843 is only one module referencing the object. You can also think of it
844 as creating a new tuple object and destroying the old one, only more
845 efficiently. In any case, don't use this if the tuple may already be
846 known to some other part of the code. */
847
848int
849_PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
850{
851 register PyTupleObject *v;
852 register PyTupleObject *sv;
853 Py_ssize_t i;
854 Py_ssize_t oldsize;
855
856 v = (PyTupleObject *) *pv;
857 if (v == NULL || Py_TYPE(v) != &PyTuple_Type ||
858 (Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {
859 *pv = 0;
860 Py_XDECREF(v);
861 PyErr_BadInternalCall();
862 return -1;
863 }
864 oldsize = Py_SIZE(v);
865 if (oldsize == newsize)
866 return 0;
867
868 if (oldsize == 0) {
869 /* Empty tuples are often shared, so we should never
870 resize them in-place even if we do own the only
871 (current) reference */
872 Py_DECREF(v);
873 *pv = PyTuple_New(newsize);
874 return *pv == NULL ? -1 : 0;
875 }
876
877 /* XXX UNREF/NEWREF interface should be more symmetrical */
878 _Py_DEC_REFTOTAL;
879 if (_PyObject_GC_IS_TRACKED(v))
880 _PyObject_GC_UNTRACK(v);
881 _Py_ForgetReference((PyObject *) v);
882 /* DECREF items deleted by shrinkage */
883 for (i = newsize; i < oldsize; i++) {
884 Py_XDECREF(v->ob_item[i]);
885 v->ob_item[i] = NULL;
886 }
887 sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
888 if (sv == NULL) {
889 *pv = NULL;
890 PyObject_GC_Del(v);
891 return -1;
892 }
893 _Py_NewReference((PyObject *) sv);
894 /* Zero out items added by growing */
895 if (newsize > oldsize)
896 memset(&sv->ob_item[oldsize], 0,
897 sizeof(*sv->ob_item) * (newsize - oldsize));
898 *pv = (PyObject *) sv;
899 _PyObject_GC_TRACK(sv);
900 return 0;
901}
902
903int
904PyTuple_ClearFreeList(void)
905{
906 int freelist_size = 0;
907#if PyTuple_MAXSAVESIZE > 0
908 int i;
909 for (i = 1; i < PyTuple_MAXSAVESIZE; i++) {
910 PyTupleObject *p, *q;
911 p = free_list[i];
912 freelist_size += numfree[i];
913 free_list[i] = NULL;
914 numfree[i] = 0;
915 while (p) {
916 q = p;
917 p = (PyTupleObject *)(p->ob_item[0]);
918 PyObject_GC_Del(q);
919 }
920 }
921#endif
922 return freelist_size;
923}
924
925void
926PyTuple_Fini(void)
927{
928#if PyTuple_MAXSAVESIZE > 0
929 /* empty tuples are used all over the place and applications may
930 * rely on the fact that an empty tuple is a singleton. */
931 Py_XDECREF(free_list[0]);
932 free_list[0] = NULL;
933
934 (void)PyTuple_ClearFreeList();
935#endif
936#ifdef SHOW_TRACK_COUNT
937 show_track();
938#endif
939}
940
941/*********************** Tuple Iterator **************************/
942
943typedef struct {
944 PyObject_HEAD
945 long it_index;
946 PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */
947} tupleiterobject;
948
949static void
950tupleiter_dealloc(tupleiterobject *it)
951{
952 _PyObject_GC_UNTRACK(it);
953 Py_XDECREF(it->it_seq);
954 PyObject_GC_Del(it);
955}
956
957static int
958tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)
959{
960 Py_VISIT(it->it_seq);
961 return 0;
962}
963
964static PyObject *
965tupleiter_next(tupleiterobject *it)
966{
967 PyTupleObject *seq;
968 PyObject *item;
969
970 assert(it != NULL);
971 seq = it->it_seq;
972 if (seq == NULL)
973 return NULL;
974 assert(PyTuple_Check(seq));
975
976 if (it->it_index < PyTuple_GET_SIZE(seq)) {
977 item = PyTuple_GET_ITEM(seq, it->it_index);
978 ++it->it_index;
979 Py_INCREF(item);
980 return item;
981 }
982
983 Py_DECREF(seq);
984 it->it_seq = NULL;
985 return NULL;
986}
987
988static PyObject *
989tupleiter_len(tupleiterobject *it)
990{
991 Py_ssize_t len = 0;
992 if (it->it_seq)
993 len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
994 return PyInt_FromSsize_t(len);
995}
996
997PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
998
999static PyMethodDef tupleiter_methods[] = {
1000 {"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},
1001 {NULL, NULL} /* sentinel */
1002};
1003
1004PyTypeObject PyTupleIter_Type = {
1005 PyVarObject_HEAD_INIT(&PyType_Type, 0)
1006 "tupleiterator", /* tp_name */
1007 sizeof(tupleiterobject), /* tp_basicsize */
1008 0, /* tp_itemsize */
1009 /* methods */
1010 (destructor)tupleiter_dealloc, /* tp_dealloc */
1011 0, /* tp_print */
1012 0, /* tp_getattr */
1013 0, /* tp_setattr */
1014 0, /* tp_compare */
1015 0, /* tp_repr */
1016 0, /* tp_as_number */
1017 0, /* tp_as_sequence */
1018 0, /* tp_as_mapping */
1019 0, /* tp_hash */
1020 0, /* tp_call */
1021 0, /* tp_str */
1022 PyObject_GenericGetAttr, /* tp_getattro */
1023 0, /* tp_setattro */
1024 0, /* tp_as_buffer */
1025 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1026 0, /* tp_doc */
1027 (traverseproc)tupleiter_traverse, /* tp_traverse */
1028 0, /* tp_clear */
1029 0, /* tp_richcompare */
1030 0, /* tp_weaklistoffset */
1031 PyObject_SelfIter, /* tp_iter */
1032 (iternextfunc)tupleiter_next, /* tp_iternext */
1033 tupleiter_methods, /* tp_methods */
1034 0,
1035};
1036
1037static PyObject *
1038tuple_iter(PyObject *seq)
1039{
1040 tupleiterobject *it;
1041
1042 if (!PyTuple_Check(seq)) {
1043 PyErr_BadInternalCall();
1044 return NULL;
1045 }
1046 it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
1047 if (it == NULL)
1048 return NULL;
1049 it->it_index = 0;
1050 Py_INCREF(seq);
1051 it->it_seq = (PyTupleObject *)seq;
1052 _PyObject_GC_TRACK(it);
1053 return (PyObject *)it;
1054}
Note: See TracBrowser for help on using the repository browser.