[apple/libc.git] / stdlib / FreeBSD / radixsort.c

/*-
 * Copyright (c) 1990, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Peter McIlroy and by Dan Bernstein at New York University,
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)radixsort.c	8.2 (Berkeley) 4/28/95";
#endif /* LIBC_SCCS and not lint */
#include <sys/cdefs.h>
__FBSDID("$FreeBSD: src/lib/libc/stdlib/radixsort.c,v 1.8 2007/01/09 00:28:10 imp Exp $");

/*
 * Radixsort routines.
 *
 * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack.
 * Use radixsort(a, n, trace, endchar) for this case.
 *
 * For stable sorting (using N extra pointers) use sradixsort(), which calls
 * r_sort_b().
 *
 * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic,
 * "Engineering Radix Sort".
 */

#include <sys/types.h>
#include <stdlib.h>
#include <stddef.h>
#include <errno.h>

typedef struct {
	const u_char **sa;
	int sn, si;
} stack;

static inline void simplesort
(const u_char **, int, int, const u_char *, u_int);
static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
static void r_sort_b(const u_char **, const u_char **, int, int,
    const u_char *, u_int);

#define	THRESHOLD	20		/* Divert to simplesort(). */
#define	SIZE		512		/* Default stack size. */

#define SETUP {								\
	if (tab == NULL) {						\
		tr = tr0;						\
		for (c = 0; c < endch; c++)				\
			tr0[c] = c + 1;					\
		tr0[c] = 0;						\
		for (c++; c < 256; c++)					\
			tr0[c] = c;					\
		endch = 0;						\
	} else {							\
		endch = tab[endch];					\
		tr = tab;						\
		if (endch != 0 && endch != 255) {			\
			errno = EINVAL;					\
			return (-1);					\
		}							\
	}								\
}

int
radixsort(a, n, tab, endch)
	const u_char **a, *tab;
	int n;
	u_int endch;
{
	const u_char *tr;
	int c;
	u_char tr0[256];

	SETUP;
	r_sort_a(a, n, 0, tr, endch);
	return (0);
}

int
sradixsort(a, n, tab, endch)
	const u_char **a, *tab;
	int n;
	u_int endch;
{
	const u_char *tr, **ta;
	int c;
	u_char tr0[256];

	SETUP;
	if (n < THRESHOLD)
		simplesort(a, n, 0, tr, endch);
	else {
		if ((ta = malloc(n * sizeof(a))) == NULL)
			return (-1);
		r_sort_b(a, ta, n, 0, tr, endch);
		free(ta);
	}
	return (0);
}

#define empty(s)	(s >= sp)
#define pop(a, n, i)	a = (--sp)->sa, n = sp->sn, i = sp->si
#define push(a, n, i)	sp->sa = a, sp->sn = n, (sp++)->si = i
#define swap(a, b, t)	t = a, a = b, b = t

/* Unstable, in-place sort. */
static void
r_sort_a(a, n, i, tr, endch)
	const u_char **a;
	int n, i;
	const u_char *tr;
	u_int endch;
{
	static int count[256], nc, bmin;
	int c;
	const u_char **ak, *r;
	stack s[SIZE], *sp, *sp0, *sp1, temp;
	int *cp, bigc;
	const u_char **an, *t, **aj, **top[256];

	/* Set up stack. */
	sp = s;
	push(a, n, i);
	while (!empty(s)) {
		pop(a, n, i);
		if (n < THRESHOLD) {
			simplesort(a, n, i, tr, endch);
			continue;
		}
		an = a + n;

		/* Make character histogram. */
		if (nc == 0) {
			bmin = 255;	/* First occupied bin, excluding eos. */
			for (ak = a; ak < an;) {
				c = tr[(*ak++)[i]];
				if (++count[c] == 1 && c != endch) {
					if (c < bmin)
						bmin = c;
					nc++;
				}
			}
			if (sp + nc > s + SIZE) {	/* Get more stack. */
				r_sort_a(a, n, i, tr, endch);
				continue;
			}
		}

		/*
		 * Special case: if all strings have the same
		 * character at position i, move on to the next
		 * character.
		 */
		if (nc == 1 && count[bmin] == n) {
			push(a, n, i+1);
			nc = count[bmin] = 0;
			continue;
		}

		/*
		 * Set top[]; push incompletely sorted bins onto stack.
		 * top[] = pointers to last out-of-place element in bins.
		 * count[] = counts of elements in bins.
		 * Before permuting: top[c-1] + count[c] = top[c];
		 * during deal: top[c] counts down to top[c-1].
		 */
		sp0 = sp1 = sp;		/* Stack position of biggest bin. */
		bigc = 2;		/* Size of biggest bin. */
		if (endch == 0)		/* Special case: set top[eos]. */
			top[0] = ak = a + count[0];
		else {
			ak = a;
			top[255] = an;
		}
		for (cp = count + bmin; nc > 0; cp++) {
			while (*cp == 0)	/* Find next non-empty pile. */
				cp++;
			if (*cp > 1) {
				if (*cp > bigc) {
					bigc = *cp;
					sp1 = sp;
				}
				push(ak, *cp, i+1);
			}
			top[cp-count] = ak += *cp;
			nc--;
		}
		swap(*sp0, *sp1, temp);	/* Play it safe -- biggest bin last. */

		/*
		 * Permute misplacements home.  Already home: everything
		 * before aj, and in bin[c], items from top[c] on.
		 * Inner loop:
		 *	r = next element to put in place;
		 *	ak = top[r[i]] = location to put the next element.
		 *	aj = bottom of 1st disordered bin.
		 * Outer loop:
		 *	Once the 1st disordered bin is done, ie. aj >= ak,
		 *	aj<-aj + count[c] connects the bins in a linked list;
		 *	reset count[c].
		 */
		for (aj = a; aj < an;  *aj = r, aj += count[c], count[c] = 0)
			for (r = *aj;  aj < (ak = --top[c = tr[r[i]]]);)
				swap(*ak, r, t);
	}
}

/* Stable sort, requiring additional memory. */
static void
r_sort_b(a, ta, n, i, tr, endch)
	const u_char **a, **ta;
	int n, i;
	const u_char *tr;
	u_int endch;
{
	static int count[256], nc, bmin;
	int c;
	const u_char **ak, **ai;
	stack s[512], *sp, *sp0, *sp1, temp;
	const u_char **top[256];
	int *cp, bigc;

	sp = s;
	push(a, n, i);
	while (!empty(s)) {
		pop(a, n, i);
		if (n < THRESHOLD) {
			simplesort(a, n, i, tr, endch);
			continue;
		}

		if (nc == 0) {
			bmin = 255;
			for (ak = a + n; --ak >= a;) {
				c = tr[(*ak)[i]];
				if (++count[c] == 1 && c != endch) {
					if (c < bmin)
						bmin = c;
					nc++;
				}
			}
			if (sp + nc > s + SIZE) {
				r_sort_b(a, ta, n, i, tr, endch);
				continue;
			}
		}

		sp0 = sp1 = sp;
		bigc = 2;
		if (endch == 0) {
			top[0] = ak = a + count[0];
			count[0] = 0;
		} else {
			ak = a;
			top[255] = a + n;
			count[255] = 0;
		}
		for (cp = count + bmin; nc > 0; cp++) {
			while (*cp == 0)
				cp++;
			if ((c = *cp) > 1) {
				if (c > bigc) {
					bigc = c;
					sp1 = sp;
				}
				push(ak, c, i+1);
			}
			top[cp-count] = ak += c;
			*cp = 0;			/* Reset count[]. */
			nc--;
		}
		swap(*sp0, *sp1, temp);

		for (ak = ta + n, ai = a+n; ak > ta;)	/* Copy to temp. */
			*--ak = *--ai;
		for (ak = ta+n; --ak >= ta;)		/* Deal to piles. */
			*--top[tr[(*ak)[i]]] = *ak;
	}
}

static inline void
simplesort(a, n, b, tr, endch)	/* insertion sort */
	const u_char **a;
	int n, b;
	const u_char *tr;
	u_int endch;
{
	u_char ch;
	const u_char  **ak, **ai, *s, *t;

	for (ak = a+1; --n >= 1; ak++)
		for (ai = ak; ai > a; ai--) {
			for (s = ai[0] + b, t = ai[-1] + b;
			    (ch = tr[*s]) != endch; s++, t++)
				if (ch != tr[*t])
					break;
			if (ch >= tr[*t])
				break;
			swap(ai[0], ai[-1], s);
		}
}
Commit	Line	Data
9385eb3d	1	/*-
e9ce8d39 A	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
9385eb3d	6	* Peter McIlroy and by Dan Bernstein at New York University,
e9ce8d39 A	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.
e9ce8d39 A	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
9385eb3d A	33	#if defined(LIBC_SCCS) && !defined(lint)
	34	static char sccsid[] = "@(#)radixsort.c 8.2 (Berkeley) 4/28/95";
	35	#endif /* LIBC_SCCS and not lint */
	36	#include <sys/cdefs.h>
1f2f436a	37	__FBSDID("$FreeBSD: src/lib/libc/stdlib/radixsort.c,v 1.8 2007/01/09 00:28:10 imp Exp $");
e9ce8d39 A	38
	39	/*
	40	* Radixsort routines.
9385eb3d	41	*
e9ce8d39 A	42	* Program r_sort_a() is unstable but uses O(logN) extra memory for a stack.
e9ce8d39 A	43	* Use radixsort(a, n, trace, endchar) for this case.
9385eb3d	44	*
e9ce8d39 A	45	* For stable sorting (using N extra pointers) use sradixsort(), which calls
e9ce8d39 A	46	* r_sort_b().
9385eb3d	47	*
e9ce8d39 A	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
	57	typedef struct {
	58	const u_char **sa;
	59	int sn, si;
	60	} stack;
	61
	62	static inline void simplesort
9385eb3d A	63	(const u_char *, int, int, const u_char , u_int);
	64	static void r_sort_a(const u_char *, int, int, const u_char , u_int);
	65	static void r_sort_b(const u_char , const u_char , int, int,
	66	const u_char *, u_int);
e9ce8d39 A	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
	90	int
	91	radixsort(a, n, tab, endch)
	92	const u_char *a, tab;
	93	int n;
	94	u_int endch;
	95	{
	96	const u_char *tr;
	97	int c;
	98	u_char tr0[256];
	99
	100	SETUP;
	101	r_sort_a(a, n, 0, tr, endch);
	102	return (0);
	103	}
	104
	105	int
	106	sradixsort(a, n, tab, endch)
	107	const u_char *a, tab;
	108	int n;
	109	u_int endch;
	110	{
	111	const u_char tr, *ta;
	112	int c;
	113	u_char tr0[256];
	114
	115	SETUP;
	116	if (n < THRESHOLD)
	117	simplesort(a, n, 0, tr, endch);
	118	else {
	119	if ((ta = malloc(n * sizeof(a))) == NULL)
	120	return (-1);
	121	r_sort_b(a, ta, n, 0, tr, endch);
	122	free(ta);
	123	}
	124	return (0);
	125	}
	126
	127	#define empty(s) (s >= sp)
	128	#define pop(a, n, i) a = (--sp)->sa, n = sp->sn, i = sp->si
	129	#define push(a, n, i) sp->sa = a, sp->sn = n, (sp++)->si = i
	130	#define swap(a, b, t) t = a, a = b, b = t
131
132	/* Unstable, in-place sort. */
133	static void
134	r_sort_a(a, n, i, tr, endch)
135	const u_char **a;
136	int n, i;
137	const u_char *tr;
138	u_int endch;
139	{
9385eb3d A	140	static int count[256], nc, bmin;
	141	int c;
	142	const u_char *ak, r;
e9ce8d39 A	143	stack s[SIZE], sp, sp0, *sp1, temp;
	144	int *cp, bigc;
	145	const u_char *an, t, aj, top[256];
	146
	147	/* Set up stack. */
	148	sp = s;
	149	push(a, n, i);
	150	while (!empty(s)) {
	151	pop(a, n, i);
	152	if (n < THRESHOLD) {
	153	simplesort(a, n, i, tr, endch);
	154	continue;
	155	}
	156	an = a + n;
	157
	158	/* Make character histogram. */
	159	if (nc == 0) {
	160	bmin = 255; /* First occupied bin, excluding eos. */
	161	for (ak = a; ak < an;) {
	162	c = tr[(*ak++)[i]];
	163	if (++count[c] == 1 && c != endch) {
	164	if (c < bmin)
	165	bmin = c;
	166	nc++;
	167	}
	168	}
	169	if (sp + nc > s + SIZE) { /* Get more stack. */
	170	r_sort_a(a, n, i, tr, endch);
	171	continue;
	172	}
	173	}
	174
3d9156a7 A	175	/*
	176	* Special case: if all strings have the same
	177	* character at position i, move on to the next
	178	* character.
	179	*/
	180	if (nc == 1 && count[bmin] == n) {
	181	push(a, n, i+1);
	182	nc = count[bmin] = 0;
	183	continue;
	184	}
	185
e9ce8d39 A	186	/*
	187	* Set top[]; push incompletely sorted bins onto stack.
	188	* top[] = pointers to last out-of-place element in bins.
	189	* count[] = counts of elements in bins.
	190	* Before permuting: top[c-1] + count[c] = top[c];
	191	* during deal: top[c] counts down to top[c-1].
	192	*/
	193	sp0 = sp1 = sp; /* Stack position of biggest bin. */
	194	bigc = 2; /* Size of biggest bin. */
	195	if (endch == 0) /* Special case: set top[eos]. */
	196	top[0] = ak = a + count[0];
	197	else {
	198	ak = a;
	199	top[255] = an;
	200	}
	201	for (cp = count + bmin; nc > 0; cp++) {
	202	while (cp == 0) / Find next non-empty pile. */
	203	cp++;
	204	if (*cp > 1) {
	205	if (*cp > bigc) {
	206	bigc = *cp;
	207	sp1 = sp;
	208	}
	209	push(ak, *cp, i+1);
	210	}
	211	top[cp-count] = ak += *cp;
	212	nc--;
	213	}
	214	swap(sp0, sp1, temp); /* Play it safe -- biggest bin last. */
	215
	216	/*
	217	* Permute misplacements home. Already home: everything
	218	* before aj, and in bin[c], items from top[c] on.
	219	* Inner loop:
	220	* r = next element to put in place;
	221	* ak = top[r[i]] = location to put the next element.
	222	* aj = bottom of 1st disordered bin.
	223	* Outer loop:
	224	* Once the 1st disordered bin is done, ie. aj >= ak,
	225	* aj<-aj + count[c] connects the bins in a linked list;
	226	* reset count[c].
	227	*/
	228	for (aj = a; aj < an; *aj = r, aj += count[c], count[c] = 0)
	229	for (r = *aj; aj < (ak = --top[c = tr[r[i]]]);)
	230	swap(*ak, r, t);
	231	}
	232	}
	233
	234	/* Stable sort, requiring additional memory. */
	235	static void
	236	r_sort_b(a, ta, n, i, tr, endch)
	237	const u_char a, ta;
	238	int n, i;
	239	const u_char *tr;
	240	u_int endch;
	241	{
9385eb3d A	242	static int count[256], nc, bmin;
	243	int c;
	244	const u_char ak, ai;
e9ce8d39 A	245	stack s[512], sp, sp0, *sp1, temp;
	246	const u_char **top[256];
	247	int *cp, bigc;
	248
	249	sp = s;
	250	push(a, n, i);
	251	while (!empty(s)) {
	252	pop(a, n, i);
	253	if (n < THRESHOLD) {
	254	simplesort(a, n, i, tr, endch);
	255	continue;
	256	}
	257
	258	if (nc == 0) {
	259	bmin = 255;
	260	for (ak = a + n; --ak >= a;) {
	261	c = tr[(*ak)[i]];
	262	if (++count[c] == 1 && c != endch) {
	263	if (c < bmin)
	264	bmin = c;
	265	nc++;
	266	}
	267	}
	268	if (sp + nc > s + SIZE) {
	269	r_sort_b(a, ta, n, i, tr, endch);
	270	continue;
	271	}
	272	}
	273
	274	sp0 = sp1 = sp;
	275	bigc = 2;
	276	if (endch == 0) {
	277	top[0] = ak = a + count[0];
	278	count[0] = 0;
	279	} else {
	280	ak = a;
	281	top[255] = a + n;
	282	count[255] = 0;
	283	}
	284	for (cp = count + bmin; nc > 0; cp++) {
	285	while (*cp == 0)
	286	cp++;
	287	if ((c = *cp) > 1) {
	288	if (c > bigc) {
	289	bigc = c;
	290	sp1 = sp;
	291	}
	292	push(ak, c, i+1);
	293	}
	294	top[cp-count] = ak += c;
	295	cp = 0; / Reset count[]. */
	296	nc--;
	297	}
	298	swap(sp0, sp1, temp);
	299
	300	for (ak = ta + n, ai = a+n; ak > ta;) /* Copy to temp. */
	301	--ak = --ai;
	302	for (ak = ta+n; --ak >= ta;) /* Deal to piles. */
	303	--top[tr[(ak)[i]]] = *ak;
	304	}
	305	}
9385eb3d	306
e9ce8d39 A	307	static inline void
e9ce8d39 A	308	simplesort(a, n, b, tr, endch) /* insertion sort */
9385eb3d	309	const u_char **a;
e9ce8d39	310	int n, b;
9385eb3d	311	const u_char *tr;
e9ce8d39 A	312	u_int endch;
e9ce8d39 A	313	{
9385eb3d	314	u_char ch;
e9ce8d39 A	315	const u_char ak, ai, s, t;
	316
	317	for (ak = a+1; --n >= 1; ak++)
	318	for (ai = ak; ai > a; ai--) {
	319	for (s = ai[0] + b, t = ai[-1] + b;
	320	(ch = tr[*s]) != endch; s++, t++)
	321	if (ch != tr[*t])
	322	break;
	323	if (ch >= tr[*t])
	324	break;
	325	swap(ai[0], ai[-1], s);
	326	}
	327	}