[Python-checkins] r86937 - in python/branches/py3k: Misc/NEWS Objects/listobject.c
daniel.stutzbach
python-checkins at python.org
Thu Dec 2 22:55:33 CET 2010
Author: daniel.stutzbach
Date: Thu Dec 2 22:55:33 2010
New Revision: 86937
Log:
Issue9915: speeding up sorting with a key
Modified:
python/branches/py3k/Misc/NEWS
python/branches/py3k/Objects/listobject.c
Modified: python/branches/py3k/Misc/NEWS
==============================================================================
--- python/branches/py3k/Misc/NEWS (original)
+++ python/branches/py3k/Misc/NEWS Thu Dec 2 22:55:33 2010
@@ -10,6 +10,8 @@
Core and Builtins
-----------------
+- Issue #9915: Speed up sorting with a key.
+
- Issue #9333: Expose os.symlink only when the SeCreateSymbolicLinkPrivilege
is held by the user's account, i.e., when the function can actually be used.
Modified: python/branches/py3k/Objects/listobject.c
==============================================================================
--- python/branches/py3k/Objects/listobject.c (original)
+++ python/branches/py3k/Objects/listobject.c Thu Dec 2 22:55:33 2010
@@ -940,6 +940,66 @@
* 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.
*/
@@ -965,19 +1025,19 @@
the input (nothing is lost or duplicated).
*/
static int
-binarysort(PyObject **lo, PyObject **hi, PyObject **start)
+binarysort(sortslice 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.keys <= start && start <= hi);
/* assert [lo, start) is sorted */
- if (lo == start)
+ if (lo.keys == start)
++start;
for (; start < hi; ++start) {
/* set l to where *start belongs */
- l = lo;
+ l = lo.keys;
r = start;
pivot = *r;
/* Invariants:
@@ -1004,6 +1064,15 @@
for (p = start; p > l; --p)
*p = *(p-1);
*l = pivot;
+ if (lo.values != NULL) {
+ Py_ssize_t offset = lo.values - lo.keys;
+ p = start + offset;
+ pivot = *p;
+ l += offset;
+ for (p = start + offset; p > l; --p)
+ *p = *(p-1);
+ *l = pivot;
+ }
}
return 0;
@@ -1272,7 +1341,7 @@
* a convenient way to pass state around among the helper functions.
*/
struct s_slice {
- PyObject **base;
+ sortslice base;
Py_ssize_t len;
};
@@ -1286,7 +1355,7 @@
/* '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
@@ -1307,11 +1376,29 @@
/* Conceptually a MergeState's constructor. */
static void
-merge_init(MergeState *ms)
+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) {
+ /* The temporary space for merging will need at most half the list
+ * size rounded up. Use the minimum possible space so we can use the
+ * rest of temparray for other things. In particular, if there is
+ * enough extra space, listsort() will use it to store the keys.
+ */
+ ms->alloced = (list_size + 1) / 2;
+
+ /* ms->alloced describes how many keys will be stored at
+ ms->temparray, but we also need to store the values. Hence,
+ ms->alloced is capped at half of MERGESTATE_TEMP_SIZE. */
+ 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;
}
@@ -1324,10 +1411,8 @@
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 +1421,60 @@
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.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
+ * Must also have that ssa.keys[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,
+ sortslice ssb, Py_ssize_t nb)
{
Py_ssize_t k;
- PyObject **dest;
+ sortslice dest;
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 && ssb.keys && na > 0 && nb > 0);
+ assert(ssa.keys + na == ssb.keys);
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,11 +1491,11 @@
*/
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++;
+ sortslice_copy_incr(&dest, &ssb);
++bcount;
acount = 0;
--nb;
@@ -1412,7 +1505,7 @@
break;
}
else {
- *dest++ = *pa++;
+ sortslice_copy_incr(&dest, &ssa);
++acount;
bcount = 0;
--na;
@@ -1433,14 +1526,14 @@
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;
@@ -1451,24 +1544,24 @@
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 +1573,46 @@
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.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
+ * Must also have that ssa.keys[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,
+ sortslice ssb, Py_ssize_t nb)
{
Py_ssize_t k;
- PyObject **dest;
+ sortslice dest, basea, baseb;
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 && ssb.keys && na > 0 && nb > 0);
+ assert(ssa.keys + na == ssb.keys);
if (MERGE_GETMEM(ms, nb) < 0)
return -1;
- dest = pb + nb - 1;
- memcpy(ms->a, pb, nb * sizeof(PyObject*));
- basea = pa;
+ dest = ssb;
+ sortslice_advance(&dest, nb-1);
+ sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
+ basea = ssa;
baseb = ms->a;
- pb = ms->a + nb - 1;
- pa += na - 1;
+ ssb.keys = ms->a.keys + nb - 1;
+ if (ssb.values != NULL)
+ ssb.values = ms->a.values + nb - 1;
+ sortslice_advance(&ssa, na - 1);
- *dest-- = *pa--;
+ sortslice_copy_decr(&dest, &ssa);
--na;
if (na == 0)
goto Succeed;
@@ -1533,11 +1629,11 @@
*/
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--;
+ sortslice_copy_decr(&dest, &ssa);
++acount;
bcount = 0;
--na;
@@ -1547,7 +1643,7 @@
break;
}
else {
- *dest-- = *pb--;
+ sortslice_copy_decr(&dest, &ssb);
++bcount;
acount = 0;
--nb;
@@ -1568,33 +1664,33 @@
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], basea.keys, 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], baseb.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;
@@ -1605,7 +1701,7 @@
if (nb == 0)
goto Succeed;
}
- *dest-- = *pa--;
+ sortslice_copy_decr(&dest, &ssa);
--na;
if (na == 0)
goto Succeed;
@@ -1617,15 +1713,15 @@
result = 0;
Fail:
if (nb)
- memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*));
+ sortslice_memcpy(&dest, -(nb-1), &baseb, 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 +1731,7 @@
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 +1740,12 @@
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 +1759,10 @@
/* 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 +1770,7 @@
/* 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 +1778,9 @@
* min(na, nb) elements.
*/
if (na <= nb)
- return merge_lo(ms, pa, na, pb, nb);
+ return merge_lo(ms, ssa, na, ssb, nb);
else
- return merge_hi(ms, pa, na, pb, nb);
+ return merge_hi(ms, ssa, na, ssb, nb);
}
/* Examine the stack of runs waiting to be merged, merging adjacent runs
@@ -1765,103 +1861,12 @@
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)
+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,9 +1878,9 @@
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;
@@ -1883,8 +1888,8 @@
int reverse = 0;
PyObject *keyfunc = NULL;
Py_ssize_t i;
- PyObject *key, *value, *kvpair;
static char *kwlist[] = {"key", "reverse", 0};
+ PyObject **keys;
assert(self != NULL);
assert (PyList_Check(self));
@@ -1913,28 +1918,36 @@
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);
- }
- goto dsu_fail;
+ if (keyfunc == NULL) {
+ keys = NULL;
+ lo.keys = saved_ob_item;
+ lo.values = NULL;
+ }
+ else {
+ if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
+ /* Leverage stack space we allocated but won't otherwise use */
+ 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 keyfunc_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)
@@ -1942,30 +1955,31 @@
/* 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, 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)
+ if (binarysort(lo, lo.keys + force, lo.keys + n) < 0)
goto fail;
n = force;
}
@@ -1977,27 +1991,27 @@
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:
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 (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);
}
if (self->allocated != -1 && result != NULL) {
@@ -2013,7 +2027,7 @@
merge_freemem(&ms);
-dsu_fail:
+keyfunc_fail:
final_ob_item = self->ob_item;
i = Py_SIZE(self);
Py_SIZE(self) = saved_ob_size;
@@ -2862,4 +2876,3 @@
len = 0;
return PyLong_FromSsize_t(len);
}
-
More information about the Python-checkins
mailing list