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
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
57typedef struct {
58	const u_char **sa;
59	int sn, si;
60} stack;
61
62static inline void simplesort
63(const u_char **, int, int, const u_char *, u_int);
64static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
65static 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
90int
91radixsort(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
102int
103sradixsort(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. */
127static void
128r_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. */
225static void
226r_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 */
295static inline void
296simplesort(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