Back to index

tetex-bin  3.0
qsort.c
Go to the documentation of this file.
00001 /*
00002  *
00003  *  This file is part of
00004  *     MakeIndex - A formatter and format independent index processor
00005  *
00006  *  This file is public domain software donated by
00007  *  Nelson Beebe (beebe@science.utah.edu).
00008  *
00009  */
00010 
00011 /*
00012  * qsort.c: Our own version of the system qsort routine which is faster by an
00013  * average of 25%, with lows and highs of 10% and 50%. The THRESHold below is
00014  * the insertion sort threshold, and has been adjusted for records of size 48
00015  * bytes. The MTHREShold is where we stop finding a better median.
00016  */
00017 
00018 /* #include <stdio.h> -- mkind.h includes this */
00019 #include    "mkind.h"                     /* only for type declarations */
00020 
00021 #define THRESH  4                  /* threshold for insertion */
00022 #define MTHRESH 6                  /* threshold for median */
00023 
00024 static int qsz;                           /* size of each record */
00025 static int thresh;                 /* THRESHold in chars */
00026 static int mthresh;                /* MTHRESHold in chars */
00027 
00028 static int    (*qcmp) ARGS((char*,char*)); /* the comparison routine */
00029 static void   qst ARGS((char *base, char *max));
00030 /*
00031  * qqsort: First, set up some global parameters for qst to share.  Then,
00032  * quicksort with qst(), and then a cleanup insertion sort ourselves.  Sound
00033  * simple? It's not...
00034  */
00035 
00036 void
00037 #if STDC
00038 qqsort(char *base, int n, int size, int (*compar) ARGS((char*,char*)))
00039 #else
00040 qqsort(base, n, size, compar)
00041 char   *base;
00042 int     n;
00043 int     size;
00044 int     (*compar) ARGS((char*,char*));
00045 #endif
00046 {
00047     register char *i;
00048     register char *j;
00049     register char *lo;
00050     register char *hi;
00051     register char *min;
00052     register char c;
00053     char   *max;
00054 
00055     if (n <= 1)
00056        return;
00057     qsz = size;
00058     qcmp = compar;
00059     thresh = qsz * THRESH;
00060     mthresh = qsz * MTHRESH;
00061     max = base + n * qsz;
00062     if (n >= THRESH) {
00063        qst(base, max);
00064        hi = base + thresh;
00065     } else {
00066        hi = max;
00067     }
00068     /*
00069      * First put smallest element, which must be in the first THRESH, in the
00070      * first position as a sentinel.  This is done just by searching the
00071      * first THRESH elements (or the first n if n < THRESH), finding the min,
00072      * and swapping it into the first position.
00073      */
00074     for (j = lo = base; (lo += qsz) < hi;) {
00075        if ((*qcmp) (j, lo) > 0)
00076            j = lo;
00077     }
00078     if (j != base) {               /* swap j into place */
00079        for (i = base, hi = base + qsz; i < hi;) {
00080            c = *j;
00081            *j++ = *i;
00082            *i++ = c;
00083        }
00084     }
00085     /*
00086      * With our sentinel in place, we now run the following hyper-fast
00087      * insertion sort. For each remaining element, min, from [1] to [n-1],
00088      * set hi to the index of the element AFTER which this one goes. Then, do
00089      * the standard insertion sort shift on a character at a time basis for
00090      * each element in the frob.
00091      */
00092     for (min = base; (hi = min += qsz) < max;) {
00093        while ((*qcmp) (hi -= qsz, min) > 0);
00094        if ((hi += qsz) != min) {
00095            for (lo = min + qsz; --lo >= min;) {
00096               c = *lo;
00097               for (i = j = lo; (j -= qsz) >= hi; i = j)
00098                   *i = *j;
00099               *i = c;
00100            }
00101        }
00102     }
00103 }
00104 
00105 
00106 
00107 /*
00108  * qst: Do a quicksort.  First, find the median element, and put that one in
00109  * the first place as the discriminator.  (This "median" is just the median
00110  * of the first, last and middle elements).  (Using this median instead of
00111  * the first element is a big win). Then, the usual partitioning/swapping,
00112  * followed by moving the discriminator into the right place.  Then, figure
00113  * out the sizes of the two partions, do the smaller one recursively and the
00114  * larger one via a repeat of this code.  Stopping when there are less than
00115  * THRESH elements in a partition and cleaning up with an insertion sort (in
00116  * our caller) is a huge win. All data swaps are done in-line, which is
00117  * space-losing but time-saving. (And there are only three places where this
00118  * is done).
00119  */
00120 
00121 static void
00122 #if STDC
00123 qst(char *base, char *max)
00124 #else
00125 qst(base, max)
00126 char   *base;
00127 char   *max;
00128 #endif
00129 {
00130     register char *i;
00131     register char *j;
00132     register char *jj;
00133     register char *mid;
00134     register int ii;
00135     register char c;
00136     char   *tmp;
00137     int     lo;
00138     int     hi;
00139 
00140     lo = (int)(max - base);        /* number of elements as chars */
00141     do {
00142        /*
00143         * At the top here, lo is the number of characters of elements in the
00144         * current partition.  (Which should be max - base). Find the median
00145         * of the first, last, and middle element and make that the middle
00146         * element.  Set j to largest of first and middle.  If max is larger
00147         * than that guy, then it's that guy, else compare max with loser of
00148         * first and take larger.  Things are set up to prefer the middle,
00149         * then the first in case of ties.
00150         */
00151        mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
00152        if (lo >= mthresh) {
00153            j = ((*qcmp) ((jj = base), i) > 0 ? jj : i);
00154            if ((*qcmp) (j, (tmp = max - qsz)) > 0) {
00155               /* switch to first loser */
00156               j = (j == jj ? i : jj);
00157               if ((*qcmp) (j, tmp) < 0)
00158                   j = tmp;
00159            }
00160            if (j != i) {
00161               ii = qsz;
00162               do {
00163                   c = *i;
00164                   *i++ = *j;
00165                   *j++ = c;
00166               } while (--ii);
00167            }
00168        }
00169        /* Semi-standard quicksort partitioning/swapping */
00170        for (i = base, j = max - qsz;;) {
00171            while (i < mid && (*qcmp) (i, mid) <= 0)
00172               i += qsz;
00173            while (j > mid) {
00174               if ((*qcmp) (mid, j) <= 0) {
00175                   j -= qsz;
00176                   continue;
00177               }
00178               tmp = i + qsz;              /* value of i after swap */
00179               if (i == mid) {             /* j <-> mid, new mid is j */
00180                   mid = jj = j;
00181               } else {             /* i <-> j */
00182                   jj = j;
00183                   j -= qsz;
00184               }
00185               goto swap;
00186            }
00187            if (i == mid) {
00188               break;
00189            } else {                /* i <-> mid, new mid is i */
00190               jj = mid;
00191               tmp = mid = i;              /* value of i after swap */
00192               j -= qsz;
00193            }
00194     swap:
00195            ii = qsz;
00196            do {
00197               c = *i;
00198               *i++ = *jj;
00199               *jj++ = c;
00200            } while (--ii);
00201            i = tmp;
00202        }
00203        /*
00204         * Look at sizes of the two partitions, do the smaller one first by
00205         * recursion, then do the larger one by making sure lo is its size,
00206         * base and max are update correctly, and branching back. But only
00207         * repeat (recursively or by branching) if the partition is of at
00208         * least size THRESH.
00209         */
00210        i = (j = mid) + qsz;
00211        if ((lo = (int)(j - base)) <= (hi = (int)(max - i))) {
00212            if (lo >= thresh)
00213               qst(base, j);
00214            base = i;
00215            lo = hi;
00216        } else {
00217            if (hi >= thresh)
00218               qst(i, max);
00219            max = j;
00220        }
00221     } while (lo >= thresh);
00222 }