# 2.11BSD#431 - /usr/src/lib/libc/gen/qsort.c

##### Functions

    qsort             X

##### Macros

    MTHRESH           X
    THRESH            X

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

#### Defined functions

qsort defined in line 35; used 70 times

- in /usr/include/stdlib.h line 80
- in /usr/ingres/source/dbu/ksort.c line 218
- in /usr/src/bin/csh/sh.file.c line 441
- in /usr/src/bin/csh/sh.glob.c line 28
- in /usr/src/bin/diff/diffdir.c line 224
- in /usr/src/bin/ls/ls.c line 177, 227
- in /usr/src/bin/nm/nm.c line 178
- in /usr/src/bin/ps.c line 514, 703
- in /usr/src/bin/tcsh/glob.c line 402
- in /usr/src/bin/tcsh/sh.file.c line 568
- in /usr/src/bin/tcsh/sh.types.h line 140
- in /usr/src/bin/tcsh/tc.func.c line 1099
- in /usr/src/bin/tcsh/tc.os.h line 298-301(2)
- in /usr/src/bin/tcsh/tw.init.c line 76
- in /usr/src/bin/tcsh/tw.parse.c line 1003
- in /usr/src/games/atc/log.c line 177
- in /usr/src/games/boggle/boggle.c line 599
- in /usr/src/games/fortune/strfile.c line 299
- in /usr/src/games/hack/hack.mklev.c line 105
- in /usr/src/games/robots/score.c line 76
- in /usr/src/games/wump.c line 149
- in /usr/src/lib/libc/gen/scandir.c line 79
- in /usr/src/new/OLD/apl/src/a0.c line 240
- in /usr/src/new/OLD/apl/src/aa.c line 76
- in /usr/src/new/PORT/apl/src/a0.c line 240
- in /usr/src/new/PORT/apl/src/aa.c line 76
- in /usr/src/new/jove/mac.c line 731
- in /usr/src/new/jove/recover.c line 206
- in /usr/src/new/jove/scandir.c line 121, 186
- in /usr/src/new/nntp/server/active.c line 111
- in /usr/src/new/nntp/server/scandir.c line 47
- in /usr/src/new/nntp/support/mkgrdates.c line 124
- in /usr/src/new/notes/src/acssort.c line 54
- in /usr/src/new/pathalias/arpatxt.c line 350, 365
- in /usr/src/old/dump/dumpoptr.c line 290
- in /usr/src/sbin/dump/dumpoptr.c line 278
- in /usr/src/share/zoneinfo/zic.c line 513
- in /usr/src/sys/conf/netbind.c line 283, 307
- in /usr/src/ucb/Mail/cmd2.c line 502
- in /usr/src/ucb/Mail/cmd3.c line 502
- in /usr/src/ucb/PORT/pascal/src/pccaseop.c line 220
- in /usr/src/ucb/error/errorfilter.c line 87
- in /usr/src/ucb/error/errormain.c line 155
- in /usr/src/ucb/ex/exrecover.c line 295
- in /usr/src/ucb/finger/sprint.c line 116
- in /usr/src/ucb/rdist/expand.c line 36
- in /usr/src/ucb/ruptime.c line 123
- in /usr/src/ucb/rwho.c line 108
- in /usr/src/ucb/users.c line 68
- in /usr/src/usr.bin/prof/prof.c line 172, 207, 356
- in /usr/src/usr.bin/refer/refer7.c line 145
- in /usr/src/usr.bin/uucp/uuq.c line 149
- in /usr/src/usr.lib/libU77/qsort_.c line 35
- in /usr/src/usr.sbin/lpr/common.c line 202
- in /usr/src/usr.sbin/lpr/pac.c line 223
- in /usr/src/usr.sbin/named/named/ns_forw.c line 261
- in /usr/src/usr.sbin/quot/quot.c line 211
- in /usr/src/usr.sbin/sa/sa.c line 464
- in /usr/src/usr.sbin/sendmail.MX/src/queue.c line 486
- in /usr/src/usr.sbin/sendmail/src/queue.c line 473
- in /usr/src/usr.sbin/trpt/trpt.c line 163
- in /usr/src/usr.sbin/trsp/trsp.c line 185

qst defined in line 110; used 3 times

- in line 52, 198-203(2)

#### Defined variables

mthresh defined in line 26; used 2 times

- in line 49, 131

qsz defined in line 24; used 23 times

- in line 46-50(4), 63-68(2), 81-87(5), 130-133(3), 140, 151-159(4), 166, 176-179(2), 195

sccsid defined in line 8; never used
thresh defined in line 25; used 5 times

- in line 48-53(2), 197-206(3)

#### Defined macros

MTHRESH defined in line 21; used 1 times

- in line 49

THRESH defined in line 20; used 2 times

- in line 48-51(2)

Last modified: 1990-07-25 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 689 |