1 /*
2 * Taken from https://github.com/swenson/sort
3 * Revision: 05fd77bfec049ce8b7c408c4d3dd2d51ee061a15
4 * Removed all code unrelated to Timsort and made minor adjustments for
5 * cross-platform compatibility.
6 */
7
8 /*
9 * The MIT License (MIT)
10 *
11 * Copyright (c) 2010-2017 Christopher Swenson.
12 * Copyright (c) 2012 Vojtech Fried.
13 * Copyright (c) 2012 Google Inc. All Rights Reserved.
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining a
16 * copy of this software and associated documentation files (the "Software"),
17 * to deal in the Software without restriction, including without limitation
18 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
19 * and/or sell copies of the Software, and to permit persons to whom the
20 * Software is furnished to do so, subject to the following conditions:
21 *
22 * The above copyright notice and this permission notice shall be included in
23 * all copies or substantial portions of the Software.
24 *
25 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
26 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
27 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
28 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
29 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
30 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
31 * DEALINGS IN THE SOFTWARE.
32 */
33
34 #include <stdlib.h>
35 #include <stdio.h>
36 #include <string.h>
37 #ifdef HAVE_STDINT_H
38 #include <stdint.h>
39 #elif defined(_WIN32)
40 typedef unsigned __int64 uint64_t;
41 #endif
42
43 #ifndef SORT_NAME
44 #error "Must declare SORT_NAME"
45 #endif
46
47 #ifndef SORT_TYPE
48 #error "Must declare SORT_TYPE"
49 #endif
50
51 #ifndef SORT_CMP
52 #define SORT_CMP(x, y) ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))
53 #endif
54
55 #ifndef TIM_SORT_STACK_SIZE
56 #define TIM_SORT_STACK_SIZE 128
57 #endif
58
59 #define SORT_SWAP(x,y) {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;}
60
61
62 /* Common, type-agnostic functions and constants that we don't want to declare twice. */
63 #ifndef SORT_COMMON_H
64 #define SORT_COMMON_H
65
66 #ifndef MAX
67 #define MAX(x,y) (((x) > (y) ? (x) : (y)))
68 #endif
69
70 #ifndef MIN
71 #define MIN(x,y) (((x) < (y) ? (x) : (y)))
72 #endif
73
74 static int compute_minrun(const uint64_t);
75
76 #ifndef CLZ
77 #if defined(__GNUC__) && ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__GNUC__ > 3))
78 #define CLZ __builtin_clzll
79 #else
80
81 static int clzll(uint64_t);
82
83 /* adapted from Hacker's Delight */
clzll(uint64_t x)84 static int clzll(uint64_t x) {
85 int n;
86
87 if (x == 0) {
88 return 64;
89 }
90
91 n = 0;
92
93 if (x <= 0x00000000FFFFFFFFL) {
94 n = n + 32;
95 x = x << 32;
96 }
97
98 if (x <= 0x0000FFFFFFFFFFFFL) {
99 n = n + 16;
100 x = x << 16;
101 }
102
103 if (x <= 0x00FFFFFFFFFFFFFFL) {
104 n = n + 8;
105 x = x << 8;
106 }
107
108 if (x <= 0x0FFFFFFFFFFFFFFFL) {
109 n = n + 4;
110 x = x << 4;
111 }
112
113 if (x <= 0x3FFFFFFFFFFFFFFFL) {
114 n = n + 2;
115 x = x << 2;
116 }
117
118 if (x <= 0x7FFFFFFFFFFFFFFFL) {
119 n = n + 1;
120 }
121
122 return n;
123 }
124
125 #define CLZ clzll
126 #endif
127 #endif
128
compute_minrun(const uint64_t size)129 static __inline int compute_minrun(const uint64_t size) {
130 const int top_bit = 64 - CLZ(size);
131 const int shift = MAX(top_bit, 6) - 6;
132 const int minrun = size >> shift;
133 const uint64_t mask = (1ULL << shift) - 1;
134
135 if (mask & size) {
136 return minrun + 1;
137 }
138
139 return minrun;
140 }
141
142 #endif /* SORT_COMMON_H */
143
144 #define SORT_CONCAT(x, y) x ## _ ## y
145 #define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y)
146 #define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x)
147
148 #define BINARY_INSERTION_FIND SORT_MAKE_STR(binary_insertion_find)
149 #define BINARY_INSERTION_SORT_START SORT_MAKE_STR(binary_insertion_sort_start)
150 #define BINARY_INSERTION_SORT SORT_MAKE_STR(binary_insertion_sort)
151 #define REVERSE_ELEMENTS SORT_MAKE_STR(reverse_elements)
152 #define COUNT_RUN SORT_MAKE_STR(count_run)
153 #define CHECK_INVARIANT SORT_MAKE_STR(check_invariant)
154 #define TIM_SORT SORT_MAKE_STR(tim_sort)
155 #define TIM_SORT_RESIZE SORT_MAKE_STR(tim_sort_resize)
156 #define TIM_SORT_MERGE SORT_MAKE_STR(tim_sort_merge)
157 #define TIM_SORT_COLLAPSE SORT_MAKE_STR(tim_sort_collapse)
158
159 #ifndef MAX
160 #define MAX(x,y) (((x) > (y) ? (x) : (y)))
161 #endif
162 #ifndef MIN
163 #define MIN(x,y) (((x) < (y) ? (x) : (y)))
164 #endif
165
166 typedef struct {
167 size_t start;
168 size_t length;
169 } TIM_SORT_RUN_T;
170
171
172 XML_HIDDEN
173 void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size);
174 XML_HIDDEN
175 void TIM_SORT(SORT_TYPE *dst, const size_t size);
176
177
178 /* 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)179 static __inline size_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x,
180 const size_t size) {
181 size_t l, c, r;
182 SORT_TYPE cx;
183 l = 0;
184 r = size - 1;
185 c = r >> 1;
186
187 /* check for out of bounds at the beginning. */
188 if (SORT_CMP(x, dst[0]) < 0) {
189 return 0;
190 } else if (SORT_CMP(x, dst[r]) > 0) {
191 return r;
192 }
193
194 cx = dst[c];
195
196 while (1) {
197 const int val = SORT_CMP(x, cx);
198
199 if (val < 0) {
200 if (c - l <= 1) {
201 return c;
202 }
203
204 r = c;
205 } else { /* allow = for stability. The binary search favors the right. */
206 if (r - c <= 1) {
207 return c + 1;
208 }
209
210 l = c;
211 }
212
213 c = l + ((r - l) >> 1);
214 cx = dst[c];
215 }
216 }
217
218 /* 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)219 static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size) {
220 size_t i;
221
222 for (i = start; i < size; i++) {
223 size_t j;
224 SORT_TYPE x;
225 size_t location;
226
227 /* If this entry is already correct, just move along */
228 if (SORT_CMP(dst[i - 1], dst[i]) <= 0) {
229 continue;
230 }
231
232 /* Else we need to find the right place, shift everything over, and squeeze in */
233 x = dst[i];
234 location = BINARY_INSERTION_FIND(dst, x, i);
235
236 for (j = i - 1; j >= location; j--) {
237 dst[j + 1] = dst[j];
238
239 if (j == 0) { /* check edge case because j is unsigned */
240 break;
241 }
242 }
243
244 dst[location] = x;
245 }
246 }
247
248 /* Binary insertion sort */
BINARY_INSERTION_SORT(SORT_TYPE * dst,const size_t size)249 void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size) {
250 /* don't bother sorting an array of size <= 1 */
251 if (size <= 1) {
252 return;
253 }
254
255 BINARY_INSERTION_SORT_START(dst, 1, size);
256 }
257
258 /* timsort implementation, based on timsort.txt */
259
REVERSE_ELEMENTS(SORT_TYPE * dst,size_t start,size_t end)260 static __inline void REVERSE_ELEMENTS(SORT_TYPE *dst, size_t start, size_t end) {
261 while (1) {
262 if (start >= end) {
263 return;
264 }
265
266 SORT_SWAP(dst[start], dst[end]);
267 start++;
268 end--;
269 }
270 }
271
COUNT_RUN(SORT_TYPE * dst,const size_t start,const size_t size)272 static size_t COUNT_RUN(SORT_TYPE *dst, const size_t start, const size_t size) {
273 size_t curr;
274
275 if (size - start == 1) {
276 return 1;
277 }
278
279 if (start >= size - 2) {
280 if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0) {
281 SORT_SWAP(dst[size - 2], dst[size - 1]);
282 }
283
284 return 2;
285 }
286
287 curr = start + 2;
288
289 if (SORT_CMP(dst[start], dst[start + 1]) <= 0) {
290 /* increasing run */
291 while (1) {
292 if (curr == size - 1) {
293 break;
294 }
295
296 if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) {
297 break;
298 }
299
300 curr++;
301 }
302
303 return curr - start;
304 } else {
305 /* decreasing run */
306 while (1) {
307 if (curr == size - 1) {
308 break;
309 }
310
311 if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) {
312 break;
313 }
314
315 curr++;
316 }
317
318 /* reverse in-place */
319 REVERSE_ELEMENTS(dst, start, curr - 1);
320 return curr - start;
321 }
322 }
323
CHECK_INVARIANT(TIM_SORT_RUN_T * stack,const int stack_curr)324 static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr) {
325 size_t A, B, C;
326
327 if (stack_curr < 2) {
328 return 1;
329 }
330
331 if (stack_curr == 2) {
332 const size_t A1 = stack[stack_curr - 2].length;
333 const size_t B1 = stack[stack_curr - 1].length;
334
335 if (A1 <= B1) {
336 return 0;
337 }
338
339 return 1;
340 }
341
342 A = stack[stack_curr - 3].length;
343 B = stack[stack_curr - 2].length;
344 C = stack[stack_curr - 1].length;
345
346 if ((A <= B + C) || (B <= C)) {
347 return 0;
348 }
349
350 return 1;
351 }
352
353 typedef struct {
354 size_t alloc;
355 SORT_TYPE *storage;
356 } TEMP_STORAGE_T;
357
TIM_SORT_RESIZE(TEMP_STORAGE_T * store,const size_t new_size)358 static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size) {
359 if (store->alloc < new_size) {
360 SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeof(SORT_TYPE));
361
362 if (tempstore == NULL) {
363 fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu bytes",
364 (unsigned long)(sizeof(SORT_TYPE) * new_size));
365 exit(1);
366 }
367
368 store->storage = tempstore;
369 store->alloc = new_size;
370 }
371 }
372
TIM_SORT_MERGE(SORT_TYPE * dst,const TIM_SORT_RUN_T * stack,const int stack_curr,TEMP_STORAGE_T * store)373 static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const int stack_curr,
374 TEMP_STORAGE_T *store) {
375 const size_t A = stack[stack_curr - 2].length;
376 const size_t B = stack[stack_curr - 1].length;
377 const size_t curr = stack[stack_curr - 2].start;
378 SORT_TYPE *storage;
379 size_t i, j, k;
380 TIM_SORT_RESIZE(store, MIN(A, B));
381 storage = store->storage;
382
383 /* left merge */
384 if (A < B) {
385 memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE));
386 i = 0;
387 j = curr + A;
388
389 for (k = curr; k < curr + A + B; k++) {
390 if ((i < A) && (j < curr + A + B)) {
391 if (SORT_CMP(storage[i], dst[j]) <= 0) {
392 dst[k] = storage[i++];
393 } else {
394 dst[k] = dst[j++];
395 }
396 } else if (i < A) {
397 dst[k] = storage[i++];
398 } else {
399 break;
400 }
401 }
402 } else {
403 /* right merge */
404 memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
405 i = B;
406 j = curr + A;
407 k = curr + A + B;
408
409 while (k > curr) {
410 k--;
411 if ((i > 0) && (j > curr)) {
412 if (SORT_CMP(dst[j - 1], storage[i - 1]) > 0) {
413 dst[k] = dst[--j];
414 } else {
415 dst[k] = storage[--i];
416 }
417 } else if (i > 0) {
418 dst[k] = storage[--i];
419 } else {
420 break;
421 }
422 }
423 }
424 }
425
TIM_SORT_COLLAPSE(SORT_TYPE * dst,TIM_SORT_RUN_T * stack,int stack_curr,TEMP_STORAGE_T * store,const size_t size)426 static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr,
427 TEMP_STORAGE_T *store, const size_t size) {
428 while (1) {
429 size_t A, B, C, D;
430 int ABC, BCD, CD;
431
432 /* if the stack only has one thing on it, we are done with the collapse */
433 if (stack_curr <= 1) {
434 break;
435 }
436
437 /* if this is the last merge, just do it */
438 if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
439 TIM_SORT_MERGE(dst, stack, stack_curr, store);
440 stack[0].length += stack[1].length;
441 stack_curr--;
442 break;
443 }
444 /* check if the invariant is off for a stack of 2 elements */
445 else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
446 TIM_SORT_MERGE(dst, stack, stack_curr, store);
447 stack[0].length += stack[1].length;
448 stack_curr--;
449 break;
450 } else if (stack_curr == 2) {
451 break;
452 }
453
454 B = stack[stack_curr - 3].length;
455 C = stack[stack_curr - 2].length;
456 D = stack[stack_curr - 1].length;
457
458 if (stack_curr >= 4) {
459 A = stack[stack_curr - 4].length;
460 ABC = (A <= B + C);
461 } else {
462 ABC = 0;
463 }
464
465 BCD = (B <= C + D) || ABC;
466 CD = (C <= D);
467
468 /* Both invariants are good */
469 if (!BCD && !CD) {
470 break;
471 }
472
473 /* left merge */
474 if (BCD && !CD) {
475 TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
476 stack[stack_curr - 3].length += stack[stack_curr - 2].length;
477 stack[stack_curr - 2] = stack[stack_curr - 1];
478 stack_curr--;
479 } else {
480 /* right merge */
481 TIM_SORT_MERGE(dst, stack, stack_curr, store);
482 stack[stack_curr - 2].length += stack[stack_curr - 1].length;
483 stack_curr--;
484 }
485 }
486
487 return stack_curr;
488 }
489
PUSH_NEXT(SORT_TYPE * dst,const size_t size,TEMP_STORAGE_T * store,const size_t minrun,TIM_SORT_RUN_T * run_stack,size_t * stack_curr,size_t * curr)490 static __inline int PUSH_NEXT(SORT_TYPE *dst,
491 const size_t size,
492 TEMP_STORAGE_T *store,
493 const size_t minrun,
494 TIM_SORT_RUN_T *run_stack,
495 size_t *stack_curr,
496 size_t *curr) {
497 size_t len = COUNT_RUN(dst, *curr, size);
498 size_t run = minrun;
499
500 if (run > size - *curr) {
501 run = size - *curr;
502 }
503
504 if (run > len) {
505 BINARY_INSERTION_SORT_START(&dst[*curr], len, run);
506 len = run;
507 }
508
509 run_stack[*stack_curr].start = *curr;
510 run_stack[*stack_curr].length = len;
511 (*stack_curr)++;
512 *curr += len;
513
514 if (*curr == size) {
515 /* finish up */
516 while (*stack_curr > 1) {
517 TIM_SORT_MERGE(dst, run_stack, *stack_curr, store);
518 run_stack[*stack_curr - 2].length += run_stack[*stack_curr - 1].length;
519 (*stack_curr)--;
520 }
521
522 if (store->storage != NULL) {
523 free(store->storage);
524 store->storage = NULL;
525 }
526
527 return 0;
528 }
529
530 return 1;
531 }
532
TIM_SORT(SORT_TYPE * dst,const size_t size)533 void TIM_SORT(SORT_TYPE *dst, const size_t size) {
534 size_t minrun;
535 TEMP_STORAGE_T _store, *store;
536 TIM_SORT_RUN_T run_stack[TIM_SORT_STACK_SIZE];
537 size_t stack_curr = 0;
538 size_t curr = 0;
539
540 /* don't bother sorting an array of size 1 */
541 if (size <= 1) {
542 return;
543 }
544
545 if (size < 64) {
546 BINARY_INSERTION_SORT(dst, size);
547 return;
548 }
549
550 /* compute the minimum run length */
551 minrun = compute_minrun(size);
552 /* temporary storage for merges */
553 store = &_store;
554 store->alloc = 0;
555 store->storage = NULL;
556
557 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
558 return;
559 }
560
561 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
562 return;
563 }
564
565 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
566 return;
567 }
568
569 while (1) {
570 if (!CHECK_INVARIANT(run_stack, stack_curr)) {
571 stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
572 continue;
573 }
574
575 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
576 return;
577 }
578 }
579 }
580
581 #undef SORT_CONCAT
582 #undef SORT_MAKE_STR1
583 #undef SORT_MAKE_STR
584 #undef SORT_NAME
585 #undef SORT_TYPE
586 #undef SORT_CMP
587 #undef TEMP_STORAGE_T
588 #undef TIM_SORT_RUN_T
589 #undef PUSH_NEXT
590 #undef SORT_SWAP
591 #undef SORT_CONCAT
592 #undef SORT_MAKE_STR1
593 #undef SORT_MAKE_STR
594 #undef BINARY_INSERTION_FIND
595 #undef BINARY_INSERTION_SORT_START
596 #undef BINARY_INSERTION_SORT
597 #undef REVERSE_ELEMENTS
598 #undef COUNT_RUN
599 #undef TIM_SORT
600 #undef TIM_SORT_RESIZE
601 #undef TIM_SORT_COLLAPSE
602 #undef TIM_SORT_RUN_T
603 #undef TEMP_STORAGE_T
604