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.
9 * The MIT License (MIT)
11 * Copyright (c) 2010-2017 Christopher Swenson.
12 * Copyright (c) 2012 Vojtech Fried.
13 * Copyright (c) 2012 Google Inc. All Rights Reserved.
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:
22 * The above copyright notice and this permission notice shall be included in
23 * all copies or substantial portions of the Software.
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.
40 typedef unsigned __int64 uint64_t;
44 #error "Must declare SORT_NAME"
48 #error "Must declare SORT_TYPE"
52 #define SORT_CMP(x, y) ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))
55 #ifndef TIM_SORT_STACK_SIZE
56 #define TIM_SORT_STACK_SIZE 128
59 #define SORT_SWAP(x,y) {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;}
62 /* Common, type-agnosting functions and constants that we don't want to declare twice. */
67 #define MAX(x,y) (((x) > (y) ? (x) : (y)))
71 #define MIN(x,y) (((x) < (y) ? (x) : (y)))
74 static int compute_minrun(const uint64_t);
78 #define CLZ __builtin_clzll
81 static int clzll(uint64_t);
83 /* adapted from Hacker's Delight */
84 static int clzll(uint64_t x) {
93 if (x <= 0x00000000FFFFFFFFL) {
98 if (x <= 0x0000FFFFFFFFFFFFL) {
103 if (x <= 0x00FFFFFFFFFFFFFFL) {
108 if (x <= 0x0FFFFFFFFFFFFFFFL) {
113 if (x <= 0x3FFFFFFFFFFFFFFFL) {
118 if (x <= 0x7FFFFFFFFFFFFFFFL) {
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;
142 #endif /* SORT_COMMON_H */
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)
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)
160 #define MAX(x,y) (((x) > (y) ? (x) : (y)))
163 #define MIN(x,y) (((x) < (y) ? (x) : (y)))
172 void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size);
173 void TIM_SORT(SORT_TYPE *dst, const size_t size);
176 /* Function used to do a binary search for binary insertion sort */
177 static __inline size_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x,
185 /* check for out of bounds at the beginning. */
186 if (SORT_CMP(x, dst[0]) < 0) {
188 } else if (SORT_CMP(x, dst[r]) > 0) {
195 const int val = SORT_CMP(x, cx);
203 } else { /* allow = for stability. The binary search favors the right. */
211 c = l + ((r - l) >> 1);
216 /* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
217 static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size) {
220 for (i = start; i < size; i++) {
225 /* If this entry is already correct, just move along */
226 if (SORT_CMP(dst[i - 1], dst[i]) <= 0) {
230 /* Else we need to find the right place, shift everything over, and squeeze in */
232 location = BINARY_INSERTION_FIND(dst, x, i);
234 for (j = i - 1; j >= location; j--) {
237 if (j == 0) { /* check edge case because j is unsigned */
246 /* Binary insertion sort */
247 void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size) {
248 /* don't bother sorting an array of size <= 1 */
253 BINARY_INSERTION_SORT_START(dst, 1, size);
256 /* timsort implementation, based on timsort.txt */
258 static __inline void REVERSE_ELEMENTS(SORT_TYPE *dst, size_t start, size_t end) {
264 SORT_SWAP(dst[start], dst[end]);
270 static size_t COUNT_RUN(SORT_TYPE *dst, const size_t start, const size_t size) {
273 if (size - start == 1) {
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]);
287 if (SORT_CMP(dst[start], dst[start + 1]) <= 0) {
290 if (curr == size - 1) {
294 if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) {
305 if (curr == size - 1) {
309 if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) {
316 /* reverse in-place */
317 REVERSE_ELEMENTS(dst, start, curr - 1);
322 static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr) {
325 if (stack_curr < 2) {
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;
340 A = stack[stack_curr - 3].length;
341 B = stack[stack_curr - 2].length;
342 C = stack[stack_curr - 1].length;
344 if ((A <= B + C) || (B <= C)) {
356 static 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));
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));
366 store->storage = tempstore;
367 store->alloc = new_size;
371 static 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;
378 TIM_SORT_RESIZE(store, MIN(A, B));
379 storage = store->storage;
383 memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE));
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++];
395 dst[k] = storage[i++];
402 memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE));
408 if ((i > 0) && (j > curr)) {
409 if (SORT_CMP(dst[j - 1], storage[i - 1]) > 0) {
412 dst[k] = storage[--i];
415 dst[k] = storage[--i];
423 static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr,
424 TEMP_STORAGE_T *store, const size_t size) {
429 /* if the stack only has one thing on it, we are done with the collapse */
430 if (stack_curr <= 1) {
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;
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;
447 } else if (stack_curr == 2) {
451 B = stack[stack_curr - 3].length;
452 C = stack[stack_curr - 2].length;
453 D = stack[stack_curr - 1].length;
455 if (stack_curr >= 4) {
456 A = stack[stack_curr - 4].length;
462 BCD = (B <= C + D) || ABC;
465 /* Both invariants are good */
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];
478 TIM_SORT_MERGE(dst, stack, stack_curr, store);
479 stack[stack_curr - 2].length += stack[stack_curr - 1].length;
487 static __inline int PUSH_NEXT(SORT_TYPE *dst,
489 TEMP_STORAGE_T *store,
491 TIM_SORT_RUN_T *run_stack,
494 size_t len = COUNT_RUN(dst, *curr, size);
497 if (run > size - *curr) {
502 BINARY_INSERTION_SORT_START(&dst[*curr], len, run);
506 run_stack[*stack_curr].start = *curr;
507 run_stack[*stack_curr].length = len;
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;
519 if (store->storage != NULL) {
520 free(store->storage);
521 store->storage = NULL;
530 void TIM_SORT(SORT_TYPE *dst, const size_t size) {
532 TEMP_STORAGE_T _store, *store;
533 TIM_SORT_RUN_T run_stack[TIM_SORT_STACK_SIZE];
534 size_t stack_curr = 0;
537 /* don't bother sorting an array of size 1 */
543 BINARY_INSERTION_SORT(dst, size);
547 /* compute the minimum run length */
548 minrun = compute_minrun(size);
549 /* temporary storage for merges */
552 store->storage = NULL;
554 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
558 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
562 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
567 if (!CHECK_INVARIANT(run_stack, stack_curr)) {
568 stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size);
572 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
579 #undef SORT_MAKE_STR1
584 #undef TEMP_STORAGE_T
585 #undef TIM_SORT_RUN_T
589 #undef SORT_MAKE_STR1
591 #undef BINARY_INSERTION_FIND
592 #undef BINARY_INSERTION_SORT_START
593 #undef BINARY_INSERTION_SORT
594 #undef REVERSE_ELEMENTS
597 #undef TIM_SORT_RESIZE
598 #undef TIM_SORT_COLLAPSE
599 #undef TIM_SORT_RUN_T
600 #undef TEMP_STORAGE_T