2 * Copyright (c) 1992, 1993
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
29 * @(#)qsort.c 8.1 (Berkeley) 6/4/93
30 * $FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15 2008/01/14 09:21:34 das Exp $
31 * $DragonFly: src/lib/libc/stdlib/qsort.c,v 1.5 2005/11/20 12:37:49 swildner Exp $
37 typedef int cmp_t(void *, const void *, const void *);
39 typedef int cmp_t(const void *, const void *);
41 static inline char *med3(char *, char *, char *, cmp_t
*, void *);
42 static inline void swapfunc(char *, char *, int, int);
44 #define min(a, b) (a) < (b) ? a : b
47 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
49 #define swapcode(TYPE, parmi, parmj, n) { \
50 long i = (n) / sizeof (TYPE); \
51 TYPE *pi = (TYPE *) (parmi); \
52 TYPE *pj = (TYPE *) (parmj); \
60 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
61 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
64 swapfunc(char *a
, char *b
, int n
, int swaptype
)
67 swapcode(long, a
, b
, n
)
69 swapcode(char, a
, b
, n
)
73 if (swaptype == 0) { \
74 long t = *(long *)(a); \
75 *(long *)(a) = *(long *)(b); \
78 swapfunc(a, b, es, swaptype)
80 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
83 #define CMP(t, x, y) (cmp((t), (x), (y)))
85 #define CMP(t, x, y) (cmp((x), (y)))
89 med3(char *a
, char *b
, char *c
, cmp_t
*cmp
, void *thunk
95 return CMP(thunk
, a
, b
) < 0 ?
96 (CMP(thunk
, b
, c
) < 0 ? b
: (CMP(thunk
, a
, c
) < 0 ? c
: a
))
97 :(CMP(thunk
, b
, c
) > 0 ? b
: (CMP(thunk
, a
, c
) < 0 ? a
: c
));
102 qsort_r(void *a
, size_t n
, size_t es
, void *thunk
, cmp_t
*cmp
)
106 qsort(void *a
, size_t n
, size_t es
, cmp_t
*cmp
)
109 char *pa
, *pb
, *pc
, *pd
, *pl
, *pm
, *pn
;
112 int swaptype
, swap_cnt
;
114 loop
: SWAPINIT(a
, es
);
117 for (pm
= (char *)a
+ es
; pm
< (char *)a
+ n
* es
; pm
+= es
)
119 pl
> (char *)a
&& CMP(thunk
, pl
- es
, pl
) > 0;
124 pm
= (char *)a
+ (n
/ 2) * es
;
127 pn
= (char *)a
+ (n
- 1) * es
;
130 pl
= med3(pl
, pl
+ d
, pl
+ 2 * d
, cmp
, thunk
);
131 pm
= med3(pm
- d
, pm
, pm
+ d
, cmp
, thunk
);
132 pn
= med3(pn
- 2 * d
, pn
- d
, pn
, cmp
, thunk
);
134 pm
= med3(pl
, pm
, pn
, cmp
, thunk
);
137 pa
= pb
= (char *)a
+ es
;
139 pc
= pd
= (char *)a
+ (n
- 1) * es
;
141 while (pb
<= pc
&& (cmp_result
= CMP(thunk
, pb
, a
)) <= 0) {
142 if (cmp_result
== 0) {
149 while (pb
<= pc
&& (cmp_result
= CMP(thunk
, pc
, a
)) >= 0) {
150 if (cmp_result
== 0) {
164 if (swap_cnt
== 0) { /* Switch to insertion sort */
165 for (pm
= (char *)a
+ es
; pm
< (char *)a
+ n
* es
; pm
+= es
)
167 pl
> (char *)a
&& CMP(thunk
, pl
- es
, pl
) > 0;
173 pn
= (char *)a
+ n
* es
;
174 r
= min(pa
- (char *)a
, pb
- pa
);
175 vecswap(a
, pb
- r
, r
);
176 r
= min(pd
- pc
, pn
- pd
- es
);
177 vecswap(pb
, pn
- r
, r
);
178 if ((r
= pb
- pa
) > es
)
180 qsort_r(a
, r
/ es
, es
, thunk
, cmp
);
182 qsort(a
, r
/ es
, es
, cmp
);
184 if ((r
= pd
- pc
) > es
) {
185 /* Iterate rather than recurse to save stack space */
190 /* qsort(pn - r, r / es, es, cmp);*/