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