1 /* @(#)radixsort.c 8.2 (Berkeley) 4/28/95 */
2 /* $NetBSD: radix_sort.c,v 1.3 2009/09/10 22:02:40 dsl Exp $ */
5 * Copyright (c) 1990, 1993
6 * The Regents of the University of California. All rights reserved.
8 * This code is derived from software contributed to Berkeley by
9 * Peter McIlroy and by Dan Bernstein at New York University,
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * 'stable' radix sort initially from libc/stdlib/radixsort.c
40 #include <sys/types.h>
47 RECHEADER **sa; /* Base of saved area */
48 int sn; /* Number of entries */
49 int si; /* index into data for compare */
52 static void simplesort(RECHEADER **, int, int);
54 #define THRESHOLD 20 /* Divert to simplesort(). */
56 #define empty(s) (s >= sp)
57 #define pop(a, n, i) a = (--sp)->sa, n = sp->sn, i = sp->si
58 #define push(a, n, i) sp->sa = a, sp->sn = n, (sp++)->si = i
59 #define swap(a, b, t) t = a, a = b, b = t
62 radix_sort(RECHEADER **a, RECHEADER **ta, int n)
64 u_int count[256], nc, bmin;
66 RECHEADER **ak, **tai, **lim;
69 stack *s, *sp, *sp0, *sp1, temp;
75 if (n < THRESHOLD && !DEBUG('r')) {
80 alloc_size = stack_size * sizeof *s;
81 s = malloc(alloc_size);
83 err(1, "Cannot allocate %zu bytes", alloc_size);
84 memset(&count, 0, sizeof count);
85 /* Technically 'top' doesn't need zeroing */
86 memset(&top, 0, sizeof top);
89 push(a, n, data_index);
91 pop(a, n, data_index);
92 if (n < THRESHOLD && !DEBUG('r')) {
93 simplesort(a, n, data_index);
97 /* Count number of times each 'next byte' occurs */
101 for (ak = a, tai = ta; ak < lim; ak++) {
103 if (data_index >= hdr->keylen) {
104 /* Short key, copy to start of output */
105 if (UNIQUE && a != sp->sa)
106 /* Stop duplicate being written out */
112 /* Save in temp buffer for distribute */
114 c = hdr->data[data_index];
115 if (++count[c] == 1) {
122 * We need save the bounds for each 'next byte' that
123 * occurs more so we can sort each block.
125 if (sp + nc > s + stack_size) {
127 alloc_size = stack_size * sizeof *s;
128 sp1 = realloc(s, alloc_size);
130 err(1, "Cannot re-allocate %zu bytes",
136 /* Minor optimisation to do the largest set last */
139 /* Convert 'counts' positions, saving bounds for later sorts */
141 for (cp = count + bmin; nc > 0; cp++) {
149 push(ak, c, data_index+1);
153 *cp = 0; /* Reset count[]. */
156 swap(*sp0, *sp1, temp);
158 for (ak = ta+n; --ak >= ta;) /* Deal to piles. */
159 *--top[(*ak)->data[data_index]] = *ak;
165 /* insertion sort, short records are sorted before long ones */
167 simplesort(RECHEADER **a, int n, int data_index)
169 RECHEADER **ak, **ai;
171 RECHEADER **lim = a + n;
180 for (ak = a+1; ak < lim; ak++) {
186 t_len = (*ai)->keylen;
189 for (i = data_index; ; i++) {
190 if (i >= s_len || i >= t_len) {
199 if (r == 0 && UNIQUE) {
200 /* Put record below existing */
202 /* Mark as duplicate - ignore */