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