freshlybakedca.ke
Git fork
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
9static 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
48int 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 *tmp;
53
54 if (!n)
55 return 0;
56 if (!b || !cmp)
57 return -1;
58
59 tmp = xmalloc(size);
60 msort_with_tmp(b, n, s, cmp, tmp, ctx);
61 free(tmp);
62 return 0;
63}