_collectionsmodule.c

#include"Python.h"
#include"structmember.h"

/* collections module implementation of a deque() datatype
 Written and maintained by Raymond D. Hettinger <python@rcn.com>
*/

/* The block length may be set to any number over 1. Larger numbers
 * reduce the number of calls to the memory allocator, give faster
 * indexing and rotation, and reduce the link::data overhead ratio.
 *
 * Ideally, the block length will be set to two less than some
 * multiple of the cache-line length (so that the full block
 * including the leftlink and rightlink will fit neatly into
 * cache lines).
 */

#defineBLOCKLEN 62
#defineCENTER ((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.
 */

typedefstructBLOCK {
PyObject*data[BLOCKLEN];
structBLOCK*rightlink;
structBLOCK*leftlink;
} block;

#defineMAXFREEBLOCKS 10
staticPy_ssize_tnumfreeblocks=0;
staticblock*freeblocks[MAXFREEBLOCKS];

staticblock*
newblock(block*leftlink, block*rightlink, Py_ssize_tlen) {
block*b;
/* To prevent len from overflowing PY_SSIZE_T_MAX on 32-bit machines, we
 * refuse to allocate new blocks if the current len is nearing overflow. */
if (len >= PY_SSIZE_T_MAX-2*BLOCKLEN) {
PyErr_SetString(PyExc_OverflowError,
"cannot add more blocks to the deque");
returnNULL;
 }
if (numfreeblocks) {
numfreeblocks-=1;
b=freeblocks[numfreeblocks];
 } else {
b=PyMem_Malloc(sizeof(block));
if (b==NULL) {
PyErr_NoMemory();
returnNULL;
 }
 }
b->leftlink=leftlink;
b->rightlink=rightlink;
returnb;
}

staticvoid
freeblock(block*b)
{
if (numfreeblocks<MAXFREEBLOCKS) {
freeblocks[numfreeblocks] =b;
numfreeblocks++;
 } else {
PyMem_Free(b);
 }
}

typedefstruct {
PyObject_HEAD
block*leftblock;
block*rightblock;
Py_ssize_tleftindex; /* in range(BLOCKLEN) */
Py_ssize_trightindex; /* in range(BLOCKLEN) */
Py_ssize_tlen;
longstate; /* incremented whenever the indices move */
Py_ssize_tmaxlen;
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().
 */

#defineTRIM(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); \
 }

staticPyTypeObjectdeque_type;

staticPyObject*
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)
returnNULL;

b=newblock(NULL, NULL, 0);
if (b==NULL) {
Py_DECREF(deque);
returnNULL;
 }

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;
}

staticPyObject*
deque_pop(dequeobject*deque, PyObject*unused)
{
PyObject*item;
block*prevblock;

if (deque->len==0) {
PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
returnNULL;
 }
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;
 }
 }
returnitem;
}

PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");

staticPyObject*
deque_popleft(dequeobject*deque, PyObject*unused)
{
PyObject*item;
block*prevblock;

if (deque->len==0) {
PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
returnNULL;
 }
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;
 }
 }
returnitem;
}

PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");

staticPyObject*
deque_append(dequeobject*deque, PyObject*item)
{
deque->state++;
if (deque->rightindex==BLOCKLEN-1) {
block*b=newblock(deque->rightblock, NULL, deque->len);
if (b==NULL)
returnNULL;
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.");

staticPyObject*
deque_appendleft(dequeobject*deque, PyObject*item)
{
deque->state++;
if (deque->leftindex==0) {
block*b=newblock(NULL, deque->leftblock, deque->len);
if (b==NULL)
returnNULL;
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. */
staticPyObject*
consume_iterator(PyObject*it)
{
PyObject*item;

while ((item=PyIter_Next(it)) !=NULL) {
Py_DECREF(item);
 }
Py_DECREF(it);
if (PyErr_Occurred())
returnNULL;
Py_RETURN_NONE;
}

staticPyObject*
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)
returnNULL;
result=deque_extend(deque, s);
Py_DECREF(s);
returnresult;
 }

it=PyObject_GetIter(iterable);
if (it==NULL)
returnNULL;

if (deque->maxlen==0)
returnconsume_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);
returnNULL;
 }
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())
returnNULL;
Py_RETURN_NONE;
}

PyDoc_STRVAR(extend_doc,
"Extend the right side of the deque with elements from the iterable");

staticPyObject*
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)
returnNULL;
result=deque_extendleft(deque, s);
Py_DECREF(s);
returnresult;
 }

it=PyObject_GetIter(iterable);
if (it==NULL)
returnNULL;

if (deque->maxlen==0)
returnconsume_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);
returnNULL;
 }
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())
returnNULL;
Py_RETURN_NONE;
}

PyDoc_STRVAR(extendleft_doc,
"Extend the left side of the deque with elements from the iterable");

staticPyObject*
deque_inplace_concat(dequeobject*deque, PyObject*other)
{
PyObject*result;

result=deque_extend(deque, other);
if (result==NULL)
returnresult;
Py_DECREF(result);
Py_INCREF(deque);
return (PyObject*)deque;
}

staticint
_deque_rotate(dequeobject*deque, Py_ssize_tn)
{
Py_ssize_tm, len=deque->len, halflen=len>>1;

if (len <= 1)
return0;
if (n>halflen||n<-halflen) {
n %= len;
if (n>halflen)
n-=len;
elseif (n<-halflen)
n+=len;
 }
assert(len>1);
assert(-halflen <= n&&n <= halflen);

deque->state++;
while (n>0) {
if (deque->leftindex==0) {
block*b=newblock(NULL, deque->leftblock, len);
if (b==NULL)
return-1;
assert(deque->leftblock->leftlink==NULL);
deque->leftblock->leftlink=b;
deque->leftblock=b;
deque->leftindex=BLOCKLEN;
 }
assert(deque->leftindex>0);

m=n;
if (m>deque->rightindex+1)
m=deque->rightindex+1;
if (m>deque->leftindex)
m=deque->leftindex;
assert (m>0&&m <= len);
memcpy(&deque->leftblock->data[deque->leftindex-m],
&deque->rightblock->data[deque->rightindex+1-m],
m*sizeof(PyObject*));
deque->rightindex-=m;
deque->leftindex-=m;
n-=m;

if (deque->rightindex==-1) {
block*prevblock=deque->rightblock->leftlink;
assert(deque->rightblock!=NULL);
assert(deque->leftblock!=deque->rightblock);
freeblock(deque->rightblock);
prevblock->rightlink=NULL;
deque->rightblock=prevblock;
deque->rightindex=BLOCKLEN-1;
 }
 }
while (n<0) {
if (deque->rightindex==BLOCKLEN-1) {
block*b=newblock(deque->rightblock, NULL, len);
if (b==NULL)
return-1;
assert(deque->rightblock->rightlink==NULL);
deque->rightblock->rightlink=b;
deque->rightblock=b;
deque->rightindex=-1;
 }
assert (deque->rightindex<BLOCKLEN-1);

m=-n;
if (m>BLOCKLEN-deque->leftindex)
m=BLOCKLEN-deque->leftindex;
if (m>BLOCKLEN-1-deque->rightindex)
m=BLOCKLEN-1-deque->rightindex;
assert (m>0&&m <= len);
memcpy(&deque->rightblock->data[deque->rightindex+1],
&deque->leftblock->data[deque->leftindex],
m*sizeof(PyObject*));
deque->leftindex+=m;
deque->rightindex+=m;
n+=m;

if (deque->leftindex==BLOCKLEN) {
block*nextblock=deque->leftblock->rightlink;
assert(deque->leftblock!=deque->rightblock);
freeblock(deque->leftblock);
assert(nextblock!=NULL);
nextblock->leftlink=NULL;
deque->leftblock=nextblock;
deque->leftindex=0;
 }
 }
return0;
}

staticPyObject*
deque_rotate(dequeobject*deque, PyObject*args)
{
Py_ssize_tn=1;

if (!PyArg_ParseTuple(args, "|n:rotate", &n))
returnNULL;
if (_deque_rotate(deque, n) ==0)
Py_RETURN_NONE;
returnNULL;
}

PyDoc_STRVAR(rotate_doc,
"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");

staticPyObject*
deque_reverse(dequeobject*deque, PyObject*unused)
{
block*leftblock=deque->leftblock;
block*rightblock=deque->rightblock;
Py_ssize_tleftindex=deque->leftindex;
Py_ssize_trightindex=deque->rightindex;
Py_ssize_tn= (deque->len)/2;
Py_ssize_ti;
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*");

staticPyObject*
deque_count(dequeobject*deque, PyObject*v)
{
block*leftblock=deque->leftblock;
Py_ssize_tleftindex=deque->leftindex;
Py_ssize_tn=deque->len;
Py_ssize_ti;
Py_ssize_tcount=0;
PyObject*item;
longstart_state=deque->state;
intcmp;

for (i=0 ; i<n ; i++) {
item=leftblock->data[leftindex];
cmp=PyObject_RichCompareBool(item, v, Py_EQ);
if (cmp>0)
count++;
elseif (cmp<0)
returnNULL;

if (start_state!=deque->state) {
PyErr_SetString(PyExc_RuntimeError,
"deque mutated during iteration");
returnNULL;
 }

/* 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;
 }
 }
returnPyInt_FromSsize_t(count);
}

PyDoc_STRVAR(count_doc,
"D.count(value) -> integer -- return number of occurrences of value");

staticPy_ssize_t
deque_len(dequeobject*deque)
{
returndeque->len;
}

staticPyObject*
deque_remove(dequeobject*deque, PyObject*value)
{
Py_ssize_ti, n=deque->len;

for (i=0 ; i<n ; i++) {
PyObject*item=deque->leftblock->data[deque->leftindex];
intcmp=PyObject_RichCompareBool(item, value, Py_EQ);

if (deque->len!=n) {
PyErr_SetString(PyExc_IndexError,
"deque mutated during remove().");
returnNULL;
 }
if (cmp>0) {
PyObject*tgt=deque_popleft(deque, NULL);
assert (tgt!=NULL);
if (_deque_rotate(deque, i))
returnNULL;
Py_DECREF(tgt);
Py_RETURN_NONE;
 }
elseif (cmp<0) {
_deque_rotate(deque, i);
returnNULL;
 }
_deque_rotate(deque, -1);
 }
PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
returnNULL;
}

PyDoc_STRVAR(remove_doc,
"D.remove(value) -- remove first occurrence of value.");

staticint
deque_clear(dequeobject*deque)
{
block*b;
block*prevblock;
block*leftblock;
Py_ssize_tleftindex;
Py_ssize_tn;
PyObject*item;

if (deque->len==0)
return0;

/* During the process of clearing a deque, decrefs can cause the
 deque to mutate. To avoid fatal confusion, we have to make the
 deque empty before clearing the blocks and never refer to
 anything via deque->ref while clearing. (This is the same
 technique used for clearing lists, sets, and dicts.)

 Making the deque empty requires allocating a new empty block. In
 the unlikely event that memory is full, we fall back to an
 alternate method that doesn't require a new block. Repeating
 pops in a while-loop is slower, possibly re-entrant (and a clever
 adversary could cause it to never terminate).
 */

b=newblock(NULL, NULL, 0);
if (b==NULL) {
PyErr_Clear();
 goto alternate_method;
 }

/* Remember the old size, leftblock, and leftindex */
leftblock=deque->leftblock;
leftindex=deque->leftindex;
n=deque->len;

/* Set the deque to be empty using the newly allocated block */
deque->len=0;
deque->leftblock=b;
deque->rightblock=b;
deque->leftindex=CENTER+1;
deque->rightindex=CENTER;
deque->state++;

/* Now the old size, leftblock, and leftindex are disconnected from
 the empty deque and we can use them to decref the pointers.
 */
while (n--) {
item=leftblock->data[leftindex];
Py_DECREF(item);
leftindex++;
if (leftindex==BLOCKLEN&&n) {
assert(leftblock->rightlink!=NULL);
prevblock=leftblock;
leftblock=leftblock->rightlink;
leftindex=0;
freeblock(prevblock);
 }
 }
assert(leftblock->rightlink==NULL);
freeblock(leftblock);
return0;

alternate_method:
while (deque->len) {
item=deque_pop(deque, NULL);
assert (item!=NULL);
Py_DECREF(item);
 }
return0;
}

staticPyObject*
deque_item(dequeobject*deque, Py_ssize_ti)
{
block*b;
PyObject*item;
Py_ssize_tn, index=i;

if (i<0||i >= deque->len) {
PyErr_SetString(PyExc_IndexError,
"deque index out of range");
returnNULL;
 }

if (i==0) {
i=deque->leftindex;
b=deque->leftblock;
 } elseif (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);
returnitem;
}

/* 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.
*/

staticint
deque_del_item(dequeobject*deque, Py_ssize_ti)
{
PyObject*item;
intrv;

assert (i >= 0&&i<deque->len);
if (_deque_rotate(deque, -i))
return-1;
item=deque_popleft(deque, NULL);
rv=_deque_rotate(deque, i);
assert (item!=NULL);
Py_DECREF(item);
returnrv;
}

staticint
deque_ass_item(dequeobject*deque, Py_ssize_ti, PyObject*v)
{
PyObject*old_value;
block*b;
Py_ssize_tn, 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)
returndeque_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);
return0;
}

staticPyObject*
deque_clearmethod(dequeobject*deque)
{
deque_clear(deque);
Py_RETURN_NONE;
}

PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");

staticvoid
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);
}

staticint
deque_traverse(dequeobject*deque, visitprocvisit, void*arg)
{
block*b;
PyObject*item;
Py_ssize_tindex;
Py_ssize_tindexlo=deque->leftindex;

for (b=deque->leftblock; b!=NULL; b=b->rightlink) {
constPy_ssize_tindexhi=b==deque->rightblock ?
deque->rightindex :
BLOCKLEN-1;

for (index=indexlo; index <= indexhi; ++index) {
item=b->data[index];
Py_VISIT(item);
 }
indexlo=0;
 }
return0;
}

staticPyObject*
deque_copy(PyObject*deque)
{
PyObject*result;
if (((dequeobject*)deque)->maxlen==-1)
result=PyObject_CallFunction((PyObject*)(Py_TYPE(deque)), "O", deque, NULL);
else
result=PyObject_CallFunction((PyObject*)(Py_TYPE(deque)), "Oi",
deque, ((dequeobject*)deque)->maxlen, NULL);
if (result!=NULL&& !PyObject_TypeCheck(result, &deque_type)) {
PyErr_Format(PyExc_TypeError,
"%.200s() must return a deque, not %.200s",
Py_TYPE(deque)->tp_name, Py_TYPE(result)->tp_name);
Py_DECREF(result);
returnNULL;
 }
returnresult;
}

PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");

staticPyObject*
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);
returnNULL;
 }
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);
returnresult;
}

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

staticPyObject*
deque_repr(PyObject*deque)
{
PyObject*aslist, *result, *fmt;
inti;

i=Py_ReprEnter(deque);
if (i!=0) {
if (i<0)
returnNULL;
returnPyString_FromString("[...]");
 }

aslist=PySequence_List(deque);
if (aslist==NULL) {
Py_ReprLeave(deque);
returnNULL;
 }
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);
returnNULL;
 }
result=PyString_Format(fmt, aslist);
Py_DECREF(fmt);
Py_DECREF(aslist);
Py_ReprLeave(deque);
returnresult;
}

staticint
deque_tp_print(PyObject*deque, FILE*fp, intflags)
{
PyObject*it, *item;
char*emit=""; /* No separator emitted on first pass */
char*separator=", ";
inti;

i=Py_ReprEnter(deque);
if (i!=0) {
if (i<0)
returni;
Py_BEGIN_ALLOW_THREADS
fputs("[...]", fp);
Py_END_ALLOW_THREADS
return0;
 }

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
return0;
}

staticPyObject*
deque_richcompare(PyObject*v, PyObject*w, intop)
{