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