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