Merge branch 'es/worktree-cleanup'
[git] / compat / qsort_s.c
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 }