Subversion Repositories or1k_old

/*

 * This file lifted in toto from 'Dlibs' on the atari ST  (RdeBath)

 *

 *

 *    Dale Schumacher                         399 Beacon Ave.

 *    (alias: Dalnefre')                      St. Paul, MN  55104

 *    dal@syntel.UUCP                         United States of America

 *  "It's not reality that's important, but how you perceive things."

 */

#include <string.h>

char *_qbuf = 0;         /* pointer to storage for qsort() */

#define PIVOT                   ((i+j)>>1)

#define moveitem(dst,src,size)  if(dst != src) memcpy(dst, src, size)

static

_wqsort(base, lo, hi, cmp)

register int *base;

register int lo;

register int hi;

register int (*cmp) ();

{

   int   k;

   register int i, j, t;

   register int *p = &k;

   while (hi > lo)

   {

      i = lo;

      j = hi;

      t = PIVOT;

      *p = base[t];

      base[t] = base[i];

      base[i] = *p;

      while (i < j)

      {

         while (((*cmp) ((base + j), p)) > 0)

            --j;

         base[i] = base[j];

         while ((i < j) && (((*cmp) ((base + i), p)) <= 0))

            ++i;

         base[j] = base[i];

      }

      base[i] = *p;

      if ((i - lo) < (hi - i))

      {

         _wqsort(base, lo, (i - 1), cmp);

         lo = i + 1;

      }

      else

      {

         _wqsort(base, (i + 1), hi, cmp);

         hi = i - 1;

      }

   }

}

static

_lqsort(base, lo, hi, cmp)

register long *base;

register int lo;

register int hi;

register int (*cmp) ();

{

   long  k;

   register int i, j, t;

   register long *p = &k;

   while (hi > lo)

   {

      i = lo;

      j = hi;

      t = PIVOT;

      *p = base[t];

      base[t] = base[i];

      base[i] = *p;

      while (i < j)

      {

         while (((*cmp) ((base + j), p)) > 0)

            --j;

         base[i] = base[j];

         while ((i < j) && (((*cmp) ((base + i), p)) <= 0))

            ++i;

         base[j] = base[i];

      }

      base[i] = *p;

      if ((i - lo) < (hi - i))

      {

         _lqsort(base, lo, (i - 1), cmp);

         lo = i + 1;

      }

      else

      {

         _lqsort(base, (i + 1), hi, cmp);

         hi = i - 1;

      }

   }

}

static

_nqsort(base, lo, hi, size, cmp)

register char *base;

register int lo;

register int hi;

register int size;

register int (*cmp) ();

{

   register int i, j;

   register char *p = _qbuf;

   while (hi > lo)

   {

      i = lo;

      j = hi;

      p = (base + size * PIVOT);

      moveitem(_qbuf, p, size);

      moveitem(p, (base + size * i), size);

      moveitem((base + size * i), _qbuf, size);

      p = _qbuf;

      while (i < j)

      {

         while (((*cmp) ((base + size * j), p)) > 0)

            --j;

         moveitem((base + size * i), (base + size * j), size);

         while ((i < j) && (((*cmp) ((base + size * i), p)) <= 0))

            ++i;

         moveitem((base + size * j), (base + size * i), size);

      }

      moveitem((base + size * i), p, size);

      if ((i - lo) < (hi - i))

      {

         _nqsort(base, lo, (i - 1), size, cmp);

         lo = i + 1;

      }

      else

      {

         _nqsort(base, (i + 1), hi, size, cmp);

         hi = i - 1;

      }

   }

}

qsort(base, num, size, cmp)

char *base;

int   num;

int   size;

int   (*cmp) ();

{

   char  _qtemp[128];

   if (_qbuf == 0)

   {

      if (size > sizeof(_qtemp))/* records too large! */

         return;

      _qbuf = _qtemp;

   }

   if (size == 2)

      _wqsort(base, 0, num - 1, cmp);

   else if (size == 4)

      _lqsort(base, 0, num - 1, cmp);

   else

      _nqsort(base, 0, num - 1, size, cmp);

   if (_qbuf == _qtemp)

      _qbuf = 0;

}