1 /* $NetBSD: qsort.c,v 1.22 2012/05/26 21:47:05 christos Exp $ */
4 * Copyright (c) 1992, 1993
5 * The Regents of the University of California. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 #include <sys/cdefs.h>
33 #if defined(LIBC_SCCS) && !defined(lint)
35 static char sccsid
[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
37 __RCSID("$NetBSD: qsort.c,v 1.22 2012/05/26 21:47:05 christos Exp $");
39 #endif /* LIBC_SCCS and not lint */
41 #include <sys/types.h>
47 static inline char *med3(char *, char *, char *,
48 int (*)(const void *, const void *));
49 static inline void swapfunc(char *, char *, size_t, int);
51 #define min(a, b) (a) < (b) ? a : b
54 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
56 #define swapcode(TYPE, parmi, parmj, n) { \
57 size_t i = (n) / sizeof (TYPE); \
58 TYPE *pi = (TYPE *)(void *)(parmi); \
59 TYPE *pj = (TYPE *)(void *)(parmj); \
67 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
68 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
71 swapfunc(char *a
, char *b
, size_t n
, int swaptype
)
75 swapcode(long, a
, b
, n
)
77 swapcode(char, a
, b
, n
)
81 if (swaptype == 0) { \
82 long t = *(long *)(void *)(a); \
83 *(long *)(void *)(a) = *(long *)(void *)(b); \
84 *(long *)(void *)(b) = t; \
86 swapfunc(a, b, es, swaptype)
88 #define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n), swaptype)
91 med3(char *a
, char *b
, char *c
,
92 int (*cmp
)(const void *, const void *))
95 return cmp(a
, b
) < 0 ?
96 (cmp(b
, c
) < 0 ? b
: (cmp(a
, c
) < 0 ? c
: a
))
97 :(cmp(b
, c
) > 0 ? b
: (cmp(a
, c
) < 0 ? a
: c
));
101 qsort(void *a
, size_t n
, size_t es
,
102 int (*cmp
)(const void *, const void *))
104 char *pa
, *pb
, *pc
, *pd
, *pl
, *pm
, *pn
;
106 int swaptype
, cmp_result
;
108 _DIAGASSERT(a
!= NULL
|| n
== 0 || es
== 0);
109 _DIAGASSERT(cmp
!= NULL
);
111 loop
: SWAPINIT(a
, es
);
113 for (pm
= (char *) a
+ es
; pm
< (char *) a
+ n
* es
; pm
+= es
)
114 for (pl
= pm
; pl
> (char *) a
&& cmp(pl
- es
, pl
) > 0;
119 pm
= (char *) a
+ (n
/ 2) * es
;
122 pn
= (char *) a
+ (n
- 1) * es
;
125 pl
= med3(pl
, pl
+ d
, pl
+ 2 * d
, cmp
);
126 pm
= med3(pm
- d
, pm
, pm
+ d
, cmp
);
127 pn
= med3(pn
- 2 * d
, pn
- d
, pn
, cmp
);
129 pm
= med3(pl
, pm
, pn
, cmp
);
132 pa
= pb
= (char *) a
+ es
;
134 pc
= pd
= (char *) a
+ (n
- 1) * es
;
136 while (pb
<= pc
&& (cmp_result
= cmp(pb
, a
)) <= 0) {
137 if (cmp_result
== 0) {
143 while (pb
<= pc
&& (cmp_result
= cmp(pc
, a
)) >= 0) {
144 if (cmp_result
== 0) {
157 pn
= (char *) a
+ n
* es
;
158 r
= min(pa
- (char *) a
, pb
- pa
);
159 vecswap(a
, pb
- r
, r
);
160 r
= min((size_t)(pd
- pc
), pn
- pd
- es
);
161 vecswap(pb
, pn
- r
, r
);
162 if ((r
= pb
- pa
) > es
)
163 qsort(a
, r
/ es
, es
, cmp
);
164 if ((r
= pd
- pc
) > es
) {
165 /* Iterate rather than recurse to save stack space */
170 /* qsort(pn - r, r / es, es, cmp);*/