1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1990, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Peter McIlroy and by Dan Bernstein at New York University,
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35 #if defined(LIBC_SCCS) && !defined(lint)
36 static char sccsid[] = "@(#)radixsort.c 8.2 (Berkeley) 4/28/95";
37 #endif /* LIBC_SCCS and not lint */
38
39 /*
40 * Radixsort routines.
41 *
42 * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack.
43 * Use radixsort(a, n, trace, endchar) for this case.
44 *
45 * For stable sorting (using N extra pointers) use sradixsort(), which calls
46 * r_sort_b().
47 *
48 * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic,
49 * "Engineering Radix Sort".
50 */
51
52 #include <sys/types.h>
53 #include <stdlib.h>
54 #include <stddef.h>
55 #include <errno.h>
56
57 typedef struct {
58 const u_char **sa;
59 int sn, si;
60 } stack;
61
62 static inline void simplesort
63 (const u_char **, int, int, const u_char *, u_int);
64 static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
65 static void r_sort_b(const u_char **, const u_char **, int, int,
66 const u_char *, u_int);
67
68 #define THRESHOLD 20 /* Divert to simplesort(). */
69 #define SIZE 512 /* Default stack size. */
70
71 #define SETUP { \
72 if (tab == NULL) { \
73 tr = tr0; \
74 for (c = 0; c < endch; c++) \
75 tr0[c] = c + 1; \
76 tr0[c] = 0; \
77 for (c++; c < 256; c++) \
78 tr0[c] = c; \
79 endch = 0; \
80 } else { \
81 endch = tab[endch]; \
82 tr = tab; \
83 if (endch != 0 && endch != 255) { \
84 errno = EINVAL; \
85 return (-1); \
86 } \
87 } \
88 }
89
90 int
radixsort(const u_char ** a,int n,const u_char * tab,u_int endch)91 radixsort(const u_char **a, int n, const u_char *tab, u_int endch)
92 {
93 const u_char *tr;
94 int c;
95 u_char tr0[256];
96
97 SETUP;
98 r_sort_a(a, n, 0, tr, endch);
99 return (0);
100 }
101
102 int
sradixsort(const u_char ** a,int n,const u_char * tab,u_int endch)103 sradixsort(const u_char **a, int n, const u_char *tab, u_int endch)
104 {
105 const u_char *tr, **ta;
106 int c;
107 u_char tr0[256];
108
109 SETUP;
110 if (n < THRESHOLD)
111 simplesort(a, n, 0, tr, endch);
112 else {
113 if ((ta = malloc(n * sizeof(a))) == NULL)
114 return (-1);
115 r_sort_b(a, ta, n, 0, tr, endch);
116 free(ta);
117 }
118 return (0);
119 }
120
121 #define empty(s) (s >= sp)
122 #define pop(a, n, i) a = (--sp)->sa, n = sp->sn, i = sp->si
123 #define push(a, n, i) sp->sa = a, sp->sn = n, (sp++)->si = i
124 #define swap(a, b, t) t = a, a = b, b = t
125
126 /* Unstable, in-place sort. */
127 static void
r_sort_a(const u_char ** a,int n,int i,const u_char * tr,u_int endch)128 r_sort_a(const u_char **a, int n, int i, const u_char *tr, u_int endch)
129 {
130 static int count[256], nc, bmin;
131 int c;
132 const u_char **ak, *r;
133 stack s[SIZE], *sp, *sp0, *sp1, temp;
134 int *cp, bigc;
135 const u_char **an, *t, **aj, **top[256];
136
137 /* Set up stack. */
138 sp = s;
139 push(a, n, i);
140 while (!empty(s)) {
141 pop(a, n, i);
142 if (n < THRESHOLD) {
143 simplesort(a, n, i, tr, endch);
144 continue;
145 }
146 an = a + n;
147
148 /* Make character histogram. */
149 if (nc == 0) {
150 bmin = 255; /* First occupied bin, excluding eos. */
151 for (ak = a; ak < an;) {
152 c = tr[(*ak++)[i]];
153 if (++count[c] == 1 && c != endch) {
154 if (c < bmin)
155 bmin = c;
156 nc++;
157 }
158 }
159 if (sp + nc > s + SIZE) { /* Get more stack. */
160 r_sort_a(a, n, i, tr, endch);
161 continue;
162 }
163 }
164
165 /*
166 * Special case: if all strings have the same
167 * character at position i, move on to the next
168 * character.
169 */
170 if (nc == 1 && count[bmin] == n) {
171 push(a, n, i+1);
172 nc = count[bmin] = 0;
173 continue;
174 }
175
176 /*
177 * Set top[]; push incompletely sorted bins onto stack.
178 * top[] = pointers to last out-of-place element in bins.
179 * count[] = counts of elements in bins.
180 * Before permuting: top[c-1] + count[c] = top[c];
181 * during deal: top[c] counts down to top[c-1].
182 */
183 sp0 = sp1 = sp; /* Stack position of biggest bin. */
184 bigc = 2; /* Size of biggest bin. */
185 if (endch == 0) /* Special case: set top[eos]. */
186 top[0] = ak = a + count[0];
187 else {
188 ak = a;
189 top[255] = an;
190 }
191 for (cp = count + bmin; nc > 0; cp++) {
192 while (*cp == 0) /* Find next non-empty pile. */
193 cp++;
194 if (*cp > 1) {
195 if (*cp > bigc) {
196 bigc = *cp;
197 sp1 = sp;
198 }
199 push(ak, *cp, i+1);
200 }
201 top[cp-count] = ak += *cp;
202 nc--;
203 }
204 swap(*sp0, *sp1, temp); /* Play it safe -- biggest bin last. */
205
206 /*
207 * Permute misplacements home. Already home: everything
208 * before aj, and in bin[c], items from top[c] on.
209 * Inner loop:
210 * r = next element to put in place;
211 * ak = top[r[i]] = location to put the next element.
212 * aj = bottom of 1st disordered bin.
213 * Outer loop:
214 * Once the 1st disordered bin is done, ie. aj >= ak,
215 * aj<-aj + count[c] connects the bins in a linked list;
216 * reset count[c].
217 */
218 for (aj = a; aj < an; *aj = r, aj += count[c], count[c] = 0)
219 for (r = *aj; aj < (ak = --top[c = tr[r[i]]]);)
220 swap(*ak, r, t);
221 }
222 }
223
224 /* Stable sort, requiring additional memory. */
225 static void
r_sort_b(const u_char ** a,const u_char ** ta,int n,int i,const u_char * tr,u_int endch)226 r_sort_b(const u_char **a, const u_char **ta, int n, int i, const u_char *tr,
227 u_int endch)
228 {
229 static int count[256], nc, bmin;
230 int c;
231 const u_char **ak, **ai;
232 stack s[512], *sp, *sp0, *sp1, temp;
233 const u_char **top[256];
234 int *cp, bigc;
235
236 sp = s;
237 push(a, n, i);
238 while (!empty(s)) {
239 pop(a, n, i);
240 if (n < THRESHOLD) {
241 simplesort(a, n, i, tr, endch);
242 continue;
243 }
244
245 if (nc == 0) {
246 bmin = 255;
247 for (ak = a + n; --ak >= a;) {
248 c = tr[(*ak)[i]];
249 if (++count[c] == 1 && c != endch) {
250 if (c < bmin)
251 bmin = c;
252 nc++;
253 }
254 }
255 if (sp + nc > s + SIZE) {
256 r_sort_b(a, ta, n, i, tr, endch);
257 continue;
258 }
259 }
260
261 sp0 = sp1 = sp;
262 bigc = 2;
263 if (endch == 0) {
264 top[0] = ak = a + count[0];
265 count[0] = 0;
266 } else {
267 ak = a;
268 top[255] = a + n;
269 count[255] = 0;
270 }
271 for (cp = count + bmin; nc > 0; cp++) {
272 while (*cp == 0)
273 cp++;
274 if ((c = *cp) > 1) {
275 if (c > bigc) {
276 bigc = c;
277 sp1 = sp;
278 }
279 push(ak, c, i+1);
280 }
281 top[cp-count] = ak += c;
282 *cp = 0; /* Reset count[]. */
283 nc--;
284 }
285 swap(*sp0, *sp1, temp);
286
287 for (ak = ta + n, ai = a+n; ak > ta;) /* Copy to temp. */
288 *--ak = *--ai;
289 for (ak = ta+n; --ak >= ta;) /* Deal to piles. */
290 *--top[tr[(*ak)[i]]] = *ak;
291 }
292 }
293
294 /* insertion sort */
295 static inline void
simplesort(const u_char ** a,int n,int b,const u_char * tr,u_int endch)296 simplesort(const u_char **a, int n, int b, const u_char *tr, u_int endch)
297 {
298 u_char ch;
299 const u_char **ak, **ai, *s, *t;
300
301 for (ak = a+1; --n >= 1; ak++)
302 for (ai = ak; ai > a; ai--) {
303 for (s = ai[0] + b, t = ai[-1] + b;
304 (ch = tr[*s]) != endch; s++, t++)
305 if (ch != tr[*t])
306 break;
307 if (ch >= tr[*t])
308 break;
309 swap(ai[0], ai[-1], s);
310 }
311 }
312