]> git.saurik.com Git - apple/cf.git/blob - CFSortFunctions.c
projects / apple / cf.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
CF-476.10.tar.gz
[apple/cf.git] / CFSortFunctions.c
1 /*
2 * Copyright (c) 2008 Apple Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23 /* CFSortFunctions.c
24 Copyright 1999-2007, Apple, Inc. All rights reserved.
25 Responsibility: Christopher Kane
26 */
27
28 /* This file contains code copied from the Libc project's files
29 qsort.c and merge.c, and modified to suit the
30 needs of CF, which needs the comparison callback to have an
31 additional parameter. The code is collected into this one
32 file so that the individual BSD sort routines can remain
33 private and static.
34 */
35
36 #include <CoreFoundation/CFBase.h>
37 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_LINUX || DEPLOYMENT_TARGET_FREEBSD
38 #include <sys/types.h>
39 #else
40 #define EINVAL 22
41 #endif
42 #include "CFInternal.h"
43
44
45 /* stdlib.subproj/qsort.c ============================================== */
46
47 /*-
48 * Copyright (c) 1992, 1993
49 * The Regents of the University of California. All rights reserved.
50 *
51 * Redistribution and use in source and binary forms, with or without
52 * modification, are permitted provided that the following conditions
53 * are met:
54 * 1. Redistributions of source code must retain the above copyright
55 * notice, this list of conditions and the following disclaimer.
56 * 2. Redistributions in binary form must reproduce the above copyright
57 * notice, this list of conditions and the following disclaimer in the
58 * documentation and/or other materials provided with the distribution.
59 * 3. All advertising materials mentioning features or use of this software
60 * must display the following acknowledgement:
61 * This product includes software developed by the University of
62 * California, Berkeley and its contributors.
63 * 4. Neither the name of the University nor the names of its contributors
64 * may be used to endorse or promote products derived from this software
65 * without specific prior written permission.
66 *
67 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
68 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
69 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
70 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
71 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
72 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
73 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
74 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
75 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
76 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
77 * SUCH DAMAGE.
78 */
79
80 #if 0
81 #if defined(LIBC_SCCS) && !defined(lint)
82 static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
83 #endif /* LIBC_SCCS and not lint */
84 #include <sys/cdefs.h>
85 __FBSDID("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.12 2002/09/10 02:04:49 wollman Exp $");
86 #endif
87
88 #include <stdlib.h>
89
90 #ifdef I_AM_QSORT_R
91 typedef int cmp_t(void *, const void *, const void *);
92 #else
93 typedef CFComparisonResult cmp_t(const void *, const void *, void *);
94 #endif
95 static inline char *med3(char *, char *, char *, cmp_t *, void *);
96 static inline void swapfunc(char *, char *, long, long);
97
98 #if !defined(min)
99 #define min(a, b) (a) < (b) ? a : b
100 #endif
101 /*
102 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
103 */
104 #define swapcode(TYPE, parmi, parmj, n) { \
105 long i = (n) / sizeof (TYPE); \
106 TYPE *pi = (TYPE *) (parmi); \
107 TYPE *pj = (TYPE *) (parmj); \
108 do { \
109 TYPE t = *pi; \
110 *pi++ = *pj; \
111 *pj++ = t; \
112 } while (--i > 0); \
113 }
114
115 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
116 es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
117
118 static inline void
119 swapfunc(char *a, char *b, long n, long swaptype)
120 {
121 if(swaptype <= 1)
122 swapcode(long, a, b, n)
123 else
124 swapcode(char, a, b, n)
125 }
126
127 #define swap(a, b) \
128 if (swaptype == 0) { \
129 long t = *(long *)(a); \
130 *(long *)(a) = *(long *)(b); \
131 *(long *)(b) = t; \
132 } else \
133 swapfunc(a, b, es, swaptype)
134
135 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
136
137 #ifdef I_AM_QSORT_R
138 #define CMP(t, x, y) (cmp((t), (x), (y)))
139 #else
140 #define CMP(t, x, y) (cmp((x), (y), (t)))
141 #endif
142
143 static inline char *
144 med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk)
145 {
146 return CMP(thunk, a, b) < 0 ?
147 (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a ))
148 :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c ));
149 }
150
151 #ifdef I_AM_QSORT_R
152 void
153 qsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp)
154 #else
155 static void
156 bsd_qsort(void *a, size_t n, size_t es, cmp_t *cmp, void *thunk)
157 #endif
158 {
159 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
160 long d, r, swaptype, swap_cnt;
161
162 loop: SWAPINIT(a, es);
163 swap_cnt = 0;
164 if (n < 7) {
165 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
166 for (pl = pm;
167 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
168 pl -= es)
169 swap(pl, pl - es);
170 return;
171 }
172 pm = (char *)a + (n / 2) * es;
173 if (n > 7) {
174 pl = a;
175 pn = (char *)a + (n - 1) * es;
176 if (n > 40) {
177 d = (n / 8) * es;
178 pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
179 pm = med3(pm - d, pm, pm + d, cmp, thunk);
180 pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
181 }
182 pm = med3(pl, pm, pn, cmp, thunk);
183 }
184 swap(a, pm);
185 pa = pb = (char *)a + es;
186
187 pc = pd = (char *)a + (n - 1) * es;
188 for (;;) {
189 while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
190 if (r == 0) {
191 swap_cnt = 1;
192 swap(pa, pb);
193 pa += es;
194 }
195 pb += es;
196 }
197 while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
198 if (r == 0) {
199 swap_cnt = 1;
200 swap(pc, pd);
201 pd -= es;
202 }
203 pc -= es;
204 }
205 if (pb > pc)
206 break;
207 swap(pb, pc);
208 swap_cnt = 1;
209 pb += es;
210 pc -= es;
211 }
212 if (swap_cnt == 0) { /* Switch to insertion sort */
213 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
214 for (pl = pm;
215 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
216 pl -= es)
217 swap(pl, pl - es);
218 return;
219 }
220
221 pn = (char *)a + n * es;
222 r = min(pa - (char *)a, pb - pa);
223 vecswap(a, pb - r, r);
224 r = min(pd - pc, pn - pd - es);
225 vecswap(pb, pn - r, r);
226 if ((r = pb - pa) > es)
227 #ifdef I_AM_QSORT_R
228 qsort_r(a, r / es, es, thunk, cmp);
229 #else
230 bsd_qsort(a, r / es, es, cmp, thunk);
231 #endif
232 if ((r = pd - pc) > es) {
233 /* Iterate rather than recurse to save stack space */
234 a = pn - r;
235 n = r / es;
236 goto loop;
237 }
238 /* qsort(pn - r, r / es, es, cmp);*/
239 }
240
241
242 /* And now for something not so completely different, a copy/paste version that uses write-barriers so as to notify GC as necessary of changes */
243 #define ASSIGN __CFObjCStrongAssign
244 //#define ASSIGN objc_assign_strongCast
245
246 #define swapcode_wb(TYPE, parmi, parmj, n) { \
247 long i = (n) / sizeof (TYPE); \
248 TYPE *pi = (TYPE *) (parmi); \
249 TYPE *pj = (TYPE *) (parmj); \
250 do { \
251 TYPE t = *pi; \
252 ASSIGN(*pj, pi++); \
253 ASSIGN(t, pj++); \
254 } while (--i > 0); \
255 }
256
257
258 static inline void
259 swapfunc_wb(char *a, char *b, long n, long swaptype)
260 {
261 if(swaptype <= 1)
262 swapcode_wb(void *, a, b, n)
263 else
264 swapcode(char, a, b, n)
265 }
266
267 #define swap_wb(a, b) \
268 if (swaptype == 0) { \
269 const void *t = *(const void **)(a); \
270 ASSIGN(*(void **)(b), (const void **)a); \
271 ASSIGN(t, (const void **)(b)); \
272 } else \
273 printf("bad things happening\n");
274 //swapfunc_wb(a, b, es, swaptype)
275
276 #define vecswap_wb(a, b, n) if ((n) > 0) swapfunc_wb(a, b, n, swaptype)
277
278 static void
279 bsd_qsort_wb(void *a, size_t n, size_t es, cmp_t *cmp, void *thunk)
280 {
281 char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
282 long d, r, swaptype, swap_cnt;
283
284 loop: SWAPINIT(a, es);
285 swap_cnt = 0;
286 if (n < 7) {
287 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
288 for (pl = pm;
289 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
290 pl -= es)
291 swap_wb(pl, pl - es);
292 return;
293 }
294 pm = (char *)a + (n / 2) * es;
295 if (n > 7) {
296 pl = a;
297 pn = (char *)a + (n - 1) * es;
298 if (n > 40) {
299 d = (n / 8) * es;
300 pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk);
301 pm = med3(pm - d, pm, pm + d, cmp, thunk);
302 pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk);
303 }
304 pm = med3(pl, pm, pn, cmp, thunk);
305 }
306 swap_wb(a, pm);
307 pa = pb = (char *)a + es;
308
309 pc = pd = (char *)a + (n - 1) * es;
310 for (;;) {
311 while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) {
312 if (r == 0) {
313 swap_cnt = 1;
314 swap_wb(pa, pb);
315 pa += es;
316 }
317 pb += es;
318 }
319 while (pb <= pc && (r = CMP(thunk, pc, a)) >= 0) {
320 if (r == 0) {
321 swap_cnt = 1;
322 swap_wb(pc, pd);
323 pd -= es;
324 }
325 pc -= es;
326 }
327 if (pb > pc)
328 break;
329 swap_wb(pb, pc);
330 swap_cnt = 1;
331 pb += es;
332 pc -= es;
333 }
334 if (swap_cnt == 0) { /* Switch to insertion sort */
335 for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
336 for (pl = pm;
337 pl > (char *)a && CMP(thunk, pl - es, pl) > 0;
338 pl -= es)
339 swap_wb(pl, pl - es);
340 return;
341 }
342
343 pn = (char *)a + n * es;
344 r = min(pa - (char *)a, pb - pa);
345 vecswap_wb(a, pb - r, r);
346 r = min(pd - pc, pn - pd - es);
347 vecswap_wb(pb, pn - r, r);
348 if ((r = pb - pa) > es)
349 bsd_qsort_wb(a, r / es, es, cmp, thunk);
350 if ((r = pd - pc) > es) {
351 /* Iterate rather than recurse to save stack space */
352 a = pn - r;
353 n = r / es;
354 goto loop;
355 }
356 /* qsort(pn - r, r / es, es, cmp);*/
357 }
358
359 /* Comparator is passed the address of the values. */
360 void CFQSortArray(void *list, CFIndex count, CFIndex elementSize, CFComparatorFunction comparator, void *context) {
361 if (CF_USING_COLLECTABLE_MEMORY && (auto_zone_get_layout_type(__CFCollectableZone, list) & AUTO_UNSCANNED) == 0)
362 bsd_qsort_wb(list, count, elementSize, comparator, context);
363 else
364 bsd_qsort(list, count, elementSize, comparator, context);
365 }
366
367 #undef thunk
368 #undef CMP
369 #undef vecswap
370 //#undef swap
371 #undef SWAPINIT
372 #undef swapcode
373 #undef min
374
375 /* stdlib.subproj/mergesort.c ========================================== */
376
377 /*-
378 * Copyright (c) 1992, 1993
379 * The Regents of the University of California. All rights reserved.
380 *
381 * This code is derived from software contributed to Berkeley by
382 * Peter McIlroy.
383 *
384 * Redistribution and use in source and binary forms, with or without
385 * modification, are permitted provided that the following conditions
386 * are met:
387 * 1. Redistributions of source code must retain the above copyright
388 * notice, this list of conditions and the following disclaimer.
389 * 2. Redistributions in binary form must reproduce the above copyright
390 * notice, this list of conditions and the following disclaimer in the
391 * documentation and/or other materials provided with the distribution.
392 * 3. All advertising materials mentioning features or use of this software
393 * must display the following acknowledgement:
394 * This product includes software developed by the University of
395 * California, Berkeley and its contributors.
396 * 4. Neither the name of the University nor the names of its contributors
397 * may be used to endorse or promote products derived from this software
398 * without specific prior written permission.
399 *
400 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
401 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
402 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
403 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
404 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
405 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
406 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
407 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
408 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
409 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
410 * SUCH DAMAGE.
411 */
412
413 #if 0
414 #if defined(LIBC_SCCS) && !defined(lint)
415 static char sccsid[] = "@(#)merge.c 8.2 (Berkeley) 2/14/94";
416 #endif /* LIBC_SCCS and not lint */
417 #include <sys/cdefs.h>
418 __FBSDID("$FreeBSD: src/lib/libc/stdlib/merge.c,v 1.6 2002/03/21 22:48:42 obrien Exp $");
419 #endif
420
421 /*
422 * Hybrid exponential search/linear search merge sort with hybrid
423 * natural/pairwise first pass. Requires about .3% more comparisons
424 * for random data than LSMS with pairwise first pass alone.
425 * It works for objects as small as two bytes.
426 */
427
428 #define NATURAL
429 #define THRESHOLD 16 /* Best choice for natural merge cut-off. */
430
431 /* #define NATURAL to get hybrid natural merge.
432 * (The default is pairwise merging.)
433 */
434
435 #include <sys/types.h>
436
437 #include <errno.h>
438 #include <stdlib.h>
439 #include <string.h>
440
441 static void setup(u_char *, u_char *, size_t, size_t, CFComparisonResult (*)(), void *);
442 static void insertionsort(u_char *, size_t, size_t, CFComparisonResult (*)(), void *);
443
444 #define ISIZE sizeof(long)
445 #define PSIZE sizeof(u_char *)
446 #define ICOPY_LIST(src, dst, last) \
447 do \
448 *(long*)dst = *(long*)src, src += ISIZE, dst += ISIZE; \
449 while(src < last)
450 #define ICOPY_ELT(src, dst, i) \
451 do \
452 *(long*) dst = *(long*) src, src += ISIZE, dst += ISIZE; \
453 while (i -= ISIZE)
454
455 #define CCOPY_LIST(src, dst, last) \
456 do \
457 *dst++ = *src++; \
458 while (src < last)
459 #define CCOPY_ELT(src, dst, i) \
460 do \
461 *dst++ = *src++; \
462 while (i -= 1)
463
464 /*
465 * Find the next possible pointer head. (Trickery for forcing an array
466 * to do double duty as a linked list when objects do not align with word
467 * boundaries.
468 */
469 /* Assumption: PSIZE is a power of 2. */
470 #define EVAL(p) (u_char **) \
471 ((u_char *)0 + \
472 (((u_char *)p + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1)))
473
474 /*
475 * Arguments are as for qsort.
476 */
477 static int
478 bsd_mergesort(void *base, size_t nmemb, size_t size, CFComparisonResult (*cmp)(const void *, const void *, void *), void *context)
479 {
480 long i, sense;
481 long big, iflag;
482 u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
483 u_char *list2, *list1, *p2, *p, *last, **p1;
484
485 if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */
486 errno = EINVAL;
487 return (-1);
488 }
489
490 if (nmemb == 0)
491 return (0);
492
493 /*
494 * XXX
495 * Stupid subtraction for the Cray.
496 */
497 iflag = 0;
498 if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
499 iflag = 1;
500
501 if ((list2 = malloc(nmemb * size + PSIZE)) == NULL)
502 return (-1);
503
504 list1 = base;
505 setup(list1, list2, nmemb, size, cmp, context);
506 last = list2 + nmemb * size;
507 i = big = 0;
508 while (*EVAL(list2) != last) {
509 l2 = list1;
510 p1 = EVAL(list1);
511 for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
512 p2 = *EVAL(p2);
513 f1 = l2;
514 f2 = l1 = list1 + (p2 - list2);
515 if (p2 != last)
516 p2 = *EVAL(p2);
517 l2 = list1 + (p2 - list2);
518 while (f1 < l1 && f2 < l2) {
519 if ((*cmp)(f1, f2, context) <= 0) {
520 q = f2;
521 b = f1, t = l1;
522 sense = -1;
523 } else {
524 q = f1;
525 b = f2, t = l2;
526 sense = 0;
527 }
528 if (!big) { /* here i = 0 */
529 while ((b += size) < t && cmp(q, b, context) >sense)
530 if (++i == 6) {
531 big = 1;
532 goto EXPONENTIAL;
533 }
534 } else {
535 EXPONENTIAL: for (i = size; ; i <<= 1)
536 if ((p = (b + i)) >= t) {
537 if ((p = t - size) > b &&
538 (*cmp)(q, p, context) <= sense)
539 t = p;
540 else
541 b = p;
542 break;
543 } else if ((*cmp)(q, p, context) <= sense) {
544 t = p;
545 if (i == size)
546 big = 0;
547 goto FASTCASE;
548 } else
549 b = p;
550 while (t > b+size) {
551 i = (((t - b) / size) >> 1) * size;
552 if ((*cmp)(q, p = b + i, context) <= sense)
553 t = p;
554 else
555 b = p;
556 }
557 goto COPY;
558 FASTCASE: while (i > size)
559 if ((*cmp)(q,
560 p = b + (i >>= 1), context) <= sense)
561 t = p;
562 else
563 b = p;
564 COPY: b = t;
565 }
566 i = size;
567 if (q == f1) {
568 if (iflag) {
569 ICOPY_LIST(f2, tp2, b);
570 ICOPY_ELT(f1, tp2, i);
571 } else {
572 CCOPY_LIST(f2, tp2, b);
573 CCOPY_ELT(f1, tp2, i);
574 }
575 } else {
576 if (iflag) {
577 ICOPY_LIST(f1, tp2, b);
578 ICOPY_ELT(f2, tp2, i);
579 } else {
580 CCOPY_LIST(f1, tp2, b);
581 CCOPY_ELT(f2, tp2, i);
582 }
583 }
584 }
585 if (f2 < l2) {
586 if (iflag)
587 ICOPY_LIST(f2, tp2, l2);
588 else
589 CCOPY_LIST(f2, tp2, l2);
590 } else if (f1 < l1) {
591 if (iflag)
592 ICOPY_LIST(f1, tp2, l1);
593 else
594 CCOPY_LIST(f1, tp2, l1);
595 }
596 *p1 = l2;
597 }
598 tp2 = list1; /* swap list1, list2 */
599 list1 = list2;
600 list2 = tp2;
601 last = list2 + nmemb*size;
602 }
603 if (base == list2) {
604 memmove(list2, list1, nmemb*size);
605 list2 = list1;
606 }
607 free(list2);
608 return (0);
609 }
610
611 #define swap(a, b) { \
612 s = b; \
613 i = size; \
614 do { \
615 tmp = *a; *a++ = *s; *s++ = tmp; \
616 } while (--i); \
617 a -= size; \
618 }
619 #define reverse(bot, top) { \
620 s = top; \
621 do { \
622 i = size; \
623 do { \
624 tmp = *bot; *bot++ = *s; *s++ = tmp; \
625 } while (--i); \
626 s -= size2; \
627 } while(bot < s); \
628 }
629
630 /*
631 * Optional hybrid natural/pairwise first pass. Eats up list1 in runs of
632 * increasing order, list2 in a corresponding linked list. Checks for runs
633 * when THRESHOLD/2 pairs compare with same sense. (Only used when NATURAL
634 * is defined. Otherwise simple pairwise merging is used.)
635 */
636 static void
637 setup(u_char *list1, u_char *list2, size_t n, size_t size, CFComparisonResult (*cmp)(const void *, const void *, void *), void *context)
638 {
639 long i, length, size2, tmp, sense;
640 u_char *f1, *f2, *s, *l2, *last, *p2;
641
642 size2 = size*2;
643 if (n <= 5) {
644 insertionsort(list1, n, size, cmp, context);
645 *EVAL(list2) = (u_char*) list2 + n*size;
646 return;
647 }
648 /*
649 * Avoid running pointers out of bounds; limit n to evens
650 * for simplicity.
651 */
652 i = 4 + (n & 1);
653 insertionsort(list1 + (n - i) * size, i, size, cmp, context);
654 last = list1 + size * (n - i);
655 *EVAL(list2 + (last - list1)) = list2 + n * size;
656
657 #ifdef NATURAL
658 p2 = list2;
659 f1 = list1;
660 sense = (cmp(f1, f1 + size, context) > 0);
661 for (; f1 < last; sense = !sense) {
662 length = 2;
663 /* Find pairs with same sense. */
664 for (f2 = f1 + size2; f2 < last; f2 += size2) {
665 if ((cmp(f2, f2+ size, context) > 0) != sense)
666 break;
667 length += 2;
668 }
669 if (length < THRESHOLD) { /* Pairwise merge */
670 do {
671 p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
672 if (sense > 0)
673 swap (f1, f1 + size);
674 } while ((f1 += size2) < f2);
675 } else { /* Natural merge */
676 l2 = f2;
677 for (f2 = f1 + size2; f2 < l2; f2 += size2) {
678 if ((cmp(f2-size, f2, context) > 0) != sense) {
679 p2 = *EVAL(p2) = f2 - list1 + list2;
680 if (sense > 0)
681 reverse(f1, f2-size);
682 f1 = f2;
683 }
684 }
685 if (sense > 0)
686 reverse (f1, f2-size);
687 f1 = f2;
688 if (f2 < last || cmp(f2 - size, f2, context) > 0)
689 p2 = *EVAL(p2) = f2 - list1 + list2;
690 else
691 p2 = *EVAL(p2) = list2 + n*size;
692 }
693 }
694 #else /* pairwise merge only. */
695 for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
696 p2 = *EVAL(p2) = p2 + size2;
697 if (cmp (f1, f1 + size, context) > 0)
698 swap(f1, f1 + size);
699 }
700 #endif /* NATURAL */
701 }
702
703 /*
704 * This is to avoid out-of-bounds addresses in sorting the
705 * last 4 elements.
706 */
707 static void
708 insertionsort(u_char *a, size_t n, size_t size, CFComparisonResult (*cmp)(const void *, const void *, void *), void *context)
709 {
710 u_char *ai, *s, *t, *u, tmp;
711 long i;
712
713 for (ai = a+size; --n >= 1; ai += size)
714 for (t = ai; t > a; t -= size) {
715 u = t - size;
716 if (cmp(u, t, context) <= 0)
717 break;
718 swap(u, t);
719 }
720 }
721
722 /* Another version, also not so completely different, in order to handle necessary write-barriers in the face of GC */
723
724 #undef ASSIGN
725 #define ASSIGN __CFObjCStrongAssign
726 //#define ASSIGN log_assign
727
728 static void setup_wb(u_char *, u_char *, size_t, size_t, CFComparisonResult (*)(), void *);
729 static void insertionsort_wb(u_char *, size_t, size_t, CFComparisonResult (*)(), void *);
730
731 #undef ICOPY_ELT
732
733 #define ICOPY_ELT(src, dst, i) \
734 do \
735 ASSIGN(*(const void**)src, (const void *)dst), src += ISIZE, dst += ISIZE; \
736 while (i -= ISIZE)
737
738 #undef ICOPY_LIST
739
740 #define ICOPY_LIST(src, dst, last) \
741 do \
742 ASSIGN(*(const void **)src, (const void *)dst), src += ISIZE, dst += ISIZE; \
743 while (src < last)
744
745
746 /*
747 * Arguments are as for qsort.
748 */
749 static int
750 bsd_mergesort_wb(void *base, size_t nmemb, size_t size, CFComparisonResult (*cmp)(const void *, const void *, void *), void *context)
751 {
752 long i, sense;
753 long big, iflag;
754 u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2;
755 u_char *list2, *list1, *p2, *p, *last, **p1;
756
757 if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */
758 errno = EINVAL;
759 return (-1);
760 }
761
762 if (nmemb == 0)
763 return (0);
764
765 /*
766 * XXX
767 * Stupid subtraction for the Cray.
768 */
769 iflag = 0;
770 if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
771 iflag = 1;
772
773 if (!iflag)
774 return -1; // only set up for "integer" swaps, e.g. long integer
775
776 if ((list2 = CFAllocatorAllocate(NULL, (nmemb * size + PSIZE), __kCFAllocatorGCScannedMemory)) == NULL)
777 return (-1);
778
779 list1 = base;
780 setup_wb(list1, list2, nmemb, size, cmp, context);
781 last = list2 + nmemb * size;
782 i = big = 0;
783 while (*EVAL(list2) != last) {
784 l2 = list1;
785 p1 = EVAL(list1);
786 for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
787 p2 = *EVAL(p2);
788 f1 = l2;
789 f2 = l1 = list1 + (p2 - list2);
790 if (p2 != last)
791 p2 = *EVAL(p2);
792 l2 = list1 + (p2 - list2);
793 while (f1 < l1 && f2 < l2) {
794 if ((*cmp)(f1, f2, context) <= 0) {
795 q = f2;
796 b = f1, t = l1;
797 sense = -1;
798 } else {
799 q = f1;
800 b = f2, t = l2;
801 sense = 0;
802 }
803 if (!big) { /* here i = 0 */
804 while ((b += size) < t && cmp(q, b, context) >sense)
805 if (++i == 6) {
806 big = 1;
807 goto EXPONENTIAL;
808 }
809 } else {
810 EXPONENTIAL: for (i = size; ; i <<= 1)
811 if ((p = (b + i)) >= t) {
812 if ((p = t - size) > b &&
813 (*cmp)(q, p, context) <= sense)
814 t = p;
815 else
816 b = p;
817 break;
818 } else if ((*cmp)(q, p, context) <= sense) {
819 t = p;
820 if (i == size)
821 big = 0;
822 goto FASTCASE;
823 } else
824 b = p;
825 while (t > b+size) {
826 i = (((t - b) / size) >> 1) * size;
827 if ((*cmp)(q, p = b + i, context) <= sense)
828 t = p;
829 else
830 b = p;
831 }
832 goto COPY;
833 FASTCASE: while (i > size)
834 if ((*cmp)(q,
835 p = b + (i >>= 1), context) <= sense)
836 t = p;
837 else
838 b = p;
839 COPY: b = t;
840 }
841 i = size;
842 if (q == f1) {
843 if (iflag) {
844 ICOPY_LIST(f2, tp2, b);
845 ICOPY_ELT(f1, tp2, i);
846 } else {
847 CCOPY_LIST(f2, tp2, b);
848 CCOPY_ELT(f1, tp2, i);
849 }
850 } else {
851 if (iflag) {
852 ICOPY_LIST(f1, tp2, b);
853 ICOPY_ELT(f2, tp2, i);
854 } else {
855 CCOPY_LIST(f1, tp2, b);
856 CCOPY_ELT(f2, tp2, i);
857 }
858 }
859 }
860 if (f2 < l2) {
861 if (iflag)
862 ICOPY_LIST(f2, tp2, l2);
863 else
864 CCOPY_LIST(f2, tp2, l2);
865 } else if (f1 < l1) {
866 if (iflag)
867 ICOPY_LIST(f1, tp2, l1);
868 else
869 CCOPY_LIST(f1, tp2, l1);
870 }
871 *p1 = l2;
872 }
873 tp2 = list1; /* swap list1, list2 */
874 list1 = list2;
875 list2 = tp2;
876 last = list2 + nmemb*size;
877 }
878 if (base == list2) {
879 CF_WRITE_BARRIER_MEMMOVE(list2, list1, nmemb*size);
880 list2 = list1;
881 }
882 free(list2);
883 return (0);
884 }
885
886
887 #define swap_wb(a, b) { \
888 const void *object = *(void **)a; \
889 ASSIGN(*(const void **)b, (const void *)a); \
890 ASSIGN(object, (const void *)b); \
891 }
892
893 #define reverse_wb(bot, top) { \
894 s = top; \
895 do { \
896 swap_wb(bot, s); \
897 bot += size; \
898 s -= size; \
899 } while(bot < s); \
900 }
901
902 /*
903 * Optional hybrid natural/pairwise first pass. Eats up list1 in runs of
904 * increasing order, list2 in a corresponding linked list. Checks for runs
905 * when THRESHOLD/2 pairs compare with same sense. (Only used when NATURAL
906 * is defined. Otherwise simple pairwise merging is used.)
907 */
908 static void
909 setup_wb(u_char *list1, u_char *list2, size_t n, size_t size, CFComparisonResult (*cmp)(const void *, const void *, void *), void *context)
910 {
911 long i, length, size2, tmp, sense;
912 u_char *f1, *f2, *s, *l2, *last, *p2;
913
914 size2 = size*2;
915 if (n <= 5) {
916 insertionsort_wb(list1, n, size, cmp, context);
917 *EVAL(list2) = (u_char*) list2 + n*size;
918 return;
919 }
920 /*
921 * Avoid running pointers out of bounds; limit n to evens
922 * for simplicity.
923 */
924 i = 4 + (n & 1);
925 insertionsort_wb(list1 + (n - i) * size, i, size, cmp, context);
926 last = list1 + size * (n - i);
927 *EVAL(list2 + (last - list1)) = list2 + n * size;
928
929 #ifdef NATURAL
930 p2 = list2;
931 f1 = list1;
932 sense = (cmp(f1, f1 + size, context) > 0);
933 for (; f1 < last; sense = !sense) {
934 length = 2;
935 /* Find pairs with same sense. */
936 for (f2 = f1 + size2; f2 < last; f2 += size2) {
937 if ((cmp(f2, f2+ size, context) > 0) != sense)
938 break;
939 length += 2;
940 }
941 if (length < THRESHOLD) { /* Pairwise merge */
942 do {
943 p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
944 if (sense > 0)
945 swap (f1, f1 + size);
946 } while ((f1 += size2) < f2);
947 } else { /* Natural merge */
948 l2 = f2;
949 for (f2 = f1 + size2; f2 < l2; f2 += size2) {
950 if ((cmp(f2-size, f2, context) > 0) != sense) {
951 p2 = *EVAL(p2) = f2 - list1 + list2;
952 if (sense > 0) {
953 reverse_wb(f1, f2-size);
954 }
955 f1 = f2;
956 }
957 }
958 if (sense > 0) {
959 reverse_wb (f1, f2-size);
960 }
961 f1 = f2;
962 if (f2 < last || cmp(f2 - size, f2, context) > 0) {
963 p2 = *EVAL(p2) = f2 - list1 + list2;
964 }
965 else {
966 p2 = *EVAL(p2) = list2 + n*size;
967 }
968 }
969 }
970 #else /* pairwise merge only. */
971 #error unchanged
972 for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
973 p2 = *EVAL(p2) = p2 + size2;
974 if (cmp (f1, f1 + size, context) > 0)
975 swap_wb(f1, f1 + size);
976 }
977 #endif /* NATURAL */
978 }
979
980 /*
981 * This is to avoid out-of-bounds addresses in sorting the
982 * last 4 elements.
983 */
984 static void
985 insertionsort_wb(u_char *a, size_t n, size_t size, CFComparisonResult (*cmp)(const void *, const void *, void *), void *context)
986 {
987 u_char *ai, *s, *t, *u, tmp;
988 long i;
989
990 for (ai = a+size; --n >= 1; ai += size)
991 for (t = ai; t > a; t -= size) {
992 u = t - size;
993 if (cmp(u, t, context) <= 0)
994 break;
995 swap(u, t);
996 }
997 }
998
999 void CFMergeSortArray(void *list, CFIndex count, CFIndex elementSize, CFComparatorFunction comparator, void *context) {
1000 if (CF_USING_COLLECTABLE_MEMORY && (auto_zone_get_layout_type(__CFCollectableZone, list) & AUTO_UNSCANNED) == 0)
1001 bsd_mergesort_wb(list, count, elementSize, comparator, context);
1002 else
1003 bsd_mergesort(list, count, elementSize, comparator, context);
1004 }
1005
1006 #undef NATURAL
1007 #undef THRESHOLD
1008 #undef ISIZE
1009 #undef PSIZE
1010 #undef ICOPY_LIST
1011 #undef ICOPY_ELT
1012 #undef CCOPY_LIST
1013 #undef CCOPY_ELT
1014 #undef EVAL
1015 #undef swap
1016 #undef reverse
1017
1018 /* ===================================================================== */
1019
1020 #undef EINVAL
1021
mirror of CF