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