| /* |
| * Taken from https://github.com/swenson/sort |
| * Revision: 05fd77bfec049ce8b7c408c4d3dd2d51ee061a15 |
| * Removed all code unrelated to Timsort and made minor adjustments for |
| * cross-platform compatibility. |
| */ |
| |
| /* |
| * The MIT License (MIT) |
| * |
| * Copyright (c) 2010-2017 Christopher Swenson. |
| * Copyright (c) 2012 Vojtech Fried. |
| * Copyright (c) 2012 Google Inc. All Rights Reserved. |
| * |
| * 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: |
| * |
| * The above copyright notice and this permission notice shall be included in |
| * all copies or substantial portions of the Software. |
| * |
| * 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. |
| */ |
| |
| #include <stdlib.h> |
| #include <stdio.h> |
| #include <string.h> |
| #ifdef HAVE_STDINT_H |
| #include <stdint.h> |
| #elif defined(_WIN32) |
| typedef unsigned __int64 uint64_t; |
| #endif |
| |
| #ifndef SORT_NAME |
| #error "Must declare SORT_NAME" |
| #endif |
| |
| #ifndef SORT_TYPE |
| #error "Must declare SORT_TYPE" |
| #endif |
| |
| #ifndef SORT_CMP |
| #define SORT_CMP(x, y) ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1)) |
| #endif |
| |
| #ifndef TIM_SORT_STACK_SIZE |
| #define TIM_SORT_STACK_SIZE 128 |
| #endif |
| |
| #define SORT_SWAP(x,y) {SORT_TYPE __SORT_SWAP_t = (x); (x) = (y); (y) = __SORT_SWAP_t;} |
| |
| |
| /* Common, type-agnostic functions and constants that we don't want to declare twice. */ |
| #ifndef SORT_COMMON_H |
| #define SORT_COMMON_H |
| |
| #ifndef MAX |
| #define MAX(x,y) (((x) > (y) ? (x) : (y))) |
| #endif |
| |
| #ifndef MIN |
| #define MIN(x,y) (((x) < (y) ? (x) : (y))) |
| #endif |
| |
| static int compute_minrun(const uint64_t); |
| |
| #ifndef CLZ |
| #if defined(__GNUC__) && ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__GNUC__ > 3)) |
| #define CLZ __builtin_clzll |
| #else |
| |
| static int clzll(uint64_t); |
| |
| /* adapted from Hacker's Delight */ |
| static int clzll(uint64_t x) { |
| int n; |
| |
| if (x == 0) { |
| return 64; |
| } |
| |
| n = 0; |
| |
| if (x <= 0x00000000FFFFFFFFL) { |
| n = n + 32; |
| x = x << 32; |
| } |
| |
| if (x <= 0x0000FFFFFFFFFFFFL) { |
| n = n + 16; |
| x = x << 16; |
| } |
| |
| if (x <= 0x00FFFFFFFFFFFFFFL) { |
| n = n + 8; |
| x = x << 8; |
| } |
| |
| if (x <= 0x0FFFFFFFFFFFFFFFL) { |
| n = n + 4; |
| x = x << 4; |
| } |
| |
| if (x <= 0x3FFFFFFFFFFFFFFFL) { |
| n = n + 2; |
| x = x << 2; |
| } |
| |
| if (x <= 0x7FFFFFFFFFFFFFFFL) { |
| n = n + 1; |
| } |
| |
| return n; |
| } |
| |
| #define CLZ clzll |
| #endif |
| #endif |
| |
| static __inline int compute_minrun(const uint64_t size) { |
| const int top_bit = 64 - CLZ(size); |
| const int shift = MAX(top_bit, 6) - 6; |
| const int minrun = size >> shift; |
| const uint64_t mask = (1ULL << shift) - 1; |
| |
| if (mask & size) { |
| return minrun + 1; |
| } |
| |
| return minrun; |
| } |
| |
| #endif /* SORT_COMMON_H */ |
| |
| #define SORT_CONCAT(x, y) x ## _ ## y |
| #define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y) |
| #define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x) |
| |
| #define BINARY_INSERTION_FIND SORT_MAKE_STR(binary_insertion_find) |
| #define BINARY_INSERTION_SORT_START SORT_MAKE_STR(binary_insertion_sort_start) |
| #define BINARY_INSERTION_SORT SORT_MAKE_STR(binary_insertion_sort) |
| #define REVERSE_ELEMENTS SORT_MAKE_STR(reverse_elements) |
| #define COUNT_RUN SORT_MAKE_STR(count_run) |
| #define CHECK_INVARIANT SORT_MAKE_STR(check_invariant) |
| #define TIM_SORT SORT_MAKE_STR(tim_sort) |
| #define TIM_SORT_RESIZE SORT_MAKE_STR(tim_sort_resize) |
| #define TIM_SORT_MERGE SORT_MAKE_STR(tim_sort_merge) |
| #define TIM_SORT_COLLAPSE SORT_MAKE_STR(tim_sort_collapse) |
| |
| #ifndef MAX |
| #define MAX(x,y) (((x) > (y) ? (x) : (y))) |
| #endif |
| #ifndef MIN |
| #define MIN(x,y) (((x) < (y) ? (x) : (y))) |
| #endif |
| |
| typedef struct { |
| size_t start; |
| size_t length; |
| } TIM_SORT_RUN_T; |
| |
| |
| void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size); |
| void TIM_SORT(SORT_TYPE *dst, const size_t size); |
| |
| |
| /* Function used to do a binary search for binary insertion sort */ |
| static __inline size_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x, |
| const size_t size) { |
| size_t l, c, r; |
| SORT_TYPE cx; |
| l = 0; |
| r = size - 1; |
| c = r >> 1; |
| |
| /* check for out of bounds at the beginning. */ |
| if (SORT_CMP(x, dst[0]) < 0) { |
| return 0; |
| } else if (SORT_CMP(x, dst[r]) > 0) { |
| return r; |
| } |
| |
| cx = dst[c]; |
| |
| while (1) { |
| const int val = SORT_CMP(x, cx); |
| |
| if (val < 0) { |
| if (c - l <= 1) { |
| return c; |
| } |
| |
| r = c; |
| } else { /* allow = for stability. The binary search favors the right. */ |
| if (r - c <= 1) { |
| return c + 1; |
| } |
| |
| l = c; |
| } |
| |
| c = l + ((r - l) >> 1); |
| cx = dst[c]; |
| } |
| } |
| |
| /* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */ |
| static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size) { |
| size_t i; |
| |
| for (i = start; i < size; i++) { |
| size_t j; |
| SORT_TYPE x; |
| size_t location; |
| |
| /* If this entry is already correct, just move along */ |
| if (SORT_CMP(dst[i - 1], dst[i]) <= 0) { |
| continue; |
| } |
| |
| /* Else we need to find the right place, shift everything over, and squeeze in */ |
| x = dst[i]; |
| location = BINARY_INSERTION_FIND(dst, x, i); |
| |
| for (j = i - 1; j >= location; j--) { |
| dst[j + 1] = dst[j]; |
| |
| if (j == 0) { /* check edge case because j is unsigned */ |
| break; |
| } |
| } |
| |
| dst[location] = x; |
| } |
| } |
| |
| /* Binary insertion sort */ |
| void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size) { |
| /* don't bother sorting an array of size <= 1 */ |
| if (size <= 1) { |
| return; |
| } |
| |
| BINARY_INSERTION_SORT_START(dst, 1, size); |
| } |
| |
| /* timsort implementation, based on timsort.txt */ |
| |
| static __inline void REVERSE_ELEMENTS(SORT_TYPE *dst, size_t start, size_t end) { |
| while (1) { |
| if (start >= end) { |
| return; |
| } |
| |
| SORT_SWAP(dst[start], dst[end]); |
| start++; |
| end--; |
| } |
| } |
| |
| static size_t COUNT_RUN(SORT_TYPE *dst, const size_t start, const size_t size) { |
| size_t curr; |
| |
| if (size - start == 1) { |
| return 1; |
| } |
| |
| if (start >= size - 2) { |
| if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0) { |
| SORT_SWAP(dst[size - 2], dst[size - 1]); |
| } |
| |
| return 2; |
| } |
| |
| curr = start + 2; |
| |
| if (SORT_CMP(dst[start], dst[start + 1]) <= 0) { |
| /* increasing run */ |
| while (1) { |
| if (curr == size - 1) { |
| break; |
| } |
| |
| if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) { |
| break; |
| } |
| |
| curr++; |
| } |
| |
| return curr - start; |
| } else { |
| /* decreasing run */ |
| while (1) { |
| if (curr == size - 1) { |
| break; |
| } |
| |
| if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) { |
| break; |
| } |
| |
| curr++; |
| } |
| |
| /* reverse in-place */ |
| REVERSE_ELEMENTS(dst, start, curr - 1); |
| return curr - start; |
| } |
| } |
| |
| static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr) { |
| size_t A, B, C; |
| |
| if (stack_curr < 2) { |
| return 1; |
| } |
| |
| if (stack_curr == 2) { |
| const size_t A1 = stack[stack_curr - 2].length; |
| const size_t B1 = stack[stack_curr - 1].length; |
| |
| if (A1 <= B1) { |
| return 0; |
| } |
| |
| return 1; |
| } |
| |
| A = stack[stack_curr - 3].length; |
| B = stack[stack_curr - 2].length; |
| C = stack[stack_curr - 1].length; |
| |
| if ((A <= B + C) || (B <= C)) { |
| return 0; |
| } |
| |
| return 1; |
| } |
| |
| typedef struct { |
| size_t alloc; |
| SORT_TYPE *storage; |
| } TEMP_STORAGE_T; |
| |
| static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size) { |
| if (store->alloc < new_size) { |
| SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeof(SORT_TYPE)); |
| |
| if (tempstore == NULL) { |
| fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu bytes", |
| (unsigned long)(sizeof(SORT_TYPE) * new_size)); |
| exit(1); |
| } |
| |
| store->storage = tempstore; |
| store->alloc = new_size; |
| } |
| } |
| |
| static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const int stack_curr, |
| TEMP_STORAGE_T *store) { |
| const size_t A = stack[stack_curr - 2].length; |
| const size_t B = stack[stack_curr - 1].length; |
| const size_t curr = stack[stack_curr - 2].start; |
| SORT_TYPE *storage; |
| size_t i, j, k; |
| TIM_SORT_RESIZE(store, MIN(A, B)); |
| storage = store->storage; |
| |
| /* left merge */ |
| if (A < B) { |
| memcpy(storage, &dst[curr], A * sizeof(SORT_TYPE)); |
| i = 0; |
| j = curr + A; |
| |
| for (k = curr; k < curr + A + B; k++) { |
| if ((i < A) && (j < curr + A + B)) { |
| if (SORT_CMP(storage[i], dst[j]) <= 0) { |
| dst[k] = storage[i++]; |
| } else { |
| dst[k] = dst[j++]; |
| } |
| } else if (i < A) { |
| dst[k] = storage[i++]; |
| } else { |
| break; |
| } |
| } |
| } else { |
| /* right merge */ |
| memcpy(storage, &dst[curr + A], B * sizeof(SORT_TYPE)); |
| i = B; |
| j = curr + A; |
| k = curr + A + B; |
| |
| while (k > curr) { |
| k--; |
| if ((i > 0) && (j > curr)) { |
| if (SORT_CMP(dst[j - 1], storage[i - 1]) > 0) { |
| dst[k] = dst[--j]; |
| } else { |
| dst[k] = storage[--i]; |
| } |
| } else if (i > 0) { |
| dst[k] = storage[--i]; |
| } else { |
| break; |
| } |
| } |
| } |
| } |
| |
| static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr, |
| TEMP_STORAGE_T *store, const size_t size) { |
| while (1) { |
| size_t A, B, C, D; |
| int ABC, BCD, CD; |
| |
| /* if the stack only has one thing on it, we are done with the collapse */ |
| if (stack_curr <= 1) { |
| break; |
| } |
| |
| /* if this is the last merge, just do it */ |
| if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) { |
| TIM_SORT_MERGE(dst, stack, stack_curr, store); |
| stack[0].length += stack[1].length; |
| stack_curr--; |
| break; |
| } |
| /* check if the invariant is off for a stack of 2 elements */ |
| else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) { |
| TIM_SORT_MERGE(dst, stack, stack_curr, store); |
| stack[0].length += stack[1].length; |
| stack_curr--; |
| break; |
| } else if (stack_curr == 2) { |
| break; |
| } |
| |
| B = stack[stack_curr - 3].length; |
| C = stack[stack_curr - 2].length; |
| D = stack[stack_curr - 1].length; |
| |
| if (stack_curr >= 4) { |
| A = stack[stack_curr - 4].length; |
| ABC = (A <= B + C); |
| } else { |
| ABC = 0; |
| } |
| |
| BCD = (B <= C + D) || ABC; |
| CD = (C <= D); |
| |
| /* Both invariants are good */ |
| if (!BCD && !CD) { |
| break; |
| } |
| |
| /* left merge */ |
| if (BCD && !CD) { |
| TIM_SORT_MERGE(dst, stack, stack_curr - 1, store); |
| stack[stack_curr - 3].length += stack[stack_curr - 2].length; |
| stack[stack_curr - 2] = stack[stack_curr - 1]; |
| stack_curr--; |
| } else { |
| /* right merge */ |
| TIM_SORT_MERGE(dst, stack, stack_curr, store); |
| stack[stack_curr - 2].length += stack[stack_curr - 1].length; |
| stack_curr--; |
| } |
| } |
| |
| return stack_curr; |
| } |
| |
| static __inline int 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) { |
| size_t len = COUNT_RUN(dst, *curr, size); |
| size_t run = minrun; |
| |
| if (run > size - *curr) { |
| run = size - *curr; |
| } |
| |
| if (run > len) { |
| BINARY_INSERTION_SORT_START(&dst[*curr], len, run); |
| len = run; |
| } |
| |
| run_stack[*stack_curr].start = *curr; |
| run_stack[*stack_curr].length = len; |
| (*stack_curr)++; |
| *curr += len; |
| |
| if (*curr == size) { |
| /* finish up */ |
| while (*stack_curr > 1) { |
| TIM_SORT_MERGE(dst, run_stack, *stack_curr, store); |
| run_stack[*stack_curr - 2].length += run_stack[*stack_curr - 1].length; |
| (*stack_curr)--; |
| } |
| |
| if (store->storage != NULL) { |
| free(store->storage); |
| store->storage = NULL; |
| } |
| |
| return 0; |
| } |
| |
| return 1; |
| } |
| |
| void TIM_SORT(SORT_TYPE *dst, const size_t size) { |
| size_t minrun; |
| TEMP_STORAGE_T _store, *store; |
| TIM_SORT_RUN_T run_stack[TIM_SORT_STACK_SIZE]; |
| size_t stack_curr = 0; |
| size_t curr = 0; |
| |
| /* don't bother sorting an array of size 1 */ |
| if (size <= 1) { |
| return; |
| } |
| |
| if (size < 64) { |
| BINARY_INSERTION_SORT(dst, size); |
| return; |
| } |
| |
| /* compute the minimum run length */ |
| minrun = compute_minrun(size); |
| /* temporary storage for merges */ |
| store = &_store; |
| store->alloc = 0; |
| store->storage = NULL; |
| |
| if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) { |
| return; |
| } |
| |
| if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) { |
| return; |
| } |
| |
| if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) { |
| return; |
| } |
| |
| while (1) { |
| if (!CHECK_INVARIANT(run_stack, stack_curr)) { |
| stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, stack_curr, store, size); |
| continue; |
| } |
| |
| if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) { |
| return; |
| } |
| } |
| } |
| |
| #undef SORT_CONCAT |
| #undef SORT_MAKE_STR1 |
| #undef SORT_MAKE_STR |
| #undef SORT_NAME |
| #undef SORT_TYPE |
| #undef SORT_CMP |
| #undef TEMP_STORAGE_T |
| #undef TIM_SORT_RUN_T |
| #undef PUSH_NEXT |
| #undef SORT_SWAP |
| #undef SORT_CONCAT |
| #undef SORT_MAKE_STR1 |
| #undef SORT_MAKE_STR |
| #undef BINARY_INSERTION_FIND |
| #undef BINARY_INSERTION_SORT_START |
| #undef BINARY_INSERTION_SORT |
| #undef REVERSE_ELEMENTS |
| #undef COUNT_RUN |
| #undef TIM_SORT |
| #undef TIM_SORT_RESIZE |
| #undef TIM_SORT_COLLAPSE |
| #undef TIM_SORT_RUN_T |
| #undef TEMP_STORAGE_T |