lib/libc/stdlib/radixsort.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-3-Clause
   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 #if defined(LIBC_SCCS) && !defined(lint)
  36 static char sccsid[] = "@(#)radixsort.c 8.2 (Berkeley) 4/28/95";
  37 #endif /* LIBC_SCCS and not lint */
  38 #include <sys/cdefs.h>
  39 __FBSDID("$FreeBSD$");
  40
  41 /*
  42  * Radixsort routines.
  43  *
  44  * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack.
  45  * Use radixsort(a, n, trace, endchar) for this case.
  46  *
  47  * For stable sorting (using N extra pointers) use sradixsort(), which calls
  48  * r_sort_b().
  49  *
  50  * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic,
  51  * "Engineering Radix Sort".
  52  */
  53
  54 #include <sys/types.h>
  55 #include <stdlib.h>
  56 #include <stddef.h>
  57 #include <errno.h>
  58
  59 typedef struct {
  60         const u_char **sa;
  61         int sn, si;
  62 } stack;
  63
  64 static inline void simplesort
  65 (const u_char **, int, int, const u_char *, u_int);
  66 static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
  67 static void r_sort_b(const u_char **, const u_char **, int, int,
  68     const u_char *, u_int);
  69
  70 #define THRESHOLD       20              /* Divert to simplesort(). */
  71 #define SIZE            512             /* Default stack size. */
  72
  73 #define SETUP {                                                         \
  74         if (tab == NULL) {                                              \
  75                 tr = tr0;                                               \
  76                 for (c = 0; c < endch; c++)                             \
  77                         tr0[c] = c + 1;                                 \
  78                 tr0[c] = 0;                                             \
  79                 for (c++; c < 256; c++)                                 \
  80                         tr0[c] = c;                                     \
  81                 endch = 0;                                              \
  82         } else {                                                        \
  83                 endch = tab[endch];                                     \
  84                 tr = tab;                                               \
  85                 if (endch != 0 && endch != 255) {                       \
  86                         errno = EINVAL;                                 \
  87                         return (-1);                                    \
  88                 }                                                       \
  89         }                                                               \
  90 }
  91
  92 int
  93 radixsort(const u_char **a, int n, const u_char *tab, u_int endch)
  94 {
  95         const u_char *tr;
  96         int c;
  97         u_char tr0[256];
  98
  99         SETUP;
 100         r_sort_a(a, n, 0, tr, endch);
 101         return (0);
 102 }
 103
 104 int
 105 sradixsort(const u_char **a, int n, const u_char *tab, u_int endch)
 106 {
 107         const u_char *tr, **ta;
 108         int c;
 109         u_char tr0[256];
 110
 111         SETUP;
 112         if (n < THRESHOLD)
 113                 simplesort(a, n, 0, tr, endch);
 114         else {
 115                 if ((ta = malloc(n * sizeof(a))) == NULL)
 116                         return (-1);
 117                 r_sort_b(a, ta, n, 0, tr, endch);
 118                 free(ta);
 119         }
 120         return (0);
 121 }
 122
 123 #define empty(s)        (s >= sp)
 124 #define pop(a, n, i)    a = (--sp)->sa, n = sp->sn, i = sp->si
 125 #define push(a, n, i)   sp->sa = a, sp->sn = n, (sp++)->si = i
 126 #define swap(a, b, t)   t = a, a = b, b = t
 127
 128 /* Unstable, in-place sort. */
 129 static void
 130 r_sort_a(const u_char **a, int n, int i, const u_char *tr, u_int endch)
 131 {
 132         static int count[256], nc, bmin;
 133         int c;
 134         const u_char **ak, *r;
 135         stack s[SIZE], *sp, *sp0, *sp1, temp;
 136         int *cp, bigc;
 137         const u_char **an, *t, **aj, **top[256];
 138
 139         /* Set up stack. */
 140         sp = s;
 141         push(a, n, i);
 142         while (!empty(s)) {
 143                 pop(a, n, i);
 144                 if (n < THRESHOLD) {
 145                         simplesort(a, n, i, tr, endch);
 146                         continue;
 147                 }
 148                 an = a + n;
 149
 150                 /* Make character histogram. */
 151                 if (nc == 0) {
 152                         bmin = 255;     /* First occupied bin, excluding eos. */
 153                         for (ak = a; ak < an;) {
 154                                 c = tr[(*ak++)[i]];
 155                                 if (++count[c] == 1 && c != endch) {
 156                                         if (c < bmin)
 157                                                 bmin = c;
 158                                         nc++;
 159                                 }
 160                         }
 161                         if (sp + nc > s + SIZE) {       /* Get more stack. */
 162                                 r_sort_a(a, n, i, tr, endch);
 163                                 continue;
 164                         }
 165                 }
 166
 167                 /*
 168                  * Special case: if all strings have the same
 169                  * character at position i, move on to the next
 170                  * character.
 171                  */
 172                 if (nc == 1 && count[bmin] == n) {
 173                         push(a, n, i+1);
 174                         nc = count[bmin] = 0;
 175                         continue;
 176                 }
 177
 178                 /*
 179                  * Set top[]; push incompletely sorted bins onto stack.
 180                  * top[] = pointers to last out-of-place element in bins.
 181                  * count[] = counts of elements in bins.
 182                  * Before permuting: top[c-1] + count[c] = top[c];
 183                  * during deal: top[c] counts down to top[c-1].
 184                  */
 185                 sp0 = sp1 = sp;         /* Stack position of biggest bin. */
 186                 bigc = 2;               /* Size of biggest bin. */
 187                 if (endch == 0)         /* Special case: set top[eos]. */
 188                         top[0] = ak = a + count[0];
 189                 else {
 190                         ak = a;
 191                         top[255] = an;
 192                 }
 193                 for (cp = count + bmin; nc > 0; cp++) {
 194                         while (*cp == 0)        /* Find next non-empty pile. */
 195                                 cp++;
 196                         if (*cp > 1) {
 197                                 if (*cp > bigc) {
 198                                         bigc = *cp;
 199                                         sp1 = sp;
 200                                 }
 201                                 push(ak, *cp, i+1);
 202                         }
 203                         top[cp-count] = ak += *cp;
 204                         nc--;
 205                 }
 206                 swap(*sp0, *sp1, temp); /* Play it safe -- biggest bin last. */
 207
 208                 /*
 209                  * Permute misplacements home.  Already home: everything
 210                  * before aj, and in bin[c], items from top[c] on.
 211                  * Inner loop:
 212                  *      r = next element to put in place;
 213                  *      ak = top[r[i]] = location to put the next element.
 214                  *      aj = bottom of 1st disordered bin.
 215                  * Outer loop:
 216                  *      Once the 1st disordered bin is done, ie. aj >= ak,
 217                  *      aj<-aj + count[c] connects the bins in a linked list;
 218                  *      reset count[c].
 219                  */
 220                 for (aj = a; aj < an;  *aj = r, aj += count[c], count[c] = 0)
 221                         for (r = *aj;  aj < (ak = --top[c = tr[r[i]]]);)
 222                                 swap(*ak, r, t);
 223         }
 224 }
 225
 226 /* Stable sort, requiring additional memory. */
 227 static void
 228 r_sort_b(const u_char **a, const u_char **ta, int n, int i, const u_char *tr,
 229     u_int endch)
 230 {
 231         static int count[256], nc, bmin;
 232         int c;
 233         const u_char **ak, **ai;
 234         stack s[512], *sp, *sp0, *sp1, temp;
 235         const u_char **top[256];
 236         int *cp, bigc;
 237
 238         sp = s;
 239         push(a, n, i);
 240         while (!empty(s)) {
 241                 pop(a, n, i);
 242                 if (n < THRESHOLD) {
 243                         simplesort(a, n, i, tr, endch);
 244                         continue;
 245                 }
 246
 247                 if (nc == 0) {
 248                         bmin = 255;
 249                         for (ak = a + n; --ak >= a;) {
 250                                 c = tr[(*ak)[i]];
 251                                 if (++count[c] == 1 && c != endch) {
 252                                         if (c < bmin)
 253                                                 bmin = c;
 254                                         nc++;
 255                                 }
 256                         }
 257                         if (sp + nc > s + SIZE) {
 258                                 r_sort_b(a, ta, n, i, tr, endch);
 259                                 continue;
 260                         }
 261                 }
 262
 263                 sp0 = sp1 = sp;
 264                 bigc = 2;
 265                 if (endch == 0) {
 266                         top[0] = ak = a + count[0];
 267                         count[0] = 0;
 268                 } else {
 269                         ak = a;
 270                         top[255] = a + n;
 271                         count[255] = 0;
 272                 }
 273                 for (cp = count + bmin; nc > 0; cp++) {
 274                         while (*cp == 0)
 275                                 cp++;
 276                         if ((c = *cp) > 1) {
 277                                 if (c > bigc) {
 278                                         bigc = c;
 279                                         sp1 = sp;
 280                                 }
 281                                 push(ak, c, i+1);
 282                         }
 283                         top[cp-count] = ak += c;
 284                         *cp = 0;                        /* Reset count[]. */
 285                         nc--;
 286                 }
 287                 swap(*sp0, *sp1, temp);
 288
 289                 for (ak = ta + n, ai = a+n; ak > ta;)   /* Copy to temp. */
 290                         *--ak = *--ai;
 291                 for (ak = ta+n; --ak >= ta;)            /* Deal to piles. */
 292                         *--top[tr[(*ak)[i]]] = *ak;
 293         }
 294 }
 295
 296 /* insertion sort */
 297 static inline void
 298 simplesort(const u_char **a, int n, int b, const u_char *tr, u_int endch)
 299 {
 300         u_char ch;
 301         const u_char  **ak, **ai, *s, *t;
 302
 303         for (ak = a+1; --n >= 1; ak++)
 304                 for (ai = ak; ai > a; ai--) {
 305                         for (s = ai[0] + b, t = ai[-1] + b;
 306                             (ch = tr[*s]) != endch; s++, t++)
 307                                 if (ch != tr[*t])
 308                                         break;
 309                         if (ch >= tr[*t])
 310                                 break;
 311                         swap(ai[0], ai[-1], s);
 312                 }
 313 }