Exceptions raised during renaming in rotating file handlers are now passed to handleE...

[python.git] / Modules / 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>
   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;

static block *
newblock(block *leftlink, block *rightlink, int len) {
        block *b;
        /* To prevent len from overflowing INT_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 INT_MAX-2 entries in total.
         */
        if (len >= INT_MAX - 2*BLOCKLEN) {
                PyErr_SetString(PyExc_OverflowError,
                                "cannot add more blocks to the deque");
                return NULL;
        }
        b = PyMem_Malloc(sizeof(block));
        if (b == NULL) {
                PyErr_NoMemory();
                return NULL;
        }
        b->leftlink = leftlink;
        b->rightlink = rightlink;
        return b;
}

typedef struct {
        PyObject_HEAD
        block *leftblock;
        block *rightblock;
        int leftindex;  /* in range(BLOCKLEN) */
        int rightindex; /* in range(BLOCKLEN) */
        int len;
        long state;     /* incremented whenever the indices move */
        PyObject *weakreflist; /* List of weak references */
} dequeobject;

static PyTypeObject deque_type;

static PyObject *
deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
        dequeobject *deque;
        block *b;

        if (!_PyArg_NoKeywords("deque()", kwds))
                return NULL;

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

        return (PyObject *)deque;
}

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

PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the 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);
                        PyMem_Free(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;
        }
        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;
                        assert(deque->leftblock != NULL);
                        PyMem_Free(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_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;
        }
        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;
        }
        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, int n)
{
        int 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)
{
        int n=1;

        if (!PyArg_ParseTuple(args, "|i: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 int
deque_len(dequeobject *deque)
{
        return deque->len;
}

static PyObject *
deque_remove(dequeobject *deque, PyObject *value)
{
        int 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, int i)
{
        block *b;
        PyObject *item;
        int 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, int 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, int i, PyObject *v)
{
        PyObject *old_value;
        block *b;
        int 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);
                PyMem_Free(deque->leftblock);
        }
        deque->leftblock = NULL;
        deque->rightblock = NULL;
        deque->ob_type->tp_free(deque);
}

static int
deque_traverse(dequeobject *deque, visitproc visit, void *arg)
{
        block *b;
        PyObject *item;
        int index;
        int indexlo = deque->leftindex;

        for (b = deque->leftblock; b != NULL; b = b->rightlink) {
                const int 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 long
deque_nohash(PyObject *self)
{
        PyErr_SetString(PyExc_TypeError, "deque objects are unhashable");
        return -1;
}

static PyObject *
deque_copy(PyObject *deque)
{
        return PyObject_CallFunctionObjArgs((PyObject *)(deque->ob_type),
                deque, NULL);
}

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

static PyObject *
deque_reduce(dequeobject *deque)
{
        PyObject *dict, *result, *it;

        dict = PyObject_GetAttrString((PyObject *)deque, "__dict__");
        if (dict == NULL) {
                PyErr_Clear();
                dict = Py_None;
                Py_INCREF(dict);
        }
        it = PyObject_GetIter((PyObject *)deque);
        if (it == NULL) {
                Py_DECREF(dict);
                return NULL;
        }
        result = Py_BuildValue("O()ON", deque->ob_type, dict, it);
        Py_DECREF(dict);
        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;
        }

        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;
                fputs("[...]", fp);
                return 0;
        }

        it = PyObject_GetIter(deque);
        if (it == NULL)
                return -1;

        fputs("deque([", fp);
        while ((item = PyIter_Next(it)) != NULL) {
                fputs(emit, fp);
                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;
        fputs("])", fp);
        return 0;
}

static PyObject *
deque_richcompare(PyObject *v, PyObject *w, int op)
{
        PyObject *it1=NULL, *it2=NULL, *x, *y;
        int b, vs, ws, 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 *kwds)
{
        PyObject *iterable = NULL;

        if (!PyArg_UnpackTuple(args, "deque", 0, 1, &iterable))
                return -1;

        if (iterable != NULL) {
                PyObject *rv = deque_extend(deque, iterable);
                if (rv == NULL)
                        return -1;
                Py_DECREF(rv);
        }
        return 0;
}

static PySequenceMethods deque_as_sequence = {
        (inquiry)deque_len,             /* sq_length */
        0,                              /* sq_concat */
        0,                              /* sq_repeat */
        (intargfunc)deque_item,         /* sq_item */
        0,                              /* sq_slice */
        (intobjargproc)deque_ass_item,  /* sq_ass_item */
};

/* 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},
        {"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,
"deque(iterable) --> deque object\n\
\n\
Build an ordered collection accessible from endpoints only.");

static PyTypeObject deque_type = {
        PyObject_HEAD_INIT(NULL)
        0,                              /* ob_size */
        "collections.deque",            /* tp_name */
        sizeof(dequeobject),            /* tp_basicsize */
        0,                              /* tp_itemsize */
        /* methods */
        (destructor)deque_dealloc,      /* tp_dealloc */
        (printfunc)deque_tp_print,      /* tp_print */
        0,                              /* tp_getattr */
        0,                              /* tp_setattr */
        0,                              /* tp_compare */
        (reprfunc)deque_repr,           /* tp_repr */
        0,                              /* tp_as_number */
        &deque_as_sequence,             /* tp_as_sequence */
        0,                              /* tp_as_mapping */
        deque_nohash,                   /* 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 */
};

/*********************** Deque Iterator **************************/

typedef struct {
        PyObject_HEAD
        int index;
        block *b;
        dequeobject *deque;
        long state;     /* state when the iterator is created */
        int counter;    /* number of items remaining for iteration */
} dequeiterobject;

PyTypeObject dequeiter_type;

static PyObject *
deque_iter(dequeobject *deque)
{
        dequeiterobject *it;

        it = PyObject_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;
        return (PyObject *)it;
}

static void
dequeiter_dealloc(dequeiterobject *dio)
{
        Py_XDECREF(dio->deque);
        dio->ob_type->tp_free(dio);
}

static PyObject *
dequeiter_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->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_cue_doc, "Private method returning an estimate of len(list(it)).");

static PyMethodDef dequeiter_methods[] = {
        {"_length_cue", (PyCFunction)dequeiter_len, METH_NOARGS, length_cue_doc},
        {NULL,          NULL}           /* sentinel */
};

PyTypeObject dequeiter_type = {
        PyObject_HEAD_INIT(NULL)
        0,                                      /* ob_size */
        "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,                     /* tp_flags */
        0,                                      /* tp_doc */
        0,                                      /* 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 **************************/

PyTypeObject dequereviter_type;

static PyObject *
deque_reviter(dequeobject *deque)
{
        dequeiterobject *it;

        it = PyObject_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;
        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;
}

PyTypeObject dequereviter_type = {
        PyObject_HEAD_INIT(NULL)
        0,                                      /* ob_size */
        "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,                     /* tp_flags */
        0,                                      /* tp_doc */
        0,                                      /* 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,
};

/* module level code ********************************************************/

PyDoc_STRVAR(module_doc,
"High performance data structures\n\
");

PyMODINIT_FUNC
initcollections(void)
{
        PyObject *m;

        m = Py_InitModule3("collections", NULL, module_doc);

        if (PyType_Ready(&deque_type) < 0)
                return;
        Py_INCREF(&deque_type);
        PyModule_AddObject(m, "deque", (PyObject *)&deque_type);

        if (PyType_Ready(&dequeiter_type) < 0)
                return;

        if (PyType_Ready(&dequereviter_type) < 0)
                return;

        return;
}