2.11BSD#431 - /usr/src/lib/libc/gen/qsort.c

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

Defined functions

Defined variables

Defined macros