* 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
* 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.
* 3. All advertising materials mentioning features or use of this software
* must display the following acknowledgement:
* This product includes software developed by the University of
* California, Berkeley and its contributors.
* 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
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
#endif /* LIBC_SCCS and not lint */
static inline char *med3
__P((char *, char *, char *, int (*)()));
static inline void swapfunc
__P((char *, char *, int, int));
#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); \
register TYPE *pi = (TYPE *) (parmi); \
register TYPE *pj = (TYPE *) (parmj); \
#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
swapfunc(a
, b
, n
, swaptype
)
*(long *)(a) = *(long *)(b); \
swapfunc(a, b, es, swaptype)
#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
(cmp(b
, c
) < 0 ? b
: (cmp(a
, c
) < 0 ? c
: a
))
:(cmp(b
, c
) > 0 ? b
: (cmp(a
, c
) < 0 ? a
: c
));
char *pa
, *pb
, *pc
, *pd
, *pl
, *pm
, *pn
;
int d
, r
, swaptype
, swap_cnt
;
for (pm
= a
+ es
; pm
< (char *) a
+ n
* es
; pm
+= es
)
for (pl
= pm
; pl
> (char *) a
&& cmp(pl
- es
, pl
) > 0;
pl
= med3(pl
, pl
+ d
, pl
+ 2 * d
, cmp
);
pm
= med3(pm
- d
, pm
, pm
+ d
, cmp
);
pn
= med3(pn
- 2 * d
, pn
- d
, pn
, cmp
);
pm
= med3(pl
, pm
, pn
, cmp
);
pc
= pd
= a
+ (n
- 1) * es
;
while (pb
<= pc
&& (r
= cmp(pb
, a
)) <= 0) {
while (pb
<= pc
&& (r
= cmp(pc
, a
)) >= 0) {
if (swap_cnt
== 0) { /* Switch to insertion sort */
for (pm
= a
+ es
; pm
< (char *) a
+ n
* es
; pm
+= es
)
for (pl
= pm
; pl
> (char *) a
&& cmp(pl
- es
, pl
) > 0;
r
= min(pa
- (char *)a
, pb
- pa
);
r
= min(pd
- pc
, pn
- pd
- es
);
qsort(a
, r
/ es
, es
, cmp
);
if ((r
= pd
- pc
) > es
) {
/* Iterate rather than recurse to save stack space */
/* qsort(pn - r, r / es, es, cmp);*/