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 | } |
---|