![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to qsort.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / lib / libc / gen|
Return to qsort.c CVS log | Up to [CSRG BSD Unix] / 43BSD / lib / libc / gen |
1.1 root 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: 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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.