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