Line data Source code
1 :
2 : /* Tuple object implementation */
3 :
4 : #include "Python.h"
5 : #include "pycore_abstract.h" // _PyIndex_Check()
6 : #include "pycore_gc.h" // _PyObject_GC_IS_TRACKED()
7 : #include "pycore_initconfig.h" // _PyStatus_OK()
8 : #include "pycore_object.h" // _PyObject_GC_TRACK(), _Py_FatalRefcountError()
9 :
10 : /*[clinic input]
11 : class tuple "PyTupleObject *" "&PyTuple_Type"
12 : [clinic start generated code]*/
13 : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f051ba3cfdf9a189]*/
14 :
15 : #include "clinic/tupleobject.c.h"
16 :
17 :
18 : static inline PyTupleObject * maybe_freelist_pop(Py_ssize_t);
19 : static inline int maybe_freelist_push(PyTupleObject *);
20 :
21 :
22 : /* Allocate an uninitialized tuple object. Before making it public, following
23 : steps must be done:
24 :
25 : - Initialize its items.
26 : - Call _PyObject_GC_TRACK() on it.
27 :
28 : Because the empty tuple is always reused and it's already tracked by GC,
29 : this function must not be called with size == 0 (unless from PyTuple_New()
30 : which wraps this function).
31 : */
32 : static PyTupleObject *
33 284395000 : tuple_alloc(Py_ssize_t size)
34 : {
35 284395000 : if (size < 0) {
36 0 : PyErr_BadInternalCall();
37 0 : return NULL;
38 : }
39 : #ifdef Py_DEBUG
40 284395000 : assert(size != 0); // The empty tuple is statically allocated.
41 : #endif
42 :
43 284395000 : PyTupleObject *op = maybe_freelist_pop(size);
44 284395000 : if (op == NULL) {
45 : /* Check for overflow */
46 38252500 : if ((size_t)size > ((size_t)PY_SSIZE_T_MAX - (sizeof(PyTupleObject) -
47 : sizeof(PyObject *))) / sizeof(PyObject *)) {
48 0 : return (PyTupleObject *)PyErr_NoMemory();
49 : }
50 38252500 : op = PyObject_GC_NewVar(PyTupleObject, &PyTuple_Type, size);
51 38252500 : if (op == NULL)
52 0 : return NULL;
53 : }
54 284395000 : return op;
55 : }
56 :
57 : // The empty tuple singleton is not tracked by the GC.
58 : // It does not contain any Python object.
59 : // Note that tuple subclasses have their own empty instances.
60 :
61 : static inline PyObject *
62 25014100 : tuple_get_empty(void)
63 : {
64 25014100 : Py_INCREF(&_Py_SINGLETON(tuple_empty));
65 25014100 : return (PyObject *)&_Py_SINGLETON(tuple_empty);
66 : }
67 :
68 : PyObject *
69 145898000 : PyTuple_New(Py_ssize_t size)
70 : {
71 : PyTupleObject *op;
72 145898000 : if (size == 0) {
73 6788810 : return tuple_get_empty();
74 : }
75 139109000 : op = tuple_alloc(size);
76 139109000 : if (op == NULL) {
77 0 : return NULL;
78 : }
79 560208000 : for (Py_ssize_t i = 0; i < size; i++) {
80 421099000 : op->ob_item[i] = NULL;
81 : }
82 139109000 : _PyObject_GC_TRACK(op);
83 139109000 : return (PyObject *) op;
84 : }
85 :
86 : Py_ssize_t
87 19572100 : PyTuple_Size(PyObject *op)
88 : {
89 19572100 : if (!PyTuple_Check(op)) {
90 0 : PyErr_BadInternalCall();
91 0 : return -1;
92 : }
93 : else
94 19572100 : return Py_SIZE(op);
95 : }
96 :
97 : PyObject *
98 1064890000 : PyTuple_GetItem(PyObject *op, Py_ssize_t i)
99 : {
100 1064890000 : if (!PyTuple_Check(op)) {
101 0 : PyErr_BadInternalCall();
102 0 : return NULL;
103 : }
104 1064890000 : if (i < 0 || i >= Py_SIZE(op)) {
105 2 : PyErr_SetString(PyExc_IndexError, "tuple index out of range");
106 2 : return NULL;
107 : }
108 1064890000 : return ((PyTupleObject *)op) -> ob_item[i];
109 : }
110 :
111 : int
112 86 : PyTuple_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem)
113 : {
114 : PyObject **p;
115 86 : if (!PyTuple_Check(op) || Py_REFCNT(op) != 1) {
116 0 : Py_XDECREF(newitem);
117 0 : PyErr_BadInternalCall();
118 0 : return -1;
119 : }
120 86 : if (i < 0 || i >= Py_SIZE(op)) {
121 0 : Py_XDECREF(newitem);
122 0 : PyErr_SetString(PyExc_IndexError,
123 : "tuple assignment index out of range");
124 0 : return -1;
125 : }
126 86 : p = ((PyTupleObject *)op) -> ob_item + i;
127 86 : Py_XSETREF(*p, newitem);
128 86 : return 0;
129 : }
130 :
131 : void
132 83333300 : _PyTuple_MaybeUntrack(PyObject *op)
133 : {
134 : PyTupleObject *t;
135 : Py_ssize_t i, n;
136 :
137 83333300 : if (!PyTuple_CheckExact(op) || !_PyObject_GC_IS_TRACKED(op))
138 0 : return;
139 83333300 : t = (PyTupleObject *) op;
140 83333300 : n = Py_SIZE(t);
141 233880000 : for (i = 0; i < n; i++) {
142 197318000 : PyObject *elt = PyTuple_GET_ITEM(t, i);
143 : /* Tuple with NULL elements aren't
144 : fully constructed, don't untrack
145 : them yet. */
146 394622000 : if (!elt ||
147 197304000 : _PyObject_GC_MAY_BE_TRACKED(elt))
148 46770600 : return;
149 : }
150 36562700 : _PyObject_GC_UNTRACK(op);
151 : }
152 :
153 : PyObject *
154 10870700 : PyTuple_Pack(Py_ssize_t n, ...)
155 : {
156 : Py_ssize_t i;
157 : PyObject *o;
158 : PyObject **items;
159 : va_list vargs;
160 :
161 10870700 : if (n == 0) {
162 0 : return tuple_get_empty();
163 : }
164 :
165 10870700 : va_start(vargs, n);
166 10870700 : PyTupleObject *result = tuple_alloc(n);
167 10870700 : if (result == NULL) {
168 0 : va_end(vargs);
169 0 : return NULL;
170 : }
171 10870700 : items = result->ob_item;
172 28198900 : for (i = 0; i < n; i++) {
173 17328200 : o = va_arg(vargs, PyObject *);
174 17328200 : Py_INCREF(o);
175 17328200 : items[i] = o;
176 : }
177 10870700 : va_end(vargs);
178 10870700 : _PyObject_GC_TRACK(result);
179 10870700 : return (PyObject *)result;
180 : }
181 :
182 :
183 : /* Methods */
184 :
185 : static void
186 291945000 : tupledealloc(PyTupleObject *op)
187 : {
188 291945000 : if (Py_SIZE(op) == 0) {
189 : /* The empty tuple is statically allocated. */
190 43 : if (op == &_Py_SINGLETON(tuple_empty)) {
191 : #ifdef Py_DEBUG
192 0 : _Py_FatalRefcountError("deallocating the empty tuple singleton");
193 : #else
194 : return;
195 : #endif
196 : }
197 : #ifdef Py_DEBUG
198 : /* tuple subclasses have their own empty instances. */
199 43 : assert(!PyTuple_CheckExact(op));
200 : #endif
201 : }
202 :
203 291945000 : PyObject_GC_UnTrack(op);
204 291945000 : Py_TRASHCAN_BEGIN(op, tupledealloc)
205 :
206 291944000 : Py_ssize_t i = Py_SIZE(op);
207 1013470000 : while (--i >= 0) {
208 721526000 : Py_XDECREF(op->ob_item[i]);
209 : }
210 : // This will abort on the empty singleton (if there is one).
211 291944000 : if (!maybe_freelist_push(op)) {
212 23272900 : Py_TYPE(op)->tp_free((PyObject *)op);
213 : }
214 :
215 291944000 : Py_TRASHCAN_END
216 291945000 : }
217 :
218 : static PyObject *
219 24822 : tuplerepr(PyTupleObject *v)
220 : {
221 : Py_ssize_t i, n;
222 : _PyUnicodeWriter writer;
223 :
224 24822 : n = Py_SIZE(v);
225 24822 : if (n == 0)
226 1630 : return PyUnicode_FromString("()");
227 :
228 : /* While not mutable, it is still possible to end up with a cycle in a
229 : tuple through an object that stores itself within a tuple (and thus
230 : infinitely asks for the repr of itself). This should only be
231 : possible within a type. */
232 23192 : i = Py_ReprEnter((PyObject *)v);
233 23192 : if (i != 0) {
234 0 : return i > 0 ? PyUnicode_FromString("(...)") : NULL;
235 : }
236 :
237 23192 : _PyUnicodeWriter_Init(&writer);
238 23192 : writer.overallocate = 1;
239 23192 : if (Py_SIZE(v) > 1) {
240 : /* "(" + "1" + ", 2" * (len - 1) + ")" */
241 19340 : writer.min_length = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;
242 : }
243 : else {
244 : /* "(1,)" */
245 3852 : writer.min_length = 4;
246 : }
247 :
248 23192 : if (_PyUnicodeWriter_WriteChar(&writer, '(') < 0)
249 0 : goto error;
250 :
251 : /* Do repr() on each element. */
252 1151570 : for (i = 0; i < n; ++i) {
253 : PyObject *s;
254 :
255 1128380 : if (i > 0) {
256 1105180 : if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0)
257 0 : goto error;
258 : }
259 :
260 1128380 : s = PyObject_Repr(v->ob_item[i]);
261 1128380 : if (s == NULL)
262 0 : goto error;
263 :
264 1128380 : if (_PyUnicodeWriter_WriteStr(&writer, s) < 0) {
265 0 : Py_DECREF(s);
266 0 : goto error;
267 : }
268 1128380 : Py_DECREF(s);
269 : }
270 :
271 23192 : writer.overallocate = 0;
272 23192 : if (n > 1) {
273 19340 : if (_PyUnicodeWriter_WriteChar(&writer, ')') < 0)
274 0 : goto error;
275 : }
276 : else {
277 3852 : if (_PyUnicodeWriter_WriteASCIIString(&writer, ",)", 2) < 0)
278 0 : goto error;
279 : }
280 :
281 23192 : Py_ReprLeave((PyObject *)v);
282 23192 : return _PyUnicodeWriter_Finish(&writer);
283 :
284 0 : error:
285 0 : _PyUnicodeWriter_Dealloc(&writer);
286 0 : Py_ReprLeave((PyObject *)v);
287 0 : return NULL;
288 : }
289 :
290 :
291 : /* Hash for tuples. This is a slightly simplified version of the xxHash
292 : non-cryptographic hash:
293 : - we do not use any parallellism, there is only 1 accumulator.
294 : - we drop the final mixing since this is just a permutation of the
295 : output space: it does not help against collisions.
296 : - at the end, we mangle the length with a single constant.
297 : For the xxHash specification, see
298 : https://github.com/Cyan4973/xxHash/blob/master/doc/xxhash_spec.md
299 :
300 : Below are the official constants from the xxHash specification. Optimizing
301 : compilers should emit a single "rotate" instruction for the
302 : _PyHASH_XXROTATE() expansion. If that doesn't happen for some important
303 : platform, the macro could be changed to expand to a platform-specific rotate
304 : spelling instead.
305 : */
306 : #if SIZEOF_PY_UHASH_T > 4
307 : #define _PyHASH_XXPRIME_1 ((Py_uhash_t)11400714785074694791ULL)
308 : #define _PyHASH_XXPRIME_2 ((Py_uhash_t)14029467366897019727ULL)
309 : #define _PyHASH_XXPRIME_5 ((Py_uhash_t)2870177450012600261ULL)
310 : #define _PyHASH_XXROTATE(x) ((x << 31) | (x >> 33)) /* Rotate left 31 bits */
311 : #else
312 : #define _PyHASH_XXPRIME_1 ((Py_uhash_t)2654435761UL)
313 : #define _PyHASH_XXPRIME_2 ((Py_uhash_t)2246822519UL)
314 : #define _PyHASH_XXPRIME_5 ((Py_uhash_t)374761393UL)
315 : #define _PyHASH_XXROTATE(x) ((x << 13) | (x >> 19)) /* Rotate left 13 bits */
316 : #endif
317 :
318 : /* Tests have shown that it's not worth to cache the hash value, see
319 : https://bugs.python.org/issue9685 */
320 : static Py_hash_t
321 24761900 : tuplehash(PyTupleObject *v)
322 : {
323 24761900 : Py_ssize_t i, len = Py_SIZE(v);
324 24761900 : PyObject **item = v->ob_item;
325 :
326 24761900 : Py_uhash_t acc = _PyHASH_XXPRIME_5;
327 107499000 : for (i = 0; i < len; i++) {
328 82736900 : Py_uhash_t lane = PyObject_Hash(item[i]);
329 82736900 : if (lane == (Py_uhash_t)-1) {
330 60 : return -1;
331 : }
332 82736800 : acc += lane * _PyHASH_XXPRIME_2;
333 82736800 : acc = _PyHASH_XXROTATE(acc);
334 82736800 : acc *= _PyHASH_XXPRIME_1;
335 : }
336 :
337 : /* Add input length, mangled to keep the historical value of hash(()). */
338 24761900 : acc += len ^ (_PyHASH_XXPRIME_5 ^ 3527539UL);
339 :
340 24761900 : if (acc == (Py_uhash_t)-1) {
341 0 : return 1546275796;
342 : }
343 24761900 : return acc;
344 : }
345 :
346 : static Py_ssize_t
347 13300500 : tuplelength(PyTupleObject *a)
348 : {
349 13300500 : return Py_SIZE(a);
350 : }
351 :
352 : static int
353 12994000 : tuplecontains(PyTupleObject *a, PyObject *el)
354 : {
355 : Py_ssize_t i;
356 : int cmp;
357 :
358 42711900 : for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
359 29717900 : cmp = PyObject_RichCompareBool(PyTuple_GET_ITEM(a, i), el, Py_EQ);
360 12994000 : return cmp;
361 : }
362 :
363 : static PyObject *
364 3878750 : tupleitem(PyTupleObject *a, Py_ssize_t i)
365 : {
366 3878750 : if (i < 0 || i >= Py_SIZE(a)) {
367 6780 : PyErr_SetString(PyExc_IndexError, "tuple index out of range");
368 6780 : return NULL;
369 : }
370 3871970 : Py_INCREF(a->ob_item[i]);
371 3871970 : return a->ob_item[i];
372 : }
373 :
374 : PyObject *
375 119708000 : _PyTuple_FromArray(PyObject *const *src, Py_ssize_t n)
376 : {
377 119708000 : if (n == 0) {
378 14230700 : return tuple_get_empty();
379 : }
380 :
381 105477000 : PyTupleObject *tuple = tuple_alloc(n);
382 105477000 : if (tuple == NULL) {
383 0 : return NULL;
384 : }
385 105477000 : PyObject **dst = tuple->ob_item;
386 300816000 : for (Py_ssize_t i = 0; i < n; i++) {
387 195339000 : PyObject *item = src[i];
388 195339000 : Py_INCREF(item);
389 195339000 : dst[i] = item;
390 : }
391 105477000 : _PyObject_GC_TRACK(tuple);
392 105477000 : return (PyObject *)tuple;
393 : }
394 :
395 : PyObject *
396 20426600 : _PyTuple_FromArraySteal(PyObject *const *src, Py_ssize_t n)
397 : {
398 20426600 : if (n == 0) {
399 1063420 : return tuple_get_empty();
400 : }
401 19363200 : PyTupleObject *tuple = tuple_alloc(n);
402 19363200 : if (tuple == NULL) {
403 0 : for (Py_ssize_t i = 0; i < n; i++) {
404 0 : Py_DECREF(src[i]);
405 : }
406 0 : return NULL;
407 : }
408 19363200 : PyObject **dst = tuple->ob_item;
409 47612100 : for (Py_ssize_t i = 0; i < n; i++) {
410 28248800 : PyObject *item = src[i];
411 28248800 : dst[i] = item;
412 : }
413 19363200 : _PyObject_GC_TRACK(tuple);
414 19363200 : return (PyObject *)tuple;
415 : }
416 :
417 : static PyObject *
418 15057700 : tupleslice(PyTupleObject *a, Py_ssize_t ilow,
419 : Py_ssize_t ihigh)
420 : {
421 15057700 : if (ilow < 0)
422 0 : ilow = 0;
423 15057700 : if (ihigh > Py_SIZE(a))
424 77157 : ihigh = Py_SIZE(a);
425 15057700 : if (ihigh < ilow)
426 0 : ihigh = ilow;
427 15057700 : if (ilow == 0 && ihigh == Py_SIZE(a) && PyTuple_CheckExact(a)) {
428 0 : Py_INCREF(a);
429 0 : return (PyObject *)a;
430 : }
431 15057700 : return _PyTuple_FromArray(a->ob_item + ilow, ihigh - ilow);
432 : }
433 :
434 : PyObject *
435 15057500 : PyTuple_GetSlice(PyObject *op, Py_ssize_t i, Py_ssize_t j)
436 : {
437 15057500 : if (op == NULL || !PyTuple_Check(op)) {
438 0 : PyErr_BadInternalCall();
439 0 : return NULL;
440 : }
441 15057500 : return tupleslice((PyTupleObject *)op, i, j);
442 : }
443 :
444 : static PyObject *
445 195430 : tupleconcat(PyTupleObject *a, PyObject *bb)
446 : {
447 : Py_ssize_t size;
448 : Py_ssize_t i;
449 : PyObject **src, **dest;
450 : PyTupleObject *np;
451 195430 : if (Py_SIZE(a) == 0 && PyTuple_CheckExact(bb)) {
452 56810 : Py_INCREF(bb);
453 56810 : return bb;
454 : }
455 138620 : if (!PyTuple_Check(bb)) {
456 1 : PyErr_Format(PyExc_TypeError,
457 : "can only concatenate tuple (not \"%.200s\") to tuple",
458 1 : Py_TYPE(bb)->tp_name);
459 1 : return NULL;
460 : }
461 138619 : PyTupleObject *b = (PyTupleObject *)bb;
462 :
463 138619 : if (Py_SIZE(b) == 0 && PyTuple_CheckExact(a)) {
464 10987 : Py_INCREF(a);
465 10987 : return (PyObject *)a;
466 : }
467 127632 : assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
468 127632 : size = Py_SIZE(a) + Py_SIZE(b);
469 127632 : if (size == 0) {
470 1 : return tuple_get_empty();
471 : }
472 :
473 127631 : np = tuple_alloc(size);
474 127631 : if (np == NULL) {
475 0 : return NULL;
476 : }
477 127631 : src = a->ob_item;
478 127631 : dest = np->ob_item;
479 775631 : for (i = 0; i < Py_SIZE(a); i++) {
480 648000 : PyObject *v = src[i];
481 648000 : Py_INCREF(v);
482 648000 : dest[i] = v;
483 : }
484 127631 : src = b->ob_item;
485 127631 : dest = np->ob_item + Py_SIZE(a);
486 349645 : for (i = 0; i < Py_SIZE(b); i++) {
487 222014 : PyObject *v = src[i];
488 222014 : Py_INCREF(v);
489 222014 : dest[i] = v;
490 : }
491 127631 : _PyObject_GC_TRACK(np);
492 127631 : return (PyObject *)np;
493 : }
494 :
495 : static PyObject *
496 14801 : tuplerepeat(PyTupleObject *a, Py_ssize_t n)
497 : {
498 : Py_ssize_t size;
499 : PyTupleObject *np;
500 14801 : if (Py_SIZE(a) == 0 || n == 1) {
501 9374 : if (PyTuple_CheckExact(a)) {
502 : /* Since tuples are immutable, we can return a shared
503 : copy in this case */
504 9368 : Py_INCREF(a);
505 9368 : return (PyObject *)a;
506 : }
507 : }
508 5433 : if (Py_SIZE(a) == 0 || n <= 0) {
509 3990 : return tuple_get_empty();
510 : }
511 1443 : if (n > PY_SSIZE_T_MAX / Py_SIZE(a))
512 0 : return PyErr_NoMemory();
513 1443 : size = Py_SIZE(a) * n;
514 1443 : np = tuple_alloc(size);
515 1443 : if (np == NULL)
516 0 : return NULL;
517 1443 : PyObject **dest = np->ob_item;
518 1443 : PyObject **dest_end = dest + size;
519 1443 : if (Py_SIZE(a) == 1) {
520 1376 : PyObject *elem = a->ob_item[0];
521 1376 : Py_SET_REFCNT(elem, Py_REFCNT(elem) + n);
522 : #ifdef Py_REF_DEBUG
523 1376 : _Py_RefTotal += n;
524 : #endif
525 1092510 : while (dest < dest_end) {
526 1091140 : *dest++ = elem;
527 : }
528 : }
529 : else {
530 67 : PyObject **src = a->ob_item;
531 67 : PyObject **src_end = src + Py_SIZE(a);
532 15731 : while (src < src_end) {
533 15664 : Py_SET_REFCNT(*src, Py_REFCNT(*src) + n);
534 : #ifdef Py_REF_DEBUG
535 15664 : _Py_RefTotal += n;
536 : #endif
537 15664 : *dest++ = *src++;
538 : }
539 : // Now src chases after dest in the same buffer
540 67 : src = np->ob_item;
541 41700 : while (dest < dest_end) {
542 41633 : *dest++ = *src++;
543 : }
544 : }
545 1443 : _PyObject_GC_TRACK(np);
546 1443 : return (PyObject *) np;
547 : }
548 :
549 : /*[clinic input]
550 : tuple.index
551 :
552 : value: object
553 : start: slice_index(accept={int}) = 0
554 : stop: slice_index(accept={int}, c_default="PY_SSIZE_T_MAX") = sys.maxsize
555 : /
556 :
557 : Return first index of value.
558 :
559 : Raises ValueError if the value is not present.
560 : [clinic start generated code]*/
561 :
562 : static PyObject *
563 1719 : tuple_index_impl(PyTupleObject *self, PyObject *value, Py_ssize_t start,
564 : Py_ssize_t stop)
565 : /*[clinic end generated code: output=07b6f9f3cb5c33eb input=fb39e9874a21fe3f]*/
566 : {
567 : Py_ssize_t i;
568 :
569 1719 : if (start < 0) {
570 6 : start += Py_SIZE(self);
571 6 : if (start < 0)
572 3 : start = 0;
573 : }
574 1719 : if (stop < 0) {
575 4 : stop += Py_SIZE(self);
576 : }
577 1715 : else if (stop > Py_SIZE(self)) {
578 1713 : stop = Py_SIZE(self);
579 : }
580 2116 : for (i = start; i < stop; i++) {
581 2110 : int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
582 2110 : if (cmp > 0)
583 1712 : return PyLong_FromSsize_t(i);
584 398 : else if (cmp < 0)
585 1 : return NULL;
586 : }
587 6 : PyErr_SetString(PyExc_ValueError, "tuple.index(x): x not in tuple");
588 6 : return NULL;
589 : }
590 :
591 : /*[clinic input]
592 : tuple.count
593 :
594 : value: object
595 : /
596 :
597 : Return number of occurrences of value.
598 : [clinic start generated code]*/
599 :
600 : static PyObject *
601 183 : tuple_count(PyTupleObject *self, PyObject *value)
602 : /*[clinic end generated code: output=aa927affc5a97605 input=531721aff65bd772]*/
603 : {
604 183 : Py_ssize_t count = 0;
605 : Py_ssize_t i;
606 :
607 785 : for (i = 0; i < Py_SIZE(self); i++) {
608 603 : int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
609 603 : if (cmp > 0)
610 341 : count++;
611 262 : else if (cmp < 0)
612 1 : return NULL;
613 : }
614 182 : return PyLong_FromSsize_t(count);
615 : }
616 :
617 : static int
618 186433000 : tupletraverse(PyTupleObject *o, visitproc visit, void *arg)
619 : {
620 : Py_ssize_t i;
621 :
622 802707000 : for (i = Py_SIZE(o); --i >= 0; )
623 616275000 : Py_VISIT(o->ob_item[i]);
624 186433000 : return 0;
625 : }
626 :
627 : static PyObject *
628 15020200 : tuplerichcompare(PyObject *v, PyObject *w, int op)
629 : {
630 : PyTupleObject *vt, *wt;
631 : Py_ssize_t i;
632 : Py_ssize_t vlen, wlen;
633 :
634 15020200 : if (!PyTuple_Check(v) || !PyTuple_Check(w))
635 33478 : Py_RETURN_NOTIMPLEMENTED;
636 :
637 14986700 : vt = (PyTupleObject *)v;
638 14986700 : wt = (PyTupleObject *)w;
639 :
640 14986700 : vlen = Py_SIZE(vt);
641 14986700 : wlen = Py_SIZE(wt);
642 :
643 : /* Note: the corresponding code for lists has an "early out" test
644 : * here when op is EQ or NE and the lengths differ. That pays there,
645 : * but Tim was unable to find any real code where EQ/NE tuple
646 : * compares don't have the same length, so testing for it here would
647 : * have cost without benefit.
648 : */
649 :
650 : /* Search for the first index where items are different.
651 : * Note that because tuples are immutable, it's safe to reuse
652 : * vlen and wlen across the comparison calls.
653 : */
654 39279600 : for (i = 0; i < vlen && i < wlen; i++) {
655 27904000 : int k = PyObject_RichCompareBool(vt->ob_item[i],
656 : wt->ob_item[i], Py_EQ);
657 27904000 : if (k < 0)
658 2906 : return NULL;
659 27901100 : if (!k)
660 3608240 : break;
661 : }
662 :
663 14983800 : if (i >= vlen || i >= wlen) {
664 : /* No more items to compare -- compare sizes */
665 11375600 : Py_RETURN_RICHCOMPARE(vlen, wlen, op);
666 : }
667 :
668 : /* We have an item that differs -- shortcuts for EQ/NE */
669 3608240 : if (op == Py_EQ) {
670 2731160 : Py_RETURN_FALSE;
671 : }
672 877082 : if (op == Py_NE) {
673 153124 : Py_RETURN_TRUE;
674 : }
675 :
676 : /* Compare the final item again using the proper operator */
677 723958 : return PyObject_RichCompare(vt->ob_item[i], wt->ob_item[i], op);
678 : }
679 :
680 : static PyObject *
681 : tuple_subtype_new(PyTypeObject *type, PyObject *iterable);
682 :
683 : /*[clinic input]
684 : @classmethod
685 : tuple.__new__ as tuple_new
686 : iterable: object(c_default="NULL") = ()
687 : /
688 :
689 : Built-in immutable sequence.
690 :
691 : If no argument is given, the constructor returns an empty tuple.
692 : If iterable is specified the tuple is initialized from iterable's items.
693 :
694 : If the argument is a tuple, the return value is the same object.
695 : [clinic start generated code]*/
696 :
697 : static PyObject *
698 15925200 : tuple_new_impl(PyTypeObject *type, PyObject *iterable)
699 : /*[clinic end generated code: output=4546d9f0d469bce7 input=86963bcde633b5a2]*/
700 : {
701 15925200 : if (type != &PyTuple_Type)
702 7908050 : return tuple_subtype_new(type, iterable);
703 :
704 8017140 : if (iterable == NULL) {
705 30 : return tuple_get_empty();
706 : }
707 : else {
708 8017110 : return PySequence_Tuple(iterable);
709 : }
710 : }
711 :
712 : static PyObject *
713 109398 : tuple_vectorcall(PyObject *type, PyObject * const*args,
714 : size_t nargsf, PyObject *kwnames)
715 : {
716 109398 : if (!_PyArg_NoKwnames("tuple", kwnames)) {
717 4 : return NULL;
718 : }
719 :
720 109394 : Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);
721 109394 : if (!_PyArg_CheckPositional("tuple", nargs, 0, 1)) {
722 0 : return NULL;
723 : }
724 :
725 109394 : if (nargs) {
726 109084 : return tuple_new_impl(_PyType_CAST(type), args[0]);
727 : }
728 : else {
729 310 : return tuple_get_empty();
730 : }
731 : }
732 :
733 : static PyObject *
734 7908050 : tuple_subtype_new(PyTypeObject *type, PyObject *iterable)
735 : {
736 : PyObject *tmp, *newobj, *item;
737 : Py_ssize_t i, n;
738 :
739 7908050 : assert(PyType_IsSubtype(type, &PyTuple_Type));
740 : // tuple subclasses must implement the GC protocol
741 7908050 : assert(_PyType_IS_GC(type));
742 :
743 7908050 : tmp = tuple_new_impl(&PyTuple_Type, iterable);
744 7908050 : if (tmp == NULL)
745 0 : return NULL;
746 7908050 : assert(PyTuple_Check(tmp));
747 : /* This may allocate an empty tuple that is not the global one. */
748 7908050 : newobj = type->tp_alloc(type, n = PyTuple_GET_SIZE(tmp));
749 7908050 : if (newobj == NULL) {
750 0 : Py_DECREF(tmp);
751 0 : return NULL;
752 : }
753 47675400 : for (i = 0; i < n; i++) {
754 39767300 : item = PyTuple_GET_ITEM(tmp, i);
755 39767300 : Py_INCREF(item);
756 39767300 : PyTuple_SET_ITEM(newobj, i, item);
757 : }
758 7908050 : Py_DECREF(tmp);
759 :
760 : // Don't track if a subclass tp_alloc is PyType_GenericAlloc()
761 7908050 : if (!_PyObject_GC_IS_TRACKED(newobj)) {
762 0 : _PyObject_GC_TRACK(newobj);
763 : }
764 7908050 : return newobj;
765 : }
766 :
767 : static PySequenceMethods tuple_as_sequence = {
768 : (lenfunc)tuplelength, /* sq_length */
769 : (binaryfunc)tupleconcat, /* sq_concat */
770 : (ssizeargfunc)tuplerepeat, /* sq_repeat */
771 : (ssizeargfunc)tupleitem, /* sq_item */
772 : 0, /* sq_slice */
773 : 0, /* sq_ass_item */
774 : 0, /* sq_ass_slice */
775 : (objobjproc)tuplecontains, /* sq_contains */
776 : };
777 :
778 : static PyObject*
779 17426400 : tuplesubscript(PyTupleObject* self, PyObject* item)
780 : {
781 17426400 : if (_PyIndex_Check(item)) {
782 2671160 : Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
783 2671160 : if (i == -1 && PyErr_Occurred())
784 2 : return NULL;
785 2671160 : if (i < 0)
786 1847500 : i += PyTuple_GET_SIZE(self);
787 2671160 : return tupleitem(self, i);
788 : }
789 14755300 : else if (PySlice_Check(item)) {
790 : Py_ssize_t start, stop, step, slicelength, i;
791 : size_t cur;
792 : PyObject* it;
793 : PyObject **src, **dest;
794 :
795 14755300 : if (PySlice_Unpack(item, &start, &stop, &step) < 0) {
796 4 : return NULL;
797 : }
798 14755300 : slicelength = PySlice_AdjustIndices(PyTuple_GET_SIZE(self), &start,
799 : &stop, step);
800 :
801 14755300 : if (slicelength <= 0) {
802 2915600 : return tuple_get_empty();
803 : }
804 21417000 : else if (start == 0 && step == 1 &&
805 11970800 : slicelength == PyTuple_GET_SIZE(self) &&
806 2393450 : PyTuple_CheckExact(self)) {
807 2393420 : Py_INCREF(self);
808 2393420 : return (PyObject *)self;
809 : }
810 : else {
811 9446240 : PyTupleObject* result = tuple_alloc(slicelength);
812 9446240 : if (!result) return NULL;
813 :
814 9446240 : src = self->ob_item;
815 9446240 : dest = result->ob_item;
816 28743600 : for (cur = start, i = 0; i < slicelength;
817 19297300 : cur += step, i++) {
818 19297300 : it = src[cur];
819 19297300 : Py_INCREF(it);
820 19297300 : dest[i] = it;
821 : }
822 :
823 9446240 : _PyObject_GC_TRACK(result);
824 9446240 : return (PyObject *)result;
825 : }
826 : }
827 : else {
828 2 : PyErr_Format(PyExc_TypeError,
829 : "tuple indices must be integers or slices, not %.200s",
830 2 : Py_TYPE(item)->tp_name);
831 2 : return NULL;
832 : }
833 : }
834 :
835 : /*[clinic input]
836 : tuple.__getnewargs__
837 : [clinic start generated code]*/
838 :
839 : static PyObject *
840 146 : tuple___getnewargs___impl(PyTupleObject *self)
841 : /*[clinic end generated code: output=25e06e3ee56027e2 input=1aeb4b286a21639a]*/
842 : {
843 146 : return Py_BuildValue("(N)", tupleslice(self, 0, Py_SIZE(self)));
844 : }
845 :
846 : static PyMethodDef tuple_methods[] = {
847 : TUPLE___GETNEWARGS___METHODDEF
848 : TUPLE_INDEX_METHODDEF
849 : TUPLE_COUNT_METHODDEF
850 : {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
851 : {NULL, NULL} /* sentinel */
852 : };
853 :
854 : static PyMappingMethods tuple_as_mapping = {
855 : (lenfunc)tuplelength,
856 : (binaryfunc)tuplesubscript,
857 : 0
858 : };
859 :
860 : static PyObject *tuple_iter(PyObject *seq);
861 :
862 : PyTypeObject PyTuple_Type = {
863 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
864 : "tuple",
865 : sizeof(PyTupleObject) - sizeof(PyObject *),
866 : sizeof(PyObject *),
867 : (destructor)tupledealloc, /* tp_dealloc */
868 : 0, /* tp_vectorcall_offset */
869 : 0, /* tp_getattr */
870 : 0, /* tp_setattr */
871 : 0, /* tp_as_async */
872 : (reprfunc)tuplerepr, /* tp_repr */
873 : 0, /* tp_as_number */
874 : &tuple_as_sequence, /* tp_as_sequence */
875 : &tuple_as_mapping, /* tp_as_mapping */
876 : (hashfunc)tuplehash, /* tp_hash */
877 : 0, /* tp_call */
878 : 0, /* tp_str */
879 : PyObject_GenericGetAttr, /* tp_getattro */
880 : 0, /* tp_setattro */
881 : 0, /* tp_as_buffer */
882 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
883 : Py_TPFLAGS_BASETYPE | Py_TPFLAGS_TUPLE_SUBCLASS |
884 : _Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_SEQUENCE, /* tp_flags */
885 : tuple_new__doc__, /* tp_doc */
886 : (traverseproc)tupletraverse, /* tp_traverse */
887 : 0, /* tp_clear */
888 : tuplerichcompare, /* tp_richcompare */
889 : 0, /* tp_weaklistoffset */
890 : tuple_iter, /* tp_iter */
891 : 0, /* tp_iternext */
892 : tuple_methods, /* tp_methods */
893 : 0, /* tp_members */
894 : 0, /* tp_getset */
895 : 0, /* tp_base */
896 : 0, /* tp_dict */
897 : 0, /* tp_descr_get */
898 : 0, /* tp_descr_set */
899 : 0, /* tp_dictoffset */
900 : 0, /* tp_init */
901 : 0, /* tp_alloc */
902 : tuple_new, /* tp_new */
903 : PyObject_GC_Del, /* tp_free */
904 : .tp_vectorcall = tuple_vectorcall,
905 : };
906 :
907 : /* The following function breaks the notion that tuples are immutable:
908 : it changes the size of a tuple. We get away with this only if there
909 : is only one module referencing the object. You can also think of it
910 : as creating a new tuple object and destroying the old one, only more
911 : efficiently. In any case, don't use this if the tuple may already be
912 : known to some other part of the code. */
913 :
914 : int
915 251706 : _PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
916 : {
917 : PyTupleObject *v;
918 : PyTupleObject *sv;
919 : Py_ssize_t i;
920 : Py_ssize_t oldsize;
921 :
922 251706 : v = (PyTupleObject *) *pv;
923 503412 : if (v == NULL || !Py_IS_TYPE(v, &PyTuple_Type) ||
924 503411 : (Py_SIZE(v) != 0 && Py_REFCNT(v) != 1)) {
925 0 : *pv = 0;
926 0 : Py_XDECREF(v);
927 0 : PyErr_BadInternalCall();
928 0 : return -1;
929 : }
930 :
931 251706 : oldsize = Py_SIZE(v);
932 251706 : if (oldsize == newsize) {
933 61920 : return 0;
934 : }
935 189786 : if (newsize == 0) {
936 11204 : Py_DECREF(v);
937 11204 : *pv = tuple_get_empty();
938 11204 : return 0;
939 : }
940 178582 : if (oldsize == 0) {
941 : #ifdef Py_DEBUG
942 0 : assert(v == &_Py_SINGLETON(tuple_empty));
943 : #endif
944 : /* The empty tuple is statically allocated so we never
945 : resize it in-place. */
946 0 : Py_DECREF(v);
947 0 : *pv = PyTuple_New(newsize);
948 0 : return *pv == NULL ? -1 : 0;
949 : }
950 :
951 : /* XXX UNREF/NEWREF interface should be more symmetrical */
952 : #ifdef Py_REF_DEBUG
953 178582 : _Py_RefTotal--;
954 : #endif
955 178582 : if (_PyObject_GC_IS_TRACKED(v)) {
956 178577 : _PyObject_GC_UNTRACK(v);
957 : }
958 : #ifdef Py_TRACE_REFS
959 : _Py_ForgetReference((PyObject *) v);
960 : #endif
961 : /* DECREF items deleted by shrinkage */
962 1526980 : for (i = newsize; i < oldsize; i++) {
963 1348400 : Py_CLEAR(v->ob_item[i]);
964 : }
965 178582 : sv = PyObject_GC_Resize(PyTupleObject, v, newsize);
966 178582 : if (sv == NULL) {
967 0 : *pv = NULL;
968 0 : PyObject_GC_Del(v);
969 0 : return -1;
970 : }
971 178582 : _Py_NewReference((PyObject *) sv);
972 : /* Zero out items added by growing */
973 178582 : if (newsize > oldsize)
974 9556 : memset(&sv->ob_item[oldsize], 0,
975 9556 : sizeof(*sv->ob_item) * (newsize - oldsize));
976 178582 : *pv = (PyObject *) sv;
977 178582 : _PyObject_GC_TRACK(sv);
978 178582 : return 0;
979 : }
980 :
981 :
982 : PyStatus
983 3134 : _PyTuple_InitTypes(PyInterpreterState *interp)
984 : {
985 3134 : if (!_Py_IsMainInterpreter(interp)) {
986 171 : return _PyStatus_OK();
987 : }
988 :
989 2963 : if (PyType_Ready(&PyTuple_Type) < 0) {
990 0 : return _PyStatus_ERR("Can't initialize tuple type");
991 : }
992 :
993 2963 : if (PyType_Ready(&PyTupleIter_Type) < 0) {
994 0 : return _PyStatus_ERR("Can't initialize tuple iterator type");
995 : }
996 :
997 2963 : return _PyStatus_OK();
998 : }
999 :
1000 : static void maybe_freelist_clear(PyInterpreterState *, int);
1001 :
1002 : void
1003 3120 : _PyTuple_Fini(PyInterpreterState *interp)
1004 : {
1005 3120 : maybe_freelist_clear(interp, 1);
1006 3120 : }
1007 :
1008 : void
1009 27720 : _PyTuple_ClearFreeList(PyInterpreterState *interp)
1010 : {
1011 27720 : maybe_freelist_clear(interp, 0);
1012 27720 : }
1013 :
1014 : /*********************** Tuple Iterator **************************/
1015 :
1016 : typedef struct {
1017 : PyObject_HEAD
1018 : Py_ssize_t it_index;
1019 : PyTupleObject *it_seq; /* Set to NULL when iterator is exhausted */
1020 : } tupleiterobject;
1021 :
1022 : static void
1023 29410500 : tupleiter_dealloc(tupleiterobject *it)
1024 : {
1025 29410500 : _PyObject_GC_UNTRACK(it);
1026 29410500 : Py_XDECREF(it->it_seq);
1027 29410500 : PyObject_GC_Del(it);
1028 29410500 : }
1029 :
1030 : static int
1031 46468 : tupleiter_traverse(tupleiterobject *it, visitproc visit, void *arg)
1032 : {
1033 46468 : Py_VISIT(it->it_seq);
1034 46468 : return 0;
1035 : }
1036 :
1037 : static PyObject *
1038 101436000 : tupleiter_next(tupleiterobject *it)
1039 : {
1040 : PyTupleObject *seq;
1041 : PyObject *item;
1042 :
1043 101436000 : assert(it != NULL);
1044 101436000 : seq = it->it_seq;
1045 101436000 : if (seq == NULL)
1046 90 : return NULL;
1047 101436000 : assert(PyTuple_Check(seq));
1048 :
1049 101436000 : if (it->it_index < PyTuple_GET_SIZE(seq)) {
1050 72554500 : item = PyTuple_GET_ITEM(seq, it->it_index);
1051 72554500 : ++it->it_index;
1052 72554500 : Py_INCREF(item);
1053 72554500 : return item;
1054 : }
1055 :
1056 28881300 : it->it_seq = NULL;
1057 28881300 : Py_DECREF(seq);
1058 28881300 : return NULL;
1059 : }
1060 :
1061 : static PyObject *
1062 98213 : tupleiter_len(tupleiterobject *it, PyObject *Py_UNUSED(ignored))
1063 : {
1064 98213 : Py_ssize_t len = 0;
1065 98213 : if (it->it_seq)
1066 98211 : len = PyTuple_GET_SIZE(it->it_seq) - it->it_index;
1067 98213 : return PyLong_FromSsize_t(len);
1068 : }
1069 :
1070 : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
1071 :
1072 : static PyObject *
1073 168 : tupleiter_reduce(tupleiterobject *it, PyObject *Py_UNUSED(ignored))
1074 : {
1075 168 : if (it->it_seq)
1076 168 : return Py_BuildValue("N(O)n", _PyEval_GetBuiltin(&_Py_ID(iter)),
1077 : it->it_seq, it->it_index);
1078 : else
1079 0 : return Py_BuildValue("N(())", _PyEval_GetBuiltin(&_Py_ID(iter)));
1080 : }
1081 :
1082 : static PyObject *
1083 216 : tupleiter_setstate(tupleiterobject *it, PyObject *state)
1084 : {
1085 216 : Py_ssize_t index = PyLong_AsSsize_t(state);
1086 216 : if (index == -1 && PyErr_Occurred())
1087 0 : return NULL;
1088 216 : if (it->it_seq != NULL) {
1089 216 : if (index < 0)
1090 0 : index = 0;
1091 216 : else if (index > PyTuple_GET_SIZE(it->it_seq))
1092 0 : index = PyTuple_GET_SIZE(it->it_seq); /* exhausted iterator */
1093 216 : it->it_index = index;
1094 : }
1095 216 : Py_RETURN_NONE;
1096 : }
1097 :
1098 : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1099 : PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
1100 :
1101 : static PyMethodDef tupleiter_methods[] = {
1102 : {"__length_hint__", (PyCFunction)tupleiter_len, METH_NOARGS, length_hint_doc},
1103 : {"__reduce__", (PyCFunction)tupleiter_reduce, METH_NOARGS, reduce_doc},
1104 : {"__setstate__", (PyCFunction)tupleiter_setstate, METH_O, setstate_doc},
1105 : {NULL, NULL} /* sentinel */
1106 : };
1107 :
1108 : PyTypeObject PyTupleIter_Type = {
1109 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
1110 : "tuple_iterator", /* tp_name */
1111 : sizeof(tupleiterobject), /* tp_basicsize */
1112 : 0, /* tp_itemsize */
1113 : /* methods */
1114 : (destructor)tupleiter_dealloc, /* tp_dealloc */
1115 : 0, /* tp_vectorcall_offset */
1116 : 0, /* tp_getattr */
1117 : 0, /* tp_setattr */
1118 : 0, /* tp_as_async */
1119 : 0, /* tp_repr */
1120 : 0, /* tp_as_number */
1121 : 0, /* tp_as_sequence */
1122 : 0, /* tp_as_mapping */
1123 : 0, /* tp_hash */
1124 : 0, /* tp_call */
1125 : 0, /* tp_str */
1126 : PyObject_GenericGetAttr, /* tp_getattro */
1127 : 0, /* tp_setattro */
1128 : 0, /* tp_as_buffer */
1129 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1130 : 0, /* tp_doc */
1131 : (traverseproc)tupleiter_traverse, /* tp_traverse */
1132 : 0, /* tp_clear */
1133 : 0, /* tp_richcompare */
1134 : 0, /* tp_weaklistoffset */
1135 : PyObject_SelfIter, /* tp_iter */
1136 : (iternextfunc)tupleiter_next, /* tp_iternext */
1137 : tupleiter_methods, /* tp_methods */
1138 : 0,
1139 : };
1140 :
1141 : static PyObject *
1142 29410500 : tuple_iter(PyObject *seq)
1143 : {
1144 : tupleiterobject *it;
1145 :
1146 29410500 : if (!PyTuple_Check(seq)) {
1147 0 : PyErr_BadInternalCall();
1148 0 : return NULL;
1149 : }
1150 29410500 : it = PyObject_GC_New(tupleiterobject, &PyTupleIter_Type);
1151 29410500 : if (it == NULL)
1152 0 : return NULL;
1153 29410500 : it->it_index = 0;
1154 29410500 : Py_INCREF(seq);
1155 29410500 : it->it_seq = (PyTupleObject *)seq;
1156 29410500 : _PyObject_GC_TRACK(it);
1157 29410500 : return (PyObject *)it;
1158 : }
1159 :
1160 :
1161 : /*************
1162 : * freelists *
1163 : *************/
1164 :
1165 : #define STATE (interp->tuple)
1166 : #define FREELIST_FINALIZED (STATE.numfree[0] < 0)
1167 :
1168 : static inline PyTupleObject *
1169 284395000 : maybe_freelist_pop(Py_ssize_t size)
1170 : {
1171 : #if PyTuple_NFREELISTS > 0
1172 284395000 : PyInterpreterState *interp = _PyInterpreterState_GET();
1173 : #ifdef Py_DEBUG
1174 : /* maybe_freelist_pop() must not be called after maybe_freelist_fini(). */
1175 284395000 : assert(!FREELIST_FINALIZED);
1176 : #endif
1177 284395000 : if (size == 0) {
1178 0 : return NULL;
1179 : }
1180 284395000 : assert(size > 0);
1181 284395000 : if (size < PyTuple_MAXSAVESIZE) {
1182 283434000 : Py_ssize_t index = size - 1;
1183 283434000 : PyTupleObject *op = STATE.free_list[index];
1184 283434000 : if (op != NULL) {
1185 : /* op is the head of a linked list, with the first item
1186 : pointing to the next node. Here we pop off the old head. */
1187 246143000 : STATE.free_list[index] = (PyTupleObject *) op->ob_item[0];
1188 246143000 : STATE.numfree[index]--;
1189 : /* Inlined _PyObject_InitVar() without _PyType_HasFeature() test */
1190 : #ifdef Py_TRACE_REFS
1191 : /* maybe_freelist_push() ensures these were already set. */
1192 : // XXX Can we drop these? See commit 68055ce6fe01 (GvR, Dec 1998).
1193 : Py_SET_SIZE(op, size);
1194 : Py_SET_TYPE(op, &PyTuple_Type);
1195 : #endif
1196 246143000 : _Py_NewReference((PyObject *)op);
1197 : /* END inlined _PyObject_InitVar() */
1198 : OBJECT_STAT_INC(from_freelist);
1199 246143000 : return op;
1200 : }
1201 : }
1202 : #endif
1203 38252500 : return NULL;
1204 : }
1205 :
1206 : static inline int
1207 291944000 : maybe_freelist_push(PyTupleObject *op)
1208 : {
1209 : #if PyTuple_NFREELISTS > 0
1210 291944000 : PyInterpreterState *interp = _PyInterpreterState_GET();
1211 : #ifdef Py_DEBUG
1212 : /* maybe_freelist_push() must not be called after maybe_freelist_fini(). */
1213 291944000 : assert(!FREELIST_FINALIZED);
1214 : #endif
1215 291944000 : if (Py_SIZE(op) == 0) {
1216 43 : return 0;
1217 : }
1218 291944000 : Py_ssize_t index = Py_SIZE(op) - 1;
1219 291944000 : if (index < PyTuple_NFREELISTS
1220 291043000 : && STATE.numfree[index] < PyTuple_MAXFREELIST
1221 276580000 : && Py_IS_TYPE(op, &PyTuple_Type))
1222 : {
1223 : /* op is the head of a linked list, with the first item
1224 : pointing to the next node. Here we set op as the new head. */
1225 268671000 : op->ob_item[0] = (PyObject *) STATE.free_list[index];
1226 268671000 : STATE.free_list[index] = op;
1227 268671000 : STATE.numfree[index]++;
1228 : OBJECT_STAT_INC(to_freelist);
1229 268671000 : return 1;
1230 : }
1231 : #endif
1232 23272900 : return 0;
1233 : }
1234 :
1235 : static void
1236 30840 : maybe_freelist_clear(PyInterpreterState *interp, int fini)
1237 : {
1238 : #if PyTuple_NFREELISTS > 0
1239 647640 : for (Py_ssize_t i = 0; i < PyTuple_NFREELISTS; i++) {
1240 616800 : PyTupleObject *p = STATE.free_list[i];
1241 616800 : STATE.free_list[i] = NULL;
1242 616800 : STATE.numfree[i] = fini ? -1 : 0;
1243 23141600 : while (p) {
1244 22524800 : PyTupleObject *q = p;
1245 22524800 : p = (PyTupleObject *)(p->ob_item[0]);
1246 22524800 : PyObject_GC_Del(q);
1247 : }
1248 : }
1249 : #endif
1250 30840 : }
1251 :
1252 : /* Print summary info about the state of the optimized allocator */
1253 : void
1254 1 : _PyTuple_DebugMallocStats(FILE *out)
1255 : {
1256 : #if PyTuple_NFREELISTS > 0
1257 1 : PyInterpreterState *interp = _PyInterpreterState_GET();
1258 21 : for (int i = 0; i < PyTuple_NFREELISTS; i++) {
1259 20 : int len = i + 1;
1260 : char buf[128];
1261 20 : PyOS_snprintf(buf, sizeof(buf),
1262 : "free %d-sized PyTupleObject", len);
1263 20 : _PyDebugAllocatorStats(out, buf, STATE.numfree[i],
1264 20 : _PyObject_VAR_SIZE(&PyTuple_Type, len));
1265 : }
1266 : #endif
1267 1 : }
1268 :
1269 : #undef STATE
1270 : #undef FREELIST_FINALIZED
|