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