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