![[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 Darwin 0.x] / kernel / bsd / kern|
Return to qsort.c CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / kern |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: * Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved
27: *
28: * Copyright (c) 1992, 1993
29: * The Regents of the University of California. All rights reserved.
30: *
31: * The NEXTSTEP Software License Agreement specifies the terms
32: * and conditions for redistribution.
33: *
34: * @(#)qsort.c 8.1 (Berkeley) 6/4/93
35: */
36:
37:
38: #include <sys/types.h>
39: #include <stdlib.h>
40:
41: static inline char *med3 __P((char *, char *, char *, int (*)()));
42: static inline void swapfunc __P((char *, char *, int, int));
43:
44: #define min(a, b) (a) < (b) ? a : b
45:
46: /*
47: * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
48: */
49: #define swapcode(TYPE, parmi, parmj, n) { \
50: long i = (n) / sizeof (TYPE); \
51: register TYPE *pi = (TYPE *) (parmi); \
52: register TYPE *pj = (TYPE *) (parmj); \
53: do { \
54: register TYPE t = *pi; \
55: *pi++ = *pj; \
56: *pj++ = t; \
57: } while (--i > 0); \
58: }
59:
60: #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
61: es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
62:
63: static inline void
64: swapfunc(a, b, n, swaptype)
65: char *a, *b;
66: int n, swaptype;
67: {
68: if(swaptype <= 1)
69: swapcode(long, a, b, n)
70: else
71: swapcode(char, a, b, n)
72: }
73:
74: #define swap(a, b) \
75: if (swaptype == 0) { \
76: long t = *(long *)(a); \
77: *(long *)(a) = *(long *)(b); \
78: *(long *)(b) = t; \
79: } else \
80: swapfunc(a, b, es, swaptype)
81:
82: #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
83:
84: static inline char *
85: med3(a, b, c, cmp)
86: char *a, *b, *c;
87: int (*cmp)();
88: {
89: return cmp(a, b) < 0 ?
90: (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
91: :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
92: }
93:
94: void
95: qsort(a, n, es, cmp)
96: void *a;
97: size_t n, es;
98: int (*cmp)();
99: {
100: char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
101: int d, r, swaptype, swap_cnt;
102:
103: loop: SWAPINIT(a, es);
104: swap_cnt = 0;
105: if (n < 7) {
106: for (pm = a + es; pm < (char *) a + n * es; pm += es)
107: for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
108: pl -= es)
109: swap(pl, pl - es);
110: return;
111: }
112: pm = a + (n / 2) * es;
113: if (n > 7) {
114: pl = a;
115: pn = a + (n - 1) * es;
116: if (n > 40) {
117: d = (n / 8) * es;
118: pl = med3(pl, pl + d, pl + 2 * d, cmp);
119: pm = med3(pm - d, pm, pm + d, cmp);
120: pn = med3(pn - 2 * d, pn - d, pn, cmp);
121: }
122: pm = med3(pl, pm, pn, cmp);
123: }
124: swap(a, pm);
125: pa = pb = a + es;
126:
127: pc = pd = a + (n - 1) * es;
128: for (;;) {
129: while (pb <= pc && (r = cmp(pb, a)) <= 0) {
130: if (r == 0) {
131: swap_cnt = 1;
132: swap(pa, pb);
133: pa += es;
134: }
135: pb += es;
136: }
137: while (pb <= pc && (r = cmp(pc, a)) >= 0) {
138: if (r == 0) {
139: swap_cnt = 1;
140: swap(pc, pd);
141: pd -= es;
142: }
143: pc -= es;
144: }
145: if (pb > pc)
146: break;
147: swap(pb, pc);
148: swap_cnt = 1;
149: pb += es;
150: pc -= es;
151: }
152: if (swap_cnt == 0) { /* Switch to insertion sort */
153: for (pm = a + es; pm < (char *) a + n * es; pm += es)
154: for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
155: pl -= es)
156: swap(pl, pl - es);
157: return;
158: }
159:
160: pn = a + n * es;
161: r = min(pa - (char *)a, pb - pa);
162: vecswap(a, pb - r, r);
163: r = min(pd - pc, pn - pd - es);
164: vecswap(pb, pn - r, r);
165: if ((r = pb - pa) > es)
166: qsort(a, r / es, es, cmp);
167: if ((r = pd - pc) > es) {
168: /* Iterate rather than recurse to save stack space */
169: a = pn - r;
170: n = r / es;
171: goto loop;
172: }
173: /* qsort(pn - r, r / es, es, cmp);*/
174: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.