1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
23 | |
24 | |
25 | |
26 | |
27 | |
28 | |
29 | |
30 | |
31 | |
32 | |
33 | |
34 | |
35 | #include "qsort_threadsafe.h" |
36 | |
37 | #include <stdlib.h> |
38 | |
39 | static void |
40 | qsort_swapfunc(void * a, |
41 | void * b, |
42 | size_t n, |
43 | int swaptype) |
44 | { |
45 | int * ia; |
46 | int * ib; |
47 | int itmp; |
48 | |
49 | char * ca; |
50 | char * cb; |
51 | char ctmp; |
52 | |
53 | if (swaptype <= 1) |
54 | { |
55 | ia = (int *)a; |
56 | ib = (int *)b; |
57 | for (; n > 0; ia += 1, ib += 1, n -= sizeof(int)) |
58 | { |
59 | itmp = *ia; |
60 | *ia = *ib; |
61 | *ib = itmp; |
62 | } |
63 | } |
64 | else |
65 | { |
66 | ca = (char *)a; |
67 | cb = (char *)b; |
68 | for (; n > 0; ca += 1, cb += 1, n -= 1) |
69 | { |
70 | ctmp = *ca; |
71 | *ca = *cb; |
72 | *cb = ctmp; |
73 | } |
74 | } |
75 | } |
76 | |
77 | |
78 | static void * |
79 | qsort_med3(void * a, |
80 | void * b, |
81 | void * c, |
82 | int (*compar) (const void *a, const void *b)) |
83 | { |
84 | if (compar(a, b) < 0) |
85 | { |
86 | if (compar(b, c) < 0) |
87 | { |
88 | return b; |
89 | } |
90 | else if (compar(a, c) < 0) |
91 | { |
92 | return c; |
93 | } |
94 | else |
95 | { |
96 | return a; |
97 | } |
98 | } |
99 | else |
100 | { |
101 | if (compar(b, c) > 0) |
102 | { |
103 | return b; |
104 | } |
105 | else if (compar(a, c) > 0) |
106 | { |
107 | return c; |
108 | } |
109 | else |
110 | { |
111 | return a; |
112 | } |
113 | } |
114 | } |
115 | |
116 | |
117 | void |
118 | gmx_qsort(void * base, |
119 | size_t nmemb, |
120 | size_t size, |
121 | int (*compar)(const void *, const void *)) |
122 | { |
123 | #define QSORT_EXCH(a, b, t) (t = a, a = b, b = t) |
124 | #define QSORT_SWAP(a, b) swaptype != 0 ? qsort_swapfunc(a, b, size, swaptype) : \ |
125 | (void)QSORT_EXCH(*(int *)(a), *(int *)(b), t) |
126 | |
127 | char *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv, *cbase; |
128 | int r, swaptype; |
129 | int t, v; |
130 | size_t s, st; |
131 | |
132 | cbase = (char *)base; |
133 | |
134 | swaptype = (size_t)(cbase - (char *)0) % sizeof(int) || size % sizeof(int) ? 2 : size == sizeof(int) ? 0 : 1; |
| |
| |
135 | |
136 | if (nmemb < 7) |
| 3 | | Assuming 'nmemb' is >= 7 | |
|
| |
137 | { |
138 | |
139 | for (pm = cbase + size; pm < cbase + nmemb*size; pm += size) |
140 | { |
141 | for (pl = pm; (pl > cbase) && compar((void *)(pl-size), (void *) pl) > 0; pl -= size) |
142 | { |
143 | QSORT_SWAP(pl, pl-size); |
144 | } |
145 | } |
146 | return; |
147 | } |
148 | |
149 | |
150 | pm = cbase + (nmemb/2)*size; |
151 | |
152 | if (nmemb > 7) |
| 5 | | Assuming 'nmemb' is <= 7 | |
|
| |
153 | { |
154 | pl = cbase; |
155 | pn = cbase + (nmemb-1)*size; |
156 | if (nmemb > 40) |
157 | { |
158 | |
159 | s = (nmemb/8)*size; |
160 | pl = (char *)qsort_med3((void *)pl, (void *)((size_t)pl+s), (void *)((size_t)pl+2*s), compar); |
161 | pm = (char *)qsort_med3((void *)((size_t)pm-s), (void *)pm, (void *)((size_t)pm+s), compar); |
162 | pn = (char *)qsort_med3((void *)((size_t)pn-2*s), (void *)((size_t)pn-s), (void *)pn, compar); |
163 | } |
164 | |
165 | pm = (char *)qsort_med3((void *)pl, (void *)pm, (void *)pn, compar); |
166 | } |
167 | |
168 | |
169 | if (swaptype != 0) |
| |
170 | { |
171 | pv = cbase; |
172 | QSORT_SWAP(pv, pm); |
173 | } |
174 | else |
175 | { |
176 | pv = (char*)(void*)&v; |
177 | v = *(int *)pm; |
178 | } |
179 | |
180 | pa = pb = cbase; |
181 | pc = pd = cbase + (nmemb-1)*size; |
182 | |
183 | for (;; ) |
| 8 | | Loop condition is true. Entering loop body | |
|
| 12 | | Loop condition is true. Entering loop body | |
|
184 | { |
185 | while (pb <= pc && (r = compar((void *)pb, (void *) pv)) <= 0) |
| 9 | | Loop condition is false. Execution continues on line 194 | |
|
| 13 | | Loop condition is true. Entering loop body | |
|
| 16 | | Assuming 'pb' is > 'pc' | |
|
186 | { |
187 | if (r == 0) |
| 14 | | Assuming 'r' is equal to 0 | |
|
| |
188 | { |
189 | QSORT_SWAP(pa, pb); |
190 | pa += size; |
191 | } |
192 | pb += size; |
193 | } |
194 | while (pc >= pb && (r = compar((void *)pc, (void *) pv)) >= 0) |
| 10 | | Loop condition is false. Execution continues on line 203 | |
|
| 17 | | Assuming 'pc' is < 'pb' | |
|
195 | { |
196 | if (r == 0) |
197 | { |
198 | QSORT_SWAP(pc, pd); |
199 | pd -= size; |
200 | } |
201 | pc -= size; |
202 | } |
203 | if (pb > pc) |
| |
| |
204 | { |
205 | break; |
| 19 | | Execution continues on line 211 | |
|
206 | } |
207 | QSORT_SWAP(pb, pc); |
208 | pb += size; |
209 | pc -= size; |
210 | } |
211 | pn = cbase + nmemb*size; |
212 | |
213 | s = pa-cbase; |
214 | st = pb-pa; |
215 | if (st < s) |
| |
216 | { |
217 | s = st; |
218 | } |
219 | |
220 | if (s > 0) |
| |
| |
221 | { |
222 | qsort_swapfunc(cbase, pb-s, s, swaptype); |
223 | } |
224 | |
225 | s = pd-pc; |
226 | st = pn-pd-size; |
227 | if (st < s) |
| |
228 | { |
229 | s = st; |
230 | } |
231 | |
232 | if (s > 0) |
| |
| |
233 | { |
234 | qsort_swapfunc(pb, pn-s, s, swaptype); |
235 | } |
236 | |
237 | if ((s = pb-pa) > size) |
| |
238 | { |
239 | gmx_qsort(cbase, s/size, size, compar); |
240 | } |
241 | |
242 | if ((s = pd-pc) > size) |
| |
243 | { |
244 | gmx_qsort(pn-s, s/size, size, compar); |
| |
245 | } |
246 | |
247 | #undef QSORT_EXCH |
248 | #undef QSORT_SWAP |
249 | |
250 | return; |
251 | } |