stable-qsort.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  */
   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
  47 void git_stable_qsort(void *b, size_t n, size_t s,
  48                       int (*cmp)(const void *, const void *))
  49 {
  50         const size_t size = st_mult(n, s);
  51         char buf[1024];
  52
  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 = xmalloc(size);
  59                 msort_with_tmp(b, n, s, cmp, tmp);
  60                 free(tmp);
  61         }
  62 }