LCOV - code coverage report
Current view: | top level - Modules - _collectionsmodule.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 129 | 1082 | 11.9 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 20 | 72 | 27.8 %
|  |  | Branches: | 42 | 589 | 7.1 %

               Branch data     Line data    Source code
           1                 :            : #include "Python.h"
           2                 :            : #include "pycore_call.h"          // _PyObject_CallNoArgs()
           3                 :            : #include "pycore_long.h"          // _PyLong_GetZero()
           4                 :            : #include "structmember.h"         // PyMemberDef
           5                 :            : #include <stddef.h>
           6                 :            :
           7                 :            : /*[clinic input]
           8                 :            : module _collections
           9                 :            : class _tuplegetter "_tuplegetterobject *" "&tuplegetter_type"
          10                 :            : [clinic start generated code]*/
          11                 :            : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=a8ece4ccad7e30ac]*/
          12                 :            :
          13                 :            : static PyTypeObject tuplegetter_type;
          14                 :            : #include "clinic/_collectionsmodule.c.h"
          15                 :            :
          16                 :            : /* collections module implementation of a deque() datatype
          17                 :            :    Written and maintained by Raymond D. Hettinger <python@rcn.com>
          18                 :            : */
          19                 :            :
          20                 :            : /* The block length may be set to any number over 1.  Larger numbers
          21                 :            :  * reduce the number of calls to the memory allocator, give faster
          22                 :            :  * indexing and rotation, and reduce the link to data overhead ratio.
          23                 :            :  * Making the block length a power of two speeds-up the modulo
          24                 :            :  * and division calculations in deque_item() and deque_ass_item().
          25                 :            :  */
          26                 :            :
          27                 :            : #define BLOCKLEN 64
          28                 :            : #define CENTER ((BLOCKLEN - 1) / 2)
          29                 :            : #define MAXFREEBLOCKS 16
          30                 :            :
          31                 :            : /* Data for deque objects is stored in a doubly-linked list of fixed
          32                 :            :  * length blocks.  This assures that appends or pops never move any
          33                 :            :  * other data elements besides the one being appended or popped.
          34                 :            :  *
          35                 :            :  * Another advantage is that it completely avoids use of realloc(),
          36                 :            :  * resulting in more predictable performance.
          37                 :            :  *
          38                 :            :  * Textbook implementations of doubly-linked lists store one datum
          39                 :            :  * per link, but that gives them a 200% memory overhead (a prev and
          40                 :            :  * next link for each datum) and it costs one malloc() call per data
          41                 :            :  * element.  By using fixed-length blocks, the link to data ratio is
          42                 :            :  * significantly improved and there are proportionally fewer calls
          43                 :            :  * to malloc() and free().  The data blocks of consecutive pointers
          44                 :            :  * also improve cache locality.
          45                 :            :  *
          46                 :            :  * The list of blocks is never empty, so d.leftblock and d.rightblock
          47                 :            :  * are never equal to NULL.  The list is not circular.
          48                 :            :  *
          49                 :            :  * A deque d's first element is at d.leftblock[leftindex]
          50                 :            :  * and its last element is at d.rightblock[rightindex].
          51                 :            :  *
          52                 :            :  * Unlike Python slice indices, these indices are inclusive on both
          53                 :            :  * ends.  This makes the algorithms for left and right operations
          54                 :            :  * more symmetrical and it simplifies the design.
          55                 :            :  *
          56                 :            :  * The indices, d.leftindex and d.rightindex are always in the range:
          57                 :            :  *     0 <= index < BLOCKLEN
          58                 :            :  *
          59                 :            :  * And their exact relationship is:
          60                 :            :  *     (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex
          61                 :            :  *
          62                 :            :  * Whenever d.leftblock == d.rightblock, then:
          63                 :            :  *     d.leftindex + d.len - 1 == d.rightindex
          64                 :            :  *
          65                 :            :  * However, when d.leftblock != d.rightblock, the d.leftindex and
          66                 :            :  * d.rightindex become indices into distinct blocks and either may
          67                 :            :  * be larger than the other.
          68                 :            :  *
          69                 :            :  * Empty deques have:
          70                 :            :  *     d.len == 0
          71                 :            :  *     d.leftblock == d.rightblock
          72                 :            :  *     d.leftindex == CENTER + 1
          73                 :            :  *     d.rightindex == CENTER
          74                 :            :  *
          75                 :            :  * Checking for d.len == 0 is the intended way to see whether d is empty.
          76                 :            :  */
          77                 :            :
          78                 :            : typedef struct BLOCK {
          79                 :            :     struct BLOCK *leftlink;
          80                 :            :     PyObject *data[BLOCKLEN];
          81                 :            :     struct BLOCK *rightlink;
          82                 :            : } block;
          83                 :            :
          84                 :            : typedef struct {
          85                 :            :     PyObject_VAR_HEAD
          86                 :            :     block *leftblock;
          87                 :            :     block *rightblock;
          88                 :            :     Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
          89                 :            :     Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
          90                 :            :     size_t state;               /* incremented whenever the indices move */
          91                 :            :     Py_ssize_t maxlen;          /* maxlen is -1 for unbounded deques */
          92                 :            :     Py_ssize_t numfreeblocks;
          93                 :            :     block *freeblocks[MAXFREEBLOCKS];
          94                 :            :     PyObject *weakreflist;
          95                 :            : } dequeobject;
          96                 :            :
          97                 :            : static PyTypeObject deque_type;
          98                 :            :
          99                 :            : /* For debug builds, add error checking to track the endpoints
         100                 :            :  * in the chain of links.  The goal is to make sure that link
         101                 :            :  * assignments only take place at endpoints so that links already
         102                 :            :  * in use do not get overwritten.
         103                 :            :  *
         104                 :            :  * CHECK_END should happen before each assignment to a block's link field.
         105                 :            :  * MARK_END should happen whenever a link field becomes a new endpoint.
         106                 :            :  * This happens when new blocks are added or whenever an existing
         107                 :            :  * block is freed leaving another existing block as the new endpoint.
         108                 :            :  */
         109                 :            :
         110                 :            : #ifndef NDEBUG
         111                 :            : #define MARK_END(link)  link = NULL;
         112                 :            : #define CHECK_END(link) assert(link == NULL);
         113                 :            : #define CHECK_NOT_END(link) assert(link != NULL);
         114                 :            : #else
         115                 :            : #define MARK_END(link)
         116                 :            : #define CHECK_END(link)
         117                 :            : #define CHECK_NOT_END(link)
         118                 :            : #endif
         119                 :            :
         120                 :            : /* A simple freelisting scheme is used to minimize calls to the memory
         121                 :            :    allocator.  It accommodates common use cases where new blocks are being
         122                 :            :    added at about the same rate as old blocks are being freed.
         123                 :            :  */
         124                 :            :
         125                 :            : static inline block *
         126                 :          4 : newblock(dequeobject *deque) {
         127                 :            :     block *b;
         128         [ -  + ]:          4 :     if (deque->numfreeblocks) {
         129                 :          0 :         deque->numfreeblocks--;
         130                 :          0 :         return deque->freeblocks[deque->numfreeblocks];
         131                 :            :     }
         132                 :          4 :     b = PyMem_Malloc(sizeof(block));
         133         [ +  - ]:          4 :     if (b != NULL) {
         134                 :          4 :         return b;
         135                 :            :     }
         136                 :          0 :     PyErr_NoMemory();
         137                 :          0 :     return NULL;
         138                 :            : }
         139                 :            :
         140                 :            : static inline void
         141                 :          4 : freeblock(dequeobject *deque, block *b)
         142                 :            : {
         143         [ +  - ]:          4 :     if (deque->numfreeblocks < MAXFREEBLOCKS) {
         144                 :          4 :         deque->freeblocks[deque->numfreeblocks] = b;
         145                 :          4 :         deque->numfreeblocks++;
         146                 :            :     } else {
         147                 :          0 :         PyMem_Free(b);
         148                 :            :     }
         149                 :          4 : }
         150                 :            :
         151                 :            : static PyObject *
         152                 :          4 : deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
         153                 :            : {
         154                 :            :     dequeobject *deque;
         155                 :            :     block *b;
         156                 :            :
         157                 :            :     /* create dequeobject structure */
         158                 :          4 :     deque = (dequeobject *)type->tp_alloc(type, 0);
         159         [ -  + ]:          4 :     if (deque == NULL)
         160                 :          0 :         return NULL;
         161                 :            :
         162                 :          4 :     b = newblock(deque);
         163         [ -  + ]:          4 :     if (b == NULL) {
         164                 :          0 :         Py_DECREF(deque);
         165                 :          0 :         return NULL;
         166                 :            :     }
         167                 :            :     MARK_END(b->leftlink);
         168                 :            :     MARK_END(b->rightlink);
         169                 :            :
         170                 :            :     assert(BLOCKLEN >= 2);
         171                 :          4 :     Py_SET_SIZE(deque, 0);
         172                 :          4 :     deque->leftblock = b;
         173                 :          4 :     deque->rightblock = b;
         174                 :          4 :     deque->leftindex = CENTER + 1;
         175                 :          4 :     deque->rightindex = CENTER;
         176                 :          4 :     deque->state = 0;
         177                 :          4 :     deque->maxlen = -1;
         178                 :          4 :     deque->numfreeblocks = 0;
         179                 :          4 :     deque->weakreflist = NULL;
         180                 :            :
         181                 :          4 :     return (PyObject *)deque;
         182                 :            : }
         183                 :            :
         184                 :            : static PyObject *
         185                 :          0 : deque_pop(dequeobject *deque, PyObject *unused)
         186                 :            : {
         187                 :            :     PyObject *item;
         188                 :            :     block *prevblock;
         189                 :            :
         190         [ #  # ]:          0 :     if (Py_SIZE(deque) == 0) {
         191                 :          0 :         PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
         192                 :          0 :         return NULL;
         193                 :            :     }
         194                 :          0 :     item = deque->rightblock->data[deque->rightindex];
         195                 :          0 :     deque->rightindex--;
         196                 :          0 :     Py_SET_SIZE(deque, Py_SIZE(deque) - 1);
         197                 :          0 :     deque->state++;
         198                 :            :
         199         [ #  # ]:          0 :     if (deque->rightindex < 0) {
         200         [ #  # ]:          0 :         if (Py_SIZE(deque)) {
         201                 :          0 :             prevblock = deque->rightblock->leftlink;
         202                 :            :             assert(deque->leftblock != deque->rightblock);
         203                 :          0 :             freeblock(deque, deque->rightblock);
         204                 :            :             CHECK_NOT_END(prevblock);
         205                 :            :             MARK_END(prevblock->rightlink);
         206                 :          0 :             deque->rightblock = prevblock;
         207                 :          0 :             deque->rightindex = BLOCKLEN - 1;
         208                 :            :         } else {
         209                 :            :             assert(deque->leftblock == deque->rightblock);
         210                 :            :             assert(deque->leftindex == deque->rightindex+1);
         211                 :            :             /* re-center instead of freeing a block */
         212                 :          0 :             deque->leftindex = CENTER + 1;
         213                 :          0 :             deque->rightindex = CENTER;
         214                 :            :         }
         215                 :            :     }
         216                 :          0 :     return item;
         217                 :            : }
         218                 :            :
         219                 :            : PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");
         220                 :            :
         221                 :            : static PyObject *
         222                 :          0 : deque_popleft(dequeobject *deque, PyObject *unused)
         223                 :            : {
         224                 :            :     PyObject *item;
         225                 :            :     block *prevblock;
         226                 :            :
         227         [ #  # ]:          0 :     if (Py_SIZE(deque) == 0) {
         228                 :          0 :         PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
         229                 :          0 :         return NULL;
         230                 :            :     }
         231                 :            :     assert(deque->leftblock != NULL);
         232                 :          0 :     item = deque->leftblock->data[deque->leftindex];
         233                 :          0 :     deque->leftindex++;
         234                 :          0 :     Py_SET_SIZE(deque, Py_SIZE(deque) - 1);
         235                 :          0 :     deque->state++;
         236                 :            :
         237         [ #  # ]:          0 :     if (deque->leftindex == BLOCKLEN) {
         238         [ #  # ]:          0 :         if (Py_SIZE(deque)) {
         239                 :            :             assert(deque->leftblock != deque->rightblock);
         240                 :          0 :             prevblock = deque->leftblock->rightlink;
         241                 :          0 :             freeblock(deque, deque->leftblock);
         242                 :            :             CHECK_NOT_END(prevblock);
         243                 :            :             MARK_END(prevblock->leftlink);
         244                 :          0 :             deque->leftblock = prevblock;
         245                 :          0 :             deque->leftindex = 0;
         246                 :            :         } else {
         247                 :            :             assert(deque->leftblock == deque->rightblock);
         248                 :            :             assert(deque->leftindex == deque->rightindex+1);
         249                 :            :             /* re-center instead of freeing a block */
         250                 :          0 :             deque->leftindex = CENTER + 1;
         251                 :          0 :             deque->rightindex = CENTER;
         252                 :            :         }
         253                 :            :     }
         254                 :          0 :     return item;
         255                 :            : }
         256                 :            :
         257                 :            : PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
         258                 :            :
         259                 :            : /* The deque's size limit is d.maxlen.  The limit can be zero or positive.
         260                 :            :  * If there is no limit, then d.maxlen == -1.
         261                 :            :  *
         262                 :            :  * After an item is added to a deque, we check to see if the size has
         263                 :            :  * grown past the limit. If it has, we get the size back down to the limit
         264                 :            :  * by popping an item off of the opposite end.  The methods that can
         265                 :            :  * trigger this are append(), appendleft(), extend(), and extendleft().
         266                 :            :  *
         267                 :            :  * The macro to check whether a deque needs to be trimmed uses a single
         268                 :            :  * unsigned test that returns true whenever 0 <= maxlen < Py_SIZE(deque).
         269                 :            :  */
         270                 :            :
         271                 :            : #define NEEDS_TRIM(deque, maxlen) ((size_t)(maxlen) < (size_t)(Py_SIZE(deque)))
         272                 :            :
         273                 :            : static inline int
         274                 :          0 : deque_append_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
         275                 :            : {
         276         [ #  # ]:          0 :     if (deque->rightindex == BLOCKLEN - 1) {
         277                 :          0 :         block *b = newblock(deque);
         278         [ #  # ]:          0 :         if (b == NULL)
         279                 :          0 :             return -1;
         280                 :          0 :         b->leftlink = deque->rightblock;
         281                 :            :         CHECK_END(deque->rightblock->rightlink);
         282                 :          0 :         deque->rightblock->rightlink = b;
         283                 :          0 :         deque->rightblock = b;
         284                 :            :         MARK_END(b->rightlink);
         285                 :          0 :         deque->rightindex = -1;
         286                 :            :     }
         287                 :          0 :     Py_SET_SIZE(deque, Py_SIZE(deque) + 1);
         288                 :          0 :     deque->rightindex++;
         289                 :          0 :     deque->rightblock->data[deque->rightindex] = item;
         290         [ #  # ]:          0 :     if (NEEDS_TRIM(deque, maxlen)) {
         291                 :          0 :         PyObject *olditem = deque_popleft(deque, NULL);
         292                 :          0 :         Py_DECREF(olditem);
         293                 :            :     } else {
         294                 :          0 :         deque->state++;
         295                 :            :     }
         296                 :          0 :     return 0;
         297                 :            : }
         298                 :            :
         299                 :            : static PyObject *
         300                 :          0 : deque_append(dequeobject *deque, PyObject *item)
         301                 :            : {
         302         [ #  # ]:          0 :     if (deque_append_internal(deque, Py_NewRef(item), deque->maxlen) < 0)
         303                 :          0 :         return NULL;
         304                 :          0 :     Py_RETURN_NONE;
         305                 :            : }
         306                 :            :
         307                 :            : PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
         308                 :            :
         309                 :            : static inline int
         310                 :          0 : deque_appendleft_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
         311                 :            : {
         312         [ #  # ]:          0 :     if (deque->leftindex == 0) {
         313                 :          0 :         block *b = newblock(deque);
         314         [ #  # ]:          0 :         if (b == NULL)
         315                 :          0 :             return -1;
         316                 :          0 :         b->rightlink = deque->leftblock;
         317                 :            :         CHECK_END(deque->leftblock->leftlink);
         318                 :          0 :         deque->leftblock->leftlink = b;
         319                 :          0 :         deque->leftblock = b;
         320                 :            :         MARK_END(b->leftlink);
         321                 :          0 :         deque->leftindex = BLOCKLEN;
         322                 :            :     }
         323                 :          0 :     Py_SET_SIZE(deque, Py_SIZE(deque) + 1);
         324                 :          0 :     deque->leftindex--;
         325                 :          0 :     deque->leftblock->data[deque->leftindex] = item;
         326         [ #  # ]:          0 :     if (NEEDS_TRIM(deque, deque->maxlen)) {
         327                 :          0 :         PyObject *olditem = deque_pop(deque, NULL);
         328                 :          0 :         Py_DECREF(olditem);
         329                 :            :     } else {
         330                 :          0 :         deque->state++;
         331                 :            :     }
         332                 :          0 :     return 0;
         333                 :            : }
         334                 :            :
         335                 :            : static PyObject *
         336                 :          0 : deque_appendleft(dequeobject *deque, PyObject *item)
         337                 :            : {
         338         [ #  # ]:          0 :     if (deque_appendleft_internal(deque, Py_NewRef(item), deque->maxlen) < 0)
         339                 :          0 :         return NULL;
         340                 :          0 :     Py_RETURN_NONE;
         341                 :            : }
         342                 :            :
         343                 :            : PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
         344                 :            :
         345                 :            : static PyObject*
         346                 :          0 : finalize_iterator(PyObject *it)
         347                 :            : {
         348         [ #  # ]:          0 :     if (PyErr_Occurred()) {
         349         [ #  # ]:          0 :         if (PyErr_ExceptionMatches(PyExc_StopIteration))
         350                 :          0 :             PyErr_Clear();
         351                 :            :         else {
         352                 :          0 :             Py_DECREF(it);
         353                 :          0 :             return NULL;
         354                 :            :         }
         355                 :            :     }
         356                 :          0 :     Py_DECREF(it);
         357                 :          0 :     Py_RETURN_NONE;
         358                 :            : }
         359                 :            :
         360                 :            : /* Run an iterator to exhaustion.  Shortcut for
         361                 :            :    the extend/extendleft methods when maxlen == 0. */
         362                 :            : static PyObject*
         363                 :          0 : consume_iterator(PyObject *it)
         364                 :            : {
         365                 :            :     PyObject *(*iternext)(PyObject *);
         366                 :            :     PyObject *item;
         367                 :            :
         368                 :          0 :     iternext = *Py_TYPE(it)->tp_iternext;
         369         [ #  # ]:          0 :     while ((item = iternext(it)) != NULL) {
         370                 :          0 :         Py_DECREF(item);
         371                 :            :     }
         372                 :          0 :     return finalize_iterator(it);
         373                 :            : }
         374                 :            :
         375                 :            : static PyObject *
         376                 :          0 : deque_extend(dequeobject *deque, PyObject *iterable)
         377                 :            : {
         378                 :            :     PyObject *it, *item;
         379                 :            :     PyObject *(*iternext)(PyObject *);
         380                 :          0 :     Py_ssize_t maxlen = deque->maxlen;
         381                 :            :
         382                 :            :     /* Handle case where id(deque) == id(iterable) */
         383         [ #  # ]:          0 :     if ((PyObject *)deque == iterable) {
         384                 :            :         PyObject *result;
         385                 :          0 :         PyObject *s = PySequence_List(iterable);
         386         [ #  # ]:          0 :         if (s == NULL)
         387                 :          0 :             return NULL;
         388                 :          0 :         result = deque_extend(deque, s);
         389                 :          0 :         Py_DECREF(s);
         390                 :          0 :         return result;
         391                 :            :     }
         392                 :            :
         393                 :          0 :     it = PyObject_GetIter(iterable);
         394         [ #  # ]:          0 :     if (it == NULL)
         395                 :          0 :         return NULL;
         396                 :            :
         397         [ #  # ]:          0 :     if (maxlen == 0)
         398                 :          0 :         return consume_iterator(it);
         399                 :            :
         400                 :            :     /* Space saving heuristic.  Start filling from the left */
         401         [ #  # ]:          0 :     if (Py_SIZE(deque) == 0) {
         402                 :            :         assert(deque->leftblock == deque->rightblock);
         403                 :            :         assert(deque->leftindex == deque->rightindex+1);
         404                 :          0 :         deque->leftindex = 1;
         405                 :          0 :         deque->rightindex = 0;
         406                 :            :     }
         407                 :            :
         408                 :          0 :     iternext = *Py_TYPE(it)->tp_iternext;
         409         [ #  # ]:          0 :     while ((item = iternext(it)) != NULL) {
         410         [ #  # ]:          0 :         if (deque_append_internal(deque, item, maxlen) == -1) {
         411                 :          0 :             Py_DECREF(item);
         412                 :          0 :             Py_DECREF(it);
         413                 :          0 :             return NULL;
         414                 :            :         }
         415                 :            :     }
         416                 :          0 :     return finalize_iterator(it);
         417                 :            : }
         418                 :            :
         419                 :            : PyDoc_STRVAR(extend_doc,
         420                 :            : "Extend the right side of the deque with elements from the iterable");
         421                 :            :
         422                 :            : static PyObject *
         423                 :          0 : deque_extendleft(dequeobject *deque, PyObject *iterable)
         424                 :            : {
         425                 :            :     PyObject *it, *item;
         426                 :            :     PyObject *(*iternext)(PyObject *);
         427                 :          0 :     Py_ssize_t maxlen = deque->maxlen;
         428                 :            :
         429                 :            :     /* Handle case where id(deque) == id(iterable) */
         430         [ #  # ]:          0 :     if ((PyObject *)deque == iterable) {
         431                 :            :         PyObject *result;
         432                 :          0 :         PyObject *s = PySequence_List(iterable);
         433         [ #  # ]:          0 :         if (s == NULL)
         434                 :          0 :             return NULL;
         435                 :          0 :         result = deque_extendleft(deque, s);
         436                 :          0 :         Py_DECREF(s);
         437                 :          0 :         return result;
         438                 :            :     }
         439                 :            :
         440                 :          0 :     it = PyObject_GetIter(iterable);
         441         [ #  # ]:          0 :     if (it == NULL)
         442                 :          0 :         return NULL;
         443                 :            :
         444         [ #  # ]:          0 :     if (maxlen == 0)
         445                 :          0 :         return consume_iterator(it);
         446                 :            :
         447                 :            :     /* Space saving heuristic.  Start filling from the right */
         448         [ #  # ]:          0 :     if (Py_SIZE(deque) == 0) {
         449                 :            :         assert(deque->leftblock == deque->rightblock);
         450                 :            :         assert(deque->leftindex == deque->rightindex+1);
         451                 :          0 :         deque->leftindex = BLOCKLEN - 1;
         452                 :          0 :         deque->rightindex = BLOCKLEN - 2;
         453                 :            :     }
         454                 :            :
         455                 :          0 :     iternext = *Py_TYPE(it)->tp_iternext;
         456         [ #  # ]:          0 :     while ((item = iternext(it)) != NULL) {
         457         [ #  # ]:          0 :         if (deque_appendleft_internal(deque, item, maxlen) == -1) {
         458                 :          0 :             Py_DECREF(item);
         459                 :          0 :             Py_DECREF(it);
         460                 :          0 :             return NULL;
         461                 :            :         }
         462                 :            :     }
         463                 :          0 :     return finalize_iterator(it);
         464                 :            : }
         465                 :            :
         466                 :            : PyDoc_STRVAR(extendleft_doc,
         467                 :            : "Extend the left side of the deque with elements from the iterable");
         468                 :            :
         469                 :            : static PyObject *
         470                 :          0 : deque_inplace_concat(dequeobject *deque, PyObject *other)
         471                 :            : {
         472                 :            :     PyObject *result;
         473                 :            :
         474                 :          0 :     result = deque_extend(deque, other);
         475         [ #  # ]:          0 :     if (result == NULL)
         476                 :          0 :         return result;
         477                 :          0 :     Py_INCREF(deque);
         478                 :          0 :     Py_DECREF(result);
         479                 :          0 :     return (PyObject *)deque;
         480                 :            : }
         481                 :            :
         482                 :            : static PyObject *
         483                 :          0 : deque_copy(PyObject *deque, PyObject *Py_UNUSED(ignored))
         484                 :            : {
         485                 :            :     PyObject *result;
         486                 :          0 :     dequeobject *old_deque = (dequeobject *)deque;
         487         [ #  # ]:          0 :     if (Py_IS_TYPE(deque, &deque_type)) {
         488                 :            :         dequeobject *new_deque;
         489                 :            :         PyObject *rv;
         490                 :            :
         491                 :          0 :         new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL);
         492         [ #  # ]:          0 :         if (new_deque == NULL)
         493                 :          0 :             return NULL;
         494                 :          0 :         new_deque->maxlen = old_deque->maxlen;
         495                 :            :         /* Fast path for the deque_repeat() common case where len(deque) == 1 */
         496         [ #  # ]:          0 :         if (Py_SIZE(deque) == 1) {
         497                 :          0 :             PyObject *item = old_deque->leftblock->data[old_deque->leftindex];
         498                 :          0 :             rv = deque_append(new_deque, item);
         499                 :            :         } else {
         500                 :          0 :             rv = deque_extend(new_deque, deque);
         501                 :            :         }
         502         [ #  # ]:          0 :         if (rv != NULL) {
         503                 :          0 :             Py_DECREF(rv);
         504                 :          0 :             return (PyObject *)new_deque;
         505                 :            :         }
         506                 :          0 :         Py_DECREF(new_deque);
         507                 :          0 :         return NULL;
         508                 :            :     }
         509         [ #  # ]:          0 :     if (old_deque->maxlen < 0)
         510                 :          0 :         result = PyObject_CallOneArg((PyObject *)(Py_TYPE(deque)), deque);
         511                 :            :     else
         512                 :          0 :         result = PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
         513                 :            :                                        deque, old_deque->maxlen, NULL);
         514   [ #  #  #  # ]:          0 :     if (result != NULL && !PyObject_TypeCheck(result, &deque_type)) {
         515                 :          0 :         PyErr_Format(PyExc_TypeError,
         516                 :            :                      "%.200s() must return a deque, not %.200s",
         517                 :          0 :                      Py_TYPE(deque)->tp_name, Py_TYPE(result)->tp_name);
         518                 :          0 :         Py_DECREF(result);
         519                 :          0 :         return NULL;
         520                 :            :     }
         521                 :          0 :     return result;
         522                 :            : }
         523                 :            :
         524                 :            : PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
         525                 :            :
         526                 :            : static PyObject *
         527                 :          0 : deque_concat(dequeobject *deque, PyObject *other)
         528                 :            : {
         529                 :            :     PyObject *new_deque, *result;
         530                 :            :     int rv;
         531                 :            :
         532                 :          0 :     rv = PyObject_IsInstance(other, (PyObject *)&deque_type);
         533         [ #  # ]:          0 :     if (rv <= 0) {
         534         [ #  # ]:          0 :         if (rv == 0) {
         535                 :          0 :             PyErr_Format(PyExc_TypeError,
         536                 :            :                          "can only concatenate deque (not \"%.200s\") to deque",
         537                 :          0 :                          Py_TYPE(other)->tp_name);
         538                 :            :         }
         539                 :          0 :         return NULL;
         540                 :            :     }
         541                 :            :
         542                 :          0 :     new_deque = deque_copy((PyObject *)deque, NULL);
         543         [ #  # ]:          0 :     if (new_deque == NULL)
         544                 :          0 :         return NULL;
         545                 :          0 :     result = deque_extend((dequeobject *)new_deque, other);
         546         [ #  # ]:          0 :     if (result == NULL) {
         547                 :          0 :         Py_DECREF(new_deque);
         548                 :          0 :         return NULL;
         549                 :            :     }
         550                 :          0 :     Py_DECREF(result);
         551                 :          0 :     return new_deque;
         552                 :            : }
         553                 :            :
         554                 :            : static int
         555                 :          4 : deque_clear(dequeobject *deque)
         556                 :            : {
         557                 :            :     block *b;
         558                 :            :     block *prevblock;
         559                 :            :     block *leftblock;
         560                 :            :     Py_ssize_t leftindex;
         561                 :            :     Py_ssize_t n, m;
         562                 :            :     PyObject *item;
         563                 :            :     PyObject **itemptr, **limit;
         564                 :            :
         565         [ +  - ]:          4 :     if (Py_SIZE(deque) == 0)
         566                 :          4 :         return 0;
         567                 :            :
         568                 :            :     /* During the process of clearing a deque, decrefs can cause the
         569                 :            :        deque to mutate.  To avoid fatal confusion, we have to make the
         570                 :            :        deque empty before clearing the blocks and never refer to
         571                 :            :        anything via deque->ref while clearing.  (This is the same
         572                 :            :        technique used for clearing lists, sets, and dicts.)
         573                 :            :
         574                 :            :        Making the deque empty requires allocating a new empty block.  In
         575                 :            :        the unlikely event that memory is full, we fall back to an
         576                 :            :        alternate method that doesn't require a new block.  Repeating
         577                 :            :        pops in a while-loop is slower, possibly re-entrant (and a clever
         578                 :            :        adversary could cause it to never terminate).
         579                 :            :     */
         580                 :            :
         581                 :          0 :     b = newblock(deque);
         582         [ #  # ]:          0 :     if (b == NULL) {
         583                 :          0 :         PyErr_Clear();
         584                 :          0 :         goto alternate_method;
         585                 :            :     }
         586                 :            :
         587                 :            :     /* Remember the old size, leftblock, and leftindex */
         588                 :          0 :     n = Py_SIZE(deque);
         589                 :          0 :     leftblock = deque->leftblock;
         590                 :          0 :     leftindex = deque->leftindex;
         591                 :            :
         592                 :            :     /* Set the deque to be empty using the newly allocated block */
         593                 :            :     MARK_END(b->leftlink);
         594                 :            :     MARK_END(b->rightlink);
         595                 :          0 :     Py_SET_SIZE(deque, 0);
         596                 :          0 :     deque->leftblock = b;
         597                 :          0 :     deque->rightblock = b;
         598                 :          0 :     deque->leftindex = CENTER + 1;
         599                 :          0 :     deque->rightindex = CENTER;
         600                 :          0 :     deque->state++;
         601                 :            :
         602                 :            :     /* Now the old size, leftblock, and leftindex are disconnected from
         603                 :            :        the empty deque and we can use them to decref the pointers.
         604                 :            :     */
         605                 :          0 :     m = (BLOCKLEN - leftindex > n) ? n : BLOCKLEN - leftindex;
         606                 :          0 :     itemptr = &leftblock->data[leftindex];
         607                 :          0 :     limit = itemptr + m;
         608                 :          0 :     n -= m;
         609                 :            :     while (1) {
         610         [ #  # ]:          0 :         if (itemptr == limit) {
         611         [ #  # ]:          0 :             if (n == 0)
         612                 :          0 :                 break;
         613                 :            :             CHECK_NOT_END(leftblock->rightlink);
         614                 :          0 :             prevblock = leftblock;
         615                 :          0 :             leftblock = leftblock->rightlink;
         616                 :          0 :             m = (n > BLOCKLEN) ? BLOCKLEN : n;
         617                 :          0 :             itemptr = leftblock->data;
         618                 :          0 :             limit = itemptr + m;
         619                 :          0 :             n -= m;
         620                 :          0 :             freeblock(deque, prevblock);
         621                 :            :         }
         622                 :          0 :         item = *(itemptr++);
         623                 :          0 :         Py_DECREF(item);
         624                 :            :     }
         625                 :            :     CHECK_END(leftblock->rightlink);
         626                 :          0 :     freeblock(deque, leftblock);
         627                 :          0 :     return 0;
         628                 :            :
         629                 :          0 :   alternate_method:
         630         [ #  # ]:          0 :     while (Py_SIZE(deque)) {
         631                 :          0 :         item = deque_pop(deque, NULL);
         632                 :            :         assert (item != NULL);
         633                 :          0 :         Py_DECREF(item);
         634                 :            :     }
         635                 :          0 :     return 0;
         636                 :            : }
         637                 :            :
         638                 :            : static PyObject *
         639                 :          0 : deque_clearmethod(dequeobject *deque, PyObject *Py_UNUSED(ignored))
         640                 :            : {
         641                 :          0 :     deque_clear(deque);
         642                 :          0 :     Py_RETURN_NONE;
         643                 :            : }
         644                 :            :
         645                 :            : PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
         646                 :            :
         647                 :            : static PyObject *
         648                 :          0 : deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
         649                 :            : {
         650                 :            :     Py_ssize_t i, m, size;
         651                 :            :     PyObject *seq;
         652                 :            :     PyObject *rv;
         653                 :            :
         654                 :          0 :     size = Py_SIZE(deque);
         655   [ #  #  #  # ]:          0 :     if (size == 0 || n == 1) {
         656                 :          0 :         return Py_NewRef(deque);
         657                 :            :     }
         658                 :            :
         659         [ #  # ]:          0 :     if (n <= 0) {
         660                 :          0 :         deque_clear(deque);
         661                 :          0 :         return Py_NewRef(deque);
         662                 :            :     }
         663                 :            :
         664         [ #  # ]:          0 :     if (size == 1) {
         665                 :            :         /* common case, repeating a single element */
         666                 :          0 :         PyObject *item = deque->leftblock->data[deque->leftindex];
         667                 :            :
         668   [ #  #  #  # ]:          0 :         if (deque->maxlen >= 0 && n > deque->maxlen)
         669                 :          0 :             n = deque->maxlen;
         670                 :            :
         671                 :          0 :         deque->state++;
         672         [ #  # ]:          0 :         for (i = 0 ; i < n-1 ; ) {
         673         [ #  # ]:          0 :             if (deque->rightindex == BLOCKLEN - 1) {
         674                 :          0 :                 block *b = newblock(deque);
         675         [ #  # ]:          0 :                 if (b == NULL) {
         676                 :          0 :                     Py_SET_SIZE(deque, Py_SIZE(deque) + i);
         677                 :          0 :                     return NULL;
         678                 :            :                 }
         679                 :          0 :                 b->leftlink = deque->rightblock;
         680                 :            :                 CHECK_END(deque->rightblock->rightlink);
         681                 :          0 :                 deque->rightblock->rightlink = b;
         682                 :          0 :                 deque->rightblock = b;
         683                 :            :                 MARK_END(b->rightlink);
         684                 :          0 :                 deque->rightindex = -1;
         685                 :            :             }
         686                 :          0 :             m = n - 1 - i;
         687         [ #  # ]:          0 :             if (m > BLOCKLEN - 1 - deque->rightindex)
         688                 :          0 :                 m = BLOCKLEN - 1 - deque->rightindex;
         689                 :          0 :             i += m;
         690         [ #  # ]:          0 :             while (m--) {
         691                 :          0 :                 deque->rightindex++;
         692                 :          0 :                 deque->rightblock->data[deque->rightindex] = Py_NewRef(item);
         693                 :            :             }
         694                 :            :         }
         695                 :          0 :         Py_SET_SIZE(deque, Py_SIZE(deque) + i);
         696                 :          0 :         return Py_NewRef(deque);
         697                 :            :     }
         698                 :            :
         699         [ #  # ]:          0 :     if ((size_t)size > PY_SSIZE_T_MAX / (size_t)n) {
         700                 :          0 :         return PyErr_NoMemory();
         701                 :            :     }
         702                 :            :
         703                 :          0 :     seq = PySequence_List((PyObject *)deque);
         704         [ #  # ]:          0 :     if (seq == NULL)
         705                 :          0 :         return seq;
         706                 :            :
         707                 :            :     /* Reduce the number of repetitions when maxlen would be exceeded */
         708   [ #  #  #  # ]:          0 :     if (deque->maxlen >= 0 && n * size > deque->maxlen)
         709                 :          0 :         n = (deque->maxlen + size - 1) / size;
         710                 :            :
         711         [ #  # ]:          0 :     for (i = 0 ; i < n-1 ; i++) {
         712                 :          0 :         rv = deque_extend(deque, seq);
         713         [ #  # ]:          0 :         if (rv == NULL) {
         714                 :          0 :             Py_DECREF(seq);
         715                 :          0 :             return NULL;
         716                 :            :         }
         717                 :          0 :         Py_DECREF(rv);
         718                 :            :     }
         719                 :          0 :     Py_INCREF(deque);
         720                 :          0 :     Py_DECREF(seq);
         721                 :          0 :     return (PyObject *)deque;
         722                 :            : }
         723                 :            :
         724                 :            : static PyObject *
         725                 :          0 : deque_repeat(dequeobject *deque, Py_ssize_t n)
         726                 :            : {
         727                 :            :     dequeobject *new_deque;
         728                 :            :     PyObject *rv;
         729                 :            :
         730                 :          0 :     new_deque = (dequeobject *)deque_copy((PyObject *) deque, NULL);
         731         [ #  # ]:          0 :     if (new_deque == NULL)
         732                 :          0 :         return NULL;
         733                 :          0 :     rv = deque_inplace_repeat(new_deque, n);
         734                 :          0 :     Py_DECREF(new_deque);
         735                 :          0 :     return rv;
         736                 :            : }
         737                 :            :
         738                 :            : /* The rotate() method is part of the public API and is used internally
         739                 :            : as a primitive for other methods.
         740                 :            :
         741                 :            : Rotation by 1 or -1 is a common case, so any optimizations for high
         742                 :            : volume rotations should take care not to penalize the common case.
         743                 :            :
         744                 :            : Conceptually, a rotate by one is equivalent to a pop on one side and an
         745                 :            : append on the other.  However, a pop/append pair is unnecessarily slow
         746                 :            : because it requires an incref/decref pair for an object located randomly
         747                 :            : in memory.  It is better to just move the object pointer from one block
         748                 :            : to the next without changing the reference count.
         749                 :            :
         750                 :            : When moving batches of pointers, it is tempting to use memcpy() but that
         751                 :            : proved to be slower than a simple loop for a variety of reasons.
         752                 :            : Memcpy() cannot know in advance that we're copying pointers instead of
         753                 :            : bytes, that the source and destination are pointer aligned and
         754                 :            : non-overlapping, that moving just one pointer is a common case, that we
         755                 :            : never need to move more than BLOCKLEN pointers, and that at least one
         756                 :            : pointer is always moved.
         757                 :            :
         758                 :            : For high volume rotations, newblock() and freeblock() are never called
         759                 :            : more than once.  Previously emptied blocks are immediately reused as a
         760                 :            : destination block.  If a block is left-over at the end, it is freed.
         761                 :            : */
         762                 :            :
         763                 :            : static int
         764                 :          0 : _deque_rotate(dequeobject *deque, Py_ssize_t n)
         765                 :            : {
         766                 :          0 :     block *b = NULL;
         767                 :          0 :     block *leftblock = deque->leftblock;
         768                 :          0 :     block *rightblock = deque->rightblock;
         769                 :          0 :     Py_ssize_t leftindex = deque->leftindex;
         770                 :          0 :     Py_ssize_t rightindex = deque->rightindex;
         771                 :          0 :     Py_ssize_t len=Py_SIZE(deque), halflen=len>>1;
         772                 :          0 :     int rv = -1;
         773                 :            :
         774         [ #  # ]:          0 :     if (len <= 1)
         775                 :          0 :         return 0;
         776   [ #  #  #  # ]:          0 :     if (n > halflen || n < -halflen) {
         777                 :          0 :         n %= len;
         778         [ #  # ]:          0 :         if (n > halflen)
         779                 :          0 :             n -= len;
         780         [ #  # ]:          0 :         else if (n < -halflen)
         781                 :          0 :             n += len;
         782                 :            :     }
         783                 :            :     assert(len > 1);
         784                 :            :     assert(-halflen <= n && n <= halflen);
         785                 :            :
         786                 :          0 :     deque->state++;
         787         [ #  # ]:          0 :     while (n > 0) {
         788         [ #  # ]:          0 :         if (leftindex == 0) {
         789         [ #  # ]:          0 :             if (b == NULL) {
         790                 :          0 :                 b = newblock(deque);
         791         [ #  # ]:          0 :                 if (b == NULL)
         792                 :          0 :                     goto done;
         793                 :            :             }
         794                 :          0 :             b->rightlink = leftblock;
         795                 :            :             CHECK_END(leftblock->leftlink);
         796                 :          0 :             leftblock->leftlink = b;
         797                 :          0 :             leftblock = b;
         798                 :            :             MARK_END(b->leftlink);
         799                 :          0 :             leftindex = BLOCKLEN;
         800                 :          0 :             b = NULL;
         801                 :            :         }
         802                 :            :         assert(leftindex > 0);
         803                 :            :         {
         804                 :            :             PyObject **src, **dest;
         805                 :          0 :             Py_ssize_t m = n;
         806                 :            :
         807         [ #  # ]:          0 :             if (m > rightindex + 1)
         808                 :          0 :                 m = rightindex + 1;
         809         [ #  # ]:          0 :             if (m > leftindex)
         810                 :          0 :                 m = leftindex;
         811                 :            :             assert (m > 0 && m <= len);
         812                 :          0 :             rightindex -= m;
         813                 :          0 :             leftindex -= m;
         814                 :          0 :             src = &rightblock->data[rightindex + 1];
         815                 :          0 :             dest = &leftblock->data[leftindex];
         816                 :          0 :             n -= m;
         817                 :            :             do {
         818                 :          0 :                 *(dest++) = *(src++);
         819         [ #  # ]:          0 :             } while (--m);
         820                 :            :         }
         821         [ #  # ]:          0 :         if (rightindex < 0) {
         822                 :            :             assert(leftblock != rightblock);
         823                 :            :             assert(b == NULL);
         824                 :          0 :             b = rightblock;
         825                 :            :             CHECK_NOT_END(rightblock->leftlink);
         826                 :          0 :             rightblock = rightblock->leftlink;
         827                 :            :             MARK_END(rightblock->rightlink);
         828                 :          0 :             rightindex = BLOCKLEN - 1;
         829                 :            :         }
         830                 :            :     }
         831         [ #  # ]:          0 :     while (n < 0) {
         832         [ #  # ]:          0 :         if (rightindex == BLOCKLEN - 1) {
         833         [ #  # ]:          0 :             if (b == NULL) {
         834                 :          0 :                 b = newblock(deque);
         835         [ #  # ]:          0 :                 if (b == NULL)
         836                 :          0 :                     goto done;
         837                 :            :             }
         838                 :          0 :             b->leftlink = rightblock;
         839                 :            :             CHECK_END(rightblock->rightlink);
         840                 :          0 :             rightblock->rightlink = b;
         841                 :          0 :             rightblock = b;
         842                 :            :             MARK_END(b->rightlink);
         843                 :          0 :             rightindex = -1;
         844                 :          0 :             b = NULL;
         845                 :            :         }
         846                 :            :         assert (rightindex < BLOCKLEN - 1);
         847                 :            :         {
         848                 :            :             PyObject **src, **dest;
         849                 :          0 :             Py_ssize_t m = -n;
         850                 :            :
         851         [ #  # ]:          0 :             if (m > BLOCKLEN - leftindex)
         852                 :          0 :                 m = BLOCKLEN - leftindex;
         853         [ #  # ]:          0 :             if (m > BLOCKLEN - 1 - rightindex)
         854                 :          0 :                 m = BLOCKLEN - 1 - rightindex;
         855                 :            :             assert (m > 0 && m <= len);
         856                 :          0 :             src = &leftblock->data[leftindex];
         857                 :          0 :             dest = &rightblock->data[rightindex + 1];
         858                 :          0 :             leftindex += m;
         859                 :          0 :             rightindex += m;
         860                 :          0 :             n += m;
         861                 :            :             do {
         862                 :          0 :                 *(dest++) = *(src++);
         863         [ #  # ]:          0 :             } while (--m);
         864                 :            :         }
         865         [ #  # ]:          0 :         if (leftindex == BLOCKLEN) {
         866                 :            :             assert(leftblock != rightblock);
         867                 :            :             assert(b == NULL);
         868                 :          0 :             b = leftblock;
         869                 :            :             CHECK_NOT_END(leftblock->rightlink);
         870                 :          0 :             leftblock = leftblock->rightlink;
         871                 :            :             MARK_END(leftblock->leftlink);
         872                 :          0 :             leftindex = 0;
         873                 :            :         }
         874                 :            :     }
         875                 :          0 :     rv = 0;
         876                 :          0 : done:
         877         [ #  # ]:          0 :     if (b != NULL)
         878                 :          0 :         freeblock(deque, b);
         879                 :          0 :     deque->leftblock = leftblock;
         880                 :          0 :     deque->rightblock = rightblock;
         881                 :          0 :     deque->leftindex = leftindex;
         882                 :          0 :     deque->rightindex = rightindex;
         883                 :            :
         884                 :          0 :     return rv;
         885                 :            : }
         886                 :            :
         887                 :            : static PyObject *
         888                 :          0 : deque_rotate(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
         889                 :            : {
         890                 :          0 :     Py_ssize_t n=1;
         891                 :            :
         892   [ #  #  #  #  :          0 :     if (!_PyArg_CheckPositional("deque.rotate", nargs, 0, 1)) {
                       #  # ]
         893                 :          0 :         return NULL;
         894                 :            :     }
         895         [ #  # ]:          0 :     if (nargs) {
         896                 :          0 :         PyObject *index = _PyNumber_Index(args[0]);
         897         [ #  # ]:          0 :         if (index == NULL) {
         898                 :          0 :             return NULL;
         899                 :            :         }
         900                 :          0 :         n = PyLong_AsSsize_t(index);
         901                 :          0 :         Py_DECREF(index);
         902   [ #  #  #  # ]:          0 :         if (n == -1 && PyErr_Occurred()) {
         903                 :          0 :             return NULL;
         904                 :            :         }
         905                 :            :     }
         906                 :            :
         907         [ #  # ]:          0 :     if (!_deque_rotate(deque, n))
         908                 :          0 :         Py_RETURN_NONE;
         909                 :          0 :     return NULL;
         910                 :            : }
         911                 :            :
         912                 :            : PyDoc_STRVAR(rotate_doc,
         913                 :            : "Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left.");
         914                 :            :
         915                 :            : static PyObject *
         916                 :          0 : deque_reverse(dequeobject *deque, PyObject *unused)
         917                 :            : {
         918                 :          0 :     block *leftblock = deque->leftblock;
         919                 :          0 :     block *rightblock = deque->rightblock;
         920                 :          0 :     Py_ssize_t leftindex = deque->leftindex;
         921                 :          0 :     Py_ssize_t rightindex = deque->rightindex;
         922                 :          0 :     Py_ssize_t n = Py_SIZE(deque) >> 1;
         923                 :            :     PyObject *tmp;
         924                 :            :
         925         [ #  # ]:          0 :     while (--n >= 0) {
         926                 :            :         /* Validate that pointers haven't met in the middle */
         927                 :            :         assert(leftblock != rightblock || leftindex < rightindex);
         928                 :            :         CHECK_NOT_END(leftblock);
         929                 :            :         CHECK_NOT_END(rightblock);
         930                 :            :
         931                 :            :         /* Swap */
         932                 :          0 :         tmp = leftblock->data[leftindex];
         933                 :          0 :         leftblock->data[leftindex] = rightblock->data[rightindex];
         934                 :          0 :         rightblock->data[rightindex] = tmp;
         935                 :            :
         936                 :            :         /* Advance left block/index pair */
         937                 :          0 :         leftindex++;
         938         [ #  # ]:          0 :         if (leftindex == BLOCKLEN) {
         939                 :          0 :             leftblock = leftblock->rightlink;
         940                 :          0 :             leftindex = 0;
         941                 :            :         }
         942                 :            :
         943                 :            :         /* Step backwards with the right block/index pair */
         944                 :          0 :         rightindex--;
         945         [ #  # ]:          0 :         if (rightindex < 0) {
         946                 :          0 :             rightblock = rightblock->leftlink;
         947                 :          0 :             rightindex = BLOCKLEN - 1;
         948                 :            :         }
         949                 :            :     }
         950                 :          0 :     Py_RETURN_NONE;
         951                 :            : }
         952                 :            :
         953                 :            : PyDoc_STRVAR(reverse_doc,
         954                 :            : "D.reverse() -- reverse *IN PLACE*");
         955                 :            :
         956                 :            : static PyObject *
         957                 :          0 : deque_count(dequeobject *deque, PyObject *v)
         958                 :            : {
         959                 :          0 :     block *b = deque->leftblock;
         960                 :          0 :     Py_ssize_t index = deque->leftindex;
         961                 :          0 :     Py_ssize_t n = Py_SIZE(deque);
         962                 :          0 :     Py_ssize_t count = 0;
         963                 :          0 :     size_t start_state = deque->state;
         964                 :            :     PyObject *item;
         965                 :            :     int cmp;
         966                 :            :
         967         [ #  # ]:          0 :     while (--n >= 0) {
         968                 :            :         CHECK_NOT_END(b);
         969                 :          0 :         item = Py_NewRef(b->data[index]);
         970                 :          0 :         cmp = PyObject_RichCompareBool(item, v, Py_EQ);
         971                 :          0 :         Py_DECREF(item);
         972         [ #  # ]:          0 :         if (cmp < 0)
         973                 :          0 :             return NULL;
         974                 :          0 :         count += cmp;
         975                 :            :
         976         [ #  # ]:          0 :         if (start_state != deque->state) {
         977                 :          0 :             PyErr_SetString(PyExc_RuntimeError,
         978                 :            :                             "deque mutated during iteration");
         979                 :          0 :             return NULL;
         980                 :            :         }
         981                 :            :
         982                 :            :         /* Advance left block/index pair */
         983                 :          0 :         index++;
         984         [ #  # ]:          0 :         if (index == BLOCKLEN) {
         985                 :          0 :             b = b->rightlink;
         986                 :          0 :             index = 0;
         987                 :            :         }
         988                 :            :     }
         989                 :          0 :     return PyLong_FromSsize_t(count);
         990                 :            : }
         991                 :            :
         992                 :            : PyDoc_STRVAR(count_doc,
         993                 :            : "D.count(value) -> integer -- return number of occurrences of value");
         994                 :            :
         995                 :            : static int
         996                 :          0 : deque_contains(dequeobject *deque, PyObject *v)
         997                 :            : {
         998                 :          0 :     block *b = deque->leftblock;
         999                 :          0 :     Py_ssize_t index = deque->leftindex;
        1000                 :          0 :     Py_ssize_t n = Py_SIZE(deque);
        1001                 :          0 :     size_t start_state = deque->state;
        1002                 :            :     PyObject *item;
        1003                 :            :     int cmp;
        1004                 :            :
        1005         [ #  # ]:          0 :     while (--n >= 0) {
        1006                 :            :         CHECK_NOT_END(b);
        1007                 :          0 :         item = Py_NewRef(b->data[index]);
        1008                 :          0 :         cmp = PyObject_RichCompareBool(item, v, Py_EQ);
        1009                 :          0 :         Py_DECREF(item);
        1010         [ #  # ]:          0 :         if (cmp) {
        1011                 :          0 :             return cmp;
        1012                 :            :         }
        1013         [ #  # ]:          0 :         if (start_state != deque->state) {
        1014                 :          0 :             PyErr_SetString(PyExc_RuntimeError,
        1015                 :            :                             "deque mutated during iteration");
        1016                 :          0 :             return -1;
        1017                 :            :         }
        1018                 :          0 :         index++;
        1019         [ #  # ]:          0 :         if (index == BLOCKLEN) {
        1020                 :          0 :             b = b->rightlink;
        1021                 :          0 :             index = 0;
        1022                 :            :         }
        1023                 :            :     }
        1024                 :          0 :     return 0;
        1025                 :            : }
        1026                 :            :
        1027                 :            : static Py_ssize_t
        1028                 :          8 : deque_len(dequeobject *deque)
        1029                 :            : {
        1030                 :          8 :     return Py_SIZE(deque);
        1031                 :            : }
        1032                 :            :
        1033                 :            : static PyObject *
        1034                 :          0 : deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
        1035                 :            : {
        1036                 :          0 :     Py_ssize_t i, n, start=0, stop=Py_SIZE(deque);
        1037                 :            :     PyObject *v, *item;
        1038                 :          0 :     block *b = deque->leftblock;
        1039                 :          0 :     Py_ssize_t index = deque->leftindex;
        1040                 :          0 :     size_t start_state = deque->state;
        1041                 :            :     int cmp;
        1042                 :            :
        1043         [ #  # ]:          0 :     if (!_PyArg_ParseStack(args, nargs, "O|O&O&:index", &v,
        1044                 :            :                            _PyEval_SliceIndexNotNone, &start,
        1045                 :            :                            _PyEval_SliceIndexNotNone, &stop)) {
        1046                 :          0 :         return NULL;
        1047                 :            :     }
        1048                 :            :
        1049         [ #  # ]:          0 :     if (start < 0) {
        1050                 :          0 :         start += Py_SIZE(deque);
        1051         [ #  # ]:          0 :         if (start < 0)
        1052                 :          0 :             start = 0;
        1053                 :            :     }
        1054         [ #  # ]:          0 :     if (stop < 0) {
        1055                 :          0 :         stop += Py_SIZE(deque);
        1056         [ #  # ]:          0 :         if (stop < 0)
        1057                 :          0 :             stop = 0;
        1058                 :            :     }
        1059         [ #  # ]:          0 :     if (stop > Py_SIZE(deque))
        1060                 :          0 :         stop = Py_SIZE(deque);
        1061         [ #  # ]:          0 :     if (start > stop)
        1062                 :          0 :         start = stop;
        1063                 :            :     assert(0 <= start && start <= stop && stop <= Py_SIZE(deque));
        1064                 :            :
        1065         [ #  # ]:          0 :     for (i=0 ; i < start - BLOCKLEN ; i += BLOCKLEN) {
        1066                 :          0 :         b = b->rightlink;
        1067                 :            :     }
        1068         [ #  # ]:          0 :     for ( ; i < start ; i++) {
        1069                 :          0 :         index++;
        1070         [ #  # ]:          0 :         if (index == BLOCKLEN) {
        1071                 :          0 :             b = b->rightlink;
        1072                 :          0 :             index = 0;
        1073                 :            :         }
        1074                 :            :     }
        1075                 :            :
        1076                 :          0 :     n = stop - i;
        1077         [ #  # ]:          0 :     while (--n >= 0) {
        1078                 :            :         CHECK_NOT_END(b);
        1079                 :          0 :         item = b->data[index];
        1080                 :          0 :         cmp = PyObject_RichCompareBool(item, v, Py_EQ);
        1081         [ #  # ]:          0 :         if (cmp > 0)
        1082                 :          0 :             return PyLong_FromSsize_t(stop - n - 1);
        1083         [ #  # ]:          0 :         if (cmp < 0)
        1084                 :          0 :             return NULL;
        1085         [ #  # ]:          0 :         if (start_state != deque->state) {
        1086                 :          0 :             PyErr_SetString(PyExc_RuntimeError,
        1087                 :            :                             "deque mutated during iteration");
        1088                 :          0 :             return NULL;
        1089                 :            :         }
        1090                 :          0 :         index++;
        1091         [ #  # ]:          0 :         if (index == BLOCKLEN) {
        1092                 :          0 :             b = b->rightlink;
        1093                 :          0 :             index = 0;
        1094                 :            :         }
        1095                 :            :     }
        1096                 :          0 :     PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
        1097                 :          0 :     return NULL;
        1098                 :            : }
        1099                 :            :
        1100                 :            : PyDoc_STRVAR(index_doc,
        1101                 :            : "D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
        1102                 :            : "Raises ValueError if the value is not present.");
        1103                 :            :
        1104                 :            : /* insert(), remove(), and delitem() are implemented in terms of
        1105                 :            :    rotate() for simplicity and reasonable performance near the end
        1106                 :            :    points.  If for some reason these methods become popular, it is not
        1107                 :            :    hard to re-implement this using direct data movement (similar to
        1108                 :            :    the code used in list slice assignments) and achieve a performance
        1109                 :            :    boost (by moving each pointer only once instead of twice).
        1110                 :            : */
        1111                 :            :
        1112                 :            : static PyObject *
        1113                 :          0 : deque_insert(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
        1114                 :            : {
        1115                 :            :     Py_ssize_t index;
        1116                 :          0 :     Py_ssize_t n = Py_SIZE(deque);
        1117                 :            :     PyObject *value;
        1118                 :            :     PyObject *rv;
        1119                 :            :
        1120         [ #  # ]:          0 :     if (!_PyArg_ParseStack(args, nargs, "nO:insert", &index, &value)) {
        1121                 :          0 :         return NULL;
        1122                 :            :     }
        1123                 :            :
        1124         [ #  # ]:          0 :     if (deque->maxlen == Py_SIZE(deque)) {
        1125                 :          0 :         PyErr_SetString(PyExc_IndexError, "deque already at its maximum size");
        1126                 :          0 :         return NULL;
        1127                 :            :     }
        1128         [ #  # ]:          0 :     if (index >= n)
        1129                 :          0 :         return deque_append(deque, value);
        1130   [ #  #  #  # ]:          0 :     if (index <= -n || index == 0)
        1131                 :          0 :         return deque_appendleft(deque, value);
        1132         [ #  # ]:          0 :     if (_deque_rotate(deque, -index))
        1133                 :          0 :         return NULL;
        1134         [ #  # ]:          0 :     if (index < 0)
        1135                 :          0 :         rv = deque_append(deque, value);
        1136                 :            :     else
        1137                 :          0 :         rv = deque_appendleft(deque, value);
        1138         [ #  # ]:          0 :     if (rv == NULL)
        1139                 :          0 :         return NULL;
        1140                 :          0 :     Py_DECREF(rv);
        1141         [ #  # ]:          0 :     if (_deque_rotate(deque, index))
        1142                 :          0 :         return NULL;
        1143                 :          0 :     Py_RETURN_NONE;
        1144                 :            : }
        1145                 :            :
        1146                 :            : PyDoc_STRVAR(insert_doc,
        1147                 :            : "D.insert(index, object) -- insert object before index");
        1148                 :            :
        1149                 :            : PyDoc_STRVAR(remove_doc,
        1150                 :            : "D.remove(value) -- remove first occurrence of value.");
        1151                 :            :
        1152                 :            : static int
        1153                 :       1841 : valid_index(Py_ssize_t i, Py_ssize_t limit)
        1154                 :            : {
        1155                 :            :     /* The cast to size_t lets us use just a single comparison
        1156                 :            :        to check whether i is in the range: 0 <= i < limit */
        1157                 :       1841 :     return (size_t) i < (size_t) limit;
        1158                 :            : }
        1159                 :            :
        1160                 :            : static PyObject *
        1161                 :          0 : deque_item(dequeobject *deque, Py_ssize_t i)
        1162                 :            : {
        1163                 :            :     block *b;
        1164                 :            :     PyObject *item;
        1165                 :          0 :     Py_ssize_t n, index=i;
        1166                 :            :
        1167         [ #  # ]:          0 :     if (!valid_index(i, Py_SIZE(deque))) {
        1168                 :          0 :         PyErr_SetString(PyExc_IndexError, "deque index out of range");
        1169                 :          0 :         return NULL;
        1170                 :            :     }
        1171                 :            :
        1172         [ #  # ]:          0 :     if (i == 0) {
        1173                 :          0 :         i = deque->leftindex;
        1174                 :          0 :         b = deque->leftblock;
        1175         [ #  # ]:          0 :     } else if (i == Py_SIZE(deque) - 1) {
        1176                 :          0 :         i = deque->rightindex;
        1177                 :          0 :         b = deque->rightblock;
        1178                 :            :     } else {
        1179                 :          0 :         i += deque->leftindex;
        1180                 :          0 :         n = (Py_ssize_t)((size_t) i / BLOCKLEN);
        1181                 :          0 :         i = (Py_ssize_t)((size_t) i % BLOCKLEN);
        1182         [ #  # ]:          0 :         if (index < (Py_SIZE(deque) >> 1)) {
        1183                 :          0 :             b = deque->leftblock;
        1184         [ #  # ]:          0 :             while (--n >= 0)
        1185                 :          0 :                 b = b->rightlink;
        1186                 :            :         } else {
        1187                 :          0 :             n = (Py_ssize_t)(
        1188                 :          0 :                     ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
        1189                 :          0 :                     / BLOCKLEN - n);
        1190                 :          0 :             b = deque->rightblock;
        1191         [ #  # ]:          0 :             while (--n >= 0)
        1192                 :          0 :                 b = b->leftlink;
        1193                 :            :         }
        1194                 :            :     }
        1195                 :          0 :     item = b->data[i];
        1196                 :          0 :     return Py_NewRef(item);
        1197                 :            : }
        1198                 :            :
        1199                 :            : static int
        1200                 :          0 : deque_del_item(dequeobject *deque, Py_ssize_t i)
        1201                 :            : {
        1202                 :            :     PyObject *item;
        1203                 :            :     int rv;
        1204                 :            :
        1205                 :            :     assert (i >= 0 && i < Py_SIZE(deque));
        1206         [ #  # ]:          0 :     if (_deque_rotate(deque, -i))
        1207                 :          0 :         return -1;
        1208                 :          0 :     item = deque_popleft(deque, NULL);
        1209                 :          0 :     rv = _deque_rotate(deque, i);
        1210                 :            :     assert (item != NULL);
        1211                 :          0 :     Py_DECREF(item);
        1212                 :          0 :     return rv;
        1213                 :            : }
        1214                 :            :
        1215                 :            : static PyObject *
        1216                 :          0 : deque_remove(dequeobject *deque, PyObject *value)
        1217                 :            : {
        1218                 :            :     PyObject *item;
        1219                 :          0 :     block *b = deque->leftblock;
        1220                 :          0 :     Py_ssize_t i, n = Py_SIZE(deque), index = deque->leftindex;
        1221                 :          0 :     size_t start_state = deque->state;
        1222                 :            :     int cmp, rv;
        1223                 :            :
        1224         [ #  # ]:          0 :     for (i = 0 ; i < n; i++) {
        1225                 :          0 :         item = Py_NewRef(b->data[index]);
        1226                 :          0 :         cmp = PyObject_RichCompareBool(item, value, Py_EQ);
        1227                 :          0 :         Py_DECREF(item);
        1228         [ #  # ]:          0 :         if (cmp < 0) {
        1229                 :          0 :             return NULL;
        1230                 :            :         }
        1231         [ #  # ]:          0 :         if (start_state != deque->state) {
        1232                 :          0 :             PyErr_SetString(PyExc_IndexError,
        1233                 :            :                             "deque mutated during iteration");
        1234                 :          0 :             return NULL;
        1235                 :            :         }
        1236         [ #  # ]:          0 :         if (cmp > 0) {
        1237                 :          0 :             break;
        1238                 :            :         }
        1239                 :          0 :         index++;
        1240         [ #  # ]:          0 :         if (index == BLOCKLEN) {
        1241                 :          0 :             b = b->rightlink;
        1242                 :          0 :             index = 0;
        1243                 :            :         }
        1244                 :            :     }
        1245         [ #  # ]:          0 :     if (i == n) {
        1246                 :          0 :         PyErr_Format(PyExc_ValueError, "%R is not in deque", value);
        1247                 :          0 :         return NULL;
        1248                 :            :     }
        1249                 :          0 :     rv = deque_del_item(deque, i);
        1250         [ #  # ]:          0 :     if (rv == -1) {
        1251                 :          0 :         return NULL;
        1252                 :            :     }
        1253                 :          0 :     Py_RETURN_NONE;
        1254                 :            : }
        1255                 :            :
        1256                 :            : static int
        1257                 :          0 : deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
        1258                 :            : {
        1259                 :            :     block *b;
        1260                 :          0 :     Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i;
        1261                 :            :
        1262         [ #  # ]:          0 :     if (!valid_index(i, len)) {
        1263                 :          0 :         PyErr_SetString(PyExc_IndexError, "deque index out of range");
        1264                 :          0 :         return -1;
        1265                 :            :     }
        1266         [ #  # ]:          0 :     if (v == NULL)
        1267                 :          0 :         return deque_del_item(deque, i);
        1268                 :            :
        1269                 :          0 :     i += deque->leftindex;
        1270                 :          0 :     n = (Py_ssize_t)((size_t) i / BLOCKLEN);
        1271                 :          0 :     i = (Py_ssize_t)((size_t) i % BLOCKLEN);
        1272         [ #  # ]:          0 :     if (index <= halflen) {
        1273                 :          0 :         b = deque->leftblock;
        1274         [ #  # ]:          0 :         while (--n >= 0)
        1275                 :          0 :             b = b->rightlink;
        1276                 :            :     } else {
        1277                 :          0 :         n = (Py_ssize_t)(
        1278                 :          0 :                 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
        1279                 :          0 :                 / BLOCKLEN - n);
        1280                 :          0 :         b = deque->rightblock;
        1281         [ #  # ]:          0 :         while (--n >= 0)
        1282                 :          0 :             b = b->leftlink;
        1283                 :            :     }
        1284                 :          0 :     Py_SETREF(b->data[i], Py_NewRef(v));
        1285                 :          0 :     return 0;
        1286                 :            : }
        1287                 :            :
        1288                 :            : static void
        1289                 :          4 : deque_dealloc(dequeobject *deque)
        1290                 :            : {
        1291                 :            :     Py_ssize_t i;
        1292                 :            :
        1293                 :          4 :     PyObject_GC_UnTrack(deque);
        1294         [ -  + ]:          4 :     if (deque->weakreflist != NULL)
        1295                 :          0 :         PyObject_ClearWeakRefs((PyObject *) deque);
        1296         [ +  - ]:          4 :     if (deque->leftblock != NULL) {
        1297                 :          4 :         deque_clear(deque);
        1298                 :            :         assert(deque->leftblock != NULL);
        1299                 :          4 :         freeblock(deque, deque->leftblock);
        1300                 :            :     }
        1301                 :          4 :     deque->leftblock = NULL;
        1302                 :          4 :     deque->rightblock = NULL;
        1303         [ +  + ]:          8 :     for (i=0 ; i < deque->numfreeblocks ; i++) {
        1304                 :          4 :         PyMem_Free(deque->freeblocks[i]);
        1305                 :            :     }
        1306                 :          4 :     Py_TYPE(deque)->tp_free(deque);
        1307                 :          4 : }
        1308                 :            :
        1309                 :            : static int
        1310                 :         64 : deque_traverse(dequeobject *deque, visitproc visit, void *arg)
        1311                 :            : {
        1312                 :            :     block *b;
        1313                 :            :     PyObject *item;
        1314                 :            :     Py_ssize_t index;
        1315                 :         64 :     Py_ssize_t indexlo = deque->leftindex;
        1316                 :            :     Py_ssize_t indexhigh;
        1317                 :            :
        1318         [ -  + ]:         64 :     for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) {
        1319         [ #  # ]:          0 :         for (index = indexlo; index < BLOCKLEN ; index++) {
        1320                 :          0 :             item = b->data[index];
        1321   [ #  #  #  # ]:          0 :             Py_VISIT(item);
        1322                 :            :         }
        1323                 :          0 :         indexlo = 0;
        1324                 :            :     }
        1325                 :         64 :     indexhigh = deque->rightindex;
        1326         [ -  + ]:         64 :     for (index = indexlo; index <= indexhigh; index++) {
        1327                 :          0 :         item = b->data[index];
        1328   [ #  #  #  # ]:          0 :         Py_VISIT(item);
        1329                 :            :     }
        1330                 :         64 :     return 0;
        1331                 :            : }
        1332                 :            :
        1333                 :            : static PyObject *
        1334                 :          0 : deque_reduce(dequeobject *deque, PyObject *Py_UNUSED(ignored))
        1335                 :            : {
        1336                 :            :     PyObject *state, *it;
        1337                 :            :
        1338                 :          0 :     state = _PyObject_GetState((PyObject *)deque);
        1339         [ #  # ]:          0 :     if (state == NULL) {
        1340                 :          0 :         return NULL;
        1341                 :            :     }
        1342                 :            :
        1343                 :          0 :     it = PyObject_GetIter((PyObject *)deque);
        1344         [ #  # ]:          0 :     if (it == NULL) {
        1345                 :          0 :         Py_DECREF(state);
        1346                 :          0 :         return NULL;
        1347                 :            :     }
        1348                 :            :
        1349         [ #  # ]:          0 :     if (deque->maxlen < 0) {
        1350                 :          0 :         return Py_BuildValue("O()NN", Py_TYPE(deque), state, it);
        1351                 :            :     }
        1352                 :            :     else {
        1353                 :          0 :         return Py_BuildValue("O(()n)NN", Py_TYPE(deque), deque->maxlen, state, it);
        1354                 :            :     }
        1355                 :            : }
        1356                 :            :
        1357                 :            : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
        1358                 :            :
        1359                 :            : static PyObject *
        1360                 :          0 : deque_repr(PyObject *deque)
        1361                 :            : {
        1362                 :            :     PyObject *aslist, *result;
        1363                 :            :     int i;
        1364                 :            :
        1365                 :          0 :     i = Py_ReprEnter(deque);
        1366         [ #  # ]:          0 :     if (i != 0) {
        1367         [ #  # ]:          0 :         if (i < 0)
        1368                 :          0 :             return NULL;
        1369                 :          0 :         return PyUnicode_FromString("[...]");
        1370                 :            :     }
        1371                 :            :
        1372                 :          0 :     aslist = PySequence_List(deque);
        1373         [ #  # ]:          0 :     if (aslist == NULL) {
        1374                 :          0 :         Py_ReprLeave(deque);
        1375                 :          0 :         return NULL;
        1376                 :            :     }
        1377         [ #  # ]:          0 :     if (((dequeobject *)deque)->maxlen >= 0)
        1378                 :          0 :         result = PyUnicode_FromFormat("%s(%R, maxlen=%zd)",
        1379                 :            :                                       _PyType_Name(Py_TYPE(deque)), aslist,
        1380                 :            :                                       ((dequeobject *)deque)->maxlen);
        1381                 :            :     else
        1382                 :          0 :         result = PyUnicode_FromFormat("%s(%R)",
        1383                 :            :                                       _PyType_Name(Py_TYPE(deque)), aslist);
        1384                 :          0 :     Py_ReprLeave(deque);
        1385                 :          0 :     Py_DECREF(aslist);
        1386                 :          0 :     return result;
        1387                 :            : }
        1388                 :            :
        1389                 :            : static PyObject *
        1390                 :          0 : deque_richcompare(PyObject *v, PyObject *w, int op)
        1391                 :            : {
        1392                 :          0 :     PyObject *it1=NULL, *it2=NULL, *x, *y;
        1393                 :            :     Py_ssize_t vs, ws;
        1394                 :          0 :     int b, cmp=-1;
        1395                 :            :
        1396   [ #  #  #  # ]:          0 :     if (!PyObject_TypeCheck(v, &deque_type) ||
        1397                 :          0 :         !PyObject_TypeCheck(w, &deque_type)) {
        1398                 :          0 :         Py_RETURN_NOTIMPLEMENTED;
        1399                 :            :     }
        1400                 :            :
        1401                 :            :     /* Shortcuts */
        1402                 :          0 :     vs = Py_SIZE((dequeobject *)v);
        1403                 :          0 :     ws = Py_SIZE((dequeobject *)w);
        1404         [ #  # ]:          0 :     if (op == Py_EQ) {
        1405         [ #  # ]:          0 :         if (v == w)
        1406                 :          0 :             Py_RETURN_TRUE;
        1407         [ #  # ]:          0 :         if (vs != ws)
        1408                 :          0 :             Py_RETURN_FALSE;
        1409                 :            :     }
        1410         [ #  # ]:          0 :     if (op == Py_NE) {
        1411         [ #  # ]:          0 :         if (v == w)
        1412                 :          0 :             Py_RETURN_FALSE;
        1413         [ #  # ]:          0 :         if (vs != ws)
        1414                 :          0 :             Py_RETURN_TRUE;
        1415                 :            :     }
        1416                 :            :
        1417                 :            :     /* Search for the first index where items are different */
        1418                 :          0 :     it1 = PyObject_GetIter(v);
        1419         [ #  # ]:          0 :     if (it1 == NULL)
        1420                 :          0 :         goto done;
        1421                 :          0 :     it2 = PyObject_GetIter(w);
        1422         [ #  # ]:          0 :     if (it2 == NULL)
        1423                 :          0 :         goto done;
        1424                 :            :     for (;;) {
        1425                 :          0 :         x = PyIter_Next(it1);
        1426   [ #  #  #  # ]:          0 :         if (x == NULL && PyErr_Occurred())
        1427                 :          0 :             goto done;
        1428                 :          0 :         y = PyIter_Next(it2);
        1429   [ #  #  #  # ]:          0 :         if (x == NULL || y == NULL)
        1430                 :            :             break;
        1431                 :          0 :         b = PyObject_RichCompareBool(x, y, Py_EQ);
        1432         [ #  # ]:          0 :         if (b == 0) {
        1433                 :          0 :             cmp = PyObject_RichCompareBool(x, y, op);
        1434                 :          0 :             Py_DECREF(x);
        1435                 :          0 :             Py_DECREF(y);
        1436                 :          0 :             goto done;
        1437                 :            :         }
        1438                 :          0 :         Py_DECREF(x);
        1439                 :          0 :         Py_DECREF(y);
        1440         [ #  # ]:          0 :         if (b < 0)
        1441                 :          0 :             goto done;
        1442                 :            :     }
        1443                 :            :     /* We reached the end of one deque or both */
        1444                 :          0 :     Py_XDECREF(x);
        1445                 :          0 :     Py_XDECREF(y);
        1446         [ #  # ]:          0 :     if (PyErr_Occurred())
        1447                 :          0 :         goto done;
        1448   [ #  #  #  #  :          0 :     switch (op) {
                    #  #  # ]
        1449                 :          0 :     case Py_LT: cmp = y != NULL; break;  /* if w was longer */
        1450                 :          0 :     case Py_LE: cmp = x == NULL; break;  /* if v was not longer */
        1451                 :          0 :     case Py_EQ: cmp = x == y;    break;  /* if we reached the end of both */
        1452                 :          0 :     case Py_NE: cmp = x != y;    break;  /* if one deque continues */
        1453                 :          0 :     case Py_GT: cmp = x != NULL; break;  /* if v was longer */
        1454                 :          0 :     case Py_GE: cmp = y == NULL; break;  /* if w was not longer */
        1455                 :            :     }
        1456                 :            :
        1457                 :          0 : done:
        1458                 :          0 :     Py_XDECREF(it1);
        1459                 :          0 :     Py_XDECREF(it2);
        1460         [ #  # ]:          0 :     if (cmp == 1)
        1461                 :          0 :         Py_RETURN_TRUE;
        1462         [ #  # ]:          0 :     if (cmp == 0)
        1463                 :          0 :         Py_RETURN_FALSE;
        1464                 :          0 :     return NULL;
        1465                 :            : }
        1466                 :            :
        1467                 :            : static int
        1468                 :          4 : deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
        1469                 :            : {
        1470                 :          4 :     PyObject *iterable = NULL;
        1471                 :          4 :     PyObject *maxlenobj = NULL;
        1472                 :          4 :     Py_ssize_t maxlen = -1;
        1473                 :          4 :     char *kwlist[] = {"iterable", "maxlen", 0};
        1474                 :            :
        1475   [ +  -  +  - ]:          4 :     if (kwdargs == NULL && PyTuple_GET_SIZE(args) <= 2) {
        1476         [ -  + ]:          4 :         if (PyTuple_GET_SIZE(args) > 0) {
        1477                 :          0 :             iterable = PyTuple_GET_ITEM(args, 0);
        1478                 :            :         }
        1479         [ -  + ]:          4 :         if (PyTuple_GET_SIZE(args) > 1) {
        1480                 :          0 :             maxlenobj = PyTuple_GET_ITEM(args, 1);
        1481                 :            :         }
        1482                 :            :     } else {
        1483         [ #  # ]:          0 :         if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist,
        1484                 :            :                                          &iterable, &maxlenobj))
        1485                 :          0 :             return -1;
        1486                 :            :     }
        1487   [ -  +  -  - ]:          4 :     if (maxlenobj != NULL && maxlenobj != Py_None) {
        1488                 :          0 :         maxlen = PyLong_AsSsize_t(maxlenobj);
        1489   [ #  #  #  # ]:          0 :         if (maxlen == -1 && PyErr_Occurred())
        1490                 :          0 :             return -1;
        1491         [ #  # ]:          0 :         if (maxlen < 0) {
        1492                 :          0 :             PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
        1493                 :          0 :             return -1;
        1494                 :            :         }
        1495                 :            :     }
        1496                 :          4 :     deque->maxlen = maxlen;
        1497         [ -  + ]:          4 :     if (Py_SIZE(deque) > 0)
        1498                 :          0 :         deque_clear(deque);
        1499         [ -  + ]:          4 :     if (iterable != NULL) {
        1500                 :          0 :         PyObject *rv = deque_extend(deque, iterable);
        1501         [ #  # ]:          0 :         if (rv == NULL)
        1502                 :          0 :             return -1;
        1503                 :          0 :         Py_DECREF(rv);
        1504                 :            :     }
        1505                 :          4 :     return 0;
        1506                 :            : }
        1507                 :            :
        1508                 :            : static PyObject *
        1509                 :          0 : deque_sizeof(dequeobject *deque, void *unused)
        1510                 :            : {
        1511                 :          0 :     size_t res = _PyObject_SIZE(Py_TYPE(deque));
        1512                 :            :     size_t blocks;
        1513                 :          0 :     blocks = (size_t)(deque->leftindex + Py_SIZE(deque) + BLOCKLEN - 1) / BLOCKLEN;
        1514                 :            :     assert(((size_t)deque->leftindex + (size_t)Py_SIZE(deque) - 1) ==
        1515                 :            :            ((blocks - 1) * BLOCKLEN + (size_t)deque->rightindex));
        1516                 :          0 :     res += blocks * sizeof(block);
        1517                 :          0 :     return PyLong_FromSize_t(res);
        1518                 :            : }
        1519                 :            :
        1520                 :            : PyDoc_STRVAR(sizeof_doc,
        1521                 :            : "D.__sizeof__() -- size of D in memory, in bytes");
        1522                 :            :
        1523                 :            : static PyObject *
        1524                 :          0 : deque_get_maxlen(dequeobject *deque, void *Py_UNUSED(ignored))
        1525                 :            : {
        1526         [ #  # ]:          0 :     if (deque->maxlen < 0)
        1527                 :          0 :         Py_RETURN_NONE;
        1528                 :          0 :     return PyLong_FromSsize_t(deque->maxlen);
        1529                 :            : }
        1530                 :            :
        1531                 :            :
        1532                 :            : /* deque object ********************************************************/
        1533                 :            :
        1534                 :            : static PyGetSetDef deque_getset[] = {
        1535                 :            :     {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
        1536                 :            :      "maximum size of a deque or None if unbounded"},
        1537                 :            :     {0}
        1538                 :            : };
        1539                 :            :
        1540                 :            : static PySequenceMethods deque_as_sequence = {
        1541                 :            :     (lenfunc)deque_len,                 /* sq_length */
        1542                 :            :     (binaryfunc)deque_concat,           /* sq_concat */
        1543                 :            :     (ssizeargfunc)deque_repeat,         /* sq_repeat */
        1544                 :            :     (ssizeargfunc)deque_item,           /* sq_item */
        1545                 :            :     0,                                  /* sq_slice */
        1546                 :            :     (ssizeobjargproc)deque_ass_item,    /* sq_ass_item */
        1547                 :            :     0,                                  /* sq_ass_slice */
        1548                 :            :     (objobjproc)deque_contains,         /* sq_contains */
        1549                 :            :     (binaryfunc)deque_inplace_concat,   /* sq_inplace_concat */
        1550                 :            :     (ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */
        1551                 :            : };
        1552                 :            :
        1553                 :            : static PyObject *deque_iter(dequeobject *deque);
        1554                 :            : static PyObject *deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored));
        1555                 :            : PyDoc_STRVAR(reversed_doc,
        1556                 :            :     "D.__reversed__() -- return a reverse iterator over the deque");
        1557                 :            :
        1558                 :            : static PyMethodDef deque_methods[] = {
        1559                 :            :     {"append",                  (PyCFunction)deque_append,
        1560                 :            :         METH_O,                  append_doc},
        1561                 :            :     {"appendleft",              (PyCFunction)deque_appendleft,
        1562                 :            :         METH_O,                  appendleft_doc},
        1563                 :            :     {"clear",                   (PyCFunction)deque_clearmethod,
        1564                 :            :         METH_NOARGS,             clear_doc},
        1565                 :            :     {"__copy__",                deque_copy,
        1566                 :            :         METH_NOARGS,             copy_doc},
        1567                 :            :     {"copy",                    deque_copy,
        1568                 :            :         METH_NOARGS,             copy_doc},
        1569                 :            :     {"count",                   (PyCFunction)deque_count,
        1570                 :            :         METH_O,                  count_doc},
        1571                 :            :     {"extend",                  (PyCFunction)deque_extend,
        1572                 :            :         METH_O,                  extend_doc},
        1573                 :            :     {"extendleft",              (PyCFunction)deque_extendleft,
        1574                 :            :         METH_O,                  extendleft_doc},
        1575                 :            :     {"index",                   _PyCFunction_CAST(deque_index),
        1576                 :            :         METH_FASTCALL,            index_doc},
        1577                 :            :     {"insert",                  _PyCFunction_CAST(deque_insert),
        1578                 :            :         METH_FASTCALL,            insert_doc},
        1579                 :            :     {"pop",                     (PyCFunction)deque_pop,
        1580                 :            :         METH_NOARGS,             pop_doc},
        1581                 :            :     {"popleft",                 (PyCFunction)deque_popleft,
        1582                 :            :         METH_NOARGS,             popleft_doc},
        1583                 :            :     {"__reduce__",              (PyCFunction)deque_reduce,
        1584                 :            :         METH_NOARGS,             reduce_doc},
        1585                 :            :     {"remove",                  (PyCFunction)deque_remove,
        1586                 :            :         METH_O,                  remove_doc},
        1587                 :            :     {"__reversed__",            (PyCFunction)deque_reviter,
        1588                 :            :         METH_NOARGS,             reversed_doc},
        1589                 :            :     {"reverse",                 (PyCFunction)deque_reverse,
        1590                 :            :         METH_NOARGS,             reverse_doc},
        1591                 :            :     {"rotate",                  _PyCFunction_CAST(deque_rotate),
        1592                 :            :         METH_FASTCALL,            rotate_doc},
        1593                 :            :     {"__sizeof__",              (PyCFunction)deque_sizeof,
        1594                 :            :         METH_NOARGS,             sizeof_doc},
        1595                 :            :     {"__class_getitem__",       Py_GenericAlias,
        1596                 :            :         METH_O|METH_CLASS,       PyDoc_STR("See PEP 585")},
        1597                 :            :     {NULL,              NULL}   /* sentinel */
        1598                 :            : };
        1599                 :            :
        1600                 :            : PyDoc_STRVAR(deque_doc,
        1601                 :            : "deque([iterable[, maxlen]]) --> deque object\n\
        1602                 :            : \n\
        1603                 :            : A list-like sequence optimized for data accesses near its endpoints.");
        1604                 :            :
        1605                 :            : static PyTypeObject deque_type = {
        1606                 :            :     PyVarObject_HEAD_INIT(NULL, 0)
        1607                 :            :     "collections.deque",                /* tp_name */
        1608                 :            :     sizeof(dequeobject),                /* tp_basicsize */
        1609                 :            :     0,                                  /* tp_itemsize */
        1610                 :            :     /* methods */
        1611                 :            :     (destructor)deque_dealloc,          /* tp_dealloc */
        1612                 :            :     0,                                  /* tp_vectorcall_offset */
        1613                 :            :     0,                                  /* tp_getattr */
        1614                 :            :     0,                                  /* tp_setattr */
        1615                 :            :     0,                                  /* tp_as_async */
        1616                 :            :     deque_repr,                         /* tp_repr */
        1617                 :            :     0,                                  /* tp_as_number */
        1618                 :            :     &deque_as_sequence,                 /* tp_as_sequence */
        1619                 :            :     0,                                  /* tp_as_mapping */
        1620                 :            :     PyObject_HashNotImplemented,        /* tp_hash */
        1621                 :            :     0,                                  /* tp_call */
        1622                 :            :     0,                                  /* tp_str */
        1623                 :            :     PyObject_GenericGetAttr,            /* tp_getattro */
        1624                 :            :     0,                                  /* tp_setattro */
        1625                 :            :     0,                                  /* tp_as_buffer */
        1626                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
        1627                 :            :     Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_SEQUENCE,
        1628                 :            :                                         /* tp_flags */
        1629                 :            :     deque_doc,                          /* tp_doc */
        1630                 :            :     (traverseproc)deque_traverse,       /* tp_traverse */
        1631                 :            :     (inquiry)deque_clear,               /* tp_clear */
        1632                 :            :     (richcmpfunc)deque_richcompare,     /* tp_richcompare */
        1633                 :            :     offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
        1634                 :            :     (getiterfunc)deque_iter,            /* tp_iter */
        1635                 :            :     0,                                  /* tp_iternext */
        1636                 :            :     deque_methods,                      /* tp_methods */
        1637                 :            :     0,                                  /* tp_members */
        1638                 :            :     deque_getset,                       /* tp_getset */
        1639                 :            :     0,                                  /* tp_base */
        1640                 :            :     0,                                  /* tp_dict */
        1641                 :            :     0,                                  /* tp_descr_get */
        1642                 :            :     0,                                  /* tp_descr_set */
        1643                 :            :     0,                                  /* tp_dictoffset */
        1644                 :            :     (initproc)deque_init,               /* tp_init */
        1645                 :            :     PyType_GenericAlloc,                /* tp_alloc */
        1646                 :            :     deque_new,                          /* tp_new */
        1647                 :            :     PyObject_GC_Del,                    /* tp_free */
        1648                 :            : };
        1649                 :            :
        1650                 :            : /*********************** Deque Iterator **************************/
        1651                 :            :
        1652                 :            : typedef struct {
        1653                 :            :     PyObject_HEAD
        1654                 :            :     block *b;
        1655                 :            :     Py_ssize_t index;
        1656                 :            :     dequeobject *deque;
        1657                 :            :     size_t state;          /* state when the iterator is created */
        1658                 :            :     Py_ssize_t counter;    /* number of items remaining for iteration */
        1659                 :            : } dequeiterobject;
        1660                 :            :
        1661                 :            : static PyTypeObject dequeiter_type;
        1662                 :            :
        1663                 :            : static PyObject *
        1664                 :          0 : deque_iter(dequeobject *deque)
        1665                 :            : {
        1666                 :            :     dequeiterobject *it;
        1667                 :            :
        1668                 :          0 :     it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
        1669         [ #  # ]:          0 :     if (it == NULL)
        1670                 :          0 :         return NULL;
        1671                 :          0 :     it->b = deque->leftblock;
        1672                 :          0 :     it->index = deque->leftindex;
        1673                 :          0 :     it->deque = (dequeobject*)Py_NewRef(deque);
        1674                 :          0 :     it->state = deque->state;
        1675                 :          0 :     it->counter = Py_SIZE(deque);
        1676                 :          0 :     PyObject_GC_Track(it);
        1677                 :          0 :     return (PyObject *)it;
        1678                 :            : }
        1679                 :            :
        1680                 :            : static int
        1681                 :          0 : dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
        1682                 :            : {
        1683   [ #  #  #  # ]:          0 :     Py_VISIT(dio->deque);
        1684                 :          0 :     return 0;
        1685                 :            : }
        1686                 :            :
        1687                 :            : static void
        1688                 :          0 : dequeiter_dealloc(dequeiterobject *dio)
        1689                 :            : {
        1690                 :            :     /* bpo-31095: UnTrack is needed before calling any callbacks */
        1691                 :          0 :     PyObject_GC_UnTrack(dio);
        1692                 :          0 :     Py_XDECREF(dio->deque);
        1693                 :          0 :     PyObject_GC_Del(dio);
        1694                 :          0 : }
        1695                 :            :
        1696                 :            : static PyObject *
        1697                 :          0 : dequeiter_next(dequeiterobject *it)
        1698                 :            : {
        1699                 :            :     PyObject *item;
        1700                 :            :
        1701         [ #  # ]:          0 :     if (it->deque->state != it->state) {
        1702                 :          0 :         it->counter = 0;
        1703                 :          0 :         PyErr_SetString(PyExc_RuntimeError,
        1704                 :            :                         "deque mutated during iteration");
        1705                 :          0 :         return NULL;
        1706                 :            :     }
        1707         [ #  # ]:          0 :     if (it->counter == 0)
        1708                 :          0 :         return NULL;
        1709                 :            :     assert (!(it->b == it->deque->rightblock &&
        1710                 :            :               it->index > it->deque->rightindex));
        1711                 :            :
        1712                 :          0 :     item = it->b->data[it->index];
        1713                 :          0 :     it->index++;
        1714                 :          0 :     it->counter--;
        1715   [ #  #  #  # ]:          0 :     if (it->index == BLOCKLEN && it->counter > 0) {
        1716                 :            :         CHECK_NOT_END(it->b->rightlink);
        1717                 :          0 :         it->b = it->b->rightlink;
        1718                 :          0 :         it->index = 0;
        1719                 :            :     }
        1720                 :          0 :     return Py_NewRef(item);
        1721                 :            : }
        1722                 :            :
        1723                 :            : static PyObject *
        1724                 :          0 : dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
        1725                 :            : {
        1726                 :          0 :     Py_ssize_t i, index=0;
        1727                 :            :     PyObject *deque;
        1728                 :            :     dequeiterobject *it;
        1729         [ #  # ]:          0 :     if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
        1730                 :          0 :         return NULL;
        1731                 :            :     assert(type == &dequeiter_type);
        1732                 :            :
        1733                 :          0 :     it = (dequeiterobject*)deque_iter((dequeobject *)deque);
        1734         [ #  # ]:          0 :     if (!it)
        1735                 :          0 :         return NULL;
        1736                 :            :     /* consume items from the queue */
        1737         [ #  # ]:          0 :     for(i=0; i<index; i++) {
        1738                 :          0 :         PyObject *item = dequeiter_next(it);
        1739         [ #  # ]:          0 :         if (item) {
        1740                 :          0 :             Py_DECREF(item);
        1741                 :            :         } else {
        1742         [ #  # ]:          0 :             if (it->counter) {
        1743                 :          0 :                 Py_DECREF(it);
        1744                 :          0 :                 return NULL;
        1745                 :            :             } else
        1746                 :          0 :                 break;
        1747                 :            :         }
        1748                 :            :     }
        1749                 :          0 :     return (PyObject*)it;
        1750                 :            : }
        1751                 :            :
        1752                 :            : static PyObject *
        1753                 :          0 : dequeiter_len(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
        1754                 :            : {
        1755                 :          0 :     return PyLong_FromSsize_t(it->counter);
        1756                 :            : }
        1757                 :            :
        1758                 :            : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
        1759                 :            :
        1760                 :            : static PyObject *
        1761                 :          0 : dequeiter_reduce(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
        1762                 :            : {
        1763                 :          0 :     return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter);
        1764                 :            : }
        1765                 :            :
        1766                 :            : static PyMethodDef dequeiter_methods[] = {
        1767                 :            :     {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
        1768                 :            :     {"__reduce__", (PyCFunction)dequeiter_reduce, METH_NOARGS, reduce_doc},
        1769                 :            :     {NULL,              NULL}           /* sentinel */
        1770                 :            : };
        1771                 :            :
        1772                 :            : static PyTypeObject dequeiter_type = {
        1773                 :            :     PyVarObject_HEAD_INIT(NULL, 0)
        1774                 :            :     "_collections._deque_iterator",             /* tp_name */
        1775                 :            :     sizeof(dequeiterobject),                    /* tp_basicsize */
        1776                 :            :     0,                                          /* tp_itemsize */
        1777                 :            :     /* methods */
        1778                 :            :     (destructor)dequeiter_dealloc,              /* tp_dealloc */
        1779                 :            :     0,                                          /* tp_vectorcall_offset */
        1780                 :            :     0,                                          /* tp_getattr */
        1781                 :            :     0,                                          /* tp_setattr */
        1782                 :            :     0,                                          /* tp_as_async */
        1783                 :            :     0,                                          /* tp_repr */
        1784                 :            :     0,                                          /* tp_as_number */
        1785                 :            :     0,                                          /* tp_as_sequence */
        1786                 :            :     0,                                          /* tp_as_mapping */
        1787                 :            :     0,                                          /* tp_hash */
        1788                 :            :     0,                                          /* tp_call */
        1789                 :            :     0,                                          /* tp_str */
        1790                 :            :     PyObject_GenericGetAttr,                    /* tp_getattro */
        1791                 :            :     0,                                          /* tp_setattro */
        1792                 :            :     0,                                          /* tp_as_buffer */
        1793                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,    /* tp_flags */
        1794                 :            :     0,                                          /* tp_doc */
        1795                 :            :     (traverseproc)dequeiter_traverse,           /* tp_traverse */
        1796                 :            :     0,                                          /* tp_clear */
        1797                 :            :     0,                                          /* tp_richcompare */
        1798                 :            :     0,                                          /* tp_weaklistoffset */
        1799                 :            :     PyObject_SelfIter,                          /* tp_iter */
        1800                 :            :     (iternextfunc)dequeiter_next,               /* tp_iternext */
        1801                 :            :     dequeiter_methods,                          /* tp_methods */
        1802                 :            :     0,                                          /* tp_members */
        1803                 :            :     0,                                          /* tp_getset */
        1804                 :            :     0,                                          /* tp_base */
        1805                 :            :     0,                                          /* tp_dict */
        1806                 :            :     0,                                          /* tp_descr_get */
        1807                 :            :     0,                                          /* tp_descr_set */
        1808                 :            :     0,                                          /* tp_dictoffset */
        1809                 :            :     0,                                          /* tp_init */
        1810                 :            :     0,                                          /* tp_alloc */
        1811                 :            :     dequeiter_new,                              /* tp_new */
        1812                 :            :     0,
        1813                 :            : };
        1814                 :            :
        1815                 :            : /*********************** Deque Reverse Iterator **************************/
        1816                 :            :
        1817                 :            : static PyTypeObject dequereviter_type;
        1818                 :            :
        1819                 :            : static PyObject *
        1820                 :          0 : deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored))
        1821                 :            : {
        1822                 :            :     dequeiterobject *it;
        1823                 :            :
        1824                 :          0 :     it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
        1825         [ #  # ]:          0 :     if (it == NULL)
        1826                 :          0 :         return NULL;
        1827                 :          0 :     it->b = deque->rightblock;
        1828                 :          0 :     it->index = deque->rightindex;
        1829                 :          0 :     it->deque = (dequeobject*)Py_NewRef(deque);
        1830                 :          0 :     it->state = deque->state;
        1831                 :          0 :     it->counter = Py_SIZE(deque);
        1832                 :          0 :     PyObject_GC_Track(it);
        1833                 :          0 :     return (PyObject *)it;
        1834                 :            : }
        1835                 :            :
        1836                 :            : static PyObject *
        1837                 :          0 : dequereviter_next(dequeiterobject *it)
        1838                 :            : {
        1839                 :            :     PyObject *item;
        1840         [ #  # ]:          0 :     if (it->counter == 0)
        1841                 :          0 :         return NULL;
        1842                 :            :
        1843         [ #  # ]:          0 :     if (it->deque->state != it->state) {
        1844                 :          0 :         it->counter = 0;
        1845                 :          0 :         PyErr_SetString(PyExc_RuntimeError,
        1846                 :            :                         "deque mutated during iteration");
        1847                 :          0 :         return NULL;
        1848                 :            :     }
        1849                 :            :     assert (!(it->b == it->deque->leftblock &&
        1850                 :            :               it->index < it->deque->leftindex));
        1851                 :            :
        1852                 :          0 :     item = it->b->data[it->index];
        1853                 :          0 :     it->index--;
        1854                 :          0 :     it->counter--;
        1855   [ #  #  #  # ]:          0 :     if (it->index < 0 && it->counter > 0) {
        1856                 :            :         CHECK_NOT_END(it->b->leftlink);
        1857                 :          0 :         it->b = it->b->leftlink;
        1858                 :          0 :         it->index = BLOCKLEN - 1;
        1859                 :            :     }
        1860                 :          0 :     return Py_NewRef(item);
        1861                 :            : }
        1862                 :            :
        1863                 :            : static PyObject *
        1864                 :          0 : dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
        1865                 :            : {
        1866                 :          0 :     Py_ssize_t i, index=0;
        1867                 :            :     PyObject *deque;
        1868                 :            :     dequeiterobject *it;
        1869         [ #  # ]:          0 :     if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
        1870                 :          0 :         return NULL;
        1871                 :            :     assert(type == &dequereviter_type);
        1872                 :            :
        1873                 :          0 :     it = (dequeiterobject*)deque_reviter((dequeobject *)deque, NULL);
        1874         [ #  # ]:          0 :     if (!it)
        1875                 :          0 :         return NULL;
        1876                 :            :     /* consume items from the queue */
        1877         [ #  # ]:          0 :     for(i=0; i<index; i++) {
        1878                 :          0 :         PyObject *item = dequereviter_next(it);
        1879         [ #  # ]:          0 :         if (item) {
        1880                 :          0 :             Py_DECREF(item);
        1881                 :            :         } else {
        1882         [ #  # ]:          0 :             if (it->counter) {
        1883                 :          0 :                 Py_DECREF(it);
        1884                 :          0 :                 return NULL;
        1885                 :            :             } else
        1886                 :          0 :                 break;
        1887                 :            :         }
        1888                 :            :     }
        1889                 :          0 :     return (PyObject*)it;
        1890                 :            : }
        1891                 :            :
        1892                 :            : static PyTypeObject dequereviter_type = {
        1893                 :            :     PyVarObject_HEAD_INIT(NULL, 0)
        1894                 :            :     "_collections._deque_reverse_iterator",     /* tp_name */
        1895                 :            :     sizeof(dequeiterobject),                    /* tp_basicsize */
        1896                 :            :     0,                                          /* tp_itemsize */
        1897                 :            :     /* methods */
        1898                 :            :     (destructor)dequeiter_dealloc,              /* tp_dealloc */
        1899                 :            :     0,                                          /* tp_vectorcall_offset */
        1900                 :            :     0,                                          /* tp_getattr */
        1901                 :            :     0,                                          /* tp_setattr */
        1902                 :            :     0,                                          /* tp_as_async */
        1903                 :            :     0,                                          /* tp_repr */
        1904                 :            :     0,                                          /* tp_as_number */
        1905                 :            :     0,                                          /* tp_as_sequence */
        1906                 :            :     0,                                          /* tp_as_mapping */
        1907                 :            :     0,                                          /* tp_hash */
        1908                 :            :     0,                                          /* tp_call */
        1909                 :            :     0,                                          /* tp_str */
        1910                 :            :     PyObject_GenericGetAttr,                    /* tp_getattro */
        1911                 :            :     0,                                          /* tp_setattro */
        1912                 :            :     0,                                          /* tp_as_buffer */
        1913                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,    /* tp_flags */
        1914                 :            :     0,                                          /* tp_doc */
        1915                 :            :     (traverseproc)dequeiter_traverse,           /* tp_traverse */
        1916                 :            :     0,                                          /* tp_clear */
        1917                 :            :     0,                                          /* tp_richcompare */
        1918                 :            :     0,                                          /* tp_weaklistoffset */
        1919                 :            :     PyObject_SelfIter,                          /* tp_iter */
        1920                 :            :     (iternextfunc)dequereviter_next,            /* tp_iternext */
        1921                 :            :     dequeiter_methods,                          /* tp_methods */
        1922                 :            :     0,                                          /* tp_members */
        1923                 :            :     0,                                          /* tp_getset */
        1924                 :            :     0,                                          /* tp_base */
        1925                 :            :     0,                                          /* tp_dict */
        1926                 :            :     0,                                          /* tp_descr_get */
        1927                 :            :     0,                                          /* tp_descr_set */
        1928                 :            :     0,                                          /* tp_dictoffset */
        1929                 :            :     0,                                          /* tp_init */
        1930                 :            :     0,                                          /* tp_alloc */
        1931                 :            :     dequereviter_new,                           /* tp_new */
        1932                 :            :     0,
        1933                 :            : };
        1934                 :            :
        1935                 :            : /* defaultdict type *********************************************************/
        1936                 :            :
        1937                 :            : typedef struct {
        1938                 :            :     PyDictObject dict;
        1939                 :            :     PyObject *default_factory;
        1940                 :            : } defdictobject;
        1941                 :            :
        1942                 :            : static PyTypeObject defdict_type; /* Forward */
        1943                 :            :
        1944                 :            : PyDoc_STRVAR(defdict_missing_doc,
        1945                 :            : "__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
        1946                 :            :   if self.default_factory is None: raise KeyError((key,))\n\
        1947                 :            :   self[key] = value = self.default_factory()\n\
        1948                 :            :   return value\n\
        1949                 :            : ");
        1950                 :            :
        1951                 :            : static PyObject *
        1952                 :       2233 : defdict_missing(defdictobject *dd, PyObject *key)
        1953                 :            : {
        1954                 :       2233 :     PyObject *factory = dd->default_factory;
        1955                 :            :     PyObject *value;
        1956   [ +  -  -  + ]:       2233 :     if (factory == NULL || factory == Py_None) {
        1957                 :            :         /* XXX Call dict.__missing__(key) */
        1958                 :            :         PyObject *tup;
        1959                 :          0 :         tup = PyTuple_Pack(1, key);
        1960         [ #  # ]:          0 :         if (!tup) return NULL;
        1961                 :          0 :         PyErr_SetObject(PyExc_KeyError, tup);
        1962                 :          0 :         Py_DECREF(tup);
        1963                 :          0 :         return NULL;
        1964                 :            :     }
        1965                 :       2233 :     value = _PyObject_CallNoArgs(factory);
        1966         [ -  + ]:       2233 :     if (value == NULL)
        1967                 :          0 :         return value;
        1968         [ -  + ]:       2233 :     if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
        1969                 :          0 :         Py_DECREF(value);
        1970                 :          0 :         return NULL;
        1971                 :            :     }
        1972                 :       2233 :     return value;
        1973                 :            : }
        1974                 :            :
        1975                 :            : static inline PyObject*
        1976                 :          0 : new_defdict(defdictobject *dd, PyObject *arg)
        1977                 :            : {
        1978                 :          0 :     return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
        1979         [ #  # ]:          0 :         dd->default_factory ? dd->default_factory : Py_None, arg, NULL);
        1980                 :            : }
        1981                 :            :
        1982                 :            : PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
        1983                 :            :
        1984                 :            : static PyObject *
        1985                 :          0 : defdict_copy(defdictobject *dd, PyObject *Py_UNUSED(ignored))
        1986                 :            : {
        1987                 :            :     /* This calls the object's class.  That only works for subclasses
        1988                 :            :        whose class constructor has the same signature.  Subclasses that
        1989                 :            :        define a different constructor signature must override copy().
        1990                 :            :     */
        1991                 :          0 :     return new_defdict(dd, (PyObject*)dd);
        1992                 :            : }
        1993                 :            :
        1994                 :            : static PyObject *
        1995                 :          0 : defdict_reduce(defdictobject *dd, PyObject *Py_UNUSED(ignored))
        1996                 :            : {
        1997                 :            :     /* __reduce__ must return a 5-tuple as follows:
        1998                 :            :
        1999                 :            :        - factory function
        2000                 :            :        - tuple of args for the factory function
        2001                 :            :        - additional state (here None)
        2002                 :            :        - sequence iterator (here None)
        2003                 :            :        - dictionary iterator (yielding successive (key, value) pairs
        2004                 :            :
        2005                 :            :        This API is used by pickle.py and copy.py.
        2006                 :            :
        2007                 :            :        For this to be useful with pickle.py, the default_factory
        2008                 :            :        must be picklable; e.g., None, a built-in, or a global
        2009                 :            :        function in a module or package.
        2010                 :            :
        2011                 :            :        Both shallow and deep copying are supported, but for deep
        2012                 :            :        copying, the default_factory must be deep-copyable; e.g. None,
        2013                 :            :        or a built-in (functions are not copyable at this time).
        2014                 :            :
        2015                 :            :        This only works for subclasses as long as their constructor
        2016                 :            :        signature is compatible; the first argument must be the
        2017                 :            :        optional default_factory, defaulting to None.
        2018                 :            :     */
        2019                 :            :     PyObject *args;
        2020                 :            :     PyObject *items;
        2021                 :            :     PyObject *iter;
        2022                 :            :     PyObject *result;
        2023                 :            :
        2024   [ #  #  #  # ]:          0 :     if (dd->default_factory == NULL || dd->default_factory == Py_None)
        2025                 :          0 :         args = PyTuple_New(0);
        2026                 :            :     else
        2027                 :          0 :         args = PyTuple_Pack(1, dd->default_factory);
        2028         [ #  # ]:          0 :     if (args == NULL)
        2029                 :          0 :         return NULL;
        2030                 :          0 :     items = PyObject_CallMethodNoArgs((PyObject *)dd, &_Py_ID(items));
        2031         [ #  # ]:          0 :     if (items == NULL) {
        2032                 :          0 :         Py_DECREF(args);
        2033                 :          0 :         return NULL;
        2034                 :            :     }
        2035                 :          0 :     iter = PyObject_GetIter(items);
        2036         [ #  # ]:          0 :     if (iter == NULL) {
        2037                 :          0 :         Py_DECREF(items);
        2038                 :          0 :         Py_DECREF(args);
        2039                 :          0 :         return NULL;
        2040                 :            :     }
        2041                 :          0 :     result = PyTuple_Pack(5, Py_TYPE(dd), args,
        2042                 :            :                           Py_None, Py_None, iter);
        2043                 :          0 :     Py_DECREF(iter);
        2044                 :          0 :     Py_DECREF(items);
        2045                 :          0 :     Py_DECREF(args);
        2046                 :          0 :     return result;
        2047                 :            : }
        2048                 :            :
        2049                 :            : static PyMethodDef defdict_methods[] = {
        2050                 :            :     {"__missing__", (PyCFunction)defdict_missing, METH_O,
        2051                 :            :      defdict_missing_doc},
        2052                 :            :     {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
        2053                 :            :      defdict_copy_doc},
        2054                 :            :     {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
        2055                 :            :      defdict_copy_doc},
        2056                 :            :     {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
        2057                 :            :      reduce_doc},
        2058                 :            :     {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS,
        2059                 :            :      PyDoc_STR("See PEP 585")},
        2060                 :            :     {NULL}
        2061                 :            : };
        2062                 :            :
        2063                 :            : static PyMemberDef defdict_members[] = {
        2064                 :            :     {"default_factory", T_OBJECT,
        2065                 :            :      offsetof(defdictobject, default_factory), 0,
        2066                 :            :      PyDoc_STR("Factory for default value called by __missing__().")},
        2067                 :            :     {NULL}
        2068                 :            : };
        2069                 :            :
        2070                 :            : static void
        2071                 :        775 : defdict_dealloc(defdictobject *dd)
        2072                 :            : {
        2073                 :            :     /* bpo-31095: UnTrack is needed before calling any callbacks */
        2074                 :        775 :     PyObject_GC_UnTrack(dd);
        2075         [ +  - ]:        775 :     Py_CLEAR(dd->default_factory);
        2076                 :        775 :     PyDict_Type.tp_dealloc((PyObject *)dd);
        2077                 :        775 : }
        2078                 :            :
        2079                 :            : static PyObject *
        2080                 :          0 : defdict_repr(defdictobject *dd)
        2081                 :            : {
        2082                 :            :     PyObject *baserepr;
        2083                 :            :     PyObject *defrepr;
        2084                 :            :     PyObject *result;
        2085                 :          0 :     baserepr = PyDict_Type.tp_repr((PyObject *)dd);
        2086         [ #  # ]:          0 :     if (baserepr == NULL)
        2087                 :          0 :         return NULL;
        2088         [ #  # ]:          0 :     if (dd->default_factory == NULL)
        2089                 :          0 :         defrepr = PyUnicode_FromString("None");
        2090                 :            :     else
        2091                 :            :     {
        2092                 :          0 :         int status = Py_ReprEnter(dd->default_factory);
        2093         [ #  # ]:          0 :         if (status != 0) {
        2094         [ #  # ]:          0 :             if (status < 0) {
        2095                 :          0 :                 Py_DECREF(baserepr);
        2096                 :          0 :                 return NULL;
        2097                 :            :             }
        2098                 :          0 :             defrepr = PyUnicode_FromString("...");
        2099                 :            :         }
        2100                 :            :         else
        2101                 :          0 :             defrepr = PyObject_Repr(dd->default_factory);
        2102                 :          0 :         Py_ReprLeave(dd->default_factory);
        2103                 :            :     }
        2104         [ #  # ]:          0 :     if (defrepr == NULL) {
        2105                 :          0 :         Py_DECREF(baserepr);
        2106                 :          0 :         return NULL;
        2107                 :            :     }
        2108                 :          0 :     result = PyUnicode_FromFormat("%s(%U, %U)",
        2109                 :            :                                   _PyType_Name(Py_TYPE(dd)),
        2110                 :            :                                   defrepr, baserepr);
        2111                 :          0 :     Py_DECREF(defrepr);
        2112                 :          0 :     Py_DECREF(baserepr);
        2113                 :          0 :     return result;
        2114                 :            : }
        2115                 :            :
        2116                 :            : static PyObject*
        2117                 :          0 : defdict_or(PyObject* left, PyObject* right)
        2118                 :            : {
        2119                 :            :     PyObject *self, *other;
        2120         [ #  # ]:          0 :     if (PyObject_TypeCheck(left, &defdict_type)) {
        2121                 :          0 :         self = left;
        2122                 :          0 :         other = right;
        2123                 :            :     }
        2124                 :            :     else {
        2125                 :          0 :         self = right;
        2126                 :          0 :         other = left;
        2127                 :            :     }
        2128         [ #  # ]:          0 :     if (!PyDict_Check(other)) {
        2129                 :          0 :         Py_RETURN_NOTIMPLEMENTED;
        2130                 :            :     }
        2131                 :            :     // Like copy(), this calls the object's class.
        2132                 :            :     // Override __or__/__ror__ for subclasses with different constructors.
        2133                 :          0 :     PyObject *new = new_defdict((defdictobject*)self, left);
        2134         [ #  # ]:          0 :     if (!new) {
        2135                 :          0 :         return NULL;
        2136                 :            :     }
        2137         [ #  # ]:          0 :     if (PyDict_Update(new, right)) {
        2138                 :          0 :         Py_DECREF(new);
        2139                 :          0 :         return NULL;
        2140                 :            :     }
        2141                 :          0 :     return new;
        2142                 :            : }
        2143                 :            :
        2144                 :            : static PyNumberMethods defdict_as_number = {
        2145                 :            :     .nb_or = defdict_or,
        2146                 :            : };
        2147                 :            :
        2148                 :            : static int
        2149                 :         40 : defdict_traverse(PyObject *self, visitproc visit, void *arg)
        2150                 :            : {
        2151   [ +  -  -  + ]:         40 :     Py_VISIT(((defdictobject *)self)->default_factory);
        2152                 :         40 :     return PyDict_Type.tp_traverse(self, visit, arg);
        2153                 :            : }
        2154                 :            :
        2155                 :            : static int
        2156                 :          0 : defdict_tp_clear(defdictobject *dd)
        2157                 :            : {
        2158         [ #  # ]:          0 :     Py_CLEAR(dd->default_factory);
        2159                 :          0 :     return PyDict_Type.tp_clear((PyObject *)dd);
        2160                 :            : }
        2161                 :            :
        2162                 :            : static int
        2163                 :        775 : defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
        2164                 :            : {
        2165                 :        775 :     defdictobject *dd = (defdictobject *)self;
        2166                 :        775 :     PyObject *olddefault = dd->default_factory;
        2167                 :        775 :     PyObject *newdefault = NULL;
        2168                 :            :     PyObject *newargs;
        2169                 :            :     int result;
        2170   [ +  -  -  + ]:        775 :     if (args == NULL || !PyTuple_Check(args))
        2171                 :          0 :         newargs = PyTuple_New(0);
        2172                 :            :     else {
        2173                 :        775 :         Py_ssize_t n = PyTuple_GET_SIZE(args);
        2174         [ +  - ]:        775 :         if (n > 0) {
        2175                 :        775 :             newdefault = PyTuple_GET_ITEM(args, 0);
        2176   [ -  +  -  - ]:        775 :             if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
        2177                 :          0 :                 PyErr_SetString(PyExc_TypeError,
        2178                 :            :                     "first argument must be callable or None");
        2179                 :          0 :                 return -1;
        2180                 :            :             }
        2181                 :            :         }
        2182                 :        775 :         newargs = PySequence_GetSlice(args, 1, n);
        2183                 :            :     }
        2184         [ -  + ]:        775 :     if (newargs == NULL)
        2185                 :          0 :         return -1;
        2186                 :        775 :     dd->default_factory = Py_XNewRef(newdefault);
        2187                 :        775 :     result = PyDict_Type.tp_init(self, newargs, kwds);
        2188                 :        775 :     Py_DECREF(newargs);
        2189                 :        775 :     Py_XDECREF(olddefault);
        2190                 :        775 :     return result;
        2191                 :            : }
        2192                 :            :
        2193                 :            : PyDoc_STRVAR(defdict_doc,
        2194                 :            : "defaultdict(default_factory=None, /, [...]) --> dict with default factory\n\
        2195                 :            : \n\
        2196                 :            : The default factory is called without arguments to produce\n\
        2197                 :            : a new value when a key is not present, in __getitem__ only.\n\
        2198                 :            : A defaultdict compares equal to a dict with the same items.\n\
        2199                 :            : All remaining arguments are treated the same as if they were\n\
        2200                 :            : passed to the dict constructor, including keyword arguments.\n\
        2201                 :            : ");
        2202                 :            :
        2203                 :            : /* See comment in xxsubtype.c */
        2204                 :            : #define DEFERRED_ADDRESS(ADDR) 0
        2205                 :            :
        2206                 :            : static PyTypeObject defdict_type = {
        2207                 :            :     PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
        2208                 :            :     "collections.defaultdict",          /* tp_name */
        2209                 :            :     sizeof(defdictobject),              /* tp_basicsize */
        2210                 :            :     0,                                  /* tp_itemsize */
        2211                 :            :     /* methods */
        2212                 :            :     (destructor)defdict_dealloc,        /* tp_dealloc */
        2213                 :            :     0,                                  /* tp_vectorcall_offset */
        2214                 :            :     0,                                  /* tp_getattr */
        2215                 :            :     0,                                  /* tp_setattr */
        2216                 :            :     0,                                  /* tp_as_async */
        2217                 :            :     (reprfunc)defdict_repr,             /* tp_repr */
        2218                 :            :     &defdict_as_number,                 /* tp_as_number */
        2219                 :            :     0,                                  /* tp_as_sequence */
        2220                 :            :     0,                                  /* tp_as_mapping */
        2221                 :            :     0,                                  /* tp_hash */
        2222                 :            :     0,                                  /* tp_call */
        2223                 :            :     0,                                  /* tp_str */
        2224                 :            :     PyObject_GenericGetAttr,            /* tp_getattro */
        2225                 :            :     0,                                  /* tp_setattro */
        2226                 :            :     0,                                  /* tp_as_buffer */
        2227                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
        2228                 :            :                                     /* tp_flags */
        2229                 :            :     defdict_doc,                        /* tp_doc */
        2230                 :            :     defdict_traverse,                   /* tp_traverse */
        2231                 :            :     (inquiry)defdict_tp_clear,          /* tp_clear */
        2232                 :            :     0,                                  /* tp_richcompare */
        2233                 :            :     0,                                  /* tp_weaklistoffset*/
        2234                 :            :     0,                                  /* tp_iter */
        2235                 :            :     0,                                  /* tp_iternext */
        2236                 :            :     defdict_methods,                    /* tp_methods */
        2237                 :            :     defdict_members,                    /* tp_members */
        2238                 :            :     0,                                  /* tp_getset */
        2239                 :            :     DEFERRED_ADDRESS(&PyDict_Type),     /* tp_base */
        2240                 :            :     0,                                  /* tp_dict */
        2241                 :            :     0,                                  /* tp_descr_get */
        2242                 :            :     0,                                  /* tp_descr_set */
        2243                 :            :     0,                                  /* tp_dictoffset */
        2244                 :            :     defdict_init,                       /* tp_init */
        2245                 :            :     PyType_GenericAlloc,                /* tp_alloc */
        2246                 :            :     0,                                  /* tp_new */
        2247                 :            :     PyObject_GC_Del,                    /* tp_free */
        2248                 :            : };
        2249                 :            :
        2250                 :            : /* helper function for Counter  *********************************************/
        2251                 :            :
        2252                 :            : /*[clinic input]
        2253                 :            : _collections._count_elements
        2254                 :            :
        2255                 :            :     mapping: object
        2256                 :            :     iterable: object
        2257                 :            :     /
        2258                 :            :
        2259                 :            : Count elements in the iterable, updating the mapping
        2260                 :            : [clinic start generated code]*/
        2261                 :            :
        2262                 :            : static PyObject *
        2263                 :          0 : _collections__count_elements_impl(PyObject *module, PyObject *mapping,
        2264                 :            :                                   PyObject *iterable)
        2265                 :            : /*[clinic end generated code: output=7e0c1789636b3d8f input=e79fad04534a0b45]*/
        2266                 :            : {
        2267                 :            :     PyObject *it, *oldval;
        2268                 :          0 :     PyObject *newval = NULL;
        2269                 :          0 :     PyObject *key = NULL;
        2270                 :          0 :     PyObject *bound_get = NULL;
        2271                 :            :     PyObject *mapping_get;
        2272                 :            :     PyObject *dict_get;
        2273                 :            :     PyObject *mapping_setitem;
        2274                 :            :     PyObject *dict_setitem;
        2275                 :          0 :     PyObject *one = _PyLong_GetOne();  // borrowed reference
        2276                 :            :
        2277                 :          0 :     it = PyObject_GetIter(iterable);
        2278         [ #  # ]:          0 :     if (it == NULL)
        2279                 :          0 :         return NULL;
        2280                 :            :
        2281                 :            :     /* Only take the fast path when get() and __setitem__()
        2282                 :            :      * have not been overridden.
        2283                 :            :      */
        2284                 :          0 :     mapping_get = _PyType_Lookup(Py_TYPE(mapping), &_Py_ID(get));
        2285                 :          0 :     dict_get = _PyType_Lookup(&PyDict_Type, &_Py_ID(get));
        2286                 :          0 :     mapping_setitem = _PyType_Lookup(Py_TYPE(mapping), &_Py_ID(__setitem__));
        2287                 :          0 :     dict_setitem = _PyType_Lookup(&PyDict_Type, &_Py_ID(__setitem__));
        2288                 :            :
        2289   [ #  #  #  #  :          0 :     if (mapping_get != NULL && mapping_get == dict_get &&
                       #  # ]
        2290   [ #  #  #  # ]:          0 :         mapping_setitem != NULL && mapping_setitem == dict_setitem &&
        2291                 :          0 :         PyDict_Check(mapping))
        2292                 :            :     {
        2293                 :          0 :         while (1) {
        2294                 :            :             /* Fast path advantages:
        2295                 :            :                    1. Eliminate double hashing
        2296                 :            :                       (by re-using the same hash for both the get and set)
        2297                 :            :                    2. Avoid argument overhead of PyObject_CallFunctionObjArgs
        2298                 :            :                       (argument tuple creation and parsing)
        2299                 :            :                    3. Avoid indirection through a bound method object
        2300                 :            :                       (creates another argument tuple)
        2301                 :            :                    4. Avoid initial increment from zero
        2302                 :            :                       (reuse an existing one-object instead)
        2303                 :            :             */
        2304                 :            :             Py_hash_t hash;
        2305                 :            :
        2306                 :          0 :             key = PyIter_Next(it);
        2307         [ #  # ]:          0 :             if (key == NULL)
        2308                 :          0 :                 break;
        2309                 :            :
        2310         [ #  # ]:          0 :             if (!PyUnicode_CheckExact(key) ||
        2311         [ #  # ]:          0 :                 (hash = _PyASCIIObject_CAST(key)->hash) == -1)
        2312                 :            :             {
        2313                 :          0 :                 hash = PyObject_Hash(key);
        2314         [ #  # ]:          0 :                 if (hash == -1)
        2315                 :          0 :                     goto done;
        2316                 :            :             }
        2317                 :            :
        2318                 :          0 :             oldval = _PyDict_GetItem_KnownHash(mapping, key, hash);
        2319         [ #  # ]:          0 :             if (oldval == NULL) {
        2320         [ #  # ]:          0 :                 if (PyErr_Occurred())
        2321                 :          0 :                     goto done;
        2322         [ #  # ]:          0 :                 if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) < 0)
        2323                 :          0 :                     goto done;
        2324                 :            :             } else {
        2325                 :          0 :                 newval = PyNumber_Add(oldval, one);
        2326         [ #  # ]:          0 :                 if (newval == NULL)
        2327                 :          0 :                     goto done;
        2328         [ #  # ]:          0 :                 if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0)
        2329                 :          0 :                     goto done;
        2330         [ #  # ]:          0 :                 Py_CLEAR(newval);
        2331                 :            :             }
        2332                 :          0 :             Py_DECREF(key);
        2333                 :            :         }
        2334                 :            :     }
        2335                 :            :     else {
        2336                 :          0 :         bound_get = PyObject_GetAttr(mapping, &_Py_ID(get));
        2337         [ #  # ]:          0 :         if (bound_get == NULL)
        2338                 :          0 :             goto done;
        2339                 :            :
        2340                 :          0 :         PyObject *zero = _PyLong_GetZero();  // borrowed reference
        2341                 :            :         while (1) {
        2342                 :          0 :             key = PyIter_Next(it);
        2343         [ #  # ]:          0 :             if (key == NULL)
        2344                 :          0 :                 break;
        2345                 :          0 :             oldval = PyObject_CallFunctionObjArgs(bound_get, key, zero, NULL);
        2346         [ #  # ]:          0 :             if (oldval == NULL)
        2347                 :          0 :                 break;
        2348                 :          0 :             newval = PyNumber_Add(oldval, one);
        2349                 :          0 :             Py_DECREF(oldval);
        2350         [ #  # ]:          0 :             if (newval == NULL)
        2351                 :          0 :                 break;
        2352         [ #  # ]:          0 :             if (PyObject_SetItem(mapping, key, newval) < 0)
        2353                 :          0 :                 break;
        2354         [ #  # ]:          0 :             Py_CLEAR(newval);
        2355                 :          0 :             Py_DECREF(key);
        2356                 :            :         }
        2357                 :            :     }
        2358                 :            :
        2359                 :          0 : done:
        2360                 :          0 :     Py_DECREF(it);
        2361                 :          0 :     Py_XDECREF(key);
        2362                 :          0 :     Py_XDECREF(newval);
        2363                 :          0 :     Py_XDECREF(bound_get);
        2364         [ #  # ]:          0 :     if (PyErr_Occurred())
        2365                 :          0 :         return NULL;
        2366                 :          0 :     Py_RETURN_NONE;
        2367                 :            : }
        2368                 :            :
        2369                 :            : /* Helper function for namedtuple() ************************************/
        2370                 :            :
        2371                 :            : typedef struct {
        2372                 :            :     PyObject_HEAD
        2373                 :            :     Py_ssize_t index;
        2374                 :            :     PyObject* doc;
        2375                 :            : } _tuplegetterobject;
        2376                 :            :
        2377                 :            : /*[clinic input]
        2378                 :            : @classmethod
        2379                 :            : _tuplegetter.__new__ as tuplegetter_new
        2380                 :            :
        2381                 :            :     index: Py_ssize_t
        2382                 :            :     doc: object
        2383                 :            :     /
        2384                 :            : [clinic start generated code]*/
        2385                 :            :
        2386                 :            : static PyObject *
        2387                 :        255 : tuplegetter_new_impl(PyTypeObject *type, Py_ssize_t index, PyObject *doc)
        2388                 :            : /*[clinic end generated code: output=014be444ad80263f input=87c576a5bdbc0bbb]*/
        2389                 :            : {
        2390                 :            :     _tuplegetterobject* self;
        2391                 :        255 :     self = (_tuplegetterobject *)type->tp_alloc(type, 0);
        2392         [ -  + ]:        255 :     if (self == NULL) {
        2393                 :          0 :         return NULL;
        2394                 :            :     }
        2395                 :        255 :     self->index = index;
        2396                 :        255 :     self->doc = Py_NewRef(doc);
        2397                 :        255 :     return (PyObject *)self;
        2398                 :            : }
        2399                 :            :
        2400                 :            : static PyObject *
        2401                 :       1899 : tuplegetter_descr_get(PyObject *self, PyObject *obj, PyObject *type)
        2402                 :            : {
        2403                 :       1899 :     Py_ssize_t index = ((_tuplegetterobject*)self)->index;
        2404                 :            :     PyObject *result;
        2405                 :            :
        2406         [ +  + ]:       1899 :     if (obj == NULL) {
        2407                 :         58 :         return Py_NewRef(self);
        2408                 :            :     }
        2409         [ -  + ]:       1841 :     if (!PyTuple_Check(obj)) {
        2410         [ #  # ]:          0 :         if (obj == Py_None) {
        2411                 :          0 :             return Py_NewRef(self);
        2412                 :            :         }
        2413                 :          0 :         PyErr_Format(PyExc_TypeError,
        2414                 :            :                      "descriptor for index '%zd' for tuple subclasses "
        2415                 :            :                      "doesn't apply to '%s' object",
        2416                 :            :                      index,
        2417                 :          0 :                      Py_TYPE(obj)->tp_name);
        2418                 :          0 :         return NULL;
        2419                 :            :     }
        2420                 :            :
        2421         [ -  + ]:       1841 :     if (!valid_index(index, PyTuple_GET_SIZE(obj))) {
        2422                 :          0 :         PyErr_SetString(PyExc_IndexError, "tuple index out of range");
        2423                 :          0 :         return NULL;
        2424                 :            :     }
        2425                 :            :
        2426                 :       1841 :     result = PyTuple_GET_ITEM(obj, index);
        2427                 :       1841 :     return Py_NewRef(result);
        2428                 :            : }
        2429                 :            :
        2430                 :            : static int
        2431                 :          0 : tuplegetter_descr_set(PyObject *self, PyObject *obj, PyObject *value)
        2432                 :            : {
        2433         [ #  # ]:          0 :     if (value == NULL) {
        2434                 :          0 :         PyErr_SetString(PyExc_AttributeError, "can't delete attribute");
        2435                 :            :     } else {
        2436                 :          0 :         PyErr_SetString(PyExc_AttributeError, "can't set attribute");
        2437                 :            :     }
        2438                 :          0 :     return -1;
        2439                 :            : }
        2440                 :            :
        2441                 :            : static int
        2442                 :       4188 : tuplegetter_traverse(PyObject *self, visitproc visit, void *arg)
        2443                 :            : {
        2444                 :       4188 :     _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self;
        2445   [ +  -  -  + ]:       4188 :     Py_VISIT(tuplegetter->doc);
        2446                 :       4188 :     return 0;
        2447                 :            : }
        2448                 :            :
        2449                 :            : static int
        2450                 :        249 : tuplegetter_clear(PyObject *self)
        2451                 :            : {
        2452                 :        249 :     _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self;
        2453         [ +  - ]:        249 :     Py_CLEAR(tuplegetter->doc);
        2454                 :        249 :     return 0;
        2455                 :            : }
        2456                 :            :
        2457                 :            : static void
        2458                 :        249 : tuplegetter_dealloc(_tuplegetterobject *self)
        2459                 :            : {
        2460                 :        249 :     PyObject_GC_UnTrack(self);
        2461                 :        249 :     tuplegetter_clear((PyObject*)self);
        2462                 :        249 :     Py_TYPE(self)->tp_free((PyObject*)self);
        2463                 :        249 : }
        2464                 :            :
        2465                 :            : static PyObject*
        2466                 :          0 : tuplegetter_reduce(_tuplegetterobject *self, PyObject *Py_UNUSED(ignored))
        2467                 :            : {
        2468                 :          0 :     return Py_BuildValue("(O(nO))", (PyObject*) Py_TYPE(self), self->index, self->doc);
        2469                 :            : }
        2470                 :            :
        2471                 :            : static PyObject*
        2472                 :          0 : tuplegetter_repr(_tuplegetterobject *self)
        2473                 :            : {
        2474                 :          0 :     return PyUnicode_FromFormat("%s(%zd, %R)",
        2475                 :            :                                 _PyType_Name(Py_TYPE(self)),
        2476                 :            :                                 self->index, self->doc);
        2477                 :            : }
        2478                 :            :
        2479                 :            :
        2480                 :            : static PyMemberDef tuplegetter_members[] = {
        2481                 :            :     {"__doc__",  T_OBJECT, offsetof(_tuplegetterobject, doc), 0},
        2482                 :            :     {0}
        2483                 :            : };
        2484                 :            :
        2485                 :            : static PyMethodDef tuplegetter_methods[] = {
        2486                 :            :     {"__reduce__", (PyCFunction)tuplegetter_reduce, METH_NOARGS, NULL},
        2487                 :            :     {NULL},
        2488                 :            : };
        2489                 :            :
        2490                 :            : static PyTypeObject tuplegetter_type = {
        2491                 :            :     PyVarObject_HEAD_INIT(NULL, 0)
        2492                 :            :     "_collections._tuplegetter",                /* tp_name */
        2493                 :            :     sizeof(_tuplegetterobject),                 /* tp_basicsize */
        2494                 :            :     0,                                          /* tp_itemsize */
        2495                 :            :     /* methods */
        2496                 :            :     (destructor)tuplegetter_dealloc,            /* tp_dealloc */
        2497                 :            :     0,                                          /* tp_vectorcall_offset */
        2498                 :            :     0,                                          /* tp_getattr */
        2499                 :            :     0,                                          /* tp_setattr */
        2500                 :            :     0,                                          /* tp_as_async */
        2501                 :            :     (reprfunc)tuplegetter_repr,                 /* tp_repr */
        2502                 :            :     0,                                          /* tp_as_number */
        2503                 :            :     0,                                          /* tp_as_sequence */
        2504                 :            :     0,                                          /* tp_as_mapping */
        2505                 :            :     0,                                          /* tp_hash */
        2506                 :            :     0,                                          /* tp_call */
        2507                 :            :     0,                                          /* tp_str */
        2508                 :            :     0,                                          /* tp_getattro */
        2509                 :            :     0,                                          /* tp_setattro */
        2510                 :            :     0,                                          /* tp_as_buffer */
        2511                 :            :     Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,    /* tp_flags */
        2512                 :            :     0,                                          /* tp_doc */
        2513                 :            :     (traverseproc)tuplegetter_traverse,         /* tp_traverse */
        2514                 :            :     (inquiry)tuplegetter_clear,                 /* tp_clear */
        2515                 :            :     0,                                          /* tp_richcompare */
        2516                 :            :     0,                                          /* tp_weaklistoffset */
        2517                 :            :     0,                                          /* tp_iter */
        2518                 :            :     0,                                          /* tp_iternext */
        2519                 :            :     tuplegetter_methods,                        /* tp_methods */
        2520                 :            :     tuplegetter_members,                        /* tp_members */
        2521                 :            :     0,                                          /* tp_getset */
        2522                 :            :     0,                                          /* tp_base */
        2523                 :            :     0,                                          /* tp_dict */
        2524                 :            :     tuplegetter_descr_get,                      /* tp_descr_get */
        2525                 :            :     tuplegetter_descr_set,                      /* tp_descr_set */
        2526                 :            :     0,                                          /* tp_dictoffset */
        2527                 :            :     0,                                          /* tp_init */
        2528                 :            :     0,                                          /* tp_alloc */
        2529                 :            :     tuplegetter_new,                            /* tp_new */
        2530                 :            :     0,
        2531                 :            : };
        2532                 :            :
        2533                 :            :
        2534                 :            : /* module level code ********************************************************/
        2535                 :            :
        2536                 :            : PyDoc_STRVAR(collections_doc,
        2537                 :            : "High performance data structures.\n\
        2538                 :            : - deque:        ordered collection accessible from endpoints only\n\
        2539                 :            : - defaultdict:  dict subclass with a default value factory\n\
        2540                 :            : ");
        2541                 :            :
        2542                 :            : static struct PyMethodDef collections_methods[] = {
        2543                 :            :     _COLLECTIONS__COUNT_ELEMENTS_METHODDEF
        2544                 :            :     {NULL,       NULL}          /* sentinel */
        2545                 :            : };
        2546                 :            :
        2547                 :            : static int
        2548                 :          6 : collections_exec(PyObject *module) {
        2549                 :          6 :     PyTypeObject *typelist[] = {
        2550                 :            :         &deque_type,
        2551                 :            :         &defdict_type,
        2552                 :            :         &PyODict_Type,
        2553                 :            :         &dequeiter_type,
        2554                 :            :         &dequereviter_type,
        2555                 :            :         &tuplegetter_type
        2556                 :            :     };
        2557                 :            :
        2558                 :          6 :     defdict_type.tp_base = &PyDict_Type;
        2559                 :            :
        2560         [ +  + ]:         42 :     for (size_t i = 0; i < Py_ARRAY_LENGTH(typelist); i++) {
        2561         [ -  + ]:         36 :         if (PyModule_AddType(module, typelist[i]) < 0) {
        2562                 :          0 :             return -1;
        2563                 :            :         }
        2564                 :            :     }
        2565                 :            :
        2566                 :          6 :     return 0;
        2567                 :            : }
        2568                 :            :
        2569                 :            : static struct PyModuleDef_Slot collections_slots[] = {
        2570                 :            :     {Py_mod_exec, collections_exec},
        2571                 :            :     {0, NULL}
        2572                 :            : };
        2573                 :            :
        2574                 :            : static struct PyModuleDef _collectionsmodule = {
        2575                 :            :     PyModuleDef_HEAD_INIT,
        2576                 :            :     "_collections",
        2577                 :            :     collections_doc,
        2578                 :            :     0,
        2579                 :            :     collections_methods,
        2580                 :            :     collections_slots,
        2581                 :            :     NULL,
        2582                 :            :     NULL,
        2583                 :            :     NULL
        2584                 :            : };
        2585                 :            :
        2586                 :            : PyMODINIT_FUNC
        2587                 :          6 : PyInit__collections(void)
        2588                 :            : {
        2589                 :          6 :     return PyModuleDef_Init(&_collectionsmodule);
        2590                 :            : }

Generated by: LCOV version 1.14