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 * 3. All advertising materials mentioning features or use of this software
14 *    must display the following acknowledgement:
15 *	This product includes software developed by the University of
16 *	California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 *    may be used to endorse or promote products derived from this software
19 *    without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34
35#include <stdlib.h>
36
37#define min(a, b)	(a) < (b) ? a : b
38
39
40typedef int		 cmp_t(void const *, void const *);
41static inline char	*med3(char *, char *, char *, cmp_t *);
42static inline void	 swapfunc(char *, char *, int, int);
43
44
45/*
46 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
47 */
48#define swapcode(TYPE, parmi, parmj, n) { 		\
49	long i = (n) / sizeof (TYPE); 			\
50	register TYPE *pi = (TYPE *) (parmi); 		\
51	register TYPE *pj = (TYPE *) (parmj); 		\
52	do { 						\
53		register TYPE	t = *pi;		\
54		*pi++ = *pj;				\
55		*pj++ = t;				\
56        } while (--i > 0);				\
57}
58
59#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
60	es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
61
62static inline
63void
64swapfunc(char *a, char *b, int n, int swaptype)
65{
66	if(swaptype <= 1)
67		swapcode(long, a, b, n)
68	else
69		swapcode(char, a, b, n)
70}
71
72#define swap(a, b)					\
73	if (swaptype == 0) {				\
74		long t = *(long *)(a);			\
75		*(long *)(a) = *(long *)(b);		\
76		*(long *)(b) = t;			\
77	} else						\
78		swapfunc(a, b, es, swaptype)
79
80#define vecswap(a, b, n) 	if ((n) > 0) swapfunc(a, b, n, swaptype)
81
82static inline
83char *
84med3(char *a, char *b, char *c, cmp_t *cmp)
85{
86	return cmp(a, b) < 0 ?
87	       (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
88              :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
89}
90
91void
92qsort(void *a, size_t n, size_t es, cmp_t *cmp)
93{
94	char *pa;
95	char *pb;
96	char *pc;
97	char *pd;
98	char *pl;
99	char *pm;
100	char *pn;
101	int d;
102	int r;
103	int swaptype;
104	int swap_cnt;
105
106loop:	SWAPINIT(a, es);
107	swap_cnt = 0;
108	if (n < 7) {
109		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
110			for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
111			     pl -= es)
112				swap(pl, pl - es);
113		return;
114	}
115	pm = (char *)a + (n / 2) * es;
116	if (n > 7) {
117		pl = a;
118		pn = (char *)a + (n - 1) * es;
119		if (n > 40) {
120			d = (n / 8) * es;
121			pl = med3(pl, pl + d, pl + 2 * d, cmp);
122			pm = med3(pm - d, pm, pm + d, cmp);
123			pn = med3(pn - 2 * d, pn - d, pn, cmp);
124		}
125		pm = med3(pl, pm, pn, cmp);
126	}
127	swap(a, pm);
128	pa = pb = (char *)a + es;
129
130	pc = pd = (char *)a + (n - 1) * es;
131	for (;;) {
132		while (pb <= pc && (r = cmp(pb, a)) <= 0) {
133			if (r == 0) {
134				swap_cnt = 1;
135				swap(pa, pb);
136				pa += es;
137			}
138			pb += es;
139		}
140		while (pb <= pc && (r = cmp(pc, a)) >= 0) {
141			if (r == 0) {
142				swap_cnt = 1;
143				swap(pc, pd);
144				pd -= es;
145			}
146			pc -= es;
147		}
148		if (pb > pc)
149			break;
150		swap(pb, pc);
151		swap_cnt = 1;
152		pb += es;
153		pc -= es;
154	}
155	if (swap_cnt == 0) {  /* Switch to insertion sort */
156		for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
157			for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
158			     pl -= es)
159				swap(pl, pl - es);
160		return;
161	}
162
163	pn = (char *)a + n * es;
164	r = min(pa - (char *)a, pb - pa);
165	vecswap(a, pb - r, r);
166	r = min((int)(pd - pc), (int)(pn - pd - es));
167	vecswap(pb, pn - r, r);
168	if ((r = pb - pa) > (int)es)
169		qsort(a, r / es, es, cmp);
170	if ((r = pd - pc) > (int)es) {
171		/* Iterate rather than recurse to save stack space */
172		a = pn - r;
173		n = r / es;
174		goto loop;
175	}
176/*		qsort(pn - r, r / es, es, cmp);*/
177}
178