lib/sorter/array.h

   1 /*
   2  *      UCW Library -- Optimized Array Sorter
   3  *
   4  *      (c) 2003--2007 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 /*
  11  *  This is a generator of routines for sorting huge arrays, similar to the one
  12  *  in lib/arraysort.h. It cannot handle discontiguous arrays, but it is able
  13  *  to employ radix-sorting if a monotone hash function is available and also
  14  *  use several threads in parallel on SMP systems (this assumes that all
  15  *  callbacks you provide are thread-safe).
  16  *
  17  *  It is usually called internally by the generic shorter machinery, but
  18  *  you are free to use it explicitly if you need.
  19  *
  20  *  So much for advocacy, there are the parameters (those marked with [*]
  21  *  are mandatory):
  22  *
  23  *  ASORT_PREFIX(x) [*] add a name prefix (used on all global names
  24  *                      defined by the sorter)
  25  *  ASORT_KEY_TYPE  [*] data type of a single array entry key
  26  *  ASORT_LT(x,y)       x < y for ASORT_KEY_TYPE (default: "x<y")
  27  *  ASORT_HASH(x)       a monotone hash function (safisfying hash(x) < hash(y) => x<y)
  28  *  ASORT_LONG_HASH     hashes are 64-bit numbers (default is 32 bits)
  29  *
  30  *  Fine-tuning parameters: (if you really insist)
  31  *
  32  *  ASORT_THRESHOLD     threshold for switching between quicksort and insertsort
  33  *  ASORT_RADIX_BITS    how many bits of the hash functions are to be used at once for
  34  *                      radix-sorting.
  35  *
  36  *  After including this file, a function
  37  *      ASORT_KEY_TYPE *ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, uns num_elts [, ASORT_KEY_TYPE *buf, uns hash_bits])
  38  *  is declared and all parameter macros are automatically undef'd. Here `buf' is an
  39  *  auxiliary buffer of the same size as the input array, required whenever radix
  40  *  sorting should be used, and `hash_bits' is the number of significant bits returned
  41  *  by the hash function. If the buffer is specified, the sorting function returns either
  42  *  a pointer to the input array or to the buffer, depending on where the result is stored.
  43  *  If you do not use hashing, these parameters should be omitted.
  44  */
  45
  46 #include "lib/sorter/common.h"
  47
  48 #define Q(x) ASORT_PREFIX(x)
  49
  50 typedef ASORT_KEY_TYPE Q(key);
  51
  52 #ifndef ASORT_LT
  53 #define ASORT_LT(x,y) ((x) < (y))
  54 #endif
  55
  56 #ifndef ASORT_SWAP
  57 #define ASORT_SWAP(i,j) do { Q(key) tmp = array[i]; array[i]=array[j]; array[j]=tmp; } while (0)
  58 #endif
  59
  60 #ifndef ASORT_THRESHOLD
  61 #define ASORT_THRESHOLD 8               /* Guesswork and experimentation */
  62 #endif
  63
  64 #ifndef ASORT_RADIX_BITS
  65 #define ASORT_RADIX_BITS CONFIG_UCW_RADIX_SORTER_BITS
  66 #endif
  67 #define ASORT_RADIX_MASK ((1 << (ASORT_RADIX_BITS)) - 1)
  68
  69 /* QuickSort with optimizations a'la Sedgewick, inspired by qsort() from GNU libc. */
  70
  71 static void Q(quicksort)(void *array_ptr, uns num_elts)
  72 {
  73   Q(key) *array = array_ptr;
  74   struct stk { int l, r; } stack[8*sizeof(uns)];
  75   int l, r, left, right, m;
  76   uns sp = 0;
  77   Q(key) pivot;
  78
  79   if (num_elts <= 1)
  80     return;
  81
  82   left = 0;
  83   right = num_elts - 1;
  84   for(;;)
  85     {
  86       l = left;
  87       r = right;
  88       m = (l+r)/2;
  89       if (ASORT_LT(array[m], array[l]))
  90         ASORT_SWAP(l,m);
  91       if (ASORT_LT(array[r], array[m]))
  92         {
  93           ASORT_SWAP(m,r);
  94           if (ASORT_LT(array[m], array[l]))
  95             ASORT_SWAP(l,m);
  96         }
  97       pivot = array[m];
  98       do
  99         {
 100           while (ASORT_LT(array[l], pivot))
 101             l++;
 102           while (ASORT_LT(pivot, array[r]))
 103             r--;
 104           if (l < r)
 105             {
 106               ASORT_SWAP(l,r);
 107               l++;
 108               r--;
 109             }
 110           else if (l == r)
 111             {
 112               l++;
 113               r--;
 114             }
 115         }
 116       while (l <= r);
 117       if ((r - left) >= ASORT_THRESHOLD && (right - l) >= ASORT_THRESHOLD)
 118         {
 119           /* Both partitions ok => push the larger one */
 120           if ((r - left) > (right - l))
 121             {
 122               stack[sp].l = left;
 123               stack[sp].r = r;
 124               left = l;
 125             }
 126           else
 127             {
 128               stack[sp].l = l;
 129               stack[sp].r = right;
 130               right = r;
 131             }
 132           sp++;
 133         }
 134       else if ((r - left) >= ASORT_THRESHOLD)
 135         {
 136           /* Left partition OK, right undersize */
 137           right = r;
 138         }
 139       else if ((right - l) >= ASORT_THRESHOLD)
 140         {
 141           /* Right partition OK, left undersize */
 142           left = l;
 143         }
 144       else
 145         {
 146           /* Both partitions undersize => pop */
 147           if (!sp)
 148             break;
 149           sp--;
 150           left = stack[sp].l;
 151           right = stack[sp].r;
 152         }
 153     }
 154
 155   /*
 156    * We have a partially sorted array, finish by insertsort. Inspired
 157    * by qsort() in GNU libc.
 158    */
 159
 160   /* Find minimal element which will serve as a barrier */
 161   r = MIN(num_elts, ASORT_THRESHOLD);
 162   m = 0;
 163   for (l=1; l<r; l++)
 164     if (ASORT_LT(array[l], array[m]))
 165       m = l;
 166   ASORT_SWAP(0,m);
 167
 168   /* Insertion sort */
 169   for (m=1; m<(int)num_elts; m++)
 170     {
 171       l=m;
 172       while (ASORT_LT(array[m], array[l-1]))
 173         l--;
 174       while (l < m)
 175         {
 176           ASORT_SWAP(l,m);
 177           l++;
 178         }
 179     }
 180 }
 181
 182 /* Just the splitting part of QuickSort */
 183
 184 static void Q(quicksplit)(void *array_ptr, uns num_elts, int *leftp, int *rightp)
 185 {
 186   Q(key) *array = array_ptr;
 187   int l, r, m;
 188   Q(key) pivot;
 189
 190   l = 0;
 191   r = num_elts - 1;
 192   m = (l+r)/2;
 193   if (ASORT_LT(array[m], array[l]))
 194     ASORT_SWAP(l,m);
 195   if (ASORT_LT(array[r], array[m]))
 196     {
 197       ASORT_SWAP(m,r);
 198       if (ASORT_LT(array[m], array[l]))
 199         ASORT_SWAP(l,m);
 200     }
 201   pivot = array[m];
 202   do
 203     {
 204       while (ASORT_LT(array[l], pivot))
 205         l++;
 206       while (ASORT_LT(pivot, array[r]))
 207         r--;
 208       if (l < r)
 209         {
 210           ASORT_SWAP(l,r);
 211           l++;
 212           r--;
 213         }
 214       else if (l == r)
 215         {
 216           l++;
 217           r--;
 218         }
 219     }
 220   while (l <= r);
 221   *leftp = l;
 222   *rightp = r;
 223 }
 224
 225 #ifdef ASORT_HASH
 226
 227 static void Q(radix_count)(void *src_ptr, uns num_elts, uns *cnt, uns shift)
 228 {
 229   Q(key) *src = src_ptr;
 230   uns i;
 231
 232   switch (shift)
 233     {
 234 #define RC(s) \
 235     case s:                                                             \
 236       for (i=0; i<num_elts; i++)                                        \
 237         cnt[ (ASORT_HASH(src[i]) >> s) & ASORT_RADIX_MASK ] ++;         \
 238       break;                                                            \
 239
 240 #ifdef ASORT_LONG_HASH
 241       RC(63); RC(62); RC(61); RC(60); RC(59); RC(58); RC(57); RC(56);
 242       RC(55); RC(54); RC(53); RC(52); RC(51); RC(50); RC(49); RC(48);
 243       RC(47); RC(46); RC(45); RC(44); RC(43); RC(42); RC(41); RC(40);
 244       RC(39); RC(38); RC(37); RC(36); RC(35); RC(34); RC(33); RC(32);
 245 #endif
 246       RC(31); RC(30); RC(29); RC(28); RC(27); RC(26); RC(25); RC(24);
 247       RC(23); RC(22); RC(21); RC(20); RC(19); RC(18); RC(17); RC(16);
 248       RC(15); RC(14); RC(13); RC(12); RC(11); RC(10); RC(9); RC(8);
 249       RC(7); RC(6); RC(5); RC(4); RC(3); RC(2); RC(1); RC(0);
 250     default:
 251       ASSERT(0);
 252     }
 253 #undef RC
 254 }
 255
 256 static void Q(radix_split)(void *src_ptr, void *dest_ptr, uns num_elts, uns *ptrs, uns shift)
 257 {
 258   Q(key) *src = src_ptr, *dest = dest_ptr;
 259   uns i;
 260
 261   switch (shift)
 262     {
 263 #define RS(s) \
 264     case s:                                                                             \
 265       for (i=0; i<num_elts; i++)                                                        \
 266         dest[ ptrs[ (ASORT_HASH(src[i]) >> s) & ASORT_RADIX_MASK ]++ ] = src[i];        \
 267       break;
 268
 269 #ifdef ASORT_LONG_HASH
 270       RS(63); RS(62); RS(61); RS(60); RS(59); RS(58); RS(57); RS(56);
 271       RS(55); RS(54); RS(53); RS(52); RS(51); RS(50); RS(49); RS(48);
 272       RS(47); RS(46); RS(45); RS(44); RS(43); RS(42); RS(41); RS(40);
 273       RS(39); RS(38); RS(37); RS(36); RS(35); RS(34); RS(33); RS(32);
 274 #endif
 275       RS(31); RS(30); RS(29); RS(28); RS(27); RS(26); RS(25); RS(24);
 276       RS(23); RS(22); RS(21); RS(20); RS(19); RS(18); RS(17); RS(16);
 277       RS(15); RS(14); RS(13); RS(12); RS(11); RS(10); RS(9); RS(8);
 278       RS(7); RS(6); RS(5); RS(4); RS(3); RS(2); RS(1); RS(0);
 279     default:
 280       ASSERT(0);
 281     }
 282 #undef RS
 283 }
 284
 285 #endif
 286
 287 static Q(key) *Q(sort)(Q(key) *array, uns num_elts
 288 #ifdef ASORT_HASH
 289   , Q(key) *buffer, uns hash_bits
 290 #endif
 291   )
 292 {
 293   struct asort_context ctx = {
 294     .array = array,
 295     .num_elts = num_elts,
 296     .elt_size = sizeof(Q(key)),
 297     .quicksort = Q(quicksort),
 298     .quicksplit = Q(quicksplit),
 299 #ifdef ASORT_HASH
 300     .buffer = buffer,
 301     .hash_bits = hash_bits,
 302     .radix_count = Q(radix_count),
 303     .radix_split = Q(radix_split),
 304     .radix_bits = ASORT_RADIX_BITS,
 305 #endif
 306   };
 307   asort_run(&ctx);
 308   return ctx.array;
 309 }
 310
 311 #undef ASORT_HASH
 312 #undef ASORT_KEY_TYPE
 313 #undef ASORT_LONG_HASH
 314 #undef ASORT_LT
 315 #undef ASORT_PAGE_ALIGNED
 316 #undef ASORT_PREFIX
 317 #undef ASORT_RADIX_BITS
 318 #undef ASORT_RADIX_MASK
 319 #undef ASORT_SWAP
 320 #undef ASORT_THRESHOLD
 321 #undef Q