sort with a key speed patch - Code Review (original) (raw)

OLD

NEW

1 /* List object implementation */

3 #include "Python.h"

5 #ifdef STDC_HEADERS

6 #include <stddef.h>

7 #else

8 #include <sys/types.h> /* For size_t */

9 #endif

(...skipping 922 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading...

933 *hi = t;

934 ++lo;

935 --hi;

936 }

937 }

938

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.

941 */

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 . X and Y are PyObject*s.

1011 started. It makes more sense in context . 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+1 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 Py_LOCAL_INLINE(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 int 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)

977 ++start;

978 for (; start < hi; ++start) {

1036 for (; start < hi; ++start) {

979 /* set l to where *start belongs */

1037 /* set l to where *start belongs */

980 l = lo;

1038 l = lo.keys;

981 r = start;

1039 r = start;

982 pivot = *r;

1040 pivot = *r;

983 /* Invariants:

1041 /* Invariants:

984 * pivot >= all in [lo, l).

1042 * pivot >= all in [lo, l).

985 * pivot < all in [r, start).

1043 * pivot < all in [r, start).

986 * The second is vacuously true at the start.

1044 * The second is vacuously true at the start.

987 */

1045 */

988 assert(l < r);

1046 assert(l < r);

989 do {

1047 do {

990 p = l + ((r - l) >> 1);

1048 p = l + ((r - l) >> 1);

991 IFLT(pivot, *p)

1049 IFLT(pivot, *p)

992 r = p;

1050 r = p;

993 else

1051 else

994 l = p+1;

1052 l = p+1;

995 } while (l < r);

1053 } while (l < r);

996 assert(l == r);

1054 assert(l == r);

997 /* The invariants still hold, so pivot >= all in [lo, l) and

1055 /* The invariants still hold, so pivot >= all in [lo, l) and

998 pivot < all in [l, start), so pivot belongs at l. Note

1056 pivot < all in [l, start), so pivot belongs at l. Note

999 that if there are elements equal to pivot, l points to the

1057 that if there are elements equal to pivot, l points to the

1000 first slot after them -- that's why this sort is stable.

1058 first slot after them -- that's why this sort is stable.

1001 Slide over to make room.

1059 Slide over to make room.

1002 Caution: using memmove is much slower under MSVC 5;

1060 Caution: using memmove is much slower under MSVC 5;

1003 we're not usually moving many slots. */

1061 we're not usually moving many slots. */

1004 for (p = start; p > l; --p)

1062 for (p = start; p > l; --p)

1005 *p = *(p-1);

1063 *p = *(p-1);

1006 *l = pivot;

1064 *l = pivot;

1065 if (lo.values != NULL) {

1066 Py_ssize_t offset = lo.values - lo.keys;

1067 p = start + offset;

1068 pivot = *p;

1069 l += offset;

1070 for (p = start + offset; p > l; --p)

1071 *p = *(p-1);

1072 *l = pivot;

1073 }

1007 }

1074 }

1008 return 0;

1075 return 0;

1009

1076

1010 fail:

1077 fail:

1011 return -1;

1078 return -1;

1012 }

1079 }

1013

1080

1014 /*

1081 /*

1015 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi

1082 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

1083 is required on entry. "A run" is the longest ascending sequence, with

1017

1084

1018 lo[0] <= lo[1] <= lo[2] <= ...

1085 lo[0] <= lo[1] <= lo[2] <= ...

1019

1086

1020 or the longest descending sequence, with

1087 or the longest descending sequence, with

1021

1088

1022 lo[0] > lo[1] > lo[2] > ...

1089 lo[0] > lo[1] > lo[2] > ...

1023

1090

1024 Boolean *descending is set to 0 in the former case, or to 1 in the latter.

1091 Boolean *descending is set to 0 in the former case, or to 1 in the latter.

1025 For its intended use in a stable mergesort, the strictness of the defn of

1092 For its intended use in a stable mergesort, the strictness of the defn of

1026 "descending" is needed so that the caller can safely reverse a descending

1093 "descending" is needed so that the caller can safely reverse a descending

1027 sequence without violating stability (strict > ensures there are no equal

1094 sequence without violating stability (strict > ensures there are no equal

1028 elements to get out of order).

1095 elements to get out of order).

1029

1096

1030 Returns -1 in case of error.

1097 Returns -1 in case of error.

1031 */

1098 */

1032 static Py_ssize_t

1099 Py_LOCAL_INLINE(Py_ssize_t)

1033 count_run(PyObject **lo, PyObject **hi, int *descending)

1100 count_run(PyObject **lo, PyObject **hi, int *descending)

1034 {

1101 {

1035 Py_ssize_t k;

1102 int k;

1036 Py_ssize_t n;

1103 Py_ssize_t n;

1037

1104

1038 assert(lo < hi);

1105 assert(lo < hi);

1039 *descending = 0;

1106 *descending = 0;

1040 ++lo;

1107 ++lo;

1041 if (lo == hi)

1108 if (lo == hi)

1042 return 1;

1109 return 1;

1043

1110

1044 n = 2;

1111 n = 2;

1045 IFLT(*lo, *(lo-1)) {

1112 IFLT(*lo, *(lo-1)) {

1046 *descending = 1;

1113 *descending = 1;

1047 for (lo = lo+1; lo < hi; ++lo, ++n) {

1114 for (lo = lo+1; lo < hi; ++lo, ++n) {

1048 IFLT(*lo, *(lo-1))

1115 IFLT(*lo, *(lo-1))

1049 ;

1116 ;

1050 else

1117 else

1051 break;

1118 break;

1052 }

1119 }

1053 }

1120 } else {

1054 else {

1055 for (lo = lo+1; lo < hi; ++lo, ++n) {

1121 for (lo = lo+1; lo < hi; ++lo, ++n) {

1056 IFLT(*lo, *(lo-1))

1122 IFLT(*lo, *(lo-1))

1057 break;

1123 break;

1058 }

1124 }

1059 }

1125 }

1060

1126

1061 return n;

1127 return n;

1062 fail:

1128 fail:

1063 return -1;

1129 return -1;

1064 }

1130 }

(...skipping 17 matching lines...) Expand all Loading...

1082 key belongs at index k; or, IOW, the first k elements of a should precede

1148 key belongs at index k; or, IOW, the first k elements of a should precede

1083 key, and the last n-k should follow key.

1149 key, and the last n-k should follow key.

1084

1150

1085 Returns -1 on error. See listsort.txt for info on the method.

1151 Returns -1 on error. See listsort.txt for info on the method.

1086 */

1152 */

1087 static Py_ssize_t

1153 static Py_ssize_t

1088 gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)

1154 gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)

1089 {

1155 {

1090 Py_ssize_t ofs;

1156 Py_ssize_t ofs;

1091 Py_ssize_t lastofs;

1157 Py_ssize_t lastofs;

1092 Py_ssize_t k;

1158 int k;

1093

1159

1094 assert(key && a && n > 0 && hint >= 0 && hint < n);

1160 assert(key && a && n > 0 && hint >= 0 && hint < n);

1095

1161

1096 a += hint;

1162 a += hint;

1097 lastofs = 0;

1163 lastofs = 0;

1098 ofs = 1;

1164 ofs = 1;

1099 IFLT(*a, key) {

1165 IFLT(*a, key) {

1100 /* a[hint] < key -- gallop right, until

1166 /* a[hint] < key -- gallop right, until

1101 * a[hint + lastofs] < key <= a[hint + ofs]

1167 * a[hint + lastofs] < key <= a[hint + ofs]

1102 */

1168 */

(...skipping 12 matching lines...) Expand all Loading...

1115 ofs = maxofs;

1181 ofs = maxofs;

1116 /* Translate back to offsets relative to &a[0]. */

1182 /* Translate back to offsets relative to &a[0]. */

1117 lastofs += hint;

1183 lastofs += hint;

1118 ofs += hint;

1184 ofs += hint;

1119 }

1185 }

1120 else {

1186 else {

1121 /* key <= a[hint] -- gallop left, until

1187 /* key <= a[hint] -- gallop left, until

1122 * a[hint - ofs] < key <= a[hint - lastofs]

1188 * a[hint - ofs] < key <= a[hint - lastofs]

1123 */

1189 */

1124 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */

1190 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */

1191 Py_ssize_t tmp;

1125 while (ofs < maxofs) {

1192 while (ofs < maxofs) {

1126 IFLT(*(a-ofs), key)

1193 IFLT(*(a-ofs), key)

1127 break;

1194 break;

1128 /* key <= a[hint - ofs] */

1195 /* key <= a[hint - ofs] */

1129 lastofs = ofs;

1196 lastofs = ofs;

1130 ofs = (ofs << 1) + 1;

1197 ofs = (ofs << 1) + 1;

1131 if (ofs <= 0) /* int overflow */

1198 if (ofs <= 0) /* int overflow */

1132 ofs = maxofs;

1199 ofs = maxofs;

1133 }

1200 }

1134 if (ofs > maxofs)

1201 if (ofs > maxofs)

1135 ofs = maxofs;

1202 ofs = maxofs;

1136 /* Translate back to positive offsets relative to &a[0]. */

1203 /* Translate back to positive offsets relative to &a[0]. */

1137 k = lastofs;

1204 tmp = lastofs;

1138 lastofs = hint - ofs;

1205 lastofs = hint - ofs;

1139 ofs = hint - k;

1206 ofs = hint - tmp;

1140 }

1207 }

1141 a -= hint;

1208 a -= hint;

1142

1209

1143 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);

1210 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);

1144 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the

1211 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the

1145 * right of lastofs but no farther right than ofs. Do a binary

1212 * right of lastofs but no farther right than ofs. Do a binary

1146 * search, with invariant a[lastofs-1] < key <= a[ofs].

1213 * search, with invariant a[lastofs-1] < key <= a[ofs].

1147 */

1214 */

1148 ++lastofs;

1215 ++lastofs;

1149 while (lastofs < ofs) {

1216 while (lastofs < ofs) {

(...skipping 23 matching lines...) Expand all Loading...

1173

1240

1174 The code duplication is massive, but this is enough different given that

1241 The code duplication is massive, but this is enough different given that

1175 we're sticking to "<" comparisons that it's much harder to follow if

1242 we're sticking to "<" comparisons that it's much harder to follow if

1176 written as one routine with yet another "left or right?" flag.

1243 written as one routine with yet another "left or right?" flag.

1177 */

1244 */

1178 static Py_ssize_t

1245 static Py_ssize_t

1179 gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)

1246 gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)

1180 {

1247 {

1181 Py_ssize_t ofs;

1248 Py_ssize_t ofs;

1182 Py_ssize_t lastofs;

1249 Py_ssize_t lastofs;

1183 Py_ssize_t k;

1250 int k;

1184

1251

1185 assert(key && a && n > 0 && hint >= 0 && hint < n);

1252 assert(key && a && n > 0 && hint >= 0 && hint < n);

1186

1253

1187 a += hint;

1254 a += hint;

1188 lastofs = 0;

1255 lastofs = 0;

1189 ofs = 1;

1256 ofs = 1;

1190 IFLT(key, *a) {

1257 IFLT(key, *a) {

1191 /* key < a[hint] -- gallop left, until

1258 /* key < a[hint] -- gallop left, until

1192 * a[hint - ofs] <= key < a[hint - lastofs]

1259 * a[hint - ofs] <= key < a[hint - lastofs]

1193 */

1260 */

1194 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */

1261 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */

1262 Py_ssize_t tmp;

1195 while (ofs < maxofs) {

1263 while (ofs < maxofs) {

1196 IFLT(key, *(a-ofs)) {

1264 IFLT(key, *(a-ofs)) {

1197 lastofs = ofs;

1265 lastofs = ofs;

1198 ofs = (ofs << 1) + 1;

1266 ofs = (ofs << 1) + 1;

1199 if (ofs <= 0) /* int overflow */

1267 if (ofs <= 0) /* int overflow */

1200 ofs = maxofs;

1268 ofs = maxofs;

1201 }

1269 }

1202 else /* a[hint - ofs] <= key */

1270 else /* a[hint - ofs] <= key */

1203 break;

1271 break;

1204 }

1272 }

1205 if (ofs > maxofs)

1273 if (ofs > maxofs)

1206 ofs = maxofs;

1274 ofs = maxofs;

1207 /* Translate back to positive offsets relative to &a[0]. */

1275 /* Translate back to positive offsets relative to &a[0]. */

1208 k = lastofs;

1276 tmp = lastofs;

1209 lastofs = hint - ofs;

1277 lastofs = hint - ofs;

1210 ofs = hint - k;

1278 ofs = hint - tmp;

1211 }

1279 }

1212 else {

1280 else {

1213 /* a[hint] <= key -- gallop right, until

1281 /* a[hint] <= key -- gallop right, until

1214 * a[hint + lastofs] <= key < a[hint + ofs]

1282 * a[hint + lastofs] <= key < a[hint + ofs]

1215 */

1283 */

1216 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */

1284 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */

1217 while (ofs < maxofs) {

1285 while (ofs < maxofs) {

1218 IFLT(key, a[ofs])

1286 IFLT(key, a[ofs])

1219 break;

1287 break;

1220 /* a[hint + ofs] <= key */

1288 /* a[hint + ofs] <= key */

1221 lastofs = ofs;

1289 lastofs = ofs;

1222 ofs = (ofs << 1) + 1;

1290 ofs = (ofs << 1) + 1;

1223 if (ofs <= 0) /* int overflow */

1291 if (ofs <= 0) /* int overflow */

1224 ofs = maxofs;

1292 ofs = maxofs;

1225 }

1293 }

1226 if (ofs > maxofs)

1294 if (ofs > maxofs)

(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading...

1264 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.

1332 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.

1265 */

1333 */

1266 #define MIN_GALLOP 7

1334 #define MIN_GALLOP 7

1267

1335

1268 /* Avoid malloc for small temp arrays. */

1336 /* Avoid malloc for small temp arrays. */

1269 #define MERGESTATE_TEMP_SIZE 256

1337 #define MERGESTATE_TEMP_SIZE 256

1270

1338

1271 /* One MergeState exists on the stack per invocation of mergesort. It's just

1339 /* 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.

1340 * a convenient way to pass state around among the helper functions.

1273 */

1341 */

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 Py_LOCAL_INLINE(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;

1384 if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)

1385 ms->alloced = MERGESTATE_TEMP_SIZE / 2;

1386 ms->a.values = &ms->temparray[ms->alloced];

1387 } else {

1388 ms->alloced = MERGESTATE_TEMP_SIZE;

1389 ms->a.values = NULL;

1390 }

1391 ms->a.keys = ms->temparray;

1315 ms->n = 0;

1392 ms->n = 0;

1316 ms->min_gallop = MIN_GALLOP;

1393 ms->min_gallop = MIN_GALLOP;

1317 }

1394 }

1318

1395

1319 /* Free all the temp memory owned by the MergeState. This must be called

1396 /* 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

1397 * when you're done with a MergeState, and may be called before then if

1321 * you want to free the temp memory early.

1398 * you want to free the temp memory early.

1322 */

1399 */

1323 static void

1400 Py_LOCAL_INLINE(void)

1324 merge_freemem(MergeState *ms)

1401 merge_freemem(MergeState *ms)

1325 {

1402 {

1326 assert(ms != NULL);

1403 assert(ms != NULL);

1327 if (ms->a != ms->temparray)

1404 if (ms->a.keys != ms->temparray)

1328 PyMem_Free(ms->a);

1405 PyMem_Free(ms->a.keys);

1329 ms->a = ms->temparray;

1330 ms->alloced = MERGESTATE_TEMP_SIZE;

1331 }

1406 }

1332

1407

1333 /* Ensure enough temp memory for 'need' array slots is available.

1408 /* Ensure enough temp memory for 'need' array slots is available.

1334 * Returns 0 on success and -1 if the memory can't be gotten.

1409 * Returns 0 on success and -1 if the memory can't be gotten.

1335 */

1410 */

1336 static int

1411 static int

1337 merge_getmem(MergeState *ms, Py_ssize_t need)

1412 merge_getmem(MergeState *ms, Py_ssize_t need)

1338 {

1413 {

1414 int multiplier;

1415

1339 assert(ms != NULL);

1416 assert(ms != NULL);

1340 if (need <= ms->alloced)

1417 if (need <= ms->alloced)

1341 return 0;

1418 return 0;

1419

1420 multiplier = ms->a.values != NULL ? 2 : 1;

1421

1342 /* Don't realloc! That can cost cycles to copy the old data, but

1422 /* Don't realloc! That can cost cycles to copy the old data, but

1343 * we don't care what's in the block.

1423 * we don't care what's in the block.

1344 */

1424 */

1345 merge_freemem(ms);

1425 merge_freemem(ms);

1346 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) {

1426 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*) / multiplier) {

1347 PyErr_NoMemory();

1427 PyErr_NoMemory();

1348 return -1;

1428 return -1;

1349 }

1429 }

1350 ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*));

1430 ms->a.keys = (PyObject**)PyMem_Malloc(multiplier * need

1351 if (ms->a) {

1431 * sizeof(PyObject *));

1432 if (ms->a.keys != NULL) {

1352 ms->alloced = need;

1433 ms->alloced = need;

1434 if (ms->a.values != NULL)

1435 ms->a.values = &ms->a.keys[need];

1353 return 0;

1436 return 0;

1354 }

1437 }

1355 PyErr_NoMemory();

1438 PyErr_NoMemory();

1356 merge_freemem(ms); /* reset to sane state */

1357 return -1;

1439 return -1;

1358 }

1440 }

1359 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \

1441 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \

1360 merge_getmem(MS, NEED))

1442 merge_getmem(MS, NEED))

1361

1443

1362 /* Merge the na elements starting at pa with the nb elements starting at pb

1444 /* 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.

1445 * 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

1446 * 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.

1447 * merge, and should have na <= nb. See listsort.txt for more info.

1366 * Return 0 if successful, -1 if error.

1448 * Return 0 if successful, -1 if error.

1367 */

1449 */

1368 static Py_ssize_t

1450 static Py_ssize_t

1369 merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na,

1451 merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,

1370 PyObject **pb, Py_ssize_t nb)

1452 sortslice ssb, Py_ssize_t nb)

1371 {

1453 {

1372 Py_ssize_t k;

1454 Py_ssize_t k;

1373 PyObject **dest;

1455 sortslice dest;

1374 int result = -1; /* guilty until proved innocent */

1456 int result = -1; /* guilty until proved innocent */

1375 Py_ssize_t min_gallop;

1457 Py_ssize_t min_gallop;

1376

1458

1377 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb);

1459 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);

1460 assert(ssa.keys + na == ssb.keys);

1378 if (MERGE_GETMEM(ms, na) < 0)

1461 if (MERGE_GETMEM(ms, na) < 0)

1379 return -1;

1462 return -1;

1380 memcpy(ms->a, pa, na * sizeof(PyObject*));

1463 sortslice_memcpy(&ms->a, 0, &ssa, 0, na);

1381 dest = pa;

1464 dest = ssa;

1382 pa = ms->a;

1465 ssa = ms->a;

1383

1466

1384 *dest++ = *pb++;

1467 sortslice_copy_incr(&dest, &ssb);

1385 --nb;

1468 --nb;

1386 if (nb == 0)

1469 if (nb == 0)

1387 goto Succeed;

1470 goto Succeed;

1388 if (na == 1)

1471 if (na == 1)

1389 goto CopyB;

1472 goto CopyB;

1390

1473

1391 min_gallop = ms->min_gallop;

1474 min_gallop = ms->min_gallop;

1392 for (;;) {

1475 for (;;) {

1393 Py_ssize_t acount = 0; /* # of times A won in a row */

1476 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 */

1477 Py_ssize_t bcount = 0; /* # of times B won in a row */

1395

1478

1396 /* Do the straightforward thing until (if ever) one run

1479 /* Do the straightforward thing until (if ever) one run

1397 * appears to win consistently.

1480 * appears to win consistently.

1398 */

1481 */

1399 for (;;) {

1482 for (;;) {

1400 assert(na > 1 && nb > 0);

1483 assert(na > 1 && nb > 0);

1401 k = ISLT(*pb, *pa);

1484 k = ISLT(ssb.keys[0], ssa.keys[0]);

1402 if (k) {

1485 if (k) {

1403 if (k < 0)

1486 if (k < 0)

1404 goto Fail;

1487 goto Fail;

1405 *dest++ = *pb++;

1488 sortslice_copy_incr(&dest, &ssb);

1406 ++bcount;

1489 ++bcount;

1407 acount = 0;

1490 acount = 0;

1408 --nb;

1491 --nb;

1409 if (nb == 0)

1492 if (nb == 0)

1410 goto Succeed;

1493 goto Succeed;

1411 if (bcount >= min_gallop)

1494 if (bcount >= min_gallop)

1412 break;

1495 break;

1413 }

1496 } else {

1414 else {

1497 sortslice_copy_incr(&dest, &ssa);

1415 *dest++ = *pa++;

1416 ++acount;

1498 ++acount;

1417 bcount = 0;

1499 bcount = 0;

1418 --na;

1500 --na;

1419 if (na == 1)

1501 if (na == 1)

1420 goto CopyB;

1502 goto CopyB;

1421 if (acount >= min_gallop)

1503 if (acount >= min_gallop)

1422 break;

1504 break;

1423 }

1505 }

1424 }

1506 }

1425

1507

1426 /* One run is winning so consistently that galloping may

1508 /* One run is winning so consistently that galloping may

1427 * be a huge win. So try that, and continue galloping until

1509 * be a huge win. So try that, and continue galloping until

1428 * (if ever) neither run appears to be winning consistently

1510 * (if ever) neither run appears to be winning consistently

1429 * anymore.

1511 * anymore.

1430 */

1512 */

1431 ++min_gallop;

1513 ++min_gallop;

1432 do {

1514 do {

1433 assert(na > 1 && nb > 0);

1515 assert(na > 1 && nb > 0);

1434 min_gallop -= min_gallop > 1;

1516 min_gallop -= min_gallop > 1;

1435 ms->min_gallop = min_gallop;

1517 ms->min_gallop = min_gallop;

1436 k = gallop_right(*pb, pa, na, 0);

1518 k = gallop_right(ssb.keys[0], ssa.keys, na, 0);

1437 acount = k;

1519 acount = k;

1438 if (k) {

1520 if (k) {

1439 if (k < 0)

1521 if (k < 0)

1440 goto Fail;

1522 goto Fail;

1441 memcpy(dest, pa, k * sizeof(PyObject *));

1523 sortslice_memcpy(&dest, 0, &ssa, 0, k);

1442 dest += k;

1524 sortslice_advance(&dest, k);

1443 pa += k;

1525 sortslice_advance(&ssa, k);

1444 na -= k;

1526 na -= k;

1445 if (na == 1)

1527 if (na == 1)

1446 goto CopyB;

1528 goto CopyB;

1447 /* na==0 is impossible now if the comparison

1529 /* na==0 is impossible now if the comparison

1448 * function is consistent, but we can't assume

1530 * function is consistent, but we can't assume

1449 * that it is.

1531 * that it is.

1450 */

1532 */

1451 if (na == 0)

1533 if (na == 0)

1452 goto Succeed;

1534 goto Succeed;

1453 }

1535 }

1454 *dest++ = *pb++;

1536 sortslice_copy_incr(&dest, &ssb);

1455 --nb;

1537 --nb;

1456 if (nb == 0)

1538 if (nb == 0)

1457 goto Succeed;

1539 goto Succeed;

1458

1540

1459 k = gallop_left(*pa, pb, nb, 0);

1541 k = gallop_left(ssa.keys[0], ssb.keys, nb, 0);

1460 bcount = k;

1542 bcount = k;

1461 if (k) {

1543 if (k) {

1462 if (k < 0)

1544 if (k < 0)

1463 goto Fail;

1545 goto Fail;

1464 memmove(dest, pb, k * sizeof(PyObject *));

1546 sortslice_memmove(&dest, 0, &ssb, 0, k);

1465 dest += k;

1547 sortslice_advance(&dest, k);

1466 pb += k;

1548 sortslice_advance(&ssb, k);

1467 nb -= k;

1549 nb -= k;

1468 if (nb == 0)

1550 if (nb == 0)

1469 goto Succeed;

1551 goto Succeed;

1470 }

1552 }

1471 *dest++ = *pa++;

1553 sortslice_copy_incr(&dest, &ssa);

1472 --na;

1554 --na;

1473 if (na == 1)

1555 if (na == 1)

1474 goto CopyB;

1556 goto CopyB;

1475 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);

1557 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);

1476 ++min_gallop; /* penalize it for leaving galloping mode */

1558 ++min_gallop; /* penalize it for leaving galloping mode */

1477 ms->min_gallop = min_gallop;

1559 ms->min_gallop = min_gallop;

1478 }

1560 }

1479 Succeed:

1561 Succeed:

1480 result = 0;

1562 result = 0;

1481 Fail:

1563 Fail:

1482 if (na)

1564 if (na)

1483 memcpy(dest, pa, na * sizeof(PyObject*));

1565 sortslice_memcpy(&dest, 0, &ssa, 0, na);

1484 return result;

1566 return result;

1485 CopyB:

1567 CopyB:

1486 assert(na == 1 && nb > 0);

1568 assert(na == 1 && nb > 0);

1487 /* The last element of pa belongs at the end of the merge. */

1569 /* The last element of pa belongs at the end of the merge. */

1488 memmove(dest, pb, nb * sizeof(PyObject *));

1570 sortslice_memmove(&dest, 0, &ssb, 0, nb);

1489 dest[nb] = *pa;

1571 sortslice_copy(&dest, nb, &ssa, 0);

1490 return 0;

1572 return 0;

1491 }

1573 }

1492

1574

1493 /* Merge the na elements starting at pa with the nb elements starting at pb

1575 /* 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.

1576 * 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

1577 * 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.

1578 * merge, and should have na >= nb. See listsort.txt for more info.

1497 * Return 0 if successful, -1 if error.

1579 * Return 0 if successful, -1 if error.

1498 */

1580 */

1499 static Py_ssize_t

1581 static Py_ssize_t

1500 merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb)

1582 merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,

1583 sortslice ssb, Py_ssize_t nb)

1501 {

1584 {

1502 Py_ssize_t k;

1585 Py_ssize_t k;

1503 PyObject **dest;

1586 sortslice dest;

1504 int result = -1; /* guilty until proved innocent */

1587 int result = -1; /* guilty until proved innocent */

1505 PyObject **basea;

1588 sortslice basea;

1506 PyObject **baseb;

1589 sortslice 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 pb 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 *

1698 * Returns 0 on success, -1 on error.

1785 * Returns 0 on success, -1 on error.

1699 */

1786 */

1700 static int

1787 Py_LOCAL_INLINE(int)

1701 merge_collapse(MergeState *ms)

1788 merge_collapse(MergeState *ms)

1702 {

1789 {

1703 struct s_slice *p = ms->pending;

1790 struct s_slice *p = ms->pending;

1704

1791

1705 assert(ms);

1792 assert(ms);

1706 while (ms->n > 1) {

1793 while (ms->n > 1) {

1707 Py_ssize_t n = ms->n - 2;

1794 Py_ssize_t n = ms->n - 2;

1708 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {

1795 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {

1709 if (p[n-1].len < p[n+1].len)

1796 if (p[n-1].len < p[n+1].len)

1710 --n;

1797 --n;

1711 if (merge_at(ms, n) < 0)

1798 if (merge_at(ms, n) < 0)

1712 return -1;

1799 return -1;

1713 }

1800 }

1714 else if (p[n].len <= p[n+1].len) {

1801 else if (p[n].len <= p[n+1].len) {

1715 if (merge_at(ms, n) < 0)

1802 if (merge_at(ms, n) < 0)

1716 return -1;

1803 return -1;

1717 }

1804 }

1718 else

1805 else

1719 break;

1806 break;

1720 }

1807 }

1721 return 0;

1808 return 0;

1722 }

1809 }

1723

1810

1724 /* Regardless of invariants, merge all runs on the stack until only one

1811 /* Regardless of invariants, merge all runs on the stack until only one

1725 * remains. This is used at the end of the mergesort.

1812 * remains. This is used at the end of the mergesort.

1726 *

1813 *

1727 * Returns 0 on success, -1 on error.

1814 * Returns 0 on success, -1 on error.

1728 */

1815 */

1729 static int

1816 Py_LOCAL_INLINE(int)

1730 merge_force_collapse(MergeState *ms)

1817 merge_force_collapse(MergeState *ms)

1731 {

1818 {

1732 struct s_slice *p = ms->pending;

1819 struct s_slice *p = ms->pending;

1733

1820

1734 assert(ms);

1821 assert(ms);

1735 while (ms->n > 1) {

1822 while (ms->n > 1) {

1736 Py_ssize_t n = ms->n - 2;

1823 Py_ssize_t n = ms->n - 2;

1737 if (n > 0 && p[n-1].len < p[n+1].len)

1824 if (n > 0 && p[n-1].len < p[n+1].len)

1738 --n;

1825 --n;

1739 if (merge_at(ms, n) < 0)

1826 if (merge_at(ms, n) < 0)

1740 return -1;

1827 return -1;

1741 }

1828 }

1742 return 0;

1829 return 0;

1743 }

1830 }

1744

1831

1745 /* Compute a good value for the minimum run length; natural runs shorter

1832 /* Compute a good value for the minimum run length; natural runs shorter

1746 * than this are boosted artificially via binary insertion.

1833 * than this are boosted artificially via binary insertion.

1747 *

1834 *

1748 * If n < 64, return n (it's too small to bother with fancy stuff).

1835 * If n < 64, return n (it's too small to bother with fancy stuff).

1749 * Else if n is an exact power of 2, return 32.

1836 * Else if n is an exact power of 2, return 32.

1750 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but

1837 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but

1751 * strictly less than, an exact power of 2.

1838 * strictly less than, an exact power of 2.

1752 *

1839 *

1753 * See listsort.txt for more info.

1840 * See listsort.txt for more info.

1754 */

1841 */

1755 static Py_ssize_t

1842 Py_LOCAL_INLINE(Py_ssize_t)

1756 merge_compute_minrun(Py_ssize_t n)

1843 merge_compute_minrun(Py_ssize_t n)

1757 {

1844 {

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

1855 Py_LOCAL_INLINE(void)

1769 pattern. Holds a key which is used for comparisons and the original record

1856 reverse_sortslice(sortslice s, Py_ssize_t n)

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

1785 sortwrapper_dealloc(sortwrapperobject *);

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;

1872 sortslice lo, hi;

1877 Py_ssize_t nremaining;

1873 Py_ssize_t nremaining;

1878 Py_ssize_t minrun;

1874 Py_ssize_t minrun;

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, was_allocated;

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 }

1896 if (keyfunc == Py_None)

1897 keyfunc = NULL;

1900 }

1898 }

1901 if (keyfunc == Py_None)

1902 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);

1906 if (saved_ob_size < 2)

1907 Py_RETURN_NONE;

1910 saved_ob_item = self->ob_item;

1908 saved_ob_item = self->ob_item;

1911 saved_allocated = self->allocated;

1909 saved_allocated = self->allocated;

1912 Py_SIZE(self) = 0;

1910 Py_SIZE(self) = 0;

1913 self->ob_item = NULL;

1911 self->ob_item = NULL;

1914 self->allocated = -1; /* any operation will reset it to >= 0 */

1912 self->allocated = -1; /* any operation will reset it to >= 0 */

1915

1913

1916 if (keyfunc != NULL) {

1914 if (keyfunc == NULL) {

1917 for (i=0 ; i < saved_ob_size ; i++) {

1915 keys = NULL;

1918 value = saved_ob_item[i];

1916 lo.keys = saved_ob_item;

1919 key = PyObject_CallFunctionObjArgs(keyfunc, value,

1917 lo.values = NULL;

1920 NULL);

1918 hi.keys = saved_ob_item + saved_ob_size;

1921 if (key == NULL) {

1919 hi.values = NULL;

1922 for (i=i-1 ; i>=0 ; i--) {

1920 } else {

1923 kvpair = saved_ob_item[i];

1921 if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)

1924 value = sortwrapper_getvalue(kvpair);

1922 keys = &ms.temparray[saved_ob_size+1];

1925 saved_ob_item[i] = value;

1923 else {

1926 Py_DECREF(kvpair);

1924 keys = PyMem_MALLOC(sizeof(PyObject *) * saved_ob_size);

1927 }

1925 if (keys == NULL)

1926 return NULL;

1927 }

1928

1929 for (i = 0; i < saved_ob_size ; i++) {

1930 keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i],

1931 NULL);

1932 if (keys[i] == NULL) {

1933 for (i=i-1 ; i>=0 ; i--)

1934 Py_DECREF(keys[i]);

1928 goto dsu_fail;

1935 goto dsu_fail;

1929 }

1936 }

1930 kvpair = build_sortwrapper(key, value);

1931 if (kvpair == NULL)

1932 goto dsu_fail;

1933 saved_ob_item[i] = kvpair;

1934 }

1937 }

1938

1939 lo.keys = keys;

1940 lo.values = saved_ob_item;

1941 hi.keys = keys + saved_ob_size;

1942 hi.values = saved_ob_item + saved_ob_size;

1935 }

1943 }

1936

1944

1937 merge_init(&ms);

1945 merge_init(&ms, saved_ob_size, keys != NULL);

1938

1946

1939 nremaining = saved_ob_size;

1947 nremaining = saved_ob_size;

1940 if (nremaining < 2)

1941 goto succeed;

1942

1948

1943 /* Reverse sort stability achieved by initially reversing the list,

1949 /* Reverse sort stability achieved by initially reversing the list,

1944 applying a stable forward sort, then reversing the final result. */

1950 applying a stable forward sort, then reversing the final result. */

1945 if (reverse)

1951 if (reverse) {

1946 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);

1952 if (keys != NULL)

1953 reverse_slice(&keys[0], &keys[saved_ob_size]);

1954 reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);

1955 }

1947

1956

1948 /* March over the array once, left to right, finding natural runs,

1957 /* March over the array once, left to right, finding natural runs,

1949 * and extending short natural runs to minrun elements.

1958 * and extending short natural runs to minrun elements.

1950 */

1959 */

1951 lo = saved_ob_item;

1952 hi = lo + nremaining;

1953 minrun = merge_compute_minrun(nremaining);

1960 minrun = merge_compute_minrun(nremaining);

1954 do {

1961 do {

1955 int descending;

1962 int descending;

1956 Py_ssize_t n;

1963 Py_ssize_t n;

1957

1964

1958 /* Identify next run. */

1965 /* Identify next run. */

1959 n = count_run(lo, hi, &descending);

1966 n = count_run(lo.keys, hi.keys, &descending);

1960 if (n < 0)

1967 if (n < 0)

1961 goto fail;

1968 goto fail;

1962 if (descending)

1969 if (descending)

1963 reverse_slice(lo, lo + n);

1970 reverse_sortslice(lo, n);

1964 /* If short, extend to min(minrun, nremaining). */

1971 /* If short, extend to min(minrun, nremaining). */

1965 if (n < minrun) {

1972 if (n < minrun) {

1966 const Py_ssize_t force = nremaining <= minrun ?

1973 Py_ssize_t force = nremaining <= minrun ? nremaining : minrun;

1967 nremaining : minrun;

1974 if (binarysort(lo, lo.keys + force, lo.keys + n) < 0)

1968 if (binarysort(lo, lo + force, lo + n) < 0)

1969 goto fail;

1975 goto fail;

1970 n = force;

1976 n = force;

1971 }

1977 }

1978 if (n == saved_ob_size)

1979 goto all_done;

1980

1972 /* Push run onto pending-runs stack, and maybe merge. */

1981 /* Push run onto pending-runs stack, and maybe merge. */

1973 assert(ms.n < MAX_MERGE_PENDING);

1982 assert(ms.n < MAX_MERGE_PENDING);

1974 ms.pending[ms.n].base = lo;

1983 ms.pending[ms.n].base = lo;

1975 ms.pending[ms.n].len = n;

1984 ms.pending[ms.n].len = n;

1976 ++ms.n;

1985 ++ms.n;

1977 if (merge_collapse(&ms) < 0)

1986 if (merge_collapse(&ms) < 0)

1978 goto fail;

1987 goto fail;

1979 /* Advance to find next run. */

1988 /* Advance to find next run. */

1980 lo += n;

1989 sortslice_advance(&lo, n);

1981 nremaining -= n;

1990 nremaining -= n;

1982 } while (nremaining);

1991 } while (nremaining);

1983 assert(lo == hi);

1992 assert(lo.keys == hi.keys);

1984

1993

1985 if (merge_force_collapse(&ms) < 0)

1994 if (merge_force_collapse(&ms) < 0)

1986 goto fail;

1995 goto fail;

1987 assert(ms.n == 1);

1996 assert(ms.n == 1);

1988 assert(ms.pending[0].base == saved_ob_item);

1997 assert(keys == NULL

1998 ? ms.pending[0].base.keys == saved_ob_item

1999 : ms.pending[0].base.keys == &keys[0]);

1989 assert(ms.pending[0].len == saved_ob_size);

2000 assert(ms.pending[0].len == saved_ob_size);

2001 lo = ms.pending[0].base;

1990

2002

1991 succeed:

2003 all_done:

1992 result = Py_None;

2004 result = Py_None;

2005

2006 if (reverse)

2007 reverse_sortslice(lo, saved_ob_size);

2008

1993 fail:

2009 fail:

1994 if (keyfunc != NULL) {

2010 if (keys != NULL) {

1995 for (i=0 ; i < saved_ob_size ; i++) {

2011 for (i = 0; i < saved_ob_size; i++)

1996 kvpair = saved_ob_item[i];

2012 Py_DECREF(keys[i]);

1997 value = sortwrapper_getvalue(kvpair);

2013 if (keys != &ms.temparray[saved_ob_size+1])

1998 saved_ob_item[i] = value;

2014 PyMem_FREE(keys);

1999 Py_DECREF(kvpair);

2000 }

2001 }

2015 }

2002

2016

2003 if (self->allocated != -1 && result != NULL) {

2004 /* The user mucked with the list during the sort,

2005 * and we don't already have another error to report.

2006 */

2007 PyErr_SetString(PyExc_ValueError, "list modified during sort");

2008 result = NULL;

2009 }

2010

2011 if (reverse && saved_ob_size > 1)

2012 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);

2013

2014 merge_freemem(&ms);

2017 merge_freemem(&ms);

2015

2018

2016 dsu_fail:

2019 dsu_fail:

2020 was_allocated = self->allocated;

2021 self->allocated = saved_allocated;

2017 final_ob_item = self->ob_item;

2022 final_ob_item = self->ob_item;

2018 i = Py_SIZE(self);

2023 i = Py_SIZE(self);

2019 Py_SIZE(self) = saved_ob_size;

2024 Py_SIZE(self) = saved_ob_size;

2020 self->ob_item = saved_ob_item;

2025 self->ob_item = saved_ob_item;

2021 self->allocated = saved_allocated;

2026

2022 if (final_ob_item != NULL) {

2027 if (was_allocated != -1) {

2023 /* we cannot use list_clear() for this because it does not

2028 if (result != NULL) {

2024 guarantee that the list is really empty when it returns */

2029 /* The user mucked with the list during the sort,

2025 while (--i >= 0) {

2030 * and we don't already have another error to report.

2026 Py_XDECREF(final_ob_item[i]);

2031 */

2032 PyErr_SetString(PyExc_ValueError, "list modified during sort");

2033 result = NULL;

2027 }

2034 }

2028 PyMem_FREE(final_ob_item);

2035

2036 if (final_ob_item != NULL) {

2037 /* we cannot use list_clear() for this because it does not

2038 guarantee that the list is really empty when it returns */

2039 while (--i >= 0)

2040 Py_XDECREF(final_ob_item[i]);

2041 PyMem_FREE(final_ob_item);

2042 }

2029 }

2043 }

2044

2030 Py_XINCREF(result);

2045 Py_XINCREF(result);

2031 return result;

2046 return result;

2032 }

2047 }

2033 #undef IFLT

2048 #undef IFLT

2034 #undef ISLT

2049 #undef ISLT

2035

2050

2036 int

2051 int

2037 PyList_Sort(PyObject *v)

2052 PyList_Sort(PyObject *v)

2038 {

2053 {

2039 if (v == NULL || !PyList_Check(v)) {

2054 if (v == NULL || !PyList_Check(v)) {

(...skipping 816 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading...

2856

2871

2857 static PyObject *

2872 static PyObject *

2858 listreviter_len(listreviterobject *it)

2873 listreviter_len(listreviterobject *it)

2859 {

2874 {

2860 Py_ssize_t len = it->it_index + 1;

2875 Py_ssize_t len = it->it_index + 1;

2861 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)

2876 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)

2862 len = 0;

2877 len = 0;

2863 return PyLong_FromSsize_t(len);

2878 return PyLong_FromSsize_t(len);

2864 }

2879 }

2865

2880

OLD

NEW