home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume26 / mytinfo / part02 / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-26  |  6.1 KB  |  245 lines
  1. /*
  2.  * qsort.c
  3.  *
  4.  * This came from the GNU Emacs (18.55) tape.
  5.  * Modified by Ross Ridge for use in mytinfo
  6.  * 92/06/04 11:39:25
  7.  *
  8.  */
  9.  
  10. #ifdef USE_MYQSORT
  11.  
  12. #ifdef USE_SCCS_IDS
  13. static const char SCCSid[] = "@(#) mytinfo qsort.c 3.3 92/06/04 public domain, By Ross Ridge";
  14. #endif
  15.  
  16. /*
  17.  * qsort.c:
  18.  * Our own version of the system qsort routine which is faster by an average
  19.  * of 25%, with lows and highs of 10% and 50%.
  20.  * The THRESHold below is the insertion sort threshold, and has been adjusted
  21.  * for records of size 48 bytes.
  22.  * The MTHREShold is where we stop finding a better median.
  23.  */
  24.  
  25. #define        THRESH        4        /* threshold for insertion */
  26.  
  27. #define        MTHRESH        6        /* threshold for median */
  28.  
  29.  
  30.  
  31. static  int        qsz;            /* size of each record */
  32. static  compar_fn    qcmp;            /* the comparison routine */
  33.  
  34. static  int        thresh;            /* THRESHold in chars */
  35. static  int        mthresh;        /* MTHRESHold in chars */
  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. static void
  52. qst (base, max)
  53.      char *base; char *max;
  54. {
  55.   register char *i, *j, *jj, *mid;
  56.   register int ii, c;
  57.   char *tmp;
  58.   int lo, hi;
  59.  
  60.   lo = max - base;    /* number of elements as chars */
  61.   do
  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 that the
  67.        * middle element.  Set j to largest of first and middle.  If max is larger
  68.        * than that guy, then it's that guy, else compare max with loser of first
  69.        * and take larger.  Things are set up to prefer the middle, then the first
  70.        * in case of ties.
  71.        */
  72.       mid = i = base + qsz * ((lo/qsz) >> 1);
  73.       if (lo >= mthresh)
  74.     {
  75.       j = ((*qcmp) ((anyptr)(jj = base), (anyptr)i) > 0 ? jj : i);
  76.       if ((*qcmp) ((anyptr)j, (anyptr)(tmp = max - qsz)) > 0)
  77.         {
  78.           j = (j == jj ? i : jj);    /* switch to first loser */
  79.           if ((*qcmp) ((anyptr)j, (anyptr)tmp) < 0)
  80.         j = tmp;
  81.         }
  82.       if (j != i)
  83.         {
  84.           ii = qsz;
  85.           do
  86.         {
  87.           c = *i;
  88.           *i++ = *j;
  89.           *j++ = c;
  90.         }
  91.           while(  --ii  );
  92.         }
  93.     }
  94.       /*
  95.        * Semi-standard quicksort partitioning/swapping
  96.        */
  97.       for (i = base, j = max - qsz; ;)
  98.     {
  99.       while (i < mid && (*qcmp) ((anyptr)i, (anyptr)mid) <= 0)
  100.         i += qsz;
  101.       while (j > mid)
  102.         {
  103.           if ((*qcmp) ((anyptr)mid, (anyptr)j) <= 0)
  104.         {
  105.           j -= qsz;
  106.           continue;
  107.         }
  108.           tmp = i + qsz;        /* value of i after swap */
  109.           if (i == mid)
  110.         {    /* j <-> mid, new mid is j */
  111.           mid = jj = j;
  112.         }
  113.           else
  114.         {            /* i <-> j */
  115.           jj = j;
  116.           j -= qsz;
  117.         }
  118.           goto  swap;
  119.         }
  120.       if (i == mid)
  121.         {
  122.           break;
  123.         }
  124.       else
  125.         {                /* i <-> mid, new mid is i */
  126.           jj = mid;
  127.           tmp = mid = i;        /* value of i after swap */
  128.           j -= qsz;
  129.         }
  130.     swap:
  131.       ii = qsz;
  132.       do
  133.         {
  134.           c = *i;
  135.           *i++ = *jj;
  136.           *jj++ = c;
  137.         }
  138.       while (--ii);
  139.       i = tmp;
  140.     }
  141.       /*
  142.        * Look at sizes of the two partitions, do the smaller one first by
  143.        * recursion, then do the larger one by making sure lo is its size,
  144.        * base and max are update correctly, and branching back.
  145.        * But only repeat (recursively or by branching) if the partition is
  146.        * of at least size THRESH.
  147.        */
  148.       i = (j = mid) + qsz;
  149.       if ((lo = j - base) <= (hi = max - i))
  150.     {
  151.       if (lo >= thresh)
  152.         qst (base, j);
  153.       base = i;
  154.       lo = hi;
  155.     }
  156.       else
  157.     {
  158.       if (hi >= thresh)
  159.         qst (i, max);
  160.       max = j;
  161.     }
  162.     }
  163.   while (lo >= thresh);
  164. }
  165.  
  166.  
  167. /*
  168.  * qsort:
  169.  * First, set up some global parameters for qst to share.  Then, quicksort
  170.  * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
  171.  * It's not...
  172.  */
  173. static void
  174. qsort (base, n, size, compar)
  175.      anyptr base;
  176.      unsigned n;
  177.      mysize_t size;
  178.      compar_fn compar;
  179. {
  180.   register char *i, *j, *lo, *hi, *min;
  181.   register int c;
  182.   char *max;
  183.  
  184.   if (n <= 1)  return;
  185.   qsz = size / sizeof(char); /* of course if sizeof(char) aint one it had
  186.                 better be an even divisor of size      */
  187.   qcmp = compar;
  188.   thresh = qsz*THRESH;
  189.   mthresh = qsz*MTHRESH;
  190.   max = (char *)base + n*qsz;
  191.   if (n >= THRESH)
  192.     {
  193.       qst ((char *)base, max);
  194.       hi = (char *)base + thresh;
  195.     }
  196.   else
  197.     {
  198.       hi = max;
  199.     }
  200.   /*
  201.    * First put smallest element, which must be in the first THRESH, in
  202.    * the first position as a sentinel.  This is done just by searching
  203.    * the first THRESH elements (or the first n if n < THRESH), finding
  204.    * the min, and swapping it into the first position.
  205.    */
  206.   for (j = lo = (char *)base; (lo += qsz) < hi; )
  207.     {
  208.       if ((*qcmp) ((anyptr)j, (anyptr)lo) > 0)
  209.     j = lo;
  210.     }
  211.   if (j != (char *)base)
  212.     {            /* swap j into place */
  213.       for (i = (char *)base, hi = (char *)base + 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 = (char *)base; (hi = min += qsz) < max;)
  228.     {
  229.       while ( (*qcmp) ((anyptr)(hi -= qsz), (anyptr) min) > 0);
  230.       if ((hi += qsz) != min)
  231.     {
  232.       for (lo = min + qsz; --lo >= min;)
  233.         {
  234.           c = *lo;
  235.           for (i = j = lo; (j -= qsz) >= hi; i = j)
  236.         *i = *j;
  237.           *i = c;
  238.         }
  239.     }
  240.     }
  241. }
  242.  
  243.  
  244. #endif /* USE_MYQSORT */
  245.