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 */
clzll(uint64_t x)58 int clzll(uint64_t x) /* {{{ */
59 {
60   int n;
61 
62   if (x == 0) return(64);
63   n = 0;
64   if (x <= MK_UINT64(0x00000000FFFFFFFF)) {n = n + 32; x = x << 32;}
65   if (x <= MK_UINT64(0x0000FFFFFFFFFFFF)) {n = n + 16; x = x << 16;}
66   if (x <= MK_UINT64(0x00FFFFFFFFFFFFFF)) {n = n + 8; x = x << 8;}
67   if (x <= MK_UINT64(0x0FFFFFFFFFFFFFFF)) {n = n + 4; x = x << 4;}
68   if (x <= MK_UINT64(0x3FFFFFFFFFFFFFFF)) {n = n + 2; x = x << 2;}
69   if (x <= MK_UINT64(0x7FFFFFFFFFFFFFFF)) {n = n + 1;}
70   return n;
71 }
72 /* }}} */
73 
74 #define CLZ clzll
75 #endif
76 #endif
77 
compute_minrun(uint64_t size)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 */
BINARY_INSERTION_FIND(SORT_TYPE * dst,const SORT_TYPE x,const size_t size)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. */
BINARY_INSERTION_SORT_START(SORT_TYPE * dst,const size_t start,const size_t size)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 */
BINARY_INSERTION_SORT(SORT_TYPE * dst,const size_t size)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 
REVERSE_ELEMENTS(SORT_TYPE * dst,int64_t start,int64_t end)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 
COUNT_RUN(SORT_TYPE * dst,const int64_t start,const size_t size)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 
CHECK_INVARIANT(TIM_SORT_RUN_T * stack,const int stack_curr)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 
TIM_SORT_RESIZE(TEMP_STORAGE_T * store,const size_t new_size)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 
TIM_SORT_MERGE(SORT_TYPE * dst,const TIM_SORT_RUN_T * stack,const int stack_curr,TEMP_STORAGE_T * store)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 
TIM_SORT_COLLAPSE(SORT_TYPE * dst,TIM_SORT_RUN_T * stack,int stack_curr,TEMP_STORAGE_T * store,const size_t size)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     int64_t A, B, C, D;
397     int ABC, BCD, BD, CD;
398 
399     /* if the stack only has one thing on it, we are done with the collapse */
400     if (stack_curr <= 1) {
401       break;
402     }
403 
404     /* if this is the last merge, just do it */
405     if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
406       TIM_SORT_MERGE(dst, stack, stack_curr, store);
407       stack[0].length += stack[1].length;
408       stack_curr--;
409       break;
410     }
411     /* check if the invariant is off for a stack of 2 elements */
412     else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
413       TIM_SORT_MERGE(dst, stack, stack_curr, store);
414       stack[0].length += stack[1].length;
415       stack_curr--;
416       break;
417     } else if (stack_curr == 2) {
418       break;
419     }
420 
421     B = stack[stack_curr - 3].length;
422     C = stack[stack_curr - 2].length;
423     D = stack[stack_curr - 1].length;
424 
425     if (stack_curr >= 4) {
426       A = stack[stack_curr - 4].length;
427       ABC = (A <= B + C);
428     } else {
429       ABC = 0;
430     }
431 
432     BCD = (B <= C + D) || ABC;
433     CD = (C <= D);
434     BD = (B < D);
435 
436     /* Both invariants are good */
437     if (!BCD && !CD) {
438       break;
439     }
440 
441     /* left merge */
442     if (BCD && !CD) {
443       TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
444       stack[stack_curr - 3].length += stack[stack_curr - 2].length;
445       stack[stack_curr - 2] = stack[stack_curr - 1];
446       stack_curr--;
447     } else {
448       /* right merge */
449       TIM_SORT_MERGE(dst, stack, stack_curr, store);
450       stack[stack_curr - 2].length += stack[stack_curr - 1].length;
451       stack_curr--;
452     }
453   }
454 
455   return stack_curr;
456 }
457 
TIM_SORT(SORT_TYPE * dst,const size_t size)458 void TIM_SORT(SORT_TYPE *dst, const size_t size)
459 {
460   int minrun;
461   TEMP_STORAGE_T _store, *store;
462   TIM_SORT_RUN_T run_stack[128];
463   int stack_curr = 0;
464   int64_t len, run;
465   int64_t curr = 0;
466 
467   if (size < 64)
468   {
469     BINARY_INSERTION_SORT(dst, size);
470     return;
471   }
472 
473   /* compute the minimum run length */
474   minrun = compute_minrun(size);
475 
476   /* temporary storage for merges */
477   store = &_store;
478   store->alloc = 0;
479   store->storage = NULL;
480 
481   PUSH_NEXT();
482   PUSH_NEXT();
483   PUSH_NEXT();
484 
485   while (1)
486   {
487     if (!CHECK_INVARIANT(run_stack, stack_curr))
488     {
489       stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
490       continue;
491     }
492     PUSH_NEXT();
493   }
494 }
495 
496 #undef SORT_CONCAT
497 #undef SORT_MAKE_STR1
498 #undef SORT_MAKE_STR
499 #undef SORT_NAME
500 #undef SORT_TYPE
501 #undef SORT_CMP
502 #undef TEMP_STORAGE_T
503 #undef TIM_SORT_RUN_T
504 #undef PUSH_NEXT
505 #undef SORT_SWAP
506 #undef SORT_CONCAT
507 #undef SORT_MAKE_STR1
508 #undef SORT_MAKE_STR
509 #undef BINARY_INSERTION_FIND
510 #undef BINARY_INSERTION_SORT_START
511 #undef BINARY_INSERTION_SORT
512 #undef REVERSE_ELEMENTS
513 #undef COUNT_RUN
514 #undef TIM_SORT
515 #undef TIM_SORT_RESIZE
516 #undef TIM_SORT_COLLAPSE
517 #undef TIM_SORT_RUN_T
518 #undef TEMP_STORAGE_T
519