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