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)
38static char sccsid[] = "@(#)radixsort.c	8.2 (Berkeley) 4/28/95";
39#endif /* LIBC_SCCS and not lint */
40
41/*
42 * Radixsort routines.
43 *
44 * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack.
45 * Use radixsort(a, n, trace, endchar) for this case.
46 *
47 * For stable sorting (using N extra pointers) use sradixsort(), which calls
48 * r_sort_b().
49 *
50 * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic,
51 * "Engineering Radix Sort".
52 */
53
54#include <sys/types.h>
55#include <stdlib.h>
56#include <errno.h>
57
58#include <errno_private.h>
59
60typedef struct {
61	const u_char **sa;
62	int sn, si;
63} stack;
64
65static inline void simplesort(u_char const **, int, int, u_char const *, u_int);
66static void r_sort_a(u_char const **, int, int, u_char const *, u_int);
67static void r_sort_b(u_char const **, u_char const **, int, int, u_char const *, u_int);
68
69#define	THRESHOLD	20		/* Divert to simplesort(). */
70#define	SIZE		512		/* Default stack size. */
71
72#define SETUP {								\
73	if (tab == NULL) {						\
74		tr = tr0;						\
75		for (c = 0; c < endch; c++)				\
76			tr0[c] = c + 1;					\
77		tr0[c] = 0;						\
78		for (c++; c < 256; c++)					\
79			tr0[c] = c;					\
80		endch = 0;						\
81	} else {							\
82		endch = tab[endch];					\
83		tr = tab;						\
84		if (endch != 0 && endch != 255) {			\
85			/* __set_errno(EINVAL); */				\
86			return (-1);					\
87		}							\
88	}								\
89}
90
91int
92radixsort(u_char const **a, int n, u_char const *tab, u_int endch)
93{
94	u_char const *tr;
95	u_int c;
96	u_char tr0[256];
97
98	SETUP;
99	r_sort_a(a, n, 0, tr, endch);
100	return (0);
101}
102
103int
104sradixsort(u_char const **a, int n, u_char const *tab, u_int endch)
105{
106	u_char const *tr;
107	u_char const **ta;
108	u_int c;
109	u_char tr0[256];
110
111	SETUP;
112	if (n < THRESHOLD)
113		simplesort(a, n, 0, tr, endch);
114	else {
115		if ((ta = malloc(n * sizeof(a))) == NULL)
116			return (-1);
117		r_sort_b(a, ta, n, 0, tr, endch);
118		free(ta);
119	}
120	return (0);
121}
122
123#define empty(s)	(s >= sp)
124#define pop(a, n, i)	a = (--sp)->sa, n = sp->sn, i = sp->si
125#define push(a, n, i)	sp->sa = a, sp->sn = n, (sp++)->si = i
126#define swap(a, b, t)	t = a, a = b, b = t
127
128/* Unstable, in-place sort. */
129static void
130r_sort_a(u_char const **a, int n, int i, u_char const *tr, u_int endch)
131{
132	static u_int count[256];
133	static int  nc;
134	static u_int  bmin;
135	u_int c;
136	u_char const **ak;
137	u_char const *r;
138	stack s[SIZE];
139	stack *sp;
140	stack *sp0;
141	stack *sp1;
142	stack temp;
143	u_int *cp;
144	u_int bigc;
145	u_char const **an;
146	u_char const *t;
147	u_char const **aj;
148	u_char const **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. */
227static
228void
229r_sort_b(u_char const **a, u_char const **ta, int n, int i, u_char const *tr, u_int endch)
230{
231	static int count[256];
232	static u_int  nc;
233	static u_int  bmin;
234	u_int c;
235	u_char const **ak, **ai;
236	stack s[512], *sp, *sp0, *sp1, temp;
237	u_char const **top[256];
238	int *cp;
239	u_int 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
299static inline
300void
301simplesort(u_char const **a, int n, int b, u_char const *tr, u_int endch)	/* insertion sort */
302{
303	u_char ch;
304	u_char const **ak;
305	u_char const **ai;
306	u_char const  *s;
307	u_char const  *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}
321