![[BACK]](/icons/back.gif){kind=icon}
Return to qsort.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / prex-old / usr / lib / libc / stdlib|
Return to qsort.c CVS log | Up to [local] / prex-old / usr / lib / libc / stdlib |
1.1 nbrk 1: /*-
2: * Copyright (c) 1992, 1993
3: * The Regents of the University of California. All rights reserved.
4: *
5: * Redistribution and use in source and binary forms, with or without
6: * modification, are permitted provided that the following conditions
7: * are met:
8: * 1. Redistributions of source code must retain the above copyright
9: * notice, this list of conditions and the following disclaimer.
10: * 2. Redistributions in binary form must reproduce the above copyright
11: * notice, this list of conditions and the following disclaimer in the
12: * documentation and/or other materials provided with the distribution.
13: * 3. Neither the name of the University nor the names of its contributors
14: * may be used to endorse or promote products derived from this software
15: * without specific prior written permission.
16: *
17: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27: * SUCH DAMAGE.
28: */
29:
30: #include <sys/cdefs.h>
31: #include <sys/types.h>
32:
33: #include <assert.h>
34: #include <errno.h>
35: #include <stdlib.h>
36:
37: static __inline char *med3(char *, char *, char *,
38: int (*)(const void *, const void *));
39: static __inline void swapfunc(char *, char *, size_t, int);
40:
41: #define min(a, b) (a) < (b) ? a : b
42:
43: /*
44: * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
45: */
46: #define swapcode(TYPE, parmi, parmj, n) { \
47: size_t i = (n) / sizeof (TYPE); \
48: TYPE *pi = (TYPE *)(void *)(parmi); \
49: TYPE *pj = (TYPE *)(void *)(parmj); \
50: do { \
51: TYPE t = *pi; \
52: *pi++ = *pj; \
53: *pj++ = t; \
54: } while (--i > 0); \
55: }
56:
57: #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
58: es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
59:
60: static __inline void
61: swapfunc(a, b, n, swaptype)
62: char *a, *b;
63: size_t n;
64: int swaptype;
65: {
66: if (swaptype <= 1)
67: swapcode(long, a, b, n)
68: else
69: swapcode(char, a, b, n)
70: }
71:
72: #define swap(a, b) \
73: if (swaptype == 0) { \
74: long t = *(long *)(void *)(a); \
75: *(long *)(void *)(a) = *(long *)(void *)(b); \
76: *(long *)(void *)(b) = t; \
77: } else \
78: swapfunc(a, b, es, swaptype)
79:
80: #define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n), swaptype)
81:
82: static __inline char *
83: med3(a, b, c, cmp)
84: char *a, *b, *c;
85: int (*cmp)(const void *, const void *);
86: {
87: return cmp(a, b) < 0 ?
88: (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
89: :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
90: }
91:
92: void
93: qsort(a, n, es, cmp)
94: void *a;
95: size_t n, es;
96: int (*cmp)(const void *, const void *);
97: {
98: char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
99: int d, r, swaptype, swap_cnt;
100:
101: loop: SWAPINIT(a, es);
102: swap_cnt = 0;
103: if (n < 7) {
104: for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
105: for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
106: pl -= es)
107: swap(pl, pl - es);
108: return;
109: }
110: pm = (char *) a + (n / 2) * es;
111: if (n > 7) {
112: pl = (char *) a;
113: pn = (char *) a + (n - 1) * es;
114: if (n > 40) {
115: d = (n / 8) * es;
116: pl = med3(pl, pl + d, pl + 2 * d, cmp);
117: pm = med3(pm - d, pm, pm + d, cmp);
118: pn = med3(pn - 2 * d, pn - d, pn, cmp);
119: }
120: pm = med3(pl, pm, pn, cmp);
121: }
122: swap(a, pm);
123: pa = pb = (char *) a + es;
124:
125: pc = pd = (char *) a + (n - 1) * es;
126: for (;;) {
127: while (pb <= pc && (r = cmp(pb, a)) <= 0) {
128: if (r == 0) {
129: swap_cnt = 1;
130: swap(pa, pb);
131: pa += es;
132: }
133: pb += es;
134: }
135: while (pb <= pc && (r = cmp(pc, a)) >= 0) {
136: if (r == 0) {
137: swap_cnt = 1;
138: swap(pc, pd);
139: pd -= es;
140: }
141: pc -= es;
142: }
143: if (pb > pc)
144: break;
145: swap(pb, pc);
146: swap_cnt = 1;
147: pb += es;
148: pc -= es;
149: }
150: if (swap_cnt == 0) { /* Switch to insertion sort */
151: for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
152: for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
153: pl -= es)
154: swap(pl, pl - es);
155: return;
156: }
157: pn = (char *) a + n * es;
158: r = min(pa - (char *) a, pb - pa);
159: vecswap(a, pb - r, r);
160: r = min(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 */
166: a = pn - r;
167: n = r / es;
168: goto loop;
169: }
170: /* qsort(pn - r, r / es, es, cmp);*/
171: }