summaryrefslogtreecommitdiff
path: root/Build/source/texk/makeindexk/qsort.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/makeindexk/qsort.c')
-rw-r--r--Build/source/texk/makeindexk/qsort.c206
1 files changed, 0 insertions, 206 deletions
diff --git a/Build/source/texk/makeindexk/qsort.c b/Build/source/texk/makeindexk/qsort.c
deleted file mode 100644
index df95890e68b..00000000000
--- a/Build/source/texk/makeindexk/qsort.c
+++ /dev/null
@@ -1,206 +0,0 @@
-/*
- *
- * 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);
-}