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)
36static char sccsid[] = "@(#)radixsort.c	8.2 (Berkeley) 4/28/95";
37#endif /* LIBC_SCCS and not lint */
38#include <sys/cdefs.h>
39__FBSDID("$FreeBSD$");
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 <stddef.h>
57#include <errno.h>
58
59typedef struct {
60	const u_char **sa;
61	int sn, si;
62} stack;
63
64static inline void simplesort
65(const u_char **, int, int, const u_char *, u_int);
66static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
67static void r_sort_b(const u_char **, const u_char **, int, int,
68    const u_char *, u_int);
69
70#define	THRESHOLD	20		/* Divert to simplesort(). */
71#define	SIZE		512		/* Default stack size. */
72
73#define SETUP {								\
74	if (tab == NULL) {						\
75		tr = tr0;						\
76		for (c = 0; c < endch; c++)				\
77			tr0[c] = c + 1;					\
78		tr0[c] = 0;						\
79		for (c++; c < 256; c++)					\
80			tr0[c] = c;					\
81		endch = 0;						\
82	} else {							\
83		endch = tab[endch];					\
84		tr = tab;						\
85		if (endch != 0 && endch != 255) {			\
86			errno = EINVAL;					\
87			return (-1);					\
88		}							\
89	}								\
90}
91
92int
93radixsort(const u_char **a, int n, const u_char *tab, u_int endch)
94{
95	const u_char *tr;
96	int c;
97	u_char tr0[256];
98
99	SETUP;
100	r_sort_a(a, n, 0, tr, endch);
101	return (0);
102}
103
104int
105sradixsort(const u_char **a, int n, const u_char *tab, u_int endch)
106{
107	const u_char *tr, **ta;
108	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(const u_char **a, int n, int i, const u_char *tr, u_int endch)
131{
132	static int count[256], nc, bmin;
133	int c;
134	const u_char **ak, *r;
135	stack s[SIZE], *sp, *sp0, *sp1, temp;
136	int *cp, bigc;
137	const u_char **an, *t, **aj, **top[256];
138
139	/* Set up stack. */
140	sp = s;
141	push(a, n, i);
142	while (!empty(s)) {
143		pop(a, n, i);
144		if (n < THRESHOLD) {
145			simplesort(a, n, i, tr, endch);
146			continue;
147		}
148		an = a + n;
149
150		/* Make character histogram. */
151		if (nc == 0) {
152			bmin = 255;	/* First occupied bin, excluding eos. */
153			for (ak = a; ak < an;) {
154				c = tr[(*ak++)[i]];
155				if (++count[c] == 1 && c != endch) {
156					if (c < bmin)
157						bmin = c;
158					nc++;
159				}
160			}
161			if (sp + nc > s + SIZE) {	/* Get more stack. */
162				r_sort_a(a, n, i, tr, endch);
163				continue;
164			}
165		}
166
167		/*
168		 * Special case: if all strings have the same
169		 * character at position i, move on to the next
170		 * character.
171		 */
172		if (nc == 1 && count[bmin] == n) {
173			push(a, n, i+1);
174			nc = count[bmin] = 0;
175			continue;
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 void
228r_sort_b(const u_char **a, const u_char **ta, int n, int i, const u_char *tr,
229    u_int endch)
230{
231	static int count[256], nc, bmin;
232	int c;
233	const u_char **ak, **ai;
234	stack s[512], *sp, *sp0, *sp1, temp;
235	const u_char **top[256];
236	int *cp, bigc;
237
238	sp = s;
239	push(a, n, i);
240	while (!empty(s)) {
241		pop(a, n, i);
242		if (n < THRESHOLD) {
243			simplesort(a, n, i, tr, endch);
244			continue;
245		}
246
247		if (nc == 0) {
248			bmin = 255;
249			for (ak = a + n; --ak >= a;) {
250				c = tr[(*ak)[i]];
251				if (++count[c] == 1 && c != endch) {
252					if (c < bmin)
253						bmin = c;
254					nc++;
255				}
256			}
257			if (sp + nc > s + SIZE) {
258				r_sort_b(a, ta, n, i, tr, endch);
259				continue;
260			}
261		}
262
263		sp0 = sp1 = sp;
264		bigc = 2;
265		if (endch == 0) {
266			top[0] = ak = a + count[0];
267			count[0] = 0;
268		} else {
269			ak = a;
270			top[255] = a + n;
271			count[255] = 0;
272		}
273		for (cp = count + bmin; nc > 0; cp++) {
274			while (*cp == 0)
275				cp++;
276			if ((c = *cp) > 1) {
277				if (c > bigc) {
278					bigc = c;
279					sp1 = sp;
280				}
281				push(ak, c, i+1);
282			}
283			top[cp-count] = ak += c;
284			*cp = 0;			/* Reset count[]. */
285			nc--;
286		}
287		swap(*sp0, *sp1, temp);
288
289		for (ak = ta + n, ai = a+n; ak > ta;)	/* Copy to temp. */
290			*--ak = *--ai;
291		for (ak = ta+n; --ak >= ta;)		/* Deal to piles. */
292			*--top[tr[(*ak)[i]]] = *ak;
293	}
294}
295
296/* insertion sort */
297static inline void
298simplesort(const u_char **a, int n, int b, const u_char *tr, u_int endch)
299{
300	u_char ch;
301	const u_char  **ak, **ai, *s, *t;
302
303	for (ak = a+1; --n >= 1; ak++)
304		for (ai = ak; ai > a; ai--) {
305			for (s = ai[0] + b, t = ai[-1] + b;
306			    (ch = tr[*s]) != endch; s++, t++)
307				if (ch != tr[*t])
308					break;
309			if (ch >= tr[*t])
310				break;
311			swap(ai[0], ai[-1], s);
312		}
313}
314