summaryrefslogtreecommitdiffstats
path: root/Objects/listobject.c
diff options
context:
space:
mode:
authorGuido van Rossum <guido@python.org>1998-05-28 20:18:46 (GMT)
committerGuido van Rossum <guido@python.org>1998-05-28 20:18:46 (GMT)
commitae621ff7b7226d093f944fbf27876e6750e768fc (patch)
tree9ddc5726f2a84169e34c0e2603da739f25c93da3 /Objects/listobject.c
parent578de30fd71c592ff434d7fe238a1f657a3802f4 (diff)
downloadcpython-ae621ff7b7226d093f944fbf27876e6750e768fc.zip
cpython-ae621ff7b7226d093f944fbf27876e6750e768fc.tar.gz
cpython-ae621ff7b7226d093f944fbf27876e6750e768fc.tar.bz2
Guard against changes in the list size during a compare or sort.
Diffstat (limited to 'Objects/listobject.c')
-rw-r--r--Objects/listobject.c53
1 files changed, 31 insertions, 22 deletions
diff --git a/Objects/listobject.c b/Objects/listobject.c
index b608d53..c2e9d5e 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -283,9 +283,8 @@ static int
list_compare(v, w)
PyListObject *v, *w;
{
- int len = (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
int i;
- for (i = 0; i < len; i++) {
+ for (i = 0; i < v->ob_size && i < w->ob_size; i++) {
int cmp = PyObject_Compare(v->ob_item[i], w->ob_item[i]);
if (cmp != 0)
return cmp;
@@ -587,11 +586,14 @@ listappend(self, args)
function is NULL. */
static int
-docompare(x, y, compare)
+docompare(x, y, compare, list)
PyObject *x;
PyObject *y;
PyObject *compare;
+ PyListObject *list;
{
+ int size = list->ob_size; /* Number of elements to sort */
+ PyObject **array = list->ob_item; /* Start of array to sort */
PyObject *args, *res;
int i;
@@ -599,6 +601,11 @@ docompare(x, y, compare)
i = PyObject_Compare(x, y);
if (i && PyErr_Occurred())
i = CMPERROR;
+ else if (size != list->ob_size || array != list->ob_item) {
+ PyErr_SetString(PyExc_SystemError,
+ "list changed size during sort");
+ i = CMPERROR;
+ }
return i;
}
@@ -615,6 +622,11 @@ docompare(x, y, compare)
"comparison function should return int");
return CMPERROR;
}
+ if (size != list->ob_size || array != list->ob_item) {
+ PyErr_SetString(PyExc_SystemError,
+ "list changed size during sort");
+ return CMPERROR;
+ }
i = PyInt_AsLong(res);
Py_DECREF(res);
if (i < 0)
@@ -643,11 +655,12 @@ docompare(x, y, compare)
(i.e. no items have been removed or duplicated). */
static int
-quicksort(array, size, compare)
- PyObject **array; /* Start of array to sort */
- int size; /* Number of elements to sort */
+quicksort(list, compare)
+ PyListObject *list; /* List to sort */
PyObject *compare;/* Comparison function object, or NULL for default */
{
+ int size = list->ob_size; /* Number of elements to sort */
+ PyObject **array = list->ob_item; /* Start of array to sort */
register PyObject *tmp, *pivot;
register PyObject **l, **r, **p;
PyObject **lo, **hi, **notp;
@@ -675,7 +688,8 @@ quicksort(array, size, compare)
pivot = *r;
do {
p = l + ((r - l) >> 1);
- k = docompare(pivot, *p, compare);
+ k = docompare(pivot, *p,
+ compare, list);
if (k == CMPERROR)
return -1;
if (k < 0)
@@ -699,19 +713,19 @@ quicksort(array, size, compare)
p = lo + (n>>1); /* Middle */
r = hi - 1; /* Last */
- k = docompare(*p, *l, compare);
+ k = docompare(*p, *l, compare, list);
if (k == CMPERROR)
return -1;
if (k < 0)
{ tmp = *p; *p = *l; *l = tmp; }
- k = docompare(*r, *p, compare);
+ k = docompare(*r, *p, compare, list);
if (k == CMPERROR)
return -1;
if (k < 0)
{ tmp = *r; *r = *p; *p = tmp; }
- k = docompare(*p, *l, compare);
+ k = docompare(*p, *l, compare, list);
if (k == CMPERROR)
return -1;
if (k < 0)
@@ -727,7 +741,7 @@ quicksort(array, size, compare)
/* Move left index to element >= pivot */
while (l < p) {
- k = docompare(*l, pivot, compare);
+ k = docompare(*l, pivot, compare, list);
if (k == CMPERROR)
return -1;
if (k < 0)
@@ -739,7 +753,7 @@ quicksort(array, size, compare)
}
/* Move right index to element <= pivot */
while (r > p) {
- k = docompare(pivot, *r, compare);
+ k = docompare(pivot, *r, compare, list);
if (k == CMPERROR)
return -1;
if (k < 0)
@@ -804,7 +818,7 @@ quicksort(array, size, compare)
* This wastes a compare if it fails, but can win big
* when there are runs of duplicates.
*/
- k = docompare(pivot, *l, compare);
+ k = docompare(pivot, *l, compare, list);
if (k == CMPERROR)
return -1;
if (!(k < 0)) {
@@ -817,7 +831,7 @@ quicksort(array, size, compare)
*/
while (r > lo) {
/* because r-1 < p, *(r-1) <= pivot is known */
- k = docompare(*(r-1), pivot, compare);
+ k = docompare(*(r-1), pivot, compare, list);
if (k == CMPERROR)
return -1;
if (k < 0)
@@ -829,7 +843,7 @@ quicksort(array, size, compare)
l++;
while (l < hi) {
/* because l > p, pivot <= *l is known */
- k = docompare(pivot, *l, compare);
+ k = docompare(pivot, *l, compare, list);
if (k == CMPERROR)
return -1;
if (k < 0)
@@ -866,8 +880,7 @@ listsort(self, compare)
PyListObject *self;
PyObject *compare;
{
- /* XXX Don't you *dare* changing the list's length in compare()! */
- if (quicksort(self->ob_item, self->ob_size, compare) < 0)
+ if (quicksort(self, compare) < 0)
return NULL;
Py_INCREF(Py_None);
return Py_None;
@@ -922,11 +935,7 @@ PyList_Sort(v)
PyErr_BadInternalCall();
return -1;
}
- v = listsort((PyListObject *)v, (PyObject *)NULL);
- if (v == NULL)
- return -1;
- Py_DECREF(v);
- return 0;
+ return quicksort((PyListObject *)v, (PyObject *)NULL);
}
PyObject *