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