diff options
author | Armin Rigo <arigo@tunes.org> | 2004-10-02 13:59:34 (GMT) |
---|---|---|
committer | Armin Rigo <arigo@tunes.org> | 2004-10-02 13:59:34 (GMT) |
commit | 974d757af15c22049a2aaa8cecf1456cd79d6397 (patch) | |
tree | 1bae979021d1710798b4cc979b3dcdaa1cdfbcef /Modules/collectionsmodule.c | |
parent | 565ea5ae3701b3600cb7ac2f6405574b51c19ba7 (diff) | |
download | cpython-974d757af15c22049a2aaa8cecf1456cd79d6397.zip cpython-974d757af15c22049a2aaa8cecf1456cd79d6397.tar.gz cpython-974d757af15c22049a2aaa8cecf1456cd79d6397.tar.bz2 |
Upon insertion, if memory runs out, the deque was left in a corrupted state.
deque_item(): a performance bug: the linked list of blocks was followed
from the left in most cases, because the test (i < (deque->len >> 1)) was
after "i %= BLOCKLEN".
deque_clear(): replaced a call to deque_len() with deque->len; not sure what
this call was here for, nor if all compilers under the sun would inline it.
deque_traverse(): I belive that it could be called by the GC when the deque
has leftblock==rightblock==NULL, because it is tracked before the first block
is allocated (though closely before). Still, a C extension module subclassing
deque could provide its own tp_alloc that could trigger a GC collection after
the PyObject_GC_Track()...
deque_richcompare(): rewrote to cleanly check for end-of-iterations instead of
relying on deque.__iter__().next() to succeed exactly len(deque) times -- an
assumption which can break if deques are subclassed. Added a test.
I wonder if the length should be explicitely bounded to INT_MAX, with
OverflowErrors, as in listobject.c. On 64-bit machines, adding more than
INT_MAX in the deque will result in trouble. (Note to anyone/me fixing
this: carefully check for overflows if len is close to INT_MAX in the
following functions: deque_rotate(), deque_item(), deque_ass_item())
Diffstat (limited to 'Modules/collectionsmodule.c')
-rw-r--r-- | Modules/collectionsmodule.c | 68 |
1 files changed, 34 insertions, 34 deletions
diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c index da2486a..15530a7 100644 --- a/Modules/collectionsmodule.c +++ b/Modules/collectionsmodule.c @@ -108,19 +108,19 @@ deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds) static PyObject * deque_append(dequeobject *deque, PyObject *item) { - deque->rightindex++; - deque->len++; deque->state++; - if (deque->rightindex == BLOCKLEN) { + if (deque->rightindex == BLOCKLEN-1) { block *b = newblock(deque->rightblock, NULL); if (b == NULL) return NULL; assert(deque->rightblock->rightlink == NULL); deque->rightblock->rightlink = b; deque->rightblock = b; - deque->rightindex = 0; + deque->rightindex = -1; } Py_INCREF(item); + deque->len++; + deque->rightindex++; deque->rightblock->data[deque->rightindex] = item; Py_RETURN_NONE; } @@ -130,19 +130,19 @@ PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque."); static PyObject * deque_appendleft(dequeobject *deque, PyObject *item) { - deque->leftindex--; - deque->len++; deque->state++; - if (deque->leftindex == -1) { + if (deque->leftindex == 0) { block *b = newblock(NULL, deque->leftblock); if (b == NULL) return NULL; assert(deque->leftblock->leftlink == NULL); deque->leftblock->leftlink = b; deque->leftblock = b; - deque->leftindex = BLOCKLEN - 1; + deque->leftindex = BLOCKLEN; } Py_INCREF(item); + deque->len++; + deque->leftindex--; deque->leftblock->data[deque->leftindex] = item; Py_RETURN_NONE; } @@ -233,10 +233,8 @@ deque_extend(dequeobject *deque, PyObject *iterable) return NULL; while ((item = PyIter_Next(it)) != NULL) { - deque->rightindex++; - deque->len++; deque->state++; - if (deque->rightindex == BLOCKLEN) { + if (deque->rightindex == BLOCKLEN-1) { block *b = newblock(deque->rightblock, NULL); if (b == NULL) { Py_DECREF(item); @@ -246,8 +244,10 @@ deque_extend(dequeobject *deque, PyObject *iterable) assert(deque->rightblock->rightlink == NULL); deque->rightblock->rightlink = b; deque->rightblock = b; - deque->rightindex = 0; + deque->rightindex = -1; } + deque->len++; + deque->rightindex++; deque->rightblock->data[deque->rightindex] = item; } Py_DECREF(it); @@ -269,10 +269,8 @@ deque_extendleft(dequeobject *deque, PyObject *iterable) return NULL; while ((item = PyIter_Next(it)) != NULL) { - deque->leftindex--; - deque->len++; deque->state++; - if (deque->leftindex == -1) { + if (deque->leftindex == 0) { block *b = newblock(NULL, deque->leftblock); if (b == NULL) { Py_DECREF(item); @@ -282,8 +280,10 @@ deque_extendleft(dequeobject *deque, PyObject *iterable) assert(deque->leftblock->leftlink == NULL); deque->leftblock->leftlink = b; deque->leftblock = b; - deque->leftindex = BLOCKLEN - 1; + deque->leftindex = BLOCKLEN; } + deque->len++; + deque->leftindex--; deque->leftblock->data[deque->leftindex] = item; } Py_DECREF(it); @@ -365,7 +365,7 @@ deque_item(dequeobject *deque, int i) { block *b; PyObject *item; - int n; + int n, index=i; if (i < 0 || i >= deque->len) { PyErr_SetString(PyExc_IndexError, @@ -383,7 +383,7 @@ deque_item(dequeobject *deque, int i) i += deque->leftindex; n = i / BLOCKLEN; i %= BLOCKLEN; - if (i < (deque->len >> 1)) { + if (index < (deque->len >> 1)) { b = deque->leftblock; while (n--) b = b->rightlink; @@ -514,7 +514,6 @@ deque_traverse(dequeobject *deque, visitproc visit, void *arg) int index; int indexlo = deque->leftindex; - assert(deque->leftblock != NULL); for (b = deque->leftblock; b != NULL; b = b->rightlink) { const int indexhi = b == deque->rightblock ? deque->rightindex : @@ -642,7 +641,7 @@ static PyObject * deque_richcompare(PyObject *v, PyObject *w, int op) { PyObject *it1=NULL, *it2=NULL, *x, *y; - int i, b, vs, ws, minlen, cmp=-1; + int b, vs, ws, cmp=-1; if (!PyObject_TypeCheck(v, &deque_type) || !PyObject_TypeCheck(w, &deque_type)) { @@ -673,16 +672,13 @@ deque_richcompare(PyObject *v, PyObject *w, int op) it2 = PyObject_GetIter(w); if (it2 == NULL) goto done; - minlen = (vs < ws) ? vs : ws; - for (i=0 ; i < minlen ; i++) { + for (;;) { x = PyIter_Next(it1); - if (x == NULL) + if (x == NULL && PyErr_Occurred()) goto done; y = PyIter_Next(it2); - if (y == NULL) { - Py_DECREF(x); - goto done; - } + if (x == NULL || y == NULL) + break; b = PyObject_RichCompareBool(x, y, Py_EQ); if (b == 0) { cmp = PyObject_RichCompareBool(x, y, op); @@ -695,14 +691,18 @@ deque_richcompare(PyObject *v, PyObject *w, int op) if (b == -1) goto done; } - /* Elements are equal through minlen. The longest input is the greatest */ + /* 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 = vs < ws; break; - case Py_LE: cmp = vs <= ws; break; - case Py_EQ: cmp = vs == ws; break; - case Py_NE: cmp = vs != ws; break; - case Py_GT: cmp = vs > ws; break; - case Py_GE: cmp = vs >= ws; break; + 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: |