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