diff options
| -rw-r--r-- | src/tsort.c | 8 | ||||
| -rw-r--r-- | src/util.c | 34 | ||||
| -rw-r--r-- | src/util.h | 12 |
3 files changed, 39 insertions, 15 deletions
diff --git a/src/tsort.c b/src/tsort.c index 97473be91..4885e435b 100644 --- a/src/tsort.c +++ b/src/tsort.c @@ -24,7 +24,7 @@ #endif static int binsearch( - void **dst, const void *x, size_t size, git__tsort_r_cmp cmp, void *payload) + void **dst, const void *x, size_t size, git__sort_r_cmp cmp, void *payload) { int l, c, r; void *lx, *cx; @@ -71,7 +71,7 @@ static int binsearch( /* 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__tsort_r_cmp cmp, void *payload) + void **dst, size_t start, size_t size, git__sort_r_cmp cmp, void *payload) { size_t i; void *x; @@ -102,7 +102,7 @@ struct tsort_run { struct tsort_store { size_t alloc; - git__tsort_r_cmp cmp; + git__sort_r_cmp cmp; void *payload; void **storage; }; @@ -334,7 +334,7 @@ static ssize_t collapse(void **dst, struct tsort_run *stack, ssize_t stack_curr, while (0) void git__tsort_r( - void **dst, size_t size, git__tsort_r_cmp cmp, void *payload) + void **dst, size_t size, git__sort_r_cmp cmp, void *payload) { struct tsort_store _store, *store = &_store; struct tsort_run run_stack[128]; diff --git a/src/util.c b/src/util.c index 561288f72..102bbaeb3 100644 --- a/src/util.c +++ b/src/util.c @@ -610,7 +610,7 @@ size_t git__unescape(char *str) #if defined(GIT_WIN32) || defined(BSD) typedef struct { - git__qsort_r_cmp cmp; + git__sort_r_cmp cmp; void *payload; } git__qsort_r_glue; @@ -623,17 +623,39 @@ static int GIT_STDLIB_CALL git__qsort_r_glue_cmp( #endif void git__qsort_r( - void *els, size_t nel, size_t elsize, git__qsort_r_cmp cmp, void *payload) + void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload) { -#if defined(GIT_WIN32) +#if defined(__MINGW32__) + git__insertsort_r(els, nel, elsize, NULL, cmp, payload); +#elif defined(GIT_WIN32) git__qsort_r_glue glue = { cmp, payload }; qsort_s(els, nel, elsize, git__qsort_r_glue_cmp, &glue); -#else -#if defined(BSD) +#elif defined(BSD) git__qsort_r_glue glue = { cmp, payload }; qsort_r(els, nel, elsize, &glue, git__qsort_r_glue_cmp); #else qsort_r(els, nel, elsize, cmp, payload); #endif -#endif +} + +void git__insertsort_r( + void *els, size_t nel, size_t elsize, void *swapel, + git__sort_r_cmp cmp, void *payload) +{ + uint8_t *base = els, *end = els + nel * elsize; + uint8_t *i, *j; + bool freeswap = !swapel; + + if (freeswap) + swapel = git__malloc(elsize); + + for (i = base + elsize; i < end; i += elsize) + for (j = i; j > base && cmp(j, j - elsize, payload) < 0; j -= elsize) { + memcpy(swapel, j, elsize); + memcpy(j, j - elsize, elsize); + memcpy(j - elsize, swapel, elsize); + } + + if (freeswap) + git__free(swapel); } diff --git a/src/util.h b/src/util.h index e77f17efc..c0f271997 100644 --- a/src/util.h +++ b/src/util.h @@ -146,15 +146,17 @@ typedef int (*git__tsort_cmp)(const void *a, const void *b); extern void git__tsort(void **dst, size_t size, git__tsort_cmp cmp); -typedef int (*git__tsort_r_cmp)(const void *a, const void *b, void *payload); +typedef int (*git__sort_r_cmp)(const void *a, const void *b, void *payload); extern void git__tsort_r( - void **dst, size_t size, git__tsort_r_cmp cmp, void *payload); - -typedef int (*git__qsort_r_cmp)(const void *a, const void *b, void *payload); + void **dst, size_t size, git__sort_r_cmp cmp, void *payload); extern void git__qsort_r( - void *els, size_t nel, size_t elsize, git__qsort_r_cmp cmp, void *payload); + void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload); + +extern void git__insertsort_r( + void *els, size_t nel, size_t elsize, void *swapel, + git__sort_r_cmp cmp, void *payload); /** * @param position If non-NULL, this will be set to the position where the |