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
  61 #define ASORT_ELT(i) array[i]
  62 #endif
  63
  64 static void ASORT_PREFIX(sort)(
  65 #ifdef ASORT_ARRAY_ARG
  66   ASORT_KEY_TYPE *array,
  67 #endif
  68   uns array_size ASORT_EXTRA_ARGS)
  69 {
  70   struct stk { int l, r; } stack[8*sizeof(uns)];
  71   int l, r, left, right, m;
  72   uns sp = 0;
  73   ASORT_KEY_TYPE pivot;
  74
  75   if (array_size <= 1)
  76     return;
  77
  78   /* QuickSort with optimizations a'la Sedgewick, but stop at ASORT_THRESHOLD */
  79
  80   left = 0;
  81   right = array_size - 1;
  82   for(;;)
  83     {
  84       l = left;
  85       r = right;
  86       m = (l+r)/2;
  87       if (ASORT_LT(ASORT_ELT(m), ASORT_ELT(l)))
  88         ASORT_SWAP(l,m);
  89       if (ASORT_LT(ASORT_ELT(r), ASORT_ELT(m)))
  90         {
  91           ASORT_SWAP(m,r);
  92           if (ASORT_LT(ASORT_ELT(m), ASORT_ELT(l)))
  93             ASORT_SWAP(l,m);
  94         }
  95       pivot = ASORT_ELT(m);
  96       do
  97         {
  98           while (ASORT_LT(ASORT_ELT(l), pivot))
  99             l++;
 100           while (ASORT_LT(pivot, ASORT_ELT(r)))
 101             r--;
 102           if (l < r)
 103             {
 104               ASORT_SWAP(l,r);
 105               l++;
 106               r--;
 107             }
 108           else if (l == r)
 109             {
 110               l++;
 111               r--;
 112             }
 113         }
 114       while (l <= r);
 115       if ((r - left) >= ASORT_THRESHOLD && (right - l) >= ASORT_THRESHOLD)
 116         {
 117           /* Both partitions ok => push the larger one */
 118           if ((r - left) > (right - l))
 119             {
 120               stack[sp].l = left;
 121               stack[sp].r = r;
 122               left = l;
 123             }
 124           else
 125             {
 126               stack[sp].l = l;
 127               stack[sp].r = right;
 128               right = r;
 129             }
 130           sp++;
 131         }
 132       else if ((r - left) >= ASORT_THRESHOLD)
 133         {
 134           /* Left partition OK, right undersize */
 135           right = r;
 136         }
 137       else if ((right - l) >= ASORT_THRESHOLD)
 138         {
 139           /* Right partition OK, left undersize */
 140           left = l;
 141         }
 142       else
 143         {
 144           /* Both partitions undersize => pop */
 145           if (!sp)
 146             break;
 147           sp--;
 148           left = stack[sp].l;
 149           right = stack[sp].r;
 150         }
 151     }
 152
 153   /*
 154    * We have a partially sorted array, finish by insertsort. Inspired
 155    * by qsort() in GNU libc.
 156    */
 157
 158   /* Find minimal element which will serve as a barrier */
 159   r = MIN(array_size, ASORT_THRESHOLD);
 160   m = 0;
 161   for (l=1; l<r; l++)
 162     if (ASORT_LT(ASORT_ELT(l),ASORT_ELT(m)))
 163       m = l;
 164   ASORT_SWAP(0,m);
 165
 166   /* Insertion sort */
 167   for (m=1; m<(int)array_size; m++)
 168     {
 169       l=m;
 170       while (ASORT_LT(ASORT_ELT(m),ASORT_ELT(l-1)))
 171         l--;
 172       while (l < m)
 173         {
 174           ASORT_SWAP(l,m);
 175           l++;
 176         }
 177     }
 178 }
 179
 180 #undef ASORT_PREFIX
 181 #undef ASORT_KEY_TYPE
 182 #undef ASORT_ELT
 183 #undef ASORT_LT
 184 #undef ASORT_SWAP
 185 #undef ASORT_THRESHOLD
 186 #undef ASORT_EXTRA_ARGS
 187 #undef ASORT_ARRAY_ARG