compilers/bcc/linux86-0.16.17/libc/misc/qsort.c

   1 /*
   2  * This file lifted in toto from 'Dlibs' on the atari ST  (RdeBath)
   3  *
   4  *
   5  *    Dale Schumacher                         399 Beacon Ave.
   6  *    (alias: Dalnefre')                      St. Paul, MN  55104
   7  *    dal@syntel.UUCP                         United States of America
   8  *  "It's not reality that's important, but how you perceive things."
   9  */
  10
  11 /*
  12  * Sun Feb  8 21:02:15 EST 1998 claudio@pos.inf.ufpr.br (Claudio Matsuoka)
  13  * Changed sort direction
  14  */
  15
  16 #include <string.h>
  17
  18 char *_qbuf = 0;                /* pointer to storage for qsort() */
  19
  20 #define PIVOT                   ((i+j)>>1)
  21 #define moveitem(dst,src,size)  if(dst != src) memcpy(dst, src, size)
  22
  23 static
  24 _wqsort(base, lo, hi, cmp)
  25 register int *base;
  26 register int lo;
  27 register int hi;
  28 register int (*cmp) ();
  29 {
  30    int   k;
  31    register int i, j, t;
  32    register int *p = &k;
  33
  34    while (hi > lo)
  35    {
  36       i = lo;
  37       j = hi;
  38       t = PIVOT;
  39       *p = base[t];
  40       base[t] = base[i];
  41       base[i] = *p;
  42       while (i < j)
  43       {
  44          while (((*cmp) ((base + j), p)) <= 0)
  45             --j;
  46          base[i] = base[j];
  47          while ((i < j) && (((*cmp) ((base + i), p)) > 0))
  48             ++i;
  49          base[j] = base[i];
  50       }
  51       base[i] = *p;
  52       if ((i - lo) < (hi - i))
  53       {
  54          _wqsort(base, lo, (i - 1), cmp);
  55          lo = i + 1;
  56       }
  57       else
  58       {
  59          _wqsort(base, (i + 1), hi, cmp);
  60          hi = i - 1;
  61       }
  62    }
  63 }
  64
  65 static
  66 _lqsort(base, lo, hi, cmp)
  67 register long *base;
  68 register int lo;
  69 register int hi;
  70 register int (*cmp) ();
  71 {
  72    long  k;
  73    register int i, j, t;
  74    register long *p = &k;
  75
  76    while (hi > lo)
  77    {
  78       i = lo;
  79       j = hi;
  80       t = PIVOT;
  81       *p = base[t];
  82       base[t] = base[i];
  83       base[i] = *p;
  84       while (i < j)
  85       {
  86          while (((*cmp) ((base + j), p)) <= 0)
  87             --j;
  88          base[i] = base[j];
  89          while ((i < j) && (((*cmp) ((base + i), p)) > 0))
  90             ++i;
  91          base[j] = base[i];
  92       }
  93       base[i] = *p;
  94       if ((i - lo) < (hi - i))
  95       {
  96          _lqsort(base, lo, (i - 1), cmp);
  97          lo = i + 1;
  98       }
  99       else
 100       {
 101          _lqsort(base, (i + 1), hi, cmp);
 102          hi = i - 1;
 103       }
 104    }
 105 }
 106
 107 static
 108 _nqsort(base, lo, hi, size, cmp)
 109 register char *base;
 110 register int lo;
 111 register int hi;
 112 register int size;
 113 register int (*cmp) ();
 114 {
 115    register int i, j;
 116    register char *p = _qbuf;
 117
 118    while (hi > lo)
 119    {
 120       i = lo;
 121       j = hi;
 122       p = (base + size * PIVOT);
 123       moveitem(_qbuf, p, size);
 124       moveitem(p, (base + size * i), size);
 125       moveitem((base + size * i), _qbuf, size);
 126       p = _qbuf;
 127       while (i < j)
 128       {
 129          while (((*cmp) ((base + size * j), p)) <= 0)
 130             --j;
 131          moveitem((base + size * i), (base + size * j), size);
 132          while ((i < j) && (((*cmp) ((base + size * i), p)) > 0))
 133             ++i;
 134          moveitem((base + size * j), (base + size * i), size);
 135       }
 136       moveitem((base + size * i), p, size);
 137       if ((i - lo) < (hi - i))
 138       {
 139          _nqsort(base, lo, (i - 1), size, cmp);
 140          lo = i + 1;
 141       }
 142       else
 143       {
 144          _nqsort(base, (i + 1), hi, size, cmp);
 145          hi = i - 1;
 146       }
 147    }
 148 }
 149
 150 qsort(base, num, size, cmp)
 151 char *base;
 152 int   num;
 153 int   size;
 154 int   (*cmp) ();
 155 {
 156    char  _qtemp[128];
 157
 158    if (_qbuf == 0)
 159    {
 160       if (size > sizeof(_qtemp))/* records too large! */
 161          return;
 162       _qbuf = _qtemp;
 163    }
 164    if (size == 2)
 165       _wqsort(base, 0, num - 1, cmp);
 166    else if (size == 4)
 167       _lqsort(base, 0, num - 1, cmp);
 168    else
 169       _nqsort(base, 0, num - 1, size, cmp);
 170    if (_qbuf == _qtemp)
 171       _qbuf = 0;
 172 }