usr.bin/sort/radix_sort.c

   1 /*      $NetBSD: radix_sort.c,v 1.3 2009/09/10 22:02:40 dsl Exp $       */
   2
   3 /*-
   4  * Copyright (c) 1990, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Peter McIlroy and by Dan Bernstein at New York University,
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  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.
  21  *
  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
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <sys/cdefs.h>
  36 #if defined(LIBC_SCCS) && !defined(lint)
  37 #if 0
  38 static char sccsid[] = "@(#)radixsort.c 8.2 (Berkeley) 4/28/95";
  39 #else
  40 __RCSID("$NetBSD: radix_sort.c,v 1.3 2009/09/10 22:02:40 dsl Exp $");
  41 #endif
  42 #endif /* LIBC_SCCS and not lint */
  43
  44 /*
  45  * 'stable' radix sort initially from libc/stdlib/radixsort.c
  46  */
  47
  48 #include <sys/types.h>
  49
  50 #include <assert.h>
  51 #include <errno.h>
  52 #include "sort.h"
  53
  54 typedef struct {
  55         RECHEADER **sa;         /* Base of saved area */
  56         int sn;                 /* Number of entries */
  57         int si;                 /* index into data for compare */
  58 } stack;
  59
  60 static void simplesort(RECHEADER **, int, int);
  61
  62 #define THRESHOLD       20              /* Divert to simplesort(). */
  63
  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
  68
  69 void
  70 radix_sort(RECHEADER **a, RECHEADER **ta, int n)
  71 {
  72         u_int count[256], nc, bmin;
  73         u_int c;
  74         RECHEADER **ak, **tai, **lim;
  75         RECHEADER *hdr;
  76         int stack_size = 512;
  77         stack *s, *sp, *sp0, *sp1, temp;
  78         RECHEADER **top[256];
  79         u_int *cp, bigc;
  80         size_t alloc_size;
  81         int data_index = 0;
  82
  83         if (n < THRESHOLD && !DEBUG('r')) {
  84                 simplesort(a, n, 0);
  85                 return;
  86         }
  87
  88         alloc_size = stack_size * sizeof *s;
  89         s = malloc(alloc_size);
  90         if (s == NULL)
  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);
  95
  96         sp = s;
  97         push(a, n, data_index);
  98         while (!empty(s)) {
  99                 pop(a, n, data_index);
 100                 if (n < THRESHOLD && !DEBUG('r')) {
 101                         simplesort(a, n, data_index);
 102                         continue;
 103                 }
 104
 105                 /* Count number of times each 'next byte' occurs */
 106                 nc = 0;
 107                 bmin = 255;
 108                 lim = a + n;
 109                 for (ak = a, tai = ta; ak < lim; ak++) {
 110                         hdr = *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 */
 115                                         hdr->keylen = -1;
 116                                 *a++ = hdr;
 117                                 n--;
 118                                 continue;
 119                         }
 120                         /* Save in temp buffer for distribute */
 121                         *tai++ = hdr;
 122                         c = hdr->data[data_index];
 123                         if (++count[c] == 1) {
 124                                 if (c < bmin)
 125                                         bmin = c;
 126                                 nc++;
 127                         }
 128                 }
 129                 /*
 130                  * We need save the bounds for each 'next byte' that
 131                  * occurs more so we can sort each block.
 132                  */
 133                 if (sp + nc > s + stack_size) {
 134                         stack_size *= 2;
 135                         alloc_size = stack_size * sizeof *s;
 136                         sp1 = realloc(s, alloc_size);
 137                         if (sp1 == NULL)
 138                                 err(1, "Cannot re-allocate %zu bytes",
 139                                     alloc_size);
 140                         sp = sp1 + (sp - s);
 141                         s = sp1;
 142                 }
 143
 144                 /* Minor optimisation to do the largest set last */
 145                 sp0 = sp1 = sp;
 146                 bigc = 2;
 147                 /* Convert 'counts' positions, saving bounds for later sorts */
 148                 ak = a;
 149                 for (cp = count + bmin; nc > 0; cp++) {
 150                         while (*cp == 0)
 151                                 cp++;
 152                         if ((c = *cp) > 1) {
 153                                 if (c > bigc) {
 154                                         bigc = c;
 155                                         sp1 = sp;
 156                                 }
 157                                 push(ak, c, data_index+1);
 158                         }
 159                         ak += c;
 160                         top[cp-count] = ak;
 161                         *cp = 0;                        /* Reset count[]. */
 162                         nc--;
 163                 }
 164                 swap(*sp0, *sp1, temp);
 165
 166                 for (ak = ta+n; --ak >= ta;)            /* Deal to piles. */
 167                         *--top[(*ak)->data[data_index]] = *ak;
 168         }
 169
 170         free(s);
 171 }
 172
 173 /* insertion sort, short records are sorted before long ones */
 174 static void
 175 simplesort(RECHEADER **a, int n, int data_index)
 176 {
 177         RECHEADER **ak, **ai;
 178         RECHEADER *akh;
 179         RECHEADER **lim = a + n;
 180         const u_char *s, *t;
 181         int s_len, t_len;
 182         int i;
 183         int r;
 184
 185         if (n <= 1)
 186                 return;
 187
 188         for (ak = a+1; ak < lim; ak++) {
 189                 akh = *ak;
 190                 s = akh->data;
 191                 s_len = akh->keylen;
 192                 for (ai = ak; ;) {
 193                         ai--;
 194                         t_len = (*ai)->keylen;
 195                         if (t_len != -1) {
 196                                 t = (*ai)->data;
 197                                 for (i = data_index; ; i++) {
 198                                         if (i >= s_len || i >= t_len) {
 199                                                 r = s_len - t_len;
 200                                                 break;
 201                                         }
 202                                         r =  s[i]  - t[i];
 203                                         if (r != 0)
 204                                                 break;
 205                                 }
 206                                 if (r >= 0) {
 207                                         if (r == 0 && UNIQUE) {
 208                                                 /* Put record below existing */
 209                                                 ai[1] = ai[0];
 210                                                 /* Mark as duplicate - ignore */
 211                                                 akh->keylen = -1;
 212                                         } else {
 213                                                 ai++;
 214                                         }
 215                                         break;
 216                                 }
 217                         }
 218                         ai[1] = ai[0];
 219                         if (ai == a)
 220                                 break;
 221                 }
 222                 ai[0] = akh;
 223         }
 224 }