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 * 4. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33#if defined(LIBC_SCCS) && !defined(lint)
34static char sccsid[] = "@(#)radixsort.c	8.2 (Berkeley) 4/28/95";
35#endif /* LIBC_SCCS and not lint */
36#include <sys/cdefs.h>
37__FBSDID("$FreeBSD: src/lib/libc/stdlib/radixsort.c,v 1.8 2007/01/09 00:28:10 imp Exp $");
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#include <pthread.h>
57
58typedef struct {
59	const u_char **sa;
60	int sn, si;
61} stack;
62
63static inline void simplesort
64(const u_char **, int, int, const u_char *, u_int) __attribute__((always_inline));
65static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
66static void r_sort_b(const u_char **, const u_char **, int, int,
67    const u_char *, u_int);
68
69static int *r_sort_a_count;
70static int *r_sort_b_count;
71
72static void r_sort_count_allocate(void);
73static pthread_once_t r_sort_count_control = PTHREAD_ONCE_INIT;
74
75#define	THRESHOLD	20		/* Divert to simplesort(). */
76#define	SIZE		512		/* Default stack size. */
77
78#define SETUP {								\
79	if (tab == NULL) {						\
80		tr = tr0;						\
81		for (c = 0; c < endch; c++)				\
82			tr0[c] = c + 1;					\
83		tr0[c] = 0;						\
84		for (c++; c < 256; c++)					\
85			tr0[c] = c;					\
86		endch = 0;						\
87	} else {							\
88		endch = tab[endch];					\
89		tr = tab;						\
90		if (endch != 0 && endch != 255) {			\
91			errno = EINVAL;					\
92			return (-1);					\
93		}							\
94	}								\
95}
96
97int
98radixsort(a, n, tab, endch)
99	const u_char **a, *tab;
100	int n;
101	u_int endch;
102{
103	const u_char *tr;
104	int c;
105	u_char tr0[256];
106
107	SETUP;
108	r_sort_a(a, n, 0, tr, endch);
109	return (0);
110}
111
112int
113sradixsort(a, n, tab, endch)
114	const u_char **a, *tab;
115	int n;
116	u_int endch;
117{
118	const u_char *tr, **ta;
119	int c;
120	u_char tr0[256];
121
122	SETUP;
123	if (n < THRESHOLD)
124		simplesort(a, n, 0, tr, endch);
125	else {
126		if ((ta = malloc(n * sizeof(a))) == NULL)
127			return (-1);
128		r_sort_b(a, ta, n, 0, tr, endch);
129		free(ta);
130	}
131	return (0);
132}
133
134static void r_sort_count_allocate(void)
135{
136	r_sort_a_count = calloc(256, sizeof(int));
137	r_sort_b_count = calloc(256, sizeof(int));
138}
139
140#define empty(s)	(s >= sp)
141#define pop(a, n, i)	a = (--sp)->sa, n = sp->sn, i = sp->si
142#define push(a, n, i)	sp->sa = a, sp->sn = n, (sp++)->si = i
143#define swap(a, b, t)	t = a, a = b, b = t
144
145/* Unstable, in-place sort. */
146static void
147r_sort_a(a, n, i, tr, endch)
148	const u_char **a;
149	int n, i;
150	const u_char *tr;
151	u_int endch;
152{
153	static int *count, nc, bmin;
154	int c;
155	const u_char **ak, *r;
156	stack s[SIZE], *sp, *sp0, *sp1, temp;
157	int *cp, bigc;
158	const u_char **an, *t, **aj, **top[256];
159
160	if (pthread_once(&r_sort_count_control, r_sort_count_allocate)) {
161		return;
162	}
163
164	count = r_sort_a_count;
165
166	/* Set up stack. */
167	sp = s;
168	push(a, n, i);
169	while (!empty(s)) {
170		pop(a, n, i);
171		if (n < THRESHOLD) {
172			simplesort(a, n, i, tr, endch);
173			continue;
174		}
175		an = a + n;
176
177		/* Make character histogram. */
178		if (nc == 0) {
179			bmin = 255;	/* First occupied bin, excluding eos. */
180			for (ak = a; ak < an;) {
181				c = tr[(*ak++)[i]];
182				if (++count[c] == 1 && c != endch) {
183					if (c < bmin)
184						bmin = c;
185					nc++;
186				}
187			}
188			if (sp + nc > s + SIZE) {	/* Get more stack. */
189				r_sort_a(a, n, i, tr, endch);
190				continue;
191			}
192		}
193
194		/*
195		 * Special case: if all strings have the same
196		 * character at position i, move on to the next
197		 * character.
198		 */
199		if (nc == 1 && count[bmin] == n) {
200			push(a, n, i+1);
201			nc = count[bmin] = 0;
202			continue;
203		}
204
205		/*
206		 * Set top[]; push incompletely sorted bins onto stack.
207		 * top[] = pointers to last out-of-place element in bins.
208		 * count[] = counts of elements in bins.
209		 * Before permuting: top[c-1] + count[c] = top[c];
210		 * during deal: top[c] counts down to top[c-1].
211		 */
212		sp0 = sp1 = sp;		/* Stack position of biggest bin. */
213		bigc = 2;		/* Size of biggest bin. */
214		if (endch == 0)		/* Special case: set top[eos]. */
215			top[0] = ak = a + count[0];
216		else {
217			ak = a;
218			top[255] = an;
219		}
220		for (cp = count + bmin; nc > 0; cp++) {
221			while (*cp == 0)	/* Find next non-empty pile. */
222				cp++;
223			if (*cp > 1) {
224				if (*cp > bigc) {
225					bigc = *cp;
226					sp1 = sp;
227				}
228				push(ak, *cp, i+1);
229			}
230			top[cp-count] = ak += *cp;
231			nc--;
232		}
233		swap(*sp0, *sp1, temp);	/* Play it safe -- biggest bin last. */
234
235		/*
236		 * Permute misplacements home.  Already home: everything
237		 * before aj, and in bin[c], items from top[c] on.
238		 * Inner loop:
239		 *	r = next element to put in place;
240		 *	ak = top[r[i]] = location to put the next element.
241		 *	aj = bottom of 1st disordered bin.
242		 * Outer loop:
243		 *	Once the 1st disordered bin is done, ie. aj >= ak,
244		 *	aj<-aj + count[c] connects the bins in a linked list;
245		 *	reset count[c].
246		 */
247		for (aj = a; aj < an;  *aj = r, aj += count[c], count[c] = 0)
248			for (r = *aj;  aj < (ak = --top[c = tr[r[i]]]);)
249				swap(*ak, r, t);
250	}
251}
252
253/* Stable sort, requiring additional memory. */
254static void
255r_sort_b(a, ta, n, i, tr, endch)
256	const u_char **a, **ta;
257	int n, i;
258	const u_char *tr;
259	u_int endch;
260{
261	static int *count, nc, bmin;
262	int c;
263	const u_char **ak, **ai;
264	stack s[512], *sp, *sp0, *sp1, temp;
265	const u_char **top[256];
266	int *cp, bigc;
267
268	if (pthread_once(&r_sort_count_control, r_sort_count_allocate)) {
269		return;
270	}
271
272	count = r_sort_b_count;
273
274	sp = s;
275	push(a, n, i);
276	while (!empty(s)) {
277		pop(a, n, i);
278		if (n < THRESHOLD) {
279			simplesort(a, n, i, tr, endch);
280			continue;
281		}
282
283		if (nc == 0) {
284			bmin = 255;
285			for (ak = a + n; --ak >= a;) {
286				c = tr[(*ak)[i]];
287				if (++count[c] == 1 && c != endch) {
288					if (c < bmin)
289						bmin = c;
290					nc++;
291				}
292			}
293			if (sp + nc > s + SIZE) {
294				r_sort_b(a, ta, n, i, tr, endch);
295				continue;
296			}
297		}
298
299		sp0 = sp1 = sp;
300		bigc = 2;
301		if (endch == 0) {
302			top[0] = ak = a + count[0];
303			count[0] = 0;
304		} else {
305			ak = a;
306			top[255] = a + n;
307			count[255] = 0;
308		}
309		for (cp = count + bmin; nc > 0; cp++) {
310			while (*cp == 0)
311				cp++;
312			if ((c = *cp) > 1) {
313				if (c > bigc) {
314					bigc = c;
315					sp1 = sp;
316				}
317				push(ak, c, i+1);
318			}
319			top[cp-count] = ak += c;
320			*cp = 0;			/* Reset count[]. */
321			nc--;
322		}
323		swap(*sp0, *sp1, temp);
324
325		for (ak = ta + n, ai = a+n; ak > ta;)	/* Copy to temp. */
326			*--ak = *--ai;
327		for (ak = ta+n; --ak >= ta;)		/* Deal to piles. */
328			*--top[tr[(*ak)[i]]] = *ak;
329	}
330}
331
332static inline void
333simplesort(a, n, b, tr, endch)	/* insertion sort */
334	const u_char **a;
335	int n, b;
336	const u_char *tr;
337	u_int endch;
338{
339	u_char ch;
340	const u_char  **ak, **ai, *s, *t;
341
342	for (ak = a+1; --n >= 1; ak++)
343		for (ai = ak; ai > a; ai--) {
344			for (s = ai[0] + b, t = ai[-1] + b;
345			    (ch = tr[*s]) != endch; s++, t++)
346				if (ch != tr[*t])
347					break;
348			if (ch >= tr[*t])
349				break;
350			swap(ai[0], ai[-1], s);
351		}
352}
353