Index: Objects/listobject.c |
diff --git a/Objects/listobject.c b/Objects/listobject.c |
index 0f4552510ada091c46d708691b1604e12ecf41fa..bdf81bae3d9013e45d0af5c24ffc1a3ca6d77342 100644 |
--- a/Objects/listobject.c |
+++ b/Objects/listobject.c |
@@ -940,11 +940,70 @@ reverse_slice(PyObject **lo, PyObject **hi) |
* pieces to this algorithm; read listsort.txt for overviews and details. |
*/ |
+/* A sortslice contains a pointer to an array of keys and a pointer to |
+ * an array of corresponding values. In other words, keys[i] |
+ * corresponds with values[i]. If values == NULL, then the keys are |
+ * also the values. |
+ * |
+ * Several convenience routines are provided here, so that keys and |
+ * values are always moved in sync. |
+ */ |
+typedef struct { |
+ PyObject **keys; |
+ PyObject **values; |
+} sortslice; |
+ |
+Py_LOCAL_INLINE(void) |
+sortslice_copy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j) |
+{ |
+ s1->keys[i] = s2->keys[j]; |
+ if (s1->values != NULL) |
+ s1->values[i] = s2->values[j]; |
+} |
+ |
+Py_LOCAL_INLINE(void) |
+sortslice_copy_incr(sortslice *dst, sortslice *src) { |
+ *dst->keys++ = *src->keys++; |
+ if (dst->values != NULL) |
+ *dst->values++ = *src->values++; |
+} |
+ |
+Py_LOCAL_INLINE(void) |
+sortslice_copy_decr(sortslice *dst, sortslice *src) { |
+ *dst->keys-- = *src->keys--; |
+ if (dst->values != NULL) |
+ *dst->values-- = *src->values--; |
+} |
+ |
+ |
+Py_LOCAL_INLINE(void) |
+sortslice_memcpy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j, |
+ Py_ssize_t n) { |
+ memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n); |
+ if (s1->values != NULL) |
+ memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n); |
+} |
+ |
+Py_LOCAL_INLINE(void) |
+sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j, |
+ Py_ssize_t n) { |
+ memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n); |
+ if (s1->values != NULL) |
+ memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n); |
+} |
+ |
+Py_LOCAL_INLINE(void) |
+sortslice_advance(sortslice *slice, Py_ssize_t n) { |
+ slice->keys += n; |
+ if (slice->values != NULL) |
+ slice->values += n; |
+} |
+ |
/* Comparison function: PyObject_RichCompareBool with Py_LT. |
* Returns -1 on error, 1 if x < y, 0 if x >= y. |
*/ |
-#define ISLT(X, Y) (PyObject_RichCompareBool(X, Y, Py_LT)) |
+#define ISLT(X, Y) (PyObject_RichCompareBool((X), (Y), Py_LT)) |
/* Compare X to Y via "<". Goto "fail" if the comparison raises an |
error. Else "k" is set to true iff X<Y, and an "if (k)" block is |
@@ -958,57 +1017,63 @@ reverse_slice(PyObject **lo, PyObject **hi) |
elements. |
[lo, hi) is a contiguous slice of a list, and is sorted via |
binary insertion. This sort is stable. |
- On entry, must have lo <= start <= hi, and that [lo, start) is already |
- sorted (pass start == lo if you don't know!). |
+ On entry, must have lo < start <= hi, and that [lo, start) is already |
+ sorted (pass start == lo+1 if you don't know!). |
If islt() complains return -1, else 0. |
Even in case of error, the output slice will be some permutation of |
the input (nothing is lost or duplicated). |
*/ |
-static int |
-binarysort(PyObject **lo, PyObject **hi, PyObject **start) |
-{ |
- register Py_ssize_t k; |
- register PyObject **l, **p, **r; |
- register PyObject *pivot; |
- |
- assert(lo <= start && start <= hi); |
- /* assert [lo, start) is sorted */ |
- if (lo == start) |
- ++start; |
- for (; start < hi; ++start) { |
- /* set l to where *start belongs */ |
- l = lo; |
- r = start; |
+Py_LOCAL_INLINE(int) |
+binarysort(sortslice lo, int n, int start_offset) |
+{ |
+ PyObject **next = lo.keys + start_offset; |
+ int k; |
+ PyObject **l, **p, **r; |
+ PyObject *pivot; |
+ |
+ assert(start_offset >= 0); |
+ /* assert [lo, next) is sorted */ |
+ for (; next - lo.keys < n; ++next) { |
+ /* set l to where *next belongs */ |
+ l = lo.keys; |
+ r = next; |
pivot = *r; |
/* Invariants: |
* pivot >= all in [lo, l). |
- * pivot < all in [r, start). |
- * The second is vacuously true at the start. |
+ * pivot < all in [r, next). |
+ * The second is vacuously true at the next. |
*/ |
assert(l < r); |
do { |
p = l + ((r - l) >> 1); |
- IFLT(pivot, *p) |
+ if ((k = ISLT(pivot, *p))) { |
+ if (k < 0) return -1; |
r = p; |
- else |
+ } else |
l = p+1; |
} while (l < r); |
assert(l == r); |
/* The invariants still hold, so pivot >= all in [lo, l) and |
- pivot < all in [l, start), so pivot belongs at l. Note |
+ pivot < all in [l, next), so pivot belongs at l. Note |
that if there are elements equal to pivot, l points to the |
first slot after them -- that's why this sort is stable. |
Slide over to make room. |
Caution: using memmove is much slower under MSVC 5; |
we're not usually moving many slots. */ |
- for (p = start; p > l; --p) |
+ for (p = next; p > l; --p) |
*p = *(p-1); |
*l = pivot; |
+ if (lo.values != NULL) { |
+ Py_ssize_t offset = lo.values - lo.keys; |
+ p = next + offset; |
+ pivot = *p; |
+ l += offset; |
+ for (p = next + offset; p > l; --p) |
+ *p = *(p-1); |
+ *l = pivot; |
+ } |
} |
return 0; |
- |
- fail: |
- return -1; |
} |
/* |
@@ -1029,10 +1094,11 @@ elements to get out of order). |
Returns -1 in case of error. |
*/ |
-static Py_ssize_t |
-count_run(PyObject **lo, PyObject **hi, int *descending) |
+Py_LOCAL_INLINE(Py_ssize_t) |
+count_run(PyObject **lo, Py_ssize_t nremaining, int *descending) |
{ |
- Py_ssize_t k; |
+ PyObject **hi = lo + nremaining; |
+ int k; |
Py_ssize_t n; |
assert(lo < hi); |
@@ -1042,19 +1108,21 @@ count_run(PyObject **lo, PyObject **hi, int *descending) |
return 1; |
n = 2; |
- IFLT(*lo, *(lo-1)) { |
+ if ((k = ISLT(*lo, *(lo-1)))) { |
+ if (k < 0) goto fail; |
*descending = 1; |
for (lo = lo+1; lo < hi; ++lo, ++n) { |
- IFLT(*lo, *(lo-1)) |
- ; |
- else |
+ if ((k = ISLT(*lo, *(lo-1)))) { |
+ if (k < 0) goto fail; |
+ } else |
break; |
} |
- } |
- else { |
+ } else { |
for (lo = lo+1; lo < hi; ++lo, ++n) { |
- IFLT(*lo, *(lo-1)) |
+ if ((k = ISLT(*lo, *(lo-1)))) { |
+ if (k < 0) goto fail; |
break; |
+ } |
} |
} |
@@ -1089,7 +1157,7 @@ gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint) |
{ |
Py_ssize_t ofs; |
Py_ssize_t lastofs; |
- Py_ssize_t k; |
+ int k; |
assert(key && a && n > 0 && hint >= 0 && hint < n); |
@@ -1122,6 +1190,7 @@ gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint) |
* a[hint - ofs] < key <= a[hint - lastofs] |
*/ |
const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */ |
+ Py_ssize_t tmp; |
while (ofs < maxofs) { |
IFLT(*(a-ofs), key) |
break; |
@@ -1134,9 +1203,9 @@ gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint) |
if (ofs > maxofs) |
ofs = maxofs; |
/* Translate back to positive offsets relative to &a[0]. */ |
- k = lastofs; |
+ tmp = lastofs; |
lastofs = hint - ofs; |
- ofs = hint - k; |
+ ofs = hint - tmp; |
} |
a -= hint; |
@@ -1180,7 +1249,7 @@ gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint) |
{ |
Py_ssize_t ofs; |
Py_ssize_t lastofs; |
- Py_ssize_t k; |
+ int k; |
assert(key && a && n > 0 && hint >= 0 && hint < n); |
@@ -1192,6 +1261,7 @@ gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint) |
* a[hint - ofs] <= key < a[hint - lastofs] |
*/ |
const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */ |
+ Py_ssize_t tmp; |
while (ofs < maxofs) { |
IFLT(key, *(a-ofs)) { |
lastofs = ofs; |
@@ -1205,15 +1275,15 @@ gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint) |
if (ofs > maxofs) |
ofs = maxofs; |
/* Translate back to positive offsets relative to &a[0]. */ |
- k = lastofs; |
+ tmp = lastofs; |
lastofs = hint - ofs; |
- ofs = hint - k; |
+ ofs = hint - tmp; |
} |
else { |
/* a[hint] <= key -- gallop right, until |
* a[hint + lastofs] <= key < a[hint + ofs] |
*/ |
- const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */ |
+ const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */ |
while (ofs < maxofs) { |
IFLT(key, a[ofs]) |
break; |
@@ -1272,7 +1342,7 @@ fail: |
* a convenient way to pass state around among the helper functions. |
*/ |
struct s_slice { |
- PyObject **base; |
+ sortslice base; |
Py_ssize_t len; |
}; |
@@ -1286,7 +1356,7 @@ typedef struct s_MergeState { |
/* 'a' is temp storage to help with merges. It contains room for |
* alloced entries. |
*/ |
- PyObject **a; /* may point to temparray below */ |
+ sortslice a; /* may point to temparray below */ |
Py_ssize_t alloced; |
/* A stack of n pending runs yet to be merged. Run #i starts at |
@@ -1306,12 +1376,20 @@ typedef struct s_MergeState { |
} MergeState; |
/* Conceptually a MergeState's constructor. */ |
-static void |
-merge_init(MergeState *ms) |
+Py_LOCAL_INLINE(void) |
+merge_init(MergeState *ms, int list_size, int has_keyfunc) |
{ |
assert(ms != NULL); |
- ms->a = ms->temparray; |
- ms->alloced = MERGESTATE_TEMP_SIZE; |
+ if (has_keyfunc) { |
+ ms->alloced = (list_size+1)/2; |
+ if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced) |
+ ms->alloced = MERGESTATE_TEMP_SIZE / 2; |
+ ms->a.values = &ms->temparray[ms->alloced]; |
+ } else { |
+ ms->alloced = MERGESTATE_TEMP_SIZE; |
+ ms->a.values = NULL; |
+ } |
+ ms->a.keys = ms->temparray; |
ms->n = 0; |
ms->min_gallop = MIN_GALLOP; |
} |
@@ -1320,14 +1398,12 @@ merge_init(MergeState *ms) |
* when you're done with a MergeState, and may be called before then if |
* you want to free the temp memory early. |
*/ |
-static void |
+Py_LOCAL_INLINE(void) |
merge_freemem(MergeState *ms) |
{ |
assert(ms != NULL); |
- if (ms->a != ms->temparray) |
- PyMem_Free(ms->a); |
- ms->a = ms->temparray; |
- ms->alloced = MERGESTATE_TEMP_SIZE; |
+ if (ms->a.keys != ms->temparray) |
+ PyMem_Free(ms->a.keys); |
} |
/* Ensure enough temp memory for 'need' array slots is available. |
@@ -1336,52 +1412,60 @@ merge_freemem(MergeState *ms) |
static int |
merge_getmem(MergeState *ms, Py_ssize_t need) |
{ |
+ int multiplier; |
+ |
assert(ms != NULL); |
if (need <= ms->alloced) |
return 0; |
+ |
+ multiplier = ms->a.values != NULL ? 2 : 1; |
+ |
/* Don't realloc! That can cost cycles to copy the old data, but |
* we don't care what's in the block. |
*/ |
merge_freemem(ms); |
- if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) { |
+ if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*) / multiplier) { |
PyErr_NoMemory(); |
return -1; |
} |
- ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*)); |
- if (ms->a) { |
+ ms->a.keys = (PyObject**)PyMem_Malloc(multiplier * need |
+ * sizeof(PyObject *)); |
+ if (ms->a.keys != NULL) { |
ms->alloced = need; |
+ if (ms->a.values != NULL) |
+ ms->a.values = &ms->a.keys[need]; |
return 0; |
} |
PyErr_NoMemory(); |
- merge_freemem(ms); /* reset to sane state */ |
return -1; |
} |
#define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ |
merge_getmem(MS, NEED)) |
-/* Merge the na elements starting at pa with the nb elements starting at pb |
- * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. |
- * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the |
- * merge, and should have na <= nb. See listsort.txt for more info. |
- * Return 0 if successful, -1 if error. |
+/* Merge the na elements starting at ssa with the nb elements starting at |
+ * ssb = ssa + na in a stable way, in-place. na and nb must be > 0. Must |
+ * also have that pa[na-1] belongs at the end of the merge, and should have |
+ * na <= nb. See listsort.txt for more info. Return 0 if successful, |
+ * -1 if error. |
*/ |
static Py_ssize_t |
-merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na, |
- PyObject **pb, Py_ssize_t nb) |
+merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na, Py_ssize_t nb) |
{ |
Py_ssize_t k; |
- PyObject **dest; |
+ sortslice dest, ssb; |
int result = -1; /* guilty until proved innocent */ |
Py_ssize_t min_gallop; |
- assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); |
+ assert(ms && ssa.keys && na > 0 && nb > 0); |
+ ssb = ssa; |
+ sortslice_advance(&ssb, na); |
if (MERGE_GETMEM(ms, na) < 0) |
return -1; |
- memcpy(ms->a, pa, na * sizeof(PyObject*)); |
- dest = pa; |
- pa = ms->a; |
+ sortslice_memcpy(&ms->a, 0, &ssa, 0, na); |
+ dest = ssa; |
+ ssa = ms->a; |
- *dest++ = *pb++; |
+ sortslice_copy_incr(&dest, &ssb); |
--nb; |
if (nb == 0) |
goto Succeed; |
@@ -1398,77 +1482,70 @@ merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na, |
*/ |
for (;;) { |
assert(na > 1 && nb > 0); |
- k = ISLT(*pb, *pa); |
+ k = ISLT(ssb.keys[0], ssa.keys[0]); |
if (k) { |
if (k < 0) |
goto Fail; |
- *dest++ = *pb++; |
- ++bcount; |
- acount = 0; |
- --nb; |
- if (nb == 0) |
+ sortslice_copy_incr(&dest, &ssb); |
+ if (--nb == 0) |
goto Succeed; |
- if (bcount >= min_gallop) |
+ if (++bcount >= min_gallop) |
break; |
- } |
- else { |
- *dest++ = *pa++; |
- ++acount; |
- bcount = 0; |
- --na; |
- if (na == 1) |
+ acount = 0; |
+ } else { |
+ sortslice_copy_incr(&dest, &ssa); |
+ if (--na == 1) |
goto CopyB; |
- if (acount >= min_gallop) |
+ if (++acount >= min_gallop) |
break; |
+ bcount = 0; |
} |
} |
- /* One run is winning so consistently that galloping may |
- * be a huge win. So try that, and continue galloping until |
- * (if ever) neither run appears to be winning consistently |
- * anymore. |
+ /* One run is winning so consistently that galloping may be a huge |
+ * win. So try that, and continue galloping until (if ever) neither |
+ * run appears to be winning consistently anymore. |
*/ |
++min_gallop; |
do { |
assert(na > 1 && nb > 0); |
min_gallop -= min_gallop > 1; |
ms->min_gallop = min_gallop; |
- k = gallop_right(*pb, pa, na, 0); |
+ k = gallop_right(ssb.keys[0], ssa.keys, na, 0); |
acount = k; |
if (k) { |
if (k < 0) |
goto Fail; |
- memcpy(dest, pa, k * sizeof(PyObject *)); |
- dest += k; |
- pa += k; |
+ sortslice_memcpy(&dest, 0, &ssa, 0, k); |
+ sortslice_advance(&dest, k); |
+ sortslice_advance(&ssa, k); |
na -= k; |
if (na == 1) |
goto CopyB; |
- /* na==0 is impossible now if the comparison |
- * function is consistent, but we can't assume |
- * that it is. |
+ /* na==0 is impossible now if the comparison function is |
+ * consistent, but we can't assume that it is. |
*/ |
if (na == 0) |
goto Succeed; |
} |
- *dest++ = *pb++; |
+ sortslice_copy_incr(&dest, &ssb); |
--nb; |
if (nb == 0) |
goto Succeed; |
- k = gallop_left(*pa, pb, nb, 0); |
+ k = gallop_left(ssa.keys[0], ssb.keys, nb, 0); |
bcount = k; |
if (k) { |
if (k < 0) |
goto Fail; |
- memmove(dest, pb, k * sizeof(PyObject *)); |
- dest += k; |
- pb += k; |
+ sortslice_memmove(&dest, 0, &ssb, 0, k); |
+ sortslice_advance(&dest, k); |
+ sortslice_advance(&ssb, k); |
nb -= k; |
if (nb == 0) |
goto Succeed; |
} |
- *dest++ = *pa++; |
+ sortslice_copy_incr(&dest, &ssa); |
--na; |
if (na == 1) |
goto CopyB; |
@@ -1480,43 +1557,41 @@ Succeed: |
result = 0; |
Fail: |
if (na) |
- memcpy(dest, pa, na * sizeof(PyObject*)); |
+ sortslice_memcpy(&dest, 0, &ssa, 0, na); |
return result; |
CopyB: |
assert(na == 1 && nb > 0); |
- /* The last element of pa belongs at the end of the merge. */ |
- memmove(dest, pb, nb * sizeof(PyObject *)); |
- dest[nb] = *pa; |
+ /* The last element of ssa belongs at the end of the merge. */ |
+ sortslice_memmove(&dest, 0, &ssb, 0, nb); |
+ sortslice_copy(&dest, nb, &ssa, 0); |
return 0; |
} |
-/* Merge the na elements starting at pa with the nb elements starting at pb |
- * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. |
- * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the |
- * merge, and should have na >= nb. See listsort.txt for more info. |
- * Return 0 if successful, -1 if error. |
+/* Merge the na elements starting at pa with the nb elements starting at |
+ * ssb = ssa + na in a stable way, in-place. na and nb must be > 0. |
+ * Must also have that pa[na-1] belongs at the end of the merge, and |
+ * should have na >= nb. See listsort.txt for more info. Return 0 if |
+ * successful, -1 if error. |
*/ |
static Py_ssize_t |
-merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb) |
+merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na, Py_ssize_t nb) |
{ |
Py_ssize_t k; |
- PyObject **dest; |
+ sortslice dest, ssb; |
int result = -1; /* guilty until proved innocent */ |
- PyObject **basea; |
- PyObject **baseb; |
Py_ssize_t min_gallop; |
- assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); |
+ assert(ms && ssa.keys && na > 0 && nb > 0); |
if (MERGE_GETMEM(ms, nb) < 0) |
return -1; |
- dest = pb + nb - 1; |
- memcpy(ms->a, pb, nb * sizeof(PyObject*)); |
- basea = pa; |
- baseb = ms->a; |
- pb = ms->a + nb - 1; |
- pa += na - 1; |
- |
- *dest-- = *pa--; |
+ dest = ssa; |
+ sortslice_advance(&dest, na + nb - 1); |
+ sortslice_memcpy(&ms->a, 0, &ssa, na, nb); |
+ ssb = ms->a; |
+ sortslice_advance(&ssb, nb - 1); |
+ sortslice_advance(&ssa, na - 1); |
+ |
+ sortslice_copy_decr(&dest, &ssa); |
--na; |
if (na == 0) |
goto Succeed; |
@@ -1533,79 +1608,72 @@ merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t |
*/ |
for (;;) { |
assert(na > 0 && nb > 1); |
- k = ISLT(*pb, *pa); |
+ k = ISLT(ssb.keys[0], ssa.keys[0]); |
if (k) { |
if (k < 0) |
goto Fail; |
- *dest-- = *pa--; |
- ++acount; |
- bcount = 0; |
- --na; |
- if (na == 0) |
+ sortslice_copy_decr(&dest, &ssa); |
+ if (--na == 0) |
goto Succeed; |
- if (acount >= min_gallop) |
+ if (++acount >= min_gallop) |
break; |
- } |
- else { |
- *dest-- = *pb--; |
- ++bcount; |
- acount = 0; |
- --nb; |
- if (nb == 1) |
+ bcount = 0; |
+ } else { |
+ sortslice_copy_decr(&dest, &ssb); |
+ if (--nb == 1) |
goto CopyA; |
- if (bcount >= min_gallop) |
+ if (++bcount >= min_gallop) |
break; |
+ acount = 0; |
} |
} |
- /* One run is winning so consistently that galloping may |
- * be a huge win. So try that, and continue galloping until |
- * (if ever) neither run appears to be winning consistently |
- * anymore. |
+ /* One run is winning so consistently that galloping may be a huge |
+ * win. So try that, and continue galloping until (if ever) neither |
+ * run appears to be winning consistently anymore. |
*/ |
++min_gallop; |
do { |
assert(na > 0 && nb > 1); |
min_gallop -= min_gallop > 1; |
ms->min_gallop = min_gallop; |
- k = gallop_right(*pb, basea, na, na-1); |
+ k = gallop_right(ssb.keys[0], ssa.keys - (na - 1), na, na - 1); |
if (k < 0) |
goto Fail; |
k = na - k; |
acount = k; |
if (k) { |
- dest -= k; |
- pa -= k; |
- memmove(dest+1, pa+1, k * sizeof(PyObject *)); |
+ sortslice_advance(&dest, -k); |
+ sortslice_advance(&ssa, -k); |
+ sortslice_memmove(&dest, 1, &ssa, 1, k); |
na -= k; |
if (na == 0) |
goto Succeed; |
} |
- *dest-- = *pb--; |
+ sortslice_copy_decr(&dest, &ssb); |
--nb; |
if (nb == 1) |
goto CopyA; |
- k = gallop_left(*pa, baseb, nb, nb-1); |
+ k = gallop_left(ssa.keys[0], ms->a.keys, nb, nb-1); |
if (k < 0) |
goto Fail; |
k = nb - k; |
bcount = k; |
if (k) { |
- dest -= k; |
- pb -= k; |
- memcpy(dest+1, pb+1, k * sizeof(PyObject *)); |
+ sortslice_advance(&dest, -k); |
+ sortslice_advance(&ssb, -k); |
+ sortslice_memcpy(&dest, 1, &ssb, 1, k); |
nb -= k; |
if (nb == 1) |
goto CopyA; |
- /* nb==0 is impossible now if the comparison |
- * function is consistent, but we can't assume |
- * that it is. |
+ /* nb==0 is impossible now if the comparison function is |
+ * consistent, but we can't assume that it is. |
*/ |
if (nb == 0) |
goto Succeed; |
} |
- *dest-- = *pa--; |
+ sortslice_copy_decr(&dest, &ssa); |
--na; |
if (na == 0) |
goto Succeed; |
@@ -1617,15 +1685,15 @@ Succeed: |
result = 0; |
Fail: |
if (nb) |
- memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*)); |
+ sortslice_memcpy(&dest, -(nb-1), &ms->a, 0, nb); |
return result; |
CopyA: |
assert(nb == 1 && na > 0); |
- /* The first element of pb belongs at the front of the merge. */ |
- dest -= na; |
- pa -= na; |
- memmove(dest+1, pa+1, na * sizeof(PyObject *)); |
- *dest = *pb; |
+ /* The first element of ssb belongs at the front of the merge. */ |
+ sortslice_memmove(&dest, 1-na, &ssa, 1-na, na); |
+ sortslice_advance(&dest, -na); |
+ sortslice_advance(&ssa, -na); |
+ sortslice_copy(&dest, 0, &ssb, 0); |
return 0; |
} |
@@ -1635,7 +1703,7 @@ CopyA: |
static Py_ssize_t |
merge_at(MergeState *ms, Py_ssize_t i) |
{ |
- PyObject **pa, **pb; |
+ sortslice ssa, ssb; |
Py_ssize_t na, nb; |
Py_ssize_t k; |
@@ -1644,12 +1712,12 @@ merge_at(MergeState *ms, Py_ssize_t i) |
assert(i >= 0); |
assert(i == ms->n - 2 || i == ms->n - 3); |
- pa = ms->pending[i].base; |
+ ssa = ms->pending[i].base; |
na = ms->pending[i].len; |
- pb = ms->pending[i+1].base; |
+ ssb = ms->pending[i+1].base; |
nb = ms->pending[i+1].len; |
assert(na > 0 && nb > 0); |
- assert(pa + na == pb); |
+ assert(ssa.keys + na == ssb.keys); |
/* Record the length of the combined runs; if i is the 3rd-last |
* run now, also slide over the last run (which isn't involved |
@@ -1663,10 +1731,10 @@ merge_at(MergeState *ms, Py_ssize_t i) |
/* Where does b start in a? Elements in a before that can be |
* ignored (already in place). |
*/ |
- k = gallop_right(*pb, pa, na, 0); |
+ k = gallop_right(*ssb.keys, ssa.keys, na, 0); |
if (k < 0) |
return -1; |
- pa += k; |
+ sortslice_advance(&ssa, k); |
na -= k; |
if (na == 0) |
return 0; |
@@ -1674,7 +1742,7 @@ merge_at(MergeState *ms, Py_ssize_t i) |
/* Where does a end in b? Elements in b after that can be |
* ignored (already in place). |
*/ |
- nb = gallop_left(pa[na-1], pb, nb, nb-1); |
+ nb = gallop_left(ssa.keys[na-1], ssb.keys, nb, nb-1); |
if (nb <= 0) |
return nb; |
@@ -1682,9 +1750,9 @@ merge_at(MergeState *ms, Py_ssize_t i) |
* min(na, nb) elements. |
*/ |
if (na <= nb) |
- return merge_lo(ms, pa, na, pb, nb); |
+ return merge_lo(ms, ssa, na, nb); |
else |
- return merge_hi(ms, pa, na, pb, nb); |
+ return merge_hi(ms, ssa, na, nb); |
} |
/* Examine the stack of runs waiting to be merged, merging adjacent runs |
@@ -1697,7 +1765,7 @@ merge_at(MergeState *ms, Py_ssize_t i) |
* |
* Returns 0 on success, -1 on error. |
*/ |
-static int |
+Py_LOCAL_INLINE(int) |
merge_collapse(MergeState *ms) |
{ |
struct s_slice *p = ms->pending; |
@@ -1726,7 +1794,7 @@ merge_collapse(MergeState *ms) |
* |
* Returns 0 on success, -1 on error. |
*/ |
-static int |
+Py_LOCAL_INLINE(int) |
merge_force_collapse(MergeState *ms) |
{ |
struct s_slice *p = ms->pending; |
@@ -1752,7 +1820,7 @@ merge_force_collapse(MergeState *ms) |
* |
* See listsort.txt for more info. |
*/ |
-static Py_ssize_t |
+Py_LOCAL_INLINE(Py_ssize_t) |
merge_compute_minrun(Py_ssize_t n) |
{ |
Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */ |
@@ -1765,103 +1833,12 @@ merge_compute_minrun(Py_ssize_t n) |
return n + r; |
} |
-/* Special wrapper to support stable sorting using the decorate-sort-undecorate |
- pattern. Holds a key which is used for comparisons and the original record |
- which is returned during the undecorate phase. By exposing only the key |
- during comparisons, the underlying sort stability characteristics are left |
- unchanged. Also, the comparison function will only see the key instead of |
- a full record. */ |
- |
-typedef struct { |
- PyObject_HEAD |
- PyObject *key; |
- PyObject *value; |
-} sortwrapperobject; |
- |
-PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key."); |
-static PyObject * |
-sortwrapper_richcompare(sortwrapperobject *, sortwrapperobject *, int); |
-static void |
-sortwrapper_dealloc(sortwrapperobject *); |
- |
-PyTypeObject PySortWrapper_Type = { |
- PyVarObject_HEAD_INIT(&PyType_Type, 0) |
- "sortwrapper", /* tp_name */ |
- sizeof(sortwrapperobject), /* tp_basicsize */ |
- 0, /* tp_itemsize */ |
- /* methods */ |
- (destructor)sortwrapper_dealloc, /* tp_dealloc */ |
- 0, /* tp_print */ |
- 0, /* tp_getattr */ |
- 0, /* tp_setattr */ |
- 0, /* tp_reserved */ |
- 0, /* tp_repr */ |
- 0, /* tp_as_number */ |
- 0, /* tp_as_sequence */ |
- 0, /* tp_as_mapping */ |
- 0, /* tp_hash */ |
- 0, /* tp_call */ |
- 0, /* tp_str */ |
- PyObject_GenericGetAttr, /* tp_getattro */ |
- 0, /* tp_setattro */ |
- 0, /* tp_as_buffer */ |
- Py_TPFLAGS_DEFAULT, /* tp_flags */ |
- sortwrapper_doc, /* tp_doc */ |
- 0, /* tp_traverse */ |
- 0, /* tp_clear */ |
- (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */ |
-}; |
- |
- |
-static PyObject * |
-sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op) |
+Py_LOCAL(void) |
+reverse_sortslice(sortslice s, Py_ssize_t n) |
{ |
- if (!PyObject_TypeCheck(b, &PySortWrapper_Type)) { |
- PyErr_SetString(PyExc_TypeError, |
- "expected a sortwrapperobject"); |
- return NULL; |
- } |
- return PyObject_RichCompare(a->key, b->key, op); |
-} |
- |
-static void |
-sortwrapper_dealloc(sortwrapperobject *so) |
-{ |
- Py_XDECREF(so->key); |
- Py_XDECREF(so->value); |
- PyObject_Del(so); |
-} |
- |
-/* Returns a new reference to a sortwrapper. |
- Consumes the references to the two underlying objects. */ |
- |
-static PyObject * |
-build_sortwrapper(PyObject *key, PyObject *value) |
-{ |
- sortwrapperobject *so; |
- |
- so = PyObject_New(sortwrapperobject, &PySortWrapper_Type); |
- if (so == NULL) |
- return NULL; |
- so->key = key; |
- so->value = value; |
- return (PyObject *)so; |
-} |
- |
-/* Returns a new reference to the value underlying the wrapper. */ |
-static PyObject * |
-sortwrapper_getvalue(PyObject *so) |
-{ |
- PyObject *value; |
- |
- if (!PyObject_TypeCheck(so, &PySortWrapper_Type)) { |
- PyErr_SetString(PyExc_TypeError, |
- "expected a sortwrapperobject"); |
- return NULL; |
- } |
- value = ((sortwrapperobject *)so)->value; |
- Py_INCREF(value); |
- return value; |
+ reverse_slice(s.keys, &s.keys[n]); |
+ if (s.values != NULL) |
+ reverse_slice(s.values, &s.values[n]); |
} |
/* An adaptive, stable, natural mergesort. See listsort.txt. |
@@ -1873,18 +1850,18 @@ static PyObject * |
listsort(PyListObject *self, PyObject *args, PyObject *kwds) |
{ |
MergeState ms; |
- PyObject **lo, **hi; |
Py_ssize_t nremaining; |
Py_ssize_t minrun; |
+ sortslice lo; |
Py_ssize_t saved_ob_size, saved_allocated; |
PyObject **saved_ob_item; |
PyObject **final_ob_item; |
PyObject *result = NULL; /* guilty until proved innocent */ |
int reverse = 0; |
PyObject *keyfunc = NULL; |
- Py_ssize_t i; |
- PyObject *key, *value, *kvpair; |
+ Py_ssize_t i, was_allocated; |
static char *kwlist[] = {"key", "reverse", 0}; |
+ PyObject **keys; |
assert(self != NULL); |
assert (PyList_Check(self)); |
@@ -1897,9 +1874,9 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds) |
"must use keyword argument for key function"); |
return NULL; |
} |
+ if (keyfunc == Py_None) |
+ keyfunc = NULL; |
} |
- if (keyfunc == Py_None) |
- keyfunc = NULL; |
/* The list is temporarily made empty, so that mutations performed |
* by comparison functions can't affect the slice of memory we're |
@@ -1907,68 +1884,77 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds) |
* factory, since ob_item may change). |
*/ |
saved_ob_size = Py_SIZE(self); |
+ if (saved_ob_size < 2) |
+ Py_RETURN_NONE; |
saved_ob_item = self->ob_item; |
saved_allocated = self->allocated; |
Py_SIZE(self) = 0; |
self->ob_item = NULL; |
self->allocated = -1; /* any operation will reset it to >= 0 */ |
- if (keyfunc != NULL) { |
- for (i=0 ; i < saved_ob_size ; i++) { |
- value = saved_ob_item[i]; |
- key = PyObject_CallFunctionObjArgs(keyfunc, value, |
- NULL); |
- if (key == NULL) { |
- for (i=i-1 ; i>=0 ; i--) { |
- kvpair = saved_ob_item[i]; |
- value = sortwrapper_getvalue(kvpair); |
- saved_ob_item[i] = value; |
- Py_DECREF(kvpair); |
- } |
+ if (keyfunc == NULL) { |
+ keys = NULL; |
+ lo.keys = saved_ob_item; |
+ lo.values = NULL; |
+ } else { |
+ if (saved_ob_size < MERGESTATE_TEMP_SIZE/2) |
+ keys = &ms.temparray[saved_ob_size+1]; |
+ else { |
+ keys = PyMem_MALLOC(sizeof(PyObject *) * saved_ob_size); |
+ if (keys == NULL) |
+ return NULL; |
+ } |
+ |
+ for (i = 0; i < saved_ob_size ; i++) { |
+ keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i], |
+ NULL); |
+ if (keys[i] == NULL) { |
+ for (i=i-1 ; i>=0 ; i--) |
+ Py_DECREF(keys[i]); |
goto dsu_fail; |
} |
- kvpair = build_sortwrapper(key, value); |
- if (kvpair == NULL) |
- goto dsu_fail; |
- saved_ob_item[i] = kvpair; |
} |
+ |
+ lo.keys = keys; |
+ lo.values = saved_ob_item; |
} |
- merge_init(&ms); |
+ merge_init(&ms, saved_ob_size, keys != NULL); |
nremaining = saved_ob_size; |
- if (nremaining < 2) |
- goto succeed; |
/* Reverse sort stability achieved by initially reversing the list, |
applying a stable forward sort, then reversing the final result. */ |
- if (reverse) |
- reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); |
+ if (reverse) { |
+ if (keys != NULL) |
+ reverse_slice(&keys[0], &keys[saved_ob_size]); |
+ reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]); |
+ } |
/* March over the array once, left to right, finding natural runs, |
* and extending short natural runs to minrun elements. |
*/ |
- lo = saved_ob_item; |
- hi = lo + nremaining; |
minrun = merge_compute_minrun(nremaining); |
do { |
int descending; |
Py_ssize_t n; |
/* Identify next run. */ |
- n = count_run(lo, hi, &descending); |
+ n = count_run(lo.keys, nremaining, &descending); |
if (n < 0) |
goto fail; |
if (descending) |
- reverse_slice(lo, lo + n); |
+ reverse_sortslice(lo, n); |
/* If short, extend to min(minrun, nremaining). */ |
if (n < minrun) { |
- const Py_ssize_t force = nremaining <= minrun ? |
- nremaining : minrun; |
- if (binarysort(lo, lo + force, lo + n) < 0) |
+ Py_ssize_t force = nremaining <= minrun ? nremaining : minrun; |
+ if (binarysort(lo, force, n) < 0) |
goto fail; |
n = force; |
} |
+ if (n == saved_ob_size) |
+ goto all_done; |
+ |
/* Push run onto pending-runs stack, and maybe merge. */ |
assert(ms.n < MAX_MERGE_PENDING); |
ms.pending[ms.n].base = lo; |
@@ -1977,56 +1963,61 @@ listsort(PyListObject *self, PyObject *args, PyObject *kwds) |
if (merge_collapse(&ms) < 0) |
goto fail; |
/* Advance to find next run. */ |
- lo += n; |
+ sortslice_advance(&lo, n); |
nremaining -= n; |
} while (nremaining); |
- assert(lo == hi); |
if (merge_force_collapse(&ms) < 0) |
goto fail; |
assert(ms.n == 1); |
- assert(ms.pending[0].base == saved_ob_item); |
+ assert(keys == NULL |
+ ? ms.pending[0].base.keys == saved_ob_item |
+ : ms.pending[0].base.keys == &keys[0]); |
assert(ms.pending[0].len == saved_ob_size); |
+ lo = ms.pending[0].base; |
-succeed: |
+all_done: |
result = Py_None; |
-fail: |
- if (keyfunc != NULL) { |
- for (i=0 ; i < saved_ob_size ; i++) { |
- kvpair = saved_ob_item[i]; |
- value = sortwrapper_getvalue(kvpair); |
- saved_ob_item[i] = value; |
- Py_DECREF(kvpair); |
- } |
- } |
- if (self->allocated != -1 && result != NULL) { |
- /* The user mucked with the list during the sort, |
- * and we don't already have another error to report. |
- */ |
- PyErr_SetString(PyExc_ValueError, "list modified during sort"); |
- result = NULL; |
- } |
+ if (reverse) |
+ reverse_sortslice(lo, saved_ob_size); |
- if (reverse && saved_ob_size > 1) |
- reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); |
+fail: |
+ if (keys != NULL) { |
+ for (i = 0; i < saved_ob_size; i++) |
+ Py_DECREF(keys[i]); |
+ if (keys != &ms.temparray[saved_ob_size+1]) |
+ PyMem_FREE(keys); |
+ } |
merge_freemem(&ms); |
dsu_fail: |
+ was_allocated = self->allocated; |
+ self->allocated = saved_allocated; |
final_ob_item = self->ob_item; |
i = Py_SIZE(self); |
Py_SIZE(self) = saved_ob_size; |
self->ob_item = saved_ob_item; |
- self->allocated = saved_allocated; |
- if (final_ob_item != NULL) { |
- /* we cannot use list_clear() for this because it does not |
- guarantee that the list is really empty when it returns */ |
- while (--i >= 0) { |
- Py_XDECREF(final_ob_item[i]); |
+ |
+ if (was_allocated != -1) { |
+ if (result != NULL) { |
+ /* The user mucked with the list during the sort, |
+ * and we don't already have another error to report. |
+ */ |
+ PyErr_SetString(PyExc_ValueError, "list modified during sort"); |
+ result = NULL; |
+ } |
+ |
+ if (final_ob_item != NULL) { |
+ /* we cannot use list_clear() for this because it does not |
+ guarantee that the list is really empty when it returns */ |
+ while (--i >= 0) |
+ Py_XDECREF(final_ob_item[i]); |
+ PyMem_FREE(final_ob_item); |
} |
- PyMem_FREE(final_ob_item); |
} |
+ |
Py_XINCREF(result); |
return result; |
} |
@@ -2862,4 +2853,3 @@ listreviter_len(listreviterobject *it) |
len = 0; |
return PyLong_FromSsize_t(len); |
} |
- |