use bzero

[unix-history] / usr / src / lib / libc / stdlib / qsort.c

diff --git a/usr/src/lib/libc/stdlib/qsort.c b/usr/src/lib/libc/stdlib/qsort.c
index b8f38e2..740f45f 100644 (file)
--- a/usr/src/lib/libc/stdlib/qsort.c
+++ b/usr/src/lib/libc/stdlib/qsort.c
@@ -1,121 +1,199 @@
-/* @(#)qsort.c 4.1 (Berkeley) %G% */
+/* @(#)qsort.c 4.2 (Berkeley) %G% */

 
 

-static int     (*qscmp)();
-static int     qses;
+/*
+ * 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.
+ */

 
 

-qsort(a, n, es, fc)
-char *a;
-unsigned n;
-int es;
-int (*fc)();
-{
-       qscmp = fc;
-       qses = es;
-       qs1(a, a+n*es);
-}
+#define                THRESH          4               /* threshold for insertion */
+#define                MTHRESH         6               /* threshold for median */

 
 

-static qs1(a, l)
-char *a, *l;
-{
-       register char *i, *j;
-       register es;
-       char **k;
-       char *lp, *hp;
-       int c;
-       unsigned n;
+static  int            (*qcmp)();              /* the comparison routine */
+static  int            qsz;                    /* size of each record */
+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...
+ */

 
 

-       es = qses;
+qsort(base, n, size, compar)
+       char    *base;
+       int     n;
+       int     size;
+       int     (*compar)();
+{
+       register char c, *i, *j, *lo, *hi;
+       char *min, *max;

 
 

-start:
-       if((n=l-a) <= es)
+       if (n <= 1)

                return;
                return;

-       n = es * (n / (2*es));
-       hp = lp = a+n;
-       i = a;
-       j = l-es;
-       for(;;) {
-               if(i < lp) {
-                       if((c = (*qscmp)(i, lp)) == 0) {
-                               qsexc(i, lp -= es);
-                               continue;
-                       }
-                       if(c < 0) {
-                               i += es;
-                               continue;
-                       }
-               }
-
-loop:
-               if(j > hp) {
-                       if((c = (*qscmp)(hp, j)) == 0) {
-                               qsexc(hp += es, j);
-                               goto loop;
-                       }
-                       if(c > 0) {
-                               if(i == lp) {
-                                       qstexc(i, hp += es, j);
-                                       i = lp += es;
-                                       goto loop;
-                               }
-                               qsexc(i, j);
-                               j -= es;
-                               i += es;
-                               continue;
-                       }
-                       j -= es;
-                       goto loop;
+       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;

                }
                }

-
-
-               if(i == lp) {
-                       if(lp-a >= l-hp) {
-                               qs1(hp+es, l);
-                               l = lp;
-                       } else {
-                               qs1(a, lp);
-                               a = hp+es;
+       }
+       /*
+        * 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)
+                       /* void */;
+               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;

                        }
                        }

-                       goto start;

                }
                }

-
-
-               qstexc(j, lp -= es, i);
-               j = hp -= es;

        }
 }
 
        }
 }
 

-static qsexc(i, j)
-char *i, *j;
-{
-       register char *ri, *rj, c;
-       int n;
-
-       n = qses;
-       ri = i;
-       rj = j;
-       do {
-               c = *ri;
-               *ri++ = *rj;
-               *rj++ = c;
-       } while(--n);
-}
+/*
+ * 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 qstexc(i, j, k)
-char *i, *j, *k;
+static
+qst(base, max)
+       char *base, *max;

 {
 {

-       register char *ri, *rj, *rk;
-       int c;
-       int n;
+       register char c, *i, *j, *jj;
+       register int ii;
+       char *mid, *tmp;
+       int lo, hi;

 
 

-       n = qses;
-       ri = i;
-       rj = j;
-       rk = k;
-       do {
-               c = *ri;
-               *ri++ = *rk;
-               *rk++ = *rj;
-               *rj++ = c;
-       } while(--n);
+       /*
+        * 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.
+        */
+       lo = max - base;                /* number of elements as chars */
+       do      {
+               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) {
+                               /* 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 = 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);

 }
 }