scoutos / prex-0.9.0 / usr / lib / libc / stdlib / qsort.c @ 03e9c04a
History | View | Annotate | Download (4.73 KB)
1 | 03e9c04a | Brad Neuman | /*-
|
---|---|---|---|
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 | } |