1 /*
2 FUNCTION
3 <<qsort>>---sort an array
4
5 INDEX
6 qsort
7
8 SYNOPSIS
9 #include <stdlib.h>
10 void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>,
11 int (*<[compar]>)(const void *, const void *) );
12
13 DESCRIPTION
14 <<qsort>> sorts an array (beginning at <[base]>) of <[nmemb]> objects.
15 <[size]> describes the size of each element of the array.
16
17 You must supply a pointer to a comparison function, using the argument
18 shown as <[compar]>. (This permits sorting objects of unknown
19 properties.) Define the comparison function to accept two arguments,
20 each a pointer to an element of the array starting at <[base]>. The
21 result of <<(*<[compar]>)>> must be negative if the first argument is
22 less than the second, zero if the two arguments match, and positive if
23 the first argument is greater than the second (where ``less than'' and
24 ``greater than'' refer to whatever arbitrary ordering is appropriate).
25
26 The array is sorted in place; that is, when <<qsort>> returns, the
27 array elements beginning at <[base]> have been reordered.
28
29 RETURNS
30 <<qsort>> does not return a result.
31
32 PORTABILITY
33 <<qsort>> is required by ANSI (without specifying the sorting algorithm).
34 */
35
36 /*-
37 * Copyright (c) 1992, 1993
38 * The Regents of the University of California. All rights reserved.
39 *
40 * Redistribution and use in source and binary forms, with or without
41 * modification, are permitted provided that the following conditions
42 * are met:
43 * 1. Redistributions of source code must retain the above copyright
44 * notice, this list of conditions and the following disclaimer.
45 * 2. Redistributions in binary form must reproduce the above copyright
46 * notice, this list of conditions and the following disclaimer in the
47 * documentation and/or other materials provided with the distribution.
48 * 3. Neither the name of the University nor the names of its contributors
49 * may be used to endorse or promote products derived from this software
50 * without specific prior written permission.
51 *
52 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
53 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
54 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
55 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
56 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
57 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
58 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
59 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
60 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
61 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62 * SUCH DAMAGE.
63 */
64
65 #include <_ansi.h>
66 #include <sys/cdefs.h>
67 #include <stdlib.h>
68 #include <stdint.h>
69
70 #ifndef __GNUC__
71 #define inline
72 #endif
73
74 #if defined(I_AM_QSORT_R)
75 typedef int cmp_t(void *, const void *, const void *);
76 #elif defined(I_AM_GNU_QSORT_R)
77 typedef int cmp_t(const void *, const void *, void *);
78 #else
79 typedef int cmp_t(const void *, const void *);
80 #endif
81 static inline char *med3 (char *, char *, char *, cmp_t *, void *);
82 static inline void swapfunc (char *, char *, size_t, int);
83
84 #define min(a, b) (a) < (b) ? a : b
85
86 /*
87 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
88 */
89 #define swapcode(TYPE, parmi, parmj, n) { \
90 size_t i = (n) / sizeof (TYPE); \
91 TYPE *pi = (TYPE *) (parmi); \
92 TYPE *pj = (TYPE *) (parmj); \
93 do { \
94 TYPE t = *pi; \
95 *pi++ = *pj; \
96 *pj++ = t; \
97 } while (--i > 0); \
98 }
99
100 #define SWAPINIT(a, es) swaptype = ((uintptr_t)(a) % sizeof(long)) || \
101 ((es) % sizeof(long)) ? 2 : ((es) == sizeof(long)) ? 0 : 1
102
103 static inline void
swapfunc(char * a,char * b,size_t n,int swaptype)104 swapfunc (char *a,
105 char *b,
106 size_t n,
107 int swaptype)
108 {
109 if(swaptype <= 1)
110 swapcode(long, a, b, n)
111 else
112 swapcode(char, a, b, n)
113 }
114
115 #define swap(a, b) \
116 if (swaptype == 0) { \
117 long t = *(long *)(a); \
118 *(long *)(a) = *(long *)(b); \
119 *(long *)(b) = t; \
120 } else \
121 swapfunc(a, b, es, swaptype)
122
123 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
124
125 #if defined(I_AM_QSORT_R)
126 #define CMP(t, x, y) (cmp((t), (x), (y)))
127 #elif defined(I_AM_GNU_QSORT_R)
128 #define CMP(t, x, y) (cmp((x), (y), (t)))
129 #else
130 #define CMP(t, x, y) (cmp((x), (y)))
131 #endif
132
133 static inline char *
med3(char * a,char * b,char * c,cmp_t * cmp,void * thunk __unused)134 med3 (char *a,
135 char *b,
136 char *c,
137 cmp_t *cmp,
138 void *thunk
139 #if !defined(I_AM_QSORT_R) && !defined(I_AM_GNU_QSORT_R)
140 __unused
141 #endif
142 )
143 {
144 return CMP(thunk, a, b) < 0 ?
145 (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
146 :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
147 }
148
149 /*
150 * Classical function call recursion wastes a lot of stack space. Each
151 * recursion level requires a full stack frame comprising all local variables
152 * and additional space as dictated by the processor calling convention.
153 *
154 * This implementation instead stores the variables that are unique for each
155 * recursion level in a parameter stack array, and uses iteration to emulate
156 * recursion. Function call recursion is not used until the array is full.
157 *
158 * To ensure the stack consumption isn't worsened by this design, the size of
159 * the parameter stack array is chosen to be similar to the stack frame
160 * excluding the array. Each function call recursion level can handle this
161 * number of iterative recursion levels.
162 */
163 #define PARAMETER_STACK_LEVELS 8u
164
165 #if defined(I_AM_QSORT_R)
166 void
__bsd_qsort_r(void * a,size_t n,size_t es,void * thunk,cmp_t * cmp)167 __bsd_qsort_r (void *a,
168 size_t n,
169 size_t es,
170 void *thunk,
171 cmp_t *cmp)
172 #elif defined(I_AM_GNU_QSORT_R)
173 void
174 qsort_r (void *a,
175 size_t n,
176 size_t es,
177 cmp_t *cmp,
178 void *thunk)
179 #else
180 #define thunk NULL
181 void
182 qsort (void *a,
183 size_t n,
184 size_t es,
185 cmp_t *cmp)
186 #endif
187 {
188 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
189 size_t d, r;
190 int cmp_result;
191 int swaptype, swap_cnt;
192 size_t recursion_level = 0;
193 struct { void *a; size_t n; } parameter_stack[PARAMETER_STACK_LEVELS];
194
195 SWAPINIT(a, es);
196 loop: swap_cnt = 0;
197 if (n < 7) {
198 /* Short arrays are insertion sorted. */
199 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
200 for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
201 pl -= es)
202 swap(pl, pl - es);
203 goto pop;
204 }
205
206 /* Select a pivot element, move it to the left. */
207 pm = (char *) a + (n / 2) * es;
208 if (n > 7) {
209 pl = a;
210 pn = (char *) a + (n - 1) * es;
211 if (n > 40) {
212 d = (n / 8) * es;
213 pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
214 pm = med3(pm - d, pm, pm + d, cmp, thunk);
215 pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
216 }
217 pm = med3(pl, pm, pn, cmp, thunk);
218 }
219 swap(a, pm);
220
221 /*
222 * Sort the array relative the pivot in four ranges as follows:
223 * { elems == pivot, elems < pivot, elems > pivot, elems == pivot }
224 */
225 pa = pb = (char *) a + es;
226 pc = pd = (char *) a + (n - 1) * es;
227 for (;;) {
228 /* Scan left to right stopping at first element > pivot. */
229 while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
230 /* Move elements == pivot to the left (to pa) */
231 if (cmp_result == 0) {
232 swap_cnt = 1;
233 swap(pa, pb);
234 pa += es;
235 }
236 pb += es;
237 }
238 /* Scan right to left stopping at first element < pivot. */
239 while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
240 /* Move elements == pivot to the right (to pd) */
241 if (cmp_result == 0) {
242 swap_cnt = 1;
243 swap(pc, pd);
244 pd -= es;
245 }
246 pc -= es;
247 }
248 if (pb > pc)
249 break;
250 /* The scan has found two elements to swap with each other. */
251 swap(pb, pc);
252 swap_cnt = 1;
253 pb += es;
254 pc -= es;
255 }
256 if (swap_cnt == 0) { /* Switch to insertion sort */
257 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
258 for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
259 pl -= es)
260 swap(pl, pl - es);
261 goto pop;
262 }
263
264 /*
265 * Rearrange the array in three parts sorted like this:
266 * { elements < pivot, elements == pivot, elements > pivot }
267 */
268 pn = (char *) a + n * es;
269 r = min(pa - (char *)a, pb - pa);
270 vecswap(a, pb - r, r);
271 r = min((size_t) (pd - pc), (size_t) (pn - pd) - es);
272 vecswap(pb, pn - r, r);
273 d = pb - pa; /* d = Size of left part. */
274 r = pd - pc; /* r = Size of right part. */
275 pn -= r; /* pn = Base of right part. */
276
277 /*
278 * Check which of the left and right parts are larger.
279 * Set (a, n) to (base, size) of the larger part.
280 * Set (pa, r) to (base, size) of the smaller part.
281 */
282 if (r > d) { /* Right part is the larger part */
283 pa = a;
284 a = pn;
285 n = r;
286 r = d;
287 }
288 else { /* Left part is the larger part, or both are equal. */
289 pa = pn;
290 n = d;
291 }
292
293 /*
294 * The left and right parts each need further sorting if they
295 * contain two elements or more. If both need sorting we use
296 * recursion to sort the smaller part and save the larger part
297 * to be sorted by iteration after the recursion.
298 * Using recursion only for the smaller part guarantees a
299 * recursion depth that is bounded to be less than (log2(n)).
300 */
301 if (r > es) { /* Smaller part > 1 element. Both parts need sorting. */
302 if (recursion_level < PARAMETER_STACK_LEVELS) {
303 /*
304 * The smaller part needs to be recursively sorted
305 * before the larger part is sorted. To avoid function
306 * call recursion the parameters for the larger part
307 * are pushed on the parameter_stack array. The smaller
308 * part is sorted using iteration and the larger part
309 * will be sorted when the parameter_stack is popped
310 * after the smaller part has been sorted.
311 */
312 parameter_stack[recursion_level].a = a;
313 parameter_stack[recursion_level].n = n / es;
314 recursion_level++;
315 a = pa;
316 n = r / es;
317 goto loop;
318 }
319 else {
320 /*
321 * The parameter_stack array is full. The smaller part
322 * is sorted using function call recursion. The larger
323 * part will be sorted after the function call returns.
324 */
325 #if defined(I_AM_QSORT_R)
326 __bsd_qsort_r(pa, r / es, es, thunk, cmp);
327 #elif defined(I_AM_GNU_QSORT_R)
328 qsort_r(pa, r / es, es, cmp, thunk);
329 #else
330 qsort(pa, r / es, es, cmp);
331 #endif
332 }
333 }
334 if (n > es) { /* The larger part needs sorting. Iterate to sort. */
335 n = n / es;
336 goto loop;
337 }
338 /* Both left and right parts are one element or less - level done. */
339 pop:
340 if (recursion_level != 0) {
341 recursion_level--;
342 a = parameter_stack[recursion_level].a;
343 n = parameter_stack[recursion_level].n;
344 goto loop;
345 }
346 }
347
