![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to qsort.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / XNU / bsd / kern|
Return to qsort.c CVS log | Up to [Apple XNU] / XNU / bsd / kern |
1.1 root 1: /*
2: * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * The contents of this file constitute Original Code as defined in and
7: * are subject to the Apple Public Source License Version 1.1 (the
8: * "License"). You may not use this file except in compliance with the
9: * License. Please obtain a copy of the License at
10: * http://www.apple.com/publicsource and read it before using this file.
11: *
12: * This Original Code and all software distributed under the License are
13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17: * License for the specific language governing rights and limitations
18: * under the License.
19: *
20: * @APPLE_LICENSE_HEADER_END@
21: */
22: /*
23: * Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved
24: *
25: * Copyright (c) 1992, 1993
26: * The Regents of the University of California. All rights reserved.
27: *
28: * Redistribution and use in source and binary forms, with or without
29: * modification, are permitted provided that the following conditions
30: * are met:
31: * 1. Redistributions of source code must retain the above copyright
32: * notice, this list of conditions and the following disclaimer.
33: * 2. Redistributions in binary form must reproduce the above copyright
34: * notice, this list of conditions and the following disclaimer in the
35: * documentation and/or other materials provided with the distribution.
36: * 3. All advertising materials mentioning features or use of this software
37: * must display the following acknowledgement:
38: * This product includes software developed by the University of
39: * California, Berkeley and its contributors.
40: * 4. Neither the name of the University nor the names of its contributors
41: * may be used to endorse or promote products derived from this software
42: * without specific prior written permission.
43: *
44: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
45: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
46: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
47: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
48: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
49: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
50: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
51: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
52: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
53: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
54: * SUCH DAMAGE.
55: *
56: * @(#)qsort.c 8.1 (Berkeley) 6/4/93
57: */
58:
59:
60: #include <sys/types.h>
61: #include <stdlib.h>
62:
63: static inline char *med3 __P((char *, char *, char *, int (*)()));
64: static inline void swapfunc __P((char *, char *, int, int));
65:
66: #define min(a, b) (a) < (b) ? a : b
67:
68: /*
69: * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
70: */
71: #define swapcode(TYPE, parmi, parmj, n) { \
72: long i = (n) / sizeof (TYPE); \
73: register TYPE *pi = (TYPE *) (parmi); \
74: register TYPE *pj = (TYPE *) (parmj); \
75: do { \
76: register TYPE t = *pi; \
77: *pi++ = *pj; \
78: *pj++ = t; \
79: } while (--i > 0); \
80: }
81:
82: #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
83: es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
84:
85: static inline void
86: swapfunc(a, b, n, swaptype)
87: char *a, *b;
88: int n, swaptype;
89: {
90: if(swaptype <= 1)
91: swapcode(long, a, b, n)
92: else
93: swapcode(char, a, b, n)
94: }
95:
96: #define swap(a, b) \
97: if (swaptype == 0) { \
98: long t = *(long *)(a); \
99: *(long *)(a) = *(long *)(b); \
100: *(long *)(b) = t; \
101: } else \
102: swapfunc(a, b, es, swaptype)
103:
104: #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
105:
106: static inline char *
107: med3(a, b, c, cmp)
108: char *a, *b, *c;
109: int (*cmp)();
110: {
111: return cmp(a, b) < 0 ?
112: (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
113: :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
114: }
115:
116: void
117: qsort(a, n, es, cmp)
118: void *a;
119: size_t n, es;
120: int (*cmp)();
121: {
122: char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
123: int d, r, swaptype, swap_cnt;
124:
125: loop: SWAPINIT(a, es);
126: swap_cnt = 0;
127: if (n < 7) {
128: for (pm = a + es; pm < (char *) a + n * es; pm += es)
129: for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
130: pl -= es)
131: swap(pl, pl - es);
132: return;
133: }
134: pm = a + (n / 2) * es;
135: if (n > 7) {
136: pl = a;
137: pn = a + (n - 1) * es;
138: if (n > 40) {
139: d = (n / 8) * es;
140: pl = med3(pl, pl + d, pl + 2 * d, cmp);
141: pm = med3(pm - d, pm, pm + d, cmp);
142: pn = med3(pn - 2 * d, pn - d, pn, cmp);
143: }
144: pm = med3(pl, pm, pn, cmp);
145: }
146: swap(a, pm);
147: pa = pb = a + es;
148:
149: pc = pd = a + (n - 1) * es;
150: for (;;) {
151: while (pb <= pc && (r = cmp(pb, a)) <= 0) {
152: if (r == 0) {
153: swap_cnt = 1;
154: swap(pa, pb);
155: pa += es;
156: }
157: pb += es;
158: }
159: while (pb <= pc && (r = cmp(pc, a)) >= 0) {
160: if (r == 0) {
161: swap_cnt = 1;
162: swap(pc, pd);
163: pd -= es;
164: }
165: pc -= es;
166: }
167: if (pb > pc)
168: break;
169: swap(pb, pc);
170: swap_cnt = 1;
171: pb += es;
172: pc -= es;
173: }
174: if (swap_cnt == 0) { /* Switch to insertion sort */
175: for (pm = a + es; pm < (char *) a + n * es; pm += es)
176: for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
177: pl -= es)
178: swap(pl, pl - es);
179: return;
180: }
181:
182: pn = a + n * es;
183: r = min(pa - (char *)a, pb - pa);
184: vecswap(a, pb - r, r);
185: r = min(pd - pc, pn - pd - es);
186: vecswap(pb, pn - r, r);
187: if ((r = pb - pa) > es)
188: qsort(a, r / es, es, cmp);
189: if ((r = pd - pc) > es) {
190: /* Iterate rather than recurse to save stack space */
191: a = pn - r;
192: n = r / es;
193: goto loop;
194: }
195: /* qsort(pn - r, r / es, es, cmp);*/
196: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.