]>
Commit | Line | Data |
---|---|---|
97fff610 | 1 | #include "git-compat-util.h" |
43fe901b BD |
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 | */ | |
7 | ||
8 | static void msort_with_tmp(void *b, size_t n, size_t s, | |
9 | int (*cmp)(const void *, const void *), | |
10 | char *t) | |
11 | { | |
12 | char *tmp; | |
13 | char *b1, *b2; | |
14 | size_t n1, n2; | |
15 | ||
16 | if (n <= 1) | |
17 | return; | |
18 | ||
19 | n1 = n / 2; | |
20 | n2 = n - n1; | |
21 | b1 = b; | |
22 | b2 = (char *)b + (n1 * s); | |
23 | ||
24 | msort_with_tmp(b1, n1, s, cmp, t); | |
25 | msort_with_tmp(b2, n2, s, cmp, t); | |
26 | ||
27 | tmp = t; | |
28 | ||
29 | while (n1 > 0 && n2 > 0) { | |
30 | if (cmp(b1, b2) <= 0) { | |
31 | memcpy(tmp, b1, s); | |
32 | tmp += s; | |
33 | b1 += s; | |
34 | --n1; | |
35 | } else { | |
36 | memcpy(tmp, b2, s); | |
37 | tmp += s; | |
38 | b2 += s; | |
39 | --n2; | |
40 | } | |
41 | } | |
42 | if (n1 > 0) | |
43 | memcpy(tmp, b1, n1 * s); | |
44 | memcpy(b, t, (n - n2) * s); | |
45 | } | |
46 | ||
97fff610 JS |
47 | void git_stable_qsort(void *b, size_t n, size_t s, |
48 | int (*cmp)(const void *, const void *)) | |
43fe901b | 49 | { |
50a6c8ef | 50 | const size_t size = st_mult(n, s); |
b80741e5 RS |
51 | char *tmp; |
52 | ||
53 | tmp = xmalloc(size); | |
54 | msort_with_tmp(b, n, s, cmp, tmp); | |
55 | free(tmp); | |
43fe901b | 56 | } |