#include "Python.h"

#include "structmember.h"

#define BLOCKLEN 62

#define CENTER ((BLOCKLEN - 1) / 2)

typedef struct BLOCK {

} 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

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;

#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.");

static PyObject *

deque_extend(dequeobject *deque, PyObject *iterable)

{

PyObject *it, *item;

it = PyObject_GetIter(iterable);

if (it == NULL)

return NULL;

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;

it = PyObject_GetIter(iterable);

if (it == NULL)

return NULL;

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

}

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

};

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

{"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},

{"rotate", (PyCFunction)deque_rotate,

METH_VARARGS, rotate_doc},

{NULL, NULL} /* sentinel */

};

PyDoc_STRVAR(deque_doc,

Build an ordered collection accessible from endpoints only.");

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

0, /* 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 */

};

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;