[apple/libc.git] / stdlib / FreeBSD / qsort.c

/*-
 * Copyright (c) 1992, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)qsort.c	8.1 (Berkeley) 6/4/93";
#endif /* LIBC_SCCS and not lint */
#include <sys/cdefs.h>
__FBSDID("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15 2008/01/14 09:21:34 das Exp $");

#include <stdlib.h>
#include <string.h>

#ifdef I_AM_QSORT_R
typedef int		 cmp_t(void *, const void *, const void *);
#else
typedef int		 cmp_t(const void *, const void *);
#endif
#ifdef I_AM_QSORT_B
static inline char	*med3(char *, char *, char *, cmp_t ^, void *) __attribute__((always_inline));
#else
static inline char	*med3(char *, char *, char *, cmp_t *, void *) __attribute__((always_inline));
#endif
static inline void	 swapfunc(char *, char *, int, int) __attribute__((always_inline));

#define min(a, b)	(a) < (b) ? a : b

/*
 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
 */
#define swapcode(TYPE, parmi, parmj, n) { 		\
	long i = (n) / sizeof (TYPE); 			\
	TYPE *pi = (TYPE *) (parmi); 		\
	TYPE *pj = (TYPE *) (parmj); 		\
	do { 						\
		TYPE	t = *pi;		\
		*pi++ = *pj;				\
		*pj++ = t;				\
        } while (--i > 0);				\
}

#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

static inline void
swapfunc(a, b, n, swaptype)
	char *a, *b;
	int n, swaptype;
{
	if(swaptype <= 1)
		swapcode(long, a, b, n)
	else
		swapcode(char, a, b, n)
}

#define swap(a, b)					\
	if (swaptype == 0) {				\
		long t = *(long *)(a);			\
		*(long *)(a) = *(long *)(b);		\
		*(long *)(b) = t;			\
	} else						\
		swapfunc(a, b, es, swaptype)

#define vecswap(a, b, n) 	if ((n) > 0) swapfunc(a, b, n, swaptype)

#ifdef I_AM_QSORT_R
#define	CMP(t, x, y) (cmp((t), (x), (y)))
#else
#define	CMP(t, x, y) (cmp((x), (y)))
#endif

static inline char *
med3(char *a, char *b, char *c,
#ifdef I_AM_QSORT_B
cmp_t ^cmp,
#else
cmp_t *cmp,
#endif
void *thunk
#ifndef I_AM_QSORT_R
__unused
#endif
)
{
	return CMP(thunk, a, b) < 0 ?
	       (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
              :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
}

#ifdef __LP64__
#define DEPTH(x)	(2 * (flsl((long)(x)) - 1))
#else /* !__LP64__ */
#define DEPTH(x)	(2 * (fls((int)(x)) - 1))
#endif /* __LP64__ */

#ifdef I_AM_QSORT_R
int __heapsort_r(void *, size_t, size_t, void *, int (*)(void *, const void *, const void *));
#endif

static void
_qsort(void *a, size_t n, size_t es,
#ifdef I_AM_QSORT_R
void *thunk,
#else
#define thunk	NULL
#endif
#ifdef I_AM_QSORT_B
cmp_t ^cmp,
#else
cmp_t *cmp,
#endif
int depth_limit)
{
	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
	size_t d, r;
	int cmp_result;
	int swaptype, swap_cnt;

loop:
	if (depth_limit-- <= 0) {
#ifdef I_AM_QSORT_B
		heapsort_b(a, n, es, cmp);
#elif defined(I_AM_QSORT_R)
		__heapsort_r(a, n, es, thunk, cmp);
#else
		heapsort(a, n, es, cmp);
#endif
		return;
	}
	SWAPINIT(a, es);
	swap_cnt = 0;
	if (n < 7) {
		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
			for (pl = pm; 
			     pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
			     pl -= es)
				swap(pl, pl - es);
		return;
	}
	pm = (char *)a + (n / 2) * es;
	if (n > 7) {
		pl = a;
		pn = (char *)a + (n - 1) * es;
		if (n > 40) {
			d = (n / 8) * es;
			pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
			pm = med3(pm - d, pm, pm + d, cmp, thunk);
			pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
		}
		pm = med3(pl, pm, pn, cmp, thunk);
	}
	swap(a, pm);
	pa = pb = (char *)a + es;

	pc = pd = (char *)a + (n - 1) * es;
	for (;;) {
		while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
			if (cmp_result == 0) {
				swap_cnt = 1;
				swap(pa, pb);
				pa += es;
			}
			pb += es;
		}
		while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
			if (cmp_result == 0) {
				swap_cnt = 1;
				swap(pc, pd);
				pd -= es;
			}
			pc -= es;
		}
		if (pb > pc)
			break;
		swap(pb, pc);
		swap_cnt = 1;
		pb += es;
		pc -= es;
	}

	pn = (char *)a + n * es;
	r = min(pa - (char *)a, pb - pa);
	vecswap(a, pb - r, r);
	r = min(pd - pc, pn - pd - es);
	vecswap(pb, pn - r, r);

	if (swap_cnt == 0) {  /* Switch to insertion sort */
		r = 1 + n / 4; /* n >= 7, so r >= 2 */
		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
			for (pl = pm; 
			     pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
			     pl -= es) {
				swap(pl, pl - es);
				if (++swap_cnt > r) goto nevermind;
			}
		return;
	}

nevermind:
	if ((r = pb - pa) > es)
#ifdef I_AM_QSORT_R
		_qsort(a, r / es, es, thunk, cmp, depth_limit);
#else
		_qsort(a, r / es, es, cmp, depth_limit);
#endif
	if ((r = pd - pc) > es) {
		/* Iterate rather than recurse to save stack space */
		a = pn - r;
		n = r / es;
		goto loop;
	}
/*		qsort(pn - r, r / es, es, cmp);*/
}

void
#ifdef I_AM_QSORT_R
qsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp)
#elif defined(I_AM_QSORT_B)
qsort_b(void *a, size_t n, size_t es, cmp_t ^cmp)
#else
qsort(void *a, size_t n, size_t es, cmp_t *cmp)
#endif
{
	_qsort(a, n, es,
#ifdef I_AM_QSORT_R
		thunk,
#endif
		cmp, DEPTH(n));
}
Commit	Line	Data
9385eb3d	1	/*-
e9ce8d39 A	2	* Copyright (c) 1992, 1993
	3	* The Regents of the University of California. All rights reserved.
	4	*
	5	* Redistribution and use in source and binary forms, with or without
	6	* modification, are permitted provided that the following conditions
	7	* are met:
	8	* 1. Redistributions of source code must retain the above copyright
	9	* notice, this list of conditions and the following disclaimer.
	10	* 2. Redistributions in binary form must reproduce the above copyright
	11	* notice, this list of conditions and the following disclaimer in the
	12	* documentation and/or other materials provided with the distribution.
e9ce8d39 A	13	* 4. Neither the name of the University nor the names of its contributors
	14	* may be used to endorse or promote products derived from this software
	15	* without specific prior written permission.
	16	*
	17	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	18	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	19	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	20	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	21	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	22	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	23	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	24	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	25	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	26	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	27	* SUCH DAMAGE.
	28	*/
	29
9385eb3d A	30	#if defined(LIBC_SCCS) && !defined(lint)
	31	static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
	32	#endif /* LIBC_SCCS and not lint */
	33	#include <sys/cdefs.h>
34e8f829	34	__FBSDID("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15 2008/01/14 09:21:34 das Exp $");
e9ce8d39	35
e9ce8d39	36	#include <stdlib.h>
ad3c9f2a	37	#include <string.h>
e9ce8d39	38
9385eb3d A	39	#ifdef I_AM_QSORT_R
	40	typedef int cmp_t(void , const void , const void *);
	41	#else
	42	typedef int cmp_t(const void , const void );
	43	#endif
ad3c9f2a A	44	#ifdef I_AM_QSORT_B
	45	static inline char med3(char , char , char , cmp_t ^, void *) __attribute__((always_inline));
	46	#else
	47	static inline char med3(char , char , char , cmp_t , void ) __attribute__((always_inline));
	48	#endif
	49	static inline void swapfunc(char , char , int, int) __attribute__((always_inline));
e9ce8d39 A	50
	51	#define min(a, b) (a) < (b) ? a : b
	52
	53	/*
	54	* Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
	55	*/
	56	#define swapcode(TYPE, parmi, parmj, n) { \
	57	long i = (n) / sizeof (TYPE); \
9385eb3d A	58	TYPE pi = (TYPE ) (parmi); \
9385eb3d A	59	TYPE pj = (TYPE ) (parmj); \
e9ce8d39	60	do { \
9385eb3d	61	TYPE t = *pi; \
e9ce8d39 A	62	pi++ = pj; \
	63	*pj++ = t; \
	64	} while (--i > 0); \
	65	}
	66
	67	#define SWAPINIT(a, es) swaptype = ((char )a - (char )0) % sizeof(long) \|\| \
	68	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
	69
	70	static inline void
	71	swapfunc(a, b, n, swaptype)
	72	char a, b;
	73	int n, swaptype;
	74	{
9385eb3d	75	if(swaptype <= 1)
e9ce8d39 A	76	swapcode(long, a, b, n)
	77	else
	78	swapcode(char, a, b, n)
	79	}
	80
	81	#define swap(a, b) \
	82	if (swaptype == 0) { \
	83	long t = (long )(a); \
	84	(long )(a) = (long )(b); \
	85	(long )(b) = t; \
	86	} else \
	87	swapfunc(a, b, es, swaptype)
	88
	89	#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
	90
9385eb3d A	91	#ifdef I_AM_QSORT_R
	92	#define CMP(t, x, y) (cmp((t), (x), (y)))
	93	#else
	94	#define CMP(t, x, y) (cmp((x), (y)))
	95	#endif
	96
e9ce8d39	97	static inline char *
ad3c9f2a A	98	med3(char a, char b, char *c,
	99	#ifdef I_AM_QSORT_B
	100	cmp_t ^cmp,
	101	#else
	102	cmp_t *cmp,
	103	#endif
	104	void *thunk
9385eb3d A	105	#ifndef I_AM_QSORT_R
	106	__unused
	107	#endif
	108	)
e9ce8d39	109	{
9385eb3d A	110	return CMP(thunk, a, b) < 0 ?
	111	(CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
	112	:(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
e9ce8d39 A	113	}
e9ce8d39 A	114
ad3c9f2a A	115	#ifdef __LP64__
	116	#define DEPTH(x) (2 * (flsl((long)(x)) - 1))
	117	#else /* !__LP64__ */
	118	#define DEPTH(x) (2 * (fls((int)(x)) - 1))
	119	#endif /* __LP64__ */
	120
9385eb3d	121	#ifdef I_AM_QSORT_R
ad3c9f2a A	122	int __heapsort_r(void , size_t, size_t, void , int ()(void , const void , const void ));
	123	#endif
	124
	125	static void
	126	_qsort(void *a, size_t n, size_t es,
	127	#ifdef I_AM_QSORT_R
	128	void *thunk,
9385eb3d	129	#else
ad3c9f2a A	130	#define thunk NULL
	131	#endif
	132	#ifdef I_AM_QSORT_B
	133	cmp_t ^cmp,
	134	#else
	135	cmp_t *cmp,
9385eb3d	136	#endif
ad3c9f2a	137	int depth_limit)
e9ce8d39 A	138	{
e9ce8d39 A	139	char pa, pb, pc, pd, pl, pm, *pn;
34e8f829 A	140	size_t d, r;
	141	int cmp_result;
	142	int swaptype, swap_cnt;
e9ce8d39	143
ad3c9f2a A	144	loop:
	145	if (depth_limit-- <= 0) {
	146	#ifdef I_AM_QSORT_B
	147	heapsort_b(a, n, es, cmp);
	148	#elif defined(I_AM_QSORT_R)
	149	__heapsort_r(a, n, es, thunk, cmp);
	150	#else
	151	heapsort(a, n, es, cmp);
	152	#endif
	153	return;
	154	}
	155	SWAPINIT(a, es);
e9ce8d39 A	156	swap_cnt = 0;
e9ce8d39 A	157	if (n < 7) {
9385eb3d A	158	for (pm = (char )a + es; pm < (char )a + n * es; pm += es)
	159	for (pl = pm;
	160	pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
e9ce8d39 A	161	pl -= es)
	162	swap(pl, pl - es);
	163	return;
	164	}
9385eb3d	165	pm = (char )a + (n / 2) es;
e9ce8d39 A	166	if (n > 7) {
e9ce8d39 A	167	pl = a;
9385eb3d	168	pn = (char )a + (n - 1) es;
e9ce8d39 A	169	if (n > 40) {
e9ce8d39 A	170	d = (n / 8) * es;
9385eb3d A	171	pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
	172	pm = med3(pm - d, pm, pm + d, cmp, thunk);
	173	pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
e9ce8d39	174	}
9385eb3d	175	pm = med3(pl, pm, pn, cmp, thunk);
e9ce8d39 A	176	}
e9ce8d39 A	177	swap(a, pm);
9385eb3d	178	pa = pb = (char *)a + es;
e9ce8d39	179
9385eb3d	180	pc = pd = (char )a + (n - 1) es;
e9ce8d39	181	for (;;) {
34e8f829 A	182	while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
34e8f829 A	183	if (cmp_result == 0) {
e9ce8d39 A	184	swap_cnt = 1;
	185	swap(pa, pb);
	186	pa += es;
	187	}
	188	pb += es;
	189	}
34e8f829 A	190	while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
34e8f829 A	191	if (cmp_result == 0) {
e9ce8d39 A	192	swap_cnt = 1;
	193	swap(pc, pd);
	194	pd -= es;
	195	}
	196	pc -= es;
	197	}
	198	if (pb > pc)
	199	break;
	200	swap(pb, pc);
	201	swap_cnt = 1;
	202	pb += es;
	203	pc -= es;
	204	}
ad3c9f2a A	205
	206	pn = (char )a + n es;
	207	r = min(pa - (char *)a, pb - pa);
	208	vecswap(a, pb - r, r);
	209	r = min(pd - pc, pn - pd - es);
	210	vecswap(pb, pn - r, r);
	211
e9ce8d39	212	if (swap_cnt == 0) { /* Switch to insertion sort */
ad3c9f2a	213	r = 1 + n / 4; /* n >= 7, so r >= 2 */
9385eb3d A	214	for (pm = (char )a + es; pm < (char )a + n * es; pm += es)
	215	for (pl = pm;
	216	pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
ad3c9f2a	217	pl -= es) {
e9ce8d39	218	swap(pl, pl - es);
ad3c9f2a A	219	if (++swap_cnt > r) goto nevermind;
ad3c9f2a A	220	}
e9ce8d39 A	221	return;
	222	}
	223
ad3c9f2a	224	nevermind:
e9ce8d39	225	if ((r = pb - pa) > es)
9385eb3d	226	#ifdef I_AM_QSORT_R
ad3c9f2a	227	_qsort(a, r / es, es, thunk, cmp, depth_limit);
9385eb3d	228	#else
ad3c9f2a	229	_qsort(a, r / es, es, cmp, depth_limit);
9385eb3d A	230	#endif
9385eb3d A	231	if ((r = pd - pc) > es) {
e9ce8d39 A	232	/* Iterate rather than recurse to save stack space */
	233	a = pn - r;
	234	n = r / es;
	235	goto loop;
	236	}
	237	/* qsort(pn - r, r / es, es, cmp);*/
	238	}
ad3c9f2a A	239
	240	void
	241	#ifdef I_AM_QSORT_R
	242	qsort_r(void a, size_t n, size_t es, void thunk, cmp_t *cmp)
	243	#elif defined(I_AM_QSORT_B)
	244	qsort_b(void *a, size_t n, size_t es, cmp_t ^cmp)
	245	#else
	246	qsort(void a, size_t n, size_t es, cmp_t cmp)
	247	#endif
	248	{
	249	_qsort(a, n, es,
	250	#ifdef I_AM_QSORT_R
	251	thunk,
	252	#endif
	253	cmp, DEPTH(n));
	254	}