lib/arraysort.h

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