ucw/sorter/array-simple.h

   1 /*
   2  *      UCW Library -- Universal Simple Array Sorter
   3  *
   4  *      (c) 2003--2008 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 not a normal header file, it's a generator of sorting
  12  *  routines.  Each time you include it with parameters set in the
  13  *  corresponding preprocessor macros, it generates an array sorter
  14  *  with the parameters given.
  15  *
  16  *  You might wonder why the heck do we implement our own array sorter
  17  *  instead of using qsort(). The primary reason is that qsort handles
  18  *  only continuous arrays, but we need to sort array-like data structures
  19  *  where the only way to access elements is by using an indexing macro.
  20  *  Besides that, we are more than 2 times faster.
  21  *
  22  *  So much for advocacy, there are the parameters (those marked with [*]
  23  *  are mandatory):
  24  *
  25  *  ASORT_PREFIX(x) [*] add a name prefix (used on all global names
  26  *                      defined by the sorter)
  27  *  ASORT_KEY_TYPE  [*] data type of a single array entry key
  28  *  ASORT_ELT(i)        returns the key of i-th element; if this macro is not
  29  *                      defined, the function gets a pointer to an array to be sorted
  30  *  ASORT_LT(x,y)       x < y for ASORT_TYPE (default: "x<y")
  31  *  ASORT_SWAP(i,j)     swap i-th and j-th element (default: assume _ELT
  32  *                      is an l-value and swap just the keys)
  33  *  ASORT_THRESHOLD     threshold for switching between quicksort and insertsort
  34  *  ASORT_EXTRA_ARGS    extra arguments for the sort function (they are always
  35  *                      visible in all the macros supplied above), starts with comma
  36  *
  37  *  After including this file, a function ASORT_PREFIX(sort)(uns array_size)
  38  *  or ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, uns array_size) [if ASORT_ELT
  39  *  is not defined] is declared and all parameter macros are automatically
  40  *  undef'd.
  41  */
  42
  43 #ifndef ASORT_LT
  44 #define ASORT_LT(x,y) ((x) < (y))
  45 #endif
  46
  47 #ifndef ASORT_SWAP
  48 #define ASORT_SWAP(i,j) do { ASORT_KEY_TYPE tmp = ASORT_ELT(i); ASORT_ELT(i)=ASORT_ELT(j); ASORT_ELT(j)=tmp; } while (0)
  49 #endif
  50
  51 #ifndef ASORT_THRESHOLD
  52 #define ASORT_THRESHOLD 8               /* Guesswork and experimentation */
  53 #endif
  54
  55 #ifndef ASORT_EXTRA_ARGS
  56 #define ASORT_EXTRA_ARGS
  57 #endif
  58
  59 #ifndef ASORT_ELT
  60 #define ASORT_ARRAY_ARG ASORT_KEY_TYPE *array,
  61 #define ASORT_ELT(i) array[i]
  62 #else
  63 #define ASORT_ARRAY_ARG
  64 #endif
  65
  66 /**
  67  * The generated sorting function. If `ASORT_ELT` macro is not provided, the
  68  * @ASORT_ARRAY_ARG is equal to `ASORT_KEY_TYPE *array` and is the array to be
  69  * sorted. If the macro is provided, this parameter is omitted. In that case,
  70  * you can sort global variables or pass your structure by @ASORT_EXTRA_ARGS.
  71  **/
  72 static void ASORT_PREFIX(sort)(ASORT_ARRAY_ARG uns array_size ASORT_EXTRA_ARGS)
  73 {
  74   struct stk { int l, r; } stack[8*sizeof(uns)];
  75   int l, r, left, right, m;
  76   uns sp = 0;
  77   ASORT_KEY_TYPE pivot;
  78
  79   if (array_size <= 1)
  80     return;
  81
  82   /* QuickSort with optimizations a'la Sedgewick, but stop at ASORT_THRESHOLD */
  83
  84   left = 0;
  85   right = array_size - 1;
  86   for(;;)
  87     {
  88       l = left;
  89       r = right;
  90       m = (l+r)/2;
  91       if (ASORT_LT(ASORT_ELT(m), ASORT_ELT(l)))
  92         ASORT_SWAP(l,m);
  93       if (ASORT_LT(ASORT_ELT(r), ASORT_ELT(m)))
  94         {
  95           ASORT_SWAP(m,r);
  96           if (ASORT_LT(ASORT_ELT(m), ASORT_ELT(l)))
  97             ASORT_SWAP(l,m);
  98         }
  99       pivot = ASORT_ELT(m);
 100       do
 101         {
 102           while (ASORT_LT(ASORT_ELT(l), pivot))
 103             l++;
 104           while (ASORT_LT(pivot, ASORT_ELT(r)))
 105             r--;
 106           if (l < r)
 107             {
 108               ASORT_SWAP(l,r);
 109               l++;
 110               r--;
 111             }
 112           else if (l == r)
 113             {
 114               l++;
 115               r--;
 116             }
 117         }
 118       while (l <= r);
 119       if ((r - left) >= ASORT_THRESHOLD && (right - l) >= ASORT_THRESHOLD)
 120         {
 121           /* Both partitions ok => push the larger one */
 122           if ((r - left) > (right - l))
 123             {
 124               stack[sp].l = left;
 125               stack[sp].r = r;
 126               left = l;
 127             }
 128           else
 129             {
 130               stack[sp].l = l;
 131               stack[sp].r = right;
 132               right = r;
 133             }
 134           sp++;
 135         }
 136       else if ((r - left) >= ASORT_THRESHOLD)
 137         {
 138           /* Left partition OK, right undersize */
 139           right = r;
 140         }
 141       else if ((right - l) >= ASORT_THRESHOLD)
 142         {
 143           /* Right partition OK, left undersize */
 144           left = l;
 145         }
 146       else
 147         {
 148           /* Both partitions undersize => pop */
 149           if (!sp)
 150             break;
 151           sp--;
 152           left = stack[sp].l;
 153           right = stack[sp].r;
 154         }
 155     }
 156
 157   /*
 158    * We have a partially sorted array, finish by insertsort. Inspired
 159    * by qsort() in GNU libc.
 160    */
 161
 162   /* Find minimal element which will serve as a barrier */
 163   r = MIN(array_size, ASORT_THRESHOLD);
 164   m = 0;
 165   for (l=1; l<r; l++)
 166     if (ASORT_LT(ASORT_ELT(l),ASORT_ELT(m)))
 167       m = l;
 168   ASORT_SWAP(0,m);
 169
 170   /* Insertion sort */
 171   for (m=1; m<(int)array_size; m++)
 172     {
 173       l=m;
 174       while (ASORT_LT(ASORT_ELT(m),ASORT_ELT(l-1)))
 175         l--;
 176       while (l < m)
 177         {
 178           ASORT_SWAP(l,m);
 179           l++;
 180         }
 181     }
 182 }
 183
 184 #undef ASORT_PREFIX
 185 #undef ASORT_KEY_TYPE
 186 #undef ASORT_ELT
 187 #undef ASORT_LT
 188 #undef ASORT_SWAP
 189 #undef ASORT_THRESHOLD
 190 #undef ASORT_EXTRA_ARGS
 191 #undef ASORT_ARRAY_ARG