Commit | Line | Data |
---|---|---|
b8f253e8 KM |
1 | /* |
2 | * Copyright (c) 1980 Regents of the University of California. | |
202a4bd9 KB |
3 | * All rights reserved. |
4 | * | |
5 | * Redistribution and use in source and binary forms are permitted | |
9e31603f KB |
6 | * provided that the above copyright notice and this paragraph are |
7 | * duplicated in all such forms and that any documentation, | |
8 | * advertising materials, and other materials related to such | |
9 | * distribution and use acknowledge that the software was developed | |
10 | * by the University of California, Berkeley. The name of the | |
11 | * University may not be used to endorse or promote products derived | |
12 | * from this software without specific prior written permission. | |
13 | * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR | |
14 | * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED | |
15 | * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. | |
b8f253e8 KM |
16 | */ |
17 | ||
2ce81398 | 18 | #if defined(LIBC_SCCS) && !defined(lint) |
9e31603f | 19 | static char sccsid[] = "@(#)qsort.c 5.4 (Berkeley) %G%"; |
202a4bd9 | 20 | #endif /* LIBC_SCCS and not lint */ |
b4751583 | 21 | |
6c625db4 KM |
22 | /* |
23 | * qsort.c: | |
24 | * Our own version of the system qsort routine which is faster by an average | |
25 | * of 25%, with lows and highs of 10% and 50%. | |
26 | * The THRESHold below is the insertion sort threshold, and has been adjusted | |
27 | * for records of size 48 bytes. | |
28 | * The MTHREShold is where we stop finding a better median. | |
29 | */ | |
b4751583 | 30 | |
6c625db4 KM |
31 | #define THRESH 4 /* threshold for insertion */ |
32 | #define MTHRESH 6 /* threshold for median */ | |
b4751583 | 33 | |
6c625db4 KM |
34 | static int (*qcmp)(); /* the comparison routine */ |
35 | static int qsz; /* size of each record */ | |
36 | static int thresh; /* THRESHold in chars */ | |
37 | static int mthresh; /* MTHRESHold in chars */ | |
b4751583 | 38 | |
6c625db4 KM |
39 | /* |
40 | * qsort: | |
41 | * First, set up some global parameters for qst to share. Then, quicksort | |
42 | * with qst(), and then a cleanup insertion sort ourselves. Sound simple? | |
43 | * It's not... | |
44 | */ | |
b4751583 | 45 | |
6c625db4 KM |
46 | qsort(base, n, size, compar) |
47 | char *base; | |
48 | int n; | |
49 | int size; | |
50 | int (*compar)(); | |
51 | { | |
52 | register char c, *i, *j, *lo, *hi; | |
53 | char *min, *max; | |
b4751583 | 54 | |
6c625db4 | 55 | if (n <= 1) |
b4751583 | 56 | return; |
6c625db4 KM |
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 | |
70 | * the first position as a sentinel. This is done just by searching | |
71 | * the first THRESH elements (or the first n if n < THRESH), finding | |
72 | * the min, 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 | if (j != base) { | |
78 | /* swap j into place */ | |
79 | for (i = base, hi = base + qsz; i < hi; ) { | |
80 | c = *j; | |
81 | *j++ = *i; | |
82 | *i++ = c; | |
b4751583 | 83 | } |
6c625db4 KM |
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. | |
89 | * Then, do the standard insertion sort shift on a character at a time | |
90 | * basis for each element in the frob. | |
91 | */ | |
92 | for (min = base; (hi = min += qsz) < max; ) { | |
93 | while (qcmp(hi -= qsz, min) > 0) | |
94 | /* void */; | |
95 | if ((hi += qsz) != min) { | |
96 | for (lo = min + qsz; --lo >= min; ) { | |
97 | c = *lo; | |
98 | for (i = j = lo; (j -= qsz) >= hi; i = j) | |
99 | *i = *j; | |
100 | *i = c; | |
b4751583 | 101 | } |
b4751583 | 102 | } |
b4751583 BJ |
103 | } |
104 | } | |
105 | ||
6c625db4 KM |
106 | /* |
107 | * qst: | |
108 | * Do a quicksort | |
109 | * First, find the median element, and put that one in the first place as the | |
110 | * discriminator. (This "median" is just the median of the first, last and | |
111 | * middle elements). (Using this median instead of the first element is a big | |
112 | * win). Then, the usual partitioning/swapping, followed by moving the | |
113 | * discriminator into the right place. Then, figure out the sizes of the two | |
114 | * partions, do the smaller one recursively and the larger one via a repeat of | |
115 | * this code. Stopping when there are less than THRESH elements in a partition | |
116 | * and cleaning up with an insertion sort (in our caller) is a huge win. | |
117 | * All data swaps are done in-line, which is space-losing but time-saving. | |
118 | * (And there are only three places where this is done). | |
119 | */ | |
b4751583 | 120 | |
6c625db4 KM |
121 | static |
122 | qst(base, max) | |
123 | char *base, *max; | |
b4751583 | 124 | { |
6c625db4 KM |
125 | register char c, *i, *j, *jj; |
126 | register int ii; | |
127 | char *mid, *tmp; | |
128 | int lo, hi; | |
b4751583 | 129 | |
6c625db4 KM |
130 | /* |
131 | * At the top here, lo is the number of characters of elements in the | |
132 | * current partition. (Which should be max - base). | |
133 | * Find the median of the first, last, and middle element and make | |
134 | * that the middle element. Set j to largest of first and middle. | |
135 | * If max is larger than that guy, then it's that guy, else compare | |
136 | * max with loser of first and take larger. Things are set up to | |
137 | * prefer the middle, then the first in case of ties. | |
138 | */ | |
139 | lo = max - base; /* number of elements as chars */ | |
140 | do { | |
141 | mid = i = base + qsz * ((lo / qsz) >> 1); | |
142 | if (lo >= mthresh) { | |
143 | j = (qcmp((jj = base), i) > 0 ? jj : i); | |
144 | if (qcmp(j, (tmp = max - qsz)) > 0) { | |
145 | /* switch to first loser */ | |
146 | j = (j == jj ? i : jj); | |
147 | if (qcmp(j, tmp) < 0) | |
148 | j = tmp; | |
149 | } | |
150 | if (j != i) { | |
151 | ii = qsz; | |
152 | do { | |
153 | c = *i; | |
154 | *i++ = *j; | |
155 | *j++ = c; | |
156 | } while (--ii); | |
157 | } | |
158 | } | |
159 | /* | |
160 | * Semi-standard quicksort partitioning/swapping | |
161 | */ | |
162 | for (i = base, j = max - qsz; ; ) { | |
163 | while (i < mid && qcmp(i, mid) <= 0) | |
164 | i += qsz; | |
165 | while (j > mid) { | |
166 | if (qcmp(mid, j) <= 0) { | |
167 | j -= qsz; | |
168 | continue; | |
169 | } | |
170 | tmp = i + qsz; /* value of i after swap */ | |
171 | if (i == mid) { | |
172 | /* j <-> mid, new mid is j */ | |
173 | mid = jj = j; | |
174 | } else { | |
175 | /* i <-> j */ | |
176 | jj = j; | |
177 | j -= qsz; | |
178 | } | |
179 | goto swap; | |
180 | } | |
181 | if (i == mid) { | |
182 | break; | |
183 | } else { | |
184 | /* i <-> mid, new mid is i */ | |
185 | jj = mid; | |
186 | tmp = mid = i; /* value of i after swap */ | |
187 | j -= qsz; | |
188 | } | |
189 | swap: | |
190 | ii = qsz; | |
191 | do { | |
192 | c = *i; | |
193 | *i++ = *jj; | |
194 | *jj++ = c; | |
195 | } while (--ii); | |
196 | i = tmp; | |
197 | } | |
198 | /* | |
199 | * Look at sizes of the two partitions, do the smaller | |
200 | * one first by recursion, then do the larger one by | |
201 | * making sure lo is its size, base and max are update | |
202 | * correctly, and branching back. But only repeat | |
203 | * (recursively or by branching) if the partition is | |
204 | * of at least size THRESH. | |
205 | */ | |
206 | i = (j = mid) + qsz; | |
207 | if ((lo = j - base) <= (hi = max - i)) { | |
208 | if (lo >= thresh) | |
209 | qst(base, j); | |
210 | base = i; | |
211 | lo = hi; | |
212 | } else { | |
213 | if (hi >= thresh) | |
214 | qst(i, max); | |
215 | max = j; | |
216 | } | |
217 | } while (lo >= thresh); | |
b4751583 | 218 | } |