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...) Expand 10 before | Expand all | Expand 10 after 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; |
| 1033 PyObject *pivot_value; |
973 | 1034 |
974 assert(lo <= start && start <= hi); | 1035 assert(lo.keys <= start && start <= hi); |
975 /* assert [lo, start) is sorted */ | 1036 /* assert [lo, start) is sorted */ |
976 if (lo == start) | 1037 if (lo.keys == start) |
977 ++start; | 1038 ++start; |
978 for (; start < hi; ++start) { | 1039 for (; start < hi; ++start) { |
979 /* set l to where *start belongs */ | 1040 /* set l to where *start belongs */ |
980 l = lo; | 1041 l = lo.keys; |
981 r = start; | 1042 r = start; |
982 pivot = *r; | 1043 pivot = *r; |
| 1044 if (lo.values != NULL) |
| 1045 pivot_value = lo.values[r-lo.keys]; |
983 /* Invariants: | 1046 /* Invariants: |
984 * pivot >= all in [lo, l). | 1047 * pivot >= all in [lo, l). |
985 * pivot < all in [r, start). | 1048 * pivot < all in [r, start). |
986 * The second is vacuously true at the start. | 1049 * The second is vacuously true at the start. |
987 */ | 1050 */ |
988 assert(l < r); | 1051 assert(l < r); |
989 do { | 1052 do { |
990 p = l + ((r - l) >> 1); | 1053 p = l + ((r - l) >> 1); |
991 IFLT(pivot, *p) | 1054 IFLT(pivot, *p) |
992 r = p; | 1055 r = p; |
993 else | 1056 else |
994 l = p+1; | 1057 l = p+1; |
995 } while (l < r); | 1058 } while (l < r); |
996 assert(l == r); | 1059 assert(l == r); |
997 /* The invariants still hold, so pivot >= all in [lo, l) and | 1060 /* The invariants still hold, so pivot >= all in [lo, l) and |
998 pivot < all in [l, start), so pivot belongs at l. Note | 1061 pivot < all in [l, start), so pivot belongs at l. Note |
999 that if there are elements equal to pivot, l points to the | 1062 that if there are elements equal to pivot, l points to the |
1000 first slot after them -- that's why this sort is stable. | 1063 first slot after them -- that's why this sort is stable. |
1001 Slide over to make room. | 1064 Slide over to make room. |
1002 Caution: using memmove is much slower under MSVC 5; | 1065 Caution: using memmove is much slower under MSVC 5; |
1003 we're not usually moving many slots. */ | 1066 we're not usually moving many slots. */ |
1004 for (p = start; p > l; --p) | 1067 for (p = start; p > l; --p) |
1005 *p = *(p-1); | 1068 *p = *(p-1); |
1006 *l = pivot; | 1069 *l = pivot; |
| 1070 if (lo.values != NULL) { |
| 1071 l = lo.values + (l - lo.keys); |
| 1072 for (p = lo.values + (start - lo.keys); p > l; --p) |
| 1073 *p = *(p-1); |
| 1074 *l = pivot_value; |
| 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 247 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1264 * often than MIN_GALLOP consecutive times. See listsort.txt for more info. | 1333 * often than MIN_GALLOP consecutive times. See listsort.txt for more info. |
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 */ |
| 1343 |
1274 struct s_slice { | 1344 struct s_slice { |
1275 PyObject **base; | 1345 sortslice base; |
1276 Py_ssize_t len; | 1346 Py_ssize_t len; |
1277 }; | 1347 }; |
1278 | 1348 |
1279 typedef struct s_MergeState { | 1349 typedef struct s_MergeState { |
1280 /* This controls when we get *into* galloping mode. It's initialized | 1350 /* 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 | 1351 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for |
1282 * random data, and lower for highly structured data. | 1352 * random data, and lower for highly structured data. |
1283 */ | 1353 */ |
1284 Py_ssize_t min_gallop; | 1354 Py_ssize_t min_gallop; |
1285 | 1355 |
1286 /* 'a' is temp storage to help with merges. It contains room for | 1356 /* 'a' is temp storage to help with merges. It contains room for |
1287 * alloced entries. | 1357 * alloced entries. |
1288 */ | 1358 */ |
1289 PyObject **a; /* may point to temparray below */ | 1359 sortslice a; /* may point to temparray below */ |
1290 Py_ssize_t alloced; | 1360 Py_ssize_t alloced; |
1291 | 1361 |
1292 /* A stack of n pending runs yet to be merged. Run #i starts at | 1362 /* 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 | 1363 * address base[i] and extends for len[i] elements. It's always |
1294 * true (so long as the indices are in bounds) that | 1364 * true (so long as the indices are in bounds) that |
1295 * | 1365 * |
1296 * pending[i].base + pending[i].len == pending[i+1].base | 1366 * pending[i].base + pending[i].len == pending[i+1].base |
1297 * | 1367 * |
1298 * so we could cut the storage for this, but it's a minor amount, | 1368 * so we could cut the storage for this, but it's a minor amount, |
1299 * and keeping all the info explicit simplifies the code. | 1369 * and keeping all the info explicit simplifies the code. |
1300 */ | 1370 */ |
1301 int n; | 1371 int n; |
1302 struct s_slice pending[MAX_MERGE_PENDING]; | 1372 struct s_slice pending[MAX_MERGE_PENDING]; |
1303 | 1373 |
1304 /* 'a' points to this when possible, rather than muck with malloc. */ | 1374 /* 'a' points to this when possible, rather than muck with malloc. */ |
1305 PyObject *temparray[MERGESTATE_TEMP_SIZE]; | 1375 PyObject *temparray[MERGESTATE_TEMP_SIZE]; |
1306 } MergeState; | 1376 } MergeState; |
1307 | 1377 |
1308 /* Conceptually a MergeState's constructor. */ | 1378 /* Conceptually a MergeState's constructor. */ |
1309 static void | 1379 static void |
1310 merge_init(MergeState *ms) | 1380 merge_init(MergeState *ms, int has_keyfunc) |
1311 { | 1381 { |
1312 assert(ms != NULL); | 1382 assert(ms != NULL); |
1313 ms->a = ms->temparray; | 1383 ms->a.keys = ms->temparray; |
1314 ms->alloced = MERGESTATE_TEMP_SIZE; | 1384 if (has_keyfunc) { |
| 1385 ms->a.values = &ms->temparray[MERGESTATE_TEMP_SIZE/2]; |
| 1386 ms->alloced = MERGESTATE_TEMP_SIZE/2; |
| 1387 } else { |
| 1388 ms->a.values = NULL; |
| 1389 ms->alloced = MERGESTATE_TEMP_SIZE; |
| 1390 } |
1315 ms->n = 0; | 1391 ms->n = 0; |
1316 ms->min_gallop = MIN_GALLOP; | 1392 ms->min_gallop = MIN_GALLOP; |
1317 } | 1393 } |
1318 | 1394 |
1319 /* Free all the temp memory owned by the MergeState. This must be called | 1395 /* 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 | 1396 * when you're done with a MergeState, and may be called before then if |
1321 * you want to free the temp memory early. | 1397 * you want to free the temp memory early. |
1322 */ | 1398 */ |
1323 static void | 1399 static void |
1324 merge_freemem(MergeState *ms) | 1400 merge_freemem(MergeState *ms) |
1325 { | 1401 { |
1326 assert(ms != NULL); | 1402 assert(ms != NULL); |
1327 if (ms->a != ms->temparray) | 1403 if (ms->a.keys != ms->temparray) |
1328 PyMem_Free(ms->a); | 1404 PyMem_Free(ms->a.keys); |
1329 ms->a = ms->temparray; | 1405 ms->a.keys = ms->temparray; |
1330 ms->alloced = MERGESTATE_TEMP_SIZE; | 1406 if (ms->a.values != NULL) { |
| 1407 ms->a.values = &ms->temparray[MERGESTATE_TEMP_SIZE/2]; |
| 1408 ms->alloced = MERGESTATE_TEMP_SIZE/2; |
| 1409 } else |
| 1410 ms->alloced = MERGESTATE_TEMP_SIZE; |
1331 } | 1411 } |
1332 | 1412 |
1333 /* Ensure enough temp memory for 'need' array slots is available. | 1413 /* Ensure enough temp memory for 'need' array slots is available. |
1334 * Returns 0 on success and -1 if the memory can't be gotten. | 1414 * Returns 0 on success and -1 if the memory can't be gotten. |
1335 */ | 1415 */ |
1336 static int | 1416 static int |
1337 merge_getmem(MergeState *ms, Py_ssize_t need) | 1417 merge_getmem(MergeState *ms, Py_ssize_t need) |
1338 { | 1418 { |
| 1419 int multiplier; |
| 1420 |
1339 assert(ms != NULL); | 1421 assert(ms != NULL); |
1340 if (need <= ms->alloced) | 1422 if (need <= ms->alloced) |
1341 return 0; | 1423 return 0; |
| 1424 |
| 1425 multiplier = ms->a.values != NULL ? 2 : 1; |
| 1426 |
1342 /* Don't realloc! That can cost cycles to copy the old data, but | 1427 /* Don't realloc! That can cost cycles to copy the old data, but |
1343 * we don't care what's in the block. | 1428 * we don't care what's in the block. |
1344 */ | 1429 */ |
1345 merge_freemem(ms); | 1430 merge_freemem(ms); |
1346 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) { | 1431 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*) / multiplier) { |
1347 PyErr_NoMemory(); | 1432 PyErr_NoMemory(); |
1348 return -1; | 1433 return -1; |
1349 } | 1434 } |
1350 ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*)); | 1435 ms->a.keys = (PyObject**)PyMem_Malloc(multiplier * need |
1351 if (ms->a) { | 1436 * sizeof(PyObject *)); |
| 1437 if (ms->a.keys != NULL) { |
1352 ms->alloced = need; | 1438 ms->alloced = need; |
| 1439 if (ms->a.values != NULL) |
| 1440 ms->a.values = &ms->a.keys[need]; |
| 1441 else |
| 1442 ms->a.values = NULL; |
1353 return 0; | 1443 return 0; |
1354 } | 1444 } |
1355 PyErr_NoMemory(); | 1445 PyErr_NoMemory(); |
1356 merge_freemem(ms); /* reset to sane state */ | 1446 merge_freemem(ms); /* reset to sane state */ |
1357 return -1; | 1447 return -1; |
1358 } | 1448 } |
1359 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ | 1449 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ |
1360 merge_getmem(MS, NEED)) | 1450 merge_getmem(MS, NEED)) |
1361 | 1451 |
1362 /* Merge the na elements starting at pa with the nb elements starting at pb | 1452 /* Merge the na elements starting at pa with the nb elements starting at pb |
1363 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | 1453 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. |
1364 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | 1454 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the |
1365 * merge, and should have na <= nb. See listsort.txt for more info. | 1455 * merge, and should have na <= nb. See listsort.txt for more info. |
1366 * Return 0 if successful, -1 if error. | 1456 * Return 0 if successful, -1 if error. |
1367 */ | 1457 */ |
1368 static Py_ssize_t | 1458 static Py_ssize_t |
1369 merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na, | 1459 merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na, |
1370 PyObject **pb, Py_ssize_t nb) | 1460 sortslice ssb, Py_ssize_t nb) |
1371 { | 1461 { |
1372 Py_ssize_t k; | 1462 Py_ssize_t k; |
1373 PyObject **dest; | 1463 sortslice dest; |
1374 int result = -1; /* guilty until proved innocent */ | 1464 int result = -1; /* guilty until proved innocent */ |
1375 Py_ssize_t min_gallop; | 1465 Py_ssize_t min_gallop; |
1376 | 1466 |
1377 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); | 1467 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0); |
| 1468 assert(ssa.keys + na == ssb.keys); |
1378 if (MERGE_GETMEM(ms, na) < 0) | 1469 if (MERGE_GETMEM(ms, na) < 0) |
1379 return -1; | 1470 return -1; |
1380 memcpy(ms->a, pa, na * sizeof(PyObject*)); | 1471 sortslice_memcpy(&ms->a, 0, &ssa, 0, na); |
1381 dest = pa; | 1472 dest = ssa; |
1382 pa = ms->a; | 1473 ssa = ms->a; |
1383 | 1474 |
1384 *dest++ = *pb++; | 1475 sortslice_copy_incr(&dest, &ssb); |
1385 --nb; | 1476 --nb; |
1386 if (nb == 0) | 1477 if (nb == 0) |
1387 goto Succeed; | 1478 goto Succeed; |
1388 if (na == 1) | 1479 if (na == 1) |
1389 goto CopyB; | 1480 goto CopyB; |
1390 | 1481 |
1391 min_gallop = ms->min_gallop; | 1482 min_gallop = ms->min_gallop; |
1392 for (;;) { | 1483 for (;;) { |
1393 Py_ssize_t acount = 0; /* # of times A won in a row */ | 1484 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 */ | 1485 Py_ssize_t bcount = 0; /* # of times B won in a row */ |
1395 | 1486 |
1396 /* Do the straightforward thing until (if ever) one run | 1487 /* Do the straightforward thing until (if ever) one run |
1397 * appears to win consistently. | 1488 * appears to win consistently. |
1398 */ | 1489 */ |
1399 for (;;) { | 1490 for (;;) { |
1400 assert(na > 1 && nb > 0); | 1491 assert(na > 1 && nb > 0); |
1401 k = ISLT(*pb, *pa); | 1492 k = ISLT(ssb.keys[0], ssa.keys[0]); |
1402 if (k) { | 1493 if (k) { |
1403 if (k < 0) | 1494 if (k < 0) |
1404 goto Fail; | 1495 goto Fail; |
1405 *dest++ = *pb++; | 1496 sortslice_copy_incr(&dest, &ssb); |
1406 ++bcount; | 1497 ++bcount; |
1407 acount = 0; | 1498 acount = 0; |
1408 --nb; | 1499 --nb; |
1409 if (nb == 0) | 1500 if (nb == 0) |
1410 goto Succeed; | 1501 goto Succeed; |
1411 if (bcount >= min_gallop) | 1502 if (bcount >= min_gallop) |
1412 break; | 1503 break; |
1413 } | 1504 } |
1414 else { | 1505 else { |
1415 *dest++ = *pa++; | 1506 sortslice_copy_incr(&dest, &ssa); |
1416 ++acount; | 1507 ++acount; |
1417 bcount = 0; | 1508 bcount = 0; |
1418 --na; | 1509 --na; |
1419 if (na == 1) | 1510 if (na == 1) |
1420 goto CopyB; | 1511 goto CopyB; |
1421 if (acount >= min_gallop) | 1512 if (acount >= min_gallop) |
1422 break; | 1513 break; |
1423 } | 1514 } |
1424 } | 1515 } |
1425 | 1516 |
1426 /* One run is winning so consistently that galloping may | 1517 /* One run is winning so consistently that galloping may |
1427 * be a huge win. So try that, and continue galloping until | 1518 * be a huge win. So try that, and continue galloping until |
1428 * (if ever) neither run appears to be winning consistently | 1519 * (if ever) neither run appears to be winning consistently |
1429 * anymore. | 1520 * anymore. |
1430 */ | 1521 */ |
1431 ++min_gallop; | 1522 ++min_gallop; |
1432 do { | 1523 do { |
1433 assert(na > 1 && nb > 0); | 1524 assert(na > 1 && nb > 0); |
1434 min_gallop -= min_gallop > 1; | 1525 min_gallop -= min_gallop > 1; |
1435 ms->min_gallop = min_gallop; | 1526 ms->min_gallop = min_gallop; |
1436 k = gallop_right(*pb, pa, na, 0); | 1527 k = gallop_right(ssb.keys[0], ssa.keys, na, 0); |
1437 acount = k; | 1528 acount = k; |
1438 if (k) { | 1529 if (k) { |
1439 if (k < 0) | 1530 if (k < 0) |
1440 goto Fail; | 1531 goto Fail; |
1441 memcpy(dest, pa, k * sizeof(PyObject *)); | 1532 sortslice_memcpy(&dest, 0, &ssa, 0, k); |
1442 dest += k; | 1533 sortslice_advance(&dest, k); |
1443 pa += k; | 1534 sortslice_advance(&ssa, k); |
1444 na -= k; | 1535 na -= k; |
1445 if (na == 1) | 1536 if (na == 1) |
1446 goto CopyB; | 1537 goto CopyB; |
1447 /* na==0 is impossible now if the comparison | 1538 /* na==0 is impossible now if the comparison |
1448 * function is consistent, but we can't assume | 1539 * function is consistent, but we can't assume |
1449 * that it is. | 1540 * that it is. |
1450 */ | 1541 */ |
1451 if (na == 0) | 1542 if (na == 0) |
1452 goto Succeed; | 1543 goto Succeed; |
1453 } | 1544 } |
1454 *dest++ = *pb++; | 1545 sortslice_copy_incr(&dest, &ssb); |
1455 --nb; | 1546 --nb; |
1456 if (nb == 0) | 1547 if (nb == 0) |
1457 goto Succeed; | 1548 goto Succeed; |
1458 | 1549 |
1459 k = gallop_left(*pa, pb, nb, 0); | 1550 k = gallop_left(ssa.keys[0], ssb.keys, nb, 0); |
1460 bcount = k; | 1551 bcount = k; |
1461 if (k) { | 1552 if (k) { |
1462 if (k < 0) | 1553 if (k < 0) |
1463 goto Fail; | 1554 goto Fail; |
1464 memmove(dest, pb, k * sizeof(PyObject *)); | 1555 sortslice_memmove(&dest, 0, &ssb, 0, k); |
1465 dest += k; | 1556 sortslice_advance(&dest, k); |
1466 pb += k; | 1557 sortslice_advance(&ssb, k); |
1467 nb -= k; | 1558 nb -= k; |
1468 if (nb == 0) | 1559 if (nb == 0) |
1469 goto Succeed; | 1560 goto Succeed; |
1470 } | 1561 } |
1471 *dest++ = *pa++; | 1562 sortslice_copy_incr(&dest, &ssa); |
1472 --na; | 1563 --na; |
1473 if (na == 1) | 1564 if (na == 1) |
1474 goto CopyB; | 1565 goto CopyB; |
1475 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); | 1566 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
1476 ++min_gallop; /* penalize it for leaving galloping mode */ | 1567 ++min_gallop; /* penalize it for leaving galloping mode */ |
1477 ms->min_gallop = min_gallop; | 1568 ms->min_gallop = min_gallop; |
1478 } | 1569 } |
1479 Succeed: | 1570 Succeed: |
1480 result = 0; | 1571 result = 0; |
1481 Fail: | 1572 Fail: |
1482 if (na) | 1573 if (na) |
1483 memcpy(dest, pa, na * sizeof(PyObject*)); | 1574 sortslice_memcpy(&dest, 0, &ssa, 0, na); |
1484 return result; | 1575 return result; |
1485 CopyB: | 1576 CopyB: |
1486 assert(na == 1 && nb > 0); | 1577 assert(na == 1 && nb > 0); |
1487 /* The last element of pa belongs at the end of the merge. */ | 1578 /* The last element of pa belongs at the end of the merge. */ |
1488 memmove(dest, pb, nb * sizeof(PyObject *)); | 1579 sortslice_memmove(&dest, 0, &ssb, 0, nb); |
1489 dest[nb] = *pa; | 1580 sortslice_copy(&dest, nb, &ssa, 0); |
1490 return 0; | 1581 return 0; |
1491 } | 1582 } |
1492 | 1583 |
1493 /* Merge the na elements starting at pa with the nb elements starting at pb | 1584 /* Merge the na elements starting at pa with the nb elements starting at pb |
1494 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | 1585 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. |
1495 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | 1586 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the |
1496 * merge, and should have na >= nb. See listsort.txt for more info. | 1587 * merge, and should have na >= nb. See listsort.txt for more info. |
1497 * Return 0 if successful, -1 if error. | 1588 * Return 0 if successful, -1 if error. |
1498 */ | 1589 */ |
1499 static Py_ssize_t | 1590 static Py_ssize_t |
1500 merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t
nb) | 1591 merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na, |
| 1592 sortslice ssb, Py_ssize_t nb) |
1501 { | 1593 { |
1502 Py_ssize_t k; | 1594 Py_ssize_t k; |
1503 PyObject **dest; | 1595 sortslice dest; |
1504 int result = -1; /* guilty until proved innocent */ | 1596 int result = -1; /* guilty until proved innocent */ |
1505 PyObject **basea; | 1597 sortslice basea; |
1506 PyObject **baseb; | 1598 sortslice baseb; |
1507 Py_ssize_t min_gallop; | 1599 Py_ssize_t min_gallop; |
1508 | 1600 |
1509 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); | 1601 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0); |
| 1602 assert(ssa.keys + na == ssb.keys); |
1510 if (MERGE_GETMEM(ms, nb) < 0) | 1603 if (MERGE_GETMEM(ms, nb) < 0) |
1511 return -1; | 1604 return -1; |
1512 dest = pb + nb - 1; | 1605 dest = ssb; |
1513 memcpy(ms->a, pb, nb * sizeof(PyObject*)); | 1606 sortslice_advance(&dest, nb-1); |
1514 basea = pa; | 1607 sortslice_memcpy(&ms->a, 0, &ssb, 0, nb); |
| 1608 basea = ssa; |
1515 baseb = ms->a; | 1609 baseb = ms->a; |
1516 pb = ms->a + nb - 1; | 1610 ssb.keys = ms->a.keys + nb - 1; |
1517 pa += na - 1; | 1611 if (ssb.values != NULL) |
| 1612 ssb.values = ms->a.values + nb - 1; |
| 1613 sortslice_advance(&ssa, na - 1); |
1518 | 1614 |
1519 *dest-- = *pa--; | 1615 sortslice_copy_decr(&dest, &ssa); |
1520 --na; | 1616 --na; |
1521 if (na == 0) | 1617 if (na == 0) |
1522 goto Succeed; | 1618 goto Succeed; |
1523 if (nb == 1) | 1619 if (nb == 1) |
1524 goto CopyA; | 1620 goto CopyA; |
1525 | 1621 |
1526 min_gallop = ms->min_gallop; | 1622 min_gallop = ms->min_gallop; |
1527 for (;;) { | 1623 for (;;) { |
1528 Py_ssize_t acount = 0; /* # of times A won in a row */ | 1624 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 */ | 1625 Py_ssize_t bcount = 0; /* # of times B won in a row */ |
1530 | 1626 |
1531 /* Do the straightforward thing until (if ever) one run | 1627 /* Do the straightforward thing until (if ever) one run |
1532 * appears to win consistently. | 1628 * appears to win consistently. |
1533 */ | 1629 */ |
1534 for (;;) { | 1630 for (;;) { |
1535 assert(na > 0 && nb > 1); | 1631 assert(na > 0 && nb > 1); |
1536 k = ISLT(*pb, *pa); | 1632 k = ISLT(ssb.keys[0], ssa.keys[0]); |
1537 if (k) { | 1633 if (k) { |
1538 if (k < 0) | 1634 if (k < 0) |
1539 goto Fail; | 1635 goto Fail; |
1540 *dest-- = *pa--; | 1636 sortslice_copy_decr(&dest, &ssa); |
1541 ++acount; | 1637 ++acount; |
1542 bcount = 0; | 1638 bcount = 0; |
1543 --na; | 1639 --na; |
1544 if (na == 0) | 1640 if (na == 0) |
1545 goto Succeed; | 1641 goto Succeed; |
1546 if (acount >= min_gallop) | 1642 if (acount >= min_gallop) |
1547 break; | 1643 break; |
1548 } | 1644 } |
1549 else { | 1645 else { |
1550 *dest-- = *pb--; | 1646 sortslice_copy_decr(&dest, &ssb); |
1551 ++bcount; | 1647 ++bcount; |
1552 acount = 0; | 1648 acount = 0; |
1553 --nb; | 1649 --nb; |
1554 if (nb == 1) | 1650 if (nb == 1) |
1555 goto CopyA; | 1651 goto CopyA; |
1556 if (bcount >= min_gallop) | 1652 if (bcount >= min_gallop) |
1557 break; | 1653 break; |
1558 } | 1654 } |
1559 } | 1655 } |
1560 | 1656 |
1561 /* One run is winning so consistently that galloping may | 1657 /* One run is winning so consistently that galloping may |
1562 * be a huge win. So try that, and continue galloping until | 1658 * be a huge win. So try that, and continue galloping until |
1563 * (if ever) neither run appears to be winning consistently | 1659 * (if ever) neither run appears to be winning consistently |
1564 * anymore. | 1660 * anymore. |
1565 */ | 1661 */ |
1566 ++min_gallop; | 1662 ++min_gallop; |
1567 do { | 1663 do { |
1568 assert(na > 0 && nb > 1); | 1664 assert(na > 0 && nb > 1); |
1569 min_gallop -= min_gallop > 1; | 1665 min_gallop -= min_gallop > 1; |
1570 ms->min_gallop = min_gallop; | 1666 ms->min_gallop = min_gallop; |
1571 k = gallop_right(*pb, basea, na, na-1); | 1667 k = gallop_right(ssb.keys[0], basea.keys, na, na-1); |
1572 if (k < 0) | 1668 if (k < 0) |
1573 goto Fail; | 1669 goto Fail; |
1574 k = na - k; | 1670 k = na - k; |
1575 acount = k; | 1671 acount = k; |
1576 if (k) { | 1672 if (k) { |
1577 dest -= k; | 1673 sortslice_advance(&dest, -k); |
1578 pa -= k; | 1674 sortslice_advance(&ssa, -k); |
1579 memmove(dest+1, pa+1, k * sizeof(PyObject *)); | 1675 sortslice_memmove(&dest, 1, &ssa, 1, k); |
1580 na -= k; | 1676 na -= k; |
1581 if (na == 0) | 1677 if (na == 0) |
1582 goto Succeed; | 1678 goto Succeed; |
1583 } | 1679 } |
1584 *dest-- = *pb--; | 1680 sortslice_copy_decr(&dest, &ssb); |
1585 --nb; | 1681 --nb; |
1586 if (nb == 1) | 1682 if (nb == 1) |
1587 goto CopyA; | 1683 goto CopyA; |
1588 | 1684 |
1589 k = gallop_left(*pa, baseb, nb, nb-1); | 1685 k = gallop_left(ssa.keys[0], baseb.keys, nb, nb-1); |
1590 if (k < 0) | 1686 if (k < 0) |
1591 goto Fail; | 1687 goto Fail; |
1592 k = nb - k; | 1688 k = nb - k; |
1593 bcount = k; | 1689 bcount = k; |
1594 if (k) { | 1690 if (k) { |
1595 dest -= k; | 1691 sortslice_advance(&dest, -k); |
1596 pb -= k; | 1692 sortslice_advance(&ssb, -k); |
1597 memcpy(dest+1, pb+1, k * sizeof(PyObject *)); | 1693 sortslice_memcpy(&dest, 1, &ssb, 1, k); |
1598 nb -= k; | 1694 nb -= k; |
1599 if (nb == 1) | 1695 if (nb == 1) |
1600 goto CopyA; | 1696 goto CopyA; |
1601 /* nb==0 is impossible now if the comparison | 1697 /* nb==0 is impossible now if the comparison |
1602 * function is consistent, but we can't assume | 1698 * function is consistent, but we can't assume |
1603 * that it is. | 1699 * that it is. |
1604 */ | 1700 */ |
1605 if (nb == 0) | 1701 if (nb == 0) |
1606 goto Succeed; | 1702 goto Succeed; |
1607 } | 1703 } |
1608 *dest-- = *pa--; | 1704 sortslice_copy_decr(&dest, &ssa); |
1609 --na; | 1705 --na; |
1610 if (na == 0) | 1706 if (na == 0) |
1611 goto Succeed; | 1707 goto Succeed; |
1612 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); | 1708 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
1613 ++min_gallop; /* penalize it for leaving galloping mode */ | 1709 ++min_gallop; /* penalize it for leaving galloping mode */ |
1614 ms->min_gallop = min_gallop; | 1710 ms->min_gallop = min_gallop; |
1615 } | 1711 } |
1616 Succeed: | 1712 Succeed: |
1617 result = 0; | 1713 result = 0; |
1618 Fail: | 1714 Fail: |
1619 if (nb) | 1715 if (nb) |
1620 memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*)); | 1716 sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb); |
1621 return result; | 1717 return result; |
1622 CopyA: | 1718 CopyA: |
1623 assert(nb == 1 && na > 0); | 1719 assert(nb == 1 && na > 0); |
1624 /* The first element of pb belongs at the front of the merge. */ | 1720 /* The first element of pb belongs at the front of the merge. */ |
1625 dest -= na; | 1721 sortslice_memmove(&dest, 1-na, &ssa, 1-na, na); |
1626 pa -= na; | 1722 sortslice_advance(&dest, -na); |
1627 memmove(dest+1, pa+1, na * sizeof(PyObject *)); | 1723 sortslice_advance(&ssa, -na); |
1628 *dest = *pb; | 1724 sortslice_copy(&dest, 0, &ssb, 0); |
1629 return 0; | 1725 return 0; |
1630 } | 1726 } |
1631 | 1727 |
1632 /* Merge the two runs at stack indices i and i+1. | 1728 /* Merge the two runs at stack indices i and i+1. |
1633 * Returns 0 on success, -1 on error. | 1729 * Returns 0 on success, -1 on error. |
1634 */ | 1730 */ |
1635 static Py_ssize_t | 1731 static Py_ssize_t |
1636 merge_at(MergeState *ms, Py_ssize_t i) | 1732 merge_at(MergeState *ms, Py_ssize_t i) |
1637 { | 1733 { |
1638 PyObject **pa, **pb; | 1734 sortslice ssa, ssb; |
1639 Py_ssize_t na, nb; | 1735 Py_ssize_t na, nb; |
1640 Py_ssize_t k; | 1736 Py_ssize_t k; |
1641 | 1737 |
1642 assert(ms != NULL); | 1738 assert(ms != NULL); |
1643 assert(ms->n >= 2); | 1739 assert(ms->n >= 2); |
1644 assert(i >= 0); | 1740 assert(i >= 0); |
1645 assert(i == ms->n - 2 || i == ms->n - 3); | 1741 assert(i == ms->n - 2 || i == ms->n - 3); |
1646 | 1742 |
1647 pa = ms->pending[i].base; | 1743 ssa = ms->pending[i].base; |
1648 na = ms->pending[i].len; | 1744 na = ms->pending[i].len; |
1649 pb = ms->pending[i+1].base; | 1745 ssb = ms->pending[i+1].base; |
1650 nb = ms->pending[i+1].len; | 1746 nb = ms->pending[i+1].len; |
1651 assert(na > 0 && nb > 0); | 1747 assert(na > 0 && nb > 0); |
1652 assert(pa + na == pb); | 1748 assert(ssa.keys + na == ssb.keys); |
1653 | 1749 |
1654 /* Record the length of the combined runs; if i is the 3rd-last | 1750 /* 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 | 1751 * 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. | 1752 * in this merge). The current run i+1 goes away in any case. |
1657 */ | 1753 */ |
1658 ms->pending[i].len = na + nb; | 1754 ms->pending[i].len = na + nb; |
1659 if (i == ms->n - 3) | 1755 if (i == ms->n - 3) |
1660 ms->pending[i+1] = ms->pending[i+2]; | 1756 ms->pending[i+1] = ms->pending[i+2]; |
1661 --ms->n; | 1757 --ms->n; |
1662 | 1758 |
1663 /* Where does b start in a? Elements in a before that can be | 1759 /* Where does b start in a? Elements in a before that can be |
1664 * ignored (already in place). | 1760 * ignored (already in place). |
1665 */ | 1761 */ |
1666 k = gallop_right(*pb, pa, na, 0); | 1762 k = gallop_right(*ssb.keys, ssa.keys, na, 0); |
1667 if (k < 0) | 1763 if (k < 0) |
1668 return -1; | 1764 return -1; |
1669 pa += k; | 1765 sortslice_advance(&ssa, k); |
1670 na -= k; | 1766 na -= k; |
1671 if (na == 0) | 1767 if (na == 0) |
1672 return 0; | 1768 return 0; |
1673 | 1769 |
1674 /* Where does a end in b? Elements in b after that can be | 1770 /* Where does a end in b? Elements in b after that can be |
1675 * ignored (already in place). | 1771 * ignored (already in place). |
1676 */ | 1772 */ |
1677 nb = gallop_left(pa[na-1], pb, nb, nb-1); | 1773 nb = gallop_left(ssa.keys[na-1], ssb.keys, nb, nb-1); |
1678 if (nb <= 0) | 1774 if (nb <= 0) |
1679 return nb; | 1775 return nb; |
1680 | 1776 |
1681 /* Merge what remains of the runs, using a temp array with | 1777 /* Merge what remains of the runs, using a temp array with |
1682 * min(na, nb) elements. | 1778 * min(na, nb) elements. |
1683 */ | 1779 */ |
1684 if (na <= nb) | 1780 if (na <= nb) |
1685 return merge_lo(ms, pa, na, pb, nb); | 1781 return merge_lo(ms, ssa, na, ssb, nb); |
1686 else | 1782 else |
1687 return merge_hi(ms, pa, na, pb, nb); | 1783 return merge_hi(ms, ssa, na, ssb, nb); |
1688 } | 1784 } |
1689 | 1785 |
1690 /* Examine the stack of runs waiting to be merged, merging adjacent runs | 1786 /* Examine the stack of runs waiting to be merged, merging adjacent runs |
1691 * until the stack invariants are re-established: | 1787 * until the stack invariants are re-established: |
1692 * | 1788 * |
1693 * 1. len[-3] > len[-2] + len[-1] | 1789 * 1. len[-3] > len[-2] + len[-1] |
1694 * 2. len[-2] > len[-1] | 1790 * 2. len[-2] > len[-1] |
1695 * | 1791 * |
1696 * See listsort.txt for more info. | 1792 * See listsort.txt for more info. |
1697 * | 1793 * |
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1758 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */ | 1854 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */ |
1759 | 1855 |
1760 assert(n >= 0); | 1856 assert(n >= 0); |
1761 while (n >= 64) { | 1857 while (n >= 64) { |
1762 r |= n & 1; | 1858 r |= n & 1; |
1763 n >>= 1; | 1859 n >>= 1; |
1764 } | 1860 } |
1765 return n + r; | 1861 return n + r; |
1766 } | 1862 } |
1767 | 1863 |
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 | 1864 static void |
1785 sortwrapper_dealloc(sortwrapperobject *); | 1865 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 { | 1866 { |
1819 if (!PyObject_TypeCheck(b, &PySortWrapper_Type)) { | 1867 reverse_slice(s->keys, &s->keys[n]); |
1820 PyErr_SetString(PyExc_TypeError, | 1868 if (s->values != NULL) |
1821 "expected a sortwrapperobject"); | 1869 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 } | 1870 } |
1866 | 1871 |
1867 /* An adaptive, stable, natural mergesort. See listsort.txt. | 1872 /* An adaptive, stable, natural mergesort. See listsort.txt. |
1868 * Returns Py_None on success, NULL on error. Even in case of error, the | 1873 * 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 | 1874 * list will be some permutation of its input state (nothing is lost or |
1870 * duplicated). | 1875 * duplicated). |
1871 */ | 1876 */ |
1872 static PyObject * | 1877 static PyObject * |
1873 listsort(PyListObject *self, PyObject *args, PyObject *kwds) | 1878 listsort(PyListObject *self, PyObject *args, PyObject *kwds) |
1874 { | 1879 { |
1875 MergeState ms; | 1880 MergeState ms; |
1876 PyObject **lo, **hi; | 1881 sortslice lo, hi; |
1877 Py_ssize_t nremaining; | 1882 Py_ssize_t nremaining; |
1878 Py_ssize_t minrun; | 1883 Py_ssize_t minrun; |
1879 Py_ssize_t saved_ob_size, saved_allocated; | 1884 Py_ssize_t saved_ob_size, saved_allocated; |
1880 PyObject **saved_ob_item; | 1885 PyObject **saved_ob_item; |
1881 PyObject **final_ob_item; | 1886 PyObject **final_ob_item; |
1882 PyObject *result = NULL; /* guilty until proved innocent */ | 1887 PyObject *result = NULL; /* guilty until proved innocent */ |
1883 int reverse = 0; | 1888 int reverse = 0; |
1884 PyObject *keyfunc = NULL; | 1889 PyObject *keyfunc = NULL; |
1885 Py_ssize_t i; | 1890 Py_ssize_t i; |
1886 PyObject *key, *value, *kvpair; | |
1887 static char *kwlist[] = {"key", "reverse", 0}; | 1891 static char *kwlist[] = {"key", "reverse", 0}; |
| 1892 PyObject **keys; |
| 1893 PyObject *stack_keys[8]; |
1888 | 1894 |
1889 assert(self != NULL); | 1895 assert(self != NULL); |
1890 assert (PyList_Check(self)); | 1896 assert (PyList_Check(self)); |
1891 if (args != NULL) { | 1897 if (args != NULL) { |
1892 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort", | 1898 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort", |
1893 kwlist, &keyfunc, &reverse)) | 1899 kwlist, &keyfunc, &reverse)) |
1894 return NULL; | 1900 return NULL; |
1895 if (Py_SIZE(args) > 0) { | 1901 if (Py_SIZE(args) > 0) { |
1896 PyErr_SetString(PyExc_TypeError, | 1902 PyErr_SetString(PyExc_TypeError, |
1897 "must use keyword argument for key function"); | 1903 "must use keyword argument for key function"); |
1898 return NULL; | 1904 return NULL; |
1899 } | 1905 } |
1900 } | 1906 } |
1901 if (keyfunc == Py_None) | 1907 if (keyfunc == Py_None) |
1902 keyfunc = NULL; | 1908 keyfunc = NULL; |
1903 | 1909 |
| 1910 if (Py_SIZE(self) < 2) |
| 1911 Py_RETURN_NONE; |
| 1912 |
| 1913 if (keyfunc == NULL) |
| 1914 keys = NULL; |
| 1915 else if (Py_SIZE(self) <= sizeof(stack_keys) / sizeof(stack_keys[0])) { |
| 1916 keys = stack_keys; |
| 1917 } else { |
| 1918 keys = PyMem_MALLOC(sizeof(PyObject *) * Py_SIZE(self)); |
| 1919 if (keys == NULL) |
| 1920 return NULL; |
| 1921 } |
| 1922 |
1904 /* The list is temporarily made empty, so that mutations performed | 1923 /* The list is temporarily made empty, so that mutations performed |
1905 * by comparison functions can't affect the slice of memory we're | 1924 * by comparison functions can't affect the slice of memory we're |
1906 * sorting (allowing mutations during sorting is a core-dump | 1925 * sorting (allowing mutations during sorting is a core-dump |
1907 * factory, since ob_item may change). | 1926 * factory, since ob_item may change). |
1908 */ | 1927 */ |
1909 saved_ob_size = Py_SIZE(self); | 1928 saved_ob_size = Py_SIZE(self); |
1910 saved_ob_item = self->ob_item; | 1929 saved_ob_item = self->ob_item; |
1911 saved_allocated = self->allocated; | 1930 saved_allocated = self->allocated; |
1912 Py_SIZE(self) = 0; | 1931 Py_SIZE(self) = 0; |
1913 self->ob_item = NULL; | 1932 self->ob_item = NULL; |
1914 self->allocated = -1; /* any operation will reset it to >= 0 */ | 1933 self->allocated = -1; /* any operation will reset it to >= 0 */ |
1915 | 1934 |
1916 if (keyfunc != NULL) { | 1935 if (keyfunc != NULL) { |
1917 for (i=0 ; i < saved_ob_size ; i++) { | 1936 for (i = 0; i < saved_ob_size ; i++) { |
1918 value = saved_ob_item[i]; | 1937 keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i], |
1919 key = PyObject_CallFunctionObjArgs(keyfunc, value, | 1938 NULL); |
1920 NULL); | 1939 if (keys[i] == NULL) { |
1921 if (key == NULL) { | 1940 for (i=i-1 ; i>=0 ; i--) |
1922 for (i=i-1 ; i>=0 ; i--) { | 1941 Py_DECREF(keys[i]); |
1923 kvpair = saved_ob_item[i]; | |
1924 value = sortwrapper_getvalue(kvpair); | |
1925 saved_ob_item[i] = value; | |
1926 Py_DECREF(kvpair); | |
1927 } | |
1928 goto dsu_fail; | 1942 goto dsu_fail; |
1929 } | 1943 } |
1930 kvpair = build_sortwrapper(key, value); | |
1931 if (kvpair == NULL) | |
1932 goto dsu_fail; | |
1933 saved_ob_item[i] = kvpair; | |
1934 } | 1944 } |
1935 } | 1945 } |
1936 | 1946 |
1937 merge_init(&ms); | 1947 merge_init(&ms, keyfunc != NULL); |
1938 | 1948 |
1939 nremaining = saved_ob_size; | 1949 nremaining = saved_ob_size; |
1940 if (nremaining < 2) | |
1941 goto succeed; | |
1942 | 1950 |
1943 /* Reverse sort stability achieved by initially reversing the list, | 1951 /* Reverse sort stability achieved by initially reversing the list, |
1944 applying a stable forward sort, then reversing the final result. */ | 1952 applying a stable forward sort, then reversing the final result. */ |
1945 if (reverse) | 1953 if (reverse) { |
1946 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); | 1954 if (keys != NULL) |
| 1955 reverse_slice(&keys[0], &keys[saved_ob_size]); |
| 1956 reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]); |
| 1957 } |
1947 | 1958 |
1948 /* March over the array once, left to right, finding natural runs, | 1959 /* March over the array once, left to right, finding natural runs, |
1949 * and extending short natural runs to minrun elements. | 1960 * and extending short natural runs to minrun elements. |
1950 */ | 1961 */ |
1951 lo = saved_ob_item; | 1962 if (keyfunc == NULL) { |
1952 hi = lo + nremaining; | 1963 lo.keys = saved_ob_item; |
| 1964 lo.values = NULL; |
| 1965 hi.keys = lo.keys + nremaining; |
| 1966 hi.values = NULL; |
| 1967 } else { |
| 1968 lo.keys = keys; |
| 1969 lo.values = saved_ob_item; |
| 1970 hi.keys = lo.keys + nremaining; |
| 1971 hi.values = lo.values + nremaining; |
| 1972 } |
1953 minrun = merge_compute_minrun(nremaining); | 1973 minrun = merge_compute_minrun(nremaining); |
1954 do { | 1974 do { |
1955 int descending; | 1975 int descending; |
1956 Py_ssize_t n; | 1976 Py_ssize_t n; |
1957 | 1977 |
1958 /* Identify next run. */ | 1978 /* Identify next run. */ |
1959 n = count_run(lo, hi, &descending); | 1979 n = count_run(lo.keys, hi.keys, &descending); |
1960 if (n < 0) | 1980 if (n < 0) |
1961 goto fail; | 1981 goto fail; |
1962 if (descending) | 1982 if (descending) |
1963 reverse_slice(lo, lo + n); | 1983 reverse_sortslice(&lo, n); |
1964 /* If short, extend to min(minrun, nremaining). */ | 1984 /* If short, extend to min(minrun, nremaining). */ |
1965 if (n < minrun) { | 1985 if (n < minrun) { |
1966 const Py_ssize_t force = nremaining <= minrun ? | 1986 const Py_ssize_t force = nremaining <= minrun ? |
1967 nremaining : minrun; | 1987 nremaining : minrun; |
1968 if (binarysort(lo, lo + force, lo + n) < 0) | 1988 if (binarysort(lo, lo.keys + force, lo.keys + n) < 0) |
1969 goto fail; | 1989 goto fail; |
1970 n = force; | 1990 n = force; |
1971 } | 1991 } |
1972 /* Push run onto pending-runs stack, and maybe merge. */ | 1992 /* Push run onto pending-runs stack, and maybe merge. */ |
1973 assert(ms.n < MAX_MERGE_PENDING); | 1993 assert(ms.n < MAX_MERGE_PENDING); |
1974 ms.pending[ms.n].base = lo; | 1994 ms.pending[ms.n].base = lo; |
1975 ms.pending[ms.n].len = n; | 1995 ms.pending[ms.n].len = n; |
1976 ++ms.n; | 1996 ++ms.n; |
1977 if (merge_collapse(&ms) < 0) | 1997 if (merge_collapse(&ms) < 0) |
1978 goto fail; | 1998 goto fail; |
1979 /* Advance to find next run. */ | 1999 /* Advance to find next run. */ |
1980 lo += n; | 2000 sortslice_advance(&lo, n); |
1981 nremaining -= n; | 2001 nremaining -= n; |
1982 } while (nremaining); | 2002 } while (nremaining); |
1983 assert(lo == hi); | 2003 assert(lo.keys == hi.keys); |
1984 | 2004 |
1985 if (merge_force_collapse(&ms) < 0) | 2005 if (merge_force_collapse(&ms) < 0) |
1986 goto fail; | 2006 goto fail; |
1987 assert(ms.n == 1); | 2007 assert(ms.n == 1); |
1988 assert(ms.pending[0].base == saved_ob_item); | 2008 assert(keyfunc == NULL |
| 2009 ? ms.pending[0].base.keys == saved_ob_item |
| 2010 : ms.pending[0].base.keys == &keys[0]); |
1989 assert(ms.pending[0].len == saved_ob_size); | 2011 assert(ms.pending[0].len == saved_ob_size); |
1990 | 2012 |
1991 succeed: | |
1992 result = Py_None; | 2013 result = Py_None; |
| 2014 |
| 2015 if (reverse && saved_ob_size > 1) |
| 2016 reverse_sortslice(&ms.pending[0].base, saved_ob_size); |
| 2017 |
1993 fail: | 2018 fail: |
1994 if (keyfunc != NULL) { | 2019 if (keyfunc != NULL) { |
1995 for (i=0 ; i < saved_ob_size ; i++) { | 2020 for (i = 0; i < saved_ob_size; i++) |
1996 kvpair = saved_ob_item[i]; | 2021 Py_DECREF(keys[i]); |
1997 value = sortwrapper_getvalue(kvpair); | 2022 if (keys != stack_keys) |
1998 saved_ob_item[i] = value; | 2023 PyMem_FREE(keys); |
1999 Py_DECREF(kvpair); | |
2000 } | |
2001 } | 2024 } |
2002 | 2025 |
2003 if (self->allocated != -1 && result != NULL) { | 2026 if (self->allocated != -1 && result != NULL) { |
2004 /* The user mucked with the list during the sort, | 2027 /* The user mucked with the list during the sort, |
2005 * and we don't already have another error to report. | 2028 * and we don't already have another error to report. |
2006 */ | 2029 */ |
2007 PyErr_SetString(PyExc_ValueError, "list modified during sort"); | 2030 PyErr_SetString(PyExc_ValueError, "list modified during sort"); |
2008 result = NULL; | 2031 result = NULL; |
2009 } | 2032 } |
2010 | 2033 |
2011 if (reverse && saved_ob_size > 1) | |
2012 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); | |
2013 | |
2014 merge_freemem(&ms); | 2034 merge_freemem(&ms); |
2015 | 2035 |
2016 dsu_fail: | 2036 dsu_fail: |
2017 final_ob_item = self->ob_item; | 2037 final_ob_item = self->ob_item; |
2018 i = Py_SIZE(self); | 2038 i = Py_SIZE(self); |
2019 Py_SIZE(self) = saved_ob_size; | 2039 Py_SIZE(self) = saved_ob_size; |
2020 self->ob_item = saved_ob_item; | 2040 self->ob_item = saved_ob_item; |
2021 self->allocated = saved_allocated; | 2041 self->allocated = saved_allocated; |
2022 if (final_ob_item != NULL) { | 2042 if (final_ob_item != NULL) { |
2023 /* we cannot use list_clear() for this because it does not | 2043 /* we cannot use list_clear() for this because it does not |
(...skipping 832 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2856 | 2876 |
2857 static PyObject * | 2877 static PyObject * |
2858 listreviter_len(listreviterobject *it) | 2878 listreviter_len(listreviterobject *it) |
2859 { | 2879 { |
2860 Py_ssize_t len = it->it_index + 1; | 2880 Py_ssize_t len = it->it_index + 1; |
2861 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len) | 2881 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len) |
2862 len = 0; | 2882 len = 0; |
2863 return PyLong_FromSsize_t(len); | 2883 return PyLong_FromSsize_t(len); |
2864 } | 2884 } |
2865 | 2885 |
OLD | NEW |