diff options
Diffstat (limited to 'Modules/_collectionsmodule.c')
| -rw-r--r-- | Modules/_collectionsmodule.c | 182 |
1 files changed, 114 insertions, 68 deletions
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index 5dea8cb..487c765 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -209,7 +209,7 @@ deque_pop(dequeobject *deque, PyObject *unused) Py_SIZE(deque)--; deque->state++; - if (deque->rightindex == -1) { + if (deque->rightindex < 0) { if (Py_SIZE(deque)) { prevblock = deque->rightblock->leftlink; assert(deque->leftblock != deque->rightblock); @@ -371,6 +371,8 @@ static PyObject * deque_extend(dequeobject *deque, PyObject *iterable) { PyObject *it, *item; + PyObject *(*iternext)(PyObject *); + int trim = (deque->maxlen != -1); /* Handle case where id(deque) == id(iterable) */ if ((PyObject *)deque == iterable) { @@ -398,7 +400,8 @@ deque_extend(dequeobject *deque, PyObject *iterable) if (deque->maxlen == 0) return consume_iterator(it); - while ((item = PyIter_Next(it)) != NULL) { + iternext = *Py_TYPE(it)->tp_iternext; + while ((item = iternext(it)) != NULL) { deque->state++; if (deque->rightindex == BLOCKLEN - 1) { block *b = newblock(Py_SIZE(deque)); @@ -417,11 +420,16 @@ deque_extend(dequeobject *deque, PyObject *iterable) Py_SIZE(deque)++; deque->rightindex++; deque->rightblock->data[deque->rightindex] = item; - deque_trim_left(deque); + if (trim) + deque_trim_left(deque); } if (PyErr_Occurred()) { - Py_DECREF(it); - return NULL; + if (PyErr_ExceptionMatches(PyExc_StopIteration)) + PyErr_Clear(); + else { + Py_DECREF(it); + return NULL; + } } Py_DECREF(it); Py_RETURN_NONE; @@ -434,6 +442,8 @@ static PyObject * deque_extendleft(dequeobject *deque, PyObject *iterable) { PyObject *it, *item; + PyObject *(*iternext)(PyObject *); + int trim = (deque->maxlen != -1); /* Handle case where id(deque) == id(iterable) */ if ((PyObject *)deque == iterable) { @@ -461,7 +471,8 @@ deque_extendleft(dequeobject *deque, PyObject *iterable) if (deque->maxlen == 0) return consume_iterator(it); - while ((item = PyIter_Next(it)) != NULL) { + iternext = *Py_TYPE(it)->tp_iternext; + while ((item = iternext(it)) != NULL) { deque->state++; if (deque->leftindex == 0) { block *b = newblock(Py_SIZE(deque)); @@ -480,11 +491,16 @@ deque_extendleft(dequeobject *deque, PyObject *iterable) Py_SIZE(deque)++; deque->leftindex--; deque->leftblock->data[deque->leftindex] = item; - deque_trim_right(deque); + if (trim) + deque_trim_right(deque); } if (PyErr_Occurred()) { - Py_DECREF(it); - return NULL; + if (PyErr_ExceptionMatches(PyExc_StopIteration)) + PyErr_Clear(); + else { + Py_DECREF(it); + return NULL; + } } Py_DECREF(it); Py_RETURN_NONE; @@ -539,35 +555,9 @@ deque_concat(dequeobject *deque, PyObject *other) static void deque_clear(dequeobject *deque); static PyObject * -deque_repeat(dequeobject *deque, Py_ssize_t n) -{ - dequeobject *new_deque; - PyObject *result; - - /* XXX add a special case for when maxlen is defined */ - if (n < 0) - n = 0; - else if (n > 0 && Py_SIZE(deque) > MAX_DEQUE_LEN / n) - return PyErr_NoMemory(); - - new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL); - new_deque->maxlen = deque->maxlen; - - for ( ; n ; n--) { - result = deque_extend(new_deque, (PyObject *)deque); - if (result == NULL) { - Py_DECREF(new_deque); - return NULL; - } - Py_DECREF(result); - } - return (PyObject *)new_deque; -} - -static PyObject * deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) { - Py_ssize_t i, size; + Py_ssize_t i, m, size; PyObject *seq; PyObject *rv; @@ -583,10 +573,6 @@ deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) return (PyObject *)deque; } - if (size > MAX_DEQUE_LEN / n) { - return PyErr_NoMemory(); - } - if (size == 1) { /* common case, repeating a single element */ PyObject *item = deque->leftblock->data[deque->leftindex]; @@ -594,16 +580,43 @@ deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) if (deque->maxlen != -1 && n > deque->maxlen) n = deque->maxlen; - for (i = 0 ; i < n-1 ; i++) { - rv = deque_append(deque, item); - if (rv == NULL) - return NULL; - Py_DECREF(rv); + if (n > MAX_DEQUE_LEN) + return PyErr_NoMemory(); + + deque->state++; + for (i = 0 ; i < n-1 ; ) { + if (deque->rightindex == BLOCKLEN - 1) { + block *b = newblock(Py_SIZE(deque) + i); + if (b == NULL) { + Py_SIZE(deque) += i; + return NULL; + } + b->leftlink = deque->rightblock; + CHECK_END(deque->rightblock->rightlink); + deque->rightblock->rightlink = b; + deque->rightblock = b; + MARK_END(b->rightlink); + deque->rightindex = -1; + } + m = n - 1 - i; + if (m > BLOCKLEN - 1 - deque->rightindex) + m = BLOCKLEN - 1 - deque->rightindex; + i += m; + while (m--) { + deque->rightindex++; + Py_INCREF(item); + deque->rightblock->data[deque->rightindex] = item; + } } + Py_SIZE(deque) += i; Py_INCREF(deque); return (PyObject *)deque; } + if ((size_t)size > MAX_DEQUE_LEN / (size_t)n) { + return PyErr_NoMemory(); + } + seq = PySequence_List((PyObject *)deque); if (seq == NULL) return seq; @@ -621,6 +634,20 @@ deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) return (PyObject *)deque; } +static PyObject * +deque_repeat(dequeobject *deque, Py_ssize_t n) +{ + dequeobject *new_deque; + PyObject *rv; + + new_deque = (dequeobject *)deque_copy((PyObject *) deque); + if (new_deque == NULL) + return NULL; + rv = deque_inplace_repeat(new_deque, n); + Py_DECREF(new_deque); + return rv; +} + /* The rotate() method is part of the public API and is used internally as a primitive for other methods. @@ -704,7 +731,7 @@ _deque_rotate(dequeobject *deque, Py_ssize_t n) *(dest++) = *(src++); } while (--m); } - if (rightindex == -1) { + if (rightindex < 0) { assert(leftblock != rightblock); assert(b == NULL); b = rightblock; @@ -792,11 +819,10 @@ deque_reverse(dequeobject *deque, PyObject *unused) block *rightblock = deque->rightblock; Py_ssize_t leftindex = deque->leftindex; Py_ssize_t rightindex = deque->rightindex; - Py_ssize_t n = Py_SIZE(deque) / 2; - Py_ssize_t i; + Py_ssize_t n = Py_SIZE(deque) >> 1; PyObject *tmp; - for (i=0 ; i<n ; i++) { + while (n-- > 0) { /* Validate that pointers haven't met in the middle */ assert(leftblock != rightblock || leftindex < rightindex); CHECK_NOT_END(leftblock); @@ -816,7 +842,7 @@ deque_reverse(dequeobject *deque, PyObject *unused) /* Step backwards with the right block/index pair */ rightindex--; - if (rightindex == -1) { + if (rightindex < 0) { rightblock = rightblock->leftlink; rightindex = BLOCKLEN - 1; } @@ -833,20 +859,18 @@ deque_count(dequeobject *deque, PyObject *v) block *b = deque->leftblock; Py_ssize_t index = deque->leftindex; Py_ssize_t n = Py_SIZE(deque); - Py_ssize_t i; Py_ssize_t count = 0; size_t start_state = deque->state; PyObject *item; int cmp; - for (i=0 ; i<n ; i++) { + while (n--) { CHECK_NOT_END(b); item = b->data[index]; cmp = PyObject_RichCompareBool(item, v, Py_EQ); - if (cmp > 0) - count++; - else if (cmp < 0) + if (cmp < 0) return NULL; + count += cmp; if (start_state != deque->state) { PyErr_SetString(PyExc_RuntimeError, @@ -873,12 +897,11 @@ deque_contains(dequeobject *deque, PyObject *v) block *b = deque->leftblock; Py_ssize_t index = deque->leftindex; Py_ssize_t n = Py_SIZE(deque); - Py_ssize_t i; size_t start_state = deque->state; PyObject *item; int cmp; - for (i=0 ; i<n ; i++) { + while (n--) { CHECK_NOT_END(b); item = b->data[index]; cmp = PyObject_RichCompareBool(item, v, Py_EQ); @@ -1109,7 +1132,7 @@ deque_clear(dequeobject *deque) static int valid_index(Py_ssize_t i, Py_ssize_t limit) { - /* The cast to size_t let us use just a single comparison + /* The cast to size_t lets us use just a single comparison to check whether i is in the range: 0 <= i < limit */ return (size_t) i < (size_t) limit; } @@ -1256,11 +1279,34 @@ deque_traverse(dequeobject *deque, visitproc visit, void *arg) static PyObject * deque_copy(PyObject *deque) { - if (((dequeobject *)deque)->maxlen == -1) + dequeobject *old_deque = (dequeobject *)deque; + if (Py_TYPE(deque) == &deque_type) { + dequeobject *new_deque; + PyObject *rv; + + new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL); + if (new_deque == NULL) + return NULL; + new_deque->maxlen = old_deque->maxlen; + /* Fast path for the deque_repeat() common case where len(deque) == 1 */ + if (Py_SIZE(deque) == 1 && new_deque->maxlen != 0) { + PyObject *item = old_deque->leftblock->data[old_deque->leftindex]; + rv = deque_append(new_deque, item); + } else { + rv = deque_extend(new_deque, deque); + } + if (rv != NULL) { + Py_DECREF(rv); + return (PyObject *)new_deque; + } + Py_DECREF(new_deque); + return NULL; + } + if (old_deque->maxlen < 0) return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL); else return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi", - deque, ((dequeobject *)deque)->maxlen, NULL); + deque, old_deque->maxlen, NULL); } PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque."); @@ -1280,12 +1326,12 @@ deque_reduce(dequeobject *deque) return NULL; } if (dict == NULL) { - if (deque->maxlen == -1) + if (deque->maxlen < 0) 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) + if (deque->maxlen < 0) 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); @@ -1376,7 +1422,7 @@ deque_richcompare(PyObject *v, PyObject *w, int op) } Py_DECREF(x); Py_DECREF(y); - if (b == -1) + if (b < 0) goto done; } /* We reached the end of one deque or both */ @@ -1459,7 +1505,7 @@ deque_bool(dequeobject *deque) static PyObject * deque_get_maxlen(dequeobject *deque) { - if (deque->maxlen == -1) + if (deque->maxlen < 0) Py_RETURN_NONE; return PyLong_FromSsize_t(deque->maxlen); } @@ -1800,7 +1846,7 @@ dequereviter_next(dequeiterobject *it) item = it->b->data[it->index]; it->index--; it->counter--; - if (it->index == -1 && it->counter > 0) { + if (it->index < 0 && it->counter > 0) { CHECK_NOT_END(it->b->leftlink); it->b = it->b->leftlink; it->index = BLOCKLEN - 1; @@ -2229,13 +2275,13 @@ _count_elements(PyObject *self, PyObject *args) oldval = _PyDict_GetItem_KnownHash(mapping, key, hash); if (oldval == NULL) { - if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) == -1) + if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) < 0) goto done; } else { newval = PyNumber_Add(oldval, one); if (newval == NULL) goto done; - if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) == -1) + if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0) goto done; Py_CLEAR(newval); } @@ -2261,7 +2307,7 @@ _count_elements(PyObject *self, PyObject *args) Py_DECREF(oldval); if (newval == NULL) break; - if (PyObject_SetItem(mapping, key, newval) == -1) + if (PyObject_SetItem(mapping, key, newval) < 0) break; Py_CLEAR(newval); Py_DECREF(key); |