1 | /*- |
2 | * Copyright (c) 1992, 1993 |
3 | * The Regents of the University of California. All rights reserved. |
4 | * |
5 | * This code is derived from software contributed to Berkeley by |
6 | * Peter McIlroy. |
7 | * |
8 | * Redistribution and use in source and binary forms, with or without |
9 | * modification, are permitted provided that the following conditions |
10 | * are met: |
11 | * 1. Redistributions of source code must retain the above copyright |
12 | * notice, this list of conditions and the following disclaimer. |
13 | * 2. Redistributions in binary form must reproduce the above copyright |
14 | * notice, this list of conditions and the following disclaimer in the |
15 | * documentation and/or other materials provided with the distribution. |
16 | * 3. All advertising materials mentioning features or use of this software |
17 | * must display the following acknowledgement: |
18 | * This product includes software developed by the University of |
19 | * California, Berkeley and its contributors. |
20 | * 4. Neither the name of the University nor the names of its contributors |
21 | * may be used to endorse or promote products derived from this software |
22 | * without specific prior written permission. |
23 | * |
24 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
25 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
26 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
27 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
28 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
29 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
30 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
31 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
32 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
33 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
34 | * SUCH DAMAGE. |
35 | */ |
36 | |
37 | /* $Id$ */ |
38 | |
39 | #if defined(LIBC_SCCS) && !defined(lint) |
40 | static char sccsid[] = "@(#)merge.c 8.2 (Berkeley) 2/14/94" ; |
41 | #endif /* LIBC_SCCS and not lint */ |
42 | |
43 | /* |
44 | * Hybrid exponential search/linear search merge sort with hybrid |
45 | * natural/pairwise first pass. Requires about .3% more comparisons |
46 | * for random data than LSMS with pairwise first pass alone. |
47 | * It works for objects as small as two bytes. |
48 | */ |
49 | |
50 | #define NATURAL |
51 | #define THRESHOLD 16 /* Best choice for natural merge cut-off. */ |
52 | |
53 | /* #define NATURAL to get hybrid natural merge. |
54 | * (The default is pairwise merging.) |
55 | */ |
56 | |
57 | #include <sys/types.h> |
58 | |
59 | #include <errno.h> |
60 | #include <stdlib.h> |
61 | #include <string.h> |
62 | |
63 | #include "php.h" |
64 | |
65 | #ifdef PHP_WIN32 |
66 | #include <winsock2.h> /* Includes definition for u_char */ |
67 | #endif |
68 | |
69 | static void setup(u_char *list1, u_char *list2, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC); |
70 | static void insertionsort(u_char *a, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC); |
71 | |
72 | #define ISIZE sizeof(int) |
73 | #define PSIZE sizeof(u_char *) |
74 | #define ICOPY_LIST(src, dst, last) \ |
75 | do \ |
76 | *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE; \ |
77 | while(src < last) |
78 | #define ICOPY_ELT(src, dst, i) \ |
79 | do \ |
80 | *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE; \ |
81 | while (i -= ISIZE) |
82 | |
83 | #define CCOPY_LIST(src, dst, last) \ |
84 | do \ |
85 | *dst++ = *src++; \ |
86 | while (src < last) |
87 | #define CCOPY_ELT(src, dst, i) \ |
88 | do \ |
89 | *dst++ = *src++; \ |
90 | while (i -= 1) |
91 | |
92 | /* |
93 | * Find the next possible pointer head. (Trickery for forcing an array |
94 | * to do double duty as a linked list when objects do not align with word |
95 | * boundaries. |
96 | */ |
97 | /* Assumption: PSIZE is a power of 2. */ |
98 | #define EVAL(p) (u_char **) \ |
99 | ((u_char *)0 + \ |
100 | (((u_char *)p + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1))) |
101 | |
102 | /* {{{ php_mergesort |
103 | * Arguments are as for qsort. |
104 | */ |
105 | PHPAPI int php_mergesort(void *base, size_t nmemb, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC) |
106 | { |
107 | register unsigned int i; |
108 | register int sense; |
109 | int big, iflag; |
110 | register u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2; |
111 | u_char *list2, *list1, *p2, *p, *last, **p1; |
112 | |
113 | if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */ |
114 | errno = EINVAL; |
115 | return (-1); |
116 | } |
117 | |
118 | if (nmemb == 0) |
119 | return (0); |
120 | |
121 | /* |
122 | * XXX |
123 | * Stupid subtraction for the Cray. |
124 | */ |
125 | iflag = 0; |
126 | if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE)) |
127 | iflag = 1; |
128 | |
129 | if ((list2 = malloc(nmemb * size + PSIZE)) == NULL) |
130 | return (-1); |
131 | |
132 | list1 = base; |
133 | setup(list1, list2, nmemb, size, cmp TSRMLS_CC); |
134 | last = list2 + nmemb * size; |
135 | i = big = 0; |
136 | while (*EVAL(list2) != last) { |
137 | l2 = list1; |
138 | p1 = EVAL(list1); |
139 | for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) { |
140 | p2 = *EVAL(p2); |
141 | f1 = l2; |
142 | f2 = l1 = list1 + (p2 - list2); |
143 | if (p2 != last) |
144 | p2 = *EVAL(p2); |
145 | l2 = list1 + (p2 - list2); |
146 | while (f1 < l1 && f2 < l2) { |
147 | if ((*cmp)(f1, f2 TSRMLS_CC) <= 0) { |
148 | q = f2; |
149 | b = f1, t = l1; |
150 | sense = -1; |
151 | } else { |
152 | q = f1; |
153 | b = f2, t = l2; |
154 | sense = 0; |
155 | } |
156 | if (!big) { /* here i = 0 */ |
157 | while ((b += size) < t && cmp(q, b TSRMLS_CC) >sense) |
158 | if (++i == 6) { |
159 | big = 1; |
160 | goto EXPONENTIAL; |
161 | } |
162 | } else { |
163 | EXPONENTIAL: for (i = size; ; i <<= 1) |
164 | if ((p = (b + i)) >= t) { |
165 | if ((p = t - size) > b && |
166 | (*cmp)(q, p TSRMLS_CC) <= sense) |
167 | t = p; |
168 | else |
169 | b = p; |
170 | break; |
171 | } else if ((*cmp)(q, p TSRMLS_CC) <= sense) { |
172 | t = p; |
173 | if (i == size) |
174 | big = 0; |
175 | goto FASTCASE; |
176 | } else |
177 | b = p; |
178 | while (t > b+size) { |
179 | i = (((t - b) / size) >> 1) * size; |
180 | if ((*cmp)(q, p = b + i TSRMLS_CC) <= sense) |
181 | t = p; |
182 | else |
183 | b = p; |
184 | } |
185 | goto COPY; |
186 | FASTCASE: while (i > size) |
187 | if ((*cmp)(q, |
188 | p = b + (i >>= 1) TSRMLS_CC) <= sense) |
189 | t = p; |
190 | else |
191 | b = p; |
192 | COPY: b = t; |
193 | } |
194 | i = size; |
195 | if (q == f1) { |
196 | if (iflag) { |
197 | ICOPY_LIST(f2, tp2, b); |
198 | ICOPY_ELT(f1, tp2, i); |
199 | } else { |
200 | CCOPY_LIST(f2, tp2, b); |
201 | CCOPY_ELT(f1, tp2, i); |
202 | } |
203 | } else { |
204 | if (iflag) { |
205 | ICOPY_LIST(f1, tp2, b); |
206 | ICOPY_ELT(f2, tp2, i); |
207 | } else { |
208 | CCOPY_LIST(f1, tp2, b); |
209 | CCOPY_ELT(f2, tp2, i); |
210 | } |
211 | } |
212 | } |
213 | if (f2 < l2) { |
214 | if (iflag) |
215 | ICOPY_LIST(f2, tp2, l2); |
216 | else |
217 | CCOPY_LIST(f2, tp2, l2); |
218 | } else if (f1 < l1) { |
219 | if (iflag) |
220 | ICOPY_LIST(f1, tp2, l1); |
221 | else |
222 | CCOPY_LIST(f1, tp2, l1); |
223 | } |
224 | *p1 = l2; |
225 | } |
226 | tp2 = list1; /* swap list1, list2 */ |
227 | list1 = list2; |
228 | list2 = tp2; |
229 | last = list2 + nmemb*size; |
230 | } |
231 | if (base == list2) { |
232 | memmove(list2, list1, nmemb*size); |
233 | list2 = list1; |
234 | } |
235 | free(list2); |
236 | return (0); |
237 | } |
238 | /* }}} */ |
239 | |
240 | #define swap(a, b) { \ |
241 | s = b; \ |
242 | i = size; \ |
243 | do { \ |
244 | tmp = *a; *a++ = *s; *s++ = tmp; \ |
245 | } while (--i); \ |
246 | a -= size; \ |
247 | } |
248 | #define reverse(bot, top) { \ |
249 | s = top; \ |
250 | do { \ |
251 | i = size; \ |
252 | do { \ |
253 | tmp = *bot; *bot++ = *s; *s++ = tmp; \ |
254 | } while (--i); \ |
255 | s -= size2; \ |
256 | } while(bot < s); \ |
257 | } |
258 | |
259 | /* {{{ setup |
260 | * Optional hybrid natural/pairwise first pass. Eats up list1 in runs of |
261 | * increasing order, list2 in a corresponding linked list. Checks for runs |
262 | * when THRESHOLD/2 pairs compare with same sense. (Only used when NATURAL |
263 | * is defined. Otherwise simple pairwise merging is used.) |
264 | */ |
265 | static void setup(u_char *list1, u_char *list2, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC) |
266 | { |
267 | int i, length, size2, tmp, sense; |
268 | u_char *f1, *f2, *s, *l2, *last, *p2; |
269 | |
270 | size2 = size*2; |
271 | if (n <= 5) { |
272 | insertionsort(list1, n, size, cmp TSRMLS_CC); |
273 | *EVAL(list2) = (u_char*) list2 + n*size; |
274 | return; |
275 | } |
276 | /* |
277 | * Avoid running pointers out of bounds; limit n to evens |
278 | * for simplicity. |
279 | */ |
280 | i = 4 + (n & 1); |
281 | insertionsort(list1 + (n - i) * size, i, size, cmp TSRMLS_CC); |
282 | last = list1 + size * (n - i); |
283 | *EVAL(list2 + (last - list1)) = list2 + n * size; |
284 | |
285 | #ifdef NATURAL |
286 | p2 = list2; |
287 | f1 = list1; |
288 | sense = (cmp(f1, f1 + size TSRMLS_CC) > 0); |
289 | for (; f1 < last; sense = !sense) { |
290 | length = 2; |
291 | /* Find pairs with same sense. */ |
292 | for (f2 = f1 + size2; f2 < last; f2 += size2) { |
293 | if ((cmp(f2, f2+ size TSRMLS_CC) > 0) != sense) |
294 | break; |
295 | length += 2; |
296 | } |
297 | if (length < THRESHOLD) { /* Pairwise merge */ |
298 | do { |
299 | p2 = *EVAL(p2) = f1 + size2 - list1 + list2; |
300 | if (sense > 0) |
301 | swap (f1, f1 + size); |
302 | } while ((f1 += size2) < f2); |
303 | } else { /* Natural merge */ |
304 | l2 = f2; |
305 | for (f2 = f1 + size2; f2 < l2; f2 += size2) { |
306 | if ((cmp(f2-size, f2 TSRMLS_CC) > 0) != sense) { |
307 | p2 = *EVAL(p2) = f2 - list1 + list2; |
308 | if (sense > 0) |
309 | reverse(f1, f2-size); |
310 | f1 = f2; |
311 | } |
312 | } |
313 | if (sense > 0) |
314 | reverse (f1, f2-size); |
315 | f1 = f2; |
316 | if (f2 < last || cmp(f2 - size, f2 TSRMLS_CC) > 0) |
317 | p2 = *EVAL(p2) = f2 - list1 + list2; |
318 | else |
319 | p2 = *EVAL(p2) = list2 + n*size; |
320 | } |
321 | } |
322 | #else /* pairwise merge only. */ |
323 | for (f1 = list1, p2 = list2; f1 < last; f1 += size2) { |
324 | p2 = *EVAL(p2) = p2 + size2; |
325 | if (cmp (f1, f1 + size TSRMLS_CC) > 0) |
326 | swap(f1, f1 + size); |
327 | } |
328 | #endif /* NATURAL */ |
329 | } |
330 | /* }}} */ |
331 | |
332 | /* {{{ insertionsort |
333 | * This is to avoid out-of-bounds addresses in sorting the |
334 | * last 4 elements. |
335 | */ |
336 | static void insertionsort(u_char *a, size_t n, size_t size, int (*cmp)(const void *, const void * TSRMLS_DC) TSRMLS_DC) |
337 | { |
338 | u_char *ai, *s, *t, *u, tmp; |
339 | int i; |
340 | |
341 | for (ai = a+size; --n >= 1; ai += size) |
342 | for (t = ai; t > a; t -= size) { |
343 | u = t - size; |
344 | if (cmp(u, t TSRMLS_CC) <= 0) |
345 | break; |
346 | swap(u, t); |
347 | } |
348 | } |
349 | /* }}} */ |
350 | |
351 | /* |
352 | * Local variables: |
353 | * tab-width: 4 |
354 | * c-basic-offset: 4 |
355 | * End: |
356 | * vim600: fdm=marker |
357 | * vim: noet sw=4 ts=4 |
358 | */ |
359 | |