Commit 62beacd300a6d3c62943723928f45ef852485e62
2013-03-11T16:43:58
Sorting function cleanup and MinGW fix Clean up some sorting function stuff including fixing qsort_r on MinGW, common function pointer type for comparison, and basic insertion sort implementation (which we, regrettably, fall back on for MinGW).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
diff --git a/src/tsort.c b/src/tsort.c
index 97473be..4885e43 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 561288f..102bbae 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 e77f17e..c0f2719 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