+/*
+ * 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 THRESH 4 /* threshold for insertion */
+
+#define MTHRESH 6 /* threshold for median */
+
+
+
+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...
+ */
+qsort (base, n, size, compar)
+ char *base;
+ int n;
+ int size;
+ int (*compar)();
+{
+ register char *i, *j, *lo, *hi, *min;
+ register int 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).
+ */
+
+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 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 * ((lo/qsz) >> 1);
+ if (lo >= mthresh)
+ {
+ j = ((*qcmp) ((jj = base), i) > 0 ? jj : i);
+ if ((*qcmp) (j, (tmp = max - qsz)) > 0)
+ {
+ j = (j == jj ? i : jj); /* switch to first loser */
+ 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 = 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);
+}
+
+
+\f
projects / unix-history / commitdiff