Libc-825.40.1.tar.gz

[apple/libc.git] / stdlib / FreeBSD / radixsort.c

diff --git a/stdlib/FreeBSD/radixsort.c b/stdlib/FreeBSD/radixsort.c
index 7f149669df1907e4941b2142ee41d35b7cd0c98b..5208ce91ea969d47a7408c5b1562c7e4bfcf2728 100644 (file)
--- a/stdlib/FreeBSD/radixsort.c
+++ b/stdlib/FreeBSD/radixsort.c
@@ -13,10 +13,6 @@
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.

- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *     This product includes software developed by the University of
- *     California, Berkeley and its contributors.

  * 4. Neither the name of the University nor the names of its contributors
  *    may be used to endorse or promote products derived from this software
  *    without specific prior written permission.
  * 4. Neither the name of the University nor the names of its contributors
  *    may be used to endorse or promote products derived from this software
  *    without specific prior written permission.


@@ -38,7 +34,7 @@
 static char sccsid[] = "@(#)radixsort.c        8.2 (Berkeley) 4/28/95";
 #endif /* LIBC_SCCS and not lint */
 #include <sys/cdefs.h>
 static char sccsid[] = "@(#)radixsort.c        8.2 (Berkeley) 4/28/95";
 #endif /* LIBC_SCCS and not lint */
 #include <sys/cdefs.h>

-__FBSDID("$FreeBSD: src/lib/libc/stdlib/radixsort.c,v 1.6 2002/03/22 09:18:34 obrien Exp $");
+__FBSDID("$FreeBSD: src/lib/libc/stdlib/radixsort.c,v 1.8 2007/01/09 00:28:10 imp Exp $");

 
 /*
  * Radixsort routines.
 
 /*
  * Radixsort routines.


@@ -57,6 +53,7 @@ __FBSDID("$FreeBSD: src/lib/libc/stdlib/radixsort.c,v 1.6 2002/03/22 09:18:34 ob
 #include <stdlib.h>
 #include <stddef.h>
 #include <errno.h>
 #include <stdlib.h>
 #include <stddef.h>
 #include <errno.h>

+#include <pthread.h>

 
 typedef struct {
        const u_char **sa;
 
 typedef struct {
        const u_char **sa;


@@ -64,11 +61,17 @@ typedef struct {
 } stack;
 
 static inline void simplesort
 } stack;
 
 static inline void simplesort

-(const u_char **, int, int, const u_char *, u_int);
+(const u_char **, int, int, const u_char *, u_int) __attribute__((always_inline));

 static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
 static void r_sort_b(const u_char **, const u_char **, int, int,
     const u_char *, u_int);
 
 static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
 static void r_sort_b(const u_char **, const u_char **, int, int,
     const u_char *, u_int);
 

+static int *r_sort_a_count;
+static int *r_sort_b_count;
+
+static void r_sort_count_allocate(void);
+static pthread_once_t r_sort_count_control = PTHREAD_ONCE_INIT;
+

 #define        THRESHOLD       20              /* Divert to simplesort(). */
 #define        SIZE            512             /* Default stack size. */
 
 #define        THRESHOLD       20              /* Divert to simplesort(). */
 #define        SIZE            512             /* Default stack size. */
 


@@ -128,6 +131,12 @@ sradixsort(a, n, tab, endch)
        return (0);
 }
 
        return (0);
 }
 

+static void r_sort_count_allocate(void)
+{
+       r_sort_a_count = calloc(256, sizeof(int));
+       r_sort_b_count = calloc(256, sizeof(int));
+}
+

 #define empty(s)       (s >= sp)
 #define pop(a, n, i)   a = (--sp)->sa, n = sp->sn, i = sp->si
 #define push(a, n, i)  sp->sa = a, sp->sn = n, (sp++)->si = i
 #define empty(s)       (s >= sp)
 #define pop(a, n, i)   a = (--sp)->sa, n = sp->sn, i = sp->si
 #define push(a, n, i)  sp->sa = a, sp->sn = n, (sp++)->si = i


@@ -141,13 +150,19 @@ r_sort_a(a, n, i, tr, endch)
        const u_char *tr;
        u_int endch;
 {
        const u_char *tr;
        u_int endch;
 {

-       static int count[256], nc, bmin;
+       static int *count, nc, bmin;

        int c;
        const u_char **ak, *r;
        stack s[SIZE], *sp, *sp0, *sp1, temp;
        int *cp, bigc;
        const u_char **an, *t, **aj, **top[256];
 
        int c;
        const u_char **ak, *r;
        stack s[SIZE], *sp, *sp0, *sp1, temp;
        int *cp, bigc;
        const u_char **an, *t, **aj, **top[256];
 

+       if (pthread_once(&r_sort_count_control, r_sort_count_allocate)) {
+               return;
+       }
+
+       count = r_sort_a_count;
+

        /* Set up stack. */
        sp = s;
        push(a, n, i);
        /* Set up stack. */
        sp = s;
        push(a, n, i);


@@ -176,6 +191,17 @@ r_sort_a(a, n, i, tr, endch)
                        }
                }
 
                        }
                }
 

+               /*
+                * Special case: if all strings have the same
+                * character at position i, move on to the next
+                * character.
+                */
+               if (nc == 1 && count[bmin] == n) {
+                       push(a, n, i+1);
+                       nc = count[bmin] = 0;
+                       continue;
+               }
+

                /*
                 * Set top[]; push incompletely sorted bins onto stack.
                 * top[] = pointers to last out-of-place element in bins.
                /*
                 * Set top[]; push incompletely sorted bins onto stack.
                 * top[] = pointers to last out-of-place element in bins.


@@ -232,13 +258,19 @@ r_sort_b(a, ta, n, i, tr, endch)
        const u_char *tr;
        u_int endch;
 {
        const u_char *tr;
        u_int endch;
 {

-       static int count[256], nc, bmin;
+       static int *count, nc, bmin;

        int c;
        const u_char **ak, **ai;
        stack s[512], *sp, *sp0, *sp1, temp;
        const u_char **top[256];
        int *cp, bigc;
 
        int c;
        const u_char **ak, **ai;
        stack s[512], *sp, *sp0, *sp1, temp;
        const u_char **top[256];
        int *cp, bigc;
 

+       if (pthread_once(&r_sort_count_control, r_sort_count_allocate)) {
+               return;
+       }
+
+       count = r_sort_b_count;
+

        sp = s;
        push(a, n, i);
        while (!empty(s)) {
        sp = s;
        push(a, n, i);
        while (!empty(s)) {