lib/libc/stdlib/radixsort.c

   1 /*-
   2  * Copyright (c) 1990, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Peter McIlroy and by Dan Bernstein at New York University,
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 4. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  * @(#)radixsort.c      8.2 (Berkeley) 4/28/95
  33  * $FreeBSD: src/lib/libc/stdlib/radixsort.c,v 1.8 2007/01/09 00:28:10 imp Exp $
  34  * $DragonFly: src/lib/libc/stdlib/radixsort.c,v 1.5 2005/11/20 12:37:49 swildner Exp $
  35  */
  36
  37 /*
  38  * Radixsort routines.
  39  *
  40  * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack.
  41  * Use radixsort(a, n, trace, endchar) for this case.
  42  *
  43  * For stable sorting (using N extra pointers) use sradixsort(), which calls
  44  * r_sort_b().
  45  *
  46  * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic,
  47  * "Engineering Radix Sort".
  48  */
  49
  50 #include <sys/types.h>
  51 #include <stdlib.h>
  52 #include <stddef.h>
  53 #include <errno.h>
  54
  55 typedef struct {
  56         const u_char **sa;
  57         int sn, si;
  58 } stack;
  59
  60 static inline void simplesort(const u_char **, int, int, const u_char *, u_int);
  61 static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
  62 static void r_sort_b(const u_char **, const u_char **, int, int,
  63                      const u_char *, u_int);
  64
  65 #define THRESHOLD       20              /* Divert to simplesort(). */
  66 #define SIZE            512             /* Default stack size. */
  67
  68 #define SETUP {                                                         \
  69         if (tab == NULL) {                                              \
  70                 tr = tr0;                                               \
  71                 for (c = 0; c < endch; c++)                             \
  72                         tr0[c] = c + 1;                                 \
  73                 tr0[c] = 0;                                             \
  74                 for (c++; c < 256; c++)                                 \
  75                         tr0[c] = c;                                     \
  76                 endch = 0;                                              \
  77         } else {                                                        \
  78                 endch = tab[endch];                                     \
  79                 tr = tab;                                               \
  80                 if (endch != 0 && endch != 255) {                       \
  81                         errno = EINVAL;                                 \
  82                         return (-1);                                    \
  83                 }                                                       \
  84         }                                                               \
  85 }
  86
  87 int
  88 radixsort(const u_char **a, int n, const u_char *tab, u_int endch)
  89 {
  90         const u_char *tr;
  91         int c;
  92         u_char tr0[256];
  93
  94         SETUP;
  95         r_sort_a(a, n, 0, tr, endch);
  96         return (0);
  97 }
  98
  99 int
 100 sradixsort(const u_char **a, int n, const u_char *tab, u_int endch)
 101 {
 102         const u_char *tr, **ta;
 103         int c;
 104         u_char tr0[256];
 105
 106         SETUP;
 107         if (n < THRESHOLD)
 108                 simplesort(a, n, 0, tr, endch);
 109         else {
 110                 if ((ta = malloc(n * sizeof(a))) == NULL)
 111                         return (-1);
 112                 r_sort_b(a, ta, n, 0, tr, endch);
 113                 free(ta);
 114         }
 115         return (0);
 116 }
 117
 118 #define empty(s)        (s >= sp)
 119 #define pop(a, n, i)    a = (--sp)->sa, n = sp->sn, i = sp->si
 120 #define push(a, n, i)   sp->sa = a, sp->sn = n, (sp++)->si = i
 121 #define swap(a, b, t)   t = a, a = b, b = t
 122
 123 /* Unstable, in-place sort. */
 124 static void
 125 r_sort_a(const u_char **a, int n, int i, const u_char *tr, u_int endch)
 126 {
 127         static int count[256], nc, bmin;
 128         int c;
 129         const u_char **ak, *r;
 130         stack s[SIZE], *sp, *sp0, *sp1, temp;
 131         int *cp, bigc;
 132         const u_char **an, *t, **aj, **top[256];
 133
 134         /* Set up stack. */
 135         sp = s;
 136         push(a, n, i);
 137         while (!empty(s)) {
 138                 pop(a, n, i);
 139                 if (n < THRESHOLD) {
 140                         simplesort(a, n, i, tr, endch);
 141                         continue;
 142                 }
 143                 an = a + n;
 144
 145                 /* Make character histogram. */
 146                 if (nc == 0) {
 147                         bmin = 255;     /* First occupied bin, excluding eos. */
 148                         for (ak = a; ak < an;) {
 149                                 c = tr[(*ak++)[i]];
 150                                 if (++count[c] == 1 && c != endch) {
 151                                         if (c < bmin)
 152                                                 bmin = c;
 153                                         nc++;
 154                                 }
 155                         }
 156                         if (sp + nc > s + SIZE) {       /* Get more stack. */
 157                                 r_sort_a(a, n, i, tr, endch);
 158                                 continue;
 159                         }
 160                 }
 161
 162                 /*
 163                  * Special case: if all strings have the same
 164                  * character at position i, move on to the next
 165                  * character.
 166                  */
 167                 if (nc == 1 && count[bmin] == n) {
 168                         push(a, n, i+1);
 169                         nc = count[bmin] = 0;
 170                         continue;
 171                 }
 172
 173                 /*
 174                  * Set top[]; push incompletely sorted bins onto stack.
 175                  * top[] = pointers to last out-of-place element in bins.
 176                  * count[] = counts of elements in bins.
 177                  * Before permuting: top[c-1] + count[c] = top[c];
 178                  * during deal: top[c] counts down to top[c-1].
 179                  */
 180                 sp0 = sp1 = sp;         /* Stack position of biggest bin. */
 181                 bigc = 2;               /* Size of biggest bin. */
 182                 if (endch == 0)         /* Special case: set top[eos]. */
 183                         top[0] = ak = a + count[0];
 184                 else {
 185                         ak = a;
 186                         top[255] = an;
 187                 }
 188                 for (cp = count + bmin; nc > 0; cp++) {
 189                         while (*cp == 0)        /* Find next non-empty pile. */
 190                                 cp++;
 191                         if (*cp > 1) {
 192                                 if (*cp > bigc) {
 193                                         bigc = *cp;
 194                                         sp1 = sp;
 195                                 }
 196                                 push(ak, *cp, i+1);
 197                         }
 198                         top[cp-count] = ak += *cp;
 199                         nc--;
 200                 }
 201                 swap(*sp0, *sp1, temp); /* Play it safe -- biggest bin last. */
 202
 203                 /*
 204                  * Permute misplacements home.  Already home: everything
 205                  * before aj, and in bin[c], items from top[c] on.
 206                  * Inner loop:
 207                  *      r = next element to put in place;
 208                  *      ak = top[r[i]] = location to put the next element.
 209                  *      aj = bottom of 1st disordered bin.
 210                  * Outer loop:
 211                  *      Once the 1st disordered bin is done, ie. aj >= ak,
 212                  *      aj<-aj + count[c] connects the bins in a linked list;
 213                  *      reset count[c].
 214                  */
 215                 for (aj = a; aj < an;  *aj = r, aj += count[c], count[c] = 0)
 216                         for (r = *aj;  aj < (ak = --top[c = tr[r[i]]]);)
 217                                 swap(*ak, r, t);
 218         }
 219 }
 220
 221 /* Stable sort, requiring additional memory. */
 222 static void
 223 r_sort_b(const u_char **a, const u_char **ta, int n, int i, const u_char *tr,
 224          u_int endch)
 225 {
 226         static int count[256], nc, bmin;
 227         int c;
 228         const u_char **ak, **ai;
 229         stack s[512], *sp, *sp0, *sp1, temp;
 230         const u_char **top[256];
 231         int *cp, bigc;
 232
 233         sp = s;
 234         push(a, n, i);
 235         while (!empty(s)) {
 236                 pop(a, n, i);
 237                 if (n < THRESHOLD) {
 238                         simplesort(a, n, i, tr, endch);
 239                         continue;
 240                 }
 241
 242                 if (nc == 0) {
 243                         bmin = 255;
 244                         for (ak = a + n; --ak >= a;) {
 245                                 c = tr[(*ak)[i]];
 246                                 if (++count[c] == 1 && c != endch) {
 247                                         if (c < bmin)
 248                                                 bmin = c;
 249                                         nc++;
 250                                 }
 251                         }
 252                         if (sp + nc > s + SIZE) {
 253                                 r_sort_b(a, ta, n, i, tr, endch);
 254                                 continue;
 255                         }
 256                 }
 257
 258                 sp0 = sp1 = sp;
 259                 bigc = 2;
 260                 if (endch == 0) {
 261                         top[0] = ak = a + count[0];
 262                         count[0] = 0;
 263                 } else {
 264                         ak = a;
 265                         top[255] = a + n;
 266                         count[255] = 0;
 267                 }
 268                 for (cp = count + bmin; nc > 0; cp++) {
 269                         while (*cp == 0)
 270                                 cp++;
 271                         if ((c = *cp) > 1) {
 272                                 if (c > bigc) {
 273                                         bigc = c;
 274                                         sp1 = sp;
 275                                 }
 276                                 push(ak, c, i+1);
 277                         }
 278                         top[cp-count] = ak += c;
 279                         *cp = 0;                        /* Reset count[]. */
 280                         nc--;
 281                 }
 282                 swap(*sp0, *sp1, temp);
 283
 284                 for (ak = ta + n, ai = a+n; ak > ta;)   /* Copy to temp. */
 285                         *--ak = *--ai;
 286                 for (ak = ta+n; --ak >= ta;)            /* Deal to piles. */
 287                         *--top[tr[(*ak)[i]]] = *ak;
 288         }
 289 }
 290
 291 /* insertion sort */
 292 static inline void
 293 simplesort(const u_char **a, int n, int b, const u_char *tr, u_int endch)
 294 {
 295         u_char ch;
 296         const u_char  **ak, **ai, *s, *t;
 297
 298         for (ak = a+1; --n >= 1; ak++)
 299                 for (ai = ak; ai > a; ai--) {
 300                         for (s = ai[0] + b, t = ai[-1] + b;
 301                             (ch = tr[*s]) != endch; s++, t++)
 302                                 if (ch != tr[*t])
 303                                         break;
 304                         if (ch >= tr[*t])
 305                                 break;
 306                         swap(ai[0], ai[-1], s);
 307                 }
 308 }