Index: Modules/collectionsmodule.c =================================================================== --- Modules/collectionsmodule.c (revision 45688) +++ Modules/collectionsmodule.c (working copy) @@ -3,6 +3,8 @@ /* collections module implementation of a deque() datatype Written and maintained by Raymond D. Hettinger + implementation of a rbtree() datatype + Written and maintained by Hye-Shik Chang Copyright (c) 2004 Python Software Foundation. All rights reserved. */ @@ -1322,6 +1324,1837 @@ PyObject_GC_Del, /* tp_free */ }; + +/* rbtree object *******************************************************/ + +enum rbtree_color { + RED=1, BLACK=0 +}; + +struct rbtree_node { + struct rbtree_node *left; + struct rbtree_node *right; + struct rbtree_node *parent; + PyObject *value; + PyObject *key; /* for key-indexed redblack trees */ + enum rbtree_color color; +}; + +struct _rbtreeobject; + +typedef int (*rbtree_cmpprep)(struct _rbtreeobject *tree, + PyObject *v, PyObject *w, PyObject **ovp, PyObject **owp); + +typedef struct _rbtreeobject { + PyObject_HEAD + struct rbtree_node *root; /* the root node */ + PyObject *nodemap; /* dict -> tree-node mapping */ + rbtree_cmpprep cmpprep; /* comparator preparing hook */ + PyObject *cmpkey; /* "cmp" or "key" function if applicable */ + Py_ssize_t nvalues; /* how many values in the tree? */ + int reverse; /* reversed order */ + int lock; /* write lock for exclusive operations */ + long state; /* incremented whenever the indices move */ +} rbtreeobject; + +PyTypeObject rbtree_type; + +#define RBTREE_ISLOCKED(tree) ((tree)->lock) +#define RBTREE_LOCKED_ERROR() \ + PyErr_SetString(PyExc_ValueError, "access to a locked rbtree instance") +#define RBTREE_LOCK(tree) (((tree)->lock) = 1) +#define RBTREE_UNLOCK(tree) (((tree)->lock) = 0) +#define RBTREE_LOCK_IFUN(tree) do { \ + if (RBTREE_ISLOCKED(tree)) { \ + RBTREE_LOCKED_ERROR(); \ + return -1; \ + } \ + RBTREE_LOCK(tree); \ +} while (0); +#define RBTREE_LOCK_PFUN(tree) do { \ + if (RBTREE_ISLOCKED(tree)) { \ + RBTREE_LOCKED_ERROR(); \ + return NULL; \ + } \ + RBTREE_LOCK(tree); \ +} while (0); + + +/* allocation/deallocation and internal operations */ + +#define _RBTREE_TRAVERSE_HEAD(root, left, right) \ +{ \ + struct rbtree_node *_cur, *_prev, *_next; \ + \ + _cur = NULL; \ + _next = (root); \ + \ + while (_next != NULL) { \ + _prev = _cur; \ + _cur = _next; \ + \ + if (_prev == _cur->parent && _cur->left != NULL) { \ + _next = _cur->left; \ + continue; \ + } \ + \ + _next = _cur->parent; \ + if (_prev != _cur->right || _prev == NULL) { \ + if (_cur->right != NULL) \ + _next = _cur->right; + +#define _RBTREE_TRAVERSE_TAIL(left, right) \ + } \ + } \ +} + +#define RBTREE_TRAVERSE_HEAD(root) \ + _RBTREE_TRAVERSE_HEAD(root, left, right) +#define RBTREE_TRAVERSE_TAIL \ + _RBTREE_TRAVERSE_TAIL(left, right) + +#define RBTREE_TRAVERSE_REVERSE_HEAD(root) \ + _RBTREE_TRAVERSE_HEAD(root, right, left) +#define RBTREE_TRAVERSE_REVERSE_TAIL \ + _RBTREE_TRAVERSE_TAIL(right, left) + +/** + * X rbtree_left_rotate(X) -> Y + * / \ / \ + * A Y X C + * / \ <- rbtree_right_rotate(Y) / \ + * B C A B + */ + +static void +rbtree_rotate_left(rbtreeobject *tree, struct rbtree_node *x) +{ + struct rbtree_node *y; + + assert(x->right != NULL); + + y = x->right; + x->right = y->left; + + if (y->left != NULL) + y->left->parent = x; + + y->parent = x->parent; + + if (x->parent == NULL) + tree->root = y; + else if (x->parent->left == x) + x->parent->left = y; + else + x->parent->right = y; + + y->left = x; + x->parent = y; +} + +static void +rbtree_rotate_right(rbtreeobject *tree, struct rbtree_node *y) +{ + struct rbtree_node *x; + + assert(y->left != NULL); + + x = y->left; + y->left = x->right; + + if (x->right != NULL) + x->right->parent = y; + + x->parent = y->parent; + + if (y->parent == NULL) + tree->root = x; + else if (y->parent->left == y) + y->parent->left = x; + else + y->parent->right = x; + + x->right = y; + y->parent = x; +} + +static int +rbtree_compare_nodes(rbtreeobject *tree, PyObject *v, PyObject *w, int opid) +{ + PyObject *r; + int ret; + + if (tree->reverse) + switch (opid) { + case Py_LT: opid = Py_GT; break; + case Py_LE: opid = Py_GE; break; + case Py_EQ: case Py_NE: break; + case Py_GT: opid = Py_LT; break; + case Py_GE: opid = Py_LE; break; + } + + if (tree->cmpprep == NULL) + r = PyObject_RichCompare(v, w, opid); + else { + PyObject *ov, *ow; + + if (tree->cmpprep(tree, v, w, &ov, &ow) != 0) + return -1; + + r = PyObject_RichCompare(ov, ow, opid); + Py_DECREF(ov); + Py_DECREF(ow); + } + + if (r == NULL) + return -1; + ret = (r == Py_True); + Py_DECREF(r); + return ret; +} + +static void +rbtree_delete_fixup(rbtreeobject *tree, struct rbtree_node *parent, + struct rbtree_node *node) +{ + struct rbtree_node *tmp; + + while ((node == NULL || node->color == BLACK) && node != tree->root) { + if (parent->left == node) { + tmp = parent->right; + if (tmp->color == RED) { + tmp->color = BLACK; + parent->color = RED; + rbtree_rotate_left(tree, parent); + tmp = parent->right; + } + if ((tmp->left == NULL || tmp->left->color == BLACK) && + (tmp->right == NULL || + tmp->right->color == BLACK)) { + tmp->color = RED; + node = parent; + parent = node->parent; + } + else { + if (tmp->right == NULL || + tmp->right->color == BLACK) { + struct rbtree_node *oleft; + + if ((oleft = tmp->left) != NULL) + oleft->color = BLACK; + tmp->color = RED; + rbtree_rotate_right(tree, tmp); + tmp = parent->right; + } + tmp->color = parent->color; + parent->color = BLACK; + if (tmp->right != NULL) + tmp->right->color = BLACK; + rbtree_rotate_left(tree, parent); + node = tree->root; + break; + } + } + else { + tmp = parent->left; + if (tmp->color == RED) { + tmp->color = BLACK; + parent->color = RED; + rbtree_rotate_right(tree, parent); + tmp = parent->left; + } + if ((tmp->left == NULL || tmp->left->color == BLACK) && + (tmp->right == NULL || + tmp->right->color == BLACK)) { + tmp->color = RED; + node = parent; + parent = node->parent; + } + else { + if (tmp->left == NULL || + tmp->left->color == BLACK) { + struct rbtree_node *oright; + + if ((oright = tmp->right) != NULL) + oright->color = BLACK; + tmp->color = RED; + rbtree_rotate_left(tree, tmp); + tmp = parent->left; + } + tmp->color = parent->color; + parent->color = BLACK; + if (tmp->left != NULL) + tmp->left->color = BLACK; + rbtree_rotate_right(tree, parent); + node = tree->root; + break; + } + } + } + + if (node != NULL) + node->color = BLACK; +} + +static struct rbtree_node * +rbtree_delete(rbtreeobject *tree, struct rbtree_node *node) +{ + struct rbtree_node *child, *parent, *old = node; + enum rbtree_color color; + + if (node->left == NULL) + child = node->right; + else if (node->right == NULL) + child = node->left; + else { + struct rbtree_node *left; + + node = node->right; + while ((left = node->left) != NULL) + node = left; + child = node->right; + parent = node->parent; + color = node->color; + if (child != NULL) + child->parent = parent; + if (parent != NULL) { + if (parent->left == node) + parent->left = child; + else + parent->right = child; + } + else + tree->root = child; + + if (node->parent == old) + parent = node; + + node->left = old->left; + node->right = old->right; + node->parent = old->parent; + node->color = old->color; + + if (old->parent != NULL) { + if (old->parent->left == old) + old->parent->left = node; + else + old->parent->right = node; + } + else + tree->root = node; + + old->left->parent = node; + if (old->right != NULL) + old->right->parent = node; + if (parent != NULL) { + left = parent; + while ((left = left->parent) != NULL) + /* pass */; + } + + goto fix_color; + } + + parent = node->parent; + color = node->color; + if (child != NULL) + child->parent = parent; + if (parent != NULL) { + if (parent->left == node) + parent->left = child; + else + parent->right = child; + } + else + tree->root = child; + + fix_color: + if (color == BLACK) + rbtree_delete_fixup(tree, parent, child); + tree->state++; + return old; +} + +static void +rbtree_delete_free(rbtreeobject *tree, struct rbtree_node *node) +{ + (void)rbtree_delete(tree, node); + tree->nvalues--; + Py_DECREF(node->value); + Py_XDECREF(node->key); + PyMem_Del(node); +} + +static void +rbtree_nodewrap_destructor(void *node, void *tree) +{ + struct rbtree_node *nodeptr = (struct rbtree_node *)node; + + /* if key is NULL, the case is just replacing unlabled node is + * replacing a labled node */ + if (nodeptr->key != NULL) + rbtree_delete_free((rbtreeobject *)tree, nodeptr); +} + +static int +rbtree_delete_node(rbtreeobject *tree, struct rbtree_node *node) +{ + if (node->key == NULL) { + rbtree_delete_free(tree, node); + return 0; + } + else + return PyDict_DelItem(tree->nodemap, node->key); +} + +static void +rbtree_insert_fixup(rbtreeobject *tree, struct rbtree_node *node) +{ + struct rbtree_node *parent, *gparent, *tmp; + + while ((parent = node->parent) != NULL && parent->color == RED) { + gparent = parent->parent; + if (parent == gparent->left) { + tmp = gparent->right; + if (tmp && tmp->color == RED) { + tmp->color = BLACK; + parent->color = BLACK; + gparent->color = RED; + node = gparent; + continue; + } + if (parent->right == node) { + rbtree_rotate_left(tree, parent); + tmp = parent; + parent = node; + node = tmp; + } + parent->color = BLACK; + gparent->color = RED; + rbtree_rotate_right(tree, gparent); + } + else { + tmp = gparent->left; + if (tmp != NULL && tmp->color == RED) { + tmp->color = BLACK; + parent->color = BLACK; + gparent->color = RED; + node = gparent; + continue; + } + if (parent->left == node) { + rbtree_rotate_right(tree, parent); + tmp = parent; + parent = node; + node = tmp; + } + parent->color = BLACK; + gparent->color = RED; + rbtree_rotate_left(tree, gparent); + } + } + tree->root->color = BLACK; +} + +static struct rbtree_node * +rbtree_insert_node(rbtreeobject *tree, PyObject *value, PyObject *key) +{ + struct rbtree_node **bnode, *parent, *newnode; + PyObject *nodewrap = NULL; + int succeed; + + bnode = &tree->root; + parent = NULL; + + while (*bnode != NULL) { + int r; + + parent = *bnode; + + r = rbtree_compare_nodes(tree, value, (*bnode)->value, Py_LT); + if (r == -1) + return NULL; + else if (r) { + bnode = &(*bnode)->left; + continue; + } + + r = rbtree_compare_nodes(tree, value, (*bnode)->value, Py_NE); + if (r == -1) + return NULL; + else if (r) { + bnode = &(*bnode)->right; + continue; + } + + /* replace duplicated entry in the tree. */ + break; + } + + if (*bnode == NULL) { + newnode = PyMem_New(struct rbtree_node, 1); + if (newnode == NULL) + return NULL; + *bnode = newnode; + newnode->left = newnode->right = NULL; + newnode->parent = parent; + newnode->color = RED; + tree->nvalues++; + + rbtree_insert_fixup(tree, newnode); + } + else { + newnode = *bnode; + if (newnode->key != NULL) { + nodewrap = PyDict_GetItem(tree->nodemap, + newnode->key); + if (nodewrap == NULL) { + PyErr_SetString(PyExc_KeyError, + "internal mapping glitch"); + return NULL; + } + + Py_INCREF(nodewrap); + if (PyDict_DelItem(tree->nodemap, + newnode->key) == -1) { + Py_XDECREF(nodewrap); + return NULL; + } + } + + Py_DECREF(newnode->value); + Py_XDECREF(newnode->key); + } + + succeed = 1; + + /* update the node mapping */ + if (key != NULL) { + if (nodewrap == NULL) { + nodewrap = PyCObject_FromVoidPtrAndDesc(newnode, + tree, rbtree_nodewrap_destructor); + if (nodewrap == NULL) + succeed = 0; + } + + if (succeed && PyDict_SetItem(tree->nodemap, key, + nodewrap) == -1) + succeed = 0; + } + + newnode->value = value; + Py_INCREF(value); + if (succeed) { + newnode->key = key; + Py_XINCREF(key); + } + else + newnode->key = NULL; + + Py_XDECREF(nodewrap); + tree->state++; + + if (succeed) + return newnode; + else { + /* recover failure and raise error */ + if (nodewrap != NULL) + /* the nodewrap destructor should remove the node + * already */; + else + rbtree_delete_free(tree, newnode); + + return NULL; + } +} + +static PyObject * +rbtree_itemobj(struct rbtree_node *node) +{ + PyObject *t; + + t = PyTuple_New(2); + if (t == NULL) + return NULL; + + if (node->key != NULL) { + PyTuple_SET_ITEM(t, 0, node->key); + Py_INCREF(node->key); + } + else { + PyTuple_SET_ITEM(t, 0, Py_None); + Py_INCREF(Py_None); + } + + PyTuple_SET_ITEM(t, 1, node->value); + Py_INCREF(node->value); + + return t; +} + +/** + * Comparison preparers: + * rbtree_cmpprep_cmpfunc sets tree.cmp(v, w) on *ovp and int(0) on *owp + * rbtree_cmpprep_keyfunc sets tree.key(v) on *ovp and tree.key(w) on *owp + */ + +static int +rbtree_cmpprep_cmpfunc(rbtreeobject *tree, + PyObject *left, PyObject *right, + PyObject **lvp, PyObject **rvp) +{ + assert(tree->cmpkey != NULL); + *lvp = PyObject_CallFunctionObjArgs(tree->cmpkey, left, right, NULL); + if (*lvp == NULL) + return -1; + *rvp = PyInt_FromLong(0); + return 0; +} + +static int +rbtree_cmpprep_keyfunc(rbtreeobject *tree, + PyObject *left, PyObject *right, + PyObject **lvp, PyObject **rvp) +{ + assert(tree->cmpkey != NULL); + *lvp = PyObject_CallFunctionObjArgs(tree->cmpkey, left, NULL); + if (*lvp == NULL) + return -1; + *rvp = PyObject_CallFunctionObjArgs(tree->cmpkey, right, NULL); + if (*rvp == NULL) { + Py_DECREF(*lvp); + return -1; + } + return 0; +} + +/* allocation/gc */ + +static PyObject * +rbtree_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + static const char *kwargs[] = {"cmp", "key", "reverse", NULL}; + PyObject *cmp = NULL, *key = NULL; + rbtreeobject *rbtree; + int reverse = 0; + + if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OOi:rbtree", + (char **)kwargs, &cmp, &key, &reverse)) + return NULL; + + if (cmp == Py_None) + cmp = NULL; + if (key == Py_None) + key = NULL; + + if (cmp != NULL && key != NULL) { + PyErr_SetString(PyExc_ValueError, + "can't set both of cmp and key at a time"); + return NULL; + } + if (cmp != NULL && !PyCallable_Check(cmp)) { + PyErr_SetString(PyExc_TypeError, "cmp must be callable"); + return NULL; + } + if (key != NULL && !PyCallable_Check(key)) { + PyErr_SetString(PyExc_TypeError, "key must be callable"); + return NULL; + } + + rbtree = (rbtreeobject *)type->tp_alloc(type, 0); + if (rbtree == NULL) + return NULL; + + rbtree->nodemap = PyDict_New(); + if (rbtree->nodemap == NULL) { + rbtree->ob_type->tp_free(rbtree); + return NULL; + } + + if (cmp != NULL) { + rbtree->cmpkey = cmp; + Py_INCREF(cmp); + rbtree->cmpprep = rbtree_cmpprep_cmpfunc; + } + else if (key != NULL) { + rbtree->cmpkey = key; + Py_INCREF(key); + rbtree->cmpprep = rbtree_cmpprep_keyfunc; + } + else { + rbtree->cmpkey = NULL; + rbtree->cmpprep = NULL; + } + + rbtree->root = NULL; + rbtree->nvalues = 0; + rbtree->reverse = reverse; + rbtree->state = 0L; + + return (PyObject *)rbtree; +} + +static int +rbtree_init(PyObject *tree, PyObject *args, PyObject *kwds) +{ + return 0; +} + +static int +rbtree_traverse(rbtreeobject *tree, visitproc visit, void *arg) +{ + int err; + + err = visit(tree->nodemap, arg); + if (err) + return err; + + RBTREE_TRAVERSE_HEAD(tree->root) + /* keys are visited above already */ + Py_VISIT(_cur->value); + RBTREE_TRAVERSE_TAIL + + if (tree->cmpkey != NULL) + Py_VISIT(tree->nodemap); + + return 0; +} + +static long +rbtree_nohash(PyObject *self) +{ + PyErr_SetString(PyExc_TypeError, "rbtree objects are unhashable"); + return -1; +} + +static void +rbtree_dealloc(rbtreeobject *tree) +{ + PyObject_GC_UnTrack(tree); + + RBTREE_TRAVERSE_HEAD(tree->root) + rbtree_delete_node(tree, _cur); + RBTREE_TRAVERSE_TAIL + + Py_XDECREF(tree->cmpkey); + Py_DECREF(tree->nodemap); + tree->ob_type->tp_free(tree); +} + +/* type methods */ + +static Py_ssize_t +rbtree_len(rbtreeobject *tree) +{ + return tree->nvalues; +} + +static PyObject * +rbtree_subscript(rbtreeobject *tree, PyObject *key) +{ + PyObject *found; + struct rbtree_node *node; + + if (key == Py_None) { + PyErr_SetString(PyExc_TypeError, + "None is prohibited to use as a key."); + return NULL; + } + + found = PyDict_GetItem(tree->nodemap, key); + if (found == NULL) { + PyErr_SetObject(PyExc_KeyError, key); + return NULL; + } + + assert(PyCObject_Check(found)); + node = (struct rbtree_node *)PyCObject_AsVoidPtr(found); + Py_INCREF(node->value); + return node->value; +} + +static int +rbtree_ass_sub(rbtreeobject *tree, PyObject *key, PyObject *value) +{ + + if (key == Py_None) { + PyErr_SetString(PyExc_TypeError, + "None is prohibited to use as a key."); + return -1; + } + + RBTREE_LOCK_IFUN(tree); + + if (value == NULL) { /* del */ + int r = PyDict_DelItem(tree->nodemap, key); + RBTREE_UNLOCK(tree); + return r; + } + + if (PyObject_Hash(key) == -1) { + PyErr_SetString(PyExc_TypeError, "key is not hashable."); + RBTREE_UNLOCK(tree); + return -1; + } + + { + struct rbtree_node *r = rbtree_insert_node(tree, value, key); + RBTREE_UNLOCK(tree); + return r != NULL ? 0 : -1; + } +} + +static int +rbtree_contains(rbtreeobject *tree, PyObject *value) +{ + struct rbtree_node *node; + + RBTREE_LOCK_IFUN(tree); + + node = tree->root; + + while (node != NULL) { + int r; + + r = rbtree_compare_nodes(tree, value, node->value, Py_LT); + if (r == -1) + goto onError; + else if (r) { + node = node->left; + continue; + } + + r = rbtree_compare_nodes(tree, value, node->value, Py_NE); + if (r == -1) + goto onError; + else if (r) { + node = node->right; + continue; + } + + break; + } + + RBTREE_UNLOCK(tree); + return node != NULL; + + onError: + RBTREE_UNLOCK(tree); + return -1; +} + +/* member methods */ + +PyDoc_STRVAR(rbtree_insert_doc, +"T.insert(v) -> None. Add an element to the tree"); + +static PyObject * +rbtree_insert(rbtreeobject *tree, PyObject *value) +{ + struct rbtree_node *r; + + RBTREE_LOCK_PFUN(tree); + r = rbtree_insert_node(tree, value, NULL); + RBTREE_UNLOCK(tree); + if (r == NULL) + return NULL; + + Py_RETURN_NONE; +} + +PyDoc_STRVAR(rbtree_remove_doc, +"T.remove(v) -> None. Remove the value from the tree"); + +static PyObject * +rbtree_remove(rbtreeobject *tree, PyObject *value) +{ + struct rbtree_node *node; + + RBTREE_LOCK_PFUN(tree); + node = tree->root; + + while (node != NULL) { + int r; + + r = rbtree_compare_nodes(tree, value, node->value, Py_LT); + if (r == -1) + goto onError; + else if (r) { + node = node->left; + continue; + } + + r = rbtree_compare_nodes(tree, value, node->value, Py_NE); + if (r == -1) + goto onError; + else if (r) { + node = node->right; + continue; + } + + break; + } + + if (node == NULL) { + PyErr_SetString(PyExc_ValueError, + "rbtree.remove(x): x not in list"); + goto onError; + } + + if (node->key == NULL) + rbtree_delete_free(tree, node); + else if (PyDict_DelItem(tree->nodemap, node->key) == -1) + goto onError; + + RBTREE_UNLOCK(tree); + Py_RETURN_NONE; + + onError: + RBTREE_UNLOCK(tree); + return NULL; +} + +PyDoc_STRVAR(rbtree_clear_doc, +"T.clear() -> None. Remove all items from the tree"); + +static PyObject * +rbtree_clear(rbtreeobject *tree) +{ + RBTREE_LOCK_PFUN(tree); + + RBTREE_TRAVERSE_HEAD(tree->root) + rbtree_delete_node(tree, _cur); + RBTREE_TRAVERSE_TAIL + + RBTREE_UNLOCK(tree); + Py_RETURN_NONE; +} + +PyDoc_STRVAR(rbtree_copy_doc, +"T.copy() -> Return a shallow copy of a tree."); + +static PyObject * +rbtree_copy(rbtreeobject *tree) +{ + PyObject *ntree, *cmparg, *keyarg; + + RBTREE_LOCK_PFUN(tree); + + cmparg = keyarg = Py_None; + if (tree->cmpprep == rbtree_cmpprep_keyfunc) + keyarg = tree->cmpkey; + else if (tree->cmpprep == rbtree_cmpprep_cmpfunc) + cmparg = tree->cmpkey; + + ntree = PyObject_CallFunctionObjArgs((PyObject *)(tree->ob_type), + cmparg, keyarg, + tree->reverse ? Py_True : Py_False, NULL); + if (ntree == NULL) { + RBTREE_UNLOCK(tree); + return NULL; + } + + RBTREE_TRAVERSE_HEAD(tree->root) + if (rbtree_insert_node((rbtreeobject *)ntree, _cur->value, + _cur->key) == NULL) { + RBTREE_UNLOCK(tree); + Py_DECREF(ntree); + return NULL; + } + RBTREE_TRAVERSE_TAIL + + RBTREE_UNLOCK(tree); + return ntree; +} + +PyDoc_STRVAR(rbtree_has_key_doc, +"T.has_key(k) -> True if T has a key k, else False"); + +static PyObject * +rbtree_has_key(rbtreeobject *tree, PyObject *key) +{ + if (key == Py_None) { + PyErr_SetString(PyExc_TypeError, + "None is prohibited to use as a key."); + return NULL; + } + + if (PyDict_GetItem(tree->nodemap, key) != NULL) + Py_RETURN_TRUE; + else + Py_RETURN_FALSE; +} + +PyDoc_STRVAR(rbtree_values_doc, +"T.values() -> list of T's values"); + +static PyObject * +rbtree_values(rbtreeobject *tree) +{ + PyObject *l; + Py_ssize_t idx; + + l = PyList_New(tree->nvalues); + if (l == NULL) + return NULL; + + idx = 0; + + RBTREE_TRAVERSE_HEAD(tree->root) + PyList_SET_ITEM(l, idx++, _cur->value); + Py_INCREF(_cur->value); + RBTREE_TRAVERSE_TAIL + + return l; +} + +PyDoc_STRVAR(rbtree_keys_doc, +"T.keys() -> list of T's keys."); + +static PyObject * +rbtree_keys(rbtreeobject *tree) +{ + PyObject *l; + Py_ssize_t idx; + + l = PyList_New(tree->nvalues); + if (l == NULL) + return NULL; + + idx = 0; + + RBTREE_TRAVERSE_HEAD(tree->root) + if (_cur->key != NULL) { + PyList_SET_ITEM(l, idx++, _cur->key); + Py_INCREF(_cur->key); + } + else { + PyList_SET_ITEM(l, idx++, Py_None); + Py_INCREF(Py_None); + } + RBTREE_TRAVERSE_TAIL + + return l; +} + +PyDoc_STRVAR(rbtree_items_doc, +"T.items() -> list of T's (key, value) pairs, as 2-tuples"); + +static PyObject * +rbtree_items(rbtreeobject *tree) +{ + PyObject *l, *t; + Py_ssize_t idx; + + l = PyList_New(tree->nvalues); + if (l == NULL) + return NULL; + + idx = 0; + + RBTREE_TRAVERSE_HEAD(tree->root) + + t = rbtree_itemobj(_cur); + if (t == NULL) { + Py_DECREF(l); + return NULL; + } + PyList_SET_ITEM(l, idx++, t); + + RBTREE_TRAVERSE_TAIL + + return l; +} + +PyDoc_STRVAR(rbtree_nfirst_doc, +"T.nfirst(n) -> list containing the n values from the left-side of\n" +"the tree (smallest, in general)"); + +static PyObject * +rbtree_nfirst(rbtreeobject *tree, PyObject *args) +{ + PyObject *l; + Py_ssize_t idx, limit; + + if (!PyArg_ParseTuple(args, "n:nfirst", &limit)) + return NULL; + + if (limit > tree->nvalues) + limit = tree->nvalues; + + l = PyList_New(limit); + if (l == NULL) + return NULL; + + idx = 0; + + RBTREE_TRAVERSE_HEAD(tree->root) + if (idx >= limit) + break; + Py_INCREF(_cur->value); + PyList_SET_ITEM(l, idx++, _cur->value); + RBTREE_TRAVERSE_TAIL + + assert(idx == limit); + return l; +} + +PyDoc_STRVAR(rbtree_nfirstitems_doc, +"T.nfirstitems(n) -> list containing the n (key, value) pairs from\n" +"the left-side of the tree (smallest, in general)"); + +static PyObject * +rbtree_nfirstitems(rbtreeobject *tree, PyObject *args) +{ + PyObject *l, *t; + Py_ssize_t idx, limit; + + if (!PyArg_ParseTuple(args, "n:nfirstitems", &limit)) + return NULL; + + if (limit > tree->nvalues) + limit = tree->nvalues; + + l = PyList_New(limit); + if (l == NULL) + return NULL; + + idx = 0; + + RBTREE_TRAVERSE_HEAD(tree->root) + + if (idx >= limit) + break; + + t = rbtree_itemobj(_cur); + if (t == NULL) { + Py_DECREF(l); + return NULL; + } + PyList_SET_ITEM(l, idx++, t); + + RBTREE_TRAVERSE_TAIL + + assert(idx == limit); + return l; +} + +PyDoc_STRVAR(rbtree_nlast_doc, +"T.nlast(n) -> list containing the n values from the right-side of\n" +"the tree (largest, in general)"); + +static PyObject * +rbtree_nlast(rbtreeobject *tree, PyObject *args) +{ + PyObject *l; + Py_ssize_t idx, limit; + + if (!PyArg_ParseTuple(args, "n:nlast", &limit)) + return NULL; + + if (limit > tree->nvalues) + limit = tree->nvalues; + + l = PyList_New(limit); + if (l == NULL) + return NULL; + + idx = 0; + + RBTREE_TRAVERSE_REVERSE_HEAD(tree->root) + if (idx >= limit) + break; + Py_INCREF(_cur->value); + PyList_SET_ITEM(l, idx++, _cur->value); + RBTREE_TRAVERSE_REVERSE_TAIL + + assert(idx == limit); + return l; +} + +PyDoc_STRVAR(rbtree_nlastitems_doc, +"T.nlastitems(n) -> list containing the n (key, value) pairs from\n" +"the right-side of the tree (largest, in general)"); + +static PyObject * +rbtree_nlastitems(rbtreeobject *tree, PyObject *args) +{ + PyObject *l, *t; + Py_ssize_t idx, limit; + + if (!PyArg_ParseTuple(args, "n:nlastitems", &limit)) + return NULL; + + if (limit > tree->nvalues) + limit = tree->nvalues; + + l = PyList_New(limit); + if (l == NULL) + return NULL; + + idx = 0; + + RBTREE_TRAVERSE_REVERSE_HEAD(tree->root) + + if (idx >= limit) + break; + + t = rbtree_itemobj(_cur); + if (t == NULL) { + Py_DECREF(l); + return NULL; + } + PyList_SET_ITEM(l, idx++, t); + + RBTREE_TRAVERSE_REVERSE_TAIL + + assert(idx == limit); + return l; +} + +static struct rbtree_node * +_rbtree_locate_cutline(rbtreeobject *tree, PyObject *criterion, + int fromleft, int *include_equal) +{ + enum { NOWALK, LEFTDOWN, RIGHTDOWN } pathtrail; + struct rbtree_node *node, *prev; + + node = tree->root; + prev = NULL; + pathtrail = NOWALK; + + while (node != NULL) { + int r; + + r = rbtree_compare_nodes(tree, criterion, node->value, Py_LT); + if (r == -1) + return NULL; + else if (r) { + prev = node; + pathtrail = LEFTDOWN; + node = node->left; + continue; + } + + r = rbtree_compare_nodes(tree, criterion, node->value, Py_NE); + if (r == -1) + return NULL; + else if (r) { + prev = node; + pathtrail = RIGHTDOWN; + node = node->right; + continue; + } + + break; + } + + if (node == NULL) { /* not found */ + assert(pathtrail != NOWALK); + + node = prev; + if ((pathtrail == LEFTDOWN && fromleft) || + (pathtrail == RIGHTDOWN && !fromleft)) + *include_equal = 0; + else + *include_equal = 1; + } + + return node; +} + +PyDoc_STRVAR(rbtree_popleft_doc, +"T.popleft(v, include_equal=False) -> list containing the values\n" +"lesser than v and pop them from the tree. If include_equal is\n" +"True, the value that equals v are in effect, too."); + +static PyObject * +rbtree_popleft(rbtreeobject *tree, PyObject *args) +{ + PyObject *l, *criterion; + struct rbtree_node *cutline; + int include_equal = 0; + + if (!PyArg_ParseTuple(args, "O|i:popleft", &criterion, &include_equal)) + return NULL; + + if (tree->nvalues == 0) + return PyList_New(0); + + RBTREE_LOCK_PFUN(tree); + + cutline = _rbtree_locate_cutline(tree, criterion, 1, &include_equal); + if (cutline == NULL) + goto onError; + + l = PyList_New(0); + if (l == NULL) + goto onError; + + RBTREE_TRAVERSE_HEAD(tree->root) + + if (_cur != cutline || include_equal) { + if (PyList_Append(l, _cur->value) == -1 || + rbtree_delete_node(tree, _cur) == -1) { + Py_DECREF(l); + goto onError; + } + } + if (_cur == cutline) + break; + + RBTREE_TRAVERSE_TAIL + + RBTREE_UNLOCK(tree); + return l; + + onError: + RBTREE_UNLOCK(tree); + return NULL; +} + +PyDoc_STRVAR(rbtree_popleftitems_doc, +"T.popleftitems(v, include_equal=False) -> list containing the (key,\n" +"value) pairs lesser than v and pop them from the tree. If\n" +"include_equal is True, the value that equals v are in effect,\n" +"too."); + +static PyObject * +rbtree_popleftitems(rbtreeobject *tree, PyObject *args) +{ + PyObject *l, *criterion; + struct rbtree_node *cutline; + int include_equal = 0; + + if (!PyArg_ParseTuple(args, "O|i:popleftitems", &criterion, + &include_equal)) + return NULL; + + if (tree->nvalues == 0) + return PyList_New(0); + + RBTREE_LOCK_PFUN(tree); + + cutline = _rbtree_locate_cutline(tree, criterion, 1, &include_equal); + if (cutline == NULL) + goto onError; + + l = PyList_New(0); + if (l == NULL) + goto onError; + + RBTREE_TRAVERSE_HEAD(tree->root) + + if (_cur != cutline || include_equal) { + PyObject *el = rbtree_itemobj(_cur); + if (el == NULL || PyList_Append(l, el) == -1 || + rbtree_delete_node(tree, _cur) == -1) { + Py_DECREF(l); + Py_XDECREF(el); + goto onError; + } + Py_DECREF(el); + } + if (_cur == cutline) + break; + + RBTREE_TRAVERSE_TAIL + + RBTREE_UNLOCK(tree); + return l; + + onError: + RBTREE_UNLOCK(tree); + return NULL; +} + +PyDoc_STRVAR(rbtree_popright_doc, +"T.popright(v, include_equal=False) -> list containing the values\n" +"greater than v and pop them from the tree. If include_equal is\n" +"True, the value that equals v are in effect, too."); + +static PyObject * +rbtree_popright(rbtreeobject *tree, PyObject *args) +{ + PyObject *l, *criterion; + struct rbtree_node *cutline; + int include_equal = 0; + + if (!PyArg_ParseTuple(args, "O|i:popright", &criterion, &include_equal)) + return NULL; + + if (tree->nvalues == 0) + return PyList_New(0); + + RBTREE_LOCK_PFUN(tree); + + cutline = _rbtree_locate_cutline(tree, criterion, 0, &include_equal); + if (cutline == NULL) + goto onError; + + l = PyList_New(0); + if (l == NULL) + goto onError; + + RBTREE_TRAVERSE_REVERSE_HEAD(tree->root) + + if (_cur != cutline || include_equal) { + if (PyList_Append(l, _cur->value) == -1 || + rbtree_delete_node(tree, _cur) == -1) { + Py_DECREF(l); + goto onError; + } + } + if (_cur == cutline) + break; + + RBTREE_TRAVERSE_REVERSE_TAIL + + RBTREE_UNLOCK(tree); + return l; + + onError: + RBTREE_UNLOCK(tree); + return NULL; +} + +PyDoc_STRVAR(rbtree_poprightitems_doc, +"T.poprightitems(v, include_equal=False) -> list containing the\n" +"(key, value) pairs greater than v and pop them from the tree.\n" +"If include_equal is True, the value that equals v are in effect,\n" +"too."); + +static PyObject * +rbtree_poprightitems(rbtreeobject *tree, PyObject *args) +{ + PyObject *l, *criterion; + struct rbtree_node *cutline; + int include_equal = 0; + + if (!PyArg_ParseTuple(args, "O|i:poprightitems", &criterion, + &include_equal)) + return NULL; + + if (tree->nvalues == 0) + return PyList_New(0); + + RBTREE_LOCK_PFUN(tree); + + cutline = _rbtree_locate_cutline(tree, criterion, 0, &include_equal); + if (cutline == NULL) + goto onError; + + l = PyList_New(0); + if (l == NULL) + goto onError; + + RBTREE_TRAVERSE_REVERSE_HEAD(tree->root) + + if (_cur != cutline || include_equal) { + PyObject *el = rbtree_itemobj(_cur); + if (el == NULL || PyList_Append(l, el) == -1 || + rbtree_delete_node(tree, _cur) == -1) { + Py_DECREF(l); + Py_XDECREF(el); + goto onError; + } + Py_DECREF(el); + } + if (_cur == cutline) + break; + + RBTREE_TRAVERSE_REVERSE_TAIL + + RBTREE_UNLOCK(tree); + return l; + + onError: + RBTREE_UNLOCK(tree); + return NULL; +} + +#ifndef NDEBUG +PyDoc_STRVAR(rbtree_graph_doc, +"T.graph() -> None. Prints a graph that shows internal tree layout\n" +"for the debugging purpose"); + +static void +rbtree_graph_visit(struct rbtree_node *node, Py_ssize_t depth, const char *tag) +{ + Py_ssize_t i; + + for (i = 0; i < depth * 2; i++) + putc(' ', stdout); + + printf("%s: ", tag); + + if (node->key != NULL) { + PyObject_Print(node->key, stdout, 0); + printf(" => "); + } + PyObject_Print(node->value, stdout, 0); + if (node->color == BLACK) + printf(" (black)\n"); + else + printf(" (red)\n"); + + if (node->left != NULL) + rbtree_graph_visit(node->left, depth+1, "LEFT"); + + if (node->right != NULL) + rbtree_graph_visit(node->right, depth+1, "RIGHT"); +} + +static PyObject * +rbtree_graph(rbtreeobject *tree) +{ + if (tree->root == NULL) + printf("Empty\n"); + else + rbtree_graph_visit(tree->root, 0, "ROOT"); + + Py_RETURN_NONE; +} +#endif + +static PyObject *rbtree_iter(rbtreeobject *rbtree); +static PyObject *rbtree_reviter(rbtreeobject *rbtree); +PyDoc_STRVAR(rbtree_reversed_doc, + "T.__reversed__() -- return a reverse iterator over the tree"); + +static PyMethodDef rbtree_methods[] = { + {"insert", (PyCFunction)rbtree_insert, + METH_O, rbtree_insert_doc}, + {"remove", (PyCFunction)rbtree_remove, + METH_O, rbtree_remove_doc}, + {"clear", (PyCFunction)rbtree_clear, + METH_NOARGS, rbtree_clear_doc}, + {"has_key", (PyCFunction)rbtree_has_key, + METH_O, rbtree_has_key_doc}, + {"values", (PyCFunction)rbtree_values, + METH_NOARGS, rbtree_values_doc}, + {"keys", (PyCFunction)rbtree_keys, + METH_NOARGS, rbtree_keys_doc}, + {"items", (PyCFunction)rbtree_items, + METH_NOARGS, rbtree_items_doc}, + {"nfirst", (PyCFunction)rbtree_nfirst, + METH_VARARGS, rbtree_nfirst_doc}, + {"nfirstitems", (PyCFunction)rbtree_nfirstitems, + METH_VARARGS, rbtree_nfirstitems_doc}, + {"nlast", (PyCFunction)rbtree_nlast, + METH_VARARGS, rbtree_nlast_doc}, + {"nlastitems", (PyCFunction)rbtree_nlastitems, + METH_VARARGS, rbtree_nlastitems_doc}, + {"popleft", (PyCFunction)rbtree_popleft, + METH_VARARGS, rbtree_popleft_doc}, + {"popleftitems", (PyCFunction)rbtree_popleftitems, + METH_VARARGS, rbtree_popleftitems_doc}, + {"popright", (PyCFunction)rbtree_popright, + METH_VARARGS, rbtree_popright_doc}, + {"poprightitems", (PyCFunction)rbtree_poprightitems, + METH_VARARGS, rbtree_poprightitems_doc}, +#ifndef NDEBUG + {"graph", (PyCFunction)rbtree_graph, + METH_NOARGS, rbtree_graph_doc}, +#endif + {"__copy__", (PyCFunction)rbtree_copy, + METH_NOARGS, rbtree_copy_doc}, + {"__reversed__", (PyCFunction)rbtree_reviter, + METH_NOARGS, rbtree_reversed_doc}, + {NULL, NULL,}, +}; + +static PySequenceMethods rbtree_as_sequence = { + (lenfunc)rbtree_len, /* sq_length */ + (binaryfunc)0, /* sq_concat */ + 0, /* sq_repeat */ + 0, /* sq_item */ + 0, /* sq_slice */ + 0, /* sq_ass_item */ + 0, /* sq_ass_slice */ + (objobjproc)rbtree_contains, /* sq_contains */ + (binaryfunc)0, /* sq_inplace_concat */ +}; + +static PyMappingMethods rbtree_as_mapping = { + 0, /* mp_length */ + (binaryfunc)rbtree_subscript, /* mp_subscript */ + (objobjargproc)rbtree_ass_sub, /* mp_ass_subscript */ +}; + +PyTypeObject rbtree_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "collections.rbtree", /* tp_name */ + sizeof(rbtreeobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)rbtree_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_compare */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + &rbtree_as_sequence, /* tp_as_sequence */ + &rbtree_as_mapping, /* tp_as_mapping */ + rbtree_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_HAVE_GC,/* tp_flags */ + 0, /* tp_doc */ + (traverseproc)rbtree_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)rbtree_iter, /* tp_iter */ + 0, /* tp_iternext */ + rbtree_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 */ + rbtree_init, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + rbtree_new, /* tp_new */ + PyObject_GC_Del, /* tp_free */ +}; + +/*********************** Rbtree Iterator *************************/ + +typedef struct { + PyObject_HEAD + rbtreeobject *tree; + struct rbtree_node *prev, *next; + long state; /* state when the iterator is created */ +} rbtreeiterobject; + +PyTypeObject rbtreeiter_type; + +static PyObject * +rbtree_iter(rbtreeobject *rbtree) +{ + rbtreeiterobject *it; + + it = PyObject_New(rbtreeiterobject, &rbtreeiter_type); + if (it == NULL) + return NULL; + Py_INCREF(rbtree); + it->tree = rbtree; + it->prev = NULL; + it->next = rbtree->root; + it->state = rbtree->state; + return (PyObject *)it; +} + +static void +rbtreeiter_dealloc(rbtreeiterobject *rio) +{ + Py_XDECREF(rio->tree); + rio->ob_type->tp_free(rio); +} + +static PyObject * +rbtreeiter_next(rbtreeiterobject *it) +{ + struct rbtree_node *prev, *next, *cur; + int found; + + if (it->next == NULL) + return NULL; + + if (it->tree->state != it->state) { + it->next = NULL; + PyErr_SetString(PyExc_RuntimeError, + "rbtree mutated during iteration"); + return NULL; + } + + cur = it->prev; + next = it->next; + found = 0; + + while (next != NULL) { + prev = cur; + cur = next; + + if (prev == cur->parent && cur->left != NULL) { + next = cur->left; + continue; + } + + next = cur->parent; + if (prev != cur->right || prev == NULL) { + if (cur->right != NULL) + next = cur->right; + found = 1; + break; + } + } + + if (!found) + return NULL; /* StopIteration */ + + it->prev = cur; + it->next = next; + + Py_INCREF(cur->value); + return cur->value; +} + +PyTypeObject rbtreeiter_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "rbtree_iterator", /* tp_name */ + sizeof(rbtreeiterobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)rbtreeiter_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)rbtreeiter_next, /* tp_iternext */ +}; + +/******************* Rbtree Reverse Iterator *********************/ + +typedef struct { + PyObject_HEAD + rbtreeobject *tree; + struct rbtree_node *prev, *next; + long state; /* state when the iterator is created */ +} rbtreereviterobject; + +PyTypeObject rbtreereviter_type; + +static PyObject * +rbtree_reviter(rbtreeobject *rbtree) +{ + rbtreereviterobject *it; + + it = PyObject_New(rbtreereviterobject, &rbtreereviter_type); + if (it == NULL) + return NULL; + Py_INCREF(rbtree); + it->tree = rbtree; + it->prev = NULL; + it->next = rbtree->root; + it->state = rbtree->state; + return (PyObject *)it; +} + +static void +rbtreereviter_dealloc(rbtreereviterobject *rio) +{ + Py_XDECREF(rio->tree); + rio->ob_type->tp_free(rio); +} + +static PyObject * +rbtreereviter_next(rbtreereviterobject *it) +{ + struct rbtree_node *prev, *next, *cur; + int found; + + if (it->next == NULL) + return NULL; + + if (it->tree->state != it->state) { + it->next = NULL; + PyErr_SetString(PyExc_RuntimeError, + "rbtree mutated during iteration"); + return NULL; + } + + cur = it->prev; + next = it->next; + found = 0; + + while (next != NULL) { + prev = cur; + cur = next; + + if (prev == cur->parent && cur->right != NULL) { + next = cur->right; + continue; + } + + next = cur->parent; + if (prev != cur->left || prev == NULL) { + if (cur->left != NULL) + next = cur->left; + found = 1; + break; + } + } + + if (!found) + return NULL; /* StopIteration */ + + it->prev = cur; + it->next = next; + + Py_INCREF(cur->value); + return cur->value; +} + +PyTypeObject rbtreereviter_type = { + PyObject_HEAD_INIT(NULL) + 0, /* ob_size */ + "rbtree_reverse_iterator", /* tp_name */ + sizeof(rbtreereviterobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)rbtreereviter_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)rbtreereviter_next, /* tp_iternext */ +}; + + /* module level code ********************************************************/ PyDoc_STRVAR(module_doc, @@ -1334,27 +3167,36 @@ initcollections(void) { PyObject *m; + int i; + struct { + PyTypeObject *type; + const char *name; + } typelist[] = { + {&deque_type, "deque"}, + {&defdict_type, "defaultdict"}, + {&dequeiter_type, NULL}, + {&dequereviter_type, NULL}, + {&rbtree_type, "rbtree"}, + {&rbtreeiter_type, NULL}, + {&rbtreereviter_type, NULL}, + {NULL}, + }; 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); + for (i = 0; typelist[i].type != NULL; i++) { + if (PyType_Ready(typelist[i].type) < 0) + return; - if (PyType_Ready(&dequeiter_type) < 0) - return; + if (typelist[i].name != NULL) { + Py_INCREF(typelist[i].type); + PyModule_AddObject(m, typelist[i].name, + (PyObject *)typelist[i].type); + } + } - if (PyType_Ready(&dequereviter_type) < 0) - return; - return; }