|
|
| OLD | NEW |
|---|---|
| 1 /* List object implementation */ | 1 /* List object implementation */ |
| 2 | 2 |
| 3 #include "Python.h" | 3 #include "Python.h" |
| 4 | 4 |
| 5 #ifdef STDC_HEADERS | 5 #ifdef STDC_HEADERS |
| 6 #include <stddef.h> | 6 #include <stddef.h> |
| 7 #else | 7 #else |
| 8 #include <sys/types.h> /* For size_t */ | 8 #include <sys/types.h> /* For size_t */ |
| 9 #endif | 9 #endif |
| 10 | 10 |
| (...skipping 922 matching lines...) | | Loading... | |
| 933 *hi = t; | 933 *hi = t; |
| 934 ++lo; | 934 ++lo; |
| 935 --hi; | 935 --hi; |
| 936 } | 936 } |
| 937 } | 937 } |
| 938 | 938 |
| 939 /* Lots of code for an adaptive, stable, natural mergesort. There are many | 939 /* Lots of code for an adaptive, stable, natural mergesort. There are many |
| 940 * pieces to this algorithm; read listsort.txt for overviews and details. | 940 * pieces to this algorithm; read listsort.txt for overviews and details. |
| 941 */ | 941 */ |
| 942 | 942 |
| 943 /* A sortslice contains a pointer to an array of keys and a pointer to | |
| 944 * an array of corresponding values. In other words, keys[i] | |
| 945 * corresponds with values[i]. If values == NULL, then the keys are | |
| 946 * also the values. | |
| 947 * | |
| 948 * Several convenience routines are provided here, so that keys and | |
| 949 * values are always moved in sync. | |
| 950 */ | |
| 951 | |
| 952 typedef struct { | |
| 953 PyObject **keys; | |
| 954 PyObject **values; | |
| 955 } sortslice; | |
| 956 | |
| 957 Py_LOCAL_INLINE(void) | |
| 958 sortslice_copy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j) | |
| 959 { | |
| 960 s1->keys[i] = s2->keys[j]; | |
| 961 if (s1->values != NULL) | |
| 962 s1->values[i] = s2->values[j]; | |
| 963 } | |
| 964 | |
| 965 Py_LOCAL_INLINE(void) | |
| 966 sortslice_copy_incr(sortslice *dst, sortslice *src) { | |
| 967 *dst->keys++ = *src->keys++; | |
| 968 if (dst->values != NULL) | |
| 969 *dst->values++ = *src->values++; | |
| 970 } | |
| 971 | |
| 972 Py_LOCAL_INLINE(void) | |
| 973 sortslice_copy_decr(sortslice *dst, sortslice *src) { | |
| 974 *dst->keys-- = *src->keys--; | |
| 975 if (dst->values != NULL) | |
| 976 *dst->values-- = *src->values--; | |
| 977 } | |
| 978 | |
| 979 | |
| 980 Py_LOCAL_INLINE(void) | |
| 981 sortslice_memcpy(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j, | |
| 982 Py_ssize_t n) { | |
| 983 memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n); | |
| 984 if (s1->values != NULL) | |
| 985 memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n); | |
| 986 } | |
| 987 | |
| 988 Py_LOCAL_INLINE(void) | |
| 989 sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j, | |
| 990 Py_ssize_t n) { | |
| 991 memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n); | |
| 992 if (s1->values != NULL) | |
| 993 memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n); | |
| 994 } | |
| 995 | |
| 996 Py_LOCAL_INLINE(void) | |
| 997 sortslice_advance(sortslice *slice, Py_ssize_t n) { | |
| 998 slice->keys += n; | |
| 999 if (slice->values != NULL) | |
| 1000 slice->values += n; | |
| 1001 } | |
| 1002 | |
| 943 /* Comparison function: PyObject_RichCompareBool with Py_LT. | 1003 /* Comparison function: PyObject_RichCompareBool with Py_LT. |
| 944 * Returns -1 on error, 1 if x < y, 0 if x >= y. | 1004 * Returns -1 on error, 1 if x < y, 0 if x >= y. |
| 945 */ | 1005 */ |
| 946 | 1006 |
| 947 #define ISLT(X, Y) (PyObject_RichCompareBool(X, Y, Py_LT)) | 1007 #define ISLT(X, Y) (PyObject_RichCompareBool(X, Y, Py_LT)) |
| 948 | 1008 |
| 949 /* Compare X to Y via "<". Goto "fail" if the comparison raises an | 1009 /* Compare X to Y via "<". Goto "fail" if the comparison raises an |
| 950 error. Else "k" is set to true iff X<Y, and an "if (k)" block is | 1010 error. Else "k" is set to true iff X<Y, and an "if (k)" block is |
| 951 started. It makes more sense in context <wink>. X and Y are PyObject*s. | 1011 started. It makes more sense in context <wink>. X and Y are PyObject*s. |
| 952 */ | 1012 */ |
| 953 #define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail; \ | 1013 #define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail; \ |
| 954 if (k) | 1014 if (k) |
| 955 | 1015 |
| 956 /* binarysort is the best method for sorting small arrays: it does | 1016 /* binarysort is the best method for sorting small arrays: it does |
| 957 few compares, but can do data movement quadratic in the number of | 1017 few compares, but can do data movement quadratic in the number of |
| 958 elements. | 1018 elements. |
| 959 [lo, hi) is a contiguous slice of a list, and is sorted via | 1019 [lo, hi) is a contiguous slice of a list, and is sorted via |
| 960 binary insertion. This sort is stable. | 1020 binary insertion. This sort is stable. |
| 961 On entry, must have lo <= start <= hi, and that [lo, start) is already | 1021 On entry, must have lo <= start <= hi, and that [lo, start) is already |
| 962 sorted (pass start == lo if you don't know!). | 1022 sorted (pass start == lo if you don't know!). |
| 963 If islt() complains return -1, else 0. | 1023 If islt() complains return -1, else 0. |
| 964 Even in case of error, the output slice will be some permutation of | 1024 Even in case of error, the output slice will be some permutation of |
| 965 the input (nothing is lost or duplicated). | 1025 the input (nothing is lost or duplicated). |
| 966 */ | 1026 */ |
| 967 static int | 1027 static int |
| 968 binarysort(PyObject **lo, PyObject **hi, PyObject **start) | 1028 binarysort(sortslice lo, PyObject **hi, PyObject **start) |
| 969 { | 1029 { |
| 970 register Py_ssize_t k; | 1030 register Py_ssize_t k; |
| 971 register PyObject **l, **p, **r; | 1031 register PyObject **l, **p, **r; |
| 972 register PyObject *pivot; | 1032 register PyObject *pivot; |
| 973 | 1033 |
| 974 assert(lo <= start && start <= hi); | 1034 assert(lo.keys <= start && start <= hi); |
| 975 /* assert [lo, start) is sorted */ | 1035 /* assert [lo, start) is sorted */ |
| 976 if (lo == start) | 1036 if (lo.keys == start) |
| 977 ++start; | 1037 ++start; |
| 978 for (; start < hi; ++start) { | 1038 for (; start < hi; ++start) { |
| 979 /* set l to where *start belongs */ | 1039 /* set l to where *start belongs */ |
| 980 l = lo; | 1040 l = lo.keys; |
| 981 r = start; | 1041 r = start; |
| 982 pivot = *r; | 1042 pivot = *r; |
| 983 /* Invariants: | 1043 /* Invariants: |
| 984 * pivot >= all in [lo, l). | 1044 * pivot >= all in [lo, l). |
| 985 * pivot < all in [r, start). | 1045 * pivot < all in [r, start). |
| 986 * The second is vacuously true at the start. | 1046 * The second is vacuously true at the start. |
| 987 */ | 1047 */ |
| 988 assert(l < r); | 1048 assert(l < r); |
| 989 do { | 1049 do { |
| 990 p = l + ((r - l) >> 1); | 1050 p = l + ((r - l) >> 1); |
| 991 IFLT(pivot, *p) | 1051 IFLT(pivot, *p) |
| 992 r = p; | 1052 r = p; |
| 993 else | 1053 else |
| 994 l = p+1; | 1054 l = p+1; |
| 995 } while (l < r); | 1055 } while (l < r); |
| 996 assert(l == r); | 1056 assert(l == r); |
| 997 /* The invariants still hold, so pivot >= all in [lo, l) and | 1057 /* The invariants still hold, so pivot >= all in [lo, l) and |
| 998 pivot < all in [l, start), so pivot belongs at l. Note | 1058 pivot < all in [l, start), so pivot belongs at l. Note |
| 999 that if there are elements equal to pivot, l points to the | 1059 that if there are elements equal to pivot, l points to the |
| 1000 first slot after them -- that's why this sort is stable. | 1060 first slot after them -- that's why this sort is stable. |
| 1001 Slide over to make room. | 1061 Slide over to make room. |
| 1002 Caution: using memmove is much slower under MSVC 5; | 1062 Caution: using memmove is much slower under MSVC 5; |
| 1003 we're not usually moving many slots. */ | 1063 we're not usually moving many slots. */ |
| 1004 for (p = start; p > l; --p) | 1064 for (p = start; p > l; --p) |
| 1005 *p = *(p-1); | 1065 *p = *(p-1); |
| 1006 *l = pivot; | 1066 *l = pivot; |
| 1067 if (lo.values != NULL) { | |
| 1068 Py_ssize_t offset = lo.values - lo.keys; | |
| 1069 p = start + offset; | |
| 1070 pivot = *p; | |
| 1071 l += offset; | |
| 1072 for (p = start + offset; p > l; --p) | |
| 1073 *p = *(p-1); | |
| 1074 *l = pivot; | |
| 1075 } | |
| 1007 } | 1076 } |
| 1008 return 0; | 1077 return 0; |
| 1009 | 1078 |
| 1010 fail: | 1079 fail: |
| 1011 return -1; | 1080 return -1; |
| 1012 } | 1081 } |
| 1013 | 1082 |
| 1014 /* | 1083 /* |
| 1015 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi | 1084 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi |
| 1016 is required on entry. "A run" is the longest ascending sequence, with | 1085 is required on entry. "A run" is the longest ascending sequence, with |
| (...skipping 248 matching lines...) | | Loading... | |
| 1265 */ | 1334 */ |
| 1266 #define MIN_GALLOP 7 | 1335 #define MIN_GALLOP 7 |
| 1267 | 1336 |
| 1268 /* Avoid malloc for small temp arrays. */ | 1337 /* Avoid malloc for small temp arrays. */ |
| 1269 #define MERGESTATE_TEMP_SIZE 256 | 1338 #define MERGESTATE_TEMP_SIZE 256 |
| 1270 | 1339 |
| 1271 /* One MergeState exists on the stack per invocation of mergesort. It's just | 1340 /* One MergeState exists on the stack per invocation of mergesort. It's just |
| 1272 * a convenient way to pass state around among the helper functions. | 1341 * a convenient way to pass state around among the helper functions. |
| 1273 */ | 1342 */ |
| 1274 struct s_slice { | 1343 struct s_slice { |
| 1275 PyObject **base; | 1344 sortslice base; |
| 1276 Py_ssize_t len; | 1345 Py_ssize_t len; |
| 1277 }; | 1346 }; |
| 1278 | 1347 |
| 1279 typedef struct s_MergeState { | 1348 typedef struct s_MergeState { |
| 1280 /* This controls when we get *into* galloping mode. It's initialized | 1349 /* This controls when we get *into* galloping mode. It's initialized |
| 1281 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for | 1350 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for |
| 1282 * random data, and lower for highly structured data. | 1351 * random data, and lower for highly structured data. |
| 1283 */ | 1352 */ |
| 1284 Py_ssize_t min_gallop; | 1353 Py_ssize_t min_gallop; |
| 1285 | 1354 |
| 1286 /* 'a' is temp storage to help with merges. It contains room for | 1355 /* 'a' is temp storage to help with merges. It contains room for |
| 1287 * alloced entries. | 1356 * alloced entries. |
| 1288 */ | 1357 */ |
| 1289 PyObject **a; /* may point to temparray below */ | 1358 sortslice a; /* may point to temparray below */ |
| 1290 Py_ssize_t alloced; | 1359 Py_ssize_t alloced; |
| 1291 | 1360 |
| 1292 /* A stack of n pending runs yet to be merged. Run #i starts at | 1361 /* A stack of n pending runs yet to be merged. Run #i starts at |
| 1293 * address base[i] and extends for len[i] elements. It's always | 1362 * address base[i] and extends for len[i] elements. It's always |
| 1294 * true (so long as the indices are in bounds) that | 1363 * true (so long as the indices are in bounds) that |
| 1295 * | 1364 * |
| 1296 * pending[i].base + pending[i].len == pending[i+1].base | 1365 * pending[i].base + pending[i].len == pending[i+1].base |
| 1297 * | 1366 * |
| 1298 * so we could cut the storage for this, but it's a minor amount, | 1367 * so we could cut the storage for this, but it's a minor amount, |
| 1299 * and keeping all the info explicit simplifies the code. | 1368 * and keeping all the info explicit simplifies the code. |
| 1300 */ | 1369 */ |
| 1301 int n; | 1370 int n; |
| 1302 struct s_slice pending[MAX_MERGE_PENDING]; | 1371 struct s_slice pending[MAX_MERGE_PENDING]; |
| 1303 | 1372 |
| 1304 /* 'a' points to this when possible, rather than muck with malloc. */ | 1373 /* 'a' points to this when possible, rather than muck with malloc. */ |
| 1305 PyObject *temparray[MERGESTATE_TEMP_SIZE]; | 1374 PyObject *temparray[MERGESTATE_TEMP_SIZE]; |
| 1306 } MergeState; | 1375 } MergeState; |
| 1307 | 1376 |
| 1308 /* Conceptually a MergeState's constructor. */ | 1377 /* Conceptually a MergeState's constructor. */ |
| 1309 static void | 1378 static void |
| 1310 merge_init(MergeState *ms) | 1379 merge_init(MergeState *ms, int list_size, int has_keyfunc) |
| 1311 { | 1380 { |
| 1312 assert(ms != NULL); | 1381 assert(ms != NULL); |
| 1313 ms->a = ms->temparray; | 1382 if (has_keyfunc) { |
| 1314 ms->alloced = MERGESTATE_TEMP_SIZE; | 1383 ms->alloced = (list_size+1)/2; |
|
Antoine Pitrou
2010年12月01日 21:20:24
Can you add a comment before all this? It's not ob
Can you add a comment before all this? It's not obvious why "(list_size+1)/2".
Are you trying to make everything contiguous to improve cache efficiency?
stutzbach
2010年12月01日 22:08:26
I think that's what I was trying to do, but I don'
On 2010年12月01日 21:20:24, Antoine Pitrou wrote:
> Can you add a comment before all this? It's not obvious why "(list_size+1)/2".
> Are you trying to make everything contiguous to improve cache efficiency?
I think that's what I was trying to do, but I don't think it actually achieves
that. I tried playing around with a couple of variations just now (including
one that does result in contiguous use of memory), and it does not appear to
have a significant impact on performance.
I'll take this out and simply always set ms->alloced = MERGESTATE_TEMP_SIZE / 2
when has_keyfunc is true.
| |
| 1384 if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced) | |
| 1385 ms->alloced = MERGESTATE_TEMP_SIZE / 2; | |
| 1386 ms->a.values = &ms->temparray[ms->alloced]; | |
| 1387 } | |
| 1388 else { | |
| 1389 ms->alloced = MERGESTATE_TEMP_SIZE; | |
| 1390 ms->a.values = NULL; | |
| 1391 } | |
| 1392 ms->a.keys = ms->temparray; | |
| 1315 ms->n = 0; | 1393 ms->n = 0; |
| 1316 ms->min_gallop = MIN_GALLOP; | 1394 ms->min_gallop = MIN_GALLOP; |
| 1317 } | 1395 } |
| 1318 | 1396 |
| 1319 /* Free all the temp memory owned by the MergeState. This must be called | 1397 /* Free all the temp memory owned by the MergeState. This must be called |
| 1320 * when you're done with a MergeState, and may be called before then if | 1398 * when you're done with a MergeState, and may be called before then if |
| 1321 * you want to free the temp memory early. | 1399 * you want to free the temp memory early. |
| 1322 */ | 1400 */ |
| 1323 static void | 1401 static void |
| 1324 merge_freemem(MergeState *ms) | 1402 merge_freemem(MergeState *ms) |
| 1325 { | 1403 { |
| 1326 assert(ms != NULL); | 1404 assert(ms != NULL); |
| 1327 if (ms->a != ms->temparray) | 1405 if (ms->a.keys != ms->temparray) |
| 1328 PyMem_Free(ms->a); | 1406 PyMem_Free(ms->a.keys); |
| 1329 ms->a = ms->temparray; | |
| 1330 ms->alloced = MERGESTATE_TEMP_SIZE; | |
| 1331 } | 1407 } |
| 1332 | 1408 |
| 1333 /* Ensure enough temp memory for 'need' array slots is available. | 1409 /* Ensure enough temp memory for 'need' array slots is available. |
| 1334 * Returns 0 on success and -1 if the memory can't be gotten. | 1410 * Returns 0 on success and -1 if the memory can't be gotten. |
| 1335 */ | 1411 */ |
| 1336 static int | 1412 static int |
| 1337 merge_getmem(MergeState *ms, Py_ssize_t need) | 1413 merge_getmem(MergeState *ms, Py_ssize_t need) |
| 1338 { | 1414 { |
| 1415 int multiplier; | |
| 1416 | |
| 1339 assert(ms != NULL); | 1417 assert(ms != NULL); |
| 1340 if (need <= ms->alloced) | 1418 if (need <= ms->alloced) |
| 1341 return 0; | 1419 return 0; |
| 1420 | |
| 1421 multiplier = ms->a.values != NULL ? 2 : 1; | |
| 1422 | |
| 1342 /* Don't realloc! That can cost cycles to copy the old data, but | 1423 /* Don't realloc! That can cost cycles to copy the old data, but |
| 1343 * we don't care what's in the block. | 1424 * we don't care what's in the block. |
| 1344 */ | 1425 */ |
| 1345 merge_freemem(ms); | 1426 merge_freemem(ms); |
| 1346 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) { | 1427 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*) / multiplier) { |
| 1347 PyErr_NoMemory(); | 1428 PyErr_NoMemory(); |
| 1348 return -1; | 1429 return -1; |
| 1349 } | 1430 } |
| 1350 ms->a = (PyObject**)PyMem_Malloc(need * sizeof(PyObject*)); | 1431 ms->a.keys = (PyObject**)PyMem_Malloc(multiplier * need |
| 1351 if (ms->a) { | 1432 * sizeof(PyObject*)); |
| 1433 if (ms->a.keys != NULL) { | |
| 1352 ms->alloced = need; | 1434 ms->alloced = need; |
| 1435 if (ms->a.values != NULL) | |
| 1436 ms->a.values = &ms->a.keys[need]; | |
| 1353 return 0; | 1437 return 0; |
| 1354 } | 1438 } |
| 1355 PyErr_NoMemory(); | 1439 PyErr_NoMemory(); |
| 1356 merge_freemem(ms); /* reset to sane state */ | |
| 1357 return -1; | 1440 return -1; |
| 1358 } | 1441 } |
| 1359 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ | 1442 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ |
| 1360 merge_getmem(MS, NEED)) | 1443 merge_getmem(MS, NEED)) |
| 1361 | 1444 |
| 1362 /* Merge the na elements starting at pa with the nb elements starting at pb | 1445 /* Merge the na elements starting at ssa with the nb elements starting at |
| 1363 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | 1446 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0. |
| 1364 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | 1447 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and |
| 1365 * merge, and should have na <= nb. See listsort.txt for more info. | 1448 * should have na <= nb. See listsort.txt for more info. Return 0 if |
| 1366 * Return 0 if successful, -1 if error. | 1449 * successful, -1 if error. |
| 1367 */ | 1450 */ |
| 1368 static Py_ssize_t | 1451 static Py_ssize_t |
| 1369 merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na, | 1452 merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na, |
| 1370 PyObject **pb, Py_ssize_t nb) | 1453 sortslice ssb, Py_ssize_t nb) |
| 1371 { | 1454 { |
| 1372 Py_ssize_t k; | 1455 Py_ssize_t k; |
| 1373 PyObject **dest; | 1456 sortslice dest; |
| 1374 int result = -1; /* guilty until proved innocent */ | 1457 int result = -1; /* guilty until proved innocent */ |
| 1375 Py_ssize_t min_gallop; | 1458 Py_ssize_t min_gallop; |
| 1376 | 1459 |
| 1377 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); | 1460 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0); |
| 1461 assert(ssa.keys + na == ssb.keys); | |
| 1378 if (MERGE_GETMEM(ms, na) < 0) | 1462 if (MERGE_GETMEM(ms, na) < 0) |
| 1379 return -1; | 1463 return -1; |
| 1380 memcpy(ms->a, pa, na * sizeof(PyObject*)); | 1464 sortslice_memcpy(&ms->a, 0, &ssa, 0, na); |
| 1381 dest = pa; | 1465 dest = ssa; |
| 1382 pa = ms->a; | 1466 ssa = ms->a; |
| 1383 | 1467 |
| 1384 *dest++ = *pb++; | 1468 sortslice_copy_incr(&dest, &ssb); |
| 1385 --nb; | 1469 --nb; |
| 1386 if (nb == 0) | 1470 if (nb == 0) |
| 1387 goto Succeed; | 1471 goto Succeed; |
| 1388 if (na == 1) | 1472 if (na == 1) |
| 1389 goto CopyB; | 1473 goto CopyB; |
| 1390 | 1474 |
| 1391 min_gallop = ms->min_gallop; | 1475 min_gallop = ms->min_gallop; |
| 1392 for (;;) { | 1476 for (;;) { |
| 1393 Py_ssize_t acount = 0; /* # of times A won in a row */ | 1477 Py_ssize_t acount = 0; /* # of times A won in a row */ |
| 1394 Py_ssize_t bcount = 0; /* # of times B won in a row */ | 1478 Py_ssize_t bcount = 0; /* # of times B won in a row */ |
| 1395 | 1479 |
| 1396 /* Do the straightforward thing until (if ever) one run | 1480 /* Do the straightforward thing until (if ever) one run |
| 1397 * appears to win consistently. | 1481 * appears to win consistently. |
| 1398 */ | 1482 */ |
| 1399 for (;;) { | 1483 for (;;) { |
| 1400 assert(na > 1 && nb > 0); | 1484 assert(na > 1 && nb > 0); |
| 1401 k = ISLT(*pb, *pa); | 1485 k = ISLT(ssb.keys[0], ssa.keys[0]); |
| 1402 if (k) { | 1486 if (k) { |
| 1403 if (k < 0) | 1487 if (k < 0) |
| 1404 goto Fail; | 1488 goto Fail; |
| 1405 *dest++ = *pb++; | 1489 sortslice_copy_incr(&dest, &ssb); |
| 1406 ++bcount; | 1490 ++bcount; |
| 1407 acount = 0; | 1491 acount = 0; |
| 1408 --nb; | 1492 --nb; |
| 1409 if (nb == 0) | 1493 if (nb == 0) |
| 1410 goto Succeed; | 1494 goto Succeed; |
| 1411 if (bcount >= min_gallop) | 1495 if (bcount >= min_gallop) |
| 1412 break; | 1496 break; |
| 1413 } | 1497 } |
| 1414 else { | 1498 else { |
| 1415 *dest++ = *pa++; | 1499 sortslice_copy_incr(&dest, &ssa); |
| 1416 ++acount; | 1500 ++acount; |
| 1417 bcount = 0; | 1501 bcount = 0; |
| 1418 --na; | 1502 --na; |
| 1419 if (na == 1) | 1503 if (na == 1) |
| 1420 goto CopyB; | 1504 goto CopyB; |
| 1421 if (acount >= min_gallop) | 1505 if (acount >= min_gallop) |
| 1422 break; | 1506 break; |
| 1423 } | 1507 } |
| 1424 } | 1508 } |
| 1425 | 1509 |
| 1426 /* One run is winning so consistently that galloping may | 1510 /* One run is winning so consistently that galloping may |
| 1427 * be a huge win. So try that, and continue galloping until | 1511 * be a huge win. So try that, and continue galloping until |
| 1428 * (if ever) neither run appears to be winning consistently | 1512 * (if ever) neither run appears to be winning consistently |
| 1429 * anymore. | 1513 * anymore. |
| 1430 */ | 1514 */ |
| 1431 ++min_gallop; | 1515 ++min_gallop; |
| 1432 do { | 1516 do { |
| 1433 assert(na > 1 && nb > 0); | 1517 assert(na > 1 && nb > 0); |
| 1434 min_gallop -= min_gallop > 1; | 1518 min_gallop -= min_gallop > 1; |
| 1435 ms->min_gallop = min_gallop; | 1519 ms->min_gallop = min_gallop; |
| 1436 k = gallop_right(*pb, pa, na, 0); | 1520 k = gallop_right(ssb.keys[0], ssa.keys, na, 0); |
| 1437 acount = k; | 1521 acount = k; |
| 1438 if (k) { | 1522 if (k) { |
| 1439 if (k < 0) | 1523 if (k < 0) |
| 1440 goto Fail; | 1524 goto Fail; |
| 1441 memcpy(dest, pa, k * sizeof(PyObject *)); | 1525 sortslice_memcpy(&dest, 0, &ssa, 0, k); |
| 1442 dest += k; | 1526 sortslice_advance(&dest, k); |
| 1443 pa += k; | 1527 sortslice_advance(&ssa, k); |
| 1444 na -= k; | 1528 na -= k; |
| 1445 if (na == 1) | 1529 if (na == 1) |
| 1446 goto CopyB; | 1530 goto CopyB; |
| 1447 /* na==0 is impossible now if the comparison | 1531 /* na==0 is impossible now if the comparison |
| 1448 * function is consistent, but we can't assume | 1532 * function is consistent, but we can't assume |
| 1449 * that it is. | 1533 * that it is. |
| 1450 */ | 1534 */ |
| 1451 if (na == 0) | 1535 if (na == 0) |
| 1452 goto Succeed; | 1536 goto Succeed; |
| 1453 } | 1537 } |
| 1454 *dest++ = *pb++; | 1538 sortslice_copy_incr(&dest, &ssb); |
| 1455 --nb; | 1539 --nb; |
| 1456 if (nb == 0) | 1540 if (nb == 0) |
| 1457 goto Succeed; | 1541 goto Succeed; |
| 1458 | 1542 |
| 1459 k = gallop_left(*pa, pb, nb, 0); | 1543 k = gallop_left(ssa.keys[0], ssb.keys, nb, 0); |
| 1460 bcount = k; | 1544 bcount = k; |
| 1461 if (k) { | 1545 if (k) { |
| 1462 if (k < 0) | 1546 if (k < 0) |
| 1463 goto Fail; | 1547 goto Fail; |
| 1464 memmove(dest, pb, k * sizeof(PyObject *)); | 1548 sortslice_memmove(&dest, 0, &ssb, 0, k); |
| 1465 dest += k; | 1549 sortslice_advance(&dest, k); |
| 1466 pb += k; | 1550 sortslice_advance(&ssb, k); |
| 1467 nb -= k; | 1551 nb -= k; |
| 1468 if (nb == 0) | 1552 if (nb == 0) |
| 1469 goto Succeed; | 1553 goto Succeed; |
| 1470 } | 1554 } |
| 1471 *dest++ = *pa++; | 1555 sortslice_copy_incr(&dest, &ssa); |
| 1472 --na; | 1556 --na; |
| 1473 if (na == 1) | 1557 if (na == 1) |
| 1474 goto CopyB; | 1558 goto CopyB; |
| 1475 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); | 1559 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
| 1476 ++min_gallop; /* penalize it for leaving galloping mode */ | 1560 ++min_gallop; /* penalize it for leaving galloping mode */ |
| 1477 ms->min_gallop = min_gallop; | 1561 ms->min_gallop = min_gallop; |
| 1478 } | 1562 } |
| 1479 Succeed: | 1563 Succeed: |
| 1480 result = 0; | 1564 result = 0; |
| 1481 Fail: | 1565 Fail: |
| 1482 if (na) | 1566 if (na) |
| 1483 memcpy(dest, pa, na * sizeof(PyObject*)); | 1567 sortslice_memcpy(&dest, 0, &ssa, 0, na); |
| 1484 return result; | 1568 return result; |
| 1485 CopyB: | 1569 CopyB: |
| 1486 assert(na == 1 && nb > 0); | 1570 assert(na == 1 && nb > 0); |
| 1487 /* The last element of pa belongs at the end of the merge. */ | 1571 /* The last element of ssa belongs at the end of the merge. */ |
| 1488 memmove(dest, pb, nb * sizeof(PyObject *)); | 1572 sortslice_memmove(&dest, 0, &ssb, 0, nb); |
| 1489 dest[nb] = *pa; | 1573 sortslice_copy(&dest, nb, &ssa, 0); |
| 1490 return 0; | 1574 return 0; |
| 1491 } | 1575 } |
| 1492 | 1576 |
| 1493 /* Merge the na elements starting at pa with the nb elements starting at pb | 1577 /* Merge the na elements starting at pa with the nb elements starting at |
| 1494 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | 1578 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0. |
| 1495 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | 1579 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and |
| 1496 * merge, and should have na >= nb. See listsort.txt for more info. | 1580 * should have na >= nb. See listsort.txt for more info. Return 0 if |
| 1497 * Return 0 if successful, -1 if error. | 1581 * successful, -1 if error. |
| 1498 */ | 1582 */ |
| 1499 static Py_ssize_t | 1583 static Py_ssize_t |
| 1500 merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb) | 1584 merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na, |
| 1585 sortslice ssb, Py_ssize_t nb) | |
| 1501 { | 1586 { |
| 1502 Py_ssize_t k; | 1587 Py_ssize_t k; |
| 1503 PyObject **dest; | 1588 sortslice dest, basea, baseb; |
| 1504 int result = -1; /* guilty until proved innocent */ | 1589 int result = -1; /* guilty until proved innocent */ |
| 1505 PyObject **basea; | |
| 1506 PyObject **baseb; | |
| 1507 Py_ssize_t min_gallop; | 1590 Py_ssize_t min_gallop; |
| 1508 | 1591 |
| 1509 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); | 1592 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0); |
| 1593 assert(ssa.keys + na == ssb.keys); | |
| 1510 if (MERGE_GETMEM(ms, nb) < 0) | 1594 if (MERGE_GETMEM(ms, nb) < 0) |
| 1511 return -1; | 1595 return -1; |
| 1512 dest = pb + nb - 1; | 1596 dest = ssb; |
| 1513 memcpy(ms->a, pb, nb * sizeof(PyObject*)); | 1597 sortslice_advance(&dest, nb-1); |
| 1514 basea = pa; | 1598 sortslice_memcpy(&ms->a, 0, &ssb, 0, nb); |
| 1599 basea = ssa; | |
| 1515 baseb = ms->a; | 1600 baseb = ms->a; |
| 1516 pb = ms->a + nb - 1; | 1601 ssb.keys = ms->a.keys + nb - 1; |
| 1517 pa += na - 1; | 1602 if (ssb.values != NULL) |
| 1603 ssb.values = ms->a.values + nb - 1; | |
| 1604 sortslice_advance(&ssa, na - 1); | |
| 1518 | 1605 |
| 1519 *dest-- = *pa--; | 1606 sortslice_copy_decr(&dest, &ssa); |
| 1520 --na; | 1607 --na; |
| 1521 if (na == 0) | 1608 if (na == 0) |
| 1522 goto Succeed; | 1609 goto Succeed; |
| 1523 if (nb == 1) | 1610 if (nb == 1) |
| 1524 goto CopyA; | 1611 goto CopyA; |
| 1525 | 1612 |
| 1526 min_gallop = ms->min_gallop; | 1613 min_gallop = ms->min_gallop; |
| 1527 for (;;) { | 1614 for (;;) { |
| 1528 Py_ssize_t acount = 0; /* # of times A won in a row */ | 1615 Py_ssize_t acount = 0; /* # of times A won in a row */ |
| 1529 Py_ssize_t bcount = 0; /* # of times B won in a row */ | 1616 Py_ssize_t bcount = 0; /* # of times B won in a row */ |
| 1530 | 1617 |
| 1531 /* Do the straightforward thing until (if ever) one run | 1618 /* Do the straightforward thing until (if ever) one run |
| 1532 * appears to win consistently. | 1619 * appears to win consistently. |
| 1533 */ | 1620 */ |
| 1534 for (;;) { | 1621 for (;;) { |
| 1535 assert(na > 0 && nb > 1); | 1622 assert(na > 0 && nb > 1); |
| 1536 k = ISLT(*pb, *pa); | 1623 k = ISLT(ssb.keys[0], ssa.keys[0]); |
| 1537 if (k) { | 1624 if (k) { |
| 1538 if (k < 0) | 1625 if (k < 0) |
| 1539 goto Fail; | 1626 goto Fail; |
| 1540 *dest-- = *pa--; | 1627 sortslice_copy_decr(&dest, &ssa); |
| 1541 ++acount; | 1628 ++acount; |
| 1542 bcount = 0; | 1629 bcount = 0; |
| 1543 --na; | 1630 --na; |
| 1544 if (na == 0) | 1631 if (na == 0) |
| 1545 goto Succeed; | 1632 goto Succeed; |
| 1546 if (acount >= min_gallop) | 1633 if (acount >= min_gallop) |
| 1547 break; | 1634 break; |
| 1548 } | 1635 } |
| 1549 else { | 1636 else { |
| 1550 *dest-- = *pb--; | 1637 sortslice_copy_decr(&dest, &ssb); |
| 1551 ++bcount; | 1638 ++bcount; |
| 1552 acount = 0; | 1639 acount = 0; |
| 1553 --nb; | 1640 --nb; |
| 1554 if (nb == 1) | 1641 if (nb == 1) |
| 1555 goto CopyA; | 1642 goto CopyA; |
| 1556 if (bcount >= min_gallop) | 1643 if (bcount >= min_gallop) |
| 1557 break; | 1644 break; |
| 1558 } | 1645 } |
| 1559 } | 1646 } |
| 1560 | 1647 |
| 1561 /* One run is winning so consistently that galloping may | 1648 /* One run is winning so consistently that galloping may |
| 1562 * be a huge win. So try that, and continue galloping until | 1649 * be a huge win. So try that, and continue galloping until |
| 1563 * (if ever) neither run appears to be winning consistently | 1650 * (if ever) neither run appears to be winning consistently |
| 1564 * anymore. | 1651 * anymore. |
| 1565 */ | 1652 */ |
| 1566 ++min_gallop; | 1653 ++min_gallop; |
| 1567 do { | 1654 do { |
| 1568 assert(na > 0 && nb > 1); | 1655 assert(na > 0 && nb > 1); |
| 1569 min_gallop -= min_gallop > 1; | 1656 min_gallop -= min_gallop > 1; |
| 1570 ms->min_gallop = min_gallop; | 1657 ms->min_gallop = min_gallop; |
| 1571 k = gallop_right(*pb, basea, na, na-1); | 1658 k = gallop_right(ssb.keys[0], basea.keys, na, na-1); |
| 1572 if (k < 0) | 1659 if (k < 0) |
| 1573 goto Fail; | 1660 goto Fail; |
| 1574 k = na - k; | 1661 k = na - k; |
| 1575 acount = k; | 1662 acount = k; |
| 1576 if (k) { | 1663 if (k) { |
| 1577 dest -= k; | 1664 sortslice_advance(&dest, -k); |
| 1578 pa -= k; | 1665 sortslice_advance(&ssa, -k); |
| 1579 memmove(dest+1, pa+1, k * sizeof(PyObject *)); | 1666 sortslice_memmove(&dest, 1, &ssa, 1, k); |
| 1580 na -= k; | 1667 na -= k; |
| 1581 if (na == 0) | 1668 if (na == 0) |
| 1582 goto Succeed; | 1669 goto Succeed; |
| 1583 } | 1670 } |
| 1584 *dest-- = *pb--; | 1671 sortslice_copy_decr(&dest, &ssb); |
| 1585 --nb; | 1672 --nb; |
| 1586 if (nb == 1) | 1673 if (nb == 1) |
| 1587 goto CopyA; | 1674 goto CopyA; |
| 1588 | 1675 |
| 1589 k = gallop_left(*pa, baseb, nb, nb-1); | 1676 k = gallop_left(ssa.keys[0], baseb.keys, nb, nb-1); |
| 1590 if (k < 0) | 1677 if (k < 0) |
| 1591 goto Fail; | 1678 goto Fail; |
| 1592 k = nb - k; | 1679 k = nb - k; |
| 1593 bcount = k; | 1680 bcount = k; |
| 1594 if (k) { | 1681 if (k) { |
| 1595 dest -= k; | 1682 sortslice_advance(&dest, -k); |
| 1596 pb -= k; | 1683 sortslice_advance(&ssb, -k); |
| 1597 memcpy(dest+1, pb+1, k * sizeof(PyObject *)); | 1684 sortslice_memcpy(&dest, 1, &ssb, 1, k); |
| 1598 nb -= k; | 1685 nb -= k; |
| 1599 if (nb == 1) | 1686 if (nb == 1) |
| 1600 goto CopyA; | 1687 goto CopyA; |
| 1601 /* nb==0 is impossible now if the comparison | 1688 /* nb==0 is impossible now if the comparison |
| 1602 * function is consistent, but we can't assume | 1689 * function is consistent, but we can't assume |
| 1603 * that it is. | 1690 * that it is. |
| 1604 */ | 1691 */ |
| 1605 if (nb == 0) | 1692 if (nb == 0) |
| 1606 goto Succeed; | 1693 goto Succeed; |
| 1607 } | 1694 } |
| 1608 *dest-- = *pa--; | 1695 sortslice_copy_decr(&dest, &ssa); |
| 1609 --na; | 1696 --na; |
| 1610 if (na == 0) | 1697 if (na == 0) |
| 1611 goto Succeed; | 1698 goto Succeed; |
| 1612 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); | 1699 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
| 1613 ++min_gallop; /* penalize it for leaving galloping mode */ | 1700 ++min_gallop; /* penalize it for leaving galloping mode */ |
| 1614 ms->min_gallop = min_gallop; | 1701 ms->min_gallop = min_gallop; |
| 1615 } | 1702 } |
| 1616 Succeed: | 1703 Succeed: |
| 1617 result = 0; | 1704 result = 0; |
| 1618 Fail: | 1705 Fail: |
| 1619 if (nb) | 1706 if (nb) |
| 1620 memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*)); | 1707 sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb); |
| 1621 return result; | 1708 return result; |
| 1622 CopyA: | 1709 CopyA: |
| 1623 assert(nb == 1 && na > 0); | 1710 assert(nb == 1 && na > 0); |
| 1624 /* The first element of pb belongs at the front of the merge. */ | 1711 /* The first element of ssb belongs at the front of the merge. */ |
| 1625 dest -= na; | 1712 sortslice_memmove(&dest, 1-na, &ssa, 1-na, na); |
| 1626 pa -= na; | 1713 sortslice_advance(&dest, -na); |
| 1627 memmove(dest+1, pa+1, na * sizeof(PyObject *)); | 1714 sortslice_advance(&ssa, -na); |
| 1628 *dest = *pb; | 1715 sortslice_copy(&dest, 0, &ssb, 0); |
| 1629 return 0; | 1716 return 0; |
| 1630 } | 1717 } |
| 1631 | 1718 |
| 1632 /* Merge the two runs at stack indices i and i+1. | 1719 /* Merge the two runs at stack indices i and i+1. |
| 1633 * Returns 0 on success, -1 on error. | 1720 * Returns 0 on success, -1 on error. |
| 1634 */ | 1721 */ |
| 1635 static Py_ssize_t | 1722 static Py_ssize_t |
| 1636 merge_at(MergeState *ms, Py_ssize_t i) | 1723 merge_at(MergeState *ms, Py_ssize_t i) |
| 1637 { | 1724 { |
| 1638 PyObject **pa, **pb; | 1725 sortslice ssa, ssb; |
| 1639 Py_ssize_t na, nb; | 1726 Py_ssize_t na, nb; |
| 1640 Py_ssize_t k; | 1727 Py_ssize_t k; |
| 1641 | 1728 |
| 1642 assert(ms != NULL); | 1729 assert(ms != NULL); |
| 1643 assert(ms->n >= 2); | 1730 assert(ms->n >= 2); |
| 1644 assert(i >= 0); | 1731 assert(i >= 0); |
| 1645 assert(i == ms->n - 2 || i == ms->n - 3); | 1732 assert(i == ms->n - 2 || i == ms->n - 3); |
| 1646 | 1733 |
| 1647 pa = ms->pending[i].base; | 1734 ssa = ms->pending[i].base; |
| 1648 na = ms->pending[i].len; | 1735 na = ms->pending[i].len; |
| 1649 pb = ms->pending[i+1].base; | 1736 ssb = ms->pending[i+1].base; |
| 1650 nb = ms->pending[i+1].len; | 1737 nb = ms->pending[i+1].len; |
| 1651 assert(na > 0 && nb > 0); | 1738 assert(na > 0 && nb > 0); |
| 1652 assert(pa + na == pb); | 1739 assert(ssa.keys + na == ssb.keys); |
| 1653 | 1740 |
| 1654 /* Record the length of the combined runs; if i is the 3rd-last | 1741 /* Record the length of the combined runs; if i is the 3rd-last |
| 1655 * run now, also slide over the last run (which isn't involved | 1742 * run now, also slide over the last run (which isn't involved |
| 1656 * in this merge). The current run i+1 goes away in any case. | 1743 * in this merge). The current run i+1 goes away in any case. |
| 1657 */ | 1744 */ |
| 1658 ms->pending[i].len = na + nb; | 1745 ms->pending[i].len = na + nb; |
| 1659 if (i == ms->n - 3) | 1746 if (i == ms->n - 3) |
| 1660 ms->pending[i+1] = ms->pending[i+2]; | 1747 ms->pending[i+1] = ms->pending[i+2]; |
| 1661 --ms->n; | 1748 --ms->n; |
| 1662 | 1749 |
| 1663 /* Where does b start in a? Elements in a before that can be | 1750 /* Where does b start in a? Elements in a before that can be |
| 1664 * ignored (already in place). | 1751 * ignored (already in place). |
| 1665 */ | 1752 */ |
| 1666 k = gallop_right(*pb, pa, na, 0); | 1753 k = gallop_right(*ssb.keys, ssa.keys, na, 0); |
| 1667 if (k < 0) | 1754 if (k < 0) |
| 1668 return -1; | 1755 return -1; |
| 1669 pa += k; | 1756 sortslice_advance(&ssa, k); |
| 1670 na -= k; | 1757 na -= k; |
| 1671 if (na == 0) | 1758 if (na == 0) |
| 1672 return 0; | 1759 return 0; |
| 1673 | 1760 |
| 1674 /* Where does a end in b? Elements in b after that can be | 1761 /* Where does a end in b? Elements in b after that can be |
| 1675 * ignored (already in place). | 1762 * ignored (already in place). |
| 1676 */ | 1763 */ |
| 1677 nb = gallop_left(pa[na-1], pb, nb, nb-1); | 1764 nb = gallop_left(ssa.keys[na-1], ssb.keys, nb, nb-1); |
| 1678 if (nb <= 0) | 1765 if (nb <= 0) |
| 1679 return nb; | 1766 return nb; |
| 1680 | 1767 |
| 1681 /* Merge what remains of the runs, using a temp array with | 1768 /* Merge what remains of the runs, using a temp array with |
| 1682 * min(na, nb) elements. | 1769 * min(na, nb) elements. |
| 1683 */ | 1770 */ |
| 1684 if (na <= nb) | 1771 if (na <= nb) |
| 1685 return merge_lo(ms, pa, na, pb, nb); | 1772 return merge_lo(ms, ssa, na, ssb, nb); |
| 1686 else | 1773 else |
| 1687 return merge_hi(ms, pa, na, pb, nb); | 1774 return merge_hi(ms, ssa, na, ssb, nb); |
| 1688 } | 1775 } |
| 1689 | 1776 |
| 1690 /* Examine the stack of runs waiting to be merged, merging adjacent runs | 1777 /* Examine the stack of runs waiting to be merged, merging adjacent runs |
| 1691 * until the stack invariants are re-established: | 1778 * until the stack invariants are re-established: |
| 1692 * | 1779 * |
| 1693 * 1. len[-3] > len[-2] + len[-1] | 1780 * 1. len[-3] > len[-2] + len[-1] |
| 1694 * 2. len[-2] > len[-1] | 1781 * 2. len[-2] > len[-1] |
| 1695 * | 1782 * |
| 1696 * See listsort.txt for more info. | 1783 * See listsort.txt for more info. |
| 1697 * | 1784 * |
| (...skipping 60 matching lines...) | | Loading... | |
| 1758 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */ | 1845 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */ |
| 1759 | 1846 |
| 1760 assert(n >= 0); | 1847 assert(n >= 0); |
| 1761 while (n >= 64) { | 1848 while (n >= 64) { |
| 1762 r |= n & 1; | 1849 r |= n & 1; |
| 1763 n >>= 1; | 1850 n >>= 1; |
| 1764 } | 1851 } |
| 1765 return n + r; | 1852 return n + r; |
| 1766 } | 1853 } |
| 1767 | 1854 |
| 1768 /* Special wrapper to support stable sorting using the decorate-sort-undecorate | |
| 1769 pattern. Holds a key which is used for comparisons and the original record | |
| 1770 which is returned during the undecorate phase. By exposing only the key | |
| 1771 during comparisons, the underlying sort stability characteristics are left | |
| 1772 unchanged. Also, the comparison function will only see the key instead of | |
| 1773 a full record. */ | |
| 1774 | |
| 1775 typedef struct { | |
| 1776 PyObject_HEAD | |
| 1777 PyObject *key; | |
| 1778 PyObject *value; | |
| 1779 } sortwrapperobject; | |
| 1780 | |
| 1781 PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key."); | |
| 1782 static PyObject * | |
| 1783 sortwrapper_richcompare(sortwrapperobject *, sortwrapperobject *, int); | |
| 1784 static void | 1855 static void |
| 1785 sortwrapper_dealloc(sortwrapperobject *); | 1856 reverse_sortslice(sortslice *s, Py_ssize_t n) |
| 1786 | |
| 1787 PyTypeObject PySortWrapper_Type = { | |
| 1788 PyVarObject_HEAD_INIT(&PyType_Type, 0) | |
| 1789 "sortwrapper", /* tp_name */ | |
| 1790 sizeof(sortwrapperobject), /* tp_basicsize */ | |
| 1791 0, /* tp_itemsize */ | |
| 1792 /* methods */ | |
| 1793 (destructor)sortwrapper_dealloc, /* tp_dealloc */ | |
| 1794 0, /* tp_print */ | |
| 1795 0, /* tp_getattr */ | |
| 1796 0, /* tp_setattr */ | |
| 1797 0, /* tp_reserved */ | |
| 1798 0, /* tp_repr */ | |
| 1799 0, /* tp_as_number */ | |
| 1800 0, /* tp_as_sequence */ | |
| 1801 0, /* tp_as_mapping */ | |
| 1802 0, /* tp_hash */ | |
| 1803 0, /* tp_call */ | |
| 1804 0, /* tp_str */ | |
| 1805 PyObject_GenericGetAttr, /* tp_getattro */ | |
| 1806 0, /* tp_setattro */ | |
| 1807 0, /* tp_as_buffer */ | |
| 1808 Py_TPFLAGS_DEFAULT, /* tp_flags */ | |
| 1809 sortwrapper_doc, /* tp_doc */ | |
| 1810 0, /* tp_traverse */ | |
| 1811 0, /* tp_clear */ | |
| 1812 (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */ | |
| 1813 }; | |
| 1814 | |
| 1815 | |
| 1816 static PyObject * | |
| 1817 sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op) | |
| 1818 { | 1857 { |
| 1819 if (!PyObject_TypeCheck(b, &PySortWrapper_Type)) { | 1858 reverse_slice(s->keys, &s->keys[n]); |
| 1820 PyErr_SetString(PyExc_TypeError, | 1859 if (s->values != NULL) |
| 1821 "expected a sortwrapperobject"); | 1860 reverse_slice(s->values, &s->values[n]); |
| 1822 return NULL; | |
| 1823 } | |
| 1824 return PyObject_RichCompare(a->key, b->key, op); | |
| 1825 } | |
| 1826 | |
| 1827 static void | |
| 1828 sortwrapper_dealloc(sortwrapperobject *so) | |
| 1829 { | |
| 1830 Py_XDECREF(so->key); | |
| 1831 Py_XDECREF(so->value); | |
| 1832 PyObject_Del(so); | |
| 1833 } | |
| 1834 | |
| 1835 /* Returns a new reference to a sortwrapper. | |
| 1836 Consumes the references to the two underlying objects. */ | |
| 1837 | |
| 1838 static PyObject * | |
| 1839 build_sortwrapper(PyObject *key, PyObject *value) | |
| 1840 { | |
| 1841 sortwrapperobject *so; | |
| 1842 | |
| 1843 so = PyObject_New(sortwrapperobject, &PySortWrapper_Type); | |
| 1844 if (so == NULL) | |
| 1845 return NULL; | |
| 1846 so->key = key; | |
| 1847 so->value = value; | |
| 1848 return (PyObject *)so; | |
| 1849 } | |
| 1850 | |
| 1851 /* Returns a new reference to the value underlying the wrapper. */ | |
| 1852 static PyObject * | |
| 1853 sortwrapper_getvalue(PyObject *so) | |
| 1854 { | |
| 1855 PyObject *value; | |
| 1856 | |
| 1857 if (!PyObject_TypeCheck(so, &PySortWrapper_Type)) { | |
| 1858 PyErr_SetString(PyExc_TypeError, | |
| 1859 "expected a sortwrapperobject"); | |
| 1860 return NULL; | |
| 1861 } | |
| 1862 value = ((sortwrapperobject *)so)->value; | |
| 1863 Py_INCREF(value); | |
| 1864 return value; | |
| 1865 } | 1861 } |
| 1866 | 1862 |
| 1867 /* An adaptive, stable, natural mergesort. See listsort.txt. | 1863 /* An adaptive, stable, natural mergesort. See listsort.txt. |
| 1868 * Returns Py_None on success, NULL on error. Even in case of error, the | 1864 * Returns Py_None on success, NULL on error. Even in case of error, the |
| 1869 * list will be some permutation of its input state (nothing is lost or | 1865 * list will be some permutation of its input state (nothing is lost or |
| 1870 * duplicated). | 1866 * duplicated). |
| 1871 */ | 1867 */ |
| 1872 static PyObject * | 1868 static PyObject * |
| 1873 listsort(PyListObject *self, PyObject *args, PyObject *kwds) | 1869 listsort(PyListObject *self, PyObject *args, PyObject *kwds) |
| 1874 { | 1870 { |
| 1875 MergeState ms; | 1871 MergeState ms; |
| 1876 PyObject **lo, **hi; | |
| 1877 Py_ssize_t nremaining; | 1872 Py_ssize_t nremaining; |
| 1878 Py_ssize_t minrun; | 1873 Py_ssize_t minrun; |
| 1874 sortslice lo; | |
| 1879 Py_ssize_t saved_ob_size, saved_allocated; | 1875 Py_ssize_t saved_ob_size, saved_allocated; |
| 1880 PyObject **saved_ob_item; | 1876 PyObject **saved_ob_item; |
| 1881 PyObject **final_ob_item; | 1877 PyObject **final_ob_item; |
| 1882 PyObject *result = NULL; /* guilty until proved innocent */ | 1878 PyObject *result = NULL; /* guilty until proved innocent */ |
| 1883 int reverse = 0; | 1879 int reverse = 0; |
| 1884 PyObject *keyfunc = NULL; | 1880 PyObject *keyfunc = NULL; |
| 1885 Py_ssize_t i; | 1881 Py_ssize_t i; |
| 1886 PyObject *key, *value, *kvpair; | |
| 1887 static char *kwlist[] = {"key", "reverse", 0}; | 1882 static char *kwlist[] = {"key", "reverse", 0}; |
| 1883 PyObject **keys; | |
| 1888 | 1884 |
| 1889 assert(self != NULL); | 1885 assert(self != NULL); |
| 1890 assert (PyList_Check(self)); | 1886 assert (PyList_Check(self)); |
| 1891 if (args != NULL) { | 1887 if (args != NULL) { |
| 1892 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort", | 1888 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort", |
| 1893 kwlist, &keyfunc, &reverse)) | 1889 kwlist, &keyfunc, &reverse)) |
| 1894 return NULL; | 1890 return NULL; |
| 1895 if (Py_SIZE(args) > 0) { | 1891 if (Py_SIZE(args) > 0) { |
| 1896 PyErr_SetString(PyExc_TypeError, | 1892 PyErr_SetString(PyExc_TypeError, |
| 1897 "must use keyword argument for key function"); | 1893 "must use keyword argument for key function"); |
| 1898 return NULL; | 1894 return NULL; |
| 1899 } | 1895 } |
| 1900 } | 1896 } |
| 1901 if (keyfunc == Py_None) | 1897 if (keyfunc == Py_None) |
| 1902 keyfunc = NULL; | 1898 keyfunc = NULL; |
| 1903 | 1899 |
| 1904 /* The list is temporarily made empty, so that mutations performed | 1900 /* The list is temporarily made empty, so that mutations performed |
| 1905 * by comparison functions can't affect the slice of memory we're | 1901 * by comparison functions can't affect the slice of memory we're |
| 1906 * sorting (allowing mutations during sorting is a core-dump | 1902 * sorting (allowing mutations during sorting is a core-dump |
| 1907 * factory, since ob_item may change). | 1903 * factory, since ob_item may change). |
| 1908 */ | 1904 */ |
| 1909 saved_ob_size = Py_SIZE(self); | 1905 saved_ob_size = Py_SIZE(self); |
| 1910 saved_ob_item = self->ob_item; | 1906 saved_ob_item = self->ob_item; |
| 1911 saved_allocated = self->allocated; | 1907 saved_allocated = self->allocated; |
| 1912 Py_SIZE(self) = 0; | 1908 Py_SIZE(self) = 0; |
| 1913 self->ob_item = NULL; | 1909 self->ob_item = NULL; |
| 1914 self->allocated = -1; /* any operation will reset it to >= 0 */ | 1910 self->allocated = -1; /* any operation will reset it to >= 0 */ |
| 1915 | 1911 |
| 1916 if (keyfunc != NULL) { | 1912 if (keyfunc == NULL) { |
| 1917 for (i=0 ; i < saved_ob_size ; i++) { | 1913 keys = NULL; |
| 1918 value = saved_ob_item[i]; | 1914 lo.keys = saved_ob_item; |
| 1919 key = PyObject_CallFunctionObjArgs(keyfunc, value, | 1915 lo.values = NULL; |
| 1920 NULL); | 1916 } |
| 1921 if (key == NULL) { | 1917 else { |
| 1922 for (i=i-1 ; i>=0 ; i--) { | 1918 if (saved_ob_size < MERGESTATE_TEMP_SIZE/2) |
| 1923 kvpair = saved_ob_item[i]; | 1919 /* Leverage stack space we allocated but won't otherwise use */ |
| 1924 value = sortwrapper_getvalue(kvpair); | 1920 keys = &ms.temparray[saved_ob_size+1]; |
| 1925 saved_ob_item[i] = value; | 1921 else { |
| 1926 Py_DECREF(kvpair); | 1922 keys = PyMem_MALLOC(sizeof(PyObject *) * saved_ob_size); |
| 1927 } | 1923 if (keys == NULL) |
| 1924 return NULL; | |
| 1925 } | |
| 1926 | |
| 1927 for (i = 0; i < saved_ob_size ; i++) { | |
| 1928 keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i], | |
| 1929 NULL); | |
| 1930 if (keys[i] == NULL) { | |
| 1931 for (i=i-1 ; i>=0 ; i--) | |
| 1932 Py_DECREF(keys[i]); | |
| 1928 goto dsu_fail; | 1933 goto dsu_fail; |
|
Antoine Pitrou
2010年12月01日 21:20:24
Since there's no decorate-sort-undecorate anymore,
Since there's no decorate-sort-undecorate anymore, perhaps rename dsu_fail to
something else?
stutzbach
2010年12月01日 22:08:26
How about keyfunc_fail?
On 2010年12月01日 21:20:24, Antoine Pitrou wrote:
> Since there's no decorate-sort-undecorate anymore, perhaps rename dsu_fail to
> something else?
How about keyfunc_fail?
| |
| 1929 } | 1934 } |
| 1930 kvpair = build_sortwrapper(key, value); | |
| 1931 if (kvpair == NULL) | |
| 1932 goto dsu_fail; | |
| 1933 saved_ob_item[i] = kvpair; | |
| 1934 } | 1935 } |
| 1936 | |
| 1937 lo.keys = keys; | |
| 1938 lo.values = saved_ob_item; | |
| 1935 } | 1939 } |
| 1936 | 1940 |
| 1937 merge_init(&ms); | 1941 merge_init(&ms, saved_ob_size, keys != NULL); |
| 1938 | 1942 |
| 1939 nremaining = saved_ob_size; | 1943 nremaining = saved_ob_size; |
| 1940 if (nremaining < 2) | 1944 if (nremaining < 2) |
| 1941 goto succeed; | 1945 goto succeed; |
| 1942 | 1946 |
| 1943 /* Reverse sort stability achieved by initially reversing the list, | 1947 /* Reverse sort stability achieved by initially reversing the list, |
| 1944 applying a stable forward sort, then reversing the final result. */ | 1948 applying a stable forward sort, then reversing the final result. */ |
| 1945 if (reverse) | 1949 if (reverse) { |
| 1946 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); | 1950 if (keys != NULL) |
| 1951 reverse_slice(&keys[0], &keys[saved_ob_size]); | |
| 1952 reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]); | |
| 1953 } | |
| 1947 | 1954 |
| 1948 /* March over the array once, left to right, finding natural runs, | 1955 /* March over the array once, left to right, finding natural runs, |
| 1949 * and extending short natural runs to minrun elements. | 1956 * and extending short natural runs to minrun elements. |
| 1950 */ | 1957 */ |
| 1951 lo = saved_ob_item; | |
| 1952 hi = lo + nremaining; | |
| 1953 minrun = merge_compute_minrun(nremaining); | 1958 minrun = merge_compute_minrun(nremaining); |
| 1954 do { | 1959 do { |
| 1955 int descending; | 1960 int descending; |
| 1956 Py_ssize_t n; | 1961 Py_ssize_t n; |
| 1957 | 1962 |
| 1958 /* Identify next run. */ | 1963 /* Identify next run. */ |
| 1959 n = count_run(lo, hi, &descending); | 1964 n = count_run(lo.keys, lo.keys + nremaining, &descending); |
| 1960 if (n < 0) | 1965 if (n < 0) |
| 1961 goto fail; | 1966 goto fail; |
| 1962 if (descending) | 1967 if (descending) |
| 1963 reverse_slice(lo, lo + n); | 1968 reverse_sortslice(&lo, n); |
| 1964 /* If short, extend to min(minrun, nremaining). */ | 1969 /* If short, extend to min(minrun, nremaining). */ |
| 1965 if (n < minrun) { | 1970 if (n < minrun) { |
| 1966 const Py_ssize_t force = nremaining <= minrun ? | 1971 const Py_ssize_t force = nremaining <= minrun ? |
| 1967 nremaining : minrun; | 1972 nremaining : minrun; |
| 1968 if (binarysort(lo, lo + force, lo + n) < 0) | 1973 if (binarysort(lo, lo.keys + force, lo.keys + n) < 0) |
| 1969 goto fail; | 1974 goto fail; |
| 1970 n = force; | 1975 n = force; |
| 1971 } | 1976 } |
| 1972 /* Push run onto pending-runs stack, and maybe merge. */ | 1977 /* Push run onto pending-runs stack, and maybe merge. */ |
| 1973 assert(ms.n < MAX_MERGE_PENDING); | 1978 assert(ms.n < MAX_MERGE_PENDING); |
| 1974 ms.pending[ms.n].base = lo; | 1979 ms.pending[ms.n].base = lo; |
| 1975 ms.pending[ms.n].len = n; | 1980 ms.pending[ms.n].len = n; |
| 1976 ++ms.n; | 1981 ++ms.n; |
| 1977 if (merge_collapse(&ms) < 0) | 1982 if (merge_collapse(&ms) < 0) |
| 1978 goto fail; | 1983 goto fail; |
| 1979 /* Advance to find next run. */ | 1984 /* Advance to find next run. */ |
| 1980 lo += n; | 1985 sortslice_advance(&lo, n); |
| 1981 nremaining -= n; | 1986 nremaining -= n; |
| 1982 } while (nremaining); | 1987 } while (nremaining); |
| 1983 assert(lo == hi); | |
| 1984 | 1988 |
| 1985 if (merge_force_collapse(&ms) < 0) | 1989 if (merge_force_collapse(&ms) < 0) |
| 1986 goto fail; | 1990 goto fail; |
| 1987 assert(ms.n == 1); | 1991 assert(ms.n == 1); |
| 1988 assert(ms.pending[0].base == saved_ob_item); | 1992 assert(keys == NULL |
| 1993 ? ms.pending[0].base.keys == saved_ob_item | |
| 1994 : ms.pending[0].base.keys == &keys[0]); | |
| 1989 assert(ms.pending[0].len == saved_ob_size); | 1995 assert(ms.pending[0].len == saved_ob_size); |
| 1996 lo = ms.pending[0].base; | |
| 1990 | 1997 |
| 1991 succeed: | 1998 succeed: |
| 1992 result = Py_None; | 1999 result = Py_None; |
| 1993 fail: | 2000 fail: |
| 1994 if (keyfunc != NULL) { | 2001 if (keys != NULL) { |
| 1995 for (i=0 ; i < saved_ob_size ; i++) { | 2002 for (i = 0; i < saved_ob_size; i++) |
| 1996 kvpair = saved_ob_item[i]; | 2003 Py_DECREF(keys[i]); |
| 1997 value = sortwrapper_getvalue(kvpair); | 2004 if (keys != &ms.temparray[saved_ob_size+1]) |
| 1998 saved_ob_item[i] = value; | 2005 PyMem_FREE(keys); |
| 1999 Py_DECREF(kvpair); | |
| 2000 } | |
| 2001 } | 2006 } |
| 2002 | 2007 |
| 2003 if (self->allocated != -1 && result != NULL) { | 2008 if (self->allocated != -1 && result != NULL) { |
| 2004 /* The user mucked with the list during the sort, | 2009 /* The user mucked with the list during the sort, |
| 2005 * and we don't already have another error to report. | 2010 * and we don't already have another error to report. |
| 2006 */ | 2011 */ |
| 2007 PyErr_SetString(PyExc_ValueError, "list modified during sort"); | 2012 PyErr_SetString(PyExc_ValueError, "list modified during sort"); |
| 2008 result = NULL; | 2013 result = NULL; |
| 2009 } | 2014 } |
| 2010 | 2015 |
| (...skipping 844 matching lines...) | | Loading... | |
| 2855 } | 2860 } |
| 2856 | 2861 |
| 2857 static PyObject * | 2862 static PyObject * |
| 2858 listreviter_len(listreviterobject *it) | 2863 listreviter_len(listreviterobject *it) |
| 2859 { | 2864 { |
| 2860 Py_ssize_t len = it->it_index + 1; | 2865 Py_ssize_t len = it->it_index + 1; |
| 2861 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len) | 2866 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len) |
| 2862 len = 0; | 2867 len = 0; |
| 2863 return PyLong_FromSsize_t(len); | 2868 return PyLong_FromSsize_t(len); |
| 2864 } | 2869 } |
| 2865 | |
| OLD | NEW |