distr/nanotrav/ucbqsort.c

   1 #if defined(__GNUC__) && (__GNUC__ >2 || __GNUC_MINOR__ >=7)
   2 #define UNUSED __attribute__ ((unused))
   3 #else
   4 #define UNUSED
   5 #endif
   6
   7 #ifndef lint
   8 static char rcsid[] UNUSED = "$Id: ucbqsort.c,v 1.4 2004/01/01 07:06:06 fabio Exp fabio $";
   9 #endif
  10
  11 /* @(#)qsort.c  4.2 (Berkeley) 3/9/83 */
  12
  13 /*
  14  * qsort.c:
  15  * Our own version of the system qsort routine which is faster by an average
  16  * of 25%, with lows and highs of 10% and 50%.
  17  * The THRESHold below is the insertion sort threshold, and has been adjusted
  18  * for records of size 48 bytes.
  19  * The MTHREShold is where we stop finding a better median.
  20  */
  21
  22 #ifdef __cplusplus
  23 extern "C" {
  24 #endif
  25
  26 typedef  int (*QSFP)(const void *, const void *);
  27 extern void qsort ( char *base, int n, int size, QSFP compar);
  28
  29 #define         THRESH          4               /* threshold for insertion */
  30 #define         MTHRESH         6               /* threshold for median */
  31
  32 static  QSFP            qcmp;                   /* the comparison routine */
  33 static  int             qsz;                    /* size of each record */
  34 static  int             thresh;                 /* THRESHold in chars */
  35 static  int             mthresh;                /* MTHRESHold in chars */
  36
  37 static  void            qst (char *base, char *max);
  38
  39 #ifdef __cplusplus
  40 }
  41 #endif
  42
  43 /*
  44  * qsort:
  45  * First, set up some global parameters for qst to share.  Then, quicksort
  46  * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
  47  * It's not...
  48  */
  49 #undef min
  50 #undef max
  51 void
  52 qsort(
  53   char *base,
  54   int n,
  55   int size,
  56   QSFP compar)
  57 {
  58         register char c, *i, *j, *lo, *hi;
  59         char *min, *max;
  60
  61         if (n <= 1)
  62                 return;
  63         qsz = size;
  64         qcmp = compar;
  65         thresh = qsz * THRESH;
  66         mthresh = qsz * MTHRESH;
  67         max = base + n * qsz;
  68         if (n >= THRESH) {
  69                 qst(base, max);
  70                 hi = base + thresh;
  71         } else {
  72                 hi = max;
  73         }
  74         /*
  75          * First put smallest element, which must be in the first THRESH, in
  76          * the first position as a sentinel.  This is done just by searching
  77          * the first THRESH elements (or the first n if n < THRESH), finding
  78          * the min, and swapping it into the first position.
  79          */
  80         for (j = lo = base; (lo += qsz) < hi; )
  81                 if ((*qcmp)(j, lo) > 0)
  82                         j = lo;
  83         if (j != base) {
  84                 /* swap j into place */
  85                 for (i = base, hi = base + qsz; i < hi; ) {
  86                         c = *j;
  87                         *j++ = *i;
  88                         *i++ = c;
  89                 }
  90         }
  91         /*
  92          * With our sentinel in place, we now run the following hyper-fast
  93          * insertion sort. For each remaining element, min, from [1] to [n-1],
  94          * set hi to the index of the element AFTER which this one goes.
  95          * Then, do the standard insertion sort shift on a character at a time
  96          * basis for each element in the frob.
  97          */
  98         for (min = base; (hi = min += qsz) < max; ) {
  99                 while ((*qcmp)(hi -= qsz, min) > 0)
 100                         /* void */;
 101                 if ((hi += qsz) != min) {
 102                         for (lo = min + qsz; --lo >= min; ) {
 103                                 c = *lo;
 104                                 for (i = j = lo; (j -= qsz) >= hi; i = j)
 105                                         *i = *j;
 106                                 *i = c;
 107                         }
 108                 }
 109         }
 110 }
 111
 112 /*
 113  * qst:
 114  * Do a quicksort
 115  * First, find the median element, and put that one in the first place as the
 116  * discriminator.  (This "median" is just the median of the first, last and
 117  * middle elements).  (Using this median instead of the first element is a big
 118  * win).  Then, the usual partitioning/swapping, followed by moving the
 119  * discriminator into the right place.  Then, figure out the sizes of the two
 120  * partions, do the smaller one recursively and the larger one via a repeat of
 121  * this code.  Stopping when there are less than THRESH elements in a partition
 122  * and cleaning up with an insertion sort (in our caller) is a huge win.
 123  * All data swaps are done in-line, which is space-losing but time-saving.
 124  * (And there are only three places where this is done).
 125  */
 126
 127 static void
 128 qst(char *base, char *max)
 129 {
 130         register char c, *i, *j, *jj;
 131         register int ii;
 132         char *mid, *tmp;
 133         int lo, hi;
 134
 135         /*
 136          * At the top here, lo is the number of characters of elements in the
 137          * current partition.  (Which should be max - base).
 138          * Find the median of the first, last, and middle element and make
 139          * that the middle element.  Set j to largest of first and middle.
 140          * If max is larger than that guy, then it's that guy, else compare
 141          * max with loser of first and take larger.  Things are set up to
 142          * prefer the middle, then the first in case of ties.
 143          */
 144         lo = max - base;                /* number of elements as chars */
 145         do      {
 146                 mid = i = base + qsz * ((lo / qsz) >> 1);
 147                 if (lo >= mthresh) {
 148                         j = ((*qcmp)((jj = base), i) > 0 ? jj : i);
 149                         if ((*qcmp)(j, (tmp = max - qsz)) > 0) {
 150                                 /* switch to first loser */
 151                                 j = (j == jj ? i : jj);
 152                                 if ((*qcmp)(j, tmp) < 0)
 153                                         j = tmp;
 154                         }
 155                         if (j != i) {
 156                                 ii = qsz;
 157                                 do      {
 158                                         c = *i;
 159                                         *i++ = *j;
 160                                         *j++ = c;
 161                                 } while (--ii);
 162                         }
 163                 }
 164                 /*
 165                  * Semi-standard quicksort partitioning/swapping
 166                  */
 167                 for (i = base, j = max - qsz; ; ) {
 168                         while (i < mid && (*qcmp)(i, mid) <= 0)
 169                                 i += qsz;
 170                         while (j > mid) {
 171                                 if ((*qcmp)(mid, j) <= 0) {
 172                                         j -= qsz;
 173                                         continue;
 174                                 }
 175                                 tmp = i + qsz;  /* value of i after swap */
 176                                 if (i == mid) {
 177                                         /* j <-> mid, new mid is j */
 178                                         mid = jj = j;
 179                                 } else {
 180                                         /* i <-> j */
 181                                         jj = j;
 182                                         j -= qsz;
 183                                 }
 184                                 goto swap;
 185                         }
 186                         if (i == mid) {
 187                                 break;
 188                         } else {
 189                                 /* i <-> mid, new mid is i */
 190                                 jj = mid;
 191                                 tmp = mid = i;  /* value of i after swap */
 192                                 j -= qsz;
 193                         }
 194                 swap:
 195                         ii = qsz;
 196                         do      {
 197                                 c = *i;
 198                                 *i++ = *jj;
 199                                 *jj++ = c;
 200                         } while (--ii);
 201                         i = tmp;
 202                 }
 203                 /*
 204                  * Look at sizes of the two partitions, do the smaller
 205                  * one first by recursion, then do the larger one by
 206                  * making sure lo is its size, base and max are update
 207                  * correctly, and branching back.  But only repeat
 208                  * (recursively or by branching) if the partition is
 209                  * of at least size THRESH.
 210                  */
 211                 i = (j = mid) + qsz;
 212                 if ((lo = j - base) <= (hi = max - i)) {
 213                         if (lo >= thresh)
 214                                 qst(base, j);
 215                         base = i;
 216                         lo = hi;
 217                 } else {
 218                         if (hi >= thresh)
 219                                 qst(i, max);
 220                         max = j;
 221                 }
 222         } while (lo >= thresh);
 223 }
 224
 225 /*---------------------------------------------------------------------------*/
 226 /* Static function prototypes                                                */
 227 /*---------------------------------------------------------------------------*/
 228