stdlib/radixsort.c

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