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