lib/arraysort.h

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