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