Rev 4874 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4349 | Serge | 1 | /* |
2 | FUNCTION |
||
3 | < |
||
4 | |||
5 | INDEX |
||
6 | qsort |
||
7 | |||
8 | ANSI_SYNOPSIS |
||
9 | #include |
||
10 | void qsort(void *<[base]>, size_t <[nmemb]>, size_t <[size]>, |
||
11 | int (*<[compar]>)(const void *, const void *) ); |
||
12 | |||
13 | TRAD_SYNOPSIS |
||
14 | #include |
||
15 | qsort(<[base]>, <[nmemb]>, <[size]>, <[compar]> ) |
||
16 | char *<[base]>; |
||
17 | size_t <[nmemb]>; |
||
18 | size_t <[size]>; |
||
19 | int (*<[compar]>)(); |
||
20 | |||
21 | DESCRIPTION |
||
22 | < |
||
23 | <[size]> describes the size of each element of the array. |
||
24 | |||
25 | You must supply a pointer to a comparison function, using the argument |
||
26 | shown as <[compar]>. (This permits sorting objects of unknown |
||
27 | properties.) Define the comparison function to accept two arguments, |
||
28 | each a pointer to an element of the array starting at <[base]>. The |
||
29 | result of <<(*<[compar]>)>> must be negative if the first argument is |
||
30 | less than the second, zero if the two arguments match, and positive if |
||
31 | the first argument is greater than the second (where ``less than'' and |
||
32 | ``greater than'' refer to whatever arbitrary ordering is appropriate). |
||
33 | |||
34 | The array is sorted in place; that is, when < |
||
35 | array elements beginning at <[base]> have been reordered. |
||
36 | |||
37 | RETURNS |
||
38 | < |
||
39 | |||
40 | PORTABILITY |
||
41 | < |
||
42 | */ |
||
43 | |||
44 | /*- |
||
45 | * Copyright (c) 1992, 1993 |
||
46 | * The Regents of the University of California. All rights reserved. |
||
47 | * |
||
48 | * Redistribution and use in source and binary forms, with or without |
||
49 | * modification, are permitted provided that the following conditions |
||
50 | * are met: |
||
51 | * 1. Redistributions of source code must retain the above copyright |
||
52 | * notice, this list of conditions and the following disclaimer. |
||
53 | * 2. Redistributions in binary form must reproduce the above copyright |
||
54 | * notice, this list of conditions and the following disclaimer in the |
||
55 | * documentation and/or other materials provided with the distribution. |
||
6099 | serge | 56 | * 3. Neither the name of the University nor the names of its contributors |
4349 | Serge | 57 | * may be used to endorse or promote products derived from this software |
58 | * without specific prior written permission. |
||
59 | * |
||
60 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
||
61 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
||
62 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
||
63 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
||
64 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
||
65 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
||
66 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
||
67 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
||
68 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
||
69 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
||
70 | * SUCH DAMAGE. |
||
71 | */ |
||
72 | |||
73 | #include <_ansi.h> |
||
6099 | serge | 74 | #include |
4349 | Serge | 75 | #include |
76 | |||
77 | #ifndef __GNUC__ |
||
78 | #define inline |
||
79 | #endif |
||
80 | |||
6099 | serge | 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 *); |
||
85 | #else |
||
86 | typedef int cmp_t(const void *, const void *); |
||
87 | #endif |
||
88 | static inline char *med3 _PARAMS((char *, char *, char *, cmp_t *, void *)); |
||
4349 | Serge | 89 | static inline void swapfunc _PARAMS((char *, char *, int, int)); |
90 | |||
91 | #define min(a, b) (a) < (b) ? a : b |
||
92 | |||
93 | /* |
||
94 | * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". |
||
95 | */ |
||
96 | #define swapcode(TYPE, parmi, parmj, n) { \ |
||
97 | long i = (n) / sizeof (TYPE); \ |
||
6099 | serge | 98 | TYPE *pi = (TYPE *) (parmi); \ |
99 | TYPE *pj = (TYPE *) (parmj); \ |
||
4349 | Serge | 100 | do { \ |
6099 | serge | 101 | TYPE t = *pi; \ |
4349 | Serge | 102 | *pi++ = *pj; \ |
103 | *pj++ = t; \ |
||
104 | } while (--i > 0); \ |
||
105 | } |
||
106 | |||
107 | #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ |
||
108 | es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; |
||
109 | |||
110 | static inline void |
||
111 | _DEFUN(swapfunc, (a, b, n, swaptype), |
||
112 | char *a _AND |
||
113 | char *b _AND |
||
114 | int n _AND |
||
115 | int swaptype) |
||
116 | { |
||
6099 | serge | 117 | if(swaptype <= 1) |
4349 | Serge | 118 | swapcode(long, a, b, n) |
119 | else |
||
120 | swapcode(char, a, b, n) |
||
121 | } |
||
122 | |||
123 | #define swap(a, b) \ |
||
124 | if (swaptype == 0) { \ |
||
125 | long t = *(long *)(a); \ |
||
126 | *(long *)(a) = *(long *)(b); \ |
||
127 | *(long *)(b) = t; \ |
||
128 | } else \ |
||
129 | swapfunc(a, b, es, swaptype) |
||
130 | |||
131 | #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) |
||
132 | |||
6099 | serge | 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))) |
||
139 | #endif |
||
140 | |||
4349 | Serge | 141 | static inline char * |
6099 | serge | 142 | _DEFUN(med3, (a, b, c, cmp, thunk), |
4349 | Serge | 143 | char *a _AND |
144 | char *b _AND |
||
145 | char *c _AND |
||
6099 | serge | 146 | cmp_t *cmp _AND |
147 | void *thunk |
||
148 | #if !defined(I_AM_QSORT_R) && !defined(I_AM_GNU_QSORT_R) |
||
149 | __unused |
||
150 | #endif |
||
151 | ) |
||
4349 | Serge | 152 | { |
6099 | serge | 153 | return CMP(thunk, a, b) < 0 ? |
154 | (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) |
||
155 | :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c )); |
||
4349 | Serge | 156 | } |
157 | |||
6099 | serge | 158 | #if defined(I_AM_QSORT_R) |
4349 | Serge | 159 | void |
6099 | serge | 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 |
||
173 | void *thunk) |
||
174 | #else |
||
175 | #define thunk NULL |
||
176 | void |
||
4349 | Serge | 177 | _DEFUN(qsort, (a, n, es, cmp), |
178 | void *a _AND |
||
179 | size_t n _AND |
||
180 | size_t es _AND |
||
6099 | serge | 181 | cmp_t *cmp) |
182 | #endif |
||
4349 | Serge | 183 | { |
184 | char *pa, *pb, *pc, *pd, *pl, *pm, *pn; |
||
6099 | serge | 185 | size_t d, r; |
186 | int cmp_result; |
||
187 | int swaptype, swap_cnt; |
||
4349 | Serge | 188 | |
189 | loop: SWAPINIT(a, es); |
||
190 | swap_cnt = 0; |
||
191 | if (n < 7) { |
||
192 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) |
||
6099 | serge | 193 | for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0; |
4349 | Serge | 194 | pl -= es) |
195 | swap(pl, pl - es); |
||
196 | return; |
||
197 | } |
||
198 | pm = (char *) a + (n / 2) * es; |
||
199 | if (n > 7) { |
||
200 | pl = a; |
||
201 | pn = (char *) a + (n - 1) * es; |
||
202 | if (n > 40) { |
||
203 | d = (n / 8) * es; |
||
6099 | serge | 204 | pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk); |
205 | pm = med3(pm - d, pm, pm + d, cmp, thunk); |
||
206 | pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk); |
||
4349 | Serge | 207 | } |
6099 | serge | 208 | pm = med3(pl, pm, pn, cmp, thunk); |
4349 | Serge | 209 | } |
210 | swap(a, pm); |
||
211 | pa = pb = (char *) a + es; |
||
212 | |||
213 | pc = pd = (char *) a + (n - 1) * es; |
||
214 | for (;;) { |
||
6099 | serge | 215 | while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) { |
216 | if (cmp_result == 0) { |
||
4349 | Serge | 217 | swap_cnt = 1; |
218 | swap(pa, pb); |
||
219 | pa += es; |
||
220 | } |
||
221 | pb += es; |
||
222 | } |
||
6099 | serge | 223 | while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) { |
224 | if (cmp_result == 0) { |
||
4349 | Serge | 225 | swap_cnt = 1; |
226 | swap(pc, pd); |
||
227 | pd -= es; |
||
228 | } |
||
229 | pc -= es; |
||
230 | } |
||
231 | if (pb > pc) |
||
232 | break; |
||
233 | swap(pb, pc); |
||
234 | swap_cnt = 1; |
||
235 | pb += es; |
||
236 | pc -= es; |
||
237 | } |
||
238 | if (swap_cnt == 0) { /* Switch to insertion sort */ |
||
239 | for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) |
||
6099 | serge | 240 | for (pl = pm; pl > (char *) a && CMP(thunk, pl - es, pl) > 0; |
4349 | Serge | 241 | pl -= es) |
242 | swap(pl, pl - es); |
||
243 | return; |
||
244 | } |
||
245 | |||
246 | pn = (char *) a + n * es; |
||
247 | r = min(pa - (char *)a, pb - pa); |
||
248 | vecswap(a, pb - r, r); |
||
249 | r = min(pd - pc, pn - pd - es); |
||
250 | vecswap(pb, pn - r, r); |
||
251 | if ((r = pb - pa) > es) |
||
6099 | serge | 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 |
||
4349 | Serge | 257 | qsort(a, r / es, es, cmp); |
6099 | serge | 258 | #endif |
259 | if ((r = pd - pc) > es) { |
||
4349 | Serge | 260 | /* Iterate rather than recurse to save stack space */ |
261 | a = pn - r; |
||
262 | n = r / es; |
||
263 | goto loop; |
||
264 | } |
||
265 | /* qsort(pn - r, r / es, es, cmp);*/ |
||
266 | }>=>=>=>>>>>>>=>> |