diff options
Diffstat (limited to 'src/lib/libc/stdlib/merge.c')
| -rw-r--r-- | src/lib/libc/stdlib/merge.c | 40 | 
1 files changed, 14 insertions, 26 deletions
| diff --git a/src/lib/libc/stdlib/merge.c b/src/lib/libc/stdlib/merge.c index 381fdc0830..b193ae345c 100644 --- a/src/lib/libc/stdlib/merge.c +++ b/src/lib/libc/stdlib/merge.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: @(#)merge.c 8.2 (Berkeley) 2/14/94";*/ | 34 | static char *rcsid = "$OpenBSD: merge.c,v 1.7 2005/03/30 18:51:49 pat Exp $"; | 
| 39 | static char *rcsid = "$Id: merge.c,v 1.1.1.1 1995/10/18 08:42:18 deraadt Exp $"; | ||
| 40 | #endif /* LIBC_SCCS and not lint */ | 35 | #endif /* LIBC_SCCS and not lint */ | 
| 41 | 36 | ||
| 42 | /* | 37 | /* | 
| @@ -59,8 +54,8 @@ static char *rcsid = "$Id: merge.c,v 1.1.1.1 1995/10/18 08:42:18 deraadt Exp $"; | |||
| 59 | #include <stdlib.h> | 54 | #include <stdlib.h> | 
| 60 | #include <string.h> | 55 | #include <string.h> | 
| 61 | 56 | ||
| 62 | static void setup __P((u_char *, u_char *, size_t, size_t, int (*)())); | 57 | static void setup(u_char *, u_char *, size_t, size_t, int (*)()); | 
| 63 | static void insertionsort __P((u_char *, size_t, size_t, int (*)())); | 58 | static void insertionsort(u_char *, size_t, size_t, int (*)()); | 
| 64 | 59 | ||
| 65 | #define ISIZE sizeof(int) | 60 | #define ISIZE sizeof(int) | 
| 66 | #define PSIZE sizeof(u_char *) | 61 | #define PSIZE sizeof(u_char *) | 
| @@ -96,15 +91,12 @@ static void insertionsort __P((u_char *, size_t, size_t, int (*)())); | |||
| 96 | * Arguments are as for qsort. | 91 | * Arguments are as for qsort. | 
| 97 | */ | 92 | */ | 
| 98 | int | 93 | int | 
| 99 | mergesort(base, nmemb, size, cmp) | 94 | mergesort(void *base, size_t nmemb, size_t size, | 
| 100 | void *base; | 95 | int (*cmp)(const void *, const void *)) | 
| 101 | size_t nmemb; | ||
| 102 | register size_t size; | ||
| 103 | int (*cmp) __P((const void *, const void *)); | ||
| 104 | { | 96 | { | 
| 105 | register int i, sense; | 97 | int i, sense; | 
| 106 | int big, iflag; | 98 | int big, iflag; | 
| 107 | register u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2; | 99 | u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2; | 
| 108 | u_char *list2, *list1, *p2, *p, *last, **p1; | 100 | u_char *list2, *list1, *p2, *p, *last, **p1; | 
| 109 | 101 | ||
| 110 | if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */ | 102 | if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */ | 
| @@ -148,7 +140,7 @@ mergesort(base, nmemb, size, cmp) | |||
| 148 | sense = 0; | 140 | sense = 0; | 
| 149 | } | 141 | } | 
| 150 | if (!big) { /* here i = 0 */ | 142 | if (!big) { /* here i = 0 */ | 
| 151 | LINEAR: while ((b += size) < t && cmp(q, b) >sense) | 143 | while ((b += size) < t && cmp(q, b) >sense) | 
| 152 | if (++i == 6) { | 144 | if (++i == 6) { | 
| 153 | big = 1; | 145 | big = 1; | 
| 154 | goto EXPONENTIAL; | 146 | goto EXPONENTIAL; | 
| @@ -169,7 +161,7 @@ EXPONENTIAL: for (i = size; ; i <<= 1) | |||
| 169 | goto FASTCASE; | 161 | goto FASTCASE; | 
| 170 | } else | 162 | } else | 
| 171 | b = p; | 163 | b = p; | 
| 172 | SLOWCASE: while (t > b+size) { | 164 | while (t > b+size) { | 
| 173 | i = (((t - b) / size) >> 1) * size; | 165 | i = (((t - b) / size) >> 1) * size; | 
| 174 | if ((*cmp)(q, p = b + i) <= sense) | 166 | if ((*cmp)(q, p = b + i) <= sense) | 
| 175 | t = p; | 167 | t = p; | 
| @@ -256,10 +248,8 @@ COPY: b = t; | |||
| 256 | * is defined. Otherwise simple pairwise merging is used.) | 248 | * is defined. Otherwise simple pairwise merging is used.) | 
| 257 | */ | 249 | */ | 
| 258 | void | 250 | void | 
| 259 | setup(list1, list2, n, size, cmp) | 251 | setup(u_char *list1, u_char *list2, size_t n, size_t size, | 
| 260 | size_t n, size; | 252 | int (*cmp)(const void *, const void *)) | 
| 261 | int (*cmp) __P((const void *, const void *)); | ||
| 262 | u_char *list1, *list2; | ||
| 263 | { | 253 | { | 
| 264 | int i, length, size2, tmp, sense; | 254 | int i, length, size2, tmp, sense; | 
| 265 | u_char *f1, *f2, *s, *l2, *last, *p2; | 255 | u_char *f1, *f2, *s, *l2, *last, *p2; | 
| @@ -330,10 +320,8 @@ setup(list1, list2, n, size, cmp) | |||
| 330 | * last 4 elements. | 320 | * last 4 elements. | 
| 331 | */ | 321 | */ | 
| 332 | static void | 322 | static void | 
| 333 | insertionsort(a, n, size, cmp) | 323 | insertionsort(u_char *a, size_t n, size_t size, | 
| 334 | u_char *a; | 324 | int (*cmp)(const void *, const void *)) | 
| 335 | size_t n, size; | ||
| 336 | int (*cmp) __P((const void *, const void *)); | ||
| 337 | { | 325 | { | 
| 338 | u_char *ai, *s, *t, *u, tmp; | 326 | u_char *ai, *s, *t, *u, tmp; | 
| 339 | int i; | 327 | int i; | 
