+++ /dev/null
-/*
- * 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);
-}
projects / libgit2.git / blobdiff