/* GNU qsort covered by GNU GPL */
/*
 * qsort.c:
 * Our own version of the system qsort routine which is faster by an average
 * of 25%, with lows and highs of 10% and 50%.
 * The THRESHold below is the insertion sort threshold, and has been adjusted
 * for records of size 48 bytes.
 * The MTHREShold is where we stop finding a better median.
 */

#define         MTHRESH         6               /* threshold for median */
/*
#define		INTEGER		1
*/

static  int             qsz;                    /* size of each record */
static  int             (*qcmp)();              /* the comparison routine */

static  int             thresh;                 /* THRESHold in chars */
static  int             mthresh;                /* MTHRESHold in chars */


/*
 * qsort:
 * First, set up some global parameters for qst to share.  Then, quicksort
 * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
 * It's not...
 */


#if !INTEGER
#define THRESH 8
#define COMPARE(i1,i2) (*qcmp)(i1,i2)
#define SWAPP(i1,i2) \
  {ii = qsz;do {c = *(i1);*(i1)++ = *(i2);*(i2)++ = c;} while(--ii);}
#else
#define THRESH 24
#define COMPARE(i1,i2) (*(int *)(i1) - *(int *)(i2))
#define SWAPP(i1,i2) \
  {register int itmp;itmp=*(int *)(i1);*(int *)(i1)=*(int *)(i2);*(int *)(i2)=itmp;}
#endif

void qst();

void g50gnu(base, n, size, compar)
     char *base;
     int n;
     int size;
     int (*compar)();
{
  register char *i, *j, *lo, *hi, *min;
  register int c,ii;
  char *max;

  if (n <= 1)  return;
  qsz = size;
  qcmp = compar;
  thresh = qsz*THRESH;
  mthresh = qsz*MTHRESH;
  max = base + n*qsz;
  if (n >= THRESH)
    {
      qst (base, max);
      hi = base + thresh;
    }
  else
    {
      hi = max;
    }
  /*
   * First put smallest element, which must be in the first THRESH, in
   * the first position as a sentinel.  This is done just by searching
   * the first THRESH elements (or the first n if n < THRESH), finding
   * the min, and swapping it into the first position.
   */
  for (j = lo = base; (lo += qsz) < hi; )
    {
      if (COMPARE(j, lo) > 0)
        j = lo;
    }
  if (j != base)
    {                   /* swap j into place */
      for (i = base, hi = base + qsz; i < hi;)
#if !INTEGER
        {
          c = *j;
          *j++ = *i;
          *i++ = c;
        }
#else
      {
        SWAPP(i,j);
        i+=qsz;j+=qsz;
      }
#endif
    }
  /*
   * With our sentinel in place, we now run the following hyper-fast
   * insertion sort.  For each remaining element, min, from [1] to [n-1],
   * set hi to the index of the element AFTER which this one goes.
   * Then, do the standard insertion sort shift on a character at a time
   * basis for each element in the frob.
   */
  for (min = base; (hi = min += qsz) < max;)
    {
      while ( COMPARE(hi -= qsz, min) > 0);

      if ((hi += qsz) != min)
#if !INTEGER
        {
          for (lo = min + qsz; --lo >= min;)
            {
              c = *lo;
              for (i = j = lo; (j -= qsz) >= hi; i = j)
                *i = *j;
              *i = c;
            }
        }
#else
      {
        register int cI;
        register int *loI,*minI=(int *)min,*hiI=(int *)hi,*iI,*jI;
        for (loI = minI + 1; --loI >= minI;)
            {
              cI = *loI;
              for (iI = jI = loI; (jI -= 1) >= hiI; iI = jI)
                *iI = *jI;
              *iI = cI;
            }
      }
#endif
    }
}

/*
 * qst:
 * Do a quicksort
 * First, find the median element, and put that one in the first place as the
 * discriminator.  (This "median" is just the median of the first, last and
 * middle elements).  (Using this median instead of the first element is a big
 * win).  Then, the usual partitioning/swapping, followed by moving the
 * discriminator into the right place.  Then, figure out the sizes of the two
 * partions, do the smaller one recursively and the larger one via a repeat of
 * this code.  Stopping when there are less than THRESH elements in a partition
 * and cleaning up with an insertion sort (in our caller) is a huge win.
 * All data swaps are done in-line, which is space-losing but time-saving.
 * (And there are only three places where this is done).
 */

void qst (base, max)
     char *base, *max;
{
  register char *i, *j, *jj, *mid;
  register int ii, c;
  char *tmp;
  int lo, hi;

  lo = max - base;              /* number of elements as chars */
  do
    {
      /*
       * At the top here, lo is the number of characters of elements in the
       * current partition.  (Which should be max - base).
       * Find the median of the first, last, and middle element and make that th
e
       * middle element.  Set j to largest of first and middle.  If max is large
r
       * than that guy, then it's that guy, else compare max with loser of first
       * and take larger.  Things are set up to prefer the middle, then the firs
t
       * in case of ties.
       */
      mid = i = base + qsz * ((lo/qsz) >> 1);
      if (lo >= mthresh)
        {
#if !INTEGER
          j = (COMPARE((jj = base), i) > 0 ? jj : i);
          if (COMPARE(j, (tmp = max - qsz)) > 0)
#else
            jj = base;
          j = (COMPARE(jj, i) > 0 ? jj : i);
          tmp = max - qsz;
          if (COMPARE(j, tmp) > 0)
#endif
            {
              j = (j == jj ? i : jj);   /* switch to first loser */
              if (COMPARE(j, tmp) < 0)
                j = tmp;
            }
          if (j != i)
            {
#if !INTEGER
              ii = qsz;
              do
                {
                  c = *i;
                  *i++ = *j;
                  *j++ = c;
                }
              while(  --ii  );
#else
              SWAPP(i,j);
              i+=qsz;j+=qsz;
#endif
            }
        }
      /*
       * Semi-standard quicksort partitioning/swapping
       */
      for (i = base, j = max - qsz; ;)
        {
          while (i < mid && COMPARE(i, mid) <= 0)
            i += qsz;
          while (j > mid)
            {
              if (COMPARE(mid, j) <= 0)
                {
                  j -= qsz;
                  continue;
                }
              tmp = i + qsz;            /* value of i after swap */
              if (i == mid)
                {       /* j <-> mid, new mid is j */
                  mid = jj = j;
                }
              else
                {                       /* i <-> j */
                  jj = j;
                  j -= qsz;
                }
              goto  swap;
            }
          if (i == mid)
            {
              break;
            }
          else
            {                           /* i <-> mid, new mid is i */
              jj = mid;
              tmp = mid = i;            /* value of i after swap */
              j -= qsz;
            }
        swap:
#if !INTEGER
          ii = qsz;
          do
            {
              c = *i;
              *i++ = *jj;
              *jj++ = c;
            }
          while (--ii);
#else
          SWAPP(i,jj);
          i+=qsz;jj+=qsz;
#endif
          i = tmp;
        }
      /*
       * Look at sizes of the two partitions, do the smaller one first by
       * recursion, then do the larger one by making sure lo is its size,
       * base and max are update correctly, and branching back.
       * But only repeat (recursively or by branching) if the partition is
       * of at least size THRESH.
       */
      i = (j = mid) + qsz;
      if ((lo = j - base) <= (hi = max - i))
        {
          if (lo >= thresh)
            qst (base, j);
          base = i;
          lo = hi;
        }
      else
        {
          if (hi >= thresh)
            qst (i, max);
          max = j;
        }
    }
  while (lo >= thresh);
}

