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.c43
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";*/
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 */
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
62static void setup __P((u_char *, u_char *, size_t, size_t, int (*)())); 54static void setup(u_char *, u_char *, size_t, size_t, int (*)());
63static void insertionsort __P((u_char *, size_t, size_t, int (*)())); 55static 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 */
98int 90int
99mergesort(base, nmemb, size, cmp) 91mergesort(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 */
151LINEAR: 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;
172SLOWCASE: 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 */
258void 247void
259setup(list1, list2, n, size, cmp) 248setup(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 */
332static void 319static void
333insertionsort(a, n, size, cmp) 320insertionsort(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;