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