[13] | 1 | /**CFile*********************************************************************** |
---|
| 2 | |
---|
| 3 | FileName [qsort.c] |
---|
| 4 | |
---|
| 5 | PackageName [util] |
---|
| 6 | |
---|
| 7 | Synopsis [Our own qsort routine.] |
---|
| 8 | |
---|
| 9 | Author [] |
---|
| 10 | |
---|
| 11 | Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. |
---|
| 12 | All rights reserved. |
---|
| 13 | |
---|
| 14 | Permission is hereby granted, without written agreement and without license |
---|
| 15 | or royalty fees, to use, copy, modify, and distribute this software and its |
---|
| 16 | documentation for any purpose, provided that the above copyright notice and |
---|
| 17 | the following two paragraphs appear in all copies of this software. |
---|
| 18 | |
---|
| 19 | IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR |
---|
| 20 | DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT |
---|
| 21 | OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF |
---|
| 22 | CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
---|
| 23 | |
---|
| 24 | THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, |
---|
| 25 | INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND |
---|
| 26 | FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN |
---|
| 27 | "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE |
---|
| 28 | MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.] |
---|
| 29 | |
---|
| 30 | ******************************************************************************/ |
---|
| 31 | |
---|
| 32 | #include "util.h" |
---|
| 33 | |
---|
| 34 | #ifndef lint |
---|
| 35 | static char rcsid[] UNUSED = "$Id: qsort.c,v 1.5 2002/08/25 05:30:13 fabio Exp $"; |
---|
| 36 | #endif |
---|
| 37 | |
---|
| 38 | #define THRESH 4 /* threshold for insertion */ |
---|
| 39 | #define MTHRESH 6 /* threshold for median */ |
---|
| 40 | |
---|
| 41 | static int (*qcmp)(const void *, const void *); |
---|
| 42 | /* the comparison routine */ |
---|
| 43 | static int qsz; /* size of each record */ |
---|
| 44 | static int thresh; /* THRESHold in chars */ |
---|
| 45 | static int mthresh; /* MTHRESHold in chars */ |
---|
| 46 | static void qst ARGS((char *base, char *max)); |
---|
| 47 | |
---|
| 48 | /*---------------------------------------------------------------------------*/ |
---|
| 49 | /* Definition of exported functions */ |
---|
| 50 | /*---------------------------------------------------------------------------*/ |
---|
| 51 | |
---|
| 52 | #undef min |
---|
| 53 | #undef max |
---|
| 54 | /**Function******************************************************************** |
---|
| 55 | |
---|
| 56 | Synopsis [Own version of the system qsort routine.] |
---|
| 57 | |
---|
| 58 | Description [The THRESHold below is the insertion sort threshold, and has |
---|
| 59 | been adjusted for records of size 48 bytes. The MTHREShold is where we stop |
---|
| 60 | finding a better median. First, set up some global parameters for qst to |
---|
| 61 | share. Then, quicksort with qst(), and then a cleanup insertion sort |
---|
| 62 | ourselves. Sound simple? It's not...] |
---|
| 63 | |
---|
| 64 | SideEffects [] |
---|
| 65 | |
---|
| 66 | SeeAlso [qst] |
---|
| 67 | |
---|
| 68 | ******************************************************************************/ |
---|
| 69 | void |
---|
| 70 | qsort( |
---|
| 71 | void *vbase, |
---|
| 72 | size_t n, |
---|
| 73 | size_t size, |
---|
| 74 | int (*compar)(const void *, const void *)) |
---|
| 75 | { |
---|
| 76 | register char c, *i, *j, *lo, *hi; |
---|
| 77 | char *min, *max, *base; |
---|
| 78 | |
---|
| 79 | if (n <= 1) |
---|
| 80 | return; |
---|
| 81 | base = (char *) vbase; |
---|
| 82 | qsz = size; |
---|
| 83 | qcmp = compar; |
---|
| 84 | thresh = qsz * THRESH; |
---|
| 85 | mthresh = qsz * MTHRESH; |
---|
| 86 | max = base + n * qsz; |
---|
| 87 | if (n >= THRESH) { |
---|
| 88 | qst(base, max); |
---|
| 89 | hi = base + thresh; |
---|
| 90 | } else { |
---|
| 91 | hi = max; |
---|
| 92 | } |
---|
| 93 | /* |
---|
| 94 | * First put smallest element, which must be in the first THRESH, in |
---|
| 95 | * the first position as a sentinel. This is done just by searching |
---|
| 96 | * the first THRESH elements (or the first n if n < THRESH), finding |
---|
| 97 | * the min, and swapping it into the first position. |
---|
| 98 | */ |
---|
| 99 | for (j = lo = base; (lo += qsz) < hi; ) |
---|
| 100 | if ((*qcmp)(j, lo) > 0) |
---|
| 101 | j = lo; |
---|
| 102 | if (j != base) { |
---|
| 103 | /* swap j into place */ |
---|
| 104 | for (i = base, hi = base + qsz; i < hi; ) { |
---|
| 105 | c = *j; |
---|
| 106 | *j++ = *i; |
---|
| 107 | *i++ = c; |
---|
| 108 | } |
---|
| 109 | } |
---|
| 110 | /* |
---|
| 111 | * With our sentinel in place, we now run the following hyper-fast |
---|
| 112 | * insertion sort. For each remaining element, min, from [1] to [n-1], |
---|
| 113 | * set hi to the index of the element AFTER which this one goes. |
---|
| 114 | * Then, do the standard insertion sort shift on a character at a time |
---|
| 115 | * basis for each element in the frob. |
---|
| 116 | */ |
---|
| 117 | for (min = base; (hi = min += qsz) < max; ) { |
---|
| 118 | while ((*qcmp)(hi -= qsz, min) > 0) |
---|
| 119 | /* void */; |
---|
| 120 | if ((hi += qsz) != min) { |
---|
| 121 | for (lo = min + qsz; --lo >= min; ) { |
---|
| 122 | c = *lo; |
---|
| 123 | for (i = j = lo; (j -= qsz) >= hi; i = j) |
---|
| 124 | *i = *j; |
---|
| 125 | *i = c; |
---|
| 126 | } |
---|
| 127 | } |
---|
| 128 | } |
---|
| 129 | } |
---|
| 130 | |
---|
| 131 | /*---------------------------------------------------------------------------*/ |
---|
| 132 | /* Definition of static functions */ |
---|
| 133 | /*---------------------------------------------------------------------------*/ |
---|
| 134 | |
---|
| 135 | /**Function******************************************************************** |
---|
| 136 | |
---|
| 137 | Synopsis [Effectively perform qsort] |
---|
| 138 | |
---|
| 139 | Description [First, find the median element, and put that one in the first |
---|
| 140 | place as the discriminator. (This "median" is just the median of the first, |
---|
| 141 | last and middle elements). (Using this median instead of the first element |
---|
| 142 | is a big win). Then, the usual partitioning/swapping, followed by moving the |
---|
| 143 | discriminator into the right place. Then, figure out the sizes of the two |
---|
| 144 | partions, do the smaller one recursively and the larger one via a repeat of |
---|
| 145 | this code. Stopping when there are less than THRESH elements in a partition |
---|
| 146 | and cleaning up with an insertion sort (in our caller) is a huge win. All |
---|
| 147 | data swaps are done in-line, which is space-losing but time-saving. (And |
---|
| 148 | there are only three places where this is done).] |
---|
| 149 | |
---|
| 150 | SideEffects [] |
---|
| 151 | |
---|
| 152 | SeeAlso [qsort] |
---|
| 153 | |
---|
| 154 | ******************************************************************************/ |
---|
| 155 | static void |
---|
| 156 | qst(char *base, char *max) |
---|
| 157 | { |
---|
| 158 | register char c, *i, *j, *jj; |
---|
| 159 | register int ii; |
---|
| 160 | char *mid, *tmp; |
---|
| 161 | int lo, hi; |
---|
| 162 | |
---|
| 163 | /* |
---|
| 164 | * At the top here, lo is the number of characters of elements in the |
---|
| 165 | * current partition. (Which should be max - base). |
---|
| 166 | * Find the median of the first, last, and middle element and make |
---|
| 167 | * that the middle element. Set j to largest of first and middle. |
---|
| 168 | * If max is larger than that guy, then it's that guy, else compare |
---|
| 169 | * max with loser of first and take larger. Things are set up to |
---|
| 170 | * prefer the middle, then the first in case of ties. |
---|
| 171 | */ |
---|
| 172 | lo = max - base; /* number of elements as chars */ |
---|
| 173 | do { |
---|
| 174 | mid = i = base + qsz * ((lo / qsz) >> 1); |
---|
| 175 | if (lo >= mthresh) { |
---|
| 176 | j = ((*qcmp)((jj = base), i) > 0 ? jj : i); |
---|
| 177 | if ((*qcmp)(j, (tmp = max - qsz)) > 0) { |
---|
| 178 | /* switch to first loser */ |
---|
| 179 | j = (j == jj ? i : jj); |
---|
| 180 | if ((*qcmp)(j, tmp) < 0) |
---|
| 181 | j = tmp; |
---|
| 182 | } |
---|
| 183 | if (j != i) { |
---|
| 184 | ii = qsz; |
---|
| 185 | do { |
---|
| 186 | c = *i; |
---|
| 187 | *i++ = *j; |
---|
| 188 | *j++ = c; |
---|
| 189 | } while (--ii); |
---|
| 190 | } |
---|
| 191 | } |
---|
| 192 | /* |
---|
| 193 | * Semi-standard quicksort partitioning/swapping |
---|
| 194 | */ |
---|
| 195 | for (i = base, j = max - qsz; ; ) { |
---|
| 196 | while (i < mid && (*qcmp)(i, mid) <= 0) |
---|
| 197 | i += qsz; |
---|
| 198 | while (j > mid) { |
---|
| 199 | if ((*qcmp)(mid, j) <= 0) { |
---|
| 200 | j -= qsz; |
---|
| 201 | continue; |
---|
| 202 | } |
---|
| 203 | tmp = i + qsz; /* value of i after swap */ |
---|
| 204 | if (i == mid) { |
---|
| 205 | /* j <-> mid, new mid is j */ |
---|
| 206 | mid = jj = j; |
---|
| 207 | } else { |
---|
| 208 | /* i <-> j */ |
---|
| 209 | jj = j; |
---|
| 210 | j -= qsz; |
---|
| 211 | } |
---|
| 212 | goto swap; |
---|
| 213 | } |
---|
| 214 | if (i == mid) { |
---|
| 215 | break; |
---|
| 216 | } else { |
---|
| 217 | /* i <-> mid, new mid is i */ |
---|
| 218 | jj = mid; |
---|
| 219 | tmp = mid = i; /* value of i after swap */ |
---|
| 220 | j -= qsz; |
---|
| 221 | } |
---|
| 222 | swap: |
---|
| 223 | ii = qsz; |
---|
| 224 | do { |
---|
| 225 | c = *i; |
---|
| 226 | *i++ = *jj; |
---|
| 227 | *jj++ = c; |
---|
| 228 | } while (--ii); |
---|
| 229 | i = tmp; |
---|
| 230 | } |
---|
| 231 | /* |
---|
| 232 | * Look at sizes of the two partitions, do the smaller |
---|
| 233 | * one first by recursion, then do the larger one by |
---|
| 234 | * making sure lo is its size, base and max are update |
---|
| 235 | * correctly, and branching back. But only repeat |
---|
| 236 | * (recursively or by branching) if the partition is |
---|
| 237 | * of at least size THRESH. |
---|
| 238 | */ |
---|
| 239 | i = (j = mid) + qsz; |
---|
| 240 | if ((lo = j - base) <= (hi = max - i)) { |
---|
| 241 | if (lo >= thresh) |
---|
| 242 | qst(base, j); |
---|
| 243 | base = i; |
---|
| 244 | lo = hi; |
---|
| 245 | } else { |
---|
| 246 | if (hi >= thresh) |
---|
| 247 | qst(i, max); |
---|
| 248 | max = j; |
---|
| 249 | } |
---|
| 250 | } while (lo >= thresh); |
---|
| 251 | } |
---|