1 #include "../git-compat-util.h"
2
3 /*
4 * A merge sort implementation, simplified from the qsort implementation
5 * by Mike Haertel, which is a part of the GNU C Library.
6 * Added context pointer, safety checks and return value.
7 */
8
msort_with_tmp(void * b,size_t n,size_t s,int (* cmp)(const void *,const void *,void *),char * t,void * ctx)9 static void msort_with_tmp(void *b, size_t n, size_t s,
10 int (*cmp)(const void *, const void *, void *),
11 char *t, void *ctx)
12 {
13 char *tmp;
14 char *b1, *b2;
15 size_t n1, n2;
16
17 if (n <= 1)
18 return;
19
20 n1 = n / 2;
21 n2 = n - n1;
22 b1 = b;
23 b2 = (char *)b + (n1 * s);
24
25 msort_with_tmp(b1, n1, s, cmp, t, ctx);
26 msort_with_tmp(b2, n2, s, cmp, t, ctx);
27
28 tmp = t;
29
30 while (n1 > 0 && n2 > 0) {
31 if (cmp(b1, b2, ctx) <= 0) {
32 memcpy(tmp, b1, s);
33 tmp += s;
34 b1 += s;
35 --n1;
36 } else {
37 memcpy(tmp, b2, s);
38 tmp += s;
39 b2 += s;
40 --n2;
41 }
42 }
43 if (n1 > 0)
44 memcpy(tmp, b1, n1 * s);
45 memcpy(b, t, (n - n2) * s);
46 }
47
git_qsort_s(void * b,size_t n,size_t s,int (* cmp)(const void *,const void *,void *),void * ctx)48 int git_qsort_s(void *b, size_t n, size_t s,
49 int (*cmp)(const void *, const void *, void *), void *ctx)
50 {
51 const size_t size = st_mult(n, s);
52 char buf[1024];
53
54 if (!n)
55 return 0;
56 if (!b || !cmp)
57 return -1;
58
59 if (size < sizeof(buf)) {
60 /* The temporary array fits on the small on-stack buffer. */
61 msort_with_tmp(b, n, s, cmp, buf, ctx);
62 } else {
63 /* It's somewhat large, so malloc it. */
64 char *tmp = xmalloc(size);
65 msort_with_tmp(b, n, s, cmp, tmp, ctx);
66 free(tmp);
67 }
68 return 0;
69 }
70