1 /* $NetBSD: merge.c,v 1.14 2012/03/13 21:13:48 christos Exp $ */
4 * Copyright (c) 1992, 1993
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from software contributed to Berkeley by
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 #include <sys/cdefs.h>
36 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid
[] = "from: @(#)merge.c 8.2 (Berkeley) 2/14/94";
40 __RCSID("$NetBSD: merge.c,v 1.14 2012/03/13 21:13:48 christos Exp $");
42 #endif /* LIBC_SCCS and not lint */
45 * Hybrid exponential search/linear search merge sort with hybrid
46 * natural/pairwise first pass. Requires about .3% more comparisons
47 * for random data than LSMS with pairwise first pass alone.
48 * It works for objects as small as two bytes.
52 #define THRESHOLD 16 /* Best choice for natural merge cut-off. */
54 /* #define NATURAL to get hybrid natural merge.
55 * (The default is pairwise merging.)
58 #include "namespace.h"
59 #include <sys/types.h>
67 __weak_alias(mergesort
,_mergesort
)
70 static void setup(u_char
*, u_char
*, size_t, size_t,
71 int (*)(const void *, const void *));
72 static void insertionsort(u_char
*, size_t, size_t,
73 int (*)(const void *, const void *));
75 #define ISIZE sizeof(int)
76 #define PSIZE sizeof(u_char *)
77 #define ICOPY_LIST(src, dst, last) \
79 *(int*)(void *)dst = *(int*)(void *)src, \
80 src += ISIZE, dst += ISIZE; \
82 #define ICOPY_ELT(src, dst, i) \
84 *(int*)(void *)dst = *(int*)(void *)src, \
85 src += ISIZE, dst += ISIZE; \
88 #define CCOPY_LIST(src, dst, last) \
92 #define CCOPY_ELT(src, dst, i) \
98 * Find the next possible pointer head. (Trickery for forcing an array
99 * to do double duty as a linked list when objects do not align with word
102 /* Assumption: PSIZE is a power of 2. */
103 #define EVAL(p) ((u_char **)(void *) \
105 (((u_char *)(void *)(p) + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1))))
108 * Arguments are as for qsort.
111 mergesort(void *base
, size_t nmemb
, size_t size
,
112 int (*cmp
)(const void *, const void *))
117 u_char
*f1
, *f2
, *t
, *b
, *tp2
, *q
, *l1
, *l2
;
118 u_char
*list2
, *list1
, *p2
, *p
, *last
, **p1
;
120 _DIAGASSERT(base
!= NULL
);
121 _DIAGASSERT(cmp
!= NULL
);
123 if (size
< PSIZE
/ 2) { /* Pointers must fit into 2 * size. */
130 * Stupid subtraction for the Cray.
133 if (!(size
% ISIZE
) && !(((char *)base
- (char *)0) % ISIZE
))
136 if ((list2
= malloc(nmemb
* size
+ PSIZE
)) == NULL
)
140 setup(list1
, list2
, nmemb
, size
, cmp
);
141 last
= list2
+ nmemb
* size
;
143 while (*EVAL(list2
) != last
) {
146 for (tp2
= p2
= list2
; p2
!= last
; p1
= EVAL(l2
)) {
149 f2
= l1
= list1
+ (p2
- list2
);
152 l2
= list1
+ (p2
- list2
);
153 while (f1
< l1
&& f2
< l2
) {
154 if ((*cmp
)(f1
, f2
) <= 0) {
163 if (!big
) { /* here i = 0 */
167 while ((b
+= size
) < t
&& cmp(q
, b
) >sense
)
173 EXPONENTIAL
: for (i
= size
; ; i
<<= 1)
174 if ((p
= (b
+ i
)) >= t
) {
175 if ((p
= t
- size
) > b
&&
176 (*cmp
)(q
, p
) <= sense
)
181 } else if ((*cmp
)(q
, p
) <= sense
) {
192 i
= (((t
- b
) / size
) >> 1) * size
;
193 if ((*cmp
)(q
, p
= b
+ i
) <= sense
)
199 FASTCASE
: while (i
> size
)
202 (i
= (unsigned int) i
>> 1)) <= sense
)
211 ICOPY_LIST(f2
, tp2
, b
);
212 ICOPY_ELT(f1
, tp2
, i
);
214 CCOPY_LIST(f2
, tp2
, b
);
215 CCOPY_ELT(f1
, tp2
, i
);
219 ICOPY_LIST(f1
, tp2
, b
);
220 ICOPY_ELT(f2
, tp2
, i
);
222 CCOPY_LIST(f1
, tp2
, b
);
223 CCOPY_ELT(f2
, tp2
, i
);
229 ICOPY_LIST(f2
, tp2
, l2
);
231 CCOPY_LIST(f2
, tp2
, l2
);
232 } else if (f1
< l1
) {
234 ICOPY_LIST(f1
, tp2
, l1
);
236 CCOPY_LIST(f1
, tp2
, l1
);
240 tp2
= list1
; /* swap list1, list2 */
243 last
= list2
+ nmemb
*size
;
246 memmove(list2
, list1
, nmemb
*size
);
253 #define swap(a, b) { \
257 tmp = *a; *a++ = *s; *s++ = tmp; \
261 #define reverse(bot, top) { \
266 tmp = *bot; *bot++ = *s; *s++ = tmp; \
273 * Optional hybrid natural/pairwise first pass. Eats up list1 in runs of
274 * increasing order, list2 in a corresponding linked list. Checks for runs
275 * when THRESHOLD/2 pairs compare with same sense. (Only used when NATURAL
276 * is defined. Otherwise simple pairwise merging is used.)
279 /* XXX: shouldn't this function be static? - lukem 990810 */
281 setup(u_char
*list1
, u_char
*list2
, size_t n
, size_t size
,
282 int (*cmp
)(const void *, const void *))
284 int length
, tmp
, sense
;
285 u_char
*f1
, *f2
, *s
, *l2
, *last
, *p2
;
288 _DIAGASSERT(cmp
!= NULL
);
289 _DIAGASSERT(list1
!= NULL
);
290 _DIAGASSERT(list2
!= NULL
);
294 insertionsort(list1
, n
, size
, cmp
);
295 *EVAL(list2
) = list2
+ n
*size
;
299 * Avoid running pointers out of bounds; limit n to evens
303 insertionsort(list1
+ (n
- i
) * size
, i
, size
, cmp
);
304 last
= list1
+ size
* (n
- i
);
305 *EVAL(list2
+ (last
- list1
)) = list2
+ n
* size
;
310 sense
= (cmp(f1
, f1
+ size
) > 0);
311 for (; f1
< last
; sense
= !sense
) {
313 /* Find pairs with same sense. */
314 for (f2
= f1
+ size2
; f2
< last
; f2
+= size2
) {
315 if ((cmp(f2
, f2
+ size
) > 0) != sense
)
319 if (length
< THRESHOLD
) { /* Pairwise merge */
321 p2
= *EVAL(p2
) = f1
+ size2
- list1
+ list2
;
323 swap (f1
, f1
+ size
);
324 } while ((f1
+= size2
) < f2
);
325 } else { /* Natural merge */
327 for (f2
= f1
+ size2
; f2
< l2
; f2
+= size2
) {
328 if ((cmp(f2
-size
, f2
) > 0) != sense
) {
329 p2
= *EVAL(p2
) = f2
- list1
+ list2
;
331 reverse(f1
, f2
- size
);
336 reverse(f1
, f2
- size
);
338 if (f2
< last
|| cmp(f2
- size
, f2
) > 0)
339 p2
= *EVAL(p2
) = f2
- list1
+ list2
;
341 p2
= *EVAL(p2
) = list2
+ n
*size
;
344 #else /* pairwise merge only. */
345 for (f1
= list1
, p2
= list2
; f1
< last
; f1
+= size2
) {
346 p2
= *EVAL(p2
) = p2
+ size2
;
347 if (cmp (f1
, f1
+ size
) > 0)
354 * This is to avoid out-of-bounds addresses in sorting the
358 insertionsort(u_char
*a
, size_t n
, size_t size
,
359 int (*cmp
)(const void *, const void *))
361 u_char
*ai
, *s
, *t
, *u
, tmp
;
364 _DIAGASSERT(a
!= NULL
);
365 _DIAGASSERT(cmp
!= NULL
);
367 for (ai
= a
+size
; --n
>= 1; ai
+= size
)
368 for (t
= ai
; t
> a
; t
-= size
) {