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)
40typedef 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-agnosting 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
74static int compute_minrun(const uint64_t);
75
76#ifndef CLZ
77#ifdef __GNUC__
78#define CLZ __builtin_clzll
79#else
80
81static int clzll(uint64_t);
82
83/* adapted from Hacker's Delight */
84static 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
129static __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
166typedef struct {
167 size_t start;
168 size_t length;
169} TIM_SORT_RUN_T;
170
171
172void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size);
173void TIM_SORT(SORT_TYPE *dst, const size_t size);
174
175
176/* Function used to do a binary search for binary insertion sort */
177static __inline size_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x,
178 const size_t size) {
179 size_t l, c, r;
180 SORT_TYPE cx;
181 l = 0;
182 r = size - 1;
183 c = r >> 1;
184
185 /* check for out of bounds at the beginning. */
186 if (SORT_CMP(x, dst[0]) < 0) {
187 return 0;
188 } else if (SORT_CMP(x, dst[r]) > 0) {
189 return r;
190 }
191
192 cx = dst[c];
193
194 while (1) {
195 const int val = SORT_CMP(x, cx);
196
197 if (val < 0) {
198 if (c - l <= 1) {
199 return c;
200 }
201
202 r = c;
203 } else { /* allow = for stability. The binary search favors the right. */
204 if (r - c <= 1) {
205 return c + 1;
206 }
207
208 l = c;
209 }
210
211 c = l + ((r - l) >> 1);
212 cx = dst[c];
213 }
214}
215
216/* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
217static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size) {
218 size_t i;
219
220 for (i = start; i < size; i++) {
221 size_t j;
222 SORT_TYPE x;
223 size_t location;
224
225 /* If this entry is already correct, just move along */
226 if (SORT_CMP(dst[i - 1], dst[i]) <= 0) {
227 continue;
228 }
229
230 /* Else we need to find the right place, shift everything over, and squeeze in */
231 x = dst[i];
232 location = BINARY_INSERTION_FIND(dst, x, i);
233
234 for (j = i - 1; j >= location; j--) {
235 dst[j + 1] = dst[j];
236
237 if (j == 0) { /* check edge case because j is unsigned */
238 break;
239 }
240 }
241
242 dst[location] = x;
243 }
244}
245
246/* Binary insertion sort */
247void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size) {
248 /* don't bother sorting an array of size <= 1 */
249 if (size <= 1) {
250 return;
251 }
252
253 BINARY_INSERTION_SORT_START(dst, 1, size);
254}
255
256/* timsort implementation, based on timsort.txt */
257
258static __inline void REVERSE_ELEMENTS(SORT_TYPE *dst, size_t start, size_t end) {
259 while (1) {
260 if (start >= end) {
261 return;
262 }
263
264 SORT_SWAP(dst[start], dst[end]);
265 start++;
266 end--;
267 }
268}
269
270static size_t COUNT_RUN(SORT_TYPE *dst, const size_t start, const size_t size) {
271 size_t curr;
272
273 if (size - start == 1) {
274 return 1;
275 }
276
277 if (start >= size - 2) {
278 if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0) {
279 SORT_SWAP(dst[size - 2], dst[size - 1]);
280 }
281
282 return 2;
283 }
284
285 curr = start + 2;
286
287 if (SORT_CMP(dst[start], dst[start + 1]) <= 0) {
288 /* increasing run */
289 while (1) {
290 if (curr == size - 1) {
291 break;
292 }
293
294 if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) {
295 break;
296 }
297
298 curr++;
299 }
300
301 return curr - start;
302 } else {
303 /* decreasing run */
304 while (1) {
305 if (curr == size - 1) {
306 break;
307 }
308
309 if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) {
310 break;
311 }
312
313 curr++;
314 }
315
316 /* reverse in-place */
317 REVERSE_ELEMENTS(dst, start, curr - 1);
318 return curr - start;
319 }
320}
321
322static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr) {
323 size_t A, B, C;
324
325 if (stack_curr < 2) {
326 return 1;
327 }
328
329 if (stack_curr == 2) {
330 const size_t A1 = stack[stack_curr - 2].length;
331 const size_t B1 = stack[stack_curr - 1].length;
332
333 if (A1 <= B1) {
334 return 0;
335 }
336
337 return 1;
338 }
339
340 A = stack[stack_curr - 3].length;
341 B = stack[stack_curr - 2].length;
342 C = stack[stack_curr - 1].length;
343
344 if ((A <= B + C) || (B <= C)) {
345 return 0;
346 }
347
348 return 1;
349}
350
351typedef struct {
352 size_t alloc;
353 SORT_TYPE *storage;
354} TEMP_STORAGE_T;
355
356static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size) {
357 if (store->alloc < new_size) {
358 SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeof(SORT_TYPE));
359
360 if (tempstore == NULL) {
361 fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu bytes",
362 (unsigned long)(sizeof(SORT_TYPE) * new_size));
363 exit(1);
364 }
365
366 store->storage = tempstore;
367 store->alloc = new_size;
368 }
369}
370
371static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const int stack_curr,
372 TEMP_STORAGE_T *store) {
373 const size_t A = stack[stack_curr - 2].length;
374 const size_t B = stack[stack_curr - 1].length;
375 const size_t curr = stack[stack_curr - 2].start;
376 SORT_TYPE *storage;
377 size_t i, j, k;
378 TIM_SORT_RESIZE(store, MIN(A, B));
379 storage = store->storage;
380
381 /* left merge */
382 if (A < B) {
383 memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE));
384 i = 0;
385 j = curr + A;
386
387 for (k = curr; k < curr + A + B; k++) {
388 if ((i < A) && (j < curr + A + B)) {
389 if (SORT_CMP(storage[i], dst[j]) <= 0) {
390 dst[k] = storage[i++];
391 } else {
392 dst[k] = dst[j++];
393 }
394 } else if (i < A) {
395 dst[k] = storage[i++];
396 } else {
397 break;
398 }
399 }
400 } else {
401 /* right merge */
402 memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
403 i = B;
404 j = curr + A;
405 k = curr + A + B;
406
407 while (k-- > curr) {
408 if ((i > 0) && (j > curr)) {
409 if (SORT_CMP(dst[j - 1], storage[i - 1]) > 0) {
410 dst[k] = dst[--j];
411 } else {
412 dst[k] = storage[--i];
413 }
414 } else if (i > 0) {
415 dst[k] = storage[--i];
416 } else {
417 break;
418 }
419 }
420 }
421}
422
423static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr,
424 TEMP_STORAGE_T *store, const size_t size) {
425 while (1) {
426 size_t A, B, C, D;
427 int ABC, BCD, CD;
428
429 /* if the stack only has one thing on it, we are done with the collapse */
430 if (stack_curr <= 1) {
431 break;
432 }
433
434 /* if this is the last merge, just do it */
435 if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
436 TIM_SORT_MERGE(dst, stack, stack_curr, store);
437 stack[0].length += stack[1].length;
438 stack_curr--;
439 break;
440 }
441 /* check if the invariant is off for a stack of 2 elements */
442 else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
443 TIM_SORT_MERGE(dst, stack, stack_curr, store);
444 stack[0].length += stack[1].length;
445 stack_curr--;
446 break;
447 } else if (stack_curr == 2) {
448 break;
449 }
450
451 B = stack[stack_curr - 3].length;
452 C = stack[stack_curr - 2].length;
453 D = stack[stack_curr - 1].length;
454
455 if (stack_curr >= 4) {
456 A = stack[stack_curr - 4].length;
457 ABC = (A <= B + C);
458 } else {
459 ABC = 0;
460 }
461
462 BCD = (B <= C + D) || ABC;
463 CD = (C <= D);
464
465 /* Both invariants are good */
466 if (!BCD && !CD) {
467 break;
468 }
469
470 /* left merge */
471 if (BCD && !CD) {
472 TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
473 stack[stack_curr - 3].length += stack[stack_curr - 2].length;
474 stack[stack_curr - 2] = stack[stack_curr - 1];
475 stack_curr--;
476 } else {
477 /* right merge */
478 TIM_SORT_MERGE(dst, stack, stack_curr, store);
479 stack[stack_curr - 2].length += stack[stack_curr - 1].length;
480 stack_curr--;
481 }
482 }
483
484 return stack_curr;
485}
486
487static __inline int PUSH_NEXT(SORT_TYPE *dst,
488 const size_t size,
489 TEMP_STORAGE_T *store,
490 const size_t minrun,
491 TIM_SORT_RUN_T *run_stack,
492 size_t *stack_curr,
493 size_t *curr) {
494 size_t len = COUNT_RUN(dst, *curr, size);
495 size_t run = minrun;
496
497 if (run > size - *curr) {
498 run = size - *curr;
499 }
500
501 if (run > len) {
502 BINARY_INSERTION_SORT_START(&dst[*curr], len, run);
503 len = run;
504 }
505
506 run_stack[*stack_curr].start = *curr;
507 run_stack[*stack_curr].length = len;
508 (*stack_curr)++;
509 *curr += len;
510
511 if (*curr == size) {
512 /* finish up */
513 while (*stack_curr > 1) {
514 TIM_SORT_MERGE(dst, run_stack, *stack_curr, store);
515 run_stack[*stack_curr - 2].length += run_stack[*stack_curr - 1].length;
516 (*stack_curr)--;
517 }
518
519 if (store->storage != NULL) {
520 free(store->storage);
521 store->storage = NULL;
522 }
523
524 return 0;
525 }
526
527 return 1;
528}
529
530void TIM_SORT(SORT_TYPE *dst, const size_t size) {
531 size_t minrun;
532 TEMP_STORAGE_T _store, *store;
533 TIM_SORT_RUN_T run_stack[TIM_SORT_STACK_SIZE];
534 size_t stack_curr = 0;
535 size_t curr = 0;
536
537 /* don't bother sorting an array of size 1 */
538 if (size <= 1) {
539 return;
540 }
541
542 if (size < 64) {
543 BINARY_INSERTION_SORT(dst, size);
544 return;
545 }
546
547 /* compute the minimum run length */
548 minrun = compute_minrun(size);
549 /* temporary storage for merges */
550 store = &_store;
551 store->alloc = 0;
552 store->storage = NULL;
553
554 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
555 return;
556 }
557
558 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
559 return;
560 }
561
562 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
563 return;
564 }
565
566 while (1) {
567 if (!CHECK_INVARIANT(run_stack, stack_curr)) {
568 stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
569 continue;
570 }
571
572 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
573 return;
574 }
575 }
576}
577
578#undef SORT_CONCAT
579#undef SORT_MAKE_STR1
580#undef SORT_MAKE_STR
581#undef SORT_NAME
582#undef SORT_TYPE
583#undef SORT_CMP
584#undef TEMP_STORAGE_T
585#undef TIM_SORT_RUN_T
586#undef PUSH_NEXT
587#undef SORT_SWAP
588#undef SORT_CONCAT
589#undef SORT_MAKE_STR1
590#undef SORT_MAKE_STR
591#undef BINARY_INSERTION_FIND
592#undef BINARY_INSERTION_SORT_START
593#undef BINARY_INSERTION_SORT
594#undef REVERSE_ELEMENTS
595#undef COUNT_RUN
596#undef TIM_SORT
597#undef TIM_SORT_RESIZE
598#undef TIM_SORT_COLLAPSE
599#undef TIM_SORT_RUN_T
600#undef TEMP_STORAGE_T
601