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_TYPE (default: "x<y")
  27  *  ASORT_HASH(x)       a monotone hash function (safisfying hash(x) < hash(y) => x<y)
  28  *
  29  *  Fine-tuning parameters: (if you really insist)
  30  *
  31  *  ASORT_THRESHOLD     threshold for switching between quicksort and insertsort
  32  *  ASORT_RADIX_BITS    how many bits of the hash functions are to be used at once for
  33  *                      radix-sorting.
  34  *
  35  *  After including this file, a function
  36  *      ASORT_KEY_TYPE *ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, uns num_elts, ASORT_KEY_TYPE *buf, uns hash_bits)
  37  *  is declared and all parameter macros are automatically undef'd. Here `buf' is an
  38  *  auxiliary buffer of the same size as the input array, required whenever radix
  39  *  sorting should be used, and `hash_bits' is the number of significant bits returned
  40  *  by the hash function. If the buffer is specified, the sorting function returns either
  41  *  a pointer to the input array or to the buffer, depending on where the result is stored.
  42  *  If you do not use hashing, these parameters should be NULL and 0, respectively.
  43  */
  44
  45 #include "lib/sorter/common.h"
  46
  47 #define Q(x) ASORT_PREFIX(x)
  48
  49 typedef ASORT_KEY_TYPE Q(key);
  50
  51 #ifndef ASORT_LT
  52 #define ASORT_LT(x,y) ((x) < (y))
  53 #endif
  54
  55 #ifndef ASORT_SWAP
  56 #define ASORT_SWAP(i,j) do { Q(key) tmp = array[i]; array[i]=array[j]; array[j]=tmp; } while (0)
  57 #endif
  58
  59 #ifndef ASORT_THRESHOLD
  60 #define ASORT_THRESHOLD 8               /* Guesswork and experimentation */
  61 #endif
  62
  63 #ifndef ASORT_RADIX_BITS
  64 #define ASORT_RADIX_BITS 10             // FIXME: Tune automatically?
  65 #endif
  66 #define ASORT_RADIX_MASK ((1 << (ASORT_RADIX_BITS)) - 1)
  67
  68 /* QuickSort with optimizations a'la Sedgewick, inspired by qsort() from GNU libc. */
  69
  70 static void Q(quicksort)(void *array_ptr, uns num_elts)
  71 {
  72   Q(key) *array = array_ptr;
  73   struct stk { int l, r; } stack[8*sizeof(uns)];
  74   int l, r, left, right, m;
  75   uns sp = 0;
  76   Q(key) pivot;
  77
  78   if (num_elts <= 1)
  79     return;
  80
  81   left = 0;
  82   right = num_elts - 1;
  83   for(;;)
  84     {
  85       l = left;
  86       r = right;
  87       m = (l+r)/2;
  88       if (ASORT_LT(array[m], array[l]))
  89         ASORT_SWAP(l,m);
  90       if (ASORT_LT(array[r], array[m]))
  91         {
  92           ASORT_SWAP(m,r);
  93           if (ASORT_LT(array[m], array[l]))
  94             ASORT_SWAP(l,m);
  95         }
  96       pivot = array[m];
  97       do
  98         {
  99           while (ASORT_LT(array[l], pivot))
 100             l++;
 101           while (ASORT_LT(pivot, array[r]))
 102             r--;
 103           if (l < r)
 104             {
 105               ASORT_SWAP(l,r);
 106               l++;
 107               r--;
 108             }
 109           else if (l == r)
 110             {
 111               l++;
 112               r--;
 113             }
 114         }
 115       while (l <= r);
 116       if ((r - left) >= ASORT_THRESHOLD && (right - l) >= ASORT_THRESHOLD)
 117         {
 118           /* Both partitions ok => push the larger one */
 119           if ((r - left) > (right - l))
 120             {
 121               stack[sp].l = left;
 122               stack[sp].r = r;
 123               left = l;
 124             }
 125           else
 126             {
 127               stack[sp].l = l;
 128               stack[sp].r = right;
 129               right = r;
 130             }
 131           sp++;
 132         }
 133       else if ((r - left) >= ASORT_THRESHOLD)
 134         {
 135           /* Left partition OK, right undersize */
 136           right = r;
 137         }
 138       else if ((right - l) >= ASORT_THRESHOLD)
 139         {
 140           /* Right partition OK, left undersize */
 141           left = l;
 142         }
 143       else
 144         {
 145           /* Both partitions undersize => pop */
 146           if (!sp)
 147             break;
 148           sp--;
 149           left = stack[sp].l;
 150           right = stack[sp].r;
 151         }
 152     }
 153
 154   /*
 155    * We have a partially sorted array, finish by insertsort. Inspired
 156    * by qsort() in GNU libc.
 157    */
 158
 159   /* Find minimal element which will serve as a barrier */
 160   r = MIN(num_elts, ASORT_THRESHOLD);
 161   m = 0;
 162   for (l=1; l<r; l++)
 163     if (ASORT_LT(array[l], array[m]))
 164       m = l;
 165   ASORT_SWAP(0,m);
 166
 167   /* Insertion sort */
 168   for (m=1; m<(int)num_elts; m++)
 169     {
 170       l=m;
 171       while (ASORT_LT(array[m], array[l-1]))
 172         l--;
 173       while (l < m)
 174         {
 175           ASORT_SWAP(l,m);
 176           l++;
 177         }
 178     }
 179 }
 180
 181 /* Just the splitting part of QuickSort */
 182
 183 static void Q(quicksplit)(void *array_ptr, uns num_elts, uns *leftp, uns *rightp)
 184 {
 185   Q(key) *array = array_ptr;
 186   int l, r, m;
 187   Q(key) pivot;
 188
 189   l = 0;
 190   r = num_elts - 1;
 191   m = (l+r)/2;
 192   if (ASORT_LT(array[m], array[l]))
 193     ASORT_SWAP(l,m);
 194   if (ASORT_LT(array[r], array[m]))
 195     {
 196       ASORT_SWAP(m,r);
 197       if (ASORT_LT(array[m], array[l]))
 198         ASORT_SWAP(l,m);
 199     }
 200   pivot = array[m];
 201   do
 202     {
 203       while (ASORT_LT(array[l], pivot))
 204         l++;
 205       while (ASORT_LT(pivot, array[r]))
 206         r--;
 207       if (l < r)
 208         {
 209           ASORT_SWAP(l,r);
 210           l++;
 211           r--;
 212         }
 213       else if (l == r)
 214         {
 215           l++;
 216           r--;
 217         }
 218     }
 219   while (l <= r);
 220   *leftp = l;
 221   *rightp = r;
 222 }
 223
 224 #ifdef ASORT_HASH
 225
 226 static void Q(radix_count)(void *src_ptr, uns num_elts, uns *cnt, uns shift)
 227 {
 228   Q(key) *src = src_ptr;
 229   for (uns i=0; i<num_elts; i++)
 230     cnt[ (ASORT_HASH(src[i]) >> shift) & ASORT_RADIX_MASK ] ++;
 231 }
 232
 233 static void Q(radix_split)(void *src_ptr, void *dest_ptr, uns num_elts, uns *ptrs, uns shift)
 234 {
 235   Q(key) *src = src_ptr, *dest = dest_ptr;
 236   for (uns i=0; i<num_elts; i++)
 237     dest[ ptrs[ (ASORT_HASH(src[i]) >> shift) & ASORT_RADIX_MASK ]++ ] = src[i];
 238 }
 239
 240 #endif
 241
 242 static Q(key) *Q(sort)(Q(key) *array, uns num_elts, Q(key) *buffer, uns hash_bits)
 243 {
 244   struct asort_context ctx = {
 245     .array = array,
 246     .buffer = buffer,
 247     .num_elts = num_elts,
 248     .hash_bits = hash_bits,
 249     .elt_size = sizeof(Q(key)),
 250     .quicksort = Q(quicksort),
 251     .quicksplit = Q(quicksplit),
 252 #ifdef ASORT_HASH
 253     .radix_count = Q(radix_count),
 254     .radix_split = Q(radix_split),
 255     .radix_bits = ASORT_RADIX_BITS,
 256 #endif
 257   };
 258   asort_run(&ctx);
 259   return ctx.array;
 260 }
 261
 262 /* FIXME */
 263 #undef ASORT_PREFIX
 264 #undef ASORT_KEY_TYPE
 265 #undef ASORT_LT
 266 #undef ASORT_SWAP
 267 #undef ASORT_THRESHOLD
 268 #undef ASORT_PAGE_ALIGNED
 269 #undef ASORT_HASH
 270 #undef ASORT_RADIX_BITS
 271 #undef ASORT_RADIX_MASK
 272 #undef Q