1 /* Isaac Turner 29 April 2014 Public Domain */
2 #ifndef SORT_R_H_
3 #define SORT_R_H_
4
5 #include <stdlib.h>
6 #include <string.h>
7
8 /*
9
10 sort_r function to be exported.
11
12 Parameters:
13 base is the array to be sorted
14 nel is the number of elements in the array
15 width is the size in bytes of each element of the array
16 compar is the comparison function
17 arg is a pointer to be passed to the comparison function
18
19 void sort_r(void *base, size_t nel, size_t width,
20 int (*compar)(const void *_a, const void *_b, void *_arg),
21 void *arg);
22
23 */
24
25 #define _SORT_R_INLINE inline
26
27 #if ( defined __APPLE__ || defined __MACH__ || defined __DARWIN__ \
28 || defined __FreeBSD__ || defined __DragonFly__) && defined JB_HAVE_QSORT_R
29 # define _SORT_R_BSD
30 #elif ( defined _GNU_SOURCE || defined __gnu_hurd__ || defined __GNU__ \
31 || defined __linux__ || defined __MINGW32__ || defined __GLIBC__) && defined JB_HAVE_QSORT_R
32 # define _SORT_R_LINUX
33 #elif (defined _WIN32 || defined _WIN64 || defined __WINDOWS__)
34 # define _SORT_R_WINDOWS
35 # undef _SORT_R_INLINE
36 # define _SORT_R_INLINE __inline
37 #else
38 /* Using our own recursive quicksort sort_r_simple() */
39 #endif
40
41 #if (defined NESTED_QSORT && NESTED_QSORT == 0)
42 # undef NESTED_QSORT
43 #endif
44
45 #define SORT_R_SWAP(a, b, tmp) ((tmp) = (a), (a) = (b), (b) = (tmp))
46
47 /* swap a and b */
48
49 /* a and b must not be equal! */
sort_r_swap(char * __restrict a,char * __restrict b,size_t w)50 static _SORT_R_INLINE void sort_r_swap(
51 char* __restrict a, char* __restrict b,
52 size_t w) {
53 char tmp, *end = a + w;
54 for ( ; a < end; a++, b++) {
55 SORT_R_SWAP(*a, *b, tmp);
56 }
57 }
58
59 /* swap a, b iff a>b */
60
61 /* a and b must not be equal! */
62
63 /* __restrict is same as restrict but better support on old machines */
sort_r_cmpswap(char * __restrict a,char * __restrict b,size_t w,int (* compar)(const void * _a,const void * _b,void * _arg),void * arg)64 static _SORT_R_INLINE int sort_r_cmpswap(
65 char* __restrict a,
66 char* __restrict b, size_t w,
67 int (*compar)(const void *_a,
68 const void *_b,
69 void *_arg),
70 void *arg) {
71 if (compar(a, b, arg) > 0) {
72 sort_r_swap(a, b, w);
73 return 1;
74 }
75 return 0;
76 }
77
78 /*
79 Swap consecutive blocks of bytes of size na and nb starting at memory addr ptr,
80 with the smallest swap so that the blocks are in the opposite order. Blocks may
81 be internally re-ordered e.g.
82
83 12345ab -> ab34512
84 123abc -> abc123
85 12abcde -> deabc12
86 */
sort_r_swap_blocks(char * ptr,size_t na,size_t nb)87 static _SORT_R_INLINE void sort_r_swap_blocks(char *ptr, size_t na, size_t nb) {
88 if ((na > 0) && (nb > 0)) {
89 if (na > nb) {
90 sort_r_swap(ptr, ptr + na, nb);
91 } else {
92 sort_r_swap(ptr, ptr + nb, na);
93 }
94 }
95 }
96
97 /* Implement recursive quicksort ourselves */
98
99 /* Note: quicksort is not stable, equivalent values may be swapped */
sort_r_simple(void * base,size_t nel,size_t w,int (* compar)(const void * _a,const void * _b,void * _arg),void * arg)100 static _SORT_R_INLINE void sort_r_simple(
101 void *base, size_t nel, size_t w,
102 int (*compar)(const void *_a,
103 const void *_b,
104 void *_arg),
105 void *arg) {
106 char *b = (char*) base, *end = b + nel * w;
107
108 /* for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
109 printf("\n"); */
110
111 if (nel < 10) {
112 /* Insertion sort for arbitrarily small inputs */
113 char *pi, *pj;
114 for (pi = b + w; pi < end; pi += w) {
115 for (pj = pi; pj > b && sort_r_cmpswap(pj - w, pj, w, compar, arg); pj -= w) {
116 }
117 }
118 } else {
119 /* nel > 6; Quicksort */
120
121 int cmp;
122 char *pl, *ple, *pr, *pre, *pivot;
123 char *last = b + w * (nel - 1), *tmp;
124
125 /*
126 Use median of second, middle and second-last items as pivot.
127 First and last may have been swapped with pivot and therefore be extreme
128 */
129 char *l[3];
130 l[0] = b + w;
131 l[1] = b + w * (nel / 2);
132 l[2] = last - w;
133
134 /* printf("pivots: %i, %i, %i\n", *(int*)l[0], *(int*)l[1], *(int*)l[2]); */
135
136 if (compar(l[0], l[1], arg) > 0) {
137 SORT_R_SWAP(l[0], l[1], tmp);
138 }
139 if (compar(l[1], l[2], arg) > 0) {
140 SORT_R_SWAP(l[1], l[2], tmp);
141 if (compar(l[0], l[1], arg) > 0) {
142 SORT_R_SWAP(l[0], l[1], tmp);
143 }
144 }
145
146 /* swap mid value (l[1]), and last element to put pivot as last element */
147 if (l[1] != last) {
148 sort_r_swap(l[1], last, w);
149 }
150
151 /*
152 pl is the next item on the left to be compared to the pivot
153 pr is the last item on the right that was compared to the pivot
154 ple is the left position to put the next item that equals the pivot
155 ple is the last right position where we put an item that equals the pivot
156
157 v- end (beyond the array)
158 EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE.
159 ^- b ^- ple ^- pl ^- pr ^- pre ^- last (where the pivot is)
160
161 Pivot comparison key:
162 E = equal, L = less than, u = unknown, G = greater than, E = equal
163 */
164 pivot = last;
165 ple = pl = b;
166 pre = pr = last;
167
168 /*
169 Strategy:
170 Loop into the list from the left and right at the same time to find:
171 - an item on the left that is greater than the pivot
172 - an item on the right that is less than the pivot
173 Once found, they are swapped and the loop continues.
174 Meanwhile items that are equal to the pivot are moved to the edges of the
175 array.
176 */
177 while (pl < pr) {
178 /* Move left hand items which are equal to the pivot to the far left.
179 break when we find an item that is greater than the pivot */
180 for ( ; pl < pr; pl += w) {
181 cmp = compar(pl, pivot, arg);
182 if (cmp > 0) {
183 break;
184 } else if (cmp == 0) {
185 if (ple < pl) {
186 sort_r_swap(ple, pl, w);
187 }
188 ple += w;
189 }
190 }
191 /* break if last batch of left hand items were equal to pivot */
192 if (pl >= pr) {
193 break;
194 }
195 /* Move right hand items which are equal to the pivot to the far right.
196 break when we find an item that is less than the pivot */
197 for ( ; pl < pr; ) {
198 pr -= w; /* Move right pointer onto an unprocessed item */
199 cmp = compar(pr, pivot, arg);
200 if (cmp == 0) {
201 pre -= w;
202 if (pr < pre) {
203 sort_r_swap(pr, pre, w);
204 }
205 } else if (cmp < 0) {
206 if (pl < pr) {
207 sort_r_swap(pl, pr, w);
208 }
209 pl += w;
210 break;
211 }
212 }
213 }
214
215 pl = pr; /* pr may have gone below pl */
216
217 /*
218 Now we need to go from: EEELLLGGGGEEEE
219 to: LLLEEEEEEEGGGG
220
221 Pivot comparison key:
222 E = equal, L = less than, u = unknown, G = greater than, E = equal
223 */
224 sort_r_swap_blocks(b, ple - b, pl - ple);
225 sort_r_swap_blocks(pr, pre - pr, end - pre);
226
227 /*for(size_t i=0; i<nel; i++) {printf("%4i", *(int*)(b + i*sizeof(int)));}
228 printf("\n");*/
229
230 sort_r_simple(b, (pl - ple) / w, w, compar, arg);
231 sort_r_simple(end - (pre - pr), (pre - pr) / w, w, compar, arg);
232 }
233 }
234
235 #if defined NESTED_QSORT
236
sort_r(void * base,size_t nel,size_t width,int (* compar)(const void * _a,const void * _b,void * aarg),void * arg)237 static _SORT_R_INLINE void sort_r(
238 void *base, size_t nel, size_t width,
239 int (*compar)(const void *_a,
240 const void *_b,
241 void *aarg),
242 void *arg) {
243
244 int nested_cmp(const void *a, const void *b) {
245 return compar(a, b, arg);
246 }
247
248 qsort(base, nel, width, nested_cmp);
249 }
250
251 #else /* !NESTED_QSORT */
252
253 /* Declare structs and functions */
254
255 #if defined _SORT_R_BSD
256
257 /* Ensure qsort_r is defined */
258 extern void qsort_r(
259 void *base, size_t nel, size_t width, void *thunk,
260 int (*compar)(void *_thunk,
261 const void *_a, const void *_b));
262
263 #endif
264
265 #if defined _SORT_R_BSD || defined _SORT_R_WINDOWS
266
267 /* BSD (qsort_r), Windows (qsort_s) require argument swap */
268
269 struct sort_r_data {
270 void *arg;
271 int (*compar)(const void *_a, const void *_b, void *_arg);
272 };
273
sort_r_arg_swap(void * s,const void * a,const void * b)274 static _SORT_R_INLINE int sort_r_arg_swap(
275 void *s,
276 const void *a, const void *b) {
277 struct sort_r_data *ss = (struct sort_r_data*) s;
278 return (ss->compar)(a, b, ss->arg);
279 }
280
281 #endif
282
283 #if defined _SORT_R_LINUX
284
285 typedef int (*__compar_d_fn_t)(const void*, const void*, void*);
286 extern void qsort_r(
287 void *base, size_t nel, size_t width,
288 __compar_d_fn_t __compar, void *arg)
289 __attribute__((nonnull(1, 4)));
290
291 #endif
292
293 /* implementation */
294
sort_r(void * base,size_t nel,size_t width,int (* compar)(const void * _a,const void * _b,void * _arg),void * arg)295 static _SORT_R_INLINE void sort_r(
296 void *base, size_t nel, size_t width,
297 int (*compar)(const void *_a,
298 const void *_b, void *_arg),
299 void *arg) {
300 #if defined _SORT_R_LINUX
301
302 #if defined __GLIBC__ && ((__GLIBC__ < 2) || (__GLIBC__ == 2 && __GLIBC_MINOR__ < 8))
303
304 /* no qsort_r in glibc before 2.8, need to use nested qsort */
305 sort_r_simple(base, nel, width, compar, arg);
306
307 #else
308
309 qsort_r(base, nel, width, compar, arg);
310
311 #endif
312
313 #elif defined _SORT_R_BSD
314
315 struct sort_r_data tmp;
316 tmp.arg = arg;
317 tmp.compar = compar;
318 qsort_r(base, nel, width, &tmp, sort_r_arg_swap);
319
320 #elif defined _SORT_R_WINDOWS
321
322 struct sort_r_data tmp;
323 tmp.arg = arg;
324 tmp.compar = compar;
325 qsort_s(base, nel, width, sort_r_arg_swap, &tmp);
326
327 #else
328
329 /* Fall back to our own quicksort implementation */
330 sort_r_simple(base, nel, width, compar, arg);
331
332 #endif
333 }
334
335 #endif /* !NESTED_QSORT */
336
337 #undef _SORT_R_INLINE
338 #undef _SORT_R_WINDOWS
339 #undef _SORT_R_LINUX
340 #undef _SORT_R_BSD
341
342 #endif /* SORT_R_H_ */
343