reactos/sdk/lib/crt/stdlib/qsort.c

   1 /* Copyright (C) 1994 DJ Delorie, see COPYING.DJ for details */
   2
   3 #include <stdlib.h>
   4 #include <search.h>
   5
   6 /*-
   7  * Copyright (c) 1980, 1983 The Regents of the University of California.
   8  * All rights reserved.
   9  *
  10  * Redistribution and use in source and binary forms are permitted
  11  * provided that: (1) source distributions retain this entire copyright
  12  * notice and comment, and (2) distributions including binaries display
  13  * the following acknowledgement:  ``This product includes software
  14  * developed by the University of California, Berkeley and its contributors''
  15  * in the documentation or other materials provided with the distribution
  16  * and in all advertising materials mentioning features or use of this
  17  * software. Neither the name of the University nor the names of its
  18  * contributors may be used to endorse or promote products derived
  19  * from this software without specific prior written permission.
  20  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  21  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  22  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  23  */
  24
  25 /*
  26  * qsort.c:
  27  * Our own version of the system qsort routine which is faster by an average
  28  * of 25%, with lows and highs of 10% and 50%.
  29  * The THRESHold below is the insertion sort threshold, and has been adjusted
  30  * for records of size 48 bytes.
  31  * The MTHREShold is where we stop finding a better median.
  32  */
  33
  34 #define         THRESH          4               /* threshold for insertion */
  35 #define         MTHRESH         6               /* threshold for median */
  36
  37 /*
  38  * qst:
  39  * Do a quicksort
  40  * First, find the median element, and put that one in the first place as the
  41  * discriminator.  (This "median" is just the median of the first, last and
  42  * middle elements).  (Using this median instead of the first element is a big
  43  * win).  Then, the usual partitioning/swapping, followed by moving the
  44  * discriminator into the right place.  Then, figure out the sizes of the two
  45  * partions, do the smaller one recursively and the larger one via a repeat of
  46  * this code.  Stopping when there are less than THRESH elements in a partition
  47  * and cleaning up with an insertion sort (in our caller) is a huge win.
  48  * All data swaps are done in-line, which is space-losing but time-saving.
  49  * (And there are only three places where this is done).
  50  */
  51
  52 static void __cdecl
  53 qst(size_t size, int (__cdecl *compar)(const void*, const void*), char *base, char *max)
  54 {
  55   char c, *i, *j, *jj;
  56   size_t ii;
  57   char *mid, *tmp;
  58   size_t lo, hi;
  59   size_t thresh;
  60   size_t mthresh;
  61
  62   thresh = size * THRESH;
  63   mthresh = size * MTHRESH;
  64
  65   /*
  66    * At the top here, lo is the number of characters of elements in the
  67    * current partition.  (Which should be max - base).
  68    * Find the median of the first, last, and middle element and make
  69    * that the middle element.  Set j to largest of first and middle.
  70    * If max is larger than that guy, then it's that guy, else compare
  71    * max with loser of first and take larger.  Things are set up to
  72    * prefer the middle, then the first in case of ties.
  73    */
  74   lo = max - base;              /* number of elements as chars */
  75   do    {
  76     mid = i = base + size * ((lo / size) >> 1);
  77     if (lo >= mthresh)
  78     {
  79       j = (compar((jj = base), i) > 0 ? jj : i);
  80       if (compar(j, (tmp = max - size)) > 0)
  81       {
  82         /* switch to first loser */
  83         j = (j == jj ? i : jj);
  84         if (compar(j, tmp) < 0)
  85           j = tmp;
  86       }
  87       if (j != i)
  88       {
  89         ii = size;
  90         do      {
  91           c = *i;
  92           *i++ = *j;
  93           *j++ = c;
  94         } while (--ii);
  95       }
  96     }
  97     /*
  98      * Semi-standard quicksort partitioning/swapping
  99      */
 100     for (i = base, j = max - size; ; )
 101     {
 102       while (i < mid && compar(i, mid) <= 0)
 103         i += size;
 104       while (j > mid)
 105       {
 106         if (compar(mid, j) <= 0)
 107         {
 108           j -= size;
 109           continue;
 110         }
 111         tmp = i + size; /* value of i after swap */
 112         if (i == mid)
 113         {
 114           /* j <-> mid, new mid is j */
 115           mid = jj = j;
 116         }
 117         else
 118         {
 119           /* i <-> j */
 120           jj = j;
 121           j -= size;
 122         }
 123         goto swap;
 124       }
 125       if (i == mid)
 126       {
 127         break;
 128       }
 129       else
 130       {
 131         /* i <-> mid, new mid is i */
 132         jj = mid;
 133         tmp = mid = i;          /* value of i after swap */
 134         j -= size;
 135       }
 136     swap:
 137       ii = size;
 138       do        {
 139         c = *i;
 140         *i++ = *jj;
 141         *jj++ = c;
 142       } while (--ii);
 143       i = tmp;
 144     }
 145     /*
 146      * Look at sizes of the two partitions, do the smaller
 147      * one first by recursion, then do the larger one by
 148      * making sure lo is its size, base and max are update
 149      * correctly, and branching back.  But only repeat
 150      * (recursively or by branching) if the partition is
 151      * of at least size THRESH.
 152      */
 153     i = (j = mid) + size;
 154     if ((lo = j - base) <= (hi = max - i))
 155     {
 156       if (lo >= thresh)
 157         qst(size, compar, base, j);
 158       base = i;
 159       lo = hi;
 160     }
 161     else
 162     {
 163       if (hi >= thresh)
 164         qst(size, compar, i, max);
 165       max = j;
 166     }
 167   } while (lo >= thresh);
 168 }
 169
 170 /*
 171  * qsort:
 172  * First, set up some global parameters for qst to share.  Then, quicksort
 173  * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
 174  * It's not...
 175  *
 176  * @implemented
 177  */
 178 void
 179 __cdecl
 180 qsort(void *base0, size_t n, size_t size, int (__cdecl *compar)(const void*, const void*))
 181 {
 182   char *base = (char *)base0;
 183   char c, *i, *j, *lo, *hi;
 184   char *min, *max;
 185   size_t thresh;
 186
 187   if (n <= 1)
 188     return;
 189
 190   if (size == 0)
 191     return;
 192   compar = compar;
 193   thresh = size * THRESH;
 194   max = base + n * size;
 195   if (n >= THRESH)
 196   {
 197     qst(size, compar, base, max);
 198     hi = base + thresh;
 199   }
 200   else
 201   {
 202     hi = max;
 203   }
 204   /*
 205    * First put smallest element, which must be in the first THRESH, in
 206    * the first position as a sentinel.  This is done just by searching
 207    * the first THRESH elements (or the first n if n < THRESH), finding
 208    * the min, and swapping it into the first position.
 209    */
 210   for (j = lo = base; (lo += size) < hi; )
 211     if (compar(j, lo) > 0)
 212       j = lo;
 213   if (j != base)
 214   {
 215     /* swap j into place */
 216     for (i = base, hi = base + size; i < hi; )
 217     {
 218       c = *j;
 219       *j++ = *i;
 220       *i++ = c;
 221     }
 222   }
 223   /*
 224    * With our sentinel in place, we now run the following hyper-fast
 225    * insertion sort.  For each remaining element, min, from [1] to [n-1],
 226    * set hi to the index of the element AFTER which this one goes.
 227    * Then, do the standard insertion sort shift on a character at a time
 228    * basis for each element in the frob.
 229    */
 230   for (min = base; (hi = min += size) < max; )
 231   {
 232     while (compar(hi -= size, min) > 0)
 233       /* void */;
 234     if ((hi += size) != min) {
 235       for (lo = min + size; --lo >= min; )
 236       {
 237         c = *lo;
 238         for (i = j = lo; (j -= size) >= hi; i = j)
 239           *i = *j;
 240         *i = c;
 241       }
 242     }
 243   }
 244 }