]>
Commit | Line | Data |
---|---|---|
04ee8b87 RS |
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 | ||
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 | ||
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 | } |