lib/support/sort_r.h

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