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

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 * 
 * This Original Code and all software distributed under the License are
 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
 * 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.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 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.
 */


/*
 * 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
	    __P((const u_char **, int, int, const u_char *, u_int));
static void r_sort_a __P((const u_char **, int, int, const u_char *, u_int));
static void r_sort_b __P((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;
	register int c;
	register 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;
			}
		}

		/*
		 * 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;
	register int c;
	register 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 */
	register const u_char **a;
	int n, b;
	register const u_char *tr;
	u_int endch;
{
	register 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
e9ce8d39 A	1	/*
	2	* Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
	6	* The contents of this file constitute Original Code as defined in and
	7	* are subject to the Apple Public Source License Version 1.1 (the
	8	* "License"). You may not use this file except in compliance with the
	9	* License. Please obtain a copy of the License at
	10	* http://www.apple.com/publicsource and read it before using this file.
	11	*
	12	* This Original Code and all software distributed under the License are
	13	* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	14	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	15	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	16	* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
	17	* License for the specific language governing rights and limitations
	18	* under the License.
	19	*
	20	* @APPLE_LICENSE_HEADER_END@
	21	*/
	22	/*
	23	* Copyright (c) 1990, 1993
	24	* The Regents of the University of California. All rights reserved.
	25	*
	26	* This code is derived from software contributed to Berkeley by
	27	* Peter McIlroy and by Dan Bernstein at New York University,
	28	*
	29	* Redistribution and use in source and binary forms, with or without
	30	* modification, are permitted provided that the following conditions
	31	* are met:
	32	* 1. Redistributions of source code must retain the above copyright
	33	* notice, this list of conditions and the following disclaimer.
	34	* 2. Redistributions in binary form must reproduce the above copyright
	35	* notice, this list of conditions and the following disclaimer in the
	36	* documentation and/or other materials provided with the distribution.
	37	* 3. All advertising materials mentioning features or use of this software
	38	* must display the following acknowledgement:
	39	* This product includes software developed by the University of
	40	* California, Berkeley and its contributors.
	41	* 4. Neither the name of the University nor the names of its contributors
	42	* may be used to endorse or promote products derived from this software
	43	* without specific prior written permission.
	44	*
	45	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	46	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	47	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	48	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	49	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	50	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	51	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	52	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	53	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	54	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	55	* SUCH DAMAGE.
	56	*/
	57
	58
	59	/*
	60	* Radixsort routines.
	61	*
	62	* Program r_sort_a() is unstable but uses O(logN) extra memory for a stack.
	63	* Use radixsort(a, n, trace, endchar) for this case.
	64	*
65	* For stable sorting (using N extra pointers) use sradixsort(), which calls
66	* r_sort_b().
67	*
68	* For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic,
69	* "Engineering Radix Sort".
70	*/
71
72	#include <sys/types.h>
73	#include <stdlib.h>
74	#include <stddef.h>
75	#include <errno.h>
76
77	typedef struct {
78	const u_char **sa;
79	int sn, si;
80	} stack;
81
82	static inline void simplesort
83	__P((const u_char *, int, int, const u_char , u_int));
84	static void r_sort_a __P((const u_char *, int, int, const u_char , u_int));
85	static void r_sort_b __P((const u_char **,
86	const u_char *, int, int, const u_char , u_int));
87
88	#define THRESHOLD 20 /* Divert to simplesort(). */
89	#define SIZE 512 /* Default stack size. */
90
91	#define SETUP { \
92	if (tab == NULL) { \
93	tr = tr0; \
94	for (c = 0; c < endch; c++) \
95	tr0[c] = c + 1; \
96	tr0[c] = 0; \
97	for (c++; c < 256; c++) \
98	tr0[c] = c; \
99	endch = 0; \
100	} else { \
101	endch = tab[endch]; \
102	tr = tab; \
103	if (endch != 0 && endch != 255) { \
104	errno = EINVAL; \
105	return (-1); \
106	} \
107	} \
108	}
109
110	int
111	radixsort(a, n, tab, endch)
112	const u_char *a, tab;
113	int n;
114	u_int endch;
115	{
116	const u_char *tr;
117	int c;
118	u_char tr0[256];
119
120	SETUP;
121	r_sort_a(a, n, 0, tr, endch);
122	return (0);
123	}
124
125	int
126	sradixsort(a, n, tab, endch)
127	const u_char *a, tab;
128	int n;
129	u_int endch;
130	{
131	const u_char tr, *ta;
132	int c;
133	u_char tr0[256];
134
135	SETUP;
136	if (n < THRESHOLD)
137	simplesort(a, n, 0, tr, endch);
138	else {
139	if ((ta = malloc(n * sizeof(a))) == NULL)
140	return (-1);
141	r_sort_b(a, ta, n, 0, tr, endch);
142	free(ta);
143	}
144	return (0);
145	}
146
147	#define empty(s) (s >= sp)
148	#define pop(a, n, i) a = (--sp)->sa, n = sp->sn, i = sp->si
149	#define push(a, n, i) sp->sa = a, sp->sn = n, (sp++)->si = i
150	#define swap(a, b, t) t = a, a = b, b = t
151
152	/* Unstable, in-place sort. */
153	static void
154	r_sort_a(a, n, i, tr, endch)
155	const u_char **a;
156	int n, i;
157	const u_char *tr;
158	u_int endch;
159	{
160	static int count[256], nc, bmin;
161	register int c;
162	register const u_char *ak, r;
163	stack s[SIZE], sp, sp0, *sp1, temp;
164	int *cp, bigc;
165	const u_char *an, t, aj, top[256];
166
167	/* Set up stack. */
168	sp = s;
169	push(a, n, i);
170	while (!empty(s)) {
171	pop(a, n, i);
172	if (n < THRESHOLD) {
173	simplesort(a, n, i, tr, endch);
174	continue;
175	}
176	an = a + n;
177
178	/* Make character histogram. */
179	if (nc == 0) {
180	bmin = 255; /* First occupied bin, excluding eos. */
181	for (ak = a; ak < an;) {
182	c = tr[(*ak++)[i]];
183	if (++count[c] == 1 && c != endch) {
184	if (c < bmin)
185	bmin = c;
186	nc++;
187	}
188	}
189	if (sp + nc > s + SIZE) { /* Get more stack. */
190	r_sort_a(a, n, i, tr, endch);
191	continue;
192	}
193	}
194
195	/*
196	* Set top[]; push incompletely sorted bins onto stack.
197	* top[] = pointers to last out-of-place element in bins.
198	* count[] = counts of elements in bins.
199	* Before permuting: top[c-1] + count[c] = top[c];
200	* during deal: top[c] counts down to top[c-1].
201	*/
202	sp0 = sp1 = sp; /* Stack position of biggest bin. */
203	bigc = 2; /* Size of biggest bin. */
204	if (endch == 0) /* Special case: set top[eos]. */
205	top[0] = ak = a + count[0];
206	else {
207	ak = a;
208	top[255] = an;
209	}
210	for (cp = count + bmin; nc > 0; cp++) {
211	while (cp == 0) / Find next non-empty pile. */
212	cp++;
213	if (*cp > 1) {
214	if (*cp > bigc) {
215	bigc = *cp;
216	sp1 = sp;
217	}
218	push(ak, *cp, i+1);
219	}
220	top[cp-count] = ak += *cp;
221	nc--;
222	}
223	swap(sp0, sp1, temp); /* Play it safe -- biggest bin last. */
224
225	/*
226	* Permute misplacements home. Already home: everything
227	* before aj, and in bin[c], items from top[c] on.
228	* Inner loop:
229	* r = next element to put in place;
230	* ak = top[r[i]] = location to put the next element.
231	* aj = bottom of 1st disordered bin.
232	* Outer loop:
233	* Once the 1st disordered bin is done, ie. aj >= ak,
234	* aj<-aj + count[c] connects the bins in a linked list;
235	* reset count[c].
236	*/
237	for (aj = a; aj < an; *aj = r, aj += count[c], count[c] = 0)
238	for (r = *aj; aj < (ak = --top[c = tr[r[i]]]);)
239	swap(*ak, r, t);
240	}
241	}
242
243	/* Stable sort, requiring additional memory. */
244	static void
245	r_sort_b(a, ta, n, i, tr, endch)
246	const u_char a, ta;
247	int n, i;
248	const u_char *tr;
249	u_int endch;
250	{
251	static int count[256], nc, bmin;
252	register int c;
253	register const u_char ak, ai;
254	stack s[512], sp, sp0, *sp1, temp;
255	const u_char **top[256];
256	int *cp, bigc;
257
258	sp = s;
259	push(a, n, i);
260	while (!empty(s)) {
261	pop(a, n, i);
262	if (n < THRESHOLD) {
263	simplesort(a, n, i, tr, endch);
264	continue;
265	}
266
267	if (nc == 0) {
268	bmin = 255;
269	for (ak = a + n; --ak >= a;) {
270	c = tr[(*ak)[i]];
271	if (++count[c] == 1 && c != endch) {
272	if (c < bmin)
273	bmin = c;
274	nc++;
275	}
276	}
277	if (sp + nc > s + SIZE) {
278	r_sort_b(a, ta, n, i, tr, endch);
279	continue;
280	}
281	}
282
283	sp0 = sp1 = sp;
284	bigc = 2;
285	if (endch == 0) {
286	top[0] = ak = a + count[0];
287	count[0] = 0;
288	} else {
289	ak = a;
290	top[255] = a + n;
291	count[255] = 0;
292	}
293	for (cp = count + bmin; nc > 0; cp++) {
294	while (*cp == 0)
295	cp++;
296	if ((c = *cp) > 1) {
297	if (c > bigc) {
298	bigc = c;
299	sp1 = sp;
300	}
301	push(ak, c, i+1);
302	}
303	top[cp-count] = ak += c;
304	cp = 0; / Reset count[]. */
305	nc--;
306	}
307	swap(sp0, sp1, temp);
308
309	for (ak = ta + n, ai = a+n; ak > ta;) /* Copy to temp. */
310	--ak = --ai;
311	for (ak = ta+n; --ak >= ta;) /* Deal to piles. */
312	--top[tr[(ak)[i]]] = *ak;
313	}
314	}
315
316	static inline void
317	simplesort(a, n, b, tr, endch) /* insertion sort */
318	register const u_char **a;
319	int n, b;
320	register const u_char *tr;
321	u_int endch;
322	{
323	register u_char ch;
324	const u_char ak, ai, s, t;
325
326	for (ak = a+1; --n >= 1; ak++)
327	for (ai = ak; ai > a; ai--) {
328	for (s = ai[0] + b, t = ai[-1] + b;
329	(ch = tr[*s]) != endch; s++, t++)
330	if (ch != tr[*t])
331	break;
332	if (ch >= tr[*t])
333	break;
334	swap(ai[0], ai[-1], s);
335	}
336	}