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