Back to index

tetex-bin  3.0
Defines | Functions | Variables
qsort.c File Reference
#include "mkind.h"

Go to the source code of this file.

Defines

#define THRESH   4 /* threshold for insertion */
#define MTHRESH   6 /* threshold for median */

Functions

static int qcmp ARGS ((char *, char *))
static void qst ARGS ((char *base, char *max))
void qqsort (char *base, int n, int size, int *compar)
static void qst (char *base, char *max)

Variables

static int qsz
static int thresh
static int mthresh

Define Documentation

#define MTHRESH   6 /* threshold for median */

Definition at line 22 of file qsort.c.

#define THRESH   4 /* threshold for insertion */

Definition at line 21 of file qsort.c.


Function Documentation

static int qcmp ARGS ( (char *, char *)  ) [static]
static void qst ARGS ( (char *base, char *max ) [static]
void qqsort ( char *  base,
int  n,
int  size,
int compar 
)

Definition at line 40 of file qsort.c.

{
    register char *i;
    register char *j;
    register char *lo;
    register char *hi;
    register char *min;
    register char c;
    char   *max;

    if (n <= 1)
       return;
    qsz = size;
    qcmp = compar;
    thresh = qsz * THRESH;
    mthresh = qsz * MTHRESH;
    max = base + n * qsz;
    if (n >= THRESH) {
       qst(base, max);
       hi = base + thresh;
    } else {
       hi = max;
    }
    /*
     * First put smallest element, which must be in the first THRESH, in the
     * first position as a sentinel.  This is done just by searching the
     * first THRESH elements (or the first n if n < THRESH), finding the min,
     * and swapping it into the first position.
     */
    for (j = lo = base; (lo += qsz) < hi;) {
       if ((*qcmp) (j, lo) > 0)
           j = lo;
    }
    if (j != base) {               /* swap j into place */
       for (i = base, hi = base + qsz; i < hi;) {
           c = *j;
           *j++ = *i;
           *i++ = c;
       }
    }
    /*
     * With our sentinel in place, we now run the following hyper-fast
     * insertion sort. For each remaining element, min, from [1] to [n-1],
     * set hi to the index of the element AFTER which this one goes. Then, do
     * the standard insertion sort shift on a character at a time basis for
     * each element in the frob.
     */
    for (min = base; (hi = min += qsz) < max;) {
       while ((*qcmp) (hi -= qsz, min) > 0);
       if ((hi += qsz) != min) {
           for (lo = min + qsz; --lo >= min;) {
              c = *lo;
              for (i = j = lo; (j -= qsz) >= hi; i = j)
                  *i = *j;
              *i = c;
           }
       }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void qst ( char *  base,
char *  max 
) [static]

Definition at line 125 of file qsort.c.

{
    register char *i;
    register char *j;
    register char *jj;
    register char *mid;
    register int ii;
    register char c;
    char   *tmp;
    int     lo;
    int     hi;

    lo = (int)(max - base);        /* number of elements as chars */
    do {
       /*
        * At the top here, lo is the number of characters of elements in the
        * current partition.  (Which should be max - base). Find the median
        * of the first, last, and middle element and make that the middle
        * element.  Set j to largest of first and middle.  If max is larger
        * than that guy, then it's that guy, else compare max with loser of
        * first and take larger.  Things are set up to prefer the middle,
        * then the first in case of ties.
        */
       mid = i = base + qsz * ((unsigned) (lo / qsz) >> 1);
       if (lo >= mthresh) {
           j = ((*qcmp) ((jj = base), i) > 0 ? jj : i);
           if ((*qcmp) (j, (tmp = max - qsz)) > 0) {
              /* switch to first loser */
              j = (j == jj ? i : jj);
              if ((*qcmp) (j, tmp) < 0)
                  j = tmp;
           }
           if (j != i) {
              ii = qsz;
              do {
                  c = *i;
                  *i++ = *j;
                  *j++ = c;
              } while (--ii);
           }
       }
       /* Semi-standard quicksort partitioning/swapping */
       for (i = base, j = max - qsz;;) {
           while (i < mid && (*qcmp) (i, mid) <= 0)
              i += qsz;
           while (j > mid) {
              if ((*qcmp) (mid, j) <= 0) {
                  j -= qsz;
                  continue;
              }
              tmp = i + qsz;              /* value of i after swap */
              if (i == mid) {             /* j <-> mid, new mid is j */
                  mid = jj = j;
              } else {             /* i <-> j */
                  jj = j;
                  j -= qsz;
              }
              goto swap;
           }
           if (i == mid) {
              break;
           } else {                /* i <-> mid, new mid is i */
              jj = mid;
              tmp = mid = i;              /* value of i after swap */
              j -= qsz;
           }
    swap:
           ii = qsz;
           do {
              c = *i;
              *i++ = *jj;
              *jj++ = c;
           } while (--ii);
           i = tmp;
       }
       /*
        * Look at sizes of the two partitions, do the smaller one first by
        * recursion, then do the larger one by making sure lo is its size,
        * base and max are update correctly, and branching back. But only
        * repeat (recursively or by branching) if the partition is of at
        * least size THRESH.
        */
       i = (j = mid) + qsz;
       if ((lo = (int)(j - base)) <= (hi = (int)(max - i))) {
           if (lo >= thresh)
              qst(base, j);
           base = i;
           lo = hi;
       } else {
           if (hi >= thresh)
              qst(i, max);
           max = j;
       }
    } while (lo >= thresh);
}

Here is the caller graph for this function:


Variable Documentation

int mthresh [static]

Definition at line 26 of file qsort.c.

int qsz [static]

Definition at line 24 of file qsort.c.

int thresh [static]

Definition at line 25 of file qsort.c.