1 /** @file
2 Quick Sort utility function.
3
4 This utility makes use of a comparison function to search arrays of
5 unspecified type. Where an argument declared as size_t nmemb specifies the
6 length of the array for a function, nmemb can have the value zero on a call
7 to that function; the comparison function is not called, a search finds no
8 matching element. Pointer arguments on such a call shall still have valid
9 values.
10
11 The implementation shall ensure that both arguments of the comparison
12 function are pointers to elements of the array.
13
14 The comparison function shall not alter the contents of the array. The
15 implementation may reorder elements of the array between calls to the
16 comparison function, but shall not alter the contents of any individual
17 element.
18
19 When the same objects (consisting of size bytes, irrespective of their
20 current positions in the array) are passed more than once to the comparison
21 function, the results shall be consistent with one another. That is, they
22 define a total ordering on the array.
23
24 A sequence point occurs immediately before and immediately after each call to
25 the comparison function, and also between any call to the comparison function
26 and any movement of the objects passed as arguments to that call.
27
28 Copyright (c) 2010, Intel Corporation. All rights reserved.<BR>
29 * Copyright (c) 1992, 1993
30 * The Regents of the University of California. All rights reserved.
31 *
32 * Redistribution and use in source and binary forms, with or without
33 * modification, are permitted provided that the following conditions
34 * are met:
35 * 1. Redistributions of source code must retain the above copyright
36 * notice, this list of conditions and the following disclaimer.
37 * 2. Redistributions in binary form must reproduce the above copyright
38 * notice, this list of conditions and the following disclaimer in the
39 * documentation and/or other materials provided with the distribution.
40 * 4. Neither the name of the University nor the names of its contributors
41 * may be used to endorse or promote products derived from this software
42 * without specific prior written permission.
43 *
44 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
45 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
46 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
47 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
48 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
49 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
50 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
51 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
52 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
53 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
54 * SUCH DAMAGE.
55
56 ("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15.2.1.2.1 2009/10/25 01:10:29 kensmith Exp $");
57 */
58 #include <LibConfig.h>
59
60 #include <stdlib.h>
61
62 typedef int cmp_t(const void *, const void *);
63
64 static __inline char *med3(char *, char *, char *, cmp_t *);
65 static __inline void swapfunc(char *, char *, size_t, int);
66
67 /*
68 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
69 */
70 #define swapcode(TYPE, parmi, parmj, n) { \
71 size_t i = (n) / sizeof (TYPE); \
72 TYPE *pi = (TYPE *) (parmi); \
73 TYPE *pj = (TYPE *) (parmj); \
74 do { \
75 TYPE t = *pi; \
76 *pi++ = *pj; \
77 *pj++ = t; \
78 } while (--i > 0); \
79 }
80
81 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
82 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
83
84 static __inline void
swapfunc(char * a,char * b,size_t n,int swaptype)85 swapfunc(char *a, char *b, size_t n, int swaptype)
86 {
87 if(swaptype <= 1)
88 swapcode(long, a, b, n)
89 else
90 swapcode(char, a, b, n)
91 }
92
93 #define swap(a, b) \
94 if (swaptype == 0) { \
95 long t = *(long *)(a); \
96 *(long *)(a) = *(long *)(b); \
97 *(long *)(b) = t; \
98 } else \
99 swapfunc(a, b, es, swaptype)
100
101 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
102
103 static __inline char *
med3(char * a,char * b,char * c,cmp_t * cmp)104 med3(char *a, char *b, char *c, cmp_t *cmp )
105 {
106 return cmp(a, b) < 0 ?
107 (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
108 :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
109 }
110
111 /* The qsort function sorts an array of nmemb objects, the initial element of
112 which is pointed to by base. The size of each object is specified by size.
113
114 The contents of the array are sorted into ascending order according to a
115 comparison function pointed to by compar, which is called with two
116 arguments that point to the objects being compared. The function shall
117 return an integer less than, equal to, or greater than zero if the first
118 argument is considered to be respectively less than, equal to, or greater
119 than the second.
120
121 If two elements compare as equal, their order in the resulting sorted array
122 is unspecified.
123 */
124 void
qsort(void * a,size_t n,size_t es,cmp_t * cmp)125 qsort(void *a, size_t n, size_t es, cmp_t *cmp)
126 {
127 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
128 size_t d, r;
129 int cmp_result;
130 int swaptype, swap_cnt;
131
132 loop: SWAPINIT(a, es);
133 swap_cnt = 0;
134 if (n < 7) {
135 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
136 for (pl = pm;
137 pl > (char *)a && cmp(pl - es, pl) > 0;
138 pl -= es)
139 swap(pl, pl - es);
140 return;
141 }
142 pm = (char *)a + (n / 2) * es;
143 if (n > 7) {
144 pl = a;
145 pn = (char *)a + (n - 1) * es;
146 if (n > 40) {
147 d = (n / 8) * es;
148 pl = med3(pl, pl + d, pl + 2 * d, cmp);
149 pm = med3(pm - d, pm, pm + d, cmp);
150 pn = med3(pn - 2 * d, pn - d, pn, cmp);
151 }
152 pm = med3(pl, pm, pn, cmp);
153 }
154 swap(a, pm);
155 pa = pb = (char *)a + es;
156
157 pc = pd = (char *)a + (n - 1) * es;
158 for (;;) {
159 while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
160 if (cmp_result == 0) {
161 swap_cnt = 1;
162 swap(pa, pb);
163 pa += es;
164 }
165 pb += es;
166 }
167 while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
168 if (cmp_result == 0) {
169 swap_cnt = 1;
170 swap(pc, pd);
171 pd -= es;
172 }
173 pc -= es;
174 }
175 if (pb > pc)
176 break;
177 swap(pb, pc);
178 swap_cnt = 1;
179 pb += es;
180 pc -= es;
181 }
182 if (swap_cnt == 0) { /* Switch to insertion sort */
183 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
184 for (pl = pm;
185 pl > (char *)a && cmp(pl - es, pl) > 0;
186 pl -= es)
187 swap(pl, pl - es);
188 return;
189 }
190
191 pn = (char *)a + n * es;
192 r = MIN(pa - (char *)a, pb - pa);
193 vecswap(a, pb - r, r);
194 r = MIN((size_t)(pd - pc), ((size_t)(pn - pd)) - es);
195 vecswap(pb, pn - r, r);
196 if ((size_t)(r = pb - pa) > es)
197 qsort(a, r / es, es, cmp);
198 if ((size_t)(r = pd - pc) > es) {
199 /* Iterate rather than recurse to save stack space */
200 a = pn - r;
201 n = r / es;
202 goto loop;
203 }
204 /* qsort(pn - r, r / es, es, cmp);*/
205 }
206