Commit | Line | Data |
---|---|---|
34849bd9 KB |
1 | /*- |
2 | * Copyright (c) 1990 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
07d0210e | 5 | * This code is derived from software contributed to Berkeley by |
6f4f6081 | 6 | * Peter McIlroy and by Dan Bernstein at New York University, |
07d0210e | 7 | * |
34849bd9 KB |
8 | * %sccs.include.redist.c% |
9 | */ | |
10 | ||
11 | #if defined(LIBC_SCCS) && !defined(lint) | |
3f3d04c1 | 12 | static char sccsid[] = "@(#)radixsort.c 5.15 (Berkeley) %G%"; |
34849bd9 KB |
13 | #endif /* LIBC_SCCS and not lint */ |
14 | ||
6f4f6081 KB |
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 | ||
34849bd9 | 28 | #include <sys/types.h> |
34849bd9 KB |
29 | #include <stdlib.h> |
30 | #include <stddef.h> | |
a0451f54 KB |
31 | #include <errno.h> |
32 | ||
6f4f6081 KB |
33 | typedef struct { |
34 | const u_char **sa; | |
35 | int sn, si; | |
36 | } stack; | |
34849bd9 | 37 | |
3f3d04c1 KB |
38 | static inline void simplesort |
39 | __P((const u_char **, int, int, const u_char *, u_int)); | |
6f4f6081 KB |
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)); | |
a0451f54 | 43 | |
6f4f6081 KB |
44 | #define THRESHOLD 20 /* Divert to simplesort(). */ |
45 | #define SIZE 512 /* Default stack size. */ | |
34849bd9 | 46 | |
6f4f6081 KB |
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 | } | |
e061e641 | 65 | |
6f4f6081 KB |
66 | int |
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]; | |
34849bd9 | 75 | |
6f4f6081 KB |
76 | SETUP; |
77 | r_sort_a(a, n, 0, tr, endch); | |
78 | return (0); | |
34849bd9 | 79 | } |
6f4f6081 | 80 | |
f0a345ab | 81 | int |
6f4f6081 KB |
82 | sradixsort(a, n, tab, endch) |
83 | const u_char **a, *tab; | |
84 | int n; | |
85 | u_int endch; | |
34849bd9 | 86 | { |
6f4f6081 KB |
87 | const u_char *tr, **ta; |
88 | int c; | |
89 | u_char tr0[256]; | |
34849bd9 | 90 | |
6f4f6081 KB |
91 | SETUP; |
92 | if (n < THRESHOLD) | |
93 | simplesort(a, n, 0, tr, endch); | |
94 | else { | |
95 | if ((ta = malloc(n * sizeof(a))) == NULL) | |
a0451f54 | 96 | return (-1); |
6f4f6081 KB |
97 | r_sort_b(a, ta, n, 0, tr, endch); |
98 | free(ta); | |
a0451f54 | 99 | } |
6f4f6081 KB |
100 | return (0); |
101 | } | |
dfad239c | 102 | |
6f4f6081 KB |
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 | |
34849bd9 | 107 | |
6f4f6081 KB |
108 | /* Unstable, in-place sort. */ |
109 | void | |
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]; | |
34849bd9 | 122 | |
6f4f6081 | 123 | /* Set up stack. */ |
fe769590 | 124 | sp = s; |
6f4f6081 KB |
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; | |
a0451f54 | 131 | } |
6f4f6081 | 132 | an = a + n; |
34849bd9 | 133 | |
6f4f6081 KB |
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; | |
dfad239c | 148 | } |
dfad239c | 149 | } |
34849bd9 KB |
150 | |
151 | /* | |
6f4f6081 KB |
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]. | |
34849bd9 | 157 | */ |
6f4f6081 KB |
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; | |
34849bd9 | 165 | } |
6f4f6081 | 166 | for (cp = count + bmin; nc > 0; cp++) { |
fe769590 | 167 | while (*cp == 0) /* Find next non-empty pile. */ |
6f4f6081 KB |
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. */ | |
34849bd9 | 180 | |
34849bd9 | 181 | /* |
6f4f6081 KB |
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]. | |
34849bd9 | 192 | */ |
6f4f6081 KB |
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 | void | |
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; | |
6f4f6081 KB |
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; | |
dfad239c | 221 | } |
6f4f6081 KB |
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); | |
34849bd9 | 235 | continue; |
6f4f6081 KB |
236 | } |
237 | } | |
238 | ||
fe769590 KB |
239 | sp0 = sp1 = sp; |
240 | bigc = 2; | |
241 | if (endch == 0) { | |
6f4f6081 KB |
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 | } | |
fe769590 | 249 | for (cp = count + bmin; nc > 0; cp++) { |
6f4f6081 KB |
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; | |
fe769590 KB |
260 | *cp = 0; /* Reset count[]. */ |
261 | nc--; | |
34849bd9 | 262 | } |
fe769590 | 263 | swap(*sp0, *sp1, temp); |
6f4f6081 | 264 | |
fe769590 | 265 | for (ak = ta + n, ai = a+n; ak > ta;) /* Copy to temp. */ |
6f4f6081 | 266 | *--ak = *--ai; |
fe769590 | 267 | for (ak = ta+n; --ak >= ta;) /* Deal to piles. */ |
6f4f6081 | 268 | *--top[tr[(*ak)[i]]] = *ak; |
34849bd9 | 269 | } |
34849bd9 | 270 | } |
6f4f6081 | 271 | |
3f3d04c1 | 272 | static inline void |
6f4f6081 KB |
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; | |
33f8130f | 278 | { |
a0451f54 | 279 | register u_char ch; |
6f4f6081 | 280 | const u_char **ak, **ai, *s, *t; |
33f8130f | 281 | |
6f4f6081 KB |
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]) | |
33f8130f | 287 | break; |
6f4f6081 KB |
288 | if (ch >= tr[*t]) |
289 | break; | |
290 | swap(ai[0], ai[-1], s); | |
291 | } | |
33f8130f | 292 | } |