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 */
   7
   8static 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
  47void 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];
  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}