/*
 *
 *  This file is part of
 *	MakeIndex - A formatter and format independent index processor
 *
 *  This file is public domain software donated by
 *  Nelson Beebe ([email protected]).
 *
 */

/*
 * 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.
 */

/* #include <stdio.h> -- mkind.h includes this */
#include    "mkind.h"		       /* only for type declarations */

#define THRESH  4		       /* threshold for insertion */
#define MTHRESH 6		       /* threshold for median */

static int qsz;			       /* size of each record */
static int thresh;		       /* THRESHold in chars */
static int mthresh;		       /* MTHRESHold in chars */

static int	(*qcmp) ARGS((char*,char*)); /* the comparison routine */
static void	qst ARGS((char *base, char *max));
/*
 * qqsort: 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...
 */

void
#if STDC
qqsort(char *base, int n, int size, int (*compar) ARGS((char*,char*)))
#else
qqsort(base, n, size, compar)
char   *base;
int     n;
int     size;
int     (*compar) ARGS((char*,char*));
#endif
{
    register char *i;
    register char *j;
    register char *lo;
    register char *hi;
    register char *min;
    register char c;
    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 ((*qcmp) (j, lo) > 0)
	    j = lo;
    }
    if (j != base) {		       /* swap j into place */
	for (i = base, hi = base + qsz; i < hi;) {
	    c = *j;
	    *j++ = *i;
	    *i++ = c;
	}
    }
    /*
     * 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 ((*qcmp) (hi -= qsz, min) > 0);
	if ((hi += qsz) != min) {
	    for (lo = min + qsz; --lo >= min;) {
		c = *lo;
		for (i = j = lo; (j -= qsz) >= hi; i = j)
		    *i = *j;
		*i = c;
	    }
	}
    }
}



/*
 * 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).
 */

static void
#if STDC
qst(char *base, char *max)
#else
qst(base, max)
char   *base;
char   *max;
#endif
{
    register char *i;
    register char *j;
    register char *jj;
    register char *mid;
    register int ii;
    register char c;
    char   *tmp;
    int     lo;
    int     hi;

    lo = (int)(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 the middle
	 * element.  Set j to largest of first and middle.  If max is larger
	 * 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 first in case of ties.
	 */
	mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
	if (lo >= mthresh) {
	    j = ((*qcmp) ((jj = base), i) > 0 ? jj : i);
	    if ((*qcmp) (j, (tmp = max - qsz)) > 0) {
		/* switch to first loser */
		j = (j == jj ? i : jj);
		if ((*qcmp) (j, tmp) < 0)
		    j = tmp;
	    }
	    if (j != i) {
		ii = qsz;
		do {
		    c = *i;
		    *i++ = *j;
		    *j++ = c;
		} while (--ii);
	    }
	}
	/* Semi-standard quicksort partitioning/swapping */
	for (i = base, j = max - qsz;;) {
	    while (i < mid && (*qcmp) (i, mid) <= 0)
		i += qsz;
	    while (j > mid) {
		if ((*qcmp) (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:
	    ii = qsz;
	    do {
		c = *i;
		*i++ = *jj;
		*jj++ = c;
	    } while (--ii);
	    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 = (int)(j - base)) <= (hi = (int)(max - i))) {
	    if (lo >= thresh)
		qst(base, j);
	    base = i;
	    lo = hi;
	} else {
	    if (hi >= thresh)
		qst(i, max);
	    max = j;
	}
    } while (lo >= thresh);
}