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 HAVE_GNU_QSORT_R)
  28 #  define _SORT_R_LINUX
  29 #elif (defined HAVE_BSD_QSORT_R)
  30 #  define _SORT_R_BSD
  31 #elif (defined __gnu_hurd__ || defined __GNU__ || \
  32        defined __linux__ || defined __MINGW32__ || defined __GLIBC__)
  33 #  define _SORT_R_LINUX
  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! */
  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 */
  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 */
  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 */
  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
 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
 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_LINUX
 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
 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_LINUX
 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_LINUX
 323 #undef _SORT_R_BSD
 324
 325 #endif /* SORT_R_H_ */