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