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

Last change on this file since 388 was 2, checked in by Yuri Dario, 15 years ago

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