Home | History | Annotate | Line # | Download | only in stdlib
merge.c revision 1.15.2.1 
      1 /*	$NetBSD: merge.c,v 1.15.2.1 2018/06/25 07:25:34 pgoyette 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.15.2.1 2018/06/25 07:25:34 pgoyette 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 #endif
     69 
     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 *));
     74 
     75 #define ISIZE sizeof(int)
     76 #define PSIZE sizeof(u_char *)
     77 #define ICOPY_LIST(src, dst, last)				\
     78 	do							\
     79 	*(int*)(void *)dst = *(int*)(void *)src,		\
     80 		src += ISIZE, dst += ISIZE;			\
     81 	while(src < last)
     82 #define ICOPY_ELT(src, dst, i)					\
     83 	do							\
     84 	*(int*)(void *)dst = *(int*)(void *)src,		\
     85 	src += ISIZE, dst += ISIZE;				\
     86 	while (i -= ISIZE)
     87 
     88 #define CCOPY_LIST(src, dst, last)		\
     89 	do					\
     90 		*dst++ = *src++;		\
     91 	while (src < last)
     92 #define CCOPY_ELT(src, dst, i)			\
     93 	do					\
     94 		*dst++ = *src++;		\
     95 	while (i -= 1)
     96 
     97 /*
     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
    100  * boundaries.
    101  */
    102 /* Assumption: PSIZE is a power of 2. */
    103 #define EVAL(p) ((u_char **)(void *)					\
    104     (((u_char *)(void *)(p) + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1)))
    105 
    106 /*
    107  * Arguments are as for qsort.
    108  */
    109 int
    110 mergesort(void *base, size_t nmemb, size_t size,
    111     int (*cmp)(const void *, const void *))
    112 {
    113 	size_t i;
    114 	int sense;
    115 	int big, iflag;
    116 	u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
    117 	u_char *list2, *list1, *p2, *p, *last, **p1;
    118 
    119 	_DIAGASSERT(base != NULL);
    120 	_DIAGASSERT(cmp != NULL);
    121 
    122 	if (size < PSIZE / 2) {		/* Pointers must fit into 2 * size. */
    123 		errno = EINVAL;
    124 		return (-1);
    125 	}
    126 
    127 	if (nmemb == 0)
    128 		return (0);
    129 
    130 	/*
    131 	 * XXX
    132 	 * Stupid subtraction for the Cray.
    133 	 */
    134 	iflag = 0;
    135 	if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
    136 		iflag = 1;
    137 
    138 	if ((list2 = malloc(nmemb * size + PSIZE)) == NULL)
    139 		return (-1);
    140 
    141 	list1 = base;
    142 	setup(list1, list2, nmemb, size, cmp);
    143 	last = list2 + nmemb * size;
    144 	i = big = 0;
    145 	while (*EVAL(list2) != last) {
    146 	    l2 = list1;
    147 	    p1 = EVAL(list1);
    148 	    for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
    149 	    	p2 = *EVAL(p2);
    150 	    	f1 = l2;
    151 	    	f2 = l1 = list1 + (p2 - list2);
    152 	    	if (p2 != last)
    153 	    		p2 = *EVAL(p2);
    154 	    	l2 = list1 + (p2 - list2);
    155 	    	while (f1 < l1 && f2 < l2) {
    156 	    		if ((*cmp)(f1, f2) <= 0) {
    157 	    			q = f2;
    158 	    			b = f1, t = l1;
    159 	    			sense = -1;
    160 	    		} else {
    161 	    			q = f1;
    162 	    			b = f2, t = l2;
    163 	    			sense = 0;
    164 	    		}
    165 	    		if (!big) {	/* here i = 0 */
    166 #if 0
    167 LINEAR:
    168 #endif
    169 				while ((b += size) < t && cmp(q, b) >sense)
    170 	    				if (++i == 6) {
    171 	    					big = 1;
    172 	    					goto EXPONENTIAL;
    173 	    				}
    174 	    		} else {
    175 EXPONENTIAL:	    		for (i = size; ; i <<= 1)
    176 	    				if ((p = (b + i)) >= t) {
    177 	    					if ((p = t - size) > b &&
    178 						    (*cmp)(q, p) <= sense)
    179 	    						t = p;
    180 	    					else
    181 	    						b = p;
    182 	    					break;
    183 	    				} else if ((*cmp)(q, p) <= sense) {
    184 	    					t = p;
    185 	    					if (i == size)
    186 	    						big = 0;
    187 	    					goto FASTCASE;
    188 	    				} else
    189 	    					b = p;
    190 #if 0
    191 SLOWCASE:
    192 #endif
    193 				while (t > b+size) {
    194 	    				i = (((t - b) / size) >> 1) * size;
    195 	    				if ((*cmp)(q, p = b + i) <= sense)
    196 	    					t = p;
    197 	    				else
    198 	    					b = p;
    199 	    			}
    200 	    			goto COPY;
    201 FASTCASE:	    		while (i > size)
    202 	    				if ((*cmp)(q,
    203 	    					p = b +
    204 						    (i = (unsigned int) i >> 1)) <= sense)
    205 	    					t = p;
    206 	    				else
    207 	    					b = p;
    208 COPY:	    			b = t;
    209 	    		}
    210 	    		i = size;
    211 	    		if (q == f1) {
    212 	    			if (iflag) {
    213 	    				ICOPY_LIST(f2, tp2, b);
    214 	    				ICOPY_ELT(f1, tp2, i);
    215 	    			} else {
    216 	    				CCOPY_LIST(f2, tp2, b);
    217 	    				CCOPY_ELT(f1, tp2, i);
    218 	    			}
    219 	    		} else {
    220 	    			if (iflag) {
    221 	    				ICOPY_LIST(f1, tp2, b);
    222 	    				ICOPY_ELT(f2, tp2, i);
    223 	    			} else {
    224 	    				CCOPY_LIST(f1, tp2, b);
    225 	    				CCOPY_ELT(f2, tp2, i);
    226 	    			}
    227 	    		}
    228 	    	}
    229 	    	if (f2 < l2) {
    230 	    		if (iflag)
    231 	    			ICOPY_LIST(f2, tp2, l2);
    232 	    		else
    233 	    			CCOPY_LIST(f2, tp2, l2);
    234 	    	} else if (f1 < l1) {
    235 	    		if (iflag)
    236 	    			ICOPY_LIST(f1, tp2, l1);
    237 	    		else
    238 	    			CCOPY_LIST(f1, tp2, l1);
    239 	    	}
    240 	    	*p1 = l2;
    241 	    }
    242 	    tp2 = list1;	/* swap list1, list2 */
    243 	    list1 = list2;
    244 	    list2 = tp2;
    245 	    last = list2 + nmemb*size;
    246 	}
    247 	if (base == list2) {
    248 		memmove(list2, list1, nmemb*size);
    249 		list2 = list1;
    250 	}
    251 	free(list2);
    252 	return (0);
    253 }
    254 
    255 #define	swap(a, b) {					\
    256 		s = b;					\
    257 		i = size;				\
    258 		do {					\
    259 			tmp = *a; *a++ = *s; *s++ = tmp; \
    260 		} while (--i);				\
    261 		a -= size;				\
    262 	}
    263 #define reverse(bot, top) {				\
    264 	s = top;					\
    265 	do {						\
    266 		i = size;				\
    267 		do {					\
    268 			tmp = *bot; *bot++ = *s; *s++ = tmp; \
    269 		} while (--i);				\
    270 		s -= size2;				\
    271 	} while(bot < s);				\
    272 }
    273 
    274 /*
    275  * Optional hybrid natural/pairwise first pass.  Eats up list1 in runs of
    276  * increasing order, list2 in a corresponding linked list.  Checks for runs
    277  * when THRESHOLD/2 pairs compare with same sense.  (Only used when NATURAL
    278  * is defined.  Otherwise simple pairwise merging is used.)
    279  */
    280 
    281 /* XXX: shouldn't this function be static? - lukem 990810 */
    282 void
    283 setup(u_char *list1, u_char *list2, size_t n, size_t size,
    284     int (*cmp)(const void *, const void *))
    285 {
    286 	int length, tmp, sense;
    287 	u_char *f1, *f2, *s, *l2, *last, *p2;
    288 	size_t size2, i;
    289 
    290 	_DIAGASSERT(cmp != NULL);
    291 	_DIAGASSERT(list1 != NULL);
    292 	_DIAGASSERT(list2 != NULL);
    293 
    294 	size2 = size*2;
    295 	if (n <= 5) {
    296 		insertionsort(list1, n, size, cmp);
    297 		*EVAL(list2) = list2 + n*size;
    298 		return;
    299 	}
    300 	/*
    301 	 * Avoid running pointers out of bounds; limit n to evens
    302 	 * for simplicity.
    303 	 */
    304 	i = 4 + (n & 1);
    305 	insertionsort(list1 + (n - i) * size, i, size, cmp);
    306 	last = list1 + size * (n - i);
    307 	*EVAL(list2 + (last - list1)) = list2 + n * size;
    308 
    309 #ifdef NATURAL
    310 	p2 = list2;
    311 	f1 = list1;
    312 	sense = (cmp(f1, f1 + size) > 0);
    313 	for (; f1 < last; sense = !sense) {
    314 		length = 2;
    315 					/* Find pairs with same sense. */
    316 		for (f2 = f1 + size2; f2 < last; f2 += size2) {
    317 			if ((cmp(f2, f2+ size) > 0) != sense)
    318 				break;
    319 			length += 2;
    320 		}
    321 		if (length < THRESHOLD) {		/* Pairwise merge */
    322 			do {
    323 				p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
    324 				if (sense > 0)
    325 					swap (f1, f1 + size);
    326 			} while ((f1 += size2) < f2);
    327 		} else {				/* Natural merge */
    328 			l2 = f2;
    329 			for (f2 = f1 + size2; f2 < l2; f2 += size2) {
    330 				if ((cmp(f2-size, f2) > 0) != sense) {
    331 					p2 = *EVAL(p2) = f2 - list1 + list2;
    332 					if (sense > 0)
    333 						reverse(f1, f2 - size);
    334 					f1 = f2;
    335 				}
    336 			}
    337 			if (sense > 0)
    338 				reverse(f1, f2 - size);
    339 			f1 = f2;
    340 			if (f2 < last || cmp(f2 - size, f2) > 0)
    341 				p2 = *EVAL(p2) = f2 - list1 + list2;
    342 			else
    343 				p2 = *EVAL(p2) = list2 + n*size;
    344 		}
    345 	}
    346 #else		/* pairwise merge only. */
    347 	for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
    348 		p2 = *EVAL(p2) = p2 + size2;
    349 		if (cmp (f1, f1 + size) > 0)
    350 			swap(f1, f1 + size);
    351 	}
    352 #endif /* NATURAL */
    353 }
    354 
    355 /*
    356  * This is to avoid out-of-bounds addresses in sorting the
    357  * last 4 elements.
    358  */
    359 static void
    360 insertionsort(u_char *a, size_t n, size_t size,
    361     int (*cmp)(const void *, const void *))
    362 {
    363 	u_char *ai, *s, *t, *u, tmp;
    364 	size_t i;
    365 
    366 	_DIAGASSERT(a != NULL);
    367 	_DIAGASSERT(cmp != NULL);
    368 
    369 	for (ai = a+size; --n >= 1; ai += size)
    370 		for (t = ai; t > a; t -= size) {
    371 			u = t - size;
    372 			if (cmp(u, t) <= 0)
    373 				break;
    374 			swap(u, t);
    375 		}
    376 }
    377