Code

Merge branch 'jc/maint-obsd46' into maint
[git.git] / compat / qsort.c
1 #include "../git-compat-util.h"
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  */
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;
16         if (n <= 1)
17                 return;
19         n1 = n / 2;
20         n2 = n - n1;
21         b1 = b;
22         b2 = (char *)b + (n1 * s);
24         msort_with_tmp(b1, n1, s, cmp, t);
25         msort_with_tmp(b2, n2, s, cmp, t);
27         tmp = t;
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 }
47 void git_qsort(void *b, size_t n, size_t s,
48                int (*cmp)(const void *, const void *))
49 {
50         const size_t size = n * s;
51         char buf[1024];
53         if (size < sizeof(buf)) {
54                 /* The temporary array fits on the small on-stack buffer. */
55                 msort_with_tmp(b, n, s, cmp, buf);
56         } else {
57                 /* It's somewhat large, so malloc it.  */
58                 char *tmp = malloc(size);
59                 msort_with_tmp(b, n, s, cmp, tmp);
60                 free(tmp);
61         }
62 }