diff options
Diffstat (limited to 'Modules')
| -rw-r--r-- | Modules/_heapqmodule.c | 40 |
1 files changed, 34 insertions, 6 deletions
diff --git a/Modules/_heapqmodule.c b/Modules/_heapqmodule.c index c8db509..0fe64ce 100644 --- a/Modules/_heapqmodule.c +++ b/Modules/_heapqmodule.c @@ -11,12 +11,14 @@ annotated by François Pinard, and converted to C by Raymond Hettinger. static int _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) { - PyObject *newitem, *parent; + PyObject *newitem, *parent, *olditem; int cmp; Py_ssize_t parentpos; + Py_ssize_t size; assert(PyList_Check(heap)); - if (pos >= PyList_GET_SIZE(heap)) { + size = PyList_GET_SIZE(heap); + if (pos >= size) { PyErr_SetString(PyExc_IndexError, "index out of range"); return -1; } @@ -33,12 +35,24 @@ _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) Py_DECREF(newitem); return -1; } + if (size != PyList_GET_SIZE(heap)) { + Py_DECREF(newitem); + PyErr_SetString(PyExc_RuntimeError, + "list changed size during iteration"); + return -1; + } if (cmp == 0) break; Py_INCREF(parent); - Py_DECREF(PyList_GET_ITEM(heap, pos)); + olditem = PyList_GET_ITEM(heap, pos); PyList_SET_ITEM(heap, pos, parent); + Py_DECREF(olditem); pos = parentpos; + if (size != PyList_GET_SIZE(heap)) { + PyErr_SetString(PyExc_RuntimeError, + "list changed size during iteration"); + return -1; + } } Py_DECREF(PyList_GET_ITEM(heap, pos)); PyList_SET_ITEM(heap, pos, newitem); @@ -50,10 +64,12 @@ _siftup(PyListObject *heap, Py_ssize_t pos) { Py_ssize_t startpos, endpos, childpos, rightpos; int cmp; - PyObject *newitem, *tmp; + PyObject *newitem, *tmp, *olditem; + Py_ssize_t size; assert(PyList_Check(heap)); - endpos = PyList_GET_SIZE(heap); + size = PyList_GET_SIZE(heap); + endpos = size; startpos = pos; if (pos >= endpos) { PyErr_SetString(PyExc_IndexError, "index out of range"); @@ -79,13 +95,25 @@ _siftup(PyListObject *heap, Py_ssize_t pos) if (cmp == 0) childpos = rightpos; } + if (size != PyList_GET_SIZE(heap)) { + Py_DECREF(newitem); + PyErr_SetString(PyExc_RuntimeError, + "list changed size during iteration"); + return -1; + } /* Move the smaller child up. */ tmp = PyList_GET_ITEM(heap, childpos); Py_INCREF(tmp); - Py_DECREF(PyList_GET_ITEM(heap, pos)); + olditem = PyList_GET_ITEM(heap, pos); PyList_SET_ITEM(heap, pos, tmp); + Py_DECREF(olditem); pos = childpos; childpos = 2*pos + 1; + if (size != PyList_GET_SIZE(heap)) { + PyErr_SetString(PyExc_RuntimeError, + "list changed size during iteration"); + return -1; + } } /* The leaf at pos is empty now. Put newitem there, and and bubble |