From 93434890dcff674d94c87598435824909ab18481 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Sat, 3 May 2014 15:27:14 -0700 Subject: [PATCH] Issue 21375: Fix possible Py_ssizet overflow in heapq. --- Modules/_heapqmodule.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/Modules/_heapqmodule.c b/Modules/_heapqmodule.c index ec1da05400..30cedb9918 100644 --- a/Modules/_heapqmodule.c +++ b/Modules/_heapqmodule.c @@ -86,7 +86,7 @@ _siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) static int _siftup(PyListObject *heap, Py_ssize_t pos) { - Py_ssize_t startpos, endpos, childpos, rightpos; + Py_ssize_t startpos, endpos, childpos, rightpos, limit; int cmp; PyObject *newitem, *tmp, *olditem; Py_ssize_t size; @@ -103,9 +103,10 @@ _siftup(PyListObject *heap, Py_ssize_t pos) Py_INCREF(newitem); /* Bubble up the smaller child until hitting a leaf. */ - childpos = 2*pos + 1; /* leftmost child position */ - while (childpos < endpos) { + limit = endpos / 2; /* smallest pos that has no child */ + while (pos < limit) { /* Set childpos to index of smaller child. */ + childpos = 2*pos + 1; /* leftmost child position */ rightpos = childpos + 1; if (rightpos < endpos) { cmp = cmp_lt( @@ -131,7 +132,6 @@ _siftup(PyListObject *heap, Py_ssize_t 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"); @@ -439,7 +439,7 @@ _siftdownmax(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos) static int _siftupmax(PyListObject *heap, Py_ssize_t pos) { - Py_ssize_t startpos, endpos, childpos, rightpos; + Py_ssize_t startpos, endpos, childpos, rightpos, limit; int cmp; PyObject *newitem, *tmp; @@ -454,9 +454,10 @@ _siftupmax(PyListObject *heap, Py_ssize_t pos) Py_INCREF(newitem); /* Bubble up the smaller child until hitting a leaf. */ - childpos = 2*pos + 1; /* leftmost child position */ - while (childpos < endpos) { + limit = endpos / 2; /* smallest pos that has no child */ + while (pos < limit) { /* Set childpos to index of smaller child. */ + childpos = 2*pos + 1; /* leftmost child position */ rightpos = childpos + 1; if (rightpos < endpos) { cmp = cmp_lt( @@ -475,7 +476,6 @@ _siftupmax(PyListObject *heap, Py_ssize_t pos) Py_DECREF(PyList_GET_ITEM(heap, pos)); PyList_SET_ITEM(heap, pos, tmp); pos = childpos; - childpos = 2*pos + 1; } /* The leaf at pos is empty now. Put newitem there, and bubble -- 2.50.1