+++ /dev/null
-#include "Python.h"\r
-#include "structmember.h"\r
-\r
-/* collections module implementation of a deque() datatype\r
- Written and maintained by Raymond D. Hettinger <python@rcn.com>\r
- Copyright (c) 2004 Python Software Foundation.\r
- All rights reserved.\r
-*/\r
-\r
-/* The block length may be set to any number over 1. Larger numbers\r
- * reduce the number of calls to the memory allocator, give faster\r
- * indexing and rotation, and reduce the link::data overhead ratio.\r
- *\r
- * Ideally, the block length will be set to two less than some\r
- * multiple of the cache-line length (so that the full block\r
- * including the leftlink and rightlink will fit neatly into\r
- * cache lines).\r
- */\r
-\r
-#define BLOCKLEN 62\r
-#define CENTER ((BLOCKLEN - 1) / 2)\r
-\r
-/* A `dequeobject` is composed of a doubly-linked list of `block` nodes.\r
- * This list is not circular (the leftmost block has leftlink==NULL,\r
- * and the rightmost block has rightlink==NULL). A deque d's first\r
- * element is at d.leftblock[leftindex] and its last element is at\r
- * d.rightblock[rightindex]; note that, unlike as for Python slice\r
- * indices, these indices are inclusive on both ends. By being inclusive\r
- * on both ends, algorithms for left and right operations become\r
- * symmetrical which simplifies the design.\r
- *\r
- * The list of blocks is never empty, so d.leftblock and d.rightblock\r
- * are never equal to NULL.\r
- *\r
- * The indices, d.leftindex and d.rightindex are always in the range\r
- * 0 <= index < BLOCKLEN.\r
- * Their exact relationship is:\r
- * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex.\r
- *\r
- * Empty deques have d.len == 0; d.leftblock==d.rightblock;\r
- * d.leftindex == CENTER+1; and d.rightindex == CENTER.\r
- * Checking for d.len == 0 is the intended way to see whether d is empty.\r
- *\r
- * Whenever d.leftblock == d.rightblock,\r
- * d.leftindex + d.len - 1 == d.rightindex.\r
- *\r
- * However, when d.leftblock != d.rightblock, d.leftindex and d.rightindex\r
- * become indices into distinct blocks and either may be larger than the\r
- * other.\r
- */\r
-\r
-typedef struct BLOCK {\r
- PyObject *data[BLOCKLEN];\r
- struct BLOCK *rightlink;\r
- struct BLOCK *leftlink;\r
-} block;\r
-\r
-#define MAXFREEBLOCKS 10\r
-static Py_ssize_t numfreeblocks = 0;\r
-static block *freeblocks[MAXFREEBLOCKS];\r
-\r
-static block *\r
-newblock(block *leftlink, block *rightlink, Py_ssize_t len) {\r
- block *b;\r
- /* To prevent len from overflowing PY_SSIZE_T_MAX on 32-bit machines, we\r
- * refuse to allocate new blocks if the current len is nearing overflow. */\r
- if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) {\r
- PyErr_SetString(PyExc_OverflowError,\r
- "cannot add more blocks to the deque");\r
- return NULL;\r
- }\r
- if (numfreeblocks) {\r
- numfreeblocks -= 1;\r
- b = freeblocks[numfreeblocks];\r
- } else {\r
- b = PyMem_Malloc(sizeof(block));\r
- if (b == NULL) {\r
- PyErr_NoMemory();\r
- return NULL;\r
- }\r
- }\r
- b->leftlink = leftlink;\r
- b->rightlink = rightlink;\r
- return b;\r
-}\r
-\r
-static void\r
-freeblock(block *b)\r
-{\r
- if (numfreeblocks < MAXFREEBLOCKS) {\r
- freeblocks[numfreeblocks] = b;\r
- numfreeblocks++;\r
- } else {\r
- PyMem_Free(b);\r
- }\r
-}\r
-\r
-typedef struct {\r
- PyObject_HEAD\r
- block *leftblock;\r
- block *rightblock;\r
- Py_ssize_t leftindex; /* in range(BLOCKLEN) */\r
- Py_ssize_t rightindex; /* in range(BLOCKLEN) */\r
- Py_ssize_t len;\r
- long state; /* incremented whenever the indices move */\r
- Py_ssize_t maxlen;\r
- PyObject *weakreflist; /* List of weak references */\r
-} dequeobject;\r
-\r
-/* The deque's size limit is d.maxlen. The limit can be zero or positive.\r
- * If there is no limit, then d.maxlen == -1.\r
- *\r
- * After an item is added to a deque, we check to see if the size has grown past\r
- * the limit. If it has, we get the size back down to the limit by popping an\r
- * item off of the opposite end. The methods that can trigger this are append(),\r
- * appendleft(), extend(), and extendleft().\r
- */\r
-\r
-#define TRIM(d, popfunction) \\r
- if (d->maxlen != -1 && d->len > d->maxlen) { \\r
- PyObject *rv = popfunction(d, NULL); \\r
- assert(rv != NULL && d->len <= d->maxlen); \\r
- Py_DECREF(rv); \\r
- }\r
-\r
-static PyTypeObject deque_type;\r
-\r
-static PyObject *\r
-deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)\r
-{\r
- dequeobject *deque;\r
- block *b;\r
-\r
- /* create dequeobject structure */\r
- deque = (dequeobject *)type->tp_alloc(type, 0);\r
- if (deque == NULL)\r
- return NULL;\r
-\r
- b = newblock(NULL, NULL, 0);\r
- if (b == NULL) {\r
- Py_DECREF(deque);\r
- return NULL;\r
- }\r
-\r
- assert(BLOCKLEN >= 2);\r
- deque->leftblock = b;\r
- deque->rightblock = b;\r
- deque->leftindex = CENTER + 1;\r
- deque->rightindex = CENTER;\r
- deque->len = 0;\r
- deque->state = 0;\r
- deque->weakreflist = NULL;\r
- deque->maxlen = -1;\r
-\r
- return (PyObject *)deque;\r
-}\r
-\r
-static PyObject *\r
-deque_pop(dequeobject *deque, PyObject *unused)\r
-{\r
- PyObject *item;\r
- block *prevblock;\r
-\r
- if (deque->len == 0) {\r
- PyErr_SetString(PyExc_IndexError, "pop from an empty deque");\r
- return NULL;\r
- }\r
- item = deque->rightblock->data[deque->rightindex];\r
- deque->rightindex--;\r
- deque->len--;\r
- deque->state++;\r
-\r
- if (deque->rightindex == -1) {\r
- if (deque->len == 0) {\r
- assert(deque->leftblock == deque->rightblock);\r
- assert(deque->leftindex == deque->rightindex+1);\r
- /* re-center instead of freeing a block */\r
- deque->leftindex = CENTER + 1;\r
- deque->rightindex = CENTER;\r
- } else {\r
- prevblock = deque->rightblock->leftlink;\r
- assert(deque->leftblock != deque->rightblock);\r
- freeblock(deque->rightblock);\r
- prevblock->rightlink = NULL;\r
- deque->rightblock = prevblock;\r
- deque->rightindex = BLOCKLEN - 1;\r
- }\r
- }\r
- return item;\r
-}\r
-\r
-PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");\r
-\r
-static PyObject *\r
-deque_popleft(dequeobject *deque, PyObject *unused)\r
-{\r
- PyObject *item;\r
- block *prevblock;\r
-\r
- if (deque->len == 0) {\r
- PyErr_SetString(PyExc_IndexError, "pop from an empty deque");\r
- return NULL;\r
- }\r
- assert(deque->leftblock != NULL);\r
- item = deque->leftblock->data[deque->leftindex];\r
- deque->leftindex++;\r
- deque->len--;\r
- deque->state++;\r
-\r
- if (deque->leftindex == BLOCKLEN) {\r
- if (deque->len == 0) {\r
- assert(deque->leftblock == deque->rightblock);\r
- assert(deque->leftindex == deque->rightindex+1);\r
- /* re-center instead of freeing a block */\r
- deque->leftindex = CENTER + 1;\r
- deque->rightindex = CENTER;\r
- } else {\r
- assert(deque->leftblock != deque->rightblock);\r
- prevblock = deque->leftblock->rightlink;\r
- freeblock(deque->leftblock);\r
- assert(prevblock != NULL);\r
- prevblock->leftlink = NULL;\r
- deque->leftblock = prevblock;\r
- deque->leftindex = 0;\r
- }\r
- }\r
- return item;\r
-}\r
-\r
-PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");\r
-\r
-static PyObject *\r
-deque_append(dequeobject *deque, PyObject *item)\r
-{\r
- deque->state++;\r
- if (deque->rightindex == BLOCKLEN-1) {\r
- block *b = newblock(deque->rightblock, NULL, deque->len);\r
- if (b == NULL)\r
- return NULL;\r
- assert(deque->rightblock->rightlink == NULL);\r
- deque->rightblock->rightlink = b;\r
- deque->rightblock = b;\r
- deque->rightindex = -1;\r
- }\r
- Py_INCREF(item);\r
- deque->len++;\r
- deque->rightindex++;\r
- deque->rightblock->data[deque->rightindex] = item;\r
- TRIM(deque, deque_popleft);\r
- Py_RETURN_NONE;\r
-}\r
-\r
-PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");\r
-\r
-static PyObject *\r
-deque_appendleft(dequeobject *deque, PyObject *item)\r
-{\r
- deque->state++;\r
- if (deque->leftindex == 0) {\r
- block *b = newblock(NULL, deque->leftblock, deque->len);\r
- if (b == NULL)\r
- return NULL;\r
- assert(deque->leftblock->leftlink == NULL);\r
- deque->leftblock->leftlink = b;\r
- deque->leftblock = b;\r
- deque->leftindex = BLOCKLEN;\r
- }\r
- Py_INCREF(item);\r
- deque->len++;\r
- deque->leftindex--;\r
- deque->leftblock->data[deque->leftindex] = item;\r
- TRIM(deque, deque_pop);\r
- Py_RETURN_NONE;\r
-}\r
-\r
-PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");\r
-\r
-\r
-/* Run an iterator to exhaustion. Shortcut for\r
- the extend/extendleft methods when maxlen == 0. */\r
-static PyObject*\r
-consume_iterator(PyObject *it)\r
-{\r
- PyObject *item;\r
-\r
- while ((item = PyIter_Next(it)) != NULL) {\r
- Py_DECREF(item);\r
- }\r
- Py_DECREF(it);\r
- if (PyErr_Occurred())\r
- return NULL;\r
- Py_RETURN_NONE;\r
-}\r
-\r
-static PyObject *\r
-deque_extend(dequeobject *deque, PyObject *iterable)\r
-{\r
- PyObject *it, *item;\r
-\r
- /* Handle case where id(deque) == id(iterable) */\r
- if ((PyObject *)deque == iterable) {\r
- PyObject *result;\r
- PyObject *s = PySequence_List(iterable);\r
- if (s == NULL)\r
- return NULL;\r
- result = deque_extend(deque, s);\r
- Py_DECREF(s);\r
- return result;\r
- }\r
-\r
- it = PyObject_GetIter(iterable);\r
- if (it == NULL)\r
- return NULL;\r
-\r
- if (deque->maxlen == 0)\r
- return consume_iterator(it);\r
-\r
- while ((item = PyIter_Next(it)) != NULL) {\r
- deque->state++;\r
- if (deque->rightindex == BLOCKLEN-1) {\r
- block *b = newblock(deque->rightblock, NULL,\r
- deque->len);\r
- if (b == NULL) {\r
- Py_DECREF(item);\r
- Py_DECREF(it);\r
- return NULL;\r
- }\r
- assert(deque->rightblock->rightlink == NULL);\r
- deque->rightblock->rightlink = b;\r
- deque->rightblock = b;\r
- deque->rightindex = -1;\r
- }\r
- deque->len++;\r
- deque->rightindex++;\r
- deque->rightblock->data[deque->rightindex] = item;\r
- TRIM(deque, deque_popleft);\r
- }\r
- Py_DECREF(it);\r
- if (PyErr_Occurred())\r
- return NULL;\r
- Py_RETURN_NONE;\r
-}\r
-\r
-PyDoc_STRVAR(extend_doc,\r
-"Extend the right side of the deque with elements from the iterable");\r
-\r
-static PyObject *\r
-deque_extendleft(dequeobject *deque, PyObject *iterable)\r
-{\r
- PyObject *it, *item;\r
-\r
- /* Handle case where id(deque) == id(iterable) */\r
- if ((PyObject *)deque == iterable) {\r
- PyObject *result;\r
- PyObject *s = PySequence_List(iterable);\r
- if (s == NULL)\r
- return NULL;\r
- result = deque_extendleft(deque, s);\r
- Py_DECREF(s);\r
- return result;\r
- }\r
-\r
- it = PyObject_GetIter(iterable);\r
- if (it == NULL)\r
- return NULL;\r
-\r
- if (deque->maxlen == 0)\r
- return consume_iterator(it);\r
-\r
- while ((item = PyIter_Next(it)) != NULL) {\r
- deque->state++;\r
- if (deque->leftindex == 0) {\r
- block *b = newblock(NULL, deque->leftblock,\r
- deque->len);\r
- if (b == NULL) {\r
- Py_DECREF(item);\r
- Py_DECREF(it);\r
- return NULL;\r
- }\r
- assert(deque->leftblock->leftlink == NULL);\r
- deque->leftblock->leftlink = b;\r
- deque->leftblock = b;\r
- deque->leftindex = BLOCKLEN;\r
- }\r
- deque->len++;\r
- deque->leftindex--;\r
- deque->leftblock->data[deque->leftindex] = item;\r
- TRIM(deque, deque_pop);\r
- }\r
- Py_DECREF(it);\r
- if (PyErr_Occurred())\r
- return NULL;\r
- Py_RETURN_NONE;\r
-}\r
-\r
-PyDoc_STRVAR(extendleft_doc,\r
-"Extend the left side of the deque with elements from the iterable");\r
-\r
-static PyObject *\r
-deque_inplace_concat(dequeobject *deque, PyObject *other)\r
-{\r
- PyObject *result;\r
-\r
- result = deque_extend(deque, other);\r
- if (result == NULL)\r
- return result;\r
- Py_DECREF(result);\r
- Py_INCREF(deque);\r
- return (PyObject *)deque;\r
-}\r
-\r
-static int\r
-_deque_rotate(dequeobject *deque, Py_ssize_t n)\r
-{\r
- Py_ssize_t m, len=deque->len, halflen=len>>1;\r
-\r
- if (len <= 1)\r
- return 0;\r
- if (n > halflen || n < -halflen) {\r
- n %= len;\r
- if (n > halflen)\r
- n -= len;\r
- else if (n < -halflen)\r
- n += len;\r
- }\r
- assert(len > 1);\r
- assert(-halflen <= n && n <= halflen);\r
-\r
- deque->state++;\r
- while (n > 0) {\r
- if (deque->leftindex == 0) {\r
- block *b = newblock(NULL, deque->leftblock, len);\r
- if (b == NULL)\r
- return -1;\r
- assert(deque->leftblock->leftlink == NULL);\r
- deque->leftblock->leftlink = b;\r
- deque->leftblock = b;\r
- deque->leftindex = BLOCKLEN;\r
- }\r
- assert(deque->leftindex > 0);\r
-\r
- m = n;\r
- if (m > deque->rightindex + 1)\r
- m = deque->rightindex + 1;\r
- if (m > deque->leftindex)\r
- m = deque->leftindex;\r
- assert (m > 0 && m <= len);\r
- memcpy(&deque->leftblock->data[deque->leftindex - m],\r
- &deque->rightblock->data[deque->rightindex + 1 - m],\r
- m * sizeof(PyObject *));\r
- deque->rightindex -= m;\r
- deque->leftindex -= m;\r
- n -= m;\r
-\r
- if (deque->rightindex == -1) {\r
- block *prevblock = deque->rightblock->leftlink;\r
- assert(deque->rightblock != NULL);\r
- assert(deque->leftblock != deque->rightblock);\r
- freeblock(deque->rightblock);\r
- prevblock->rightlink = NULL;\r
- deque->rightblock = prevblock;\r
- deque->rightindex = BLOCKLEN - 1;\r
- }\r
- }\r
- while (n < 0) {\r
- if (deque->rightindex == BLOCKLEN - 1) {\r
- block *b = newblock(deque->rightblock, NULL, len);\r
- if (b == NULL)\r
- return -1;\r
- assert(deque->rightblock->rightlink == NULL);\r
- deque->rightblock->rightlink = b;\r
- deque->rightblock = b;\r
- deque->rightindex = -1;\r
- }\r
- assert (deque->rightindex < BLOCKLEN - 1);\r
-\r
- m = -n;\r
- if (m > BLOCKLEN - deque->leftindex)\r
- m = BLOCKLEN - deque->leftindex;\r
- if (m > BLOCKLEN - 1 - deque->rightindex)\r
- m = BLOCKLEN - 1 - deque->rightindex;\r
- assert (m > 0 && m <= len);\r
- memcpy(&deque->rightblock->data[deque->rightindex + 1],\r
- &deque->leftblock->data[deque->leftindex],\r
- m * sizeof(PyObject *));\r
- deque->leftindex += m;\r
- deque->rightindex += m;\r
- n += m;\r
-\r
- if (deque->leftindex == BLOCKLEN) {\r
- block *nextblock = deque->leftblock->rightlink;\r
- assert(deque->leftblock != deque->rightblock);\r
- freeblock(deque->leftblock);\r
- assert(nextblock != NULL);\r
- nextblock->leftlink = NULL;\r
- deque->leftblock = nextblock;\r
- deque->leftindex = 0;\r
- }\r
- }\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-deque_rotate(dequeobject *deque, PyObject *args)\r
-{\r
- Py_ssize_t n=1;\r
-\r
- if (!PyArg_ParseTuple(args, "|n:rotate", &n))\r
- return NULL;\r
- if (_deque_rotate(deque, n) == 0)\r
- Py_RETURN_NONE;\r
- return NULL;\r
-}\r
-\r
-PyDoc_STRVAR(rotate_doc,\r
-"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");\r
-\r
-static PyObject *\r
-deque_reverse(dequeobject *deque, PyObject *unused)\r
-{\r
- block *leftblock = deque->leftblock;\r
- block *rightblock = deque->rightblock;\r
- Py_ssize_t leftindex = deque->leftindex;\r
- Py_ssize_t rightindex = deque->rightindex;\r
- Py_ssize_t n = (deque->len)/2;\r
- Py_ssize_t i;\r
- PyObject *tmp;\r
-\r
- for (i=0 ; i<n ; i++) {\r
- /* Validate that pointers haven't met in the middle */\r
- assert(leftblock != rightblock || leftindex < rightindex);\r
-\r
- /* Swap */\r
- tmp = leftblock->data[leftindex];\r
- leftblock->data[leftindex] = rightblock->data[rightindex];\r
- rightblock->data[rightindex] = tmp;\r
-\r
- /* Advance left block/index pair */\r
- leftindex++;\r
- if (leftindex == BLOCKLEN) {\r
- if (leftblock->rightlink == NULL)\r
- break;\r
- leftblock = leftblock->rightlink;\r
- leftindex = 0;\r
- }\r
-\r
- /* Step backwards with the right block/index pair */\r
- rightindex--;\r
- if (rightindex == -1) {\r
- if (rightblock->leftlink == NULL)\r
- break;\r
- rightblock = rightblock->leftlink;\r
- rightindex = BLOCKLEN - 1;\r
- }\r
- }\r
- Py_RETURN_NONE;\r
-}\r
-\r
-PyDoc_STRVAR(reverse_doc,\r
-"D.reverse() -- reverse *IN PLACE*");\r
-\r
-static PyObject *\r
-deque_count(dequeobject *deque, PyObject *v)\r
-{\r
- block *leftblock = deque->leftblock;\r
- Py_ssize_t leftindex = deque->leftindex;\r
- Py_ssize_t n = deque->len;\r
- Py_ssize_t i;\r
- Py_ssize_t count = 0;\r
- PyObject *item;\r
- long start_state = deque->state;\r
- int cmp;\r
-\r
- for (i=0 ; i<n ; i++) {\r
- item = leftblock->data[leftindex];\r
- cmp = PyObject_RichCompareBool(item, v, Py_EQ);\r
- if (cmp > 0)\r
- count++;\r
- else if (cmp < 0)\r
- return NULL;\r
-\r
- if (start_state != deque->state) {\r
- PyErr_SetString(PyExc_RuntimeError,\r
- "deque mutated during iteration");\r
- return NULL;\r
- }\r
-\r
- /* Advance left block/index pair */\r
- leftindex++;\r
- if (leftindex == BLOCKLEN) {\r
- if (leftblock->rightlink == NULL) /* can occur when i==n-1 */\r
- break;\r
- leftblock = leftblock->rightlink;\r
- leftindex = 0;\r
- }\r
- }\r
- return PyInt_FromSsize_t(count);\r
-}\r
-\r
-PyDoc_STRVAR(count_doc,\r
-"D.count(value) -> integer -- return number of occurrences of value");\r
-\r
-static Py_ssize_t\r
-deque_len(dequeobject *deque)\r
-{\r
- return deque->len;\r
-}\r
-\r
-static PyObject *\r
-deque_remove(dequeobject *deque, PyObject *value)\r
-{\r
- Py_ssize_t i, n=deque->len;\r
-\r
- for (i=0 ; i<n ; i++) {\r
- PyObject *item = deque->leftblock->data[deque->leftindex];\r
- int cmp = PyObject_RichCompareBool(item, value, Py_EQ);\r
-\r
- if (deque->len != n) {\r
- PyErr_SetString(PyExc_IndexError,\r
- "deque mutated during remove().");\r
- return NULL;\r
- }\r
- if (cmp > 0) {\r
- PyObject *tgt = deque_popleft(deque, NULL);\r
- assert (tgt != NULL);\r
- if (_deque_rotate(deque, i))\r
- return NULL;\r
- Py_DECREF(tgt);\r
- Py_RETURN_NONE;\r
- }\r
- else if (cmp < 0) {\r
- _deque_rotate(deque, i);\r
- return NULL;\r
- }\r
- _deque_rotate(deque, -1);\r
- }\r
- PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");\r
- return NULL;\r
-}\r
-\r
-PyDoc_STRVAR(remove_doc,\r
-"D.remove(value) -- remove first occurrence of value.");\r
-\r
-static void\r
-deque_clear(dequeobject *deque)\r
-{\r
- PyObject *item;\r
-\r
- while (deque->len) {\r
- item = deque_pop(deque, NULL);\r
- assert (item != NULL);\r
- Py_DECREF(item);\r
- }\r
- assert(deque->leftblock == deque->rightblock &&\r
- deque->leftindex - 1 == deque->rightindex &&\r
- deque->len == 0);\r
-}\r
-\r
-static PyObject *\r
-deque_item(dequeobject *deque, Py_ssize_t i)\r
-{\r
- block *b;\r
- PyObject *item;\r
- Py_ssize_t n, index=i;\r
-\r
- if (i < 0 || i >= deque->len) {\r
- PyErr_SetString(PyExc_IndexError,\r
- "deque index out of range");\r
- return NULL;\r
- }\r
-\r
- if (i == 0) {\r
- i = deque->leftindex;\r
- b = deque->leftblock;\r
- } else if (i == deque->len - 1) {\r
- i = deque->rightindex;\r
- b = deque->rightblock;\r
- } else {\r
- i += deque->leftindex;\r
- n = i / BLOCKLEN;\r
- i %= BLOCKLEN;\r
- if (index < (deque->len >> 1)) {\r
- b = deque->leftblock;\r
- while (n--)\r
- b = b->rightlink;\r
- } else {\r
- n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;\r
- b = deque->rightblock;\r
- while (n--)\r
- b = b->leftlink;\r
- }\r
- }\r
- item = b->data[i];\r
- Py_INCREF(item);\r
- return item;\r
-}\r
-\r
-/* delitem() implemented in terms of rotate for simplicity and reasonable\r
- performance near the end points. If for some reason this method becomes\r
- popular, it is not hard to re-implement this using direct data movement\r
- (similar to code in list slice assignment) and achieve a two or threefold\r
- performance boost.\r
-*/\r
-\r
-static int\r
-deque_del_item(dequeobject *deque, Py_ssize_t i)\r
-{\r
- PyObject *item;\r
- int rv;\r
-\r
- assert (i >= 0 && i < deque->len);\r
- if (_deque_rotate(deque, -i))\r
- return -1;\r
- item = deque_popleft(deque, NULL);\r
- rv = _deque_rotate(deque, i);\r
- assert (item != NULL);\r
- Py_DECREF(item);\r
- return rv;\r
-}\r
-\r
-static int\r
-deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)\r
-{\r
- PyObject *old_value;\r
- block *b;\r
- Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i;\r
-\r
- if (i < 0 || i >= len) {\r
- PyErr_SetString(PyExc_IndexError,\r
- "deque index out of range");\r
- return -1;\r
- }\r
- if (v == NULL)\r
- return deque_del_item(deque, i);\r
-\r
- i += deque->leftindex;\r
- n = i / BLOCKLEN;\r
- i %= BLOCKLEN;\r
- if (index <= halflen) {\r
- b = deque->leftblock;\r
- while (n--)\r
- b = b->rightlink;\r
- } else {\r
- n = (deque->leftindex + len - 1) / BLOCKLEN - n;\r
- b = deque->rightblock;\r
- while (n--)\r
- b = b->leftlink;\r
- }\r
- Py_INCREF(v);\r
- old_value = b->data[i];\r
- b->data[i] = v;\r
- Py_DECREF(old_value);\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-deque_clearmethod(dequeobject *deque)\r
-{\r
- deque_clear(deque);\r
- Py_RETURN_NONE;\r
-}\r
-\r
-PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");\r
-\r
-static void\r
-deque_dealloc(dequeobject *deque)\r
-{\r
- PyObject_GC_UnTrack(deque);\r
- if (deque->weakreflist != NULL)\r
- PyObject_ClearWeakRefs((PyObject *) deque);\r
- if (deque->leftblock != NULL) {\r
- deque_clear(deque);\r
- assert(deque->leftblock != NULL);\r
- freeblock(deque->leftblock);\r
- }\r
- deque->leftblock = NULL;\r
- deque->rightblock = NULL;\r
- Py_TYPE(deque)->tp_free(deque);\r
-}\r
-\r
-static int\r
-deque_traverse(dequeobject *deque, visitproc visit, void *arg)\r
-{\r
- block *b;\r
- PyObject *item;\r
- Py_ssize_t index;\r
- Py_ssize_t indexlo = deque->leftindex;\r
-\r
- for (b = deque->leftblock; b != NULL; b = b->rightlink) {\r
- const Py_ssize_t indexhi = b == deque->rightblock ?\r
- deque->rightindex :\r
- BLOCKLEN - 1;\r
-\r
- for (index = indexlo; index <= indexhi; ++index) {\r
- item = b->data[index];\r
- Py_VISIT(item);\r
- }\r
- indexlo = 0;\r
- }\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-deque_copy(PyObject *deque)\r
-{\r
- if (((dequeobject *)deque)->maxlen == -1)\r
- return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);\r
- else\r
- return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",\r
- deque, ((dequeobject *)deque)->maxlen, NULL);\r
-}\r
-\r
-PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");\r
-\r
-static PyObject *\r
-deque_reduce(dequeobject *deque)\r
-{\r
- PyObject *dict, *result, *aslist;\r
-\r
- dict = PyObject_GetAttrString((PyObject *)deque, "__dict__");\r
- if (dict == NULL)\r
- PyErr_Clear();\r
- aslist = PySequence_List((PyObject *)deque);\r
- if (aslist == NULL) {\r
- Py_XDECREF(dict);\r
- return NULL;\r
- }\r
- if (dict == NULL) {\r
- if (deque->maxlen == -1)\r
- result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist);\r
- else\r
- result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen);\r
- } else {\r
- if (deque->maxlen == -1)\r
- result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict);\r
- else\r
- result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict);\r
- }\r
- Py_XDECREF(dict);\r
- Py_DECREF(aslist);\r
- return result;\r
-}\r
-\r
-PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");\r
-\r
-static PyObject *\r
-deque_repr(PyObject *deque)\r
-{\r
- PyObject *aslist, *result, *fmt;\r
- int i;\r
-\r
- i = Py_ReprEnter(deque);\r
- if (i != 0) {\r
- if (i < 0)\r
- return NULL;\r
- return PyString_FromString("[...]");\r
- }\r
-\r
- aslist = PySequence_List(deque);\r
- if (aslist == NULL) {\r
- Py_ReprLeave(deque);\r
- return NULL;\r
- }\r
- if (((dequeobject *)deque)->maxlen != -1)\r
- fmt = PyString_FromFormat("deque(%%r, maxlen=%zd)",\r
- ((dequeobject *)deque)->maxlen);\r
- else\r
- fmt = PyString_FromString("deque(%r)");\r
- if (fmt == NULL) {\r
- Py_DECREF(aslist);\r
- Py_ReprLeave(deque);\r
- return NULL;\r
- }\r
- result = PyString_Format(fmt, aslist);\r
- Py_DECREF(fmt);\r
- Py_DECREF(aslist);\r
- Py_ReprLeave(deque);\r
- return result;\r
-}\r
-\r
-static int\r
-deque_tp_print(PyObject *deque, FILE *fp, int flags)\r
-{\r
- PyObject *it, *item;\r
- char *emit = ""; /* No separator emitted on first pass */\r
- char *separator = ", ";\r
- int i;\r
-\r
- i = Py_ReprEnter(deque);\r
- if (i != 0) {\r
- if (i < 0)\r
- return i;\r
- Py_BEGIN_ALLOW_THREADS\r
- fputs("[...]", fp);\r
- Py_END_ALLOW_THREADS\r
- return 0;\r
- }\r
-\r
- it = PyObject_GetIter(deque);\r
- if (it == NULL)\r
- return -1;\r
-\r
- Py_BEGIN_ALLOW_THREADS\r
- fputs("deque([", fp);\r
- Py_END_ALLOW_THREADS\r
- while ((item = PyIter_Next(it)) != NULL) {\r
- Py_BEGIN_ALLOW_THREADS\r
- fputs(emit, fp);\r
- Py_END_ALLOW_THREADS\r
- emit = separator;\r
- if (PyObject_Print(item, fp, 0) != 0) {\r
- Py_DECREF(item);\r
- Py_DECREF(it);\r
- Py_ReprLeave(deque);\r
- return -1;\r
- }\r
- Py_DECREF(item);\r
- }\r
- Py_ReprLeave(deque);\r
- Py_DECREF(it);\r
- if (PyErr_Occurred())\r
- return -1;\r
-\r
- Py_BEGIN_ALLOW_THREADS\r
- if (((dequeobject *)deque)->maxlen == -1)\r
- fputs("])", fp);\r
- else\r
- fprintf(fp, "], maxlen=%" PY_FORMAT_SIZE_T "d)", ((dequeobject *)deque)->maxlen);\r
- Py_END_ALLOW_THREADS\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-deque_richcompare(PyObject *v, PyObject *w, int op)\r
-{\r
- PyObject *it1=NULL, *it2=NULL, *x, *y;\r
- Py_ssize_t vs, ws;\r
- int b, cmp=-1;\r
-\r
- if (!PyObject_TypeCheck(v, &deque_type) ||\r
- !PyObject_TypeCheck(w, &deque_type)) {\r
- Py_INCREF(Py_NotImplemented);\r
- return Py_NotImplemented;\r
- }\r
-\r
- /* Shortcuts */\r
- vs = ((dequeobject *)v)->len;\r
- ws = ((dequeobject *)w)->len;\r
- if (op == Py_EQ) {\r
- if (v == w)\r
- Py_RETURN_TRUE;\r
- if (vs != ws)\r
- Py_RETURN_FALSE;\r
- }\r
- if (op == Py_NE) {\r
- if (v == w)\r
- Py_RETURN_FALSE;\r
- if (vs != ws)\r
- Py_RETURN_TRUE;\r
- }\r
-\r
- /* Search for the first index where items are different */\r
- it1 = PyObject_GetIter(v);\r
- if (it1 == NULL)\r
- goto done;\r
- it2 = PyObject_GetIter(w);\r
- if (it2 == NULL)\r
- goto done;\r
- for (;;) {\r
- x = PyIter_Next(it1);\r
- if (x == NULL && PyErr_Occurred())\r
- goto done;\r
- y = PyIter_Next(it2);\r
- if (x == NULL || y == NULL)\r
- break;\r
- b = PyObject_RichCompareBool(x, y, Py_EQ);\r
- if (b == 0) {\r
- cmp = PyObject_RichCompareBool(x, y, op);\r
- Py_DECREF(x);\r
- Py_DECREF(y);\r
- goto done;\r
- }\r
- Py_DECREF(x);\r
- Py_DECREF(y);\r
- if (b == -1)\r
- goto done;\r
- }\r
- /* We reached the end of one deque or both */\r
- Py_XDECREF(x);\r
- Py_XDECREF(y);\r
- if (PyErr_Occurred())\r
- goto done;\r
- switch (op) {\r
- case Py_LT: cmp = y != NULL; break; /* if w was longer */\r
- case Py_LE: cmp = x == NULL; break; /* if v was not longer */\r
- case Py_EQ: cmp = x == y; break; /* if we reached the end of both */\r
- case Py_NE: cmp = x != y; break; /* if one deque continues */\r
- case Py_GT: cmp = x != NULL; break; /* if v was longer */\r
- case Py_GE: cmp = y == NULL; break; /* if w was not longer */\r
- }\r
-\r
-done:\r
- Py_XDECREF(it1);\r
- Py_XDECREF(it2);\r
- if (cmp == 1)\r
- Py_RETURN_TRUE;\r
- if (cmp == 0)\r
- Py_RETURN_FALSE;\r
- return NULL;\r
-}\r
-\r
-static int\r
-deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)\r
-{\r
- PyObject *iterable = NULL;\r
- PyObject *maxlenobj = NULL;\r
- Py_ssize_t maxlen = -1;\r
- char *kwlist[] = {"iterable", "maxlen", 0};\r
-\r
- if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj))\r
- return -1;\r
- if (maxlenobj != NULL && maxlenobj != Py_None) {\r
- maxlen = PyInt_AsSsize_t(maxlenobj);\r
- if (maxlen == -1 && PyErr_Occurred())\r
- return -1;\r
- if (maxlen < 0) {\r
- PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");\r
- return -1;\r
- }\r
- }\r
- deque->maxlen = maxlen;\r
- deque_clear(deque);\r
- if (iterable != NULL) {\r
- PyObject *rv = deque_extend(deque, iterable);\r
- if (rv == NULL)\r
- return -1;\r
- Py_DECREF(rv);\r
- }\r
- return 0;\r
-}\r
-\r
-static PyObject *\r
-deque_sizeof(dequeobject *deque, void *unused)\r
-{\r
- Py_ssize_t res;\r
- Py_ssize_t blocks;\r
-\r
- res = sizeof(dequeobject);\r
- blocks = (deque->leftindex + deque->len + BLOCKLEN - 1) / BLOCKLEN;\r
- assert(deque->leftindex + deque->len - 1 ==\r
- (blocks - 1) * BLOCKLEN + deque->rightindex);\r
- res += blocks * sizeof(block);\r
- return PyLong_FromSsize_t(res);\r
-}\r
-\r
-PyDoc_STRVAR(sizeof_doc,\r
-"D.__sizeof__() -- size of D in memory, in bytes");\r
-\r
-static PyObject *\r
-deque_get_maxlen(dequeobject *deque)\r
-{\r
- if (deque->maxlen == -1)\r
- Py_RETURN_NONE;\r
- return PyInt_FromSsize_t(deque->maxlen);\r
-}\r
-\r
-static PyGetSetDef deque_getset[] = {\r
- {"maxlen", (getter)deque_get_maxlen, (setter)NULL,\r
- "maximum size of a deque or None if unbounded"},\r
- {0}\r
-};\r
-\r
-static PySequenceMethods deque_as_sequence = {\r
- (lenfunc)deque_len, /* sq_length */\r
- 0, /* sq_concat */\r
- 0, /* sq_repeat */\r
- (ssizeargfunc)deque_item, /* sq_item */\r
- 0, /* sq_slice */\r
- (ssizeobjargproc)deque_ass_item, /* sq_ass_item */\r
- 0, /* sq_ass_slice */\r
- 0, /* sq_contains */\r
- (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */\r
- 0, /* sq_inplace_repeat */\r
-\r
-};\r
-\r
-/* deque object ********************************************************/\r
-\r
-static PyObject *deque_iter(dequeobject *deque);\r
-static PyObject *deque_reviter(dequeobject *deque);\r
-PyDoc_STRVAR(reversed_doc,\r
- "D.__reversed__() -- return a reverse iterator over the deque");\r
-\r
-static PyMethodDef deque_methods[] = {\r
- {"append", (PyCFunction)deque_append,\r
- METH_O, append_doc},\r
- {"appendleft", (PyCFunction)deque_appendleft,\r
- METH_O, appendleft_doc},\r
- {"clear", (PyCFunction)deque_clearmethod,\r
- METH_NOARGS, clear_doc},\r
- {"__copy__", (PyCFunction)deque_copy,\r
- METH_NOARGS, copy_doc},\r
- {"count", (PyCFunction)deque_count,\r
- METH_O, count_doc},\r
- {"extend", (PyCFunction)deque_extend,\r
- METH_O, extend_doc},\r
- {"extendleft", (PyCFunction)deque_extendleft,\r
- METH_O, extendleft_doc},\r
- {"pop", (PyCFunction)deque_pop,\r
- METH_NOARGS, pop_doc},\r
- {"popleft", (PyCFunction)deque_popleft,\r
- METH_NOARGS, popleft_doc},\r
- {"__reduce__", (PyCFunction)deque_reduce,\r
- METH_NOARGS, reduce_doc},\r
- {"remove", (PyCFunction)deque_remove,\r
- METH_O, remove_doc},\r
- {"__reversed__", (PyCFunction)deque_reviter,\r
- METH_NOARGS, reversed_doc},\r
- {"reverse", (PyCFunction)deque_reverse,\r
- METH_NOARGS, reverse_doc},\r
- {"rotate", (PyCFunction)deque_rotate,\r
- METH_VARARGS, rotate_doc},\r
- {"__sizeof__", (PyCFunction)deque_sizeof,\r
- METH_NOARGS, sizeof_doc},\r
- {NULL, NULL} /* sentinel */\r
-};\r
-\r
-PyDoc_STRVAR(deque_doc,\r
-"deque([iterable[, maxlen]]) --> deque object\n\\r
-\n\\r
-Build an ordered collection with optimized access from its endpoints.");\r
-\r
-static PyTypeObject deque_type = {\r
- PyVarObject_HEAD_INIT(NULL, 0)\r
- "collections.deque", /* tp_name */\r
- sizeof(dequeobject), /* tp_basicsize */\r
- 0, /* tp_itemsize */\r
- /* methods */\r
- (destructor)deque_dealloc, /* tp_dealloc */\r
- deque_tp_print, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- deque_repr, /* tp_repr */\r
- 0, /* tp_as_number */\r
- &deque_as_sequence, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- (hashfunc)PyObject_HashNotImplemented, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC |\r
- Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */\r
- deque_doc, /* tp_doc */\r
- (traverseproc)deque_traverse, /* tp_traverse */\r
- (inquiry)deque_clear, /* tp_clear */\r
- (richcmpfunc)deque_richcompare, /* tp_richcompare */\r
- offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/\r
- (getiterfunc)deque_iter, /* tp_iter */\r
- 0, /* tp_iternext */\r
- deque_methods, /* tp_methods */\r
- 0, /* tp_members */\r
- deque_getset, /* tp_getset */\r
- 0, /* tp_base */\r
- 0, /* tp_dict */\r
- 0, /* tp_descr_get */\r
- 0, /* tp_descr_set */\r
- 0, /* tp_dictoffset */\r
- (initproc)deque_init, /* tp_init */\r
- PyType_GenericAlloc, /* tp_alloc */\r
- deque_new, /* tp_new */\r
- PyObject_GC_Del, /* tp_free */\r
-};\r
-\r
-/*********************** Deque Iterator **************************/\r
-\r
-typedef struct {\r
- PyObject_HEAD\r
- Py_ssize_t index;\r
- block *b;\r
- dequeobject *deque;\r
- long state; /* state when the iterator is created */\r
- Py_ssize_t counter; /* number of items remaining for iteration */\r
-} dequeiterobject;\r
-\r
-static PyTypeObject dequeiter_type;\r
-\r
-static PyObject *\r
-deque_iter(dequeobject *deque)\r
-{\r
- dequeiterobject *it;\r
-\r
- it = PyObject_GC_New(dequeiterobject, &dequeiter_type);\r
- if (it == NULL)\r
- return NULL;\r
- it->b = deque->leftblock;\r
- it->index = deque->leftindex;\r
- Py_INCREF(deque);\r
- it->deque = deque;\r
- it->state = deque->state;\r
- it->counter = deque->len;\r
- PyObject_GC_Track(it);\r
- return (PyObject *)it;\r
-}\r
-\r
-static int\r
-dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)\r
-{\r
- Py_VISIT(dio->deque);\r
- return 0;\r
-}\r
-\r
-static void\r
-dequeiter_dealloc(dequeiterobject *dio)\r
-{\r
- Py_XDECREF(dio->deque);\r
- PyObject_GC_Del(dio);\r
-}\r
-\r
-static PyObject *\r
-dequeiter_next(dequeiterobject *it)\r
-{\r
- PyObject *item;\r
-\r
- if (it->deque->state != it->state) {\r
- it->counter = 0;\r
- PyErr_SetString(PyExc_RuntimeError,\r
- "deque mutated during iteration");\r
- return NULL;\r
- }\r
- if (it->counter == 0)\r
- return NULL;\r
- assert (!(it->b == it->deque->rightblock &&\r
- it->index > it->deque->rightindex));\r
-\r
- item = it->b->data[it->index];\r
- it->index++;\r
- it->counter--;\r
- if (it->index == BLOCKLEN && it->counter > 0) {\r
- assert (it->b->rightlink != NULL);\r
- it->b = it->b->rightlink;\r
- it->index = 0;\r
- }\r
- Py_INCREF(item);\r
- return item;\r
-}\r
-\r
-static PyObject *\r
-dequeiter_len(dequeiterobject *it)\r
-{\r
- return PyInt_FromLong(it->counter);\r
-}\r
-\r
-PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");\r
-\r
-static PyMethodDef dequeiter_methods[] = {\r
- {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},\r
- {NULL, NULL} /* sentinel */\r
-};\r
-\r
-static PyTypeObject dequeiter_type = {\r
- PyVarObject_HEAD_INIT(NULL, 0)\r
- "deque_iterator", /* tp_name */\r
- sizeof(dequeiterobject), /* tp_basicsize */\r
- 0, /* tp_itemsize */\r
- /* methods */\r
- (destructor)dequeiter_dealloc, /* tp_dealloc */\r
- 0, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- 0, /* tp_repr */\r
- 0, /* tp_as_number */\r
- 0, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- 0, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r
- 0, /* tp_doc */\r
- (traverseproc)dequeiter_traverse, /* tp_traverse */\r
- 0, /* tp_clear */\r
- 0, /* tp_richcompare */\r
- 0, /* tp_weaklistoffset */\r
- PyObject_SelfIter, /* tp_iter */\r
- (iternextfunc)dequeiter_next, /* tp_iternext */\r
- dequeiter_methods, /* tp_methods */\r
- 0,\r
-};\r
-\r
-/*********************** Deque Reverse Iterator **************************/\r
-\r
-static PyTypeObject dequereviter_type;\r
-\r
-static PyObject *\r
-deque_reviter(dequeobject *deque)\r
-{\r
- dequeiterobject *it;\r
-\r
- it = PyObject_GC_New(dequeiterobject, &dequereviter_type);\r
- if (it == NULL)\r
- return NULL;\r
- it->b = deque->rightblock;\r
- it->index = deque->rightindex;\r
- Py_INCREF(deque);\r
- it->deque = deque;\r
- it->state = deque->state;\r
- it->counter = deque->len;\r
- PyObject_GC_Track(it);\r
- return (PyObject *)it;\r
-}\r
-\r
-static PyObject *\r
-dequereviter_next(dequeiterobject *it)\r
-{\r
- PyObject *item;\r
- if (it->counter == 0)\r
- return NULL;\r
-\r
- if (it->deque->state != it->state) {\r
- it->counter = 0;\r
- PyErr_SetString(PyExc_RuntimeError,\r
- "deque mutated during iteration");\r
- return NULL;\r
- }\r
- assert (!(it->b == it->deque->leftblock &&\r
- it->index < it->deque->leftindex));\r
-\r
- item = it->b->data[it->index];\r
- it->index--;\r
- it->counter--;\r
- if (it->index == -1 && it->counter > 0) {\r
- assert (it->b->leftlink != NULL);\r
- it->b = it->b->leftlink;\r
- it->index = BLOCKLEN - 1;\r
- }\r
- Py_INCREF(item);\r
- return item;\r
-}\r
-\r
-static PyTypeObject dequereviter_type = {\r
- PyVarObject_HEAD_INIT(NULL, 0)\r
- "deque_reverse_iterator", /* tp_name */\r
- sizeof(dequeiterobject), /* tp_basicsize */\r
- 0, /* tp_itemsize */\r
- /* methods */\r
- (destructor)dequeiter_dealloc, /* tp_dealloc */\r
- 0, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- 0, /* tp_repr */\r
- 0, /* tp_as_number */\r
- 0, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- 0, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */\r
- 0, /* tp_doc */\r
- (traverseproc)dequeiter_traverse, /* tp_traverse */\r
- 0, /* tp_clear */\r
- 0, /* tp_richcompare */\r
- 0, /* tp_weaklistoffset */\r
- PyObject_SelfIter, /* tp_iter */\r
- (iternextfunc)dequereviter_next, /* tp_iternext */\r
- dequeiter_methods, /* tp_methods */\r
- 0,\r
-};\r
-\r
-/* defaultdict type *********************************************************/\r
-\r
-typedef struct {\r
- PyDictObject dict;\r
- PyObject *default_factory;\r
-} defdictobject;\r
-\r
-static PyTypeObject defdict_type; /* Forward */\r
-\r
-PyDoc_STRVAR(defdict_missing_doc,\r
-"__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\\r
- if self.default_factory is None: raise KeyError((key,))\n\\r
- self[key] = value = self.default_factory()\n\\r
- return value\n\\r
-");\r
-\r
-static PyObject *\r
-defdict_missing(defdictobject *dd, PyObject *key)\r
-{\r
- PyObject *factory = dd->default_factory;\r
- PyObject *value;\r
- if (factory == NULL || factory == Py_None) {\r
- /* XXX Call dict.__missing__(key) */\r
- PyObject *tup;\r
- tup = PyTuple_Pack(1, key);\r
- if (!tup) return NULL;\r
- PyErr_SetObject(PyExc_KeyError, tup);\r
- Py_DECREF(tup);\r
- return NULL;\r
- }\r
- value = PyEval_CallObject(factory, NULL);\r
- if (value == NULL)\r
- return value;\r
- if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {\r
- Py_DECREF(value);\r
- return NULL;\r
- }\r
- return value;\r
-}\r
-\r
-PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");\r
-\r
-static PyObject *\r
-defdict_copy(defdictobject *dd)\r
-{\r
- /* This calls the object's class. That only works for subclasses\r
- whose class constructor has the same signature. Subclasses that\r
- define a different constructor signature must override copy().\r
- */\r
-\r
- if (dd->default_factory == NULL)\r
- return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL);\r
- return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),\r
- dd->default_factory, dd, NULL);\r
-}\r
-\r
-static PyObject *\r
-defdict_reduce(defdictobject *dd)\r
-{\r
- /* __reduce__ must return a 5-tuple as follows:\r
-\r
- - factory function\r
- - tuple of args for the factory function\r
- - additional state (here None)\r
- - sequence iterator (here None)\r
- - dictionary iterator (yielding successive (key, value) pairs\r
-\r
- This API is used by pickle.py and copy.py.\r
-\r
- For this to be useful with pickle.py, the default_factory\r
- must be picklable; e.g., None, a built-in, or a global\r
- function in a module or package.\r
-\r
- Both shallow and deep copying are supported, but for deep\r
- copying, the default_factory must be deep-copyable; e.g. None,\r
- or a built-in (functions are not copyable at this time).\r
-\r
- This only works for subclasses as long as their constructor\r
- signature is compatible; the first argument must be the\r
- optional default_factory, defaulting to None.\r
- */\r
- PyObject *args;\r
- PyObject *items;\r
- PyObject *result;\r
- if (dd->default_factory == NULL || dd->default_factory == Py_None)\r
- args = PyTuple_New(0);\r
- else\r
- args = PyTuple_Pack(1, dd->default_factory);\r
- if (args == NULL)\r
- return NULL;\r
- items = PyObject_CallMethod((PyObject *)dd, "iteritems", "()");\r
- if (items == NULL) {\r
- Py_DECREF(args);\r
- return NULL;\r
- }\r
- result = PyTuple_Pack(5, Py_TYPE(dd), args,\r
- Py_None, Py_None, items);\r
- Py_DECREF(items);\r
- Py_DECREF(args);\r
- return result;\r
-}\r
-\r
-static PyMethodDef defdict_methods[] = {\r
- {"__missing__", (PyCFunction)defdict_missing, METH_O,\r
- defdict_missing_doc},\r
- {"copy", (PyCFunction)defdict_copy, METH_NOARGS,\r
- defdict_copy_doc},\r
- {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,\r
- defdict_copy_doc},\r
- {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,\r
- reduce_doc},\r
- {NULL}\r
-};\r
-\r
-static PyMemberDef defdict_members[] = {\r
- {"default_factory", T_OBJECT,\r
- offsetof(defdictobject, default_factory), 0,\r
- PyDoc_STR("Factory for default value called by __missing__().")},\r
- {NULL}\r
-};\r
-\r
-static void\r
-defdict_dealloc(defdictobject *dd)\r
-{\r
- Py_CLEAR(dd->default_factory);\r
- PyDict_Type.tp_dealloc((PyObject *)dd);\r
-}\r
-\r
-static int\r
-defdict_print(defdictobject *dd, FILE *fp, int flags)\r
-{\r
- int sts;\r
- Py_BEGIN_ALLOW_THREADS\r
- fprintf(fp, "defaultdict(");\r
- Py_END_ALLOW_THREADS\r
- if (dd->default_factory == NULL) {\r
- Py_BEGIN_ALLOW_THREADS\r
- fprintf(fp, "None");\r
- Py_END_ALLOW_THREADS\r
- } else {\r
- PyObject_Print(dd->default_factory, fp, 0);\r
- }\r
- Py_BEGIN_ALLOW_THREADS\r
- fprintf(fp, ", ");\r
- Py_END_ALLOW_THREADS\r
- sts = PyDict_Type.tp_print((PyObject *)dd, fp, 0);\r
- Py_BEGIN_ALLOW_THREADS\r
- fprintf(fp, ")");\r
- Py_END_ALLOW_THREADS\r
- return sts;\r
-}\r
-\r
-static PyObject *\r
-defdict_repr(defdictobject *dd)\r
-{\r
- PyObject *defrepr;\r
- PyObject *baserepr;\r
- PyObject *result;\r
- baserepr = PyDict_Type.tp_repr((PyObject *)dd);\r
- if (baserepr == NULL)\r
- return NULL;\r
- if (dd->default_factory == NULL)\r
- defrepr = PyString_FromString("None");\r
- else\r
- {\r
- int status = Py_ReprEnter(dd->default_factory);\r
- if (status != 0) {\r
- if (status < 0) {\r
- Py_DECREF(baserepr);\r
- return NULL;\r
- }\r
- defrepr = PyString_FromString("...");\r
- }\r
- else\r
- defrepr = PyObject_Repr(dd->default_factory);\r
- Py_ReprLeave(dd->default_factory);\r
- }\r
- if (defrepr == NULL) {\r
- Py_DECREF(baserepr);\r
- return NULL;\r
- }\r
- result = PyString_FromFormat("defaultdict(%s, %s)",\r
- PyString_AS_STRING(defrepr),\r
- PyString_AS_STRING(baserepr));\r
- Py_DECREF(defrepr);\r
- Py_DECREF(baserepr);\r
- return result;\r
-}\r
-\r
-static int\r
-defdict_traverse(PyObject *self, visitproc visit, void *arg)\r
-{\r
- Py_VISIT(((defdictobject *)self)->default_factory);\r
- return PyDict_Type.tp_traverse(self, visit, arg);\r
-}\r
-\r
-static int\r
-defdict_tp_clear(defdictobject *dd)\r
-{\r
- Py_CLEAR(dd->default_factory);\r
- return PyDict_Type.tp_clear((PyObject *)dd);\r
-}\r
-\r
-static int\r
-defdict_init(PyObject *self, PyObject *args, PyObject *kwds)\r
-{\r
- defdictobject *dd = (defdictobject *)self;\r
- PyObject *olddefault = dd->default_factory;\r
- PyObject *newdefault = NULL;\r
- PyObject *newargs;\r
- int result;\r
- if (args == NULL || !PyTuple_Check(args))\r
- newargs = PyTuple_New(0);\r
- else {\r
- Py_ssize_t n = PyTuple_GET_SIZE(args);\r
- if (n > 0) {\r
- newdefault = PyTuple_GET_ITEM(args, 0);\r
- if (!PyCallable_Check(newdefault) && newdefault != Py_None) {\r
- PyErr_SetString(PyExc_TypeError,\r
- "first argument must be callable");\r
- return -1;\r
- }\r
- }\r
- newargs = PySequence_GetSlice(args, 1, n);\r
- }\r
- if (newargs == NULL)\r
- return -1;\r
- Py_XINCREF(newdefault);\r
- dd->default_factory = newdefault;\r
- result = PyDict_Type.tp_init(self, newargs, kwds);\r
- Py_DECREF(newargs);\r
- Py_XDECREF(olddefault);\r
- return result;\r
-}\r
-\r
-PyDoc_STRVAR(defdict_doc,\r
-"defaultdict(default_factory[, ...]) --> dict with default factory\n\\r
-\n\\r
-The default factory is called without arguments to produce\n\\r
-a new value when a key is not present, in __getitem__ only.\n\\r
-A defaultdict compares equal to a dict with the same items.\n\\r
-All remaining arguments are treated the same as if they were\n\\r
-passed to the dict constructor, including keyword arguments.\n\\r
-");\r
-\r
-/* See comment in xxsubtype.c */\r
-#define DEFERRED_ADDRESS(ADDR) 0\r
-\r
-static PyTypeObject defdict_type = {\r
- PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)\r
- "collections.defaultdict", /* tp_name */\r
- sizeof(defdictobject), /* tp_basicsize */\r
- 0, /* tp_itemsize */\r
- /* methods */\r
- (destructor)defdict_dealloc, /* tp_dealloc */\r
- (printfunc)defdict_print, /* tp_print */\r
- 0, /* tp_getattr */\r
- 0, /* tp_setattr */\r
- 0, /* tp_compare */\r
- (reprfunc)defdict_repr, /* tp_repr */\r
- 0, /* tp_as_number */\r
- 0, /* tp_as_sequence */\r
- 0, /* tp_as_mapping */\r
- 0, /* tp_hash */\r
- 0, /* tp_call */\r
- 0, /* tp_str */\r
- PyObject_GenericGetAttr, /* tp_getattro */\r
- 0, /* tp_setattro */\r
- 0, /* tp_as_buffer */\r
- Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC |\r
- Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */\r
- defdict_doc, /* tp_doc */\r
- defdict_traverse, /* tp_traverse */\r
- (inquiry)defdict_tp_clear, /* tp_clear */\r
- 0, /* tp_richcompare */\r
- 0, /* tp_weaklistoffset*/\r
- 0, /* tp_iter */\r
- 0, /* tp_iternext */\r
- defdict_methods, /* tp_methods */\r
- defdict_members, /* tp_members */\r
- 0, /* tp_getset */\r
- DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */\r
- 0, /* tp_dict */\r
- 0, /* tp_descr_get */\r
- 0, /* tp_descr_set */\r
- 0, /* tp_dictoffset */\r
- defdict_init, /* tp_init */\r
- PyType_GenericAlloc, /* tp_alloc */\r
- 0, /* tp_new */\r
- PyObject_GC_Del, /* tp_free */\r
-};\r
-\r
-/* module level code ********************************************************/\r
-\r
-PyDoc_STRVAR(module_doc,\r
-"High performance data structures.\n\\r
-- deque: ordered collection accessible from endpoints only\n\\r
-- defaultdict: dict subclass with a default value factory\n\\r
-");\r
-\r
-PyMODINIT_FUNC\r
-init_collections(void)\r
-{\r
- PyObject *m;\r
-\r
- m = Py_InitModule3("_collections", NULL, module_doc);\r
- if (m == NULL)\r
- return;\r
-\r
- if (PyType_Ready(&deque_type) < 0)\r
- return;\r
- Py_INCREF(&deque_type);\r
- PyModule_AddObject(m, "deque", (PyObject *)&deque_type);\r
-\r
- defdict_type.tp_base = &PyDict_Type;\r
- if (PyType_Ready(&defdict_type) < 0)\r
- return;\r
- Py_INCREF(&defdict_type);\r
- PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type);\r
-\r
- if (PyType_Ready(&dequeiter_type) < 0)\r
- return;\r
-\r
- if (PyType_Ready(&dequereviter_type) < 0)\r
- return;\r
-\r
- return;\r
-}\r
projects / mirror_edk2.git / blobdiff