lib/crtdll/stdlib/qsort.c

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