1 /*-
2 * Copyright (c) 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Peter McIlroy and by Dan Bernstein at New York University,
7 *
8 * %sccs.include.redist.c%
9 */
10
11 #if defined(LIBC_SCCS) && !defined(lint)
12 static char sccsid[] = "@(#)radixsort.c 8.2 (Berkeley) 04/28/95";
13 #endif /* LIBC_SCCS and not lint */
14
15 /*
16 * Radixsort routines.
17 *
18 * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack.
19 * Use radixsort(a, n, trace, endchar) for this case.
20 *
21 * For stable sorting (using N extra pointers) use sradixsort(), which calls
22 * r_sort_b().
23 *
24 * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic,
25 * "Engineering Radix Sort".
26 */
27
28 #include <sys/types.h>
29 #include <stdlib.h>
30 #include <stddef.h>
31 #include <errno.h>
32
33 typedef struct {
34 const u_char **sa;
35 int sn, si;
36 } stack;
37
38 static inline void simplesort
39 __P((const u_char **, int, int, const u_char *, u_int));
40 static void r_sort_a __P((const u_char **, int, int, const u_char *, u_int));
41 static void r_sort_b __P((const u_char **,
42 const u_char **, int, int, const u_char *, u_int));
43
44 #define THRESHOLD 20 /* Divert to simplesort(). */
45 #define SIZE 512 /* Default stack size. */
46
47 #define SETUP { \
48 if (tab == NULL) { \
49 tr = tr0; \
50 for (c = 0; c < endch; c++) \
51 tr0[c] = c + 1; \
52 tr0[c] = 0; \
53 for (c++; c < 256; c++) \
54 tr0[c] = c; \
55 endch = 0; \
56 } else { \
57 endch = tab[endch]; \
58 tr = tab; \
59 if (endch != 0 && endch != 255) { \
60 errno = EINVAL; \
61 return (-1); \
62 } \
63 } \
64 }
65
66 int
radixsort(a,n,tab,endch)67 radixsort(a, n, tab, endch)
68 const u_char **a, *tab;
69 int n;
70 u_int endch;
71 {
72 const u_char *tr;
73 int c;
74 u_char tr0[256];
75
76 SETUP;
77 r_sort_a(a, n, 0, tr, endch);
78 return (0);
79 }
80
81 int
sradixsort(a,n,tab,endch)82 sradixsort(a, n, tab, endch)
83 const u_char **a, *tab;
84 int n;
85 u_int endch;
86 {
87 const u_char *tr, **ta;
88 int c;
89 u_char tr0[256];
90
91 SETUP;
92 if (n < THRESHOLD)
93 simplesort(a, n, 0, tr, endch);
94 else {
95 if ((ta = malloc(n * sizeof(a))) == NULL)
96 return (-1);
97 r_sort_b(a, ta, n, 0, tr, endch);
98 free(ta);
99 }
100 return (0);
101 }
102
103 #define empty(s) (s >= sp)
104 #define pop(a, n, i) a = (--sp)->sa, n = sp->sn, i = sp->si
105 #define push(a, n, i) sp->sa = a, sp->sn = n, (sp++)->si = i
106 #define swap(a, b, t) t = a, a = b, b = t
107
108 /* Unstable, in-place sort. */
109 static void
r_sort_a(a,n,i,tr,endch)110 r_sort_a(a, n, i, tr, endch)
111 const u_char **a;
112 int n, i;
113 const u_char *tr;
114 u_int endch;
115 {
116 static int count[256], nc, bmin;
117 register int c;
118 register const u_char **ak, *r;
119 stack s[SIZE], *sp, *sp0, *sp1, temp;
120 int *cp, bigc;
121 const u_char **an, *t, **aj, **top[256];
122
123 /* Set up stack. */
124 sp = s;
125 push(a, n, i);
126 while (!empty(s)) {
127 pop(a, n, i);
128 if (n < THRESHOLD) {
129 simplesort(a, n, i, tr, endch);
130 continue;
131 }
132 an = a + n;
133
134 /* Make character histogram. */
135 if (nc == 0) {
136 bmin = 255; /* First occupied bin, excluding eos. */
137 for (ak = a; ak < an;) {
138 c = tr[(*ak++)[i]];
139 if (++count[c] == 1 && c != endch) {
140 if (c < bmin)
141 bmin = c;
142 nc++;
143 }
144 }
145 if (sp + nc > s + SIZE) { /* Get more stack. */
146 r_sort_a(a, n, i, tr, endch);
147 continue;
148 }
149 }
150
151 /*
152 * Set top[]; push incompletely sorted bins onto stack.
153 * top[] = pointers to last out-of-place element in bins.
154 * count[] = counts of elements in bins.
155 * Before permuting: top[c-1] + count[c] = top[c];
156 * during deal: top[c] counts down to top[c-1].
157 */
158 sp0 = sp1 = sp; /* Stack position of biggest bin. */
159 bigc = 2; /* Size of biggest bin. */
160 if (endch == 0) /* Special case: set top[eos]. */
161 top[0] = ak = a + count[0];
162 else {
163 ak = a;
164 top[255] = an;
165 }
166 for (cp = count + bmin; nc > 0; cp++) {
167 while (*cp == 0) /* Find next non-empty pile. */
168 cp++;
169 if (*cp > 1) {
170 if (*cp > bigc) {
171 bigc = *cp;
172 sp1 = sp;
173 }
174 push(ak, *cp, i+1);
175 }
176 top[cp-count] = ak += *cp;
177 nc--;
178 }
179 swap(*sp0, *sp1, temp); /* Play it safe -- biggest bin last. */
180
181 /*
182 * Permute misplacements home. Already home: everything
183 * before aj, and in bin[c], items from top[c] on.
184 * Inner loop:
185 * r = next element to put in place;
186 * ak = top[r[i]] = location to put the next element.
187 * aj = bottom of 1st disordered bin.
188 * Outer loop:
189 * Once the 1st disordered bin is done, ie. aj >= ak,
190 * aj<-aj + count[c] connects the bins in a linked list;
191 * reset count[c].
192 */
193 for (aj = a; aj < an; *aj = r, aj += count[c], count[c] = 0)
194 for (r = *aj; aj < (ak = --top[c = tr[r[i]]]);)
195 swap(*ak, r, t);
196 }
197 }
198
199 /* Stable sort, requiring additional memory. */
200 static void
r_sort_b(a,ta,n,i,tr,endch)201 r_sort_b(a, ta, n, i, tr, endch)
202 const u_char **a, **ta;
203 int n, i;
204 const u_char *tr;
205 u_int endch;
206 {
207 static int count[256], nc, bmin;
208 register int c;
209 register const u_char **ak, **ai;
210 stack s[512], *sp, *sp0, *sp1, temp;
211 const u_char **top[256];
212 int *cp, bigc;
213
214 sp = s;
215 push(a, n, i);
216 while (!empty(s)) {
217 pop(a, n, i);
218 if (n < THRESHOLD) {
219 simplesort(a, n, i, tr, endch);
220 continue;
221 }
222
223 if (nc == 0) {
224 bmin = 255;
225 for (ak = a + n; --ak >= a;) {
226 c = tr[(*ak)[i]];
227 if (++count[c] == 1 && c != endch) {
228 if (c < bmin)
229 bmin = c;
230 nc++;
231 }
232 }
233 if (sp + nc > s + SIZE) {
234 r_sort_b(a, ta, n, i, tr, endch);
235 continue;
236 }
237 }
238
239 sp0 = sp1 = sp;
240 bigc = 2;
241 if (endch == 0) {
242 top[0] = ak = a + count[0];
243 count[0] = 0;
244 } else {
245 ak = a;
246 top[255] = a + n;
247 count[255] = 0;
248 }
249 for (cp = count + bmin; nc > 0; cp++) {
250 while (*cp == 0)
251 cp++;
252 if ((c = *cp) > 1) {
253 if (c > bigc) {
254 bigc = c;
255 sp1 = sp;
256 }
257 push(ak, c, i+1);
258 }
259 top[cp-count] = ak += c;
260 *cp = 0; /* Reset count[]. */
261 nc--;
262 }
263 swap(*sp0, *sp1, temp);
264
265 for (ak = ta + n, ai = a+n; ak > ta;) /* Copy to temp. */
266 *--ak = *--ai;
267 for (ak = ta+n; --ak >= ta;) /* Deal to piles. */
268 *--top[tr[(*ak)[i]]] = *ak;
269 }
270 }
271
272 static inline void
simplesort(a,n,b,tr,endch)273 simplesort(a, n, b, tr, endch) /* insertion sort */
274 register const u_char **a;
275 int n, b;
276 register const u_char *tr;
277 u_int endch;
278 {
279 register u_char ch;
280 const u_char **ak, **ai, *s, *t;
281
282 for (ak = a+1; --n >= 1; ak++)
283 for (ai = ak; ai > a; ai--) {
284 for (s = ai[0] + b, t = ai[-1] + b;
285 (ch = tr[*s]) != endch; s++, t++)
286 if (ch != tr[*t])
287 break;
288 if (ch >= tr[*t])
289 break;
290 swap(ai[0], ai[-1], s);
291 }
292 }
293