summaryrefslogtreecommitdiff
path: root/usr.bin/sort/radix_sort.c
diff options
context:
space:
mode:
authorKiyoshi Aman <kiyoshi.aman+adelie@gmail.com>2019-02-01 22:55:37 +0000
committerKiyoshi Aman <kiyoshi.aman+adelie@gmail.com>2019-02-03 18:22:05 -0600
commit5b57d28ffb6e1ef86b50f7d05d977826eae89bfe (patch)
tree154a22fe556b49e6927197336f8bf91b12eacd5e /usr.bin/sort/radix_sort.c
downloaduserland-5b57d28ffb6e1ef86b50f7d05d977826eae89bfe.tar.gz
userland-5b57d28ffb6e1ef86b50f7d05d977826eae89bfe.tar.bz2
userland-5b57d28ffb6e1ef86b50f7d05d977826eae89bfe.tar.xz
userland-5b57d28ffb6e1ef86b50f7d05d977826eae89bfe.zip
initial population
Diffstat (limited to 'usr.bin/sort/radix_sort.c')
-rw-r--r--usr.bin/sort/radix_sort.c217
1 files changed, 217 insertions, 0 deletions
diff --git a/usr.bin/sort/radix_sort.c b/usr.bin/sort/radix_sort.c
new file mode 100644
index 0000000..4ec5ff8
--- /dev/null
+++ b/usr.bin/sort/radix_sort.c
@@ -0,0 +1,217 @@
+/* $NetBSD: radix_sort.c,v 1.4 2009/09/19 16:18:00 dsl Exp $ */
+
+/*-
+ * 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. 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.
+ */
+
+#include <sys/cdefs.h>
+#if defined(LIBC_SCCS) && !defined(lint)
+#if 0
+static char sccsid[] = "@(#)radixsort.c 8.2 (Berkeley) 4/28/95";
+#else
+__RCSID("$NetBSD: radix_sort.c,v 1.4 2009/09/19 16:18:00 dsl Exp $");
+#endif
+#endif /* LIBC_SCCS and not lint */
+
+/*
+ * 'stable' radix sort initially from libc/stdlib/radixsort.c
+ */
+
+#include <sys/types.h>
+
+#include <assert.h>
+#include <errno.h>
+#include <util.h>
+#include "sort.h"
+
+typedef struct {
+ RECHEADER **sa; /* Base of saved area */
+ int sn; /* Number of entries */
+ int si; /* index into data for compare */
+} stack;
+
+static void simplesort(RECHEADER **, int, int);
+
+#define THRESHOLD 20 /* Divert to simplesort(). */
+
+#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
+
+void
+radix_sort(RECHEADER **a, RECHEADER **ta, int n)
+{
+ u_int count[256], nc, bmin;
+ u_int c;
+ RECHEADER **ak, **tai, **lim;
+ RECHEADER *hdr;
+ int stack_size = 512;
+ stack *s, *sp, *sp0, *sp1, temp;
+ RECHEADER **top[256];
+ u_int *cp, bigc;
+ int data_index = 0;
+
+ if (n < THRESHOLD && !DEBUG('r')) {
+ simplesort(a, n, 0);
+ return;
+ }
+
+ s = emalloc(stack_size * sizeof *s);
+ memset(&count, 0, sizeof count);
+ /* Technically 'top' doesn't need zeroing */
+ memset(&top, 0, sizeof top);
+
+ sp = s;
+ push(a, n, data_index);
+ while (!empty(s)) {
+ pop(a, n, data_index);
+ if (n < THRESHOLD && !DEBUG('r')) {
+ simplesort(a, n, data_index);
+ continue;
+ }
+
+ /* Count number of times each 'next byte' occurs */
+ nc = 0;
+ bmin = 255;
+ lim = a + n;
+ for (ak = a, tai = ta; ak < lim; ak++) {
+ hdr = *ak;
+ if (data_index >= hdr->keylen) {
+ /* Short key, copy to start of output */
+ if (UNIQUE && a != sp->sa)
+ /* Stop duplicate being written out */
+ hdr->keylen = -1;
+ *a++ = hdr;
+ n--;
+ continue;
+ }
+ /* Save in temp buffer for distribute */
+ *tai++ = hdr;
+ c = hdr->data[data_index];
+ if (++count[c] == 1) {
+ if (c < bmin)
+ bmin = c;
+ nc++;
+ }
+ }
+ /*
+ * We need save the bounds for each 'next byte' that
+ * occurs more so we can sort each block.
+ */
+ if (sp + nc > s + stack_size) {
+ stack_size *= 2;
+ sp1 = erealloc(s, stack_size * sizeof *s);
+ sp = sp1 + (sp - s);
+ s = sp1;
+ }
+
+ /* Minor optimisation to do the largest set last */
+ sp0 = sp1 = sp;
+ bigc = 2;
+ /* Convert 'counts' positions, saving bounds for later sorts */
+ ak = a;
+ 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, data_index+1);
+ }
+ ak += c;
+ top[cp-count] = ak;
+ *cp = 0; /* Reset count[]. */
+ nc--;
+ }
+ swap(*sp0, *sp1, temp);
+
+ for (ak = ta+n; --ak >= ta;) /* Deal to piles. */
+ *--top[(*ak)->data[data_index]] = *ak;
+ }
+
+ free(s);
+}
+
+/* insertion sort, short records are sorted before long ones */
+static void
+simplesort(RECHEADER **a, int n, int data_index)
+{
+ RECHEADER **ak, **ai;
+ RECHEADER *akh;
+ RECHEADER **lim = a + n;
+ const u_char *s, *t;
+ int s_len, t_len;
+ int i;
+ int r;
+
+ if (n <= 1)
+ return;
+
+ for (ak = a+1; ak < lim; ak++) {
+ akh = *ak;
+ s = akh->data;
+ s_len = akh->keylen;
+ for (ai = ak; ;) {
+ ai--;
+ t_len = (*ai)->keylen;
+ if (t_len != -1) {
+ t = (*ai)->data;
+ for (i = data_index; ; i++) {
+ if (i >= s_len || i >= t_len) {
+ r = s_len - t_len;
+ break;
+ }
+ r = s[i] - t[i];
+ if (r != 0)
+ break;
+ }
+ if (r >= 0) {
+ if (r == 0 && UNIQUE) {
+ /* Put record below existing */
+ ai[1] = ai[0];
+ /* Mark as duplicate - ignore */
+ akh->keylen = -1;
+ } else {
+ ai++;
+ }
+ break;
+ }
+ }
+ ai[1] = ai[0];
+ if (ai == a)
+ break;
+ }
+ ai[0] = akh;
+ }
+}