restore Build,TODO from r57911

git-svn-id: svn://tug.org/texlive/trunk@57915 c570f23f-e606-0410-a88d-b1316a301751

1 files changed, 206 insertions, 0 deletions

diff --git a/Build/source/texk/mendexk/qsort.c b/Build/source/texk/mendexk/qsort.c
new file mode 100644
index 00000000000..df95890e68b
--- /dev/null
+++ b/Build/source/texk/mendexk/qsort.c
@@ -0,0 +1,206 @@
+/*
+ *
+ *  This file is part of
+ *	MakeIndex - A formatter and format independent index processor
+ *
+ *  This file is public domain software donated by
+ *  Nelson Beebe (beebe@science.utah.edu).
+ *
+ */
+
+/*
+ * 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 "qsort.h"			/* qq_compar_fn_t type and qqsort() prototype */
+
+#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 qq_compar_fn_t qcmp;		/* the comparison routine */
+static void qst(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
+qqsort(void *base, size_t n, size_t size, qq_compar_fn_t compar)
+{
+    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 = (char *)base + n * qsz;
+    if (n >= THRESH) {
+	qst(base, max);
+	hi = (char *)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 = i + 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
+qst(char *base, char *max)
+{
+    register char *i;
+    register char *j;
+    register char *jj;
+    register char *mid;
+    register int ii;
+    register char c;
+    void *tmp;
+    int lo;
+    int 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 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 updated 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);
+}