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 #if defined(I_AM_QSORT_R)
66 #define _BSD_SOURCE
67 #else
68 #define _DEFAULT_SOURCE
69 #endif
70 #include <stdlib.h>
71 #include <stdint.h>
72
73 #if defined(I_AM_QSORT_R)
74 typedef int cmp_t(void *, const void *, const void *);
75 #elif defined(I_AM_GNU_QSORT_R)
76 typedef int cmp_t(const void *, const void *, void *);
77 #else
78 typedef int cmp_t(const void *, const void *);
79 #endif
80 static inline char *med3 (char *, char *, char *, cmp_t *, void *);
81 static inline void swapfunc(char *, char *, size_t, int, int);
82
83 #define min(a, b) (a) < (b) ? a : b
84
85 /*
86 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
87 */
88 #define swapcode(TYPE, parmi, parmj, n) { \
89 size_t i = (n) / sizeof (TYPE); \
90 TYPE *pi = (TYPE *) (parmi); \
91 TYPE *pj = (TYPE *) (parmj); \
92 do { \
93 TYPE t = *pi; \
94 *pi++ = *pj; \
95 *pj++ = t; \
96 } while (--i > 0); \
97 }
98
99 #define SWAPINIT(TYPE, a, es) swaptype_ ## TYPE = \
100 ((uintptr_t)(a) % sizeof(TYPE)) || \
101 ((es) % sizeof(TYPE)) ? 2 : ((es) == sizeof(TYPE)) ? 0 : 1;
102
103 static inline void
swapfunc(char * a,char * b,size_t n,int swaptype_intptr_t,int swaptype_int)104 swapfunc(char *a, char *b, size_t n, int swaptype_intptr_t, int swaptype_int)
105 {
106 if (swaptype_intptr_t <= 1)
107 swapcode(intptr_t, a, b, n)
108 else if (swaptype_int <= 1)
109 swapcode(int, a, b, n)
110 else
111 swapcode(char, a, b, n)
112 }
113
114 #define swap(a, b) \
115 if (swaptype_intptr_t == 0) { \
116 intptr_t t = *(intptr_t *)(a); \
117 *(intptr_t *)(a) = *(intptr_t *)(b); \
118 *(intptr_t *)(b) = t; \
119 } else if (swaptype_int == 0) { \
120 int t = *(int *)(a); \
121 *(int *)(a) = *(int *)(b); \
122 *(int *)(b) = t; \
123 } else \
124 swapfunc(a, b, es, swaptype_intptr_t, swaptype_int)
125
126 #define vecswap(a, b, n) \
127 if ((n) > 0) swapfunc(a, b, n, swaptype_intptr_t, swaptype_int)
128
129 #if defined(I_AM_QSORT_R)
130 #define CMP(t, x, y) (cmp((t), (x), (y)))
131 #elif defined(I_AM_GNU_QSORT_R)
132 #define CMP(t, x, y) (cmp((x), (y), (t)))
133 #else
134 #define CMP(t, x, y) (cmp((x), (y)))
135 #endif
136
137 static __inline char *
med3(char * a,char * b,char * c,cmp_t * cmp,void * thunk __unused)138 med3 (char *a,
139 char *b,
140 char *c,
141 cmp_t *cmp,
142 void *thunk
143 #if !defined(I_AM_QSORT_R) && !defined(I_AM_GNU_QSORT_R)
144 __unused
145 #endif
146 )
147 {
148 return CMP(thunk, a, b) < 0 ?
149 (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
150 :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
151 }
152
153 /*
154 * Classical function call recursion wastes a lot of stack space. Each
155 * recursion level requires a full stack frame comprising all local variables
156 * and additional space as dictated by the processor calling convention.
157 *
158 * This implementation instead stores the variables that are unique for each
159 * recursion level in a parameter stack array, and uses iteration to emulate
160 * recursion. Function call recursion is not used until the array is full.
161 *
162 * To ensure the stack consumption isn't worsened by this design, the size of
163 * the parameter stack array is chosen to be similar to the stack frame
164 * excluding the array. Each function call recursion level can handle this
165 * number of iterative recursion levels.
166 */
167 #define PARAMETER_STACK_LEVELS 8u
168
169 #if defined(I_AM_QSORT_R)
170 void
171 __bsd_qsort_r (void *a,
172 size_t n,
173 size_t es,
174 void *thunk,
175 cmp_t *cmp);
176
177 void
__bsd_qsort_r(void * a,size_t n,size_t es,void * thunk,cmp_t * cmp)178 __bsd_qsort_r (void *a,
179 size_t n,
180 size_t es,
181 void *thunk,
182 cmp_t *cmp)
183 #elif defined(I_AM_GNU_QSORT_R)
184 void
185 qsort_r (void *a,
186 size_t n,
187 size_t es,
188 cmp_t *cmp,
189 void *thunk)
190 #else
191 #define thunk NULL
192 void
193 qsort (void *a,
194 size_t n,
195 size_t es,
196 cmp_t *cmp)
197 #endif
198 {
199 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
200 size_t d, r;
201 int cmp_result;
202 int swaptype_intptr_t, swaptype_int, swap_cnt;
203 size_t recursion_level = 0;
204 struct { void *a; size_t n; } parameter_stack[PARAMETER_STACK_LEVELS];
205
206 SWAPINIT(intptr_t, a, es);
207 SWAPINIT(int, a, es);
208 loop: swap_cnt = 0;
209 if (n < 7) {
210 /* Short arrays are insertion sorted. */
211 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
212 for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
213 pl -= es)
214 swap(pl, pl - es);
215 goto pop;
216 }
217
218 /* Select a pivot element, move it to the left. */
219 pm = (char *) a + (n / 2) * es;
220 if (n > 7) {
221 pl = a;
222 pn = (char *) a + (n - 1) * es;
223 if (n > 40) {
224 d = (n / 8) * es;
225 pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
226 pm = med3(pm - d, pm, pm + d, cmp, thunk);
227 pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
228 }
229 pm = med3(pl, pm, pn, cmp, thunk);
230 }
231 swap(a, pm);
232
233 /*
234 * Sort the array relative the pivot in four ranges as follows:
235 * { elems == pivot, elems < pivot, elems > pivot, elems == pivot }
236 */
237 pa = pb = (char *) a + es;
238 pc = pd = (char *) a + (n - 1) * es;
239 for (;;) {
240 /* Scan left to right stopping at first element > pivot. */
241 while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
242 /* Move elements == pivot to the left (to pa) */
243 if (cmp_result == 0) {
244 swap_cnt = 1;
245 swap(pa, pb);
246 pa += es;
247 }
248 pb += es;
249 }
250 /* Scan right to left stopping at first element < pivot. */
251 while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
252 /* Move elements == pivot to the right (to pd) */
253 if (cmp_result == 0) {
254 swap_cnt = 1;
255 swap(pc, pd);
256 pd -= es;
257 }
258 pc -= es;
259 }
260 if (pb > pc)
261 break;
262 /* The scan has found two elements to swap with each other. */
263 swap(pb, pc);
264 swap_cnt = 1;
265 pb += es;
266 pc -= es;
267 }
268 if (swap_cnt == 0) { /* Switch to insertion sort */
269 for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
270 for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0;
271 pl -= es)
272 swap(pl, pl - es);
273 goto pop;
274 }
275
276 /*
277 * Rearrange the array in three parts sorted like this:
278 * { elements < pivot, elements == pivot, elements > pivot }
279 */
280 pn = (char *) a + n * es;
281 r = min(pa - (char *)a, pb - pa);
282 vecswap(a, pb - r, r);
283 r = min((size_t) (pd - pc), (size_t) (pn - pd) - es);
284 vecswap(pb, pn - r, r);
285 d = pb - pa; /* d = Size of left part. */
286 r = pd - pc; /* r = Size of right part. */
287 pn -= r; /* pn = Base of right part. */
288
289 /*
290 * Check which of the left and right parts are larger.
291 * Set (a, n) to (base, size) of the larger part.
292 * Set (pa, r) to (base, size) of the smaller part.
293 */
294 if (r > d) { /* Right part is the larger part */
295 pa = a;
296 a = pn;
297 n = r;
298 r = d;
299 }
300 else { /* Left part is the larger part, or both are equal. */
301 pa = pn;
302 n = d;
303 }
304
305 /*
306 * The left and right parts each need further sorting if they
307 * contain two elements or more. If both need sorting we use
308 * recursion to sort the smaller part and save the larger part
309 * to be sorted by iteration after the recursion.
310 * Using recursion only for the smaller part guarantees a
311 * recursion depth that is bounded to be less than (log2(n)).
312 */
313 if (r > es) { /* Smaller part > 1 element. Both parts need sorting. */
314 if (recursion_level < PARAMETER_STACK_LEVELS) {
315 /*
316 * The smaller part needs to be recursively sorted
317 * before the larger part is sorted. To avoid function
318 * call recursion the parameters for the larger part
319 * are pushed on the parameter_stack array. The smaller
320 * part is sorted using iteration and the larger part
321 * will be sorted when the parameter_stack is popped
322 * after the smaller part has been sorted.
323 */
324 parameter_stack[recursion_level].a = a;
325 parameter_stack[recursion_level].n = n / es;
326 recursion_level++;
327 a = pa;
328 n = r / es;
329 goto loop;
330 }
331 else {
332 /*
333 * The parameter_stack array is full. The smaller part
334 * is sorted using function call recursion. The larger
335 * part will be sorted after the function call returns.
336 */
337 #if defined(I_AM_QSORT_R)
338 __bsd_qsort_r(pa, r / es, es, thunk, cmp);
339 #elif defined(I_AM_GNU_QSORT_R)
340 qsort_r(pa, r / es, es, cmp, thunk);
341 #else
342 qsort(pa, r / es, es, cmp);
343 #endif
344 }
345 }
346 if (n > es) { /* The larger part needs sorting. Iterate to sort. */
347 n = n / es;
348 goto loop;
349 }
350 /* Both left and right parts are one element or less - level done. */
351 pop:
352 if (recursion_level != 0) {
353 recursion_level--;
354 a = parameter_stack[recursion_level].a;
355 n = parameter_stack[recursion_level].n;
356 goto loop;
357 }
358 }
359
