cpython/Objects/tupleobject.c

/* Tuple object implementation */

#include "Python.h"
#include "pycore_abstract.h"      // _PyIndex_Check()
#include "pycore_ceval.h"         // _PyEval_GetBuiltin()
#include "pycore_freelist.h"      // _Py_FREELIST_PUSH(), _Py_FREELIST_POP()
#include "pycore_gc.h"            // _PyObject_GC_IS_TRACKED()
#include "pycore_initconfig.h"    // _PyStatus_OK()
#include "pycore_modsupport.h"    // _PyArg_NoKwnames()
#include "pycore_object.h"        // _PyObject_GC_TRACK(), _Py_FatalRefcountError(), _PyDebugAllocatorStats()

/*[clinic input]
class tuple "PyTupleObject *" "&PyTuple_Type"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=f051ba3cfdf9a189]*/

#include "clinic/tupleobject.c.h"


static inline int maybe_freelist_push(PyTupleObject *);


/* Allocate an uninitialized tuple object. Before making it public, following
   steps must be done:

   - Initialize its items.
   - Call _PyObject_GC_TRACK() on it.

   Because the empty tuple is always reused and it's already tracked by GC,
   this function must not be called with size == 0 (unless from PyTuple_New()
   which wraps this function).
*/
static PyTupleObject *
tuple_alloc(Py_ssize_t size)
{ … }

// The empty tuple singleton is not tracked by the GC.
// It does not contain any Python object.
// Note that tuple subclasses have their own empty instances.

static inline PyObject *
tuple_get_empty(void)
{ … }

PyObject *
PyTuple_New(Py_ssize_t size)
{ … }

Py_ssize_t
PyTuple_Size(PyObject *op)
{ … }

PyObject *
PyTuple_GetItem(PyObject *op, Py_ssize_t i)
{ … }

int
PyTuple_SetItem(PyObject *op, Py_ssize_t i, PyObject *newitem)
{ … }

void
_PyTuple_MaybeUntrack(PyObject *op)
{ … }

PyObject *
PyTuple_Pack(Py_ssize_t n, ...)
{ … }


/* Methods */

static void
tupledealloc(PyTupleObject *op)
{ … }

static PyObject *
tuplerepr(PyTupleObject *v)
{ … }


/* Hash for tuples. This is a slightly simplified version of the xxHash
   non-cryptographic hash:
   - we do not use any parallelism, there is only 1 accumulator.
   - we drop the final mixing since this is just a permutation of the
     output space: it does not help against collisions.
   - at the end, we mangle the length with a single constant.
   For the xxHash specification, see
   https://github.com/Cyan4973/xxHash/blob/master/doc/xxhash_spec.md

   Below are the official constants from the xxHash specification. Optimizing
   compilers should emit a single "rotate" instruction for the
   _PyHASH_XXROTATE() expansion. If that doesn't happen for some important
   platform, the macro could be changed to expand to a platform-specific rotate
   spelling instead.
*/
#if SIZEOF_PY_UHASH_T > 4
#define _PyHASH_XXPRIME_1 …
#define _PyHASH_XXPRIME_2 …
#define _PyHASH_XXPRIME_5 …
#define _PyHASH_XXROTATE(x) …
#else
#define _PyHASH_XXPRIME_1 …
#define _PyHASH_XXPRIME_2 …
#define _PyHASH_XXPRIME_5 …
#define _PyHASH_XXROTATE …
#endif

/* Tests have shown that it's not worth to cache the hash value, see
   https://bugs.python.org/issue9685 */
static Py_hash_t
tuplehash(PyTupleObject *v)
{ … }

static Py_ssize_t
tuplelength(PyTupleObject *a)
{ … }

static int
tuplecontains(PyTupleObject *a, PyObject *el)
{ … }

static PyObject *
tupleitem(PyTupleObject *a, Py_ssize_t i)
{ … }

PyObject *
_PyTuple_FromArray(PyObject *const *src, Py_ssize_t n)
{ … }

PyObject *
_PyTuple_FromStackRefSteal(const _PyStackRef *src, Py_ssize_t n)
{ … }

PyObject *
_PyTuple_FromArraySteal(PyObject *const *src, Py_ssize_t n)
{ … }

static PyObject *
tupleslice(PyTupleObject *a, Py_ssize_t ilow,
           Py_ssize_t ihigh)
{ … }

PyObject *
PyTuple_GetSlice(PyObject *op, Py_ssize_t i, Py_ssize_t j)
{ … }

static PyObject *
tupleconcat(PyTupleObject *a, PyObject *bb)
{ … }

static PyObject *
tuplerepeat(PyTupleObject *a, Py_ssize_t n)
{ … }

/*[clinic input]
tuple.index

    value: object
    start: slice_index(accept={int}) = 0
    stop: slice_index(accept={int}, c_default="PY_SSIZE_T_MAX") = sys.maxsize
    /

Return first index of value.

Raises ValueError if the value is not present.
[clinic start generated code]*/

static PyObject *
tuple_index_impl(PyTupleObject *self, PyObject *value, Py_ssize_t start,
                 Py_ssize_t stop)
/*[clinic end generated code: output=07b6f9f3cb5c33eb input=fb39e9874a21fe3f]*/
{ … }

/*[clinic input]
tuple.count

     value: object
     /

Return number of occurrences of value.
[clinic start generated code]*/

static PyObject *
tuple_count(PyTupleObject *self, PyObject *value)
/*[clinic end generated code: output=aa927affc5a97605 input=531721aff65bd772]*/
{ … }

static int
tupletraverse(PyTupleObject *o, visitproc visit, void *arg)
{ … }

static PyObject *
tuplerichcompare(PyObject *v, PyObject *w, int op)
{ … }

static PyObject *
tuple_subtype_new(PyTypeObject *type, PyObject *iterable);

/*[clinic input]
@classmethod
tuple.__new__ as tuple_new
    iterable: object(c_default="NULL") = ()
    /

Built-in immutable sequence.

If no argument is given, the constructor returns an empty tuple.
If iterable is specified the tuple is initialized from iterable's items.

If the argument is a tuple, the return value is the same object.
[clinic start generated code]*/

static PyObject *
tuple_new_impl(PyTypeObject *type, PyObject *iterable)
/*[clinic end generated code: output=4546d9f0d469bce7 input=86963bcde633b5a2]*/
{ … }

static PyObject *
tuple_vectorcall(PyObject *type, PyObject * const*args,
                 size_t nargsf, PyObject *kwnames)
{ … }

static PyObject *
tuple_subtype_new(PyTypeObject *type, PyObject *iterable)
{ … }

static PySequenceMethods tuple_as_sequence = …;

static PyObject*
tuplesubscript(PyTupleObject* self, PyObject* item)
{ … }

/*[clinic input]
tuple.__getnewargs__
[clinic start generated code]*/

static PyObject *
tuple___getnewargs___impl(PyTupleObject *self)
/*[clinic end generated code: output=25e06e3ee56027e2 input=1aeb4b286a21639a]*/
{ … }

static PyMethodDef tuple_methods[] = …;

static PyMappingMethods tuple_as_mapping = …;

static PyObject *tuple_iter(PyObject *seq);

PyTypeObject PyTuple_Type = …;

/* The following function breaks the notion that tuples are immutable:
   it changes the size of a tuple.  We get away with this only if there
   is only one module referencing the object.  You can also think of it
   as creating a new tuple object and destroying the old one, only more
   efficiently.  In any case, don't use this if the tuple may already be
   known to some other part of the code. */

int
_PyTuple_Resize(PyObject **pv, Py_ssize_t newsize)
{ … }

/*********************** Tuple Iterator **************************/


static void
tupleiter_dealloc(_PyTupleIterObject *it)
{ … }

static int
tupleiter_traverse(_PyTupleIterObject *it, visitproc visit, void *arg)
{ … }

static PyObject *
tupleiter_next(_PyTupleIterObject *it)
{ … }

static PyObject *
tupleiter_len(_PyTupleIterObject *it, PyObject *Py_UNUSED(ignored))
{ … }

PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");

static PyObject *
tupleiter_reduce(_PyTupleIterObject *it, PyObject *Py_UNUSED(ignored))
{ … }

static PyObject *
tupleiter_setstate(_PyTupleIterObject *it, PyObject *state)
{ … }

PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");

static PyMethodDef tupleiter_methods[] = …;

PyTypeObject PyTupleIter_Type = …;

static PyObject *
tuple_iter(PyObject *seq)
{ … }


/*************
 * freelists *
 *************/

static inline int
maybe_freelist_push(PyTupleObject *op)
{ … }

/* Print summary info about the state of the optimized allocator */
void
_PyTuple_DebugMallocStats(FILE *out)
{ … }