summaryrefslogtreecommitdiff
path: root/Build/source/texk/makeindexk/qsort.c
diff options
context:
space:
mode:
authorKarl Berry <karl@freefriends.org>2006-01-17 21:41:51 +0000
committerKarl Berry <karl@freefriends.org>2006-01-17 21:41:51 +0000
commit487ca4806cc046076293cf6cc5fbba0db282bac7 (patch)
tree847b412ab5158dd7bdd7ed7e5a4cc3fbca94be32 /Build/source/texk/makeindexk/qsort.c
parenta3d3111bfe26b8e5f5bc6049dfb2a4ca2edc7881 (diff)
texk 1
git-svn-id: svn://tug.org/texlive/trunk@1485 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/makeindexk/qsort.c')
-rw-r--r--Build/source/texk/makeindexk/qsort.c222
1 files changed, 222 insertions, 0 deletions
diff --git a/Build/source/texk/makeindexk/qsort.c b/Build/source/texk/makeindexk/qsort.c
new file mode 100644
index 00000000000..7223a205450
--- /dev/null
+++ b/Build/source/texk/makeindexk/qsort.c
@@ -0,0 +1,222 @@
+/*
+ *
+ * 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 <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);
+}