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
  26  *  ASORT_HASH(x)       FIXME
  27  *  ASORT_SWAP          FIXME: probably keep private
  28  *
  29  *  After including this file, a function
  30  *      ASORT_KEY_TYPE *ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, uns num_elts, ASORT_KEY_TYPE *buf, uns hash_bits)
  31  *  is declared and all parameter macros are automatically undef'd.
  32  */
  33
  34 #include "lib/sorter/common.h"
  35
  36 #define Q(x) ASORT_PREFIX(x)
  37
  38 typedef ASORT_KEY_TYPE Q(key);
  39
  40 #ifndef ASORT_LT
  41 #define ASORT_LT(x,y) ((x) < (y))
  42 #endif
  43
  44 #ifndef ASORT_SWAP
  45 #define ASORT_SWAP(i,j) do { Q(key) tmp = array[i]; array[i]=array[j]; array[j]=tmp; } while (0)
  46 #endif
  47
  48 #ifndef ASORT_THRESHOLD
  49 #define ASORT_THRESHOLD 8               /* Guesswork and experimentation */
  50 #endif
  51
  52 static void Q(raw_sort)(Q(key) *array, uns array_size)
  53 {
  54   struct stk { int l, r; } stack[8*sizeof(uns)];
  55   int l, r, left, right, m;
  56   uns sp = 0;
  57   Q(key) pivot;
  58
  59   if (array_size <= 1)
  60     return;
  61
  62   /* QuickSort with optimizations a'la Sedgewick, but stop at ASORT_THRESHOLD */
  63
  64   left = 0;
  65   right = array_size - 1;
  66   for(;;)
  67     {
  68       l = left;
  69       r = right;
  70       m = (l+r)/2;
  71       if (ASORT_LT(array[m], array[l]))
  72         ASORT_SWAP(l,m);
  73       if (ASORT_LT(array[r], array[m]))
  74         {
  75           ASORT_SWAP(m,r);
  76           if (ASORT_LT(array[m], array[l]))
  77             ASORT_SWAP(l,m);
  78         }
  79       pivot = array[m];
  80       do
  81         {
  82           while (ASORT_LT(array[l], pivot))
  83             l++;
  84           while (ASORT_LT(pivot, array[r]))
  85             r--;
  86           if (l < r)
  87             {
  88               ASORT_SWAP(l,r);
  89               l++;
  90               r--;
  91             }
  92           else if (l == r)
  93             {
  94               l++;
  95               r--;
  96             }
  97         }
  98       while (l <= r);
  99       if ((r - left) >= ASORT_THRESHOLD && (right - l) >= ASORT_THRESHOLD)
 100         {
 101           /* Both partitions ok => push the larger one */
 102           if ((r - left) > (right - l))
 103             {
 104               stack[sp].l = left;
 105               stack[sp].r = r;
 106               left = l;
 107             }
 108           else
 109             {
 110               stack[sp].l = l;
 111               stack[sp].r = right;
 112               right = r;
 113             }
 114           sp++;
 115         }
 116       else if ((r - left) >= ASORT_THRESHOLD)
 117         {
 118           /* Left partition OK, right undersize */
 119           right = r;
 120         }
 121       else if ((right - l) >= ASORT_THRESHOLD)
 122         {
 123           /* Right partition OK, left undersize */
 124           left = l;
 125         }
 126       else
 127         {
 128           /* Both partitions undersize => pop */
 129           if (!sp)
 130             break;
 131           sp--;
 132           left = stack[sp].l;
 133           right = stack[sp].r;
 134         }
 135     }
 136
 137   /*
 138    * We have a partially sorted array, finish by insertsort. Inspired
 139    * by qsort() in GNU libc.
 140    */
 141
 142   /* Find minimal element which will serve as a barrier */
 143   r = MIN(array_size, ASORT_THRESHOLD);
 144   m = 0;
 145   for (l=1; l<r; l++)
 146     if (ASORT_LT(array[l], array[m]))
 147       m = l;
 148   ASORT_SWAP(0,m);
 149
 150   /* Insertion sort */
 151   for (m=1; m<(int)array_size; m++)
 152     {
 153       l=m;
 154       while (ASORT_LT(array[m], array[l-1]))
 155         l--;
 156       while (l < m)
 157         {
 158           ASORT_SWAP(l,m);
 159           l++;
 160         }
 161     }
 162 }
 163
 164 static Q(key) *Q(sort)(Q(key) *array, uns num_elts, Q(key) *buffer, uns hash_bits)
 165 {
 166   (void) buffer;
 167   (void) hash_bits;
 168   Q(raw_sort)(array, num_elts);
 169   return array;
 170 }
 171
 172 /* FIXME */
 173 #undef ASORT_PREFIX
 174 #undef ASORT_KEY_TYPE
 175 #undef ASORT_LT
 176 #undef ASORT_SWAP
 177 #undef ASORT_THRESHOLD
 178 #undef ASORT_PAGE_ALIGNED
 179 #undef ASORT_HASH
 180 #undef Q