qsort.c - vx32 - Local 9vx git repository for patches.
(HTM) git clone git://r-36.net/vx32
(DIR) Log
(DIR) Files
(DIR) Refs
---
qsort.c (5412B)
---
1 /*-
2 * Copyright (c) 1992, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by the University of
16 * California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34 #include <stdlib.h>
35
36 #ifdef I_AM_QSORT_R
37 typedef int cmp_t(void *, const void *, const void *);
38 #else
39 typedef int cmp_t(const void *, const void *);
40 #endif
41 static inline char *med3(char *, char *, char *, cmp_t *, void *);
42 static inline void swapfunc(char *, char *, int, int);
43
44 #define min(a, b) (a) < (b) ? a : b
45
46 /*
47 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
48 */
49 #define swapcode(TYPE, parmi, parmj, n) { \
50 long i = (n) / sizeof (TYPE); \
51 TYPE *pi = (TYPE *) (parmi); \
52 TYPE *pj = (TYPE *) (parmj); \
53 do { \
54 TYPE t = *pi; \
55 *pi++ = *pj; \
56 *pj++ = t; \
57 } while (--i > 0); \
58 }
59
60 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
61 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
62
63 static inline void
64 swapfunc(a, b, n, swaptype)
65 char *a, *b;
66 int n, swaptype;
67 {
68 if(swaptype <= 1)
69 swapcode(long, a, b, n)
70 else
71 swapcode(char, a, b, n)
72 }
73
74 #define swap(a, b) \
75 if (swaptype == 0) { \
76 long t = *(long *)(a); \
77 *(long *)(a) = *(long *)(b); \
78 *(long *)(b) = t; \
79 } else \
80 swapfunc(a, b, es, swaptype)
81
82 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
83
84 #ifdef I_AM_QSORT_R
85 #define CMP(t, x, y) (cmp((t), (x), (y)))
86 #else
87 #define CMP(t, x, y) (cmp((x), (y)))
88 #endif
89
90 static inline char *
91 med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk
92 #ifndef I_AM_QSORT_R
93 __attribute__((__unused__))
94 #endif
95 )
96 {
97 return CMP(thunk, a, b) < 0 ?
98 (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
99 :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
100 }
101
102 #ifdef I_AM_QSORT_R
103 void
104 qsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp)
105 #else
106 #define thunk NULL
107 void
108 qsort(void *a, size_t n, size_t es, cmp_t *cmp)
109 #endif
110 {
111 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
112 int d, r, swaptype, swap_cnt;
113
114 loop: SWAPINIT(a, es);
115 swap_cnt = 0;
116 if (n < 7) {
117 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
118 for (pl = pm;
119 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
120 pl -= es)
121 swap(pl, pl - es);
122 return;
123 }
124 pm = (char *)a + (n / 2) * es;
125 if (n > 7) {
126 pl = a;
127 pn = (char *)a + (n - 1) * es;
128 if (n > 40) {
129 d = (n / 8) * es;
130 pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
131 pm = med3(pm - d, pm, pm + d, cmp, thunk);
132 pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
133 }
134 pm = med3(pl, pm, pn, cmp, thunk);
135 }
136 swap(a, pm);
137 pa = pb = (char *)a + es;
138
139 pc = pd = (char *)a + (n - 1) * es;
140 for (;;) {
141 while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
142 if (r == 0) {
143 swap_cnt = 1;
144 swap(pa, pb);
145 pa += es;
146 }
147 pb += es;
148 }
149 while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
150 if (r == 0) {
151 swap_cnt = 1;
152 swap(pc, pd);
153 pd -= es;
154 }
155 pc -= es;
156 }
157 if (pb > pc)
158 break;
159 swap(pb, pc);
160 swap_cnt = 1;
161 pb += es;
162 pc -= es;
163 }
164 if (swap_cnt == 0) { /* Switch to insertion sort */
165 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
166 for (pl = pm;
167 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
168 pl -= es)
169 swap(pl, pl - es);
170 return;
171 }
172
173 pn = (char *)a + n * es;
174 r = min(pa - (char *)a, pb - pa);
175 vecswap(a, pb - r, r);
176 r = min(pd - pc, pn - pd - es);
177 vecswap(pb, pn - r, r);
178 if ((r = pb - pa) > es)
179 #ifdef I_AM_QSORT_R
180 qsort_r(a, r / es, es, thunk, cmp);
181 #else
182 qsort(a, r / es, es, cmp);
183 #endif
184 if ((r = pd - pc) > es) {
185 /* Iterate rather than recurse to save stack space */
186 a = pn - r;
187 n = r / es;
188 goto loop;
189 }
190 /* qsort(pn - r, r / es, es, cmp);*/
191 }