qsort.c revision 128019 
1/*-
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.
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
30#include <sys/cdefs.h>
31__FBSDID("$FreeBSD: head/sys/libkern/qsort.c 128019 2004-04-07 20:46:16Z imp $");
32
33#include <sys/libkern.h>
34
35typedef int		 cmp_t(const void *, const void *);
36static __inline char	*med3(char *, char *, char *, cmp_t *);
37static __inline void	 swapfunc(char *, char *, int, int);
38
39#define min(a, b)	(a) < (b) ? (a) : (b)
40
41/*
42 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
43 */
44#define swapcode(TYPE, parmi, parmj, n) { 		\
45	long i = (n) / sizeof (TYPE); 			\
46	register TYPE *pi = (TYPE *) (parmi); 		\
47	register TYPE *pj = (TYPE *) (parmj); 		\
48	do { 						\
49		register TYPE	t = *pi;		\
50		*pi++ = *pj;				\
51		*pj++ = t;				\
52        } while (--i > 0);				\
53}
54
55#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
56	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
57
58static __inline void
59swapfunc(a, b, n, swaptype)
60	char *a, *b;
61	int n, swaptype;
62{
63	if(swaptype <= 1)
64		swapcode(long, a, b, n)
65	else
66		swapcode(char, a, b, n)
67}
68
69#define swap(a, b)					\
70	if (swaptype == 0) {				\
71		long t = *(long *)(a);			\
72		*(long *)(a) = *(long *)(b);		\
73		*(long *)(b) = t;			\
74	} else						\
75		swapfunc(a, b, es, swaptype)
76
77#define vecswap(a, b, n) 	if ((n) > 0) swapfunc(a, b, n, swaptype)
78
79static __inline char *
80med3(a, b, c, cmp)
81	char *a, *b, *c;
82	cmp_t *cmp;
83{
84	return cmp(a, b) < 0 ?
85	       (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
86              :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
87}
88
89void
90qsort(a, n, es, cmp)
91	void *a;
92	size_t n, es;
93	cmp_t *cmp;
94{
95	char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
96	int d, r, swaptype, swap_cnt;
97
98loop:	SWAPINIT(a, es);
99	swap_cnt = 0;
100	if (n < 7) {
101		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
102			for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
103			     pl -= es)
104				swap(pl, pl - es);
105		return;
106	}
107	pm = (char *)a + (n / 2) * es;
108	if (n > 7) {
109		pl = a;
110		pn = (char *)a + (n - 1) * es;
111		if (n > 40) {
112			d = (n / 8) * es;
113			pl = med3(pl, pl + d, pl + 2 * d, cmp);
114			pm = med3(pm - d, pm, pm + d, cmp);
115			pn = med3(pn - 2 * d, pn - d, pn, cmp);
116		}
117		pm = med3(pl, pm, pn, cmp);
118	}
119	swap(a, pm);
120	pa = pb = (char *)a + es;
121
122	pc = pd = (char *)a + (n - 1) * es;
123	for (;;) {
124		while (pb <= pc && (r = cmp(pb, a)) <= 0) {
125			if (r == 0) {
126				swap_cnt = 1;
127				swap(pa, pb);
128				pa += es;
129			}
130			pb += es;
131		}
132		while (pb <= pc && (r = cmp(pc, a)) >= 0) {
133			if (r == 0) {
134				swap_cnt = 1;
135				swap(pc, pd);
136				pd -= es;
137			}
138			pc -= es;
139		}
140		if (pb > pc)
141			break;
142		swap(pb, pc);
143		swap_cnt = 1;
144		pb += es;
145		pc -= es;
146	}
147	if (swap_cnt == 0) {  /* Switch to insertion sort */
148		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
149			for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
150			     pl -= es)
151				swap(pl, pl - es);
152		return;
153	}
154
155	pn = (char *)a + n * es;
156	r = min(pa - (char *)a, pb - pa);
157	vecswap(a, pb - r, r);
158	r = min(pd - pc, pn - pd - es);
159	vecswap(pb, pn - r, r);
160	if ((r = pb - pa) > es)
161		qsort(a, r / es, es, cmp);
162	if ((r = pd - pc) > es) {
163		/* Iterate rather than recurse to save stack space */
164		a = pn - r;
165		n = r / es;
166		goto loop;
167	}
168/*		qsort(pn - r, r / es, es, cmp);*/
169}
170