Andrew's git - gitweb.git/blob

   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
   9static 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
  48int 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}