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