1: /*
2: * taken from https://github.com/swenson/sort
3: * Kept as is for the moment to be able to apply upstream patches for that
4: * code, currently used only to speed up XPath node sorting, see xpath.c
5: */
6:
7: /*
8: * All code in this header, unless otherwise specified, is hereby licensed under the MIT Public License:
9:
10: Copyright (c) 2010 Christopher Swenson
11:
12: Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
13:
14: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
15:
16: THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
17: */
18:
19: #include <stdlib.h>
20: #include <stdio.h>
21: #include <string.h>
22: #ifdef HAVE_STDINT_H
23: #include <stdint.h>
24: #else
25: #ifdef HAVE_INTTYPES_H
26: #include <inttypes.h>
27: #elif defined(WIN32)
28: typedef __int64 int64_t;
29: typedef unsigned __int64 uint64_t;
30: #endif
31: #endif
32:
33: #ifndef MK_UINT64
34: #if defined(WIN32) && defined(_MSC_VER) && _MSC_VER < 1300
35: #define MK_UINT64(x) ((uint64_t)(x))
36: #else
37: #define MK_UINT64(x) x##ULL
38: #endif
39: #endif
40:
41: #ifndef MAX
42: #define MAX(x,y) (((x) > (y) ? (x) : (y)))
43: #endif
44: #ifndef MIN
45: #define MIN(x,y) (((x) < (y) ? (x) : (y)))
46: #endif
47:
48: int compute_minrun(uint64_t);
49:
50: #ifndef CLZ
51: #if defined(__GNUC__) && ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__GNUC__ > 3))
52: #define CLZ __builtin_clzll
53: #else
54:
55: int clzll(uint64_t);
56:
57: /* adapted from Hacker's Delight */
58: int clzll(uint64_t x) /* {{{ */
59: {
60: int n;
61:
62: if (x == 0) return(64);
63: n = 0;
64: if (x <= 0x00000000FFFFFFFFL) {n = n + 32; x = x << 32;}
65: if (x <= 0x0000FFFFFFFFFFFFL) {n = n + 16; x = x << 16;}
66: if (x <= 0x00FFFFFFFFFFFFFFL) {n = n + 8; x = x << 8;}
67: if (x <= 0x0FFFFFFFFFFFFFFFL) {n = n + 4; x = x << 4;}
68: if (x <= 0x3FFFFFFFFFFFFFFFL) {n = n + 2; x = x << 2;}
69: if (x <= 0x7FFFFFFFFFFFFFFFL) {n = n + 1;}
70: return n;
71: }
72: /* }}} */
73:
74: #define CLZ clzll
75: #endif
76: #endif
77:
78: int compute_minrun(uint64_t size) /* {{{ */
79: {
80: const int top_bit = 64 - CLZ(size);
81: const int shift = MAX(top_bit, 6) - 6;
82: const int minrun = size >> shift;
83: const uint64_t mask = (MK_UINT64(1) << shift) - 1;
84: if (mask & size) return minrun + 1;
85: return minrun;
86: }
87: /* }}} */
88:
89: #ifndef SORT_NAME
90: #error "Must declare SORT_NAME"
91: #endif
92:
93: #ifndef SORT_TYPE
94: #error "Must declare SORT_TYPE"
95: #endif
96:
97: #ifndef SORT_CMP
98: #define SORT_CMP(x, y) ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))
99: #endif
100:
101:
102: #define SORT_SWAP(x,y) {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;}
103:
104: #define SORT_CONCAT(x, y) x ## _ ## y
105: #define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y)
106: #define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x)
107:
108: #define BINARY_INSERTION_FIND SORT_MAKE_STR(binary_insertion_find)
109: #define BINARY_INSERTION_SORT_START SORT_MAKE_STR(binary_insertion_sort_start)
110: #define BINARY_INSERTION_SORT SORT_MAKE_STR(binary_insertion_sort)
111: #define REVERSE_ELEMENTS SORT_MAKE_STR(reverse_elements)
112: #define COUNT_RUN SORT_MAKE_STR(count_run)
113: #define CHECK_INVARIANT SORT_MAKE_STR(check_invariant)
114: #define TIM_SORT SORT_MAKE_STR(tim_sort)
115: #define TIM_SORT_RESIZE SORT_MAKE_STR(tim_sort_resize)
116: #define TIM_SORT_MERGE SORT_MAKE_STR(tim_sort_merge)
117: #define TIM_SORT_COLLAPSE SORT_MAKE_STR(tim_sort_collapse)
118:
119: #define TIM_SORT_RUN_T SORT_MAKE_STR(tim_sort_run_t)
120: #define TEMP_STORAGE_T SORT_MAKE_STR(temp_storage_t)
121:
122: typedef struct {
123: int64_t start;
124: int64_t length;
125: } TIM_SORT_RUN_T;
126:
127: void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size);
128: void TIM_SORT(SORT_TYPE *dst, const size_t size);
129:
130: /* Function used to do a binary search for binary insertion sort */
131: static int64_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x, const size_t size)
132: {
133: int64_t l, c, r;
134: SORT_TYPE lx;
135: SORT_TYPE cx;
136: l = 0;
137: r = size - 1;
138: c = r >> 1;
139: lx = dst[l];
140:
141: /* check for beginning conditions */
142: if (SORT_CMP(x, lx) < 0)
143: return 0;
144: else if (SORT_CMP(x, lx) == 0)
145: {
146: int64_t i = 1;
147: while (SORT_CMP(x, dst[i]) == 0) i++;
148: return i;
149: }
150:
151: cx = dst[c];
152: while (1)
153: {
154: const int val = SORT_CMP(x, cx);
155: if (val < 0)
156: {
157: if (c - l <= 1) return c;
158: r = c;
159: }
160: else if (val > 0)
161: {
162: if (r - c <= 1) return c + 1;
163: l = c;
164: lx = cx;
165: }
166: else
167: {
168: do
169: {
170: cx = dst[++c];
171: } while (SORT_CMP(x, cx) == 0);
172: return c;
173: }
174: c = l + ((r - l) >> 1);
175: cx = dst[c];
176: }
177: }
178:
179: /* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
180: static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size)
181: {
182: int64_t i;
183: for (i = start; i < (int64_t) size; i++)
184: {
185: int64_t j;
186: SORT_TYPE x;
187: int64_t location;
188: /* If this entry is already correct, just move along */
189: if (SORT_CMP(dst[i - 1], dst[i]) <= 0) continue;
190:
191: /* Else we need to find the right place, shift everything over, and squeeze in */
192: x = dst[i];
193: location = BINARY_INSERTION_FIND(dst, x, i);
194: for (j = i - 1; j >= location; j--)
195: {
196: dst[j + 1] = dst[j];
197: }
198: dst[location] = x;
199: }
200: }
201:
202: /* Binary insertion sort */
203: void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size)
204: {
205: BINARY_INSERTION_SORT_START(dst, 1, size);
206: }
207:
208: /* timsort implementation, based on timsort.txt */
209:
210: static void REVERSE_ELEMENTS(SORT_TYPE *dst, int64_t start, int64_t end)
211: {
212: while (1)
213: {
214: if (start >= end) return;
215: SORT_SWAP(dst[start], dst[end]);
216: start++;
217: end--;
218: }
219: }
220:
221: static int64_t COUNT_RUN(SORT_TYPE *dst, const int64_t start, const size_t size)
222: {
223: int64_t curr;
224: if (size - start == 1) return 1;
225: if (start >= (int64_t) size - 2)
226: {
227: if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0)
228: SORT_SWAP(dst[size - 2], dst[size - 1]);
229: return 2;
230: }
231:
232: curr = start + 2;
233:
234: if (SORT_CMP(dst[start], dst[start + 1]) <= 0)
235: {
236: /* increasing run */
237: while (1)
238: {
239: if (curr == (int64_t) size - 1) break;
240: if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) break;
241: curr++;
242: }
243: return curr - start;
244: }
245: else
246: {
247: /* decreasing run */
248: while (1)
249: {
250: if (curr == (int64_t) size - 1) break;
251: if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) break;
252: curr++;
253: }
254: /* reverse in-place */
255: REVERSE_ELEMENTS(dst, start, curr - 1);
256: return curr - start;
257: }
258: }
259:
260: #define PUSH_NEXT() do {\
261: len = COUNT_RUN(dst, curr, size);\
262: run = minrun;\
263: if (run < minrun) run = minrun;\
264: if (run > (int64_t) size - curr) run = size - curr;\
265: if (run > len)\
266: {\
267: BINARY_INSERTION_SORT_START(&dst[curr], len, run);\
268: len = run;\
269: }\
270: {\
271: run_stack[stack_curr].start = curr;\
272: run_stack[stack_curr].length = len;\
273: stack_curr++;\
274: }\
275: curr += len;\
276: if (curr == (int64_t) size)\
277: {\
278: /* finish up */ \
279: while (stack_curr > 1) \
280: { \
281: TIM_SORT_MERGE(dst, run_stack, stack_curr, store); \
282: run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; \
283: stack_curr--; \
284: } \
285: if (store->storage != NULL)\
286: {\
287: free(store->storage);\
288: store->storage = NULL;\
289: }\
290: return;\
291: }\
292: }\
293: while (0)
294:
295: static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr)
296: {
297: int64_t A, B, C;
298: if (stack_curr < 2) return 1;
299: if (stack_curr == 2)
300: {
301: const int64_t A1 = stack[stack_curr - 2].length;
302: const int64_t B1 = stack[stack_curr - 1].length;
303: if (A1 <= B1) return 0;
304: return 1;
305: }
306: A = stack[stack_curr - 3].length;
307: B = stack[stack_curr - 2].length;
308: C = stack[stack_curr - 1].length;
309: if ((A <= B + C) || (B <= C)) return 0;
310: return 1;
311: }
312:
313: typedef struct {
314: size_t alloc;
315: SORT_TYPE *storage;
316: } TEMP_STORAGE_T;
317:
318:
319: static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size)
320: {
321: if (store->alloc < new_size)
322: {
323: SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeof(SORT_TYPE));
324: if (tempstore == NULL)
325: {
326: fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu bytes", sizeof(SORT_TYPE) * new_size);
327: exit(1);
328: }
329: store->storage = tempstore;
330: store->alloc = new_size;
331: }
332: }
333:
334: static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const int stack_curr, TEMP_STORAGE_T *store)
335: {
336: const int64_t A = stack[stack_curr - 2].length;
337: const int64_t B = stack[stack_curr - 1].length;
338: const int64_t curr = stack[stack_curr - 2].start;
339: SORT_TYPE *storage;
340: int64_t i, j, k;
341:
342: TIM_SORT_RESIZE(store, MIN(A, B));
343: storage = store->storage;
344:
345: /* left merge */
346: if (A < B)
347: {
348: memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE));
349: i = 0;
350: j = curr + A;
351:
352: for (k = curr; k < curr + A + B; k++)
353: {
354: if ((i < A) && (j < curr + A + B))
355: {
356: if (SORT_CMP(storage[i], dst[j]) <= 0)
357: dst[k] = storage[i++];
358: else
359: dst[k] = dst[j++];
360: }
361: else if (i < A)
362: {
363: dst[k] = storage[i++];
364: }
365: else
366: dst[k] = dst[j++];
367: }
368: }
369: /* right merge */
370: else
371: {
372: memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
373: i = B - 1;
374: j = curr + A - 1;
375:
376: for (k = curr + A + B - 1; k >= curr; k--)
377: {
378: if ((i >= 0) && (j >= curr))
379: {
380: if (SORT_CMP(dst[j], storage[i]) > 0)
381: dst[k] = dst[j--];
382: else
383: dst[k] = storage[i--];
384: }
385: else if (i >= 0)
386: dst[k] = storage[i--];
387: else
388: dst[k] = dst[j--];
389: }
390: }
391: }
392:
393: static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr, TEMP_STORAGE_T *store, const size_t size)
394: {
395: while (1)
396: {
397: int64_t A, B, C;
398: /* if the stack only has one thing on it, we are done with the collapse */
399: if (stack_curr <= 1) break;
400: /* if this is the last merge, just do it */
401: if ((stack_curr == 2) &&
402: (stack[0].length + stack[1].length == (int64_t) size))
403: {
404: TIM_SORT_MERGE(dst, stack, stack_curr, store);
405: stack[0].length += stack[1].length;
406: stack_curr--;
407: break;
408: }
409: /* check if the invariant is off for a stack of 2 elements */
410: else if ((stack_curr == 2) && (stack[0].length <= stack[1].length))
411: {
412: TIM_SORT_MERGE(dst, stack, stack_curr, store);
413: stack[0].length += stack[1].length;
414: stack_curr--;
415: break;
416: }
417: else if (stack_curr == 2)
418: break;
419:
420: A = stack[stack_curr - 3].length;
421: B = stack[stack_curr - 2].length;
422: C = stack[stack_curr - 1].length;
423:
424: /* check first invariant */
425: if (A <= B + C)
426: {
427: if (A < C)
428: {
429: TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
430: stack[stack_curr - 3].length += stack[stack_curr - 2].length;
431: stack[stack_curr - 2] = stack[stack_curr - 1];
432: stack_curr--;
433: }
434: else
435: {
436: TIM_SORT_MERGE(dst, stack, stack_curr, store);
437: stack[stack_curr - 2].length += stack[stack_curr - 1].length;
438: stack_curr--;
439: }
440: }
441: /* check second invariant */
442: else if (B <= C)
443: {
444: TIM_SORT_MERGE(dst, stack, stack_curr, store);
445: stack[stack_curr - 2].length += stack[stack_curr - 1].length;
446: stack_curr--;
447: }
448: else
449: break;
450: }
451: return stack_curr;
452: }
453:
454: void TIM_SORT(SORT_TYPE *dst, const size_t size)
455: {
456: int minrun;
457: TEMP_STORAGE_T _store, *store;
458: TIM_SORT_RUN_T run_stack[128];
459: int stack_curr = 0;
460: int64_t len, run;
461: int64_t curr = 0;
462:
463: if (size < 64)
464: {
465: BINARY_INSERTION_SORT(dst, size);
466: return;
467: }
468:
469: /* compute the minimum run length */
470: minrun = compute_minrun(size);
471:
472: /* temporary storage for merges */
473: store = &_store;
474: store->alloc = 0;
475: store->storage = NULL;
476:
477: PUSH_NEXT();
478: PUSH_NEXT();
479: PUSH_NEXT();
480:
481: while (1)
482: {
483: if (!CHECK_INVARIANT(run_stack, stack_curr))
484: {
485: stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
486: continue;
487: }
488: PUSH_NEXT();
489: }
490: }
491:
492: #undef SORT_CONCAT
493: #undef SORT_MAKE_STR1
494: #undef SORT_MAKE_STR
495: #undef SORT_NAME
496: #undef SORT_TYPE
497: #undef SORT_CMP
498: #undef TEMP_STORAGE_T
499: #undef TIM_SORT_RUN_T
500: #undef PUSH_NEXT
501: #undef SORT_SWAP
502: #undef SORT_CONCAT
503: #undef SORT_MAKE_STR1
504: #undef SORT_MAKE_STR
505: #undef BINARY_INSERTION_FIND
506: #undef BINARY_INSERTION_SORT_START
507: #undef BINARY_INSERTION_SORT
508: #undef REVERSE_ELEMENTS
509: #undef COUNT_RUN
510: #undef TIM_SORT
511: #undef TIM_SORT_RESIZE
512: #undef TIM_SORT_COLLAPSE
513: #undef TIM_SORT_RUN_T
514: #undef TEMP_STORAGE_T
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to timsort.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / libxml2