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