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 }