17eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#include "Python.h" 27eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#include "structmember.h" 37eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 47eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* collections module implementation of a deque() datatype 57eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Written and maintained by Raymond D. Hettinger <python@rcn.com> 67eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Copyright (c) 2004 Python Software Foundation. 77eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel All rights reserved. 87eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel*/ 97eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* The block length may be set to any number over 1. Larger numbers 117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * reduce the number of calls to the memory allocator, give faster 127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * indexing and rotation, and reduce the link::data overhead ratio. 137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * 147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * Ideally, the block length will be set to two less than some 157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * multiple of the cache-line length (so that the full block 167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * including the leftlink and rightlink will fit neatly into 177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * cache lines). 187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel */ 197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#define BLOCKLEN 62 217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#define CENTER ((BLOCKLEN - 1) / 2) 227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* A `dequeobject` is composed of a doubly-linked list of `block` nodes. 247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * This list is not circular (the leftmost block has leftlink==NULL, 257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * and the rightmost block has rightlink==NULL). A deque d's first 267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * element is at d.leftblock[leftindex] and its last element is at 277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * d.rightblock[rightindex]; note that, unlike as for Python slice 287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * indices, these indices are inclusive on both ends. By being inclusive 297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * on both ends, algorithms for left and right operations become 307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * symmetrical which simplifies the design. 317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * 327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * The list of blocks is never empty, so d.leftblock and d.rightblock 337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * are never equal to NULL. 347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * 357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * The indices, d.leftindex and d.rightindex are always in the range 367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * 0 <= index < BLOCKLEN. 377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * Their exact relationship is: 387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex. 397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * 407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * Empty deques have d.len == 0; d.leftblock==d.rightblock; 417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * d.leftindex == CENTER+1; and d.rightindex == CENTER. 427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * Checking for d.len == 0 is the intended way to see whether d is empty. 437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * 447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * Whenever d.leftblock == d.rightblock, 457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * d.leftindex + d.len - 1 == d.rightindex. 467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * 477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * However, when d.leftblock != d.rightblock, d.leftindex and d.rightindex 487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * become indices into distinct blocks and either may be larger than the 497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * other. 507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel */ 517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieltypedef struct BLOCK { 537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *data[BLOCKLEN]; 547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel struct BLOCK *rightlink; 557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel struct BLOCK *leftlink; 567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} block; 577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#define MAXFREEBLOCKS 10 597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic Py_ssize_t numfreeblocks = 0; 607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic block *freeblocks[MAXFREEBLOCKS]; 617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic block * 637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielnewblock(block *leftlink, block *rightlink, Py_ssize_t len) { 647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b; 657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* To prevent len from overflowing PY_SSIZE_T_MAX on 32-bit machines, we 667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * refuse to allocate new blocks if the current len is nearing overflow. */ 677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) { 687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_OverflowError, 697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "cannot add more blocks to the deque"); 707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (numfreeblocks) { 737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel numfreeblocks -= 1; 747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = freeblocks[numfreeblocks]; 757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else { 767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = PyMem_Malloc(sizeof(block)); 777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == NULL) { 787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_NoMemory(); 797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b->leftlink = leftlink; 837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b->rightlink = rightlink; 847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return b; 857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic void 887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielfreeblock(block *b) 897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (numfreeblocks < MAXFREEBLOCKS) { 917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel freeblocks[numfreeblocks] = b; 927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel numfreeblocks++; 937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else { 947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyMem_Free(b); 957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieltypedef struct { 997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_HEAD 1007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *leftblock; 1017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *rightblock; 1027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t leftindex; /* in range(BLOCKLEN) */ 1037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t rightindex; /* in range(BLOCKLEN) */ 1047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t len; 1057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel long state; /* incremented whenever the indices move */ 1067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t maxlen; 1077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *weakreflist; /* List of weak references */ 1087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} dequeobject; 1097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* The deque's size limit is d.maxlen. The limit can be zero or positive. 1117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * If there is no limit, then d.maxlen == -1. 1127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * 1137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * After an item is added to a deque, we check to see if the size has grown past 1147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * the limit. If it has, we get the size back down to the limit by popping an 1157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * item off of the opposite end. The methods that can trigger this are append(), 1167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel * appendleft(), extend(), and extendleft(). 1177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel */ 1187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#define TRIM(d, popfunction) \ 1207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (d->maxlen != -1 && d->len > d->maxlen) { \ 1217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *rv = popfunction(d, NULL); \ 1227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(rv != NULL && d->len <= d->maxlen); \ 1237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(rv); \ 1247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyTypeObject deque_type; 1277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 1297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 1307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 1317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel dequeobject *deque; 1327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b; 1337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* create dequeobject structure */ 1357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque = (dequeobject *)type->tp_alloc(type, 0); 1367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque == NULL) 1377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = newblock(NULL, NULL, 0); 1407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == NULL) { 1417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(deque); 1427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(BLOCKLEN >= 2); 1467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock = b; 1477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock = b; 1487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex = CENTER + 1; 1497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex = CENTER; 1507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len = 0; 1517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->state = 0; 1527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->weakreflist = NULL; 1537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->maxlen = -1; 1547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return (PyObject *)deque; 1567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 1577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 1597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_pop(dequeobject *deque, PyObject *unused) 1607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 1617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 1627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *prevblock; 1637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->len == 0) { 1657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, "pop from an empty deque"); 1667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 1677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = deque->rightblock->data[deque->rightindex]; 1697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex--; 1707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len--; 1717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->state++; 1727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->rightindex == -1) { 1747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->len == 0) { 1757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock == deque->rightblock); 1767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftindex == deque->rightindex+1); 1777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* re-center instead of freeing a block */ 1787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex = CENTER + 1; 1797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex = CENTER; 1807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else { 1817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel prevblock = deque->rightblock->leftlink; 1827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock != deque->rightblock); 1837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel freeblock(deque->rightblock); 1847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel prevblock->rightlink = NULL; 1857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock = prevblock; 1867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex = BLOCKLEN - 1; 1877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 1897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return item; 1907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 1917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(pop_doc, "Remove and return the rightmost element."); 1937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 1947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 1957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_popleft(dequeobject *deque, PyObject *unused) 1967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 1977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 1987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *prevblock; 1997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->len == 0) { 2017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, "pop from an empty deque"); 2027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock != NULL); 2057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = deque->leftblock->data[deque->leftindex]; 2067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex++; 2077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len--; 2087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->state++; 2097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->leftindex == BLOCKLEN) { 2117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->len == 0) { 2127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock == deque->rightblock); 2137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftindex == deque->rightindex+1); 2147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* re-center instead of freeing a block */ 2157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex = CENTER + 1; 2167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex = CENTER; 2177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else { 2187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock != deque->rightblock); 2197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel prevblock = deque->leftblock->rightlink; 2207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel freeblock(deque->leftblock); 2217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(prevblock != NULL); 2227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel prevblock->leftlink = NULL; 2237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock = prevblock; 2247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex = 0; 2257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return item; 2287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 2297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element."); 2317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 2337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_append(dequeobject *deque, PyObject *item) 2347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 2357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->state++; 2367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->rightindex == BLOCKLEN-1) { 2377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b = newblock(deque->rightblock, NULL, deque->len); 2387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == NULL) 2397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->rightblock->rightlink == NULL); 2417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock->rightlink = b; 2427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock = b; 2437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex = -1; 2447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(item); 2467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len++; 2477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex++; 2487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock->data[deque->rightindex] = item; 2497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel TRIM(deque, deque_popleft); 2507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 2517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 2527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(append_doc, "Add an element to the right side of the deque."); 2547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 2567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_appendleft(dequeobject *deque, PyObject *item) 2577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 2587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->state++; 2597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->leftindex == 0) { 2607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b = newblock(NULL, deque->leftblock, deque->len); 2617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == NULL) 2627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock->leftlink == NULL); 2647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock->leftlink = b; 2657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock = b; 2667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex = BLOCKLEN; 2677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(item); 2697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len++; 2707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex--; 2717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock->data[deque->leftindex] = item; 2727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel TRIM(deque, deque_pop); 2737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 2747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 2757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque."); 2777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* Run an iterator to exhaustion. Shortcut for 2807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel the extend/extendleft methods when maxlen == 0. */ 2817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject* 2827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielconsume_iterator(PyObject *it) 2837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 2847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 2857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while ((item = PyIter_Next(it)) != NULL) { 2877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(item); 2887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 2897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 2907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyErr_Occurred()) 2917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 2927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 2937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 2947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 2957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 2967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_extend(dequeobject *deque, PyObject *iterable) 2977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 2987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *it, *item; 2997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Handle case where id(deque) == id(iterable) */ 3017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if ((PyObject *)deque == iterable) { 3027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *result; 3037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *s = PySequence_List(iterable); 3047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (s == NULL) 3057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = deque_extend(deque, s); 3077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(s); 3087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return result; 3097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it = PyObject_GetIter(iterable); 3127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it == NULL) 3137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->maxlen == 0) 3167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return consume_iterator(it); 3177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while ((item = PyIter_Next(it)) != NULL) { 3197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->state++; 3207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->rightindex == BLOCKLEN-1) { 3217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b = newblock(deque->rightblock, NULL, 3227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len); 3237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == NULL) { 3247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(item); 3257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 3267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->rightblock->rightlink == NULL); 3297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock->rightlink = b; 3307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock = b; 3317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex = -1; 3327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len++; 3347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex++; 3357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock->data[deque->rightindex] = item; 3367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel TRIM(deque, deque_popleft); 3377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 3397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyErr_Occurred()) 3407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 3427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 3437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(extend_doc, 3457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"Extend the right side of the deque with elements from the iterable"); 3467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 3487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_extendleft(dequeobject *deque, PyObject *iterable) 3497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 3507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *it, *item; 3517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Handle case where id(deque) == id(iterable) */ 3537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if ((PyObject *)deque == iterable) { 3547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *result; 3557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *s = PySequence_List(iterable); 3567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (s == NULL) 3577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = deque_extendleft(deque, s); 3597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(s); 3607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return result; 3617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it = PyObject_GetIter(iterable); 3647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it == NULL) 3657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->maxlen == 0) 3687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return consume_iterator(it); 3697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while ((item = PyIter_Next(it)) != NULL) { 3717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->state++; 3727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->leftindex == 0) { 3737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b = newblock(NULL, deque->leftblock, 3747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len); 3757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == NULL) { 3767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(item); 3777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 3787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock->leftlink == NULL); 3817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock->leftlink = b; 3827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock = b; 3837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex = BLOCKLEN; 3847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len++; 3867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex--; 3877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock->data[deque->leftindex] = item; 3887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel TRIM(deque, deque_pop); 3897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 3907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 3917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyErr_Occurred()) 3927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 3937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 3947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 3957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(extendleft_doc, 3977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"Extend the left side of the deque with elements from the iterable"); 3987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 3997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 4007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_inplace_concat(dequeobject *deque, PyObject *other) 4017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 4027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *result; 4037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = deque_extend(deque, other); 4057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (result == NULL) 4067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return result; 4077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(result); 4087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(deque); 4097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return (PyObject *)deque; 4107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 4117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 4137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel_deque_rotate(dequeobject *deque, Py_ssize_t n) 4147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 4157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t m, len=deque->len, halflen=len>>1; 4167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (len <= 1) 4187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 4197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (n > halflen || n < -halflen) { 4207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n %= len; 4217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (n > halflen) 4227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n -= len; 4237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else if (n < -halflen) 4247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n += len; 4257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(len > 1); 4277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(-halflen <= n && n <= halflen); 4287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->state++; 4307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (n > 0) { 4317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->leftindex == 0) { 4327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b = newblock(NULL, deque->leftblock, len); 4337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == NULL) 4347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 4357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock->leftlink == NULL); 4367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock->leftlink = b; 4377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock = b; 4387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex = BLOCKLEN; 4397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftindex > 0); 4417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m = n; 4437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (m > deque->rightindex + 1) 4447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m = deque->rightindex + 1; 4457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (m > deque->leftindex) 4467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m = deque->leftindex; 4477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (m > 0 && m <= len); 4487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel memcpy(&deque->leftblock->data[deque->leftindex - m], 4497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel &deque->rightblock->data[deque->rightindex + 1 - m], 4507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m * sizeof(PyObject *)); 4517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex -= m; 4527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex -= m; 4537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n -= m; 4547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->rightindex == -1) { 4567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *prevblock = deque->rightblock->leftlink; 4577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->rightblock != NULL); 4587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock != deque->rightblock); 4597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel freeblock(deque->rightblock); 4607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel prevblock->rightlink = NULL; 4617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock = prevblock; 4627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex = BLOCKLEN - 1; 4637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (n < 0) { 4667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->rightindex == BLOCKLEN - 1) { 4677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b = newblock(deque->rightblock, NULL, len); 4687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == NULL) 4697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 4707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->rightblock->rightlink == NULL); 4717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock->rightlink = b; 4727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock = b; 4737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex = -1; 4747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (deque->rightindex < BLOCKLEN - 1); 4767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m = -n; 4787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (m > BLOCKLEN - deque->leftindex) 4797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m = BLOCKLEN - deque->leftindex; 4807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (m > BLOCKLEN - 1 - deque->rightindex) 4817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m = BLOCKLEN - 1 - deque->rightindex; 4827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (m > 0 && m <= len); 4837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel memcpy(&deque->rightblock->data[deque->rightindex + 1], 4847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel &deque->leftblock->data[deque->leftindex], 4857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m * sizeof(PyObject *)); 4867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex += m; 4877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex += m; 4887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n += m; 4897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 4907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->leftindex == BLOCKLEN) { 4917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *nextblock = deque->leftblock->rightlink; 4927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock != deque->rightblock); 4937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel freeblock(deque->leftblock); 4947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(nextblock != NULL); 4957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel nextblock->leftlink = NULL; 4967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock = nextblock; 4977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex = 0; 4987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 4997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 5017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 5027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 5047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_rotate(dequeobject *deque, PyObject *args) 5057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 5067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t n=1; 5077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyArg_ParseTuple(args, "|n:rotate", &n)) 5097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 5107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (_deque_rotate(deque, n) == 0) 5117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 5127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 5137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 5147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(rotate_doc, 5167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left."); 5177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 5197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_reverse(dequeobject *deque, PyObject *unused) 5207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 5217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *leftblock = deque->leftblock; 5227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *rightblock = deque->rightblock; 5237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t leftindex = deque->leftindex; 5247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t rightindex = deque->rightindex; 5257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t n = (deque->len)/2; 5267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t i; 5277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *tmp; 5287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (i=0 ; i<n ; i++) { 5307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Validate that pointers haven't met in the middle */ 5317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(leftblock != rightblock || leftindex < rightindex); 5327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Swap */ 5347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel tmp = leftblock->data[leftindex]; 5357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel leftblock->data[leftindex] = rightblock->data[rightindex]; 5367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel rightblock->data[rightindex] = tmp; 5377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Advance left block/index pair */ 5397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel leftindex++; 5407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (leftindex == BLOCKLEN) { 5417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (leftblock->rightlink == NULL) 5427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel break; 5437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel leftblock = leftblock->rightlink; 5447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel leftindex = 0; 5457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Step backwards with the right block/index pair */ 5487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel rightindex--; 5497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (rightindex == -1) { 5507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (rightblock->leftlink == NULL) 5517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel break; 5527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel rightblock = rightblock->leftlink; 5537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel rightindex = BLOCKLEN - 1; 5547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 5577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 5587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(reverse_doc, 5607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"D.reverse() -- reverse *IN PLACE*"); 5617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 5637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_count(dequeobject *deque, PyObject *v) 5647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 5657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *leftblock = deque->leftblock; 5667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t leftindex = deque->leftindex; 5677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t n = deque->len; 5687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t i; 5697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t count = 0; 5707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 5717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel long start_state = deque->state; 5727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp; 5737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (i=0 ; i<n ; i++) { 5757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = leftblock->data[leftindex]; 5767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = PyObject_RichCompareBool(item, v, Py_EQ); 5777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp > 0) 5787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel count++; 5797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else if (cmp < 0) 5807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 5817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (start_state != deque->state) { 5837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_RuntimeError, 5847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "deque mutated during iteration"); 5857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 5867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 5887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Advance left block/index pair */ 5897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel leftindex++; 5907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (leftindex == BLOCKLEN) { 5917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (leftblock->rightlink == NULL) /* can occur when i==n-1 */ 5927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel break; 5937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel leftblock = leftblock->rightlink; 5947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel leftindex = 0; 5957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 5977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyInt_FromSsize_t(count); 5987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 5997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(count_doc, 6017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"D.count(value) -> integer -- return number of occurrences of value"); 6027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic Py_ssize_t 6047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_len(dequeobject *deque) 6057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 6067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return deque->len; 6077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 6087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 6107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_remove(dequeobject *deque, PyObject *value) 6117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 6127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t i, n=deque->len; 6137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (i=0 ; i<n ; i++) { 6157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item = deque->leftblock->data[deque->leftindex]; 6167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int cmp = PyObject_RichCompareBool(item, value, Py_EQ); 6177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->len != n) { 6197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, 6207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "deque mutated during remove()."); 6217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 6227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 6237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp > 0) { 6247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *tgt = deque_popleft(deque, NULL); 6257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (tgt != NULL); 6267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (_deque_rotate(deque, i)) 6277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 6287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(tgt); 6297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 6307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 6317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else if (cmp < 0) { 6327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel _deque_rotate(deque, i); 6337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 6347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 6357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel _deque_rotate(deque, -1); 6367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 6377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque"); 6387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 6397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 6407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(remove_doc, 6427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"D.remove(value) -- remove first occurrence of value."); 6437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic void 6457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_clear(dequeobject *deque) 6467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 6477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 6487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (deque->len) { 6507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = deque_pop(deque, NULL); 6517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (item != NULL); 6527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(item); 6537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 6547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock == deque->rightblock && 6557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftindex - 1 == deque->rightindex && 6567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->len == 0); 6577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 6587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 6607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_item(dequeobject *deque, Py_ssize_t i) 6617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 6627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b; 6637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 6647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t n, index=i; 6657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (i < 0 || i >= deque->len) { 6677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, 6687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "deque index out of range"); 6697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 6707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 6717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (i == 0) { 6737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel i = deque->leftindex; 6747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = deque->leftblock; 6757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else if (i == deque->len - 1) { 6767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel i = deque->rightindex; 6777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = deque->rightblock; 6787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else { 6797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel i += deque->leftindex; 6807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n = i / BLOCKLEN; 6817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel i %= BLOCKLEN; 6827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (index < (deque->len >> 1)) { 6837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = deque->leftblock; 6847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (n--) 6857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = b->rightlink; 6867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else { 6877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n; 6887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = deque->rightblock; 6897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (n--) 6907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = b->leftlink; 6917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 6927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 6937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = b->data[i]; 6947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(item); 6957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return item; 6967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 6977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 6987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* delitem() implemented in terms of rotate for simplicity and reasonable 6997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel performance near the end points. If for some reason this method becomes 7007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel popular, it is not hard to re-implement this using direct data movement 7017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (similar to code in list slice assignment) and achieve a two or threefold 7027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel performance boost. 7037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel*/ 7047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 7067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_del_item(dequeobject *deque, Py_ssize_t i) 7077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 7087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 7097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int rv; 7107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (i >= 0 && i < deque->len); 7127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (_deque_rotate(deque, -i)) 7137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 7147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = deque_popleft(deque, NULL); 7157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel rv = _deque_rotate(deque, i); 7167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (item != NULL); 7177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(item); 7187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return rv; 7197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 7207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 7227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v) 7237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 7247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *old_value; 7257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b; 7267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i; 7277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (i < 0 || i >= len) { 7297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_IndexError, 7307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "deque index out of range"); 7317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 7327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 7337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (v == NULL) 7347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return deque_del_item(deque, i); 7357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel i += deque->leftindex; 7377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n = i / BLOCKLEN; 7387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel i %= BLOCKLEN; 7397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (index <= halflen) { 7407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = deque->leftblock; 7417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (n--) 7427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = b->rightlink; 7437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else { 7447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel n = (deque->leftindex + len - 1) / BLOCKLEN - n; 7457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = deque->rightblock; 7467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while (n--) 7477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = b->leftlink; 7487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 7497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(v); 7507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel old_value = b->data[i]; 7517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b->data[i] = v; 7527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(old_value); 7537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 7547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 7557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 7577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_clearmethod(dequeobject *deque) 7587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 7597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque_clear(deque); 7607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 7617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 7627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(clear_doc, "Remove all elements from the deque."); 7647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic void 7667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_dealloc(dequeobject *deque) 7677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 7687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GC_UnTrack(deque); 7697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->weakreflist != NULL) 7707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_ClearWeakRefs((PyObject *) deque); 7717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->leftblock != NULL) { 7727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque_clear(deque); 7737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftblock != NULL); 7747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel freeblock(deque->leftblock); 7757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 7767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->leftblock = NULL; 7777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightblock = NULL; 7787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_TYPE(deque)->tp_free(deque); 7797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 7807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 7827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_traverse(dequeobject *deque, visitproc visit, void *arg) 7837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 7847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b; 7857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 7867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t index; 7877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t indexlo = deque->leftindex; 7887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (b = deque->leftblock; b != NULL; b = b->rightlink) { 7907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel const Py_ssize_t indexhi = b == deque->rightblock ? 7917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->rightindex : 7927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel BLOCKLEN - 1; 7937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 7947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (index = indexlo; index <= indexhi; ++index) { 7957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = b->data[index]; 7967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_VISIT(item); 7977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 7987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel indexlo = 0; 7997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 8007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 8017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 8027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 8047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_copy(PyObject *deque) 8057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 8067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (((dequeobject *)deque)->maxlen == -1) 8077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL); 8087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 8097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi", 8107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque, ((dequeobject *)deque)->maxlen, NULL); 8117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 8127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque."); 8147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 8167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_reduce(dequeobject *deque) 8177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 8187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *dict, *result, *aslist; 8197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel dict = PyObject_GetAttrString((PyObject *)deque, "__dict__"); 8217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (dict == NULL) 8227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_Clear(); 8237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel aslist = PySequence_List((PyObject *)deque); 8247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (aslist == NULL) { 8257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(dict); 8267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 8277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 8287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (dict == NULL) { 8297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->maxlen == -1) 8307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist); 8317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 8327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen); 8337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else { 8347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->maxlen == -1) 8357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict); 8367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 8377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict); 8387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 8397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(dict); 8407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(aslist); 8417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return result; 8427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 8437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(reduce_doc, "Return state information for pickling."); 8457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 8477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_repr(PyObject *deque) 8487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 8497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *aslist, *result, *fmt; 8507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int i; 8517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel i = Py_ReprEnter(deque); 8537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (i != 0) { 8547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (i < 0) 8557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 8567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyString_FromString("[...]"); 8577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 8587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel aslist = PySequence_List(deque); 8607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (aslist == NULL) { 8617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ReprLeave(deque); 8627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 8637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 8647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (((dequeobject *)deque)->maxlen != -1) 8657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fmt = PyString_FromFormat("deque(%%r, maxlen=%zd)", 8667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel ((dequeobject *)deque)->maxlen); 8677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 8687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fmt = PyString_FromString("deque(%r)"); 8697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (fmt == NULL) { 8707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(aslist); 8717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ReprLeave(deque); 8727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 8737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 8747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = PyString_Format(fmt, aslist); 8757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(fmt); 8767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(aslist); 8777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ReprLeave(deque); 8787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return result; 8797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 8807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 8827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_tp_print(PyObject *deque, FILE *fp, int flags) 8837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 8847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *it, *item; 8857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel char *emit = ""; /* No separator emitted on first pass */ 8867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel char *separator = ", "; 8877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int i; 8887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel i = Py_ReprEnter(deque); 8907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (i != 0) { 8917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (i < 0) 8927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return i; 8937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_BEGIN_ALLOW_THREADS 8947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fputs("[...]", fp); 8957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_END_ALLOW_THREADS 8967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 8977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 8987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 8997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it = PyObject_GetIter(deque); 9007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it == NULL) 9017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 9027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 9037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_BEGIN_ALLOW_THREADS 9047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fputs("deque([", fp); 9057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_END_ALLOW_THREADS 9067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel while ((item = PyIter_Next(it)) != NULL) { 9077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_BEGIN_ALLOW_THREADS 9087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fputs(emit, fp); 9097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_END_ALLOW_THREADS 9107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel emit = separator; 9117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyObject_Print(item, fp, 0) != 0) { 9127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(item); 9137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 9147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ReprLeave(deque); 9157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 9167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 9177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(item); 9187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 9197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ReprLeave(deque); 9207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(it); 9217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyErr_Occurred()) 9227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 9237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 9247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_BEGIN_ALLOW_THREADS 9257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (((dequeobject *)deque)->maxlen == -1) 9267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fputs("])", fp); 9277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 9287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fprintf(fp, "], maxlen=%" PY_FORMAT_SIZE_T "d)", ((dequeobject *)deque)->maxlen); 9297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_END_ALLOW_THREADS 9307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 9317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 9327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 9337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 9347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_richcompare(PyObject *v, PyObject *w, int op) 9357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 9367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *it1=NULL, *it2=NULL, *x, *y; 9377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t vs, ws; 9387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int b, cmp=-1; 9397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 9407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyObject_TypeCheck(v, &deque_type) || 9417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel !PyObject_TypeCheck(w, &deque_type)) { 9427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(Py_NotImplemented); 9437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return Py_NotImplemented; 9447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 9457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 9467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Shortcuts */ 9477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel vs = ((dequeobject *)v)->len; 9487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel ws = ((dequeobject *)w)->len; 9497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (op == Py_EQ) { 9507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (v == w) 9517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_TRUE; 9527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (vs != ws) 9537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_FALSE; 9547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 9557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (op == Py_NE) { 9567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (v == w) 9577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_FALSE; 9587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (vs != ws) 9597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_TRUE; 9607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 9617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 9627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* Search for the first index where items are different */ 9637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it1 = PyObject_GetIter(v); 9647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it1 == NULL) 9657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto done; 9667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it2 = PyObject_GetIter(w); 9677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it2 == NULL) 9687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto done; 9697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel for (;;) { 9707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel x = PyIter_Next(it1); 9717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (x == NULL && PyErr_Occurred()) 9727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto done; 9737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel y = PyIter_Next(it2); 9747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (x == NULL || y == NULL) 9757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel break; 9767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel b = PyObject_RichCompareBool(x, y, Py_EQ); 9777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == 0) { 9787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel cmp = PyObject_RichCompareBool(x, y, op); 9797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(x); 9807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(y); 9817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto done; 9827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 9837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(x); 9847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(y); 9857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (b == -1) 9867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto done; 9877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 9887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* We reached the end of one deque or both */ 9897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(x); 9907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(y); 9917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyErr_Occurred()) 9927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel goto done; 9937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel switch (op) { 9947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel case Py_LT: cmp = y != NULL; break; /* if w was longer */ 9957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel case Py_LE: cmp = x == NULL; break; /* if v was not longer */ 9967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel case Py_EQ: cmp = x == y; break; /* if we reached the end of both */ 9977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel case Py_NE: cmp = x != y; break; /* if one deque continues */ 9987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel case Py_GT: cmp = x != NULL; break; /* if v was longer */ 9997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel case Py_GE: cmp = y == NULL; break; /* if w was not longer */ 10007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 10017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldone: 10037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(it1); 10047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(it2); 10057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == 1) 10067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_TRUE; 10077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (cmp == 0) 10087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_FALSE; 10097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 10107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 10117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 10137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs) 10147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 10157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *iterable = NULL; 10167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *maxlenobj = NULL; 10177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t maxlen = -1; 10187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel char *kwlist[] = {"iterable", "maxlen", 0}; 10197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj)) 10217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 10227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (maxlenobj != NULL && maxlenobj != Py_None) { 10237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel maxlen = PyInt_AsSsize_t(maxlenobj); 10247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (maxlen == -1 && PyErr_Occurred()) 10257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 10267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (maxlen < 0) { 10277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative"); 10287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 10297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 10307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 10317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque->maxlen = maxlen; 10327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque_clear(deque); 10337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (iterable != NULL) { 10347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *rv = deque_extend(deque, iterable); 10357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (rv == NULL) 10367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 10377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(rv); 10387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 10397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 10407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 10417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 10437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_sizeof(dequeobject *deque, void *unused) 10447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 10457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t res; 10467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t blocks; 10477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel res = sizeof(dequeobject); 10497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel blocks = (deque->leftindex + deque->len + BLOCKLEN - 1) / BLOCKLEN; 10507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert(deque->leftindex + deque->len - 1 == 10517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (blocks - 1) * BLOCKLEN + deque->rightindex); 10527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel res += blocks * sizeof(block); 10537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyLong_FromSsize_t(res); 10547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 10557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(sizeof_doc, 10577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"D.__sizeof__() -- size of D in memory, in bytes"); 10587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 10607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_get_maxlen(dequeobject *deque) 10617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 10627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (deque->maxlen == -1) 10637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_RETURN_NONE; 10647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyInt_FromSsize_t(deque->maxlen); 10657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 10667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyGetSetDef deque_getset[] = { 10687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"maxlen", (getter)deque_get_maxlen, (setter)NULL, 10697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "maximum size of a deque or None if unbounded"}, 10707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {0} 10717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 10727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PySequenceMethods deque_as_sequence = { 10747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (lenfunc)deque_len, /* sq_length */ 10757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* sq_concat */ 10767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* sq_repeat */ 10777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (ssizeargfunc)deque_item, /* sq_item */ 10787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* sq_slice */ 10797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (ssizeobjargproc)deque_ass_item, /* sq_ass_item */ 10807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* sq_ass_slice */ 10817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* sq_contains */ 10827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */ 10837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* sq_inplace_repeat */ 10847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 10867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* deque object ********************************************************/ 10887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject *deque_iter(dequeobject *deque); 10907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject *deque_reviter(dequeobject *deque); 10917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(reversed_doc, 10927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "D.__reversed__() -- return a reverse iterator over the deque"); 10937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 10947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyMethodDef deque_methods[] = { 10957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"append", (PyCFunction)deque_append, 10967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_O, append_doc}, 10977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"appendleft", (PyCFunction)deque_appendleft, 10987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_O, appendleft_doc}, 10997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"clear", (PyCFunction)deque_clearmethod, 11007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_NOARGS, clear_doc}, 11017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"__copy__", (PyCFunction)deque_copy, 11027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_NOARGS, copy_doc}, 11037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"count", (PyCFunction)deque_count, 11047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_O, count_doc}, 11057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"extend", (PyCFunction)deque_extend, 11067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_O, extend_doc}, 11077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"extendleft", (PyCFunction)deque_extendleft, 11087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_O, extendleft_doc}, 11097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"pop", (PyCFunction)deque_pop, 11107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_NOARGS, pop_doc}, 11117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"popleft", (PyCFunction)deque_popleft, 11127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_NOARGS, popleft_doc}, 11137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"__reduce__", (PyCFunction)deque_reduce, 11147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_NOARGS, reduce_doc}, 11157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"remove", (PyCFunction)deque_remove, 11167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_O, remove_doc}, 11177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"__reversed__", (PyCFunction)deque_reviter, 11187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_NOARGS, reversed_doc}, 11197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"reverse", (PyCFunction)deque_reverse, 11207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_NOARGS, reverse_doc}, 11217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"rotate", (PyCFunction)deque_rotate, 11227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_VARARGS, rotate_doc}, 11237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"__sizeof__", (PyCFunction)deque_sizeof, 11247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel METH_NOARGS, sizeof_doc}, 11257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {NULL, NULL} /* sentinel */ 11267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 11277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 11287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(deque_doc, 11297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"deque([iterable[, maxlen]]) --> deque object\n\ 11307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 11317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielBuild an ordered collection with optimized access from its endpoints."); 11327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 11337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyTypeObject deque_type = { 11347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyVarObject_HEAD_INIT(NULL, 0) 11357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "collections.deque", /* tp_name */ 11367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel sizeof(dequeobject), /* tp_basicsize */ 11377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_itemsize */ 11387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* methods */ 11397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (destructor)deque_dealloc, /* tp_dealloc */ 11407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque_tp_print, /* tp_print */ 11417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_getattr */ 11427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_setattr */ 11437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_compare */ 11447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque_repr, /* tp_repr */ 11457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_number */ 11467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel &deque_as_sequence, /* tp_as_sequence */ 11477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_mapping */ 11487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (hashfunc)PyObject_HashNotImplemented, /* tp_hash */ 11497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_call */ 11507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_str */ 11517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GenericGetAttr, /* tp_getattro */ 11527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_setattro */ 11537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_buffer */ 11547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC | 11557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */ 11567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque_doc, /* tp_doc */ 11577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (traverseproc)deque_traverse, /* tp_traverse */ 11587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (inquiry)deque_clear, /* tp_clear */ 11597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (richcmpfunc)deque_richcompare, /* tp_richcompare */ 11607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/ 11617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (getiterfunc)deque_iter, /* tp_iter */ 11627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_iternext */ 11637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque_methods, /* tp_methods */ 11647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_members */ 11657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque_getset, /* tp_getset */ 11667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_base */ 11677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_dict */ 11687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_descr_get */ 11697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_descr_set */ 11707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_dictoffset */ 11717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (initproc)deque_init, /* tp_init */ 11727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyType_GenericAlloc, /* tp_alloc */ 11737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel deque_new, /* tp_new */ 11747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GC_Del, /* tp_free */ 11757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 11767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 11777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/*********************** Deque Iterator **************************/ 11787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 11797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieltypedef struct { 11807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_HEAD 11817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t index; 11827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel block *b; 11837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel dequeobject *deque; 11847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel long state; /* state when the iterator is created */ 11857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t counter; /* number of items remaining for iteration */ 11867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} dequeiterobject; 11877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 11887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyTypeObject dequeiter_type; 11897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 11907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 11917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_iter(dequeobject *deque) 11927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 11937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel dequeiterobject *it; 11947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 11957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it = PyObject_GC_New(dequeiterobject, &dequeiter_type); 11967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it == NULL) 11977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 11987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->b = deque->leftblock; 11997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->index = deque->leftindex; 12007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(deque); 12017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->deque = deque; 12027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->state = deque->state; 12037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->counter = deque->len; 12047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GC_Track(it); 12057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return (PyObject *)it; 12067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 12077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 12097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg) 12107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 12117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_VISIT(dio->deque); 12127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return 0; 12137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 12147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic void 12167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldequeiter_dealloc(dequeiterobject *dio) 12177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 12187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(dio->deque); 12197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GC_Del(dio); 12207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 12217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 12237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldequeiter_next(dequeiterobject *it) 12247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 12257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 12267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it->deque->state != it->state) { 12287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->counter = 0; 12297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_RuntimeError, 12307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "deque mutated during iteration"); 12317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 12327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 12337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it->counter == 0) 12347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 12357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (!(it->b == it->deque->rightblock && 12367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->index > it->deque->rightindex)); 12377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = it->b->data[it->index]; 12397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->index++; 12407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->counter--; 12417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it->index == BLOCKLEN && it->counter > 0) { 12427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (it->b->rightlink != NULL); 12437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->b = it->b->rightlink; 12447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->index = 0; 12457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 12467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(item); 12477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return item; 12487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 12497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 12517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldequeiter_len(dequeiterobject *it) 12527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 12537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyInt_FromLong(it->counter); 12547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 12557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); 12577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyMethodDef dequeiter_methods[] = { 12597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc}, 12607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {NULL, NULL} /* sentinel */ 12617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 12627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyTypeObject dequeiter_type = { 12647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyVarObject_HEAD_INIT(NULL, 0) 12657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "deque_iterator", /* tp_name */ 12667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel sizeof(dequeiterobject), /* tp_basicsize */ 12677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_itemsize */ 12687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* methods */ 12697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (destructor)dequeiter_dealloc, /* tp_dealloc */ 12707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_print */ 12717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_getattr */ 12727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_setattr */ 12737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_compare */ 12747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_repr */ 12757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_number */ 12767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_sequence */ 12777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_mapping */ 12787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_hash */ 12797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_call */ 12807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_str */ 12817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GenericGetAttr, /* tp_getattro */ 12827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_setattro */ 12837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_buffer */ 12847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 12857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_doc */ 12867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (traverseproc)dequeiter_traverse, /* tp_traverse */ 12877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_clear */ 12887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_richcompare */ 12897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_weaklistoffset */ 12907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_SelfIter, /* tp_iter */ 12917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (iternextfunc)dequeiter_next, /* tp_iternext */ 12927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel dequeiter_methods, /* tp_methods */ 12937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, 12947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 12957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/*********************** Deque Reverse Iterator **************************/ 12977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 12987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyTypeObject dequereviter_type; 12997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 13017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldeque_reviter(dequeobject *deque) 13027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 13037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel dequeiterobject *it; 13047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it = PyObject_GC_New(dequeiterobject, &dequereviter_type); 13067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it == NULL) 13077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 13087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->b = deque->rightblock; 13097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->index = deque->rightindex; 13107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(deque); 13117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->deque = deque; 13127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->state = deque->state; 13137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->counter = deque->len; 13147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GC_Track(it); 13157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return (PyObject *)it; 13167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 13177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 13197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldequereviter_next(dequeiterobject *it) 13207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 13217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *item; 13227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it->counter == 0) 13237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 13247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it->deque->state != it->state) { 13267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->counter = 0; 13277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_RuntimeError, 13287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "deque mutated during iteration"); 13297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 13307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 13317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (!(it->b == it->deque->leftblock && 13327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->index < it->deque->leftindex)); 13337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel item = it->b->data[it->index]; 13357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->index--; 13367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->counter--; 13377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (it->index == -1 && it->counter > 0) { 13387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel assert (it->b->leftlink != NULL); 13397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->b = it->b->leftlink; 13407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel it->index = BLOCKLEN - 1; 13417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 13427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(item); 13437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return item; 13447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 13457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyTypeObject dequereviter_type = { 13477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyVarObject_HEAD_INIT(NULL, 0) 13487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "deque_reverse_iterator", /* tp_name */ 13497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel sizeof(dequeiterobject), /* tp_basicsize */ 13507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_itemsize */ 13517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* methods */ 13527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (destructor)dequeiter_dealloc, /* tp_dealloc */ 13537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_print */ 13547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_getattr */ 13557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_setattr */ 13567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_compare */ 13577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_repr */ 13587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_number */ 13597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_sequence */ 13607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_mapping */ 13617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_hash */ 13627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_call */ 13637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_str */ 13647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GenericGetAttr, /* tp_getattro */ 13657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_setattro */ 13667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_buffer */ 13677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 13687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_doc */ 13697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (traverseproc)dequeiter_traverse, /* tp_traverse */ 13707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_clear */ 13717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_richcompare */ 13727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_weaklistoffset */ 13737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_SelfIter, /* tp_iter */ 13747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (iternextfunc)dequereviter_next, /* tp_iternext */ 13757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel dequeiter_methods, /* tp_methods */ 13767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, 13777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 13787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* defaultdict type *********************************************************/ 13807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieltypedef struct { 13827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyDictObject dict; 13837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *default_factory; 13847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} defdictobject; 13857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyTypeObject defdict_type; /* Forward */ 13877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(defdict_missing_doc, 13897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\ 13907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if self.default_factory is None: raise KeyError((key,))\n\ 13917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel self[key] = value = self.default_factory()\n\ 13927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return value\n\ 13937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"); 13947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 13957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 13967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldefdict_missing(defdictobject *dd, PyObject *key) 13977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 13987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *factory = dd->default_factory; 13997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *value; 14007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (factory == NULL || factory == Py_None) { 14017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* XXX Call dict.__missing__(key) */ 14027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *tup; 14037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel tup = PyTuple_Pack(1, key); 14047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!tup) return NULL; 14057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetObject(PyExc_KeyError, tup); 14067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(tup); 14077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 14087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 14097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel value = PyEval_CallObject(factory, NULL); 14107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (value == NULL) 14117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return value; 14127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyObject_SetItem((PyObject *)dd, key, value) < 0) { 14137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(value); 14147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 14157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 14167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return value; 14177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 14187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D."); 14207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 14227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldefdict_copy(defdictobject *dd) 14237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 14247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* This calls the object's class. That only works for subclasses 14257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel whose class constructor has the same signature. Subclasses that 14267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel define a different constructor signature must override copy(). 14277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel */ 14287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (dd->default_factory == NULL) 14307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL); 14317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), 14327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel dd->default_factory, dd, NULL); 14337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 14347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 14367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldefdict_reduce(defdictobject *dd) 14377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 14387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* __reduce__ must return a 5-tuple as follows: 14397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel - factory function 14417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel - tuple of args for the factory function 14427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel - additional state (here None) 14437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel - sequence iterator (here None) 14447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel - dictionary iterator (yielding successive (key, value) pairs 14457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel This API is used by pickle.py and copy.py. 14477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel For this to be useful with pickle.py, the default_factory 14497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel must be picklable; e.g., None, a built-in, or a global 14507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel function in a module or package. 14517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Both shallow and deep copying are supported, but for deep 14537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel copying, the default_factory must be deep-copyable; e.g. None, 14547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel or a built-in (functions are not copyable at this time). 14557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel This only works for subclasses as long as their constructor 14577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel signature is compatible; the first argument must be the 14587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel optional default_factory, defaulting to None. 14597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel */ 14607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *args; 14617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *items; 14627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *result; 14637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (dd->default_factory == NULL || dd->default_factory == Py_None) 14647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel args = PyTuple_New(0); 14657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 14667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel args = PyTuple_Pack(1, dd->default_factory); 14677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (args == NULL) 14687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 14697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel items = PyObject_CallMethod((PyObject *)dd, "iteritems", "()"); 14707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (items == NULL) { 14717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(args); 14727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 14737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 14747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = PyTuple_Pack(5, Py_TYPE(dd), args, 14757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_None, Py_None, items); 14767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(items); 14777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(args); 14787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return result; 14797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 14807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyMethodDef defdict_methods[] = { 14827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"__missing__", (PyCFunction)defdict_missing, METH_O, 14837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdict_missing_doc}, 14847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"copy", (PyCFunction)defdict_copy, METH_NOARGS, 14857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdict_copy_doc}, 14867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS, 14877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdict_copy_doc}, 14887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS, 14897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel reduce_doc}, 14907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {NULL} 14917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 14927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 14937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyMemberDef defdict_members[] = { 14947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {"default_factory", T_OBJECT, 14957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel offsetof(defdictobject, default_factory), 0, 14967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyDoc_STR("Factory for default value called by __missing__().")}, 14977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel {NULL} 14987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 14997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 15007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic void 15017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldefdict_dealloc(defdictobject *dd) 15027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 15037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_CLEAR(dd->default_factory); 15047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyDict_Type.tp_dealloc((PyObject *)dd); 15057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 15067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 15077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 15087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldefdict_print(defdictobject *dd, FILE *fp, int flags) 15097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 15107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int sts; 15117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_BEGIN_ALLOW_THREADS 15127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fprintf(fp, "defaultdict("); 15137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_END_ALLOW_THREADS 15147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (dd->default_factory == NULL) { 15157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_BEGIN_ALLOW_THREADS 15167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fprintf(fp, "None"); 15177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_END_ALLOW_THREADS 15187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } else { 15197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_Print(dd->default_factory, fp, 0); 15207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 15217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_BEGIN_ALLOW_THREADS 15227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fprintf(fp, ", "); 15237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_END_ALLOW_THREADS 15247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel sts = PyDict_Type.tp_print((PyObject *)dd, fp, 0); 15257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_BEGIN_ALLOW_THREADS 15267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel fprintf(fp, ")"); 15277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_END_ALLOW_THREADS 15287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return sts; 15297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 15307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 15317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyObject * 15327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldefdict_repr(defdictobject *dd) 15337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 15347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *defrepr; 15357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *baserepr; 15367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *result; 15377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel baserepr = PyDict_Type.tp_repr((PyObject *)dd); 15387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (baserepr == NULL) 15397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 15407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (dd->default_factory == NULL) 15417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defrepr = PyString_FromString("None"); 15427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 15437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel { 15447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int status = Py_ReprEnter(dd->default_factory); 15457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (status != 0) { 15467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (status < 0) { 15477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(baserepr); 15487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 15497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 15507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defrepr = PyString_FromString("..."); 15517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 15527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else 15537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defrepr = PyObject_Repr(dd->default_factory); 15547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ReprLeave(dd->default_factory); 15557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 15567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (defrepr == NULL) { 15577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(baserepr); 15587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return NULL; 15597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 15607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = PyString_FromFormat("defaultdict(%s, %s)", 15617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyString_AS_STRING(defrepr), 15627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyString_AS_STRING(baserepr)); 15637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(defrepr); 15647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(baserepr); 15657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return result; 15667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 15677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 15687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 15697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldefdict_traverse(PyObject *self, visitproc visit, void *arg) 15707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 15717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_VISIT(((defdictobject *)self)->default_factory); 15727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyDict_Type.tp_traverse(self, visit, arg); 15737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 15747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 15757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 15767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldefdict_tp_clear(defdictobject *dd) 15777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 15787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_CLEAR(dd->default_factory); 15797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return PyDict_Type.tp_clear((PyObject *)dd); 15807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 15817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 15827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic int 15837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanieldefdict_init(PyObject *self, PyObject *args, PyObject *kwds) 15847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 15857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdictobject *dd = (defdictobject *)self; 15867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *olddefault = dd->default_factory; 15877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *newdefault = NULL; 15887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *newargs; 15897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel int result; 15907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (args == NULL || !PyTuple_Check(args)) 15917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel newargs = PyTuple_New(0); 15927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel else { 15937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_ssize_t n = PyTuple_GET_SIZE(args); 15947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (n > 0) { 15957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel newdefault = PyTuple_GET_ITEM(args, 0); 15967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (!PyCallable_Check(newdefault) && newdefault != Py_None) { 15977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyErr_SetString(PyExc_TypeError, 15987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "first argument must be callable"); 15997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 16007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 16017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 16027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel newargs = PySequence_GetSlice(args, 1, n); 16037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel } 16047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (newargs == NULL) 16057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return -1; 16067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XINCREF(newdefault); 16077eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel dd->default_factory = newdefault; 16087eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel result = PyDict_Type.tp_init(self, newargs, kwds); 16097eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_DECREF(newargs); 16107eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_XDECREF(olddefault); 16117eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return result; 16127eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 16137eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16147eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(defdict_doc, 16157eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"defaultdict(default_factory[, ...]) --> dict with default factory\n\ 16167eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel\n\ 16177eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielThe default factory is called without arguments to produce\n\ 16187eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniela new value when a key is not present, in __getitem__ only.\n\ 16197eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielA defaultdict compares equal to a dict with the same items.\n\ 16207eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielAll remaining arguments are treated the same as if they were\n\ 16217eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielpassed to the dict constructor, including keyword arguments.\n\ 16227eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"); 16237eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16247eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* See comment in xxsubtype.c */ 16257eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel#define DEFERRED_ADDRESS(ADDR) 0 16267eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16277eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielstatic PyTypeObject defdict_type = { 16287eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0) 16297eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel "collections.defaultdict", /* tp_name */ 16307eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel sizeof(defdictobject), /* tp_basicsize */ 16317eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_itemsize */ 16327eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel /* methods */ 16337eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (destructor)defdict_dealloc, /* tp_dealloc */ 16347eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (printfunc)defdict_print, /* tp_print */ 16357eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_getattr */ 16367eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_setattr */ 16377eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_compare */ 16387eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (reprfunc)defdict_repr, /* tp_repr */ 16397eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_number */ 16407eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_sequence */ 16417eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_mapping */ 16427eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_hash */ 16437eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_call */ 16447eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_str */ 16457eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GenericGetAttr, /* tp_getattro */ 16467eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_setattro */ 16477eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_as_buffer */ 16487eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC | 16497eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */ 16507eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdict_doc, /* tp_doc */ 16517eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdict_traverse, /* tp_traverse */ 16527eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel (inquiry)defdict_tp_clear, /* tp_clear */ 16537eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_richcompare */ 16547eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_weaklistoffset*/ 16557eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_iter */ 16567eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_iternext */ 16577eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdict_methods, /* tp_methods */ 16587eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdict_members, /* tp_members */ 16597eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_getset */ 16607eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */ 16617eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_dict */ 16627eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_descr_get */ 16637eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_descr_set */ 16647eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_dictoffset */ 16657eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdict_init, /* tp_init */ 16667eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyType_GenericAlloc, /* tp_alloc */ 16677eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 0, /* tp_new */ 16687eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject_GC_Del, /* tp_free */ 16697eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel}; 16707eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16717eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel/* module level code ********************************************************/ 16727eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16737eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyDoc_STRVAR(module_doc, 16747eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"High performance data structures.\n\ 16757eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel- deque: ordered collection accessible from endpoints only\n\ 16767eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel- defaultdict: dict subclass with a default value factory\n\ 16777eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel"); 16787eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16797eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielPyMODINIT_FUNC 16807eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDanielinit_collections(void) 16817eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel{ 16827eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyObject *m; 16837eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16847eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel m = Py_InitModule3("_collections", NULL, module_doc); 16857eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (m == NULL) 16867eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return; 16877eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16887eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyType_Ready(&deque_type) < 0) 16897eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return; 16907eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(&deque_type); 16917eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyModule_AddObject(m, "deque", (PyObject *)&deque_type); 16927eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16937eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel defdict_type.tp_base = &PyDict_Type; 16947eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyType_Ready(&defdict_type) < 0) 16957eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return; 16967eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel Py_INCREF(&defdict_type); 16977eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type); 16987eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 16997eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyType_Ready(&dequeiter_type) < 0) 17007eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return; 17017eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 17027eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel if (PyType_Ready(&dequereviter_type) < 0) 17037eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return; 17047eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel 17057eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel return; 17067eb75bccb5dacb658c63db1a9a980950c3d54d42Daryl McDaniel} 1707