usr.bin/sort/radix_sort.c

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