1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22 /*
23 * Copyright 1990 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 #pragma ident "%Z%%M% %I% %E% SMI"
28
29 /*
30 * qsort.c:
31 * Our own version of the system qsort routine which is faster by an average
32 * of 25%, with lows and highs of 10% and 50%.
33 * The THRESHold below is the insertion sort threshold, and has been adjusted
34 * for records of size 48 bytes.
35 * The MTHREShold is where we stop finding a better median.
36 */
37
38 #define THRESH 4 /* threshold for insertion */
39 #define MTHRESH 6 /* threshold for median */
40
41 static int (*qcmp)(); /* the comparison routine */
42 static int qsz; /* size of each record */
43 static int thresh; /* THRESHold in chars */
44 static int mthresh; /* MTHRESHold in chars */
45
46 static void qst(char *, char *);
47
48 /*
49 * qsort:
50 * First, set up some global parameters for qst to share. Then, quicksort
51 * with qst(), and then a cleanup insertion sort ourselves. Sound simple?
52 * It's not...
53 */
54
55 void
qsort(char * base,int n,int size,int (* compar)())56 qsort(char *base, int n, int size, int (*compar)())
57 {
58 char c, *i, *j, *lo, *hi;
59 char *min, *max;
60
61 if (n <= 1)
62 return;
63 qsz = size;
64 qcmp = compar;
65 thresh = qsz * THRESH;
66 mthresh = qsz * MTHRESH;
67 max = base + n * qsz;
68 if (n >= THRESH) {
69 qst(base, max);
70 hi = base + thresh;
71 } else {
72 hi = max;
73 }
74 /*
75 * First put smallest element, which must be in the first THRESH, in
76 * the first position as a sentinel. This is done just by searching
77 * the first THRESH elements (or the first n if n < THRESH), finding
78 * the min, and swapping it into the first position.
79 */
80 for (j = lo = base; (lo += qsz) < hi; )
81 if (qcmp(j, lo) > 0)
82 j = lo;
83 if (j != base) {
84 /* swap j into place */
85 for (i = base, hi = base + qsz; i < hi; ) {
86 c = *j;
87 *j++ = *i;
88 *i++ = c;
89 }
90 }
91 /*
92 * With our sentinel in place, we now run the following hyper-fast
93 * insertion sort. For each remaining element, min, from [1] to [n-1],
94 * set hi to the index of the element AFTER which this one goes.
95 * Then, do the standard insertion sort shift on a character at a time
96 * basis for each element in the frob.
97 */
98 for (min = base; (hi = min += qsz) < max; ) {
99 while (qcmp(hi -= qsz, min) > 0)
100 /* void */;
101 if ((hi += qsz) != min) {
102 for (lo = min + qsz; --lo >= min; ) {
103 c = *lo;
104 for (i = j = lo; (j -= qsz) >= hi; i = j)
105 *i = *j;
106 *i = c;
107 }
108 }
109 }
110 }
111
112 /*
113 * qst:
114 * Do a quicksort
115 * First, find the median element, and put that one in the first place as the
116 * discriminator. (This "median" is just the median of the first, last and
117 * middle elements). (Using this median instead of the first element is a big
118 * win). Then, the usual partitioning/swapping, followed by moving the
119 * discriminator into the right place. Then, figure out the sizes of the two
120 * partions, do the smaller one recursively and the larger one via a repeat of
121 * this code. Stopping when there are less than THRESH elements in a partition
122 * and cleaning up with an insertion sort (in our caller) is a huge win.
123 * All data swaps are done in-line, which is space-losing but time-saving.
124 * (And there are only three places where this is done).
125 */
126
127 static void
qst(char * base,char * max)128 qst(char *base, char *max)
129 {
130 char c, *i, *j, *jj;
131 int ii;
132 char *mid, *tmp;
133 int lo, hi;
134
135 /*
136 * At the top here, lo is the number of characters of elements in the
137 * current partition. (Which should be max - base).
138 * Find the median of the first, last, and middle element and make
139 * that the middle element. Set j to largest of first and middle.
140 * If max is larger than that guy, then it's that guy, else compare
141 * max with loser of first and take larger. Things are set up to
142 * prefer the middle, then the first in case of ties.
143 */
144 lo = max - base; /* number of elements as chars */
145 do {
146 mid = i = base + qsz * ((lo / qsz) >> 1);
147 if (lo >= mthresh) {
148 j = (qcmp((jj = base), i) > 0 ? jj : i);
149 if (qcmp(j, (tmp = max - qsz)) > 0) {
150 /* switch to first loser */
151 j = (j == jj ? i : jj);
152 if (qcmp(j, tmp) < 0)
153 j = tmp;
154 }
155 if (j != i) {
156 ii = qsz;
157 do {
158 c = *i;
159 *i++ = *j;
160 *j++ = c;
161 } while (--ii);
162 }
163 }
164 /*
165 * Semi-standard quicksort partitioning/swapping
166 */
167 for (i = base, j = max - qsz; ; ) {
168 while (i < mid && qcmp(i, mid) <= 0)
169 i += qsz;
170 while (j > mid) {
171 if (qcmp(mid, j) <= 0) {
172 j -= qsz;
173 continue;
174 }
175 tmp = i + qsz; /* value of i after swap */
176 if (i == mid) {
177 /* j <-> mid, new mid is j */
178 mid = jj = j;
179 } else {
180 /* i <-> j */
181 jj = j;
182 j -= qsz;
183 }
184 goto swap;
185 }
186 if (i == mid) {
187 break;
188 } else {
189 /* 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
205 * one first by recursion, then do the larger one by
206 * making sure lo is its size, base and max are update
207 * correctly, and branching back. But only repeat
208 * (recursively or by branching) if the partition is
209 * of at least size THRESH.
210 */
211 i = (j = mid) + qsz;
212 if ((lo = j - base) <= (hi = max - i)) {
213 if (lo >= thresh)
214 qst(base, j);
215 base = i;
216 lo = hi;
217 } else {
218 if (hi >= thresh)
219 qst(i, max);
220 max = j;
221 }
222 } while (lo >= thresh);
223 }
224