1 /* $NetBSD: radix_sort.c,v 1.3 2009/09/10 22:02:40 dsl Exp $ */
4 * Copyright (c) 1990, 1993
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from software contributed to Berkeley by
8 * Peter McIlroy and by Dan Bernstein at New York University,
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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
35 #include <sys/cdefs.h>
36 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] = "@(#)radixsort.c 8.2 (Berkeley) 4/28/95";
40 __RCSID("$NetBSD: radix_sort.c,v 1.3 2009/09/10 22:02:40 dsl Exp $");
42 #endif /* LIBC_SCCS and not lint */
45 * 'stable' radix sort initially from libc/stdlib/radixsort.c
48 #include <sys/types.h>
55 RECHEADER **sa; /* Base of saved area */
56 int sn; /* Number of entries */
57 int si; /* index into data for compare */
60 static void simplesort(RECHEADER **, int, int);
62 #define THRESHOLD 20 /* Divert to simplesort(). */
64 #define empty(s) (s >= sp)
65 #define pop(a, n, i) a = (--sp)->sa, n = sp->sn, i = sp->si
66 #define push(a, n, i) sp->sa = a, sp->sn = n, (sp++)->si = i
67 #define swap(a, b, t) t = a, a = b, b = t
70 radix_sort(RECHEADER **a, RECHEADER **ta, int n)
72 u_int count[256], nc, bmin;
74 RECHEADER **ak, **tai, **lim;
77 stack *s, *sp, *sp0, *sp1, temp;
83 if (n < THRESHOLD && !DEBUG('r')) {
88 alloc_size = stack_size * sizeof *s;
89 s = malloc(alloc_size);
91 err(1, "Cannot allocate %zu bytes", alloc_size);
92 memset(&count, 0, sizeof count);
93 /* Technically 'top' doesn't need zeroing */
94 memset(&top, 0, sizeof top);
97 push(a, n, data_index);
99 pop(a, n, data_index);
100 if (n < THRESHOLD && !DEBUG('r')) {
101 simplesort(a, n, data_index);
105 /* Count number of times each 'next byte' occurs */
109 for (ak = a, tai = ta; ak < lim; ak++) {
111 if (data_index >= hdr->keylen) {
112 /* Short key, copy to start of output */
113 if (UNIQUE && a != sp->sa)
114 /* Stop duplicate being written out */
120 /* Save in temp buffer for distribute */
122 c = hdr->data[data_index];
123 if (++count[c] == 1) {
130 * We need save the bounds for each 'next byte' that
131 * occurs more so we can sort each block.
133 if (sp + nc > s + stack_size) {
135 alloc_size = stack_size * sizeof *s;
136 sp1 = realloc(s, alloc_size);
138 err(1, "Cannot re-allocate %zu bytes",
144 /* Minor optimisation to do the largest set last */
147 /* Convert 'counts' positions, saving bounds for later sorts */
149 for (cp = count + bmin; nc > 0; cp++) {
157 push(ak, c, data_index+1);
161 *cp = 0; /* Reset count[]. */
164 swap(*sp0, *sp1, temp);
166 for (ak = ta+n; --ak >= ta;) /* Deal to piles. */
167 *--top[(*ak)->data[data_index]] = *ak;
173 /* insertion sort, short records are sorted before long ones */
175 simplesort(RECHEADER **a, int n, int data_index)
177 RECHEADER **ak, **ai;
179 RECHEADER **lim = a + n;
188 for (ak = a+1; ak < lim; ak++) {
194 t_len = (*ai)->keylen;
197 for (i = data_index; ; i++) {
198 if (i >= s_len || i >= t_len) {
207 if (r == 0 && UNIQUE) {
208 /* Put record below existing */
210 /* Mark as duplicate - ignore */