diff options
Diffstat (limited to 'src/lib/libc/stdlib/merge.c')
-rw-r--r-- | src/lib/libc/stdlib/merge.c | 43 |
1 files changed, 14 insertions, 29 deletions
diff --git a/src/lib/libc/stdlib/merge.c b/src/lib/libc/stdlib/merge.c index 381fdc0830..623f652134 100644 --- a/src/lib/libc/stdlib/merge.c +++ b/src/lib/libc/stdlib/merge.c | |||
@@ -1,3 +1,4 @@ | |||
1 | /* $OpenBSD: merge.c,v 1.8 2005/08/08 08:05:37 espie Exp $ */ | ||
1 | /*- | 2 | /*- |
2 | * Copyright (c) 1992, 1993 | 3 | * Copyright (c) 1992, 1993 |
3 | * The Regents of the University of California. All rights reserved. | 4 | * The Regents of the University of California. All rights reserved. |
@@ -13,11 +14,7 @@ | |||
13 | * 2. Redistributions in binary form must reproduce the above copyright | 14 | * 2. Redistributions in binary form must reproduce the above copyright |
14 | * notice, this list of conditions and the following disclaimer in the | 15 | * notice, this list of conditions and the following disclaimer in the |
15 | * documentation and/or other materials provided with the distribution. | 16 | * documentation and/or other materials provided with the distribution. |
16 | * 3. All advertising materials mentioning features or use of this software | 17 | * 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 | 18 | * may be used to endorse or promote products derived from this software |
22 | * without specific prior written permission. | 19 | * without specific prior written permission. |
23 | * | 20 | * |
@@ -34,11 +31,6 @@ | |||
34 | * SUCH DAMAGE. | 31 | * SUCH DAMAGE. |
35 | */ | 32 | */ |
36 | 33 | ||
37 | #if defined(LIBC_SCCS) && !defined(lint) | ||
38 | /*static char sccsid[] = "from: @(#)merge.c 8.2 (Berkeley) 2/14/94";*/ | ||
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 */ | ||
41 | |||
42 | /* | 34 | /* |
43 | * Hybrid exponential search/linear search merge sort with hybrid | 35 | * Hybrid exponential search/linear search merge sort with hybrid |
44 | * natural/pairwise first pass. Requires about .3% more comparisons | 36 | * natural/pairwise first pass. Requires about .3% more comparisons |
@@ -59,8 +51,8 @@ static char *rcsid = "$Id: merge.c,v 1.1.1.1 1995/10/18 08:42:18 deraadt Exp $"; | |||
59 | #include <stdlib.h> | 51 | #include <stdlib.h> |
60 | #include <string.h> | 52 | #include <string.h> |
61 | 53 | ||
62 | static void setup __P((u_char *, u_char *, size_t, size_t, int (*)())); | 54 | static void setup(u_char *, u_char *, size_t, size_t, int (*)()); |
63 | static void insertionsort __P((u_char *, size_t, size_t, int (*)())); | 55 | static void insertionsort(u_char *, size_t, size_t, int (*)()); |
64 | 56 | ||
65 | #define ISIZE sizeof(int) | 57 | #define ISIZE sizeof(int) |
66 | #define PSIZE sizeof(u_char *) | 58 | #define PSIZE sizeof(u_char *) |
@@ -96,15 +88,12 @@ static void insertionsort __P((u_char *, size_t, size_t, int (*)())); | |||
96 | * Arguments are as for qsort. | 88 | * Arguments are as for qsort. |
97 | */ | 89 | */ |
98 | int | 90 | int |
99 | mergesort(base, nmemb, size, cmp) | 91 | mergesort(void *base, size_t nmemb, size_t size, |
100 | void *base; | 92 | int (*cmp)(const void *, const void *)) |
101 | size_t nmemb; | ||
102 | register size_t size; | ||
103 | int (*cmp) __P((const void *, const void *)); | ||
104 | { | 93 | { |
105 | register int i, sense; | 94 | int i, sense; |
106 | int big, iflag; | 95 | int big, iflag; |
107 | register u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2; | 96 | u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2; |
108 | u_char *list2, *list1, *p2, *p, *last, **p1; | 97 | u_char *list2, *list1, *p2, *p, *last, **p1; |
109 | 98 | ||
110 | if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */ | 99 | if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */ |
@@ -148,7 +137,7 @@ mergesort(base, nmemb, size, cmp) | |||
148 | sense = 0; | 137 | sense = 0; |
149 | } | 138 | } |
150 | if (!big) { /* here i = 0 */ | 139 | if (!big) { /* here i = 0 */ |
151 | LINEAR: while ((b += size) < t && cmp(q, b) >sense) | 140 | while ((b += size) < t && cmp(q, b) >sense) |
152 | if (++i == 6) { | 141 | if (++i == 6) { |
153 | big = 1; | 142 | big = 1; |
154 | goto EXPONENTIAL; | 143 | goto EXPONENTIAL; |
@@ -169,7 +158,7 @@ EXPONENTIAL: for (i = size; ; i <<= 1) | |||
169 | goto FASTCASE; | 158 | goto FASTCASE; |
170 | } else | 159 | } else |
171 | b = p; | 160 | b = p; |
172 | SLOWCASE: while (t > b+size) { | 161 | while (t > b+size) { |
173 | i = (((t - b) / size) >> 1) * size; | 162 | i = (((t - b) / size) >> 1) * size; |
174 | if ((*cmp)(q, p = b + i) <= sense) | 163 | if ((*cmp)(q, p = b + i) <= sense) |
175 | t = p; | 164 | t = p; |
@@ -256,10 +245,8 @@ COPY: b = t; | |||
256 | * is defined. Otherwise simple pairwise merging is used.) | 245 | * is defined. Otherwise simple pairwise merging is used.) |
257 | */ | 246 | */ |
258 | void | 247 | void |
259 | setup(list1, list2, n, size, cmp) | 248 | setup(u_char *list1, u_char *list2, size_t n, size_t size, |
260 | size_t n, size; | 249 | int (*cmp)(const void *, const void *)) |
261 | int (*cmp) __P((const void *, const void *)); | ||
262 | u_char *list1, *list2; | ||
263 | { | 250 | { |
264 | int i, length, size2, tmp, sense; | 251 | int i, length, size2, tmp, sense; |
265 | u_char *f1, *f2, *s, *l2, *last, *p2; | 252 | u_char *f1, *f2, *s, *l2, *last, *p2; |
@@ -330,10 +317,8 @@ setup(list1, list2, n, size, cmp) | |||
330 | * last 4 elements. | 317 | * last 4 elements. |
331 | */ | 318 | */ |
332 | static void | 319 | static void |
333 | insertionsort(a, n, size, cmp) | 320 | insertionsort(u_char *a, size_t n, size_t size, |
334 | u_char *a; | 321 | int (*cmp)(const void *, const void *)) |
335 | size_t n, size; | ||
336 | int (*cmp) __P((const void *, const void *)); | ||
337 | { | 322 | { |
338 | u_char *ai, *s, *t, *u, tmp; | 323 | u_char *ai, *s, *t, *u, tmp; |
339 | int i; | 324 | int i; |