summaryrefslogtreecommitdiff
path: root/src/lib/libc/stdlib/merge.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libc/stdlib/merge.c')
-rw-r--r--src/lib/libc/stdlib/merge.c40
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";*/ 34static char *rcsid = "$OpenBSD: merge.c,v 1.7 2005/03/30 18:51:49 pat Exp $";
39static 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
62static void setup __P((u_char *, u_char *, size_t, size_t, int (*)())); 57static void setup(u_char *, u_char *, size_t, size_t, int (*)());
63static void insertionsort __P((u_char *, size_t, size_t, int (*)())); 58static 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 */
98int 93int
99mergesort(base, nmemb, size, cmp) 94mergesort(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 */
151LINEAR: 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;
172SLOWCASE: 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 */
258void 250void
259setup(list1, list2, n, size, cmp) 251setup(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 */
332static void 322static void
333insertionsort(a, n, size, cmp) 323insertionsort(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;