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