Rev 4874 | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 4874 | Rev 6099 | ||
---|---|---|---|
Line 51... | Line 51... | ||
51 | * 1. Redistributions of source code must retain the above copyright |
51 | * 1. Redistributions of source code must retain the above copyright |
52 | * notice, this list of conditions and the following disclaimer. |
52 | * notice, this list of conditions and the following disclaimer. |
53 | * 2. Redistributions in binary form must reproduce the above copyright |
53 | * 2. Redistributions in binary form must reproduce the above copyright |
54 | * notice, this list of conditions and the following disclaimer in the |
54 | * notice, this list of conditions and the following disclaimer in the |
55 | * documentation and/or other materials provided with the distribution. |
55 | * documentation and/or other materials provided with the distribution. |
56 | * 3. All advertising materials mentioning features or use of this software |
- | |
57 | * must display the following acknowledgement: |
- | |
58 | * This product includes software developed by the University of |
- | |
59 | * California, Berkeley and its contributors. |
- | |
60 | * 4. Neither the name of the University nor the names of its contributors |
56 | * 3. Neither the name of the University nor the names of its contributors |
61 | * may be used to endorse or promote products derived from this software |
57 | * may be used to endorse or promote products derived from this software |
62 | * without specific prior written permission. |
58 | * without specific prior written permission. |
63 | * |
59 | * |
64 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
60 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
65 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
61 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
Line 73... | Line 69... | ||
73 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
69 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
74 | * SUCH DAMAGE. |
70 | * SUCH DAMAGE. |
75 | */ |
71 | */ |
Line 76... | Line 72... | ||
76 | 72 | ||
- | 73 | #include <_ansi.h> |
|
77 | #include <_ansi.h> |
74 | #include |
Line 78... | Line 75... | ||
78 | #include |
75 | #include |
79 | 76 | ||
80 | #ifndef __GNUC__ |
77 | #ifndef __GNUC__ |
Line -... | Line 78... | ||
- | 78 | #define inline |
|
- | 79 | #endif |
|
- | 80 | ||
- | 81 | #if defined(I_AM_QSORT_R) |
|
- | 82 | typedef int cmp_t(void *, const void *, const void *); |
|
- | 83 | #elif defined(I_AM_GNU_QSORT_R) |
|
- | 84 | typedef int cmp_t(const void *, const void *, void *); |
|
81 | #define inline |
85 | #else |
82 | #endif |
86 | typedef int cmp_t(const void *, const void *); |
Line 83... | Line 87... | ||
83 | 87 | #endif |
|
Line 84... | Line 88... | ||
84 | static inline char *med3 _PARAMS((char *, char *, char *, int (*)())); |
88 | static inline char *med3 _PARAMS((char *, char *, char *, cmp_t *, void *)); |
85 | static inline void swapfunc _PARAMS((char *, char *, int, int)); |
89 | static inline void swapfunc _PARAMS((char *, char *, int, int)); |
86 | 90 | ||
87 | #define min(a, b) (a) < (b) ? a : b |
91 | #define min(a, b) (a) < (b) ? a : b |
88 | 92 | ||
89 | /* |
93 | /* |
90 | * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". |
94 | * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". |
91 | */ |
95 | */ |
92 | #define swapcode(TYPE, parmi, parmj, n) { \ |
96 | #define swapcode(TYPE, parmi, parmj, n) { \ |
93 | long i = (n) / sizeof (TYPE); \ |
97 | long i = (n) / sizeof (TYPE); \ |
94 | register TYPE *pi = (TYPE *) (parmi); \ |
98 | TYPE *pi = (TYPE *) (parmi); \ |
95 | register TYPE *pj = (TYPE *) (parmj); \ |
99 | TYPE *pj = (TYPE *) (parmj); \ |
96 | do { \ |
100 | do { \ |
Line 124... | Line 128... | ||
124 | } else \ |
128 | } else \ |
125 | swapfunc(a, b, es, swaptype) |
129 | swapfunc(a, b, es, swaptype) |
Line 126... | Line 130... | ||
126 | 130 | ||
Line -... | Line 131... | ||
- | 131 | #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) |
|
- | 132 | ||
- | 133 | #if defined(I_AM_QSORT_R) |
|
- | 134 | #define CMP(t, x, y) (cmp((t), (x), (y))) |
|
- | 135 | #elif defined(I_AM_GNU_QSORT_R) |
|
- | 136 | #define CMP(t, x, y) (cmp((x), (y), (t))) |
|
- | 137 | #else |
|
- | 138 | #define CMP(t, x, y) (cmp((x), (y))) |
|
127 | #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) |
139 | #endif |
128 | 140 | ||
129 | static inline char * |
141 | static inline char * |
130 | _DEFUN(med3, (a, b, c, cmp), |
142 | _DEFUN(med3, (a, b, c, cmp, thunk), |
131 | char *a _AND |
143 | char *a _AND |
132 | char *b _AND |
144 | char *b _AND |
- | 145 | char *c _AND |
|
- | 146 | cmp_t *cmp _AND |
|
- | 147 | void *thunk |
|
- | 148 | #if !defined(I_AM_QSORT_R) && !defined(I_AM_GNU_QSORT_R) |
|
- | 149 | __unused |
|
133 | char *c _AND |
150 | #endif |
134 | int (*cmp)()) |
151 | ) |
135 | { |
152 | { |
136 | return cmp(a, b) < 0 ? |
153 | return CMP(thunk, a, b) < 0 ? |
137 | (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) |
154 | (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) |
Line -... | Line 155... | ||
- | 155 | :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c )); |
|
- | 156 | } |
|
- | 157 | ||
- | 158 | #if defined(I_AM_QSORT_R) |
|
- | 159 | void |
|
- | 160 | _DEFUN(__bsd_qsort_r, (a, n, es, thunk, cmp), |
|
- | 161 | void *a _AND |
|
- | 162 | size_t n _AND |
|
- | 163 | size_t es _AND |
|
- | 164 | void *thunk _AND |
|
- | 165 | cmp_t *cmp) |
|
- | 166 | #elif defined(I_AM_GNU_QSORT_R) |
|
- | 167 | void |
|
- | 168 | _DEFUN(qsort_r, (a, n, es, cmp, thunk), |
|
- | 169 | void *a _AND |
|
- | 170 | size_t n _AND |
|
- | 171 | size_t es _AND |
|
- | 172 | cmp_t *cmp _AND |
|
138 | :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); |
173 | void *thunk) |
139 | } |
174 | #else |
140 | 175 | #define thunk NULL |
|
141 | void |
176 | void |
142 | _DEFUN(qsort, (a, n, es, cmp), |
177 | _DEFUN(qsort, (a, n, es, cmp), |
143 | void *a _AND |
178 | void *a _AND |
- | 179 | size_t n _AND |
|
144 | size_t n _AND |
180 | size_t es _AND |
145 | size_t es _AND |
181 | cmp_t *cmp) |
- | 182 | #endif |
|
- | 183 | { |
|
146 | int (*cmp)()) |
184 | char *pa, *pb, *pc, *pd, *pl, *pm, *pn; |
Line 147... | Line 185... | ||
147 | { |
185 | size_t d, r; |
148 | char *pa, *pb, *pc, *pd, *pl, *pm, *pn; |
186 | int cmp_result; |
149 | int d, r, swaptype, swap_cnt; |
187 | int swaptype, swap_cnt; |
150 | 188 | ||
151 | loop: SWAPINIT(a, es); |
189 | loop: SWAPINIT(a, es); |
152 | swap_cnt = 0; |
190 | swap_cnt = 0; |
153 | if (n < 7) { |
191 | if (n < 7) { |
154 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) |
192 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) |
155 | for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; |
193 | for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0; |
156 | pl -= es) |
194 | pl -= es) |
157 | swap(pl, pl - es); |
195 | swap(pl, pl - es); |
158 | return; |
196 | return; |
159 | } |
197 | } |
160 | pm = (char *) a + (n / 2) * es; |
198 | pm = (char *) a + (n / 2) * es; |
161 | if (n > 7) { |
199 | if (n > 7) { |
162 | pl = a; |
200 | pl = a; |
163 | pn = (char *) a + (n - 1) * es; |
201 | pn = (char *) a + (n - 1) * es; |
164 | if (n > 40) { |
202 | if (n > 40) { |
165 | d = (n / 8) * es; |
203 | d = (n / 8) * es; |
166 | pl = med3(pl, pl + d, pl + 2 * d, cmp); |
204 | pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk); |
167 | pm = med3(pm - d, pm, pm + d, cmp); |
205 | pm = med3(pm - d, pm, pm + d, cmp, thunk); |
168 | pn = med3(pn - 2 * d, pn - d, pn, cmp); |
206 | pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk); |
169 | } |
207 | } |
Line 170... | Line 208... | ||
170 | pm = med3(pl, pm, pn, cmp); |
208 | pm = med3(pl, pm, pn, cmp, thunk); |
171 | } |
209 | } |
172 | swap(a, pm); |
210 | swap(a, pm); |
173 | pa = pb = (char *) a + es; |
211 | pa = pb = (char *) a + es; |
174 | 212 | ||
175 | pc = pd = (char *) a + (n - 1) * es; |
213 | pc = pd = (char *) a + (n - 1) * es; |
176 | for (;;) { |
214 | for (;;) { |
177 | while (pb <= pc && (r = cmp(pb, a)) <= 0) { |
215 | while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) { |
178 | if (r == 0) { |
216 | if (cmp_result == 0) { |
179 | swap_cnt = 1; |
217 | swap_cnt = 1; |
180 | swap(pa, pb); |
218 | swap(pa, pb); |
181 | pa += es; |
219 | pa += es; |
182 | } |
220 | } |
183 | pb += es; |
221 | pb += es; |
184 | } |
222 | } |
185 | while (pb <= pc && (r = cmp(pc, a)) >= 0) { |
223 | while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) { |
186 | if (r == 0) { |
224 | if (cmp_result == 0) { |
Line 197... | Line 235... | ||
197 | pb += es; |
235 | pb += es; |
198 | pc -= es; |
236 | pc -= es; |
199 | } |
237 | } |
200 | if (swap_cnt == 0) { /* Switch to insertion sort */ |
238 | if (swap_cnt == 0) { /* Switch to insertion sort */ |
201 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) |
239 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) |
202 | for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; |
240 | for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0; |
203 | pl -= es) |
241 | pl -= es) |
204 | swap(pl, pl - es); |
242 | swap(pl, pl - es); |
205 | return; |
243 | return; |
206 | } |
244 | } |
Line 209... | Line 247... | ||
209 | r = min(pa - (char *)a, pb - pa); |
247 | r = min(pa - (char *)a, pb - pa); |
210 | vecswap(a, pb - r, r); |
248 | vecswap(a, pb - r, r); |
211 | r = min(pd - pc, pn - pd - es); |
249 | r = min(pd - pc, pn - pd - es); |
212 | vecswap(pb, pn - r, r); |
250 | vecswap(pb, pn - r, r); |
213 | if ((r = pb - pa) > es) |
251 | if ((r = pb - pa) > es) |
- | 252 | #if defined(I_AM_QSORT_R) |
|
- | 253 | __bsd_qsort_r(a, r / es, es, thunk, cmp); |
|
- | 254 | #elif defined(I_AM_GNU_QSORT_R) |
|
- | 255 | qsort_r(a, r / es, es, cmp, thunk); |
|
- | 256 | #else |
|
214 | qsort(a, r / es, es, cmp); |
257 | qsort(a, r / es, es, cmp); |
- | 258 | #endif |
|
215 | if ((r = pd - pc) > es) { |
259 | if ((r = pd - pc) > es) { |
216 | /* Iterate rather than recurse to save stack space */ |
260 | /* Iterate rather than recurse to save stack space */ |
217 | a = pn - r; |
261 | a = pn - r; |
218 | n = r / es; |
262 | n = r / es; |
219 | goto loop; |
263 | goto loop; |