Home | History | Annotate | Line # | Download | only in stdlib 
      1 /*	$NetBSD: merge.c,v 1.17 2025/03/02 16:35:41 riastradh Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 1992, 1993
      5  *	The Regents of the University of California.  All rights reserved.
      6  *
      7  * This code is derived from software contributed to Berkeley by
      8  * Peter McIlroy.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted provided that the following conditions
     12  * are met:
     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.
     21  *
     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
     32  * SUCH DAMAGE.
     33  */
     34 
     35 #include <sys/cdefs.h>
     36 #if defined(LIBC_SCCS) && !defined(lint)
     37 #if 0
     38 static char sccsid[] = "from: @(#)merge.c	8.2 (Berkeley) 2/14/94";
     39 #else
     40 __RCSID("$NetBSD: merge.c,v 1.17 2025/03/02 16:35:41 riastradh Exp $");
     41 #endif
     42 #endif /* LIBC_SCCS and not lint */
     43 
     44 /*
     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.
     49  */
     50 
     51 #define NATURAL
     52 #define THRESHOLD 16	/* Best choice for natural merge cut-off. */
     53 
     54 /* #define NATURAL to get hybrid natural merge.
     55  * (The default is pairwise merging.)
     56  */
     57 
     58 #include "namespace.h"
     59 #include <sys/types.h>
     60 
     61 #include <assert.h>
     62 #include <errno.h>
     63 #include <stdlib.h>
     64 #include <string.h>
     65 
     66 #ifdef __weak_alias
     67 __weak_alias(mergesort,_mergesort)
     68 __weak_alias(mergesort_r,_mergesort_r)
     69 #endif
     70 
     71 static void setup(u_char *, u_char *, size_t, size_t,
     72     int (*)(const void *, const void *, void *), void *);
     73 static void insertionsort(u_char *, size_t, size_t,
     74     int (*)(const void *, const void *, void *), void *);
     75 
     76 #define ISIZE sizeof(int)
     77 #define PSIZE sizeof(u_char *)
     78 #define ICOPY_LIST(src, dst, last)				\
     79 	do							\
     80 	*(int*)(void *)dst = *(int*)(void *)src,		\
     81 		src += ISIZE, dst += ISIZE;			\
     82 	while(src < last)
     83 #define ICOPY_ELT(src, dst, i)					\
     84 	do							\
     85 	*(int*)(void *)dst = *(int*)(void *)src,		\
     86 	src += ISIZE, dst += ISIZE;				\
     87 	while (i -= ISIZE)
     88 
     89 #define CCOPY_LIST(src, dst, last)		\
     90 	do					\
     91 		*dst++ = *src++;		\
     92 	while (src < last)
     93 #define CCOPY_ELT(src, dst, i)			\
     94 	do					\
     95 		*dst++ = *src++;		\
     96 	while (i -= 1)
     97 
     98 /*
     99  * Find the next possible pointer head.  (Trickery for forcing an array
    100  * to do double duty as a linked list when objects do not align with word
    101  * boundaries.
    102  */
    103 /* Assumption: PSIZE is a power of 2. */
    104 #define EVAL(p) ((u_char **)(void *)					\
    105     (((u_char *)(void *)(p) + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1)))
    106 
    107 /*
    108  * Arguments are as for qsort.
    109  */
    110 int
    111 mergesort_r(void *base, size_t nmemb, size_t size,
    112     int (*cmp)(const void *, const void *, void *), void *cookie)
    113 {
    114 	size_t i;
    115 	int sense;
    116 	int big, iflag;
    117 	u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
    118 	u_char *list2, *list1, *p2, *p, *last, **p1;
    119 
    120 	_DIAGASSERT(base != NULL);
    121 	_DIAGASSERT(cmp != NULL);
    122 
    123 	if (size < PSIZE / 2) {		/* Pointers must fit into 2 * size. */
    124 		errno = EINVAL;
    125 		return (-1);
    126 	}
    127 
    128 	if (nmemb == 0)
    129 		return (0);
    130 
    131 	/*
    132 	 * XXX
    133 	 * Stupid subtraction for the Cray.
    134 	 */
    135 	iflag = 0;
    136 	if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
    137 		iflag = 1;
    138 
    139 	if ((list2 = malloc(nmemb * size + PSIZE)) == NULL)
    140 		return (-1);
    141 
    142 	list1 = base;
    143 	setup(list1, list2, nmemb, size, cmp, cookie);
    144 	last = list2 + nmemb * size;
    145 	i = big = 0;
    146 	while (*EVAL(list2) != last) {
    147 	    l2 = list1;
    148 	    p1 = EVAL(list1);
    149 	    for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
    150 	    	p2 = *EVAL(p2);
    151 	    	f1 = l2;
    152 	    	f2 = l1 = list1 + (p2 - list2);
    153 	    	if (p2 != last)
    154 	    		p2 = *EVAL(p2);
    155 	    	l2 = list1 + (p2 - list2);
    156 	    	while (f1 < l1 && f2 < l2) {
    157 	    		if ((*cmp)(f1, f2, cookie) <= 0) {
    158 	    			q = f2;
    159 	    			b = f1, t = l1;
    160 	    			sense = -1;
    161 	    		} else {
    162 	    			q = f1;
    163 	    			b = f2, t = l2;
    164 	    			sense = 0;
    165 	    		}
    166 	    		if (!big) {	/* here i = 0 */
    167 #if 0
    168 LINEAR:
    169 #endif
    170 	    			while ((b += size) < t &&
    171 	    			    cmp(q, b, cookie) >sense)
    172 	    				if (++i == 6) {
    173 	    					big = 1;
    174 	    					goto EXPONENTIAL;
    175 	    				}
    176 	    		} else {
    177 EXPONENTIAL:	    		for (i = size; ; i <<= 1)
    178 	    				if ((p = (b + i)) >= t) {
    179 	    					if ((p = t - size) > b &&
    180 	    					    ((*cmp)(q, p, cookie) <=
    181 	    						sense))
    182 	    						t = p;
    183 	    					else
    184 	    						b = p;
    185 	    					break;
    186 	    				} else if ((*cmp)(q, p, cookie) <=
    187 	    				    sense) {
    188 	    					t = p;
    189 	    					if (i == size)
    190 	    						big = 0;
    191 	    					goto FASTCASE;
    192 	    				} else
    193 	    					b = p;
    194 #if 0
    195 SLOWCASE:
    196 #endif
    197 				while (t > b+size) {
    198 	    				i = (((t - b) / size) >> 1) * size;
    199 	    				if ((*cmp)(q, p = b + i, cookie) <=
    200 	    				    sense)
    201 	    					t = p;
    202 	    				else
    203 	    					b = p;
    204 	    			}
    205 	    			goto COPY;
    206 FASTCASE:	    		while (i > size) {
    207 	    				i = (unsigned int)i >> 1;
    208 	    				p = b + i;
    209 	    				if ((*cmp)(q, p, cookie) <= sense)
    210 	    					t = p;
    211 	    				else
    212 	    					b = p;
    213 	    			}
    214 COPY:	    			b = t;
    215 	    		}
    216 	    		i = size;
    217 	    		if (q == f1) {
    218 	    			if (iflag) {
    219 	    				ICOPY_LIST(f2, tp2, b);
    220 	    				ICOPY_ELT(f1, tp2, i);
    221 	    			} else {
    222 	    				CCOPY_LIST(f2, tp2, b);
    223 	    				CCOPY_ELT(f1, tp2, i);
    224 	    			}
    225 	    		} else {
    226 	    			if (iflag) {
    227 	    				ICOPY_LIST(f1, tp2, b);
    228 	    				ICOPY_ELT(f2, tp2, i);
    229 	    			} else {
    230 	    				CCOPY_LIST(f1, tp2, b);
    231 	    				CCOPY_ELT(f2, tp2, i);
    232 	    			}
    233 	    		}
    234 	    	}
    235 	    	if (f2 < l2) {
    236 	    		if (iflag)
    237 	    			ICOPY_LIST(f2, tp2, l2);
    238 	    		else
    239 	    			CCOPY_LIST(f2, tp2, l2);
    240 	    	} else if (f1 < l1) {
    241 	    		if (iflag)
    242 	    			ICOPY_LIST(f1, tp2, l1);
    243 	    		else
    244 	    			CCOPY_LIST(f1, tp2, l1);
    245 	    	}
    246 	    	*p1 = l2;
    247 	    }
    248 	    tp2 = list1;	/* swap list1, list2 */
    249 	    list1 = list2;
    250 	    list2 = tp2;
    251 	    last = list2 + nmemb*size;
    252 	}
    253 	if (base == list2) {
    254 		memmove(list2, list1, nmemb*size);
    255 		list2 = list1;
    256 	}
    257 	free(list2);
    258 	return (0);
    259 }
    260 
    261 #define	swap(a, b) {					\
    262 		s = b;					\
    263 		i = size;				\
    264 		do {					\
    265 			tmp = *a; *a++ = *s; *s++ = tmp; \
    266 		} while (--i);				\
    267 		a -= size;				\
    268 	}
    269 #define reverse(bot, top) {				\
    270 	s = top;					\
    271 	do {						\
    272 		i = size;				\
    273 		do {					\
    274 			tmp = *bot; *bot++ = *s; *s++ = tmp; \
    275 		} while (--i);				\
    276 		s -= size2;				\
    277 	} while(bot < s);				\
    278 }
    279 
    280 /*
    281  * Optional hybrid natural/pairwise first pass.  Eats up list1 in runs of
    282  * increasing order, list2 in a corresponding linked list.  Checks for runs
    283  * when THRESHOLD/2 pairs compare with same sense.  (Only used when NATURAL
    284  * is defined.  Otherwise simple pairwise merging is used.)
    285  */
    286 static void
    287 setup(u_char *list1, u_char *list2, size_t n, size_t size,
    288     int (*cmp)(const void *, const void *, void *), void *cookie)
    289 {
    290 	int length, tmp, sense;
    291 	u_char *f1, *f2, *s, *l2, *last, *p2;
    292 	size_t size2, i;
    293 
    294 	_DIAGASSERT(cmp != NULL);
    295 	_DIAGASSERT(list1 != NULL);
    296 	_DIAGASSERT(list2 != NULL);
    297 
    298 	size2 = size*2;
    299 	if (n <= 5) {
    300 		insertionsort(list1, n, size, cmp, cookie);
    301 		*EVAL(list2) = list2 + n*size;
    302 		return;
    303 	}
    304 	/*
    305 	 * Avoid running pointers out of bounds; limit n to evens
    306 	 * for simplicity.
    307 	 */
    308 	i = 4 + (n & 1);
    309 	insertionsort(list1 + (n - i) * size, i, size, cmp, cookie);
    310 	last = list1 + size * (n - i);
    311 	*EVAL(list2 + (last - list1)) = list2 + n * size;
    312 
    313 #ifdef NATURAL
    314 	p2 = list2;
    315 	f1 = list1;
    316 	sense = (cmp(f1, f1 + size, cookie) > 0);
    317 	for (; f1 < last; sense = !sense) {
    318 		length = 2;
    319 					/* Find pairs with same sense. */
    320 		for (f2 = f1 + size2; f2 < last; f2 += size2) {
    321 			if ((cmp(f2, f2 + size, cookie) > 0) != sense)
    322 				break;
    323 			length += 2;
    324 		}
    325 		if (length < THRESHOLD) {		/* Pairwise merge */
    326 			do {
    327 				p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
    328 				if (sense > 0)
    329 					swap (f1, f1 + size);
    330 			} while ((f1 += size2) < f2);
    331 		} else {				/* Natural merge */
    332 			l2 = f2;
    333 			for (f2 = f1 + size2; f2 < l2; f2 += size2) {
    334 				if ((cmp(f2-size, f2, cookie) > 0) != sense) {
    335 					p2 = *EVAL(p2) = f2 - list1 + list2;
    336 					if (sense > 0)
    337 						reverse(f1, f2 - size);
    338 					f1 = f2;
    339 				}
    340 			}
    341 			if (sense > 0)
    342 				reverse(f1, f2 - size);
    343 			f1 = f2;
    344 			if (f2 < last || cmp(f2 - size, f2, cookie) > 0)
    345 				p2 = *EVAL(p2) = f2 - list1 + list2;
    346 			else
    347 				p2 = *EVAL(p2) = list2 + n*size;
    348 		}
    349 	}
    350 #else		/* pairwise merge only. */
    351 	for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
    352 		p2 = *EVAL(p2) = p2 + size2;
    353 		if (cmp(f1, f1 + size, cookie) > 0)
    354 			swap(f1, f1 + size);
    355 	}
    356 #endif /* NATURAL */
    357 }
    358 
    359 /*
    360  * This is to avoid out-of-bounds addresses in sorting the
    361  * last 4 elements.
    362  */
    363 static void
    364 insertionsort(u_char *a, size_t n, size_t size,
    365     int (*cmp)(const void *, const void *, void *), void *cookie)
    366 {
    367 	u_char *ai, *s, *t, *u, tmp;
    368 	size_t i;
    369 
    370 	_DIAGASSERT(a != NULL);
    371 	_DIAGASSERT(cmp != NULL);
    372 
    373 	for (ai = a+size; --n >= 1; ai += size)
    374 		for (t = ai; t > a; t -= size) {
    375 			u = t - size;
    376 			if (cmp(u, t, cookie) <= 0)
    377 				break;
    378 			swap(u, t);
    379 		}
    380 }
    381 
    382 static int
    383 cmpnocookie(const void *a, const void *b, void *cookie)
    384 {
    385 	int (*cmp)(const void *, const void *) = cookie;
    386 
    387 	return cmp(a, b);
    388 }
    389 
    390 int
    391 mergesort(void *a, size_t n, size_t es,
    392     int (*cmp)(const void *, const void *))
    393 {
    394 
    395 	return mergesort_r(a, n, es, cmpnocookie, cmp);
    396 }
    397