cpython/Modules/_collectionsmodule.c

#include "Python.h"
#include "pycore_call.h"          // _PyObject_CallNoArgs()
#include "pycore_dict.h"          // _PyDict_GetItem_KnownHash()
#include "pycore_long.h"          // _PyLong_GetZero()
#include "pycore_moduleobject.h"  // _PyModule_GetState()
#include "pycore_pyatomic_ft_wrappers.h"
#include "pycore_typeobject.h"    // _PyType_GetModuleState()

#include <stddef.h>

collections_state;

static inline collections_state *
get_module_state(PyObject *mod)
{ … }

static inline collections_state *
get_module_state_by_cls(PyTypeObject *cls)
{ … }

static struct PyModuleDef _collectionsmodule;

static inline collections_state *
find_module_state_by_def(PyTypeObject *type)
{ … }

/*[clinic input]
module _collections
class _tuplegetter "_tuplegetterobject *" "clinic_state()->tuplegetter_type"
class _collections.deque "dequeobject *" "clinic_state()->deque_type"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=a033cc2a8476b3f1]*/

dequeobject;

/* We can safely assume type to be the defining class,
 * since tuplegetter is not a base type */
#define clinic_state …
#include "clinic/_collectionsmodule.c.h"
#undef clinic_state

/*[python input]
class dequeobject_converter(self_converter):
    type = "dequeobject *"
[python start generated code]*/
/*[python end generated code: output=da39a3ee5e6b4b0d input=b6ae4a3ff852be2f]*/

/* collections module implementation of a deque() datatype
   Written and maintained by Raymond D. Hettinger <[email protected]>
*/

/* The block length may be set to any number over 1.  Larger numbers
 * reduce the number of calls to the memory allocator, give faster
 * indexing and rotation, and reduce the link to data overhead ratio.
 * Making the block length a power of two speeds-up the modulo
 * and division calculations in deque_item() and deque_ass_item().
 */

#define BLOCKLEN …
#define CENTER …
#define MAXFREEBLOCKS …

/* Data for deque objects is stored in a doubly-linked list of fixed
 * length blocks.  This assures that appends or pops never move any
 * other data elements besides the one being appended or popped.
 *
 * Another advantage is that it completely avoids use of realloc(),
 * resulting in more predictable performance.
 *
 * Textbook implementations of doubly-linked lists store one datum
 * per link, but that gives them a 200% memory overhead (a prev and
 * next link for each datum) and it costs one malloc() call per data
 * element.  By using fixed-length blocks, the link to data ratio is
 * significantly improved and there are proportionally fewer calls
 * to malloc() and free().  The data blocks of consecutive pointers
 * also improve cache locality.
 *
 * The list of blocks is never empty, so d.leftblock and d.rightblock
 * are never equal to NULL.  The list is not circular.
 *
 * A deque d's first element is at d.leftblock[leftindex]
 * and its last element is at d.rightblock[rightindex].
 *
 * Unlike Python slice indices, these indices are inclusive on both
 * ends.  This makes the algorithms for left and right operations
 * more symmetrical and it simplifies the design.
 *
 * The indices, d.leftindex and d.rightindex are always in the range:
 *     0 <= index < BLOCKLEN
 *
 * And their exact relationship is:
 *     (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex
 *
 * Whenever d.leftblock == d.rightblock, then:
 *     d.leftindex + d.len - 1 == d.rightindex
 *
 * However, when d.leftblock != d.rightblock, the d.leftindex and
 * d.rightindex become indices into distinct blocks and either may
 * be larger than the other.
 *
 * Empty deques have:
 *     d.len == 0
 *     d.leftblock == d.rightblock
 *     d.leftindex == CENTER + 1
 *     d.rightindex == CENTER
 *
 * Checking for d.len == 0 is the intended way to see whether d is empty.
 */

block;

struct dequeobject { … };

/* For debug builds, add error checking to track the endpoints
 * in the chain of links.  The goal is to make sure that link
 * assignments only take place at endpoints so that links already
 * in use do not get overwritten.
 *
 * CHECK_END should happen before each assignment to a block's link field.
 * MARK_END should happen whenever a link field becomes a new endpoint.
 * This happens when new blocks are added or whenever an existing
 * block is freed leaving another existing block as the new endpoint.
 */

#ifndef NDEBUG
#define MARK_END …
#define CHECK_END …
#define CHECK_NOT_END …
#else
#define MARK_END(link) …
#define CHECK_END(link) …
#define CHECK_NOT_END(link) …
#endif

/* A simple freelisting scheme is used to minimize calls to the memory
   allocator.  It accommodates common use cases where new blocks are being
   added at about the same rate as old blocks are being freed.
 */

static inline block *
newblock(dequeobject *deque) { … }

static inline void
freeblock(dequeobject *deque, block *b)
{ … }

static PyObject *
deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{ … }

/*[clinic input]
@critical_section
_collections.deque.pop as deque_pop

    deque: dequeobject

Remove and return the rightmost element.
[clinic start generated code]*/

static PyObject *
deque_pop_impl(dequeobject *deque)
/*[clinic end generated code: output=2e5f7890c4251f07 input=55c5b6a8ad51d72f]*/
{ … }

/*[clinic input]
@critical_section
_collections.deque.popleft as deque_popleft

     deque: dequeobject

Remove and return the leftmost element.
[clinic start generated code]*/

static PyObject *
deque_popleft_impl(dequeobject *deque)
/*[clinic end generated code: output=62b154897097ff68 input=1571ce88fe3053de]*/
{ … }

/* The deque's size limit is d.maxlen.  The limit can be zero or positive.
 * If there is no limit, then d.maxlen == -1.
 *
 * After an item is added to a deque, we check to see if the size has
 * grown past the limit. If it has, we get the size back down to the limit
 * by popping an item off of the opposite end.  The methods that can
 * trigger this are append(), appendleft(), extend(), and extendleft().
 *
 * The macro to check whether a deque needs to be trimmed uses a single
 * unsigned test that returns true whenever 0 <= maxlen < Py_SIZE(deque).
 */

#define NEEDS_TRIM(deque, maxlen) …

static inline int
deque_append_lock_held(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
{ … }

/*[clinic input]
@critical_section
_collections.deque.append as deque_append

    deque: dequeobject
    item: object
    /

Add an element to the right side of the deque.
[clinic start generated code]*/

static PyObject *
deque_append_impl(dequeobject *deque, PyObject *item)
/*[clinic end generated code: output=9c7bcb8b599c6362 input=b0eeeb09b9f5cf18]*/
{ … }

static inline int
deque_appendleft_lock_held(dequeobject *deque, PyObject *item,
                           Py_ssize_t maxlen)
{ … }

/*[clinic input]
@critical_section
_collections.deque.appendleft as deque_appendleft

    deque: dequeobject
    item: object
    /

Add an element to the left side of the deque.
[clinic start generated code]*/

static PyObject *
deque_appendleft_impl(dequeobject *deque, PyObject *item)
/*[clinic end generated code: output=9a192edbcd0f20db input=236c2fbceaf08e14]*/
{ … }

static PyObject*
finalize_iterator(PyObject *it)
{ … }

/* Run an iterator to exhaustion.  Shortcut for
   the extend/extendleft methods when maxlen == 0. */
static PyObject*
consume_iterator(PyObject *it)
{ … }

/*[clinic input]
@critical_section
_collections.deque.extend as deque_extend

    deque: dequeobject
    iterable: object
    /

Extend the right side of the deque with elements from the iterable.
[clinic start generated code]*/

static PyObject *
deque_extend_impl(dequeobject *deque, PyObject *iterable)
/*[clinic end generated code: output=8b5ffa57ce82d980 input=85861954127c81da]*/
{ … }

/*[clinic input]
@critical_section
_collections.deque.extendleft as deque_extendleft

    deque: dequeobject
    iterable: object
    /

Extend the left side of the deque with elements from the iterable.
[clinic start generated code]*/

static PyObject *
deque_extendleft_impl(dequeobject *deque, PyObject *iterable)
/*[clinic end generated code: output=ba44191aa8e35a26 input=640dabd086115689]*/
{ … }

static PyObject *
deque_inplace_concat(dequeobject *deque, PyObject *other)
{ … }

/*[clinic input]
@critical_section
_collections.deque.copy as deque_copy

    deque: dequeobject

Return a shallow copy of a deque.
[clinic start generated code]*/

static PyObject *
deque_copy_impl(dequeobject *deque)
/*[clinic end generated code: output=6409b3d1ad2898b5 input=51d2ed1a23bab5e2]*/
{ … }

/*[clinic input]
@critical_section
_collections.deque.__copy__ as deque___copy__ = _collections.deque.copy

Return a shallow copy of a deque.
[clinic start generated code]*/

static PyObject *
deque___copy___impl(dequeobject *deque)
/*[clinic end generated code: output=7c5821504342bf23 input=f5464036f9686a55]*/
{ … }

static PyObject *
deque_concat_lock_held(dequeobject *deque, PyObject *other)
{ … }

static PyObject *
deque_concat(dequeobject *deque, PyObject *other)
{ … }

static int
deque_clear(dequeobject *deque)
{ … }

/*[clinic input]
@critical_section
_collections.deque.clear as deque_clearmethod

    deque: dequeobject

Remove all elements from the deque.
[clinic start generated code]*/

static PyObject *
deque_clearmethod_impl(dequeobject *deque)
/*[clinic end generated code: output=79b2513e097615c1 input=3a22e9605d20c5e9]*/
{ … }

static PyObject *
deque_inplace_repeat_lock_held(dequeobject *deque, Py_ssize_t n)
{ … }

static PyObject *
deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
{ … }

static PyObject *
deque_repeat(dequeobject *deque, Py_ssize_t n)
{ … }

/* The rotate() method is part of the public API and is used internally
as a primitive for other methods.

Rotation by 1 or -1 is a common case, so any optimizations for high
volume rotations should take care not to penalize the common case.

Conceptually, a rotate by one is equivalent to a pop on one side and an
append on the other.  However, a pop/append pair is unnecessarily slow
because it requires an incref/decref pair for an object located randomly
in memory.  It is better to just move the object pointer from one block
to the next without changing the reference count.

When moving batches of pointers, it is tempting to use memcpy() but that
proved to be slower than a simple loop for a variety of reasons.
Memcpy() cannot know in advance that we're copying pointers instead of
bytes, that the source and destination are pointer aligned and
non-overlapping, that moving just one pointer is a common case, that we
never need to move more than BLOCKLEN pointers, and that at least one
pointer is always moved.

For high volume rotations, newblock() and freeblock() are never called
more than once.  Previously emptied blocks are immediately reused as a
destination block.  If a block is left-over at the end, it is freed.
*/

static int
_deque_rotate(dequeobject *deque, Py_ssize_t n)
{ … }

/*[clinic input]
@critical_section
_collections.deque.rotate as deque_rotate

    deque: dequeobject
    n: Py_ssize_t = 1
    /

Rotate the deque n steps to the right.  If n is negative, rotates left.
[clinic start generated code]*/

static PyObject *
deque_rotate_impl(dequeobject *deque, Py_ssize_t n)
/*[clinic end generated code: output=96c2402a371eb15d input=5bf834296246e002]*/
{ … }

/*[clinic input]
@critical_section
_collections.deque.reverse as deque_reverse

    deque: dequeobject

Reverse *IN PLACE*.
[clinic start generated code]*/

static PyObject *
deque_reverse_impl(dequeobject *deque)
/*[clinic end generated code: output=bdeebc2cf8c1f064 input=26f4167fd623027f]*/
{ … }

/*[clinic input]
@critical_section
_collections.deque.count as deque_count

    deque: dequeobject
    value as v: object
    /

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

static PyObject *
deque_count_impl(dequeobject *deque, PyObject *v)
/*[clinic end generated code: output=2ca26c49b6ab0400 input=4ef67ef2b34dc1fc]*/
{ … }

static int
deque_contains_lock_held(dequeobject *deque, PyObject *v)
{ … }

static int
deque_contains(dequeobject *deque, PyObject *v)
{ … }

static Py_ssize_t
deque_len(dequeobject *deque)
{ … }

/*[clinic input]
@critical_section
@text_signature "($self, value, [start, [stop]])"
_collections.deque.index as deque_index

    deque: dequeobject
    value as v: object
    start: object(converter='_PyEval_SliceIndexNotNone', type='Py_ssize_t', c_default='0') = NULL
    stop: object(converter='_PyEval_SliceIndexNotNone', type='Py_ssize_t', c_default='Py_SIZE(deque)') = NULL
    /

Return first index of value.

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

static PyObject *
deque_index_impl(dequeobject *deque, PyObject *v, Py_ssize_t start,
                 Py_ssize_t stop)
/*[clinic end generated code: output=df45132753175ef9 input=90f48833a91e1743]*/
{ … }

/* insert(), remove(), and delitem() are implemented in terms of
   rotate() for simplicity and reasonable performance near the end
   points.  If for some reason these methods become popular, it is not
   hard to re-implement this using direct data movement (similar to
   the code used in list slice assignments) and achieve a performance
   boost (by moving each pointer only once instead of twice).
*/

/*[clinic input]
@critical_section
_collections.deque.insert as deque_insert

    deque: dequeobject
    index: Py_ssize_t
    value: object
    /

Insert value before index.
[clinic start generated code]*/

static PyObject *
deque_insert_impl(dequeobject *deque, Py_ssize_t index, PyObject *value)
/*[clinic end generated code: output=ef4d2c15d5532b80 input=dbee706586cc9cde]*/
{ … }

static int
valid_index(Py_ssize_t i, Py_ssize_t limit)
{ … }

static PyObject *
deque_item_lock_held(dequeobject *deque, Py_ssize_t i)
{ … }

static PyObject *
deque_item(dequeobject *deque, Py_ssize_t i)
{ … }

static int
deque_del_item(dequeobject *deque, Py_ssize_t i)
{ … }

/*[clinic input]
@critical_section
_collections.deque.remove as deque_remove

    deque: dequeobject
    value: object
    /

Remove first occurrence of value.
[clinic start generated code]*/

static PyObject *
deque_remove_impl(dequeobject *deque, PyObject *value)
/*[clinic end generated code: output=54cff28b8ef78c5b input=60eb3f8aa4de532a]*/
{ … }

static int
deque_ass_item_lock_held(dequeobject *deque, Py_ssize_t i, PyObject *v)
{ … }

static int
deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
{ … }

static void
deque_dealloc(dequeobject *deque)
{ … }

static int
deque_traverse(dequeobject *deque, visitproc visit, void *arg)
{ … }

/*[clinic input]
_collections.deque.__reduce__ as deque___reduce__

    deque: dequeobject

Return state information for pickling.
[clinic start generated code]*/

static PyObject *
deque___reduce___impl(dequeobject *deque)
/*[clinic end generated code: output=cb85d9e0b7d2c5ad input=991a933a5bc7a526]*/
{ … }

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

static PyObject *
deque_repr(PyObject *deque)
{ … }

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

/*[clinic input]
@critical_section
@text_signature "([iterable[, maxlen]])"
_collections.deque.__init__ as deque_init

    deque: dequeobject
    iterable: object = NULL
    maxlen as maxlenobj: object = NULL

A list-like sequence optimized for data accesses near its endpoints.
[clinic start generated code]*/

static int
deque_init_impl(dequeobject *deque, PyObject *iterable, PyObject *maxlenobj)
/*[clinic end generated code: output=7084a39d71218dcd input=2b9e37af1fd73143]*/
{ … }

/*[clinic input]
@critical_section
_collections.deque.__sizeof__ as deque___sizeof__

    deque: dequeobject

Return the size of the deque in memory, in bytes.
[clinic start generated code]*/

static PyObject *
deque___sizeof___impl(dequeobject *deque)
/*[clinic end generated code: output=4d36e9fb4f30bbaf input=762312f2d4813535]*/
{ … }

static PyObject *
deque_get_maxlen(dequeobject *deque, void *Py_UNUSED(ignored))
{ … }

static PyObject *deque_reviter(dequeobject *deque);

/*[clinic input]
_collections.deque.__reversed__ as deque___reversed__

    deque: dequeobject

Return a reverse iterator over the deque.
[clinic start generated code]*/

static PyObject *
deque___reversed___impl(dequeobject *deque)
/*[clinic end generated code: output=3e7e7e715883cf2e input=3d494c25a6fe5c7e]*/
{ … }

/* deque object ********************************************************/

static PyGetSetDef deque_getset[] = …;

static PyObject *deque_iter(dequeobject *deque);

static PyMethodDef deque_methods[] = …;

static PyMemberDef deque_members[] = …;

static PyType_Slot deque_slots[] = …;

static PyType_Spec deque_spec = …;

/*********************** Deque Iterator **************************/

dequeiterobject;

static PyObject *
deque_iter(dequeobject *deque)
{ … }

static int
dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
{ … }

static int
dequeiter_clear(dequeiterobject *dio)
{ … }

static void
dequeiter_dealloc(dequeiterobject *dio)
{ … }

static PyObject *
dequeiter_next_lock_held(dequeiterobject *it, dequeobject *deque)
{ … }

static PyObject *
dequeiter_next(dequeiterobject *it)
{ … }

static PyObject *
dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{ … }

static PyObject *
dequeiter_len(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
{ … }

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

static PyObject *
dequeiter_reduce(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
{ … }

static PyMethodDef dequeiter_methods[] = …;

static PyType_Slot dequeiter_slots[] = …;

static PyType_Spec dequeiter_spec = …;

/*********************** Deque Reverse Iterator **************************/

static PyObject *
deque_reviter(dequeobject *deque)
{ … }

static PyObject *
dequereviter_next_lock_held(dequeiterobject *it, dequeobject *deque)
{ … }

static PyObject *
dequereviter_next(dequeiterobject *it)
{ … }

static PyObject *
dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{ … }

static PyType_Slot dequereviter_slots[] = …;

static PyType_Spec dequereviter_spec = …;

/* defaultdict type *********************************************************/

defdictobject;

static PyType_Spec defdict_spec;

PyDoc_STRVAR(defdict_missing_doc,
"__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
  if self.default_factory is None: raise KeyError((key,))\n\
  self[key] = value = self.default_factory()\n\
  return value\n\
");

static PyObject *
defdict_missing(defdictobject *dd, PyObject *key)
{ … }

static inline PyObject*
new_defdict(defdictobject *dd, PyObject *arg)
{ … }

PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");

static PyObject *
defdict_copy(defdictobject *dd, PyObject *Py_UNUSED(ignored))
{ … }

static PyObject *
defdict_reduce(defdictobject *dd, PyObject *Py_UNUSED(ignored))
{ … }

static PyMethodDef defdict_methods[] = …;

static PyMemberDef defdict_members[] = …;

static void
defdict_dealloc(defdictobject *dd)
{ … }

static PyObject *
defdict_repr(defdictobject *dd)
{ … }

static PyObject*
defdict_or(PyObject* left, PyObject* right)
{ … }

static int
defdict_traverse(PyObject *self, visitproc visit, void *arg)
{ … }

static int
defdict_tp_clear(defdictobject *dd)
{ … }

static int
defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
{ … }

PyDoc_STRVAR(defdict_doc,
"defaultdict(default_factory=None, /, [...]) --> dict with default factory\n\
\n\
The default factory is called without arguments to produce\n\
a new value when a key is not present, in __getitem__ only.\n\
A defaultdict compares equal to a dict with the same items.\n\
All remaining arguments are treated the same as if they were\n\
passed to the dict constructor, including keyword arguments.\n\
");

/* See comment in xxsubtype.c */
#define DEFERRED_ADDRESS(ADDR) …

static PyType_Slot defdict_slots[] = …;

static PyType_Spec defdict_spec = …;

/* helper function for Counter  *********************************************/

/*[clinic input]
_collections._count_elements

    mapping: object
    iterable: object
    /

Count elements in the iterable, updating the mapping
[clinic start generated code]*/

static PyObject *
_collections__count_elements_impl(PyObject *module, PyObject *mapping,
                                  PyObject *iterable)
/*[clinic end generated code: output=7e0c1789636b3d8f input=e79fad04534a0b45]*/
{ … }

/* Helper function for namedtuple() ************************************/

_tuplegetterobject;

/*[clinic input]
@classmethod
_tuplegetter.__new__ as tuplegetter_new

    index: Py_ssize_t
    doc: object
    /
[clinic start generated code]*/

static PyObject *
tuplegetter_new_impl(PyTypeObject *type, Py_ssize_t index, PyObject *doc)
/*[clinic end generated code: output=014be444ad80263f input=87c576a5bdbc0bbb]*/
{ … }

static PyObject *
tuplegetter_descr_get(PyObject *self, PyObject *obj, PyObject *type)
{ … }

static int
tuplegetter_descr_set(PyObject *self, PyObject *obj, PyObject *value)
{ … }

static int
tuplegetter_traverse(PyObject *self, visitproc visit, void *arg)
{ … }

static int
tuplegetter_clear(PyObject *self)
{ … }

static void
tuplegetter_dealloc(_tuplegetterobject *self)
{ … }

static PyObject*
tuplegetter_reduce(_tuplegetterobject *self, PyObject *Py_UNUSED(ignored))
{ … }

static PyObject*
tuplegetter_repr(_tuplegetterobject *self)
{ … }


static PyMemberDef tuplegetter_members[] = …;

static PyMethodDef tuplegetter_methods[] = …;

static PyType_Slot tuplegetter_slots[] = …;

static PyType_Spec tuplegetter_spec = …;


/* module level code ********************************************************/

static int
collections_traverse(PyObject *mod, visitproc visit, void *arg)
{ … }

static int
collections_clear(PyObject *mod)
{ … }

static void
collections_free(void *module)
{ … }

PyDoc_STRVAR(collections_doc,
"High performance data structures.\n\
- deque:        ordered collection accessible from endpoints only\n\
- defaultdict:  dict subclass with a default value factory\n\
");

static struct PyMethodDef collections_methods[] = …;

#define ADD_TYPE …

static int
collections_exec(PyObject *module) { … }

#undef ADD_TYPE

static struct PyModuleDef_Slot collections_slots[] = …;

static struct PyModuleDef _collectionsmodule = …;

PyMODINIT_FUNC
PyInit__collections(void)
{ … }