diff options
Diffstat (limited to 'Modules/_collectionsmodule.c')
| -rw-r--r-- | Modules/_collectionsmodule.c | 219 |
1 files changed, 176 insertions, 43 deletions
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index 54c1343..34a1a90 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -413,10 +413,9 @@ deque_inplace_concat(dequeobject *deque, PyObject *other) static int _deque_rotate(dequeobject *deque, Py_ssize_t n) { - Py_ssize_t i, len=deque->len, halflen=(len+1)>>1; - PyObject *item, *rv; + Py_ssize_t m, len=deque->len, halflen=len>>1; - if (len == 0) + if (len <= 1) return 0; if (n > halflen || n < -halflen) { n %= len; @@ -425,24 +424,79 @@ _deque_rotate(dequeobject *deque, Py_ssize_t n) else if (n < -halflen) n += len; } + assert(len > 1); + assert(-halflen <= n && n <= halflen); - 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); + deque->state++; + while (n > 0) { + if (deque->leftindex == 0) { + block *b = newblock(NULL, deque->leftblock, len); + if (b == NULL) + return -1; + assert(deque->leftblock->leftlink == NULL); + deque->leftblock->leftlink = b; + deque->leftblock = b; + deque->leftindex = BLOCKLEN; + } + assert(deque->leftindex > 0); + + m = n; + if (m > deque->rightindex + 1) + m = deque->rightindex + 1; + if (m > deque->leftindex) + m = deque->leftindex; + assert (m > 0 && m <= len); + memcpy(&deque->leftblock->data[deque->leftindex - m], + &deque->rightblock->data[deque->rightindex + 1 - m], + m * sizeof(PyObject *)); + deque->rightindex -= m; + deque->leftindex -= m; + n -= m; + + if (deque->rightindex == -1) { + block *prevblock = deque->rightblock->leftlink; + assert(deque->rightblock != NULL); + assert(deque->leftblock != deque->rightblock); + freeblock(deque->rightblock); + prevblock->rightlink = NULL; + deque->rightblock = prevblock; + deque->rightindex = BLOCKLEN - 1; + } } - 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); + while (n < 0) { + if (deque->rightindex == BLOCKLEN - 1) { + block *b = newblock(deque->rightblock, NULL, len); + if (b == NULL) + return -1; + assert(deque->rightblock->rightlink == NULL); + deque->rightblock->rightlink = b; + deque->rightblock = b; + deque->rightindex = -1; + } + assert (deque->rightindex < BLOCKLEN - 1); + + m = -n; + if (m > BLOCKLEN - deque->leftindex) + m = BLOCKLEN - deque->leftindex; + if (m > BLOCKLEN - 1 - deque->rightindex) + m = BLOCKLEN - 1 - deque->rightindex; + assert (m > 0 && m <= len); + memcpy(&deque->rightblock->data[deque->rightindex + 1], + &deque->leftblock->data[deque->leftindex], + m * sizeof(PyObject *)); + deque->leftindex += m; + deque->rightindex += m; + n += m; + + if (deque->leftindex == BLOCKLEN) { + block *nextblock = deque->leftblock->rightlink; + assert(deque->leftblock != deque->rightblock); + freeblock(deque->leftblock); + assert(nextblock != NULL); + nextblock->leftlink = NULL; + deque->leftblock = nextblock; + deque->leftindex = 0; + } } return 0; } @@ -588,7 +642,7 @@ deque_remove(dequeobject *deque, PyObject *value) PyDoc_STRVAR(remove_doc, "D.remove(value) -- remove first occurrence of value."); -static int +static void deque_clear(dequeobject *deque) { PyObject *item; @@ -601,7 +655,6 @@ deque_clear(dequeobject *deque) assert(deque->leftblock == deque->rightblock && deque->leftindex - 1 == deque->rightindex && deque->len == 0); - return 0; } static PyObject * @@ -704,10 +757,7 @@ deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v) static PyObject * deque_clearmethod(dequeobject *deque) { - int rv; - - rv = deque_clear(deque); - assert (rv != -1); + deque_clear(deque); Py_RETURN_NONE; } @@ -767,8 +817,9 @@ static PyObject * deque_reduce(dequeobject *deque) { PyObject *dict, *result, *aslist; + _Py_IDENTIFIER(__dict__); - dict = PyObject_GetAttrString((PyObject *)deque, "__dict__"); + dict = _PyObject_GetAttrId((PyObject *)deque, &PyId___dict__); if (dict == NULL) PyErr_Clear(); aslist = PySequence_List((PyObject *)deque); @@ -832,8 +883,7 @@ deque_richcompare(PyObject *v, PyObject *w, int op) if (!PyObject_TypeCheck(v, &deque_type) || !PyObject_TypeCheck(w, &deque_type)) { - Py_INCREF(Py_NotImplemented); - return Py_NotImplemented; + Py_RETURN_NOTIMPLEMENTED; } /* Shortcuts */ @@ -1141,6 +1191,35 @@ dequeiter_next(dequeiterobject *it) } static PyObject * +dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + Py_ssize_t i, index=0; + PyObject *deque; + dequeiterobject *it; + if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index)) + return NULL; + assert(type == &dequeiter_type); + + it = (dequeiterobject*)deque_iter((dequeobject *)deque); + if (!it) + return NULL; + /* consume items from the queue */ + for(i=0; i<index; i++) { + PyObject *item = dequeiter_next(it); + if (item) { + Py_DECREF(item); + } else { + if (it->counter) { + Py_DECREF(it); + return NULL; + } else + break; + } + } + return (PyObject*)it; +} + +static PyObject * dequeiter_len(dequeiterobject *it) { return PyLong_FromSsize_t(it->counter); @@ -1148,14 +1227,21 @@ dequeiter_len(dequeiterobject *it) PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); +static PyObject * +dequeiter_reduce(dequeiterobject *it) +{ + return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, it->deque->len - it->counter); +} + static PyMethodDef dequeiter_methods[] = { {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc}, + {"__reduce__", (PyCFunction)dequeiter_reduce, METH_NOARGS, reduce_doc}, {NULL, NULL} /* sentinel */ }; static PyTypeObject dequeiter_type = { PyVarObject_HEAD_INIT(NULL, 0) - "deque_iterator", /* tp_name */ + "_collections._deque_iterator", /* tp_name */ sizeof(dequeiterobject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ @@ -1183,6 +1269,16 @@ static PyTypeObject dequeiter_type = { PyObject_SelfIter, /* tp_iter */ (iternextfunc)dequeiter_next, /* tp_iternext */ dequeiter_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 */ + 0, /* tp_init */ + 0, /* tp_alloc */ + dequeiter_new, /* tp_new */ 0, }; @@ -1236,9 +1332,38 @@ dequereviter_next(dequeiterobject *it) return item; } +static PyObject * +dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + Py_ssize_t i, index=0; + PyObject *deque; + dequeiterobject *it; + if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index)) + return NULL; + assert(type == &dequereviter_type); + + it = (dequeiterobject*)deque_reviter((dequeobject *)deque); + if (!it) + return NULL; + /* consume items from the queue */ + for(i=0; i<index; i++) { + PyObject *item = dequereviter_next(it); + if (item) { + Py_DECREF(item); + } else { + if (it->counter) { + Py_DECREF(it); + return NULL; + } else + break; + } + } + return (PyObject*)it; +} + static PyTypeObject dequereviter_type = { PyVarObject_HEAD_INIT(NULL, 0) - "deque_reverse_iterator", /* tp_name */ + "_collections._deque_reverse_iterator", /* tp_name */ sizeof(dequeiterobject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ @@ -1266,6 +1391,16 @@ static PyTypeObject dequereviter_type = { PyObject_SelfIter, /* tp_iter */ (iternextfunc)dequereviter_next, /* tp_iternext */ dequeiter_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 */ + 0, /* tp_init */ + 0, /* tp_alloc */ + dequereviter_new, /* tp_new */ 0, }; @@ -1354,13 +1489,15 @@ defdict_reduce(defdictobject *dd) PyObject *items; PyObject *iter; PyObject *result; + _Py_IDENTIFIER(items); + if (dd->default_factory == NULL || dd->default_factory == Py_None) args = PyTuple_New(0); else args = PyTuple_Pack(1, dd->default_factory); if (args == NULL) return NULL; - items = PyObject_CallMethod((PyObject *)dd, "items", "()"); + items = _PyObject_CallMethodId((PyObject *)dd, &PyId_items, "()"); if (items == NULL) { Py_DECREF(args); return NULL; @@ -1573,12 +1710,8 @@ _count_elements(PyObject *self, PyObject *args) if (PyDict_CheckExact(mapping)) { while (1) { key = PyIter_Next(it); - if (key == NULL) { - if (PyErr_Occurred() && PyErr_ExceptionMatches(PyExc_StopIteration)) - PyErr_Clear(); - else - break; - } + if (key == NULL) + break; oldval = PyDict_GetItem(mapping, key); if (oldval == NULL) { if (PyDict_SetItem(mapping, key, one) == -1) @@ -1596,12 +1729,8 @@ _count_elements(PyObject *self, PyObject *args) } else { while (1) { key = PyIter_Next(it); - if (key == NULL) { - if (PyErr_Occurred() && PyErr_ExceptionMatches(PyExc_StopIteration)) - PyErr_Clear(); - else - break; - } + if (key == NULL) + break; oldval = PyObject_GetItem(mapping, key); if (oldval == NULL) { if (!PyErr_Occurred() || !PyErr_ExceptionMatches(PyExc_KeyError)) @@ -1678,9 +1807,13 @@ PyInit__collections(void) if (PyType_Ready(&dequeiter_type) < 0) return NULL; + Py_INCREF(&dequeiter_type); + PyModule_AddObject(m, "_deque_iterator", (PyObject *)&dequeiter_type); if (PyType_Ready(&dequereviter_type) < 0) return NULL; + Py_INCREF(&dequereviter_type); + PyModule_AddObject(m, "_deque_reverse_iterator", (PyObject *)&dequereviter_type); return m; } |