home *** CD-ROM | disk | FTP | other *** search
/ OpenStep 4.2J (Developer) / os42jdev.iso / NextDeveloper / Source / GNU / emacs / etc / qsort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-09-17  |  5.5 KB  |  227 lines
  1. /*
  2.  * qsort.c:
  3.  * Our own version of the system qsort routine which is faster by an average
  4.  * of 25%, with lows and highs of 10% and 50%.
  5.  * The THRESHold below is the insertion sort threshold, and has been adjusted
  6.  * for records of size 48 bytes.
  7.  * The MTHREShold is where we stop finding a better median.
  8.  */
  9.  
  10. #define        THRESH        4        /* threshold for insertion */
  11.  
  12. #define        MTHRESH        6        /* threshold for median */
  13.  
  14.  
  15.  
  16. static  int        qsz;            /* size of each record */
  17. static  int        (*qcmp)();        /* the comparison routine */
  18.  
  19. static  int        thresh;            /* THRESHold in chars */
  20. static  int        mthresh;        /* MTHRESHold in chars */
  21.  
  22. /*
  23.  * qsort:
  24.  * First, set up some global parameters for qst to share.  Then, quicksort
  25.  * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
  26.  * It's not...
  27.  */
  28. qsort (base, n, size, compar)
  29.      char *base;
  30.      int n;
  31.      int size;
  32.      int (*compar)();
  33. {
  34.   register char *i, *j, *lo, *hi, *min;
  35.   register int c;
  36.   char *max;
  37.  
  38.   if (n <= 1)  return;
  39.   qsz = size;
  40.   qcmp = compar;
  41.   thresh = qsz*THRESH;
  42.   mthresh = qsz*MTHRESH;
  43.   max = base + n*qsz;
  44.   if (n >= THRESH)
  45.     {
  46.       qst (base, max);
  47.       hi = base + thresh;
  48.     }
  49.   else
  50.     {
  51.       hi = max;
  52.     }
  53.   /*
  54.    * First put smallest element, which must be in the first THRESH, in
  55.    * the first position as a sentinel.  This is done just by searching
  56.    * the first THRESH elements (or the first n if n < THRESH), finding
  57.    * the min, and swapping it into the first position.
  58.    */
  59.   for (j = lo = base; (lo += qsz) < hi; )
  60.     {
  61.       if ((*qcmp) (j, lo) > 0)
  62.     j = lo;
  63.     }
  64.   if (j != base)
  65.     {            /* swap j into place */
  66.       for (i = base, hi = base + qsz; i < hi;)
  67.     {
  68.       c = *j;
  69.       *j++ = *i;
  70.       *i++ = c;
  71.     }
  72.     }
  73.   /*
  74.    * With our sentinel in place, we now run the following hyper-fast
  75.    * insertion sort.  For each remaining element, min, from [1] to [n-1],
  76.    * set hi to the index of the element AFTER which this one goes.
  77.    * Then, do the standard insertion sort shift on a character at a time
  78.    * basis for each element in the frob.
  79.    */
  80.   for (min = base; (hi = min += qsz) < max;)
  81.     {
  82.       while ( (*qcmp) (hi -= qsz, min) > 0);
  83.       if ((hi += qsz) != min)
  84.     {
  85.       for (lo = min + qsz; --lo >= min;)
  86.         {
  87.           c = *lo;
  88.           for (i = j = lo; (j -= qsz) >= hi; i = j)
  89.         *i = *j;
  90.           *i = c;
  91.         }
  92.     }
  93.     }
  94. }
  95.  
  96. /*
  97.  * qst:
  98.  * Do a quicksort
  99.  * First, find the median element, and put that one in the first place as the
  100.  * discriminator.  (This "median" is just the median of the first, last and
  101.  * middle elements).  (Using this median instead of the first element is a big
  102.  * win).  Then, the usual partitioning/swapping, followed by moving the
  103.  * discriminator into the right place.  Then, figure out the sizes of the two
  104.  * partions, do the smaller one recursively and the larger one via a repeat of
  105.  * this code.  Stopping when there are less than THRESH elements in a partition
  106.  * and cleaning up with an insertion sort (in our caller) is a huge win.
  107.  * All data swaps are done in-line, which is space-losing but time-saving.
  108.  * (And there are only three places where this is done).
  109.  */
  110.  
  111. qst (base, max)
  112.      char *base, *max;
  113. {
  114.   register char *i, *j, *jj, *mid;
  115.   register int ii, c;
  116.   char *tmp;
  117.   int lo, hi;
  118.  
  119.   lo = max - base;        /* number of elements as chars */
  120.   do
  121.     {
  122.       /*
  123.        * At the top here, lo is the number of characters of elements in the
  124.        * current partition.  (Which should be max - base).
  125.        * Find the median of the first, last, and middle element and make that the
  126.        * middle element.  Set j to largest of first and middle.  If max is larger
  127.        * than that guy, then it's that guy, else compare max with loser of first
  128.        * and take larger.  Things are set up to prefer the middle, then the first
  129.        * in case of ties.
  130.        */
  131.       mid = i = base + qsz * ((lo/qsz) >> 1);
  132.       if (lo >= mthresh)
  133.     {
  134.       j = ((*qcmp) ((jj = base), i) > 0 ? jj : i);
  135.       if ((*qcmp) (j, (tmp = max - qsz)) > 0)
  136.         {
  137.           j = (j == jj ? i : jj);    /* switch to first loser */
  138.           if ((*qcmp) (j, tmp) < 0)
  139.         j = tmp;
  140.         }
  141.       if (j != i)
  142.         {
  143.           ii = qsz;
  144.           do
  145.         {
  146.           c = *i;
  147.           *i++ = *j;
  148.           *j++ = c;
  149.         }
  150.           while(  --ii  );
  151.         }
  152.     }
  153.       /*
  154.        * Semi-standard quicksort partitioning/swapping
  155.        */
  156.       for (i = base, j = max - qsz; ;)
  157.     {
  158.       while (i < mid && (*qcmp) (i, mid) <= 0)
  159.         i += qsz;
  160.       while (j > mid)
  161.         {
  162.           if ((*qcmp) (mid, j) <= 0)
  163.         {
  164.           j -= qsz;
  165.           continue;
  166.         }
  167.           tmp = i + qsz;        /* value of i after swap */
  168.           if (i == mid)
  169.         {    /* j <-> mid, new mid is j */
  170.           mid = jj = j;
  171.         }
  172.           else
  173.         {            /* i <-> j */
  174.           jj = j;
  175.           j -= qsz;
  176.         }
  177.           goto  swap;
  178.         }
  179.       if (i == mid)
  180.         {
  181.           break;
  182.         }
  183.       else
  184.         {                /* i <-> mid, new mid is i */
  185.           jj = mid;
  186.           tmp = mid = i;        /* value of i after swap */
  187.           j -= qsz;
  188.         }
  189.     swap:
  190.       ii = qsz;
  191.       do
  192.         {
  193.           c = *i;
  194.           *i++ = *jj;
  195.           *jj++ = c;
  196.         }
  197.       while (--ii);
  198.       i = tmp;
  199.     }
  200.       /*
  201.        * Look at sizes of the two partitions, do the smaller one first by
  202.        * recursion, then do the larger one by making sure lo is its size,
  203.        * base and max are update correctly, and branching back.
  204.        * But only repeat (recursively or by branching) if the partition is
  205.        * of at least size THRESH.
  206.        */
  207.       i = (j = mid) + qsz;
  208.       if ((lo = j - base) <= (hi = max - i))
  209.     {
  210.       if (lo >= thresh)
  211.         qst (base, j);
  212.       base = i;
  213.       lo = hi;
  214.     }
  215.       else
  216.     {
  217.       if (hi >= thresh)
  218.         qst (i, max);
  219.       max = j;
  220.     }
  221.     }
  222.   while (lo >= thresh);
  223. }
  224.  
  225.  
  226.  
  227.