LCOV - code coverage report
Current view: top level - Objects - tupleobject.c (source / functions) Hit Total Coverage
Test: CPython lcov report Lines: 463 535 86.5 %
Date: 2022-07-07 18:19:46 Functions: 44 44 100.0 %

          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

Generated by: LCOV version 1.14