Line data Source code
1 :
2 : /* Tuple object implementation */
3 :
4 : #include "Python.h"
5 :
6 : /* Speed optimization to avoid frequent malloc/free of small tuples */
7 : #ifndef PyTuple_MAXSAVESIZE
8 : #define PyTuple_MAXSAVESIZE 20 /* Largest tuple to save on free list */
9 : #endif
10 : #ifndef PyTuple_MAXFREELIST
11 : #define PyTuple_MAXFREELIST 2000 /* Maximum number of tuples of each size to save */
12 : #endif
13 :
14 : #if PyTuple_MAXSAVESIZE > 0
15 : /* Entries 1 up to PyTuple_MAXSAVESIZE are free lists, entry 0 is the empty
16 : tuple () of which at most one instance will be allocated.
17 : */
18 : static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
19 : static int numfree[PyTuple_MAXSAVESIZE];
20 : #endif
21 : #ifdef COUNT_ALLOCS
22 : Py_ssize_t fast_tuple_allocs;
23 : Py_ssize_t tuple_zero_allocs;
24 : #endif
25 :
26 : /* Debug statistic to count GC tracking of tuples.
27 : Please note that tuples are only untracked when considered by the GC, and
28 : many of them will be dead before. Therefore, a tracking rate close to 100%
29 : does not necessarily prove that the heuristic is inefficient.
30 : */
31 : #ifdef SHOW_TRACK_COUNT
32 : static Py_ssize_t count_untracked = 0;
33 : static Py_ssize_t count_tracked = 0;
34 :
35 : static void
36 : show_track(void)
37 : {
38 : fprintf(stderr, "Tuples created: %" PY_FORMAT_SIZE_T "d\n",
39 : count_tracked + count_untracked);
40 : fprintf(stderr, "Tuples tracked by the GC: %" PY_FORMAT_SIZE_T
41 : "d\n", count_tracked);
42 : fprintf(stderr, "%.2f%% tuple tracking rate\n\n",
43 : (100.0*count_tracked/(count_untracked+count_tracked)));
44 : }
45 : #endif
46 :
47 :
48 : PyObject *
49 244034 : PyTuple_New(register Py_ssize_t size)
50 : {
51 : register PyTupleObject *op;
52 : Py_ssize_t i;
53 244034 : if (size < 0) {
54 0 : PyErr_BadInternalCall();
55 0 : return NULL;
56 : }
57 : #if PyTuple_MAXSAVESIZE > 0
58 244034 : if (size == 0 && free_list[0]) {
59 28179 : op = free_list[0];
60 28179 : Py_INCREF(op);
61 : #ifdef COUNT_ALLOCS
62 : tuple_zero_allocs++;
63 : #endif
64 28179 : return (PyObject *) op;
65 : }
66 215855 : if (size < PyTuple_MAXSAVESIZE && (op = free_list[size]) != NULL) {
67 190808 : free_list[size] = (PyTupleObject *) op->ob_item[0];
68 190808 : 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 190808 : _Py_NewReference((PyObject *)op);
78 : }
79 : else
80 : #endif
81 : {
82 25047 : Py_ssize_t nbytes = size * sizeof(PyObject *);
83 : /* Check for overflow */
84 50094 : if (nbytes / sizeof(PyObject *) != (size_t)size ||
85 25047 : (nbytes > PY_SSIZE_T_MAX - sizeof(PyTupleObject) - sizeof(PyObject *)))
86 : {
87 0 : return PyErr_NoMemory();
88 : }
89 :
90 25047 : op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
91 25047 : if (op == NULL)
92 0 : return NULL;
93 : }
94 690122 : for (i=0; i < size; i++)
95 474267 : op->ob_item[i] = NULL;
96 : #if PyTuple_MAXSAVESIZE > 0
97 215855 : if (size == 0) {
98 3 : free_list[0] = op;
99 3 : ++numfree[0];
100 3 : 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 215855 : _PyObject_GC_TRACK(op);
107 215855 : return (PyObject *) op;
108 : }
109 :
110 : Py_ssize_t
111 50315 : PyTuple_Size(register PyObject *op)
112 : {
113 50315 : if (!PyTuple_Check(op)) {
114 0 : PyErr_BadInternalCall();
115 0 : return -1;
116 : }
117 : else
118 50315 : return Py_SIZE(op);
119 : }
120 :
121 : PyObject *
122 10906 : PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)
123 : {
124 10906 : if (!PyTuple_Check(op)) {
125 0 : PyErr_BadInternalCall();
126 0 : return NULL;
127 : }
128 10906 : if (i < 0 || i >= Py_SIZE(op)) {
129 0 : PyErr_SetString(PyExc_IndexError, "tuple index out of range");
130 0 : return NULL;
131 : }
132 10906 : return ((PyTupleObject *)op) -> ob_item[i];
133 : }
134 :
135 : int
136 36 : PyTuple_SetItem(register PyObject *op, register Py_ssize_t i, PyObject *newitem)
137 : {
138 : register PyObject *olditem;
139 : register PyObject **p;
140 36 : if (!PyTuple_Check(op) || op->ob_refcnt != 1) {
141 0 : Py_XDECREF(newitem);
142 0 : PyErr_BadInternalCall();
143 0 : return -1;
144 : }
145 36 : if (i < 0 || i >= Py_SIZE(op)) {
146 0 : Py_XDECREF(newitem);
147 0 : PyErr_SetString(PyExc_IndexError,
148 : "tuple assignment index out of range");
149 0 : return -1;
150 : }
151 36 : p = ((PyTupleObject *)op) -> ob_item + i;
152 36 : olditem = *p;
153 36 : *p = newitem;
154 36 : Py_XDECREF(olditem);
155 36 : return 0;
156 : }
157 :
158 : void
159 32930 : _PyTuple_MaybeUntrack(PyObject *op)
160 : {
161 : PyTupleObject *t;
162 : Py_ssize_t i, n;
163 :
164 32930 : if (!PyTuple_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
165 0 : return;
166 32930 : t = (PyTupleObject *) op;
167 32930 : n = Py_SIZE(t);
168 139293 : for (i = 0; i < n; i++) {
169 115126 : PyObject *elt = PyTuple_GET_ITEM(t, i);
170 : /* Tuple with NULL elements aren't
171 : fully constructed, don't untrack
172 : them yet. */
173 230245 : if (!elt ||
174 128727 : _PyObject_GC_MAY_BE_TRACKED(elt))
175 8763 : return;
176 : }
177 : #ifdef SHOW_TRACK_COUNT
178 : count_tracked--;
179 : count_untracked++;
180 : #endif
181 24167 : _PyObject_GC_UNTRACK(op);
182 : }
183 :
184 : PyObject *
185 37113 : PyTuple_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 37113 : va_start(vargs, n);
194 37113 : result = PyTuple_New(n);
195 37113 : if (result == NULL) {
196 0 : va_end(vargs);
197 0 : return NULL;
198 : }
199 37113 : items = ((PyTupleObject *)result)->ob_item;
200 109844 : for (i = 0; i < n; i++) {
201 72731 : o = va_arg(vargs, PyObject *);
202 72731 : Py_INCREF(o);
203 72731 : items[i] = o;
204 : }
205 37113 : va_end(vargs);
206 37113 : return result;
207 : }
208 :
209 :
210 : /* Methods */
211 :
212 : static void
213 208778 : tupledealloc(register PyTupleObject *op)
214 : {
215 : register Py_ssize_t i;
216 208778 : register Py_ssize_t len = Py_SIZE(op);
217 208778 : PyObject_GC_UnTrack(op);
218 208778 : Py_TRASHCAN_SAFE_BEGIN(op)
219 208766 : if (len > 0) {
220 208766 : i = len;
221 868129 : while (--i >= 0)
222 450597 : Py_XDECREF(op->ob_item[i]);
223 : #if PyTuple_MAXSAVESIZE > 0
224 416695 : if (len < PyTuple_MAXSAVESIZE &&
225 415858 : numfree[len] < PyTuple_MAXFREELIST &&
226 207929 : Py_TYPE(op) == &PyTuple_Type)
227 : {
228 205514 : op->ob_item[0] = (PyObject *) free_list[len];
229 205514 : numfree[len]++;
230 205514 : free_list[len] = op;
231 205514 : goto done; /* return */
232 : }
233 : #endif
234 : }
235 3252 : Py_TYPE(op)->tp_free((PyObject *)op);
236 : done:
237 208766 : Py_TRASHCAN_SAFE_END(op)
238 208778 : }
239 :
240 : static int
241 0 : tupleprint(PyTupleObject *op, FILE *fp, int flags)
242 : {
243 : Py_ssize_t i;
244 : Py_BEGIN_ALLOW_THREADS
245 0 : fprintf(fp, "(");
246 : Py_END_ALLOW_THREADS
247 0 : for (i = 0; i < Py_SIZE(op); i++) {
248 0 : if (i > 0) {
249 : Py_BEGIN_ALLOW_THREADS
250 0 : fprintf(fp, ", ");
251 : Py_END_ALLOW_THREADS
252 : }
253 0 : if (PyObject_Print(op->ob_item[i], fp, 0) != 0)
254 0 : return -1;
255 : }
256 0 : i = Py_SIZE(op);
257 : Py_BEGIN_ALLOW_THREADS
258 0 : if (i == 1)
259 0 : fprintf(fp, ",");
260 0 : fprintf(fp, ")");
261 : Py_END_ALLOW_THREADS
262 0 : return 0;
263 : }
264 :
265 : static PyObject *
266 81 : tuplerepr(PyTupleObject *v)
267 : {
268 : Py_ssize_t i, n;
269 : PyObject *s, *temp;
270 81 : PyObject *pieces, *result = NULL;
271 :
272 81 : n = Py_SIZE(v);
273 81 : if (n == 0)
274 0 : 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 81 : i = Py_ReprEnter((PyObject *)v);
281 81 : if (i != 0) {
282 0 : return i > 0 ? PyString_FromString("(...)") : NULL;
283 : }
284 :
285 81 : pieces = PyTuple_New(n);
286 81 : if (pieces == NULL)
287 0 : return NULL;
288 :
289 : /* Do repr() on each element. */
290 423 : for (i = 0; i < n; ++i) {
291 342 : if (Py_EnterRecursiveCall(" while getting the repr of a tuple"))
292 0 : goto Done;
293 342 : s = PyObject_Repr(v->ob_item[i]);
294 342 : Py_LeaveRecursiveCall();
295 342 : if (s == NULL)
296 0 : goto Done;
297 342 : PyTuple_SET_ITEM(pieces, i, s);
298 : }
299 :
300 : /* Add "()" decorations to the first and last items. */
301 : assert(n > 0);
302 81 : s = PyString_FromString("(");
303 81 : if (s == NULL)
304 0 : goto Done;
305 81 : temp = PyTuple_GET_ITEM(pieces, 0);
306 81 : PyString_ConcatAndDel(&s, temp);
307 81 : PyTuple_SET_ITEM(pieces, 0, s);
308 81 : if (s == NULL)
309 0 : goto Done;
310 :
311 81 : s = PyString_FromString(n == 1 ? ",)" : ")");
312 81 : if (s == NULL)
313 0 : goto Done;
314 81 : temp = PyTuple_GET_ITEM(pieces, n-1);
315 81 : PyString_ConcatAndDel(&temp, s);
316 81 : PyTuple_SET_ITEM(pieces, n-1, temp);
317 81 : if (temp == NULL)
318 0 : goto Done;
319 :
320 : /* Paste them all together with ", " between. */
321 81 : s = PyString_FromString(", ");
322 81 : if (s == NULL)
323 0 : goto Done;
324 81 : result = _PyString_Join(s, pieces);
325 81 : Py_DECREF(s);
326 :
327 : Done:
328 81 : Py_DECREF(pieces);
329 81 : Py_ReprLeave((PyObject *)v);
330 81 : 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 :
341 : static long
342 65491 : tuplehash(PyTupleObject *v)
343 : {
344 : register long x, y;
345 65491 : register Py_ssize_t len = Py_SIZE(v);
346 : register PyObject **p;
347 65491 : long mult = 1000003L;
348 65491 : x = 0x345678L;
349 65491 : p = v->ob_item;
350 275556 : while (--len >= 0) {
351 144574 : y = PyObject_Hash(*p++);
352 144574 : if (y == -1)
353 0 : return -1;
354 144574 : x = (x ^ y) * mult;
355 : /* the cast might truncate len; that doesn't change hash stability */
356 144574 : mult += (long)(82520L + len + len);
357 : }
358 65491 : x += 97531L;
359 65491 : if (x == -1)
360 0 : x = -2;
361 65491 : return x;
362 : }
363 :
364 : static Py_ssize_t
365 1969 : tuplelength(PyTupleObject *a)
366 : {
367 1969 : return Py_SIZE(a);
368 : }
369 :
370 : static int
371 7537 : tuplecontains(PyTupleObject *a, PyObject *el)
372 : {
373 : Py_ssize_t i;
374 : int cmp;
375 :
376 27227 : for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
377 19690 : cmp = PyObject_RichCompareBool(el, PyTuple_GET_ITEM(a, i),
378 : Py_EQ);
379 7537 : return cmp;
380 : }
381 :
382 : static PyObject *
383 21561 : tupleitem(register PyTupleObject *a, register Py_ssize_t i)
384 : {
385 21561 : if (i < 0 || i >= Py_SIZE(a)) {
386 270 : PyErr_SetString(PyExc_IndexError, "tuple index out of range");
387 270 : return NULL;
388 : }
389 21291 : Py_INCREF(a->ob_item[i]);
390 21291 : return a->ob_item[i];
391 : }
392 :
393 : static PyObject *
394 3366 : tupleslice(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 3366 : if (ilow < 0)
402 0 : ilow = 0;
403 3366 : if (ihigh > Py_SIZE(a))
404 9 : ihigh = Py_SIZE(a);
405 3366 : if (ihigh < ilow)
406 0 : ihigh = ilow;
407 3366 : if (ilow == 0 && ihigh == Py_SIZE(a) && PyTuple_CheckExact(a)) {
408 0 : Py_INCREF(a);
409 0 : return (PyObject *)a;
410 : }
411 3366 : len = ihigh - ilow;
412 3366 : np = (PyTupleObject *)PyTuple_New(len);
413 3366 : if (np == NULL)
414 0 : return NULL;
415 3366 : src = a->ob_item + ilow;
416 3366 : dest = np->ob_item;
417 6147 : for (i = 0; i < len; i++) {
418 2781 : PyObject *v = src[i];
419 2781 : Py_INCREF(v);
420 2781 : dest[i] = v;
421 : }
422 3366 : return (PyObject *)np;
423 : }
424 :
425 : PyObject *
426 3363 : PyTuple_GetSlice(PyObject *op, Py_ssize_t i, Py_ssize_t j)
427 : {
428 3363 : if (op == NULL || !PyTuple_Check(op)) {
429 0 : PyErr_BadInternalCall();
430 0 : return NULL;
431 : }
432 3363 : return tupleslice((PyTupleObject *)op, i, j);
433 : }
434 :
435 : static PyObject *
436 2061 : tupleconcat(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 2061 : if (!PyTuple_Check(bb)) {
443 0 : PyErr_Format(PyExc_TypeError,
444 : "can only concatenate tuple (not \"%.200s\") to tuple",
445 0 : Py_TYPE(bb)->tp_name);
446 0 : return NULL;
447 : }
448 : #define b ((PyTupleObject *)bb)
449 2061 : size = Py_SIZE(a) + Py_SIZE(b);
450 2061 : if (size < 0)
451 0 : return PyErr_NoMemory();
452 2061 : np = (PyTupleObject *) PyTuple_New(size);
453 2061 : if (np == NULL) {
454 0 : return NULL;
455 : }
456 2061 : src = a->ob_item;
457 2061 : dest = np->ob_item;
458 4137 : for (i = 0; i < Py_SIZE(a); i++) {
459 2076 : PyObject *v = src[i];
460 2076 : Py_INCREF(v);
461 2076 : dest[i] = v;
462 : }
463 2061 : src = b->ob_item;
464 2061 : dest = np->ob_item + Py_SIZE(a);
465 6192 : for (i = 0; i < Py_SIZE(b); i++) {
466 4131 : PyObject *v = src[i];
467 4131 : Py_INCREF(v);
468 4131 : dest[i] = v;
469 : }
470 2061 : return (PyObject *)np;
471 : #undef b
472 : }
473 :
474 : static PyObject *
475 0 : tuplerepeat(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 0 : if (n < 0)
482 0 : n = 0;
483 0 : if (Py_SIZE(a) == 0 || n == 1) {
484 0 : if (PyTuple_CheckExact(a)) {
485 : /* Since tuples are immutable, we can return a shared
486 : copy in this case */
487 0 : Py_INCREF(a);
488 0 : return (PyObject *)a;
489 : }
490 0 : if (Py_SIZE(a) == 0)
491 0 : return PyTuple_New(0);
492 : }
493 0 : size = Py_SIZE(a) * n;
494 0 : if (size/Py_SIZE(a) != n)
495 0 : return PyErr_NoMemory();
496 0 : np = (PyTupleObject *) PyTuple_New(size);
497 0 : if (np == NULL)
498 0 : return NULL;
499 0 : p = np->ob_item;
500 0 : items = a->ob_item;
501 0 : for (i = 0; i < n; i++) {
502 0 : for (j = 0; j < Py_SIZE(a); j++) {
503 0 : *p = items[j];
504 0 : Py_INCREF(*p);
505 0 : p++;
506 : }
507 : }
508 0 : return (PyObject *) np;
509 : }
510 :
511 : static PyObject *
512 0 : tupleindex(PyTupleObject *self, PyObject *args)
513 : {
514 0 : Py_ssize_t i, start=0, stop=Py_SIZE(self);
515 : PyObject *v;
516 :
517 0 : if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
518 : _PyEval_SliceIndex, &start,
519 : _PyEval_SliceIndex, &stop))
520 0 : return NULL;
521 0 : if (start < 0) {
522 0 : start += Py_SIZE(self);
523 0 : if (start < 0)
524 0 : start = 0;
525 : }
526 0 : if (stop < 0) {
527 0 : stop += Py_SIZE(self);
528 0 : if (stop < 0)
529 0 : stop = 0;
530 : }
531 0 : for (i = start; i < stop && i < Py_SIZE(self); i++) {
532 0 : int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
533 0 : if (cmp > 0)
534 0 : return PyInt_FromSsize_t(i);
535 0 : else if (cmp < 0)
536 0 : return NULL;
537 : }
538 0 : PyErr_SetString(PyExc_ValueError, "tuple.index(x): x not in tuple");
539 0 : return NULL;
540 : }
541 :
542 : static PyObject *
543 0 : tuplecount(PyTupleObject *self, PyObject *v)
544 : {
545 0 : Py_ssize_t count = 0;
546 : Py_ssize_t i;
547 :
548 0 : for (i = 0; i < Py_SIZE(self); i++) {
549 0 : int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
550 0 : if (cmp > 0)
551 0 : count++;
552 0 : else if (cmp < 0)
553 0 : return NULL;
554 : }
555 0 : return PyInt_FromSsize_t(count);
556 : }
557 :
558 : static int
559 65884 : tupletraverse(PyTupleObject *o, visitproc visit, void *arg)
560 : {
561 : Py_ssize_t i;
562 :
563 396542 : for (i = Py_SIZE(o); --i >= 0; )
564 264774 : Py_VISIT(o->ob_item[i]);
565 65884 : return 0;
566 : }
567 :
568 : static PyObject *
569 15403 : tuplerichcompare(PyObject *v, PyObject *w, int op)
570 : {
571 : PyTupleObject *vt, *wt;
572 : Py_ssize_t i;
573 : Py_ssize_t vlen, wlen;
574 :
575 15403 : if (!PyTuple_Check(v) || !PyTuple_Check(w)) {
576 0 : Py_INCREF(Py_NotImplemented);
577 0 : return Py_NotImplemented;
578 : }
579 :
580 15403 : vt = (PyTupleObject *)v;
581 15403 : wt = (PyTupleObject *)w;
582 :
583 15403 : vlen = Py_SIZE(vt);
584 15403 : 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 47195 : for (i = 0; i < vlen && i < wlen; i++) {
598 31943 : int k = PyObject_RichCompareBool(vt->ob_item[i],
599 : wt->ob_item[i], Py_EQ);
600 31943 : if (k < 0)
601 0 : return NULL;
602 31943 : if (!k)
603 151 : break;
604 : }
605 :
606 15403 : if (i >= vlen || i >= wlen) {
607 : /* No more items to compare -- compare sizes */
608 : int cmp;
609 : PyObject *res;
610 15252 : switch (op) {
611 0 : case Py_LT: cmp = vlen < wlen; break;
612 0 : case Py_LE: cmp = vlen <= wlen; break;
613 15246 : case Py_EQ: cmp = vlen == wlen; break;
614 6 : case Py_NE: cmp = vlen != wlen; break;
615 0 : case Py_GT: cmp = vlen > wlen; break;
616 0 : case Py_GE: cmp = vlen >= wlen; break;
617 0 : default: return NULL; /* cannot happen */
618 : }
619 15252 : if (cmp)
620 15246 : res = Py_True;
621 : else
622 6 : res = Py_False;
623 15252 : Py_INCREF(res);
624 15252 : return res;
625 : }
626 :
627 : /* We have an item that differs -- shortcuts for EQ/NE */
628 151 : if (op == Py_EQ) {
629 37 : Py_INCREF(Py_False);
630 37 : return Py_False;
631 : }
632 114 : if (op == Py_NE) {
633 114 : Py_INCREF(Py_True);
634 114 : return Py_True;
635 : }
636 :
637 : /* Compare the final item again using the proper operator */
638 0 : return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);
639 : }
640 :
641 : static PyObject *
642 : tuple_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
643 :
644 : static PyObject *
645 4968 : tuple_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
646 : {
647 4968 : PyObject *arg = NULL;
648 : static char *kwlist[] = {"sequence", 0};
649 :
650 4968 : if (type != &PyTuple_Type)
651 2415 : return tuple_subtype_new(type, args, kwds);
652 2553 : if (!PyArg_ParseTupleAndKeywords(args, kwds, "|O:tuple", kwlist, &arg))
653 0 : return NULL;
654 :
655 2553 : if (arg == NULL)
656 0 : return PyTuple_New(0);
657 : else
658 2553 : return PySequence_Tuple(arg);
659 : }
660 :
661 : static PyObject *
662 2415 : tuple_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 2415 : tmp = tuple_new(&PyTuple_Type, args, kwds);
669 2415 : if (tmp == NULL)
670 0 : return NULL;
671 : assert(PyTuple_Check(tmp));
672 2415 : newobj = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));
673 2415 : if (newobj == NULL)
674 0 : return NULL;
675 9663 : for (i = 0; i < n; i++) {
676 7248 : item = PyTuple_GET_ITEM(tmp, i);
677 7248 : Py_INCREF(item);
678 7248 : PyTuple_SET_ITEM(newobj, i, item);
679 : }
680 2415 : Py_DECREF(tmp);
681 2415 : return newobj;
682 : }
683 :
684 : PyDoc_STRVAR(tuple_doc,
685 : "tuple() -> empty tuple\n\
686 : tuple(iterable) -> tuple initialized from iterable's items\n\
687 : \n\
688 : If the argument is a tuple, the return value is the same object.");
689 :
690 : static 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 :
701 : static PyObject*
702 20889 : tuplesubscript(PyTupleObject* self, PyObject* item)
703 : {
704 20889 : if (PyIndex_Check(item)) {
705 20889 : Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
706 20889 : if (i == -1 && PyErr_Occurred())
707 0 : return NULL;
708 20889 : if (i < 0)
709 0 : i += PyTuple_GET_SIZE(self);
710 20889 : return tupleitem(self, i);
711 : }
712 0 : 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 0 : if (PySlice_GetIndicesEx((PySliceObject*)item,
719 : PyTuple_GET_SIZE(self),
720 : &start, &stop, &step, &slicelength) < 0) {
721 0 : return NULL;
722 : }
723 :
724 0 : if (slicelength <= 0) {
725 0 : return PyTuple_New(0);
726 : }
727 0 : else if (start == 0 && step == 1 &&
728 0 : slicelength == PyTuple_GET_SIZE(self) &&
729 0 : PyTuple_CheckExact(self)) {
730 0 : Py_INCREF(self);
731 0 : return (PyObject *)self;
732 : }
733 : else {
734 0 : result = PyTuple_New(slicelength);
735 0 : if (!result) return NULL;
736 :
737 0 : src = self->ob_item;
738 0 : dest = ((PyTupleObject *)result)->ob_item;
739 0 : for (cur = start, i = 0; i < slicelength;
740 0 : cur += step, i++) {
741 0 : it = src[cur];
742 0 : Py_INCREF(it);
743 0 : dest[i] = it;
744 : }
745 :
746 0 : return result;
747 : }
748 : }
749 : else {
750 0 : PyErr_Format(PyExc_TypeError,
751 : "tuple indices must be integers, not %.200s",
752 0 : Py_TYPE(item)->tp_name);
753 0 : return NULL;
754 : }
755 : }
756 :
757 : static PyObject *
758 0 : tuple_getnewargs(PyTupleObject *v)
759 : {
760 0 : return Py_BuildValue("(N)", tupleslice(v, 0, Py_SIZE(v)));
761 :
762 : }
763 :
764 : PyDoc_STRVAR(index_doc,
765 : "T.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
766 : "Raises ValueError if the value is not present."
767 : );
768 : PyDoc_STRVAR(count_doc,
769 : "T.count(value) -> integer -- return number of occurrences of value");
770 :
771 : static PyMethodDef tuple_methods[] = {
772 : {"__getnewargs__", (PyCFunction)tuple_getnewargs, METH_NOARGS},
773 : {"index", (PyCFunction)tupleindex, METH_VARARGS, index_doc},
774 : {"count", (PyCFunction)tuplecount, METH_O, count_doc},
775 : {NULL, NULL} /* sentinel */
776 : };
777 :
778 : static PyMappingMethods tuple_as_mapping = {
779 : (lenfunc)tuplelength,
780 : (binaryfunc)tuplesubscript,
781 : 0
782 : };
783 :
784 : static PyObject *tuple_iter(PyObject *seq);
785 :
786 : PyTypeObject PyTuple_Type = {
787 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
788 : "tuple",
789 : sizeof(PyTupleObject) - sizeof(PyObject *),
790 : sizeof(PyObject *),
791 : (destructor)tupledealloc, /* tp_dealloc */
792 : (printfunc)tupleprint, /* tp_print */
793 : 0, /* tp_getattr */
794 : 0, /* tp_setattr */
795 : 0, /* tp_compare */
796 : (reprfunc)tuplerepr, /* tp_repr */
797 : 0, /* tp_as_number */
798 : &tuple_as_sequence, /* tp_as_sequence */
799 : &tuple_as_mapping, /* tp_as_mapping */
800 : (hashfunc)tuplehash, /* tp_hash */
801 : 0, /* tp_call */
802 : 0, /* tp_str */
803 : PyObject_GenericGetAttr, /* tp_getattro */
804 : 0, /* tp_setattro */
805 : 0, /* tp_as_buffer */
806 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
807 : Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS, /* tp_flags */
808 : tuple_doc, /* tp_doc */
809 : (traverseproc)tupletraverse, /* tp_traverse */
810 : 0, /* tp_clear */
811 : tuplerichcompare, /* tp_richcompare */
812 : 0, /* tp_weaklistoffset */
813 : tuple_iter, /* tp_iter */
814 : 0, /* tp_iternext */
815 : tuple_methods, /* tp_methods */
816 : 0, /* tp_members */
817 : 0, /* tp_getset */
818 : 0, /* tp_base */
819 : 0, /* tp_dict */
820 : 0, /* tp_descr_get */
821 : 0, /* tp_descr_set */
822 : 0, /* tp_dictoffset */
823 : 0, /* tp_init */
824 : 0, /* tp_alloc */
825 : tuple_new, /* tp_new */
826 : PyObject_GC_Del, /* tp_free */
827 : };
828 :
829 : /* The following function breaks the notion that tuples are immutable:
830 : it changes the size of a tuple. We get away with this only if there
831 : is only one module referencing the object. You can also think of it
832 : as creating a new tuple object and destroying the old one, only more
833 : efficiently. In any case, don't use this if the tuple may already be
834 : known to some other part of the code. */
835 :
836 : int
837 114 : _PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
838 : {
839 : register PyTupleObject *v;
840 : register PyTupleObject *sv;
841 : Py_ssize_t i;
842 : Py_ssize_t oldsize;
843 :
844 114 : v = (PyTupleObject *) *pv;
845 228 : if (v == NULL || Py_TYPE(v) != &PyTuple_Type ||
846 228 : (Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {
847 0 : *pv = 0;
848 0 : Py_XDECREF(v);
849 0 : PyErr_BadInternalCall();
850 0 : return -1;
851 : }
852 114 : oldsize = Py_SIZE(v);
853 114 : if (oldsize == newsize)
854 33 : return 0;
855 :
856 81 : if (oldsize == 0) {
857 : /* Empty tuples are often shared, so we should never
858 : resize them in-place even if we do own the only
859 : (current) reference */
860 0 : Py_DECREF(v);
861 0 : *pv = PyTuple_New(newsize);
862 0 : return *pv == NULL ? -1 : 0;
863 : }
864 :
865 : /* XXX UNREF/NEWREF interface should be more symmetrical */
866 : _Py_DEC_REFTOTAL;
867 81 : if (_PyObject_GC_IS_TRACKED(v))
868 81 : _PyObject_GC_UNTRACK(v);
869 : _Py_ForgetReference((PyObject *) v);
870 : /* DECREF items deleted by shrinkage */
871 801 : for (i = newsize; i < oldsize; i++) {
872 720 : Py_CLEAR(v->ob_item[i]);
873 : }
874 81 : sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
875 81 : if (sv == NULL) {
876 0 : *pv = NULL;
877 0 : PyObject_GC_Del(v);
878 0 : return -1;
879 : }
880 81 : _Py_NewReference((PyObject *) sv);
881 : /* Zero out items added by growing */
882 81 : if (newsize > oldsize)
883 0 : memset(&sv->ob_item[oldsize], 0,
884 0 : sizeof(*sv->ob_item) * (newsize - oldsize));
885 81 : *pv = (PyObject *) sv;
886 81 : _PyObject_GC_TRACK(sv);
887 81 : return 0;
888 : }
889 :
890 : int
891 6 : PyTuple_ClearFreeList(void)
892 : {
893 6 : int freelist_size = 0;
894 : #if PyTuple_MAXSAVESIZE > 0
895 : int i;
896 120 : for (i = 1; i < PyTuple_MAXSAVESIZE; i++) {
897 : PyTupleObject *p, *q;
898 114 : p = free_list[i];
899 114 : freelist_size += numfree[i];
900 114 : free_list[i] = NULL;
901 114 : numfree[i] = 0;
902 14934 : while (p) {
903 14706 : q = p;
904 14706 : p = (PyTupleObject *)(p->ob_item[0]);
905 14706 : PyObject_GC_Del(q);
906 : }
907 : }
908 : #endif
909 6 : return freelist_size;
910 : }
911 :
912 : void
913 3 : PyTuple_Fini(void)
914 : {
915 : #if PyTuple_MAXSAVESIZE > 0
916 : /* empty tuples are used all over the place and applications may
917 : * rely on the fact that an empty tuple is a singleton. */
918 3 : Py_CLEAR(free_list[0]);
919 :
920 3 : (void)PyTuple_ClearFreeList();
921 : #endif
922 : #ifdef SHOW_TRACK_COUNT
923 : show_track();
924 : #endif
925 3 : }
926 :
927 : /*********************** Tuple Iterator **************************/
928 :
929 : typedef struct {
930 : PyObject_HEAD
931 : long it_index;
932 : PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */
933 : } tupleiterobject;
934 :
935 : static void
936 6908 : tupleiter_dealloc(tupleiterobject *it)
937 : {
938 6908 : _PyObject_GC_UNTRACK(it);
939 6908 : Py_XDECREF(it->it_seq);
940 6908 : PyObject_GC_Del(it);
941 6908 : }
942 :
943 : static int
944 6 : tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)
945 : {
946 6 : Py_VISIT(it->it_seq);
947 6 : return 0;
948 : }
949 :
950 : static PyObject *
951 17716 : tupleiter_next(tupleiterobject *it)
952 : {
953 : PyTupleObject *seq;
954 : PyObject *item;
955 :
956 : assert(it != NULL);
957 17716 : seq = it->it_seq;
958 17716 : if (seq == NULL)
959 0 : return NULL;
960 : assert(PyTuple_Check(seq));
961 :
962 17716 : if (it->it_index < PyTuple_GET_SIZE(seq)) {
963 12521 : item = PyTuple_GET_ITEM(seq, it->it_index);
964 12521 : ++it->it_index;
965 12521 : Py_INCREF(item);
966 12521 : return item;
967 : }
968 :
969 5195 : it->it_seq = NULL;
970 5195 : Py_DECREF(seq);
971 5195 : return NULL;
972 : }
973 :
974 : static PyObject *
975 0 : tupleiter_len(tupleiterobject *it)
976 : {
977 0 : Py_ssize_t len = 0;
978 0 : if (it->it_seq)
979 0 : len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
980 0 : return PyInt_FromSsize_t(len);
981 : }
982 :
983 : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
984 :
985 : static PyMethodDef tupleiter_methods[] = {
986 : {"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},
987 : {NULL, NULL} /* sentinel */
988 : };
989 :
990 : PyTypeObject PyTupleIter_Type = {
991 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
992 : "tupleiterator", /* tp_name */
993 : sizeof(tupleiterobject), /* tp_basicsize */
994 : 0, /* tp_itemsize */
995 : /* methods */
996 : (destructor)tupleiter_dealloc, /* tp_dealloc */
997 : 0, /* tp_print */
998 : 0, /* tp_getattr */
999 : 0, /* tp_setattr */
1000 : 0, /* tp_compare */
1001 : 0, /* tp_repr */
1002 : 0, /* tp_as_number */
1003 : 0, /* tp_as_sequence */
1004 : 0, /* tp_as_mapping */
1005 : 0, /* tp_hash */
1006 : 0, /* tp_call */
1007 : 0, /* tp_str */
1008 : PyObject_GenericGetAttr, /* tp_getattro */
1009 : 0, /* tp_setattro */
1010 : 0, /* tp_as_buffer */
1011 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1012 : 0, /* tp_doc */
1013 : (traverseproc)tupleiter_traverse, /* tp_traverse */
1014 : 0, /* tp_clear */
1015 : 0, /* tp_richcompare */
1016 : 0, /* tp_weaklistoffset */
1017 : PyObject_SelfIter, /* tp_iter */
1018 : (iternextfunc)tupleiter_next, /* tp_iternext */
1019 : tupleiter_methods, /* tp_methods */
1020 : 0,
1021 : };
1022 :
1023 : static PyObject *
1024 6908 : tuple_iter(PyObject *seq)
1025 : {
1026 : tupleiterobject *it;
1027 :
1028 6908 : if (!PyTuple_Check(seq)) {
1029 0 : PyErr_BadInternalCall();
1030 0 : return NULL;
1031 : }
1032 6908 : it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
1033 6908 : if (it == NULL)
1034 0 : return NULL;
1035 6908 : it->it_index = 0;
1036 6908 : Py_INCREF(seq);
1037 6908 : it->it_seq = (PyTupleObject *)seq;
1038 6908 : _PyObject_GC_TRACK(it);
1039 6908 : return (PyObject *)it;
1040 : }
|
