?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Handle urllib's renaming for Python 3.0:
[python.git] / Objects / tupleobject.c
blob79d755328c679c0100c5e3396fdfeb51d5342464
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 static PyObject *
712 tuple_sizeof(PyTupleObject *self)
713 {
714 Py_ssize_t res;
715
716 res = PyTuple_Type.tp_basicsize + Py_SIZE(self) * sizeof(PyObject *);
717 return PyInt_FromSsize_t(res);
718 }
719
720 PyDoc_STRVAR(index_doc,
721 "T.index(value, [start, [stop]]) -> integer -- return first index of value");
722 PyDoc_STRVAR(count_doc,
723 "T.count(value) -> integer -- return number of occurrences of value");
724 PyDoc_STRVAR(sizeof_doc,
725 "T.__sizeof__() -- size of T in memory, in bytes");
726
727 static PyMethodDef tuple_methods[] = {
728 {"__getnewargs__", (PyCFunction)tuple_getnewargs, METH_NOARGS},
729 {"__sizeof__", (PyCFunction)tuple_sizeof, METH_NOARGS, sizeof_doc},
730 {"index", (PyCFunction)tupleindex, METH_VARARGS, index_doc},
731 {"count", (PyCFunction)tuplecount, METH_O, count_doc},
732 {NULL, NULL} /* sentinel */
733 };
734
735 static PyMappingMethods tuple_as_mapping = {
736 (lenfunc)tuplelength,
737 (binaryfunc)tuplesubscript,
738 0
739 };
740
741 static PyObject *tuple_iter(PyObject *seq);
742
743 PyTypeObject PyTuple_Type = {
744 PyVarObject_HEAD_INIT(&PyType_Type, 0)
745 "tuple",
746 sizeof(PyTupleObject) - sizeof(PyObject *),
747 sizeof(PyObject *),
748 (destructor)tupledealloc, /* tp_dealloc */
749 (printfunc)tupleprint, /* tp_print */
750 0, /* tp_getattr */
751 0, /* tp_setattr */
752 0, /* tp_compare */
753 (reprfunc)tuplerepr, /* tp_repr */
754 0, /* tp_as_number */
755 &tuple_as_sequence, /* tp_as_sequence */
756 &tuple_as_mapping, /* tp_as_mapping */
757 (hashfunc)tuplehash, /* tp_hash */
758 0, /* tp_call */
759 0, /* tp_str */
760 PyObject_GenericGetAttr, /* tp_getattro */
761 0, /* tp_setattro */
762 0, /* tp_as_buffer */
763 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
764 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS, /* tp_flags */
765 tuple_doc, /* tp_doc */
766 (traverseproc)tupletraverse, /* tp_traverse */
767 0, /* tp_clear */
768 tuplerichcompare, /* tp_richcompare */
769 0, /* tp_weaklistoffset */
770 tuple_iter, /* tp_iter */
771 0, /* tp_iternext */
772 tuple_methods, /* tp_methods */
773 0, /* tp_members */
774 0, /* tp_getset */
775 0, /* tp_base */
776 0, /* tp_dict */
777 0, /* tp_descr_get */
778 0, /* tp_descr_set */
779 0, /* tp_dictoffset */
780 0, /* tp_init */
781 0, /* tp_alloc */
782 tuple_new, /* tp_new */
783 PyObject_GC_Del, /* tp_free */
784 };
785
786 /* The following function breaks the notion that tuples are immutable:
787 it changes the size of a tuple. We get away with this only if there
788 is only one module referencing the object. You can also think of it
789 as creating a new tuple object and destroying the old one, only more
790 efficiently. In any case, don't use this if the tuple may already be
791 known to some other part of the code. */
792
793 int
794 _PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
795 {
796 register PyTupleObject *v;
797 register PyTupleObject *sv;
798 Py_ssize_t i;
799 Py_ssize_t oldsize;
800
801 v = (PyTupleObject *) *pv;
802 if (v == NULL || Py_TYPE(v) != &PyTuple_Type ||
803 (Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {
804 *pv = 0;
805 Py_XDECREF(v);
806 PyErr_BadInternalCall();
807 return -1;
808 }
809 oldsize = Py_SIZE(v);
810 if (oldsize == newsize)
811 return 0;
812
813 if (oldsize == 0) {
814 /* Empty tuples are often shared, so we should never
815 resize them in-place even if we do own the only
816 (current) reference */
817 Py_DECREF(v);
818 *pv = PyTuple_New(newsize);
819 return *pv == NULL ? -1 : 0;
820 }
821
822 /* XXX UNREF/NEWREF interface should be more symmetrical */
823 _Py_DEC_REFTOTAL;
824 _PyObject_GC_UNTRACK(v);
825 _Py_ForgetReference((PyObject *) v);
826 /* DECREF items deleted by shrinkage */
827 for (i = newsize; i < oldsize; i++) {
828 Py_XDECREF(v->ob_item[i]);
829 v->ob_item[i] = NULL;
830 }
831 sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
832 if (sv == NULL) {
833 *pv = NULL;
834 PyObject_GC_Del(v);
835 return -1;
836 }
837 _Py_NewReference((PyObject *) sv);
838 /* Zero out items added by growing */
839 if (newsize > oldsize)
840 memset(&sv->ob_item[oldsize], 0,
841 sizeof(*sv->ob_item) * (newsize - oldsize));
842 *pv = (PyObject *) sv;
843 _PyObject_GC_TRACK(sv);
844 return 0;
845 }
846
847 int
848 PyTuple_ClearFreeList(void)
849 {
850 int freelist_size = 0;
851 #if PyTuple_MAXSAVESIZE > 0
852 int i;
853 for (i = 1; i < PyTuple_MAXSAVESIZE; i++) {
854 PyTupleObject *p, *q;
855 p = free_list[i];
856 freelist_size += numfree[i];
857 free_list[i] = NULL;
858 numfree[i] = 0;
859 while (p) {
860 q = p;
861 p = (PyTupleObject *)(p->ob_item[0]);
862 PyObject_GC_Del(q);
863 }
864 }
865 #endif
866 return freelist_size;
867 }
868
869 void
870 PyTuple_Fini(void)
871 {
872 #if PyTuple_MAXSAVESIZE > 0
873 /* empty tuples are used all over the place and applications may
874 * rely on the fact that an empty tuple is a singleton. */
875 Py_XDECREF(free_list[0]);
876 free_list[0] = NULL;
877
878 (void)PyTuple_ClearFreeList();
879 #endif
880 }
881
882 /*********************** Tuple Iterator **************************/
883
884 typedef struct {
885 PyObject_HEAD
886 long it_index;
887 PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */
888 } tupleiterobject;
889
890 static void
891 tupleiter_dealloc(tupleiterobject *it)
892 {
893 _PyObject_GC_UNTRACK(it);
894 Py_XDECREF(it->it_seq);
895 PyObject_GC_Del(it);
896 }
897
898 static int
899 tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)
900 {
901 Py_VISIT(it->it_seq);
902 return 0;
903 }
904
905 static PyObject *
906 tupleiter_next(tupleiterobject *it)
907 {
908 PyTupleObject *seq;
909 PyObject *item;
910
911 assert(it != NULL);
912 seq = it->it_seq;
913 if (seq == NULL)
914 return NULL;
915 assert(PyTuple_Check(seq));
916
917 if (it->it_index < PyTuple_GET_SIZE(seq)) {
918 item = PyTuple_GET_ITEM(seq, it->it_index);
919 ++it->it_index;
920 Py_INCREF(item);
921 return item;
922 }
923
924 Py_DECREF(seq);
925 it->it_seq = NULL;
926 return NULL;
927 }
928
929 static PyObject *
930 tupleiter_len(tupleiterobject *it)
931 {
932 Py_ssize_t len = 0;
933 if (it->it_seq)
934 len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
935 return PyInt_FromSsize_t(len);
936 }
937
938 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
939
940 static PyMethodDef tupleiter_methods[] = {
941 {"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},
942 {NULL, NULL} /* sentinel */
943 };
944
945 PyTypeObject PyTupleIter_Type = {
946 PyVarObject_HEAD_INIT(&PyType_Type, 0)
947 "tupleiterator", /* tp_name */
948 sizeof(tupleiterobject), /* tp_basicsize */
949 0, /* tp_itemsize */
950 /* methods */
951 (destructor)tupleiter_dealloc, /* tp_dealloc */
952 0, /* tp_print */
953 0, /* tp_getattr */
954 0, /* tp_setattr */
955 0, /* tp_compare */
956 0, /* tp_repr */
957 0, /* tp_as_number */
958 0, /* tp_as_sequence */
959 0, /* tp_as_mapping */
960 0, /* tp_hash */
961 0, /* tp_call */
962 0, /* tp_str */
963 PyObject_GenericGetAttr, /* tp_getattro */
964 0, /* tp_setattro */
965 0, /* tp_as_buffer */
966 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
967 0, /* tp_doc */
968 (traverseproc)tupleiter_traverse, /* tp_traverse */
969 0, /* tp_clear */
970 0, /* tp_richcompare */
971 0, /* tp_weaklistoffset */
972 PyObject_SelfIter, /* tp_iter */
973 (iternextfunc)tupleiter_next, /* tp_iternext */
974 tupleiter_methods, /* tp_methods */
975 0,
976 };
977
978 static PyObject *
979 tuple_iter(PyObject *seq)
980 {
981 tupleiterobject *it;
982
983 if (!PyTuple_Check(seq)) {
984 PyErr_BadInternalCall();
985 return NULL;
986 }
987 it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
988 if (it == NULL)
989 return NULL;
990 it->it_index = 0;
991 Py_INCREF(seq);
992 it->it_seq = (PyTupleObject *)seq;
993 _PyObject_GC_TRACK(it);
994 return (PyObject *)it;
995 }
python git mirror