diff options
Diffstat (limited to 'src/tsort.c')
| -rw-r--r-- | src/tsort.c | 382 |
1 files changed, 0 insertions, 382 deletions
diff --git a/src/tsort.c b/src/tsort.c deleted file mode 100644 index 045efad23..000000000 --- a/src/tsort.c +++ /dev/null @@ -1,382 +0,0 @@ -/* - * Copyright (C) the libgit2 contributors. All rights reserved. - * - * This file is part of libgit2, distributed under the GNU GPL v2 with - * a Linking Exception. For full terms see the included COPYING file. - */ - -#include "common.h" - -/** - * An array-of-pointers implementation of Python's Timsort - * Based on code by Christopher Swenson under the MIT license - * - * Copyright (c) 2010 Christopher Swenson - * Copyright (c) 2011 Vicent Marti - */ - -#ifndef MAX -# define MAX(x,y) (((x) > (y) ? (x) : (y))) -#endif - -#ifndef MIN -# define MIN(x,y) (((x) < (y) ? (x) : (y))) -#endif - -static int binsearch( - void **dst, const void *x, size_t size, git__sort_r_cmp cmp, void *payload) -{ - int l, c, r; - void *lx, *cx; - - l = 0; - r = (int)size - 1; - c = r >> 1; - lx = dst[l]; - - /* check for beginning conditions */ - if (cmp(x, lx, payload) < 0) - return 0; - - else if (cmp(x, lx, payload) == 0) { - int i = 1; - while (cmp(x, dst[i], payload) == 0) - i++; - return i; - } - - /* guaranteed not to be >= rx */ - cx = dst[c]; - while (1) { - const int val = cmp(x, cx, payload); - if (val < 0) { - if (c - l <= 1) return c; - r = c; - } else if (val > 0) { - if (r - c <= 1) return c + 1; - l = c; - lx = cx; - } else { - do { - cx = dst[++c]; - } while (cmp(x, cx, payload) == 0); - return 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 bisort( - void **dst, size_t start, size_t size, git__sort_r_cmp cmp, void *payload) -{ - size_t i; - void *x; - int location; - - for (i = start; i < size; i++) { - int j; - /* If this entry is already correct, just move along */ - if (cmp(dst[i - 1], dst[i], payload) <= 0) - continue; - - /* Else we need to find the right place, shift everything over, and squeeze in */ - x = dst[i]; - location = binsearch(dst, x, i, cmp, payload); - for (j = (int)i - 1; j >= location; j--) { - dst[j + 1] = dst[j]; - } - dst[location] = x; - } -} - - -/* timsort implementation, based on timsort.txt */ -struct tsort_run { - ssize_t start; - ssize_t length; -}; - -struct tsort_store { - size_t alloc; - git__sort_r_cmp cmp; - void *payload; - void **storage; -}; - -static void reverse_elements(void **dst, ssize_t start, ssize_t end) -{ - while (start < end) { - void *tmp = dst[start]; - dst[start] = dst[end]; - dst[end] = tmp; - - start++; - end--; - } -} - -static ssize_t count_run( - void **dst, ssize_t start, ssize_t size, struct tsort_store *store) -{ - ssize_t curr = start + 2; - - if (size - start == 1) - return 1; - - if (start >= size - 2) { - if (store->cmp(dst[size - 2], dst[size - 1], store->payload) > 0) { - void *tmp = dst[size - 1]; - dst[size - 1] = dst[size - 2]; - dst[size - 2] = tmp; - } - - return 2; - } - - if (store->cmp(dst[start], dst[start + 1], store->payload) <= 0) { - while (curr < size - 1 && - store->cmp(dst[curr - 1], dst[curr], store->payload) <= 0) - curr++; - - return curr - start; - } else { - while (curr < size - 1 && - store->cmp(dst[curr - 1], dst[curr], store->payload) > 0) - curr++; - - /* reverse in-place */ - reverse_elements(dst, start, curr - 1); - return curr - start; - } -} - -static size_t compute_minrun(size_t n) -{ - int r = 0; - while (n >= 64) { - r |= n & 1; - n >>= 1; - } - return n + r; -} - -static int check_invariant(struct tsort_run *stack, ssize_t stack_curr) -{ - if (stack_curr < 2) - return 1; - - else if (stack_curr == 2) { - const ssize_t A = stack[stack_curr - 2].length; - const ssize_t B = stack[stack_curr - 1].length; - return (A > B); - } else { - const ssize_t A = stack[stack_curr - 3].length; - const ssize_t B = stack[stack_curr - 2].length; - const ssize_t C = stack[stack_curr - 1].length; - return !((A <= B + C) || (B <= C)); - } -} - -static int resize(struct tsort_store *store, size_t new_size) -{ - if (store->alloc < new_size) { - void **tempstore; - - tempstore = git__reallocarray(store->storage, new_size, sizeof(void *)); - - /** - * Do not propagate on OOM; this will abort the sort and - * leave the array unsorted, but no error code will be - * raised - */ - if (tempstore == NULL) - return -1; - - store->storage = tempstore; - store->alloc = new_size; - } - - return 0; -} - -static void merge(void **dst, const struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store) -{ - const ssize_t A = stack[stack_curr - 2].length; - const ssize_t B = stack[stack_curr - 1].length; - const ssize_t curr = stack[stack_curr - 2].start; - - void **storage; - ssize_t i, j, k; - - if (resize(store, MIN(A, B)) < 0) - return; - - storage = store->storage; - - /* left merge */ - if (A < B) { - memcpy(storage, &dst[curr], A * sizeof(void *)); - i = 0; - j = curr + A; - - for (k = curr; k < curr + A + B; k++) { - if ((i < A) && (j < curr + A + B)) { - if (store->cmp(storage[i], dst[j], store->payload) <= 0) - dst[k] = storage[i++]; - else - dst[k] = dst[j++]; - } else if (i < A) { - dst[k] = storage[i++]; - } else - dst[k] = dst[j++]; - } - } else { - memcpy(storage, &dst[curr + A], B * sizeof(void *)); - i = B - 1; - j = curr + A - 1; - - for (k = curr + A + B - 1; k >= curr; k--) { - if ((i >= 0) && (j >= curr)) { - if (store->cmp(dst[j], storage[i], store->payload) > 0) - dst[k] = dst[j--]; - else - dst[k] = storage[i--]; - } else if (i >= 0) - dst[k] = storage[i--]; - else - dst[k] = dst[j--]; - } - } -} - -static ssize_t collapse(void **dst, struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store, ssize_t size) -{ - ssize_t A, B, C; - - while (1) { - /* 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)) { - 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)) { - merge(dst, stack, stack_curr, store); - stack[0].length += stack[1].length; - stack_curr--; - break; - } - else if (stack_curr == 2) - break; - - A = stack[stack_curr - 3].length; - B = stack[stack_curr - 2].length; - C = stack[stack_curr - 1].length; - - /* check first invariant */ - if (A <= B + C) { - if (A < C) { - 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 { - merge(dst, stack, stack_curr, store); - stack[stack_curr - 2].length += stack[stack_curr - 1].length; - stack_curr--; - } - } else if (B <= C) { - merge(dst, stack, stack_curr, store); - stack[stack_curr - 2].length += stack[stack_curr - 1].length; - stack_curr--; - } else - break; - } - - return stack_curr; -} - -#define PUSH_NEXT() do {\ - len = count_run(dst, curr, size, store);\ - run = minrun;\ - if (run > (ssize_t)size - curr) run = size - curr;\ - if (run > len) {\ - bisort(&dst[curr], len, run, cmp, payload);\ - len = run;\ - }\ - run_stack[stack_curr].start = curr;\ - run_stack[stack_curr++].length = len;\ - curr += len;\ - if (curr == (ssize_t)size) {\ - /* finish up */ \ - while (stack_curr > 1) { \ - 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) {\ - git__free(store->storage);\ - store->storage = NULL;\ - }\ - return;\ - }\ -}\ -while (0) - -void git__tsort_r( - void **dst, size_t size, git__sort_r_cmp cmp, void *payload) -{ - struct tsort_store _store, *store = &_store; - struct tsort_run run_stack[128]; - - ssize_t stack_curr = 0; - ssize_t len, run; - ssize_t curr = 0; - ssize_t minrun; - - if (size < 64) { - bisort(dst, 1, size, cmp, payload); - return; - } - - /* compute the minimum run length */ - minrun = (ssize_t)compute_minrun(size); - - /* temporary storage for merges */ - store->alloc = 0; - store->storage = NULL; - store->cmp = cmp; - store->payload = payload; - - PUSH_NEXT(); - PUSH_NEXT(); - PUSH_NEXT(); - - while (1) { - if (!check_invariant(run_stack, stack_curr)) { - stack_curr = collapse(dst, run_stack, stack_curr, store, size); - continue; - } - - PUSH_NEXT(); - } -} - -static int tsort_r_cmp(const void *a, const void *b, void *payload) -{ - return ((git__tsort_cmp)payload)(a, b); -} - -void git__tsort(void **dst, size_t size, git__tsort_cmp cmp) -{ - git__tsort_r(dst, size, tsort_r_cmp, cmp); -} |