lib/msvcrt/stdlib/qsort.c

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