summaryrefslogtreecommitdiff
path: root/src/lib/libc/stdlib/radixsort.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libc/stdlib/radixsort.c')
-rw-r--r--src/lib/libc/stdlib/radixsort.c61
1 files changed, 20 insertions, 41 deletions
diff --git a/src/lib/libc/stdlib/radixsort.c b/src/lib/libc/stdlib/radixsort.c
index dd51013c94..96392ea73a 100644
--- a/src/lib/libc/stdlib/radixsort.c
+++ b/src/lib/libc/stdlib/radixsort.c
@@ -13,11 +13,7 @@
13 * 2. Redistributions in binary form must reproduce the above copyright 13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the 14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution. 15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software 16 * 3. Neither the name of the University nor the names of its contributors
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 17 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission. 18 * without specific prior written permission.
23 * 19 *
@@ -35,8 +31,7 @@
35 */ 31 */
36 32
37#if defined(LIBC_SCCS) && !defined(lint) 33#if defined(LIBC_SCCS) && !defined(lint)
38/*static char sccsid[] = "from: @(#)radixsort.c 8.1 (Berkeley) 6/4/93";*/ 34static char *rcsid = "$OpenBSD: radixsort.c,v 1.7 2005/03/30 18:51:49 pat Exp $";
39static char *rcsid = "$Id: radixsort.c,v 1.1.1.1 1995/10/18 08:42:19 deraadt Exp $";
40#endif /* LIBC_SCCS and not lint */ 35#endif /* LIBC_SCCS and not lint */
41 36
42/* 37/*
@@ -61,11 +56,11 @@ typedef struct {
61 int sn, si; 56 int sn, si;
62} stack; 57} stack;
63 58
64static inline void simplesort 59static __inline void simplesort
65 __P((const u_char **, int, int, const u_char *, u_int)); 60(const u_char **, int, int, const u_char *, u_int);
66static void r_sort_a __P((const u_char **, int, int, const u_char *, u_int)); 61static void r_sort_a(const u_char **, int, int, const u_char *, u_int);
67static void r_sort_b __P((const u_char **, 62static void r_sort_b(const u_char **,
68 const u_char **, int, int, const u_char *, u_int)); 63 const u_char **, int, int, const u_char *, u_int);
69 64
70#define THRESHOLD 20 /* Divert to simplesort(). */ 65#define THRESHOLD 20 /* Divert to simplesort(). */
71#define SIZE 512 /* Default stack size. */ 66#define SIZE 512 /* Default stack size. */
@@ -90,10 +85,7 @@ static void r_sort_b __P((const u_char **,
90} 85}
91 86
92int 87int
93radixsort(a, n, tab, endch) 88radixsort(const u_char **a, int n, const u_char *tab, u_int endch)
94 const u_char **a, *tab;
95 int n;
96 u_int endch;
97{ 89{
98 const u_char *tr; 90 const u_char *tr;
99 int c; 91 int c;
@@ -105,10 +97,7 @@ radixsort(a, n, tab, endch)
105} 97}
106 98
107int 99int
108sradixsort(a, n, tab, endch) 100sradixsort(const u_char **a, int n, const u_char *tab, u_int endch)
109 const u_char **a, *tab;
110 int n;
111 u_int endch;
112{ 101{
113 const u_char *tr, **ta; 102 const u_char *tr, **ta;
114 int c; 103 int c;
@@ -133,15 +122,11 @@ sradixsort(a, n, tab, endch)
133 122
134/* Unstable, in-place sort. */ 123/* Unstable, in-place sort. */
135void 124void
136r_sort_a(a, n, i, tr, endch) 125r_sort_a(const u_char **a, int n, int i, const u_char *tr, u_int endch)
137 const u_char **a;
138 int n, i;
139 const u_char *tr;
140 u_int endch;
141{ 126{
142 static int count[256], nc, bmin; 127 static int count[256], nc, bmin;
143 register int c; 128 int c;
144 register const u_char **ak, *r; 129 const u_char **ak, *r;
145 stack s[SIZE], *sp, *sp0, *sp1, temp; 130 stack s[SIZE], *sp, *sp0, *sp1, temp;
146 int *cp, bigc; 131 int *cp, bigc;
147 const u_char **an, *t, **aj, **top[256]; 132 const u_char **an, *t, **aj, **top[256];
@@ -224,15 +209,12 @@ r_sort_a(a, n, i, tr, endch)
224 209
225/* Stable sort, requiring additional memory. */ 210/* Stable sort, requiring additional memory. */
226void 211void
227r_sort_b(a, ta, n, i, tr, endch) 212r_sort_b(const u_char **a, const u_char **ta, int n, int i, const u_char *tr,
228 const u_char **a, **ta; 213 u_int endch)
229 int n, i;
230 const u_char *tr;
231 u_int endch;
232{ 214{
233 static int count[256], nc, bmin; 215 static int count[256], nc, bmin;
234 register int c; 216 int c;
235 register const u_char **ak, **ai; 217 const u_char **ak, **ai;
236 stack s[512], *sp, *sp0, *sp1, temp; 218 stack s[512], *sp, *sp0, *sp1, temp;
237 const u_char **top[256]; 219 const u_char **top[256];
238 int *cp, bigc; 220 int *cp, bigc;
@@ -295,14 +277,11 @@ r_sort_b(a, ta, n, i, tr, endch)
295 } 277 }
296} 278}
297 279
298static inline void 280static __inline void
299simplesort(a, n, b, tr, endch) /* insertion sort */ 281simplesort(const u_char **a, int n, int b, const u_char *tr, u_int endch)
300 register const u_char **a; 282 /* insertion sort */
301 int n, b;
302 register const u_char *tr;
303 u_int endch;
304{ 283{
305 register u_char ch; 284 u_char ch;
306 const u_char **ak, **ai, *s, *t; 285 const u_char **ak, **ai, *s, *t;
307 286
308 for (ak = a+1; --n >= 1; ak++) 287 for (ak = a+1; --n >= 1; ak++)