CFSortFunctions.c

   1 /*
   2  * Copyright (c) 2009 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 (c) 1999-2009, Apple Inc. All rights reserved.
  25         Responsibility: Christopher Kane
  26 */
  27
  28 #include <CoreFoundation/CFBase.h>
  29 #include "CFInternal.h"
  30 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED
  31 #include <dispatch/dispatch.h>
  32 #include <sys/sysctl.h>
  33 #endif
  34
  35
  36 enum {
  37     kCFSortConcurrent = (1 << 0),
  38     kCFSortStable = (1 << 4),
  39 };
  40
  41 typedef CFIndex VALUE_TYPE;
  42 typedef CFIndex INDEX_TYPE;
  43 typedef CFComparisonResult CMP_RESULT_TYPE;
  44 typedef CMP_RESULT_TYPE (^COMPARATOR_BLOCK)(VALUE_TYPE, VALUE_TYPE);
  45
  46 /*
  47 Number of elements in a list and expected number of compares,
  48 when the initial short-circuiting compare is not done.
  49 1       0
  50 2       1
  51 3       2.667
  52 4       4.667
  53 5       7.167
  54 6       9.833
  55 7       12.733
  56 8       15.733
  57 9       19.167
  58 10      22.667
  59 11      26.2857
  60 12      29.9524
  61 */
  62
  63 static void __CFSimpleMerge(VALUE_TYPE listp[], INDEX_TYPE cnt1, INDEX_TYPE cnt2, VALUE_TYPE tmp[], COMPARATOR_BLOCK cmp) {
  64     if (cnt1 <= 0 || cnt2 <= 0) return;
  65     // if the last element of listp1 <= the first of listp2, lists are already ordered
  66     if (16 < cnt1 + cnt2 && cmp(listp[cnt1 - 1], listp[cnt1]) <= 0) return;
  67
  68     INDEX_TYPE idx = 0, idx1 = 0, idx2 = cnt1;
  69     for (;;) {
  70         if (cnt1 <= idx1) {
  71             while (idx--) {
  72                 listp[idx] = tmp[idx];
  73             }
  74             return;
  75         }
  76         if (cnt1 + cnt2 <= idx2) {
  77             for (INDEX_TYPE t = cnt1 + cnt2 - 1; idx <= t; t--) {
  78                 listp[t] = listp[t - cnt2];
  79             }
  80             while (idx--) {
  81                 listp[idx] = tmp[idx];
  82             }
  83             return;
  84         }
  85         VALUE_TYPE v1 = listp[idx1], v2 = listp[idx2];
  86         if (cmp(v1, v2) <= 0) {
  87             tmp[idx] = v1;
  88             idx1++;
  89         } else {
  90             tmp[idx] = v2;
  91             idx2++;
  92         }
  93         idx++;
  94     }
  95 }
  96
  97 static void __CFSimpleMergeSort(VALUE_TYPE listp[], INDEX_TYPE cnt, VALUE_TYPE tmp[], COMPARATOR_BLOCK cmp) {
  98     if (cnt < 2) {
  99         /* do nothing */
 100     } else if (2 == cnt) {
 101         VALUE_TYPE v0 = listp[0], v1 = listp[1];
 102         if (0 < cmp(v0, v1)) {
 103             listp[0] = v1;
 104             listp[1] = v0;
 105         }
 106     } else if (3 == cnt) {
 107         VALUE_TYPE v0 = listp[0], v1 = listp[1], v2 = listp[2], vt;
 108         if (0 < cmp(v0, v1)) {
 109             vt = v0;
 110             v0 = v1;
 111             v1 = vt;
 112         }
 113         if (0 < cmp(v1, v2)) {
 114             vt = v1;
 115             v1 = v2;
 116             v2 = vt;
 117             if (0 < cmp(v0, v1)) {
 118                 vt = v0;
 119                 v0 = v1;
 120                 v1 = vt;
 121             }
 122         }
 123         listp[0] = v0;
 124         listp[1] = v1;
 125         listp[2] = v2;
 126     } else {
 127         INDEX_TYPE half_cnt = cnt / 2;
 128         __CFSimpleMergeSort(listp, half_cnt, tmp, cmp);
 129         __CFSimpleMergeSort(listp + half_cnt, cnt - half_cnt, tmp, cmp);
 130         __CFSimpleMerge(listp, half_cnt, cnt - half_cnt, tmp, cmp);
 131     }
 132 }
 133
 134 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED
 135 // if !right, put the cnt1 smallest values in tmp, else put the cnt2 largest values in tmp
 136 static void __CFSortIndexesNMerge(VALUE_TYPE listp1[], INDEX_TYPE cnt1, VALUE_TYPE listp2[], INDEX_TYPE cnt2, VALUE_TYPE tmp[], size_t right, COMPARATOR_BLOCK cmp) {
 137     // if the last element of listp1 <= the first of listp2, lists are already ordered
 138     if (16 < cnt1 + cnt2 && cmp(listp1[cnt1 - 1], listp2[0]) <= 0) {
 139         memmove(tmp, (right ? listp2 : listp1), (right ? cnt2 : cnt1) * sizeof(VALUE_TYPE));
 140         return;
 141     }
 142
 143     if (right) {
 144         VALUE_TYPE *listp1_end = listp1;
 145         VALUE_TYPE *listp2_end = listp2;
 146         VALUE_TYPE *tmp_end = tmp;
 147         listp1 += cnt1 - 1;
 148         listp2 += cnt2 - 1;
 149         tmp += cnt2;
 150         while (tmp_end < tmp) {
 151             tmp--;
 152             if (listp2 < listp2_end) {
 153                 listp1--;
 154                 *tmp = *listp1;
 155             } else if (listp1 < listp1_end) {
 156                 listp2--;
 157                 *tmp = *listp2;
 158             } else {
 159                 VALUE_TYPE v1 = *listp1, v2 = *listp2;
 160                 CMP_RESULT_TYPE res = cmp(v1, v2);
 161                 if (res <= 0) {
 162                     *tmp = v2;
 163                     listp2--;
 164                 } else {
 165                     *tmp = v1;
 166                     listp1--;
 167                 }
 168             }
 169         }
 170     } else {
 171         VALUE_TYPE *listp1_end = listp1 + cnt1;
 172         VALUE_TYPE *listp2_end = listp2 + cnt2;
 173         VALUE_TYPE *tmp_end = tmp + cnt1;
 174         while (tmp < tmp_end) {
 175             if (listp2_end <= listp2) {
 176                 *tmp = *listp1;
 177                 listp1++;
 178             } else if (listp1_end <= listp1) {
 179                 *tmp = *listp2;
 180                 listp2++;
 181             } else {
 182                 VALUE_TYPE v1 = *listp1, v2 = *listp2;
 183                 CMP_RESULT_TYPE res = cmp(v1, v2);
 184                 if (res <= 0) {
 185                     *tmp = v1;
 186                     listp1++;
 187                 } else {
 188                     *tmp = v2;
 189                     listp2++;
 190                 }
 191             }
 192             tmp++;
 193         }
 194     }
 195 }
 196
 197 /* Merging algorithm based on
 198     "A New Parallel Sorting Algorithm based on Odd-Even Mergesort", Ezequiel Herruzo, et al
 199 */
 200 static void __CFSortIndexesN(VALUE_TYPE listp[], INDEX_TYPE count, int32_t ncores, CMP_RESULT_TYPE (^cmp)(INDEX_TYPE, INDEX_TYPE)) {
 201     /* Divide the array up into up to ncores, multiple-of-16-sized, chunks */
 202     INDEX_TYPE sz = ((((count + ncores - 1) / ncores) + 15) / 16) * 16;
 203     INDEX_TYPE num_sect = (count + sz - 1) / sz;
 204     INDEX_TYPE last_sect_len = count + sz - sz * num_sect;
 205
 206     STACK_BUFFER_DECL(VALUE_TYPE *, stack_tmps, num_sect);
 207     for (INDEX_TYPE idx = 0; idx < num_sect; idx++) {
 208         stack_tmps[idx] = malloc(sz * sizeof(VALUE_TYPE));
 209     }
 210     VALUE_TYPE **tmps = stack_tmps;
 211
 212     dispatch_queue_t q = dispatch_get_concurrent_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT);
 213     dispatch_apply(num_sect, q, ^(size_t sect) {
 214             INDEX_TYPE sect_len = (sect < num_sect - 1) ? sz : last_sect_len;
 215             __CFSimpleMergeSort(listp + sect * sz, sect_len, tmps[sect], cmp); // naturally stable
 216         });
 217
 218     INDEX_TYPE even_phase_cnt = ((num_sect / 2) * 2);
 219     INDEX_TYPE odd_phase_cnt = (((num_sect - 1) / 2) * 2);
 220     for (INDEX_TYPE idx = 0; idx < (num_sect + 1) / 2; idx++) {
 221         dispatch_apply(even_phase_cnt, q, ^(size_t sect) { // merge even
 222                 size_t right = sect & (size_t)0x1;
 223                 VALUE_TYPE *left_base = listp + sect * sz - (right ? sz : 0);
 224                 VALUE_TYPE *right_base = listp + sect * sz + (right ? 0 : sz);
 225                 INDEX_TYPE sect2_len = (sect + 1 + (right ? 0 : 1) == num_sect) ? last_sect_len : sz;
 226                 __CFSortIndexesNMerge(left_base, sz, right_base, sect2_len, tmps[sect], right, cmp);
 227             });
 228         if (num_sect & 0x1) {
 229             memmove(tmps[num_sect - 1], listp + (num_sect - 1) * sz, last_sect_len * sizeof(VALUE_TYPE));
 230         }
 231         dispatch_apply(odd_phase_cnt, q, ^(size_t sect) { // merge odd
 232                 size_t right = sect & (size_t)0x1;
 233                 VALUE_TYPE *left_base = tmps[sect + (right ? 0 : 1)];
 234                 VALUE_TYPE *right_base = tmps[sect + (right ? 1 : 2)];
 235                 INDEX_TYPE sect2_len = (sect + 1 + (right ? 1 : 2) == num_sect) ? last_sect_len : sz;
 236                 __CFSortIndexesNMerge(left_base, sz, right_base, sect2_len, listp + sect * sz + sz, right, cmp);
 237             });
 238         memmove(listp + 0 * sz, tmps[0], sz * sizeof(VALUE_TYPE));
 239         if (!(num_sect & 0x1)) {
 240             memmove(listp + (num_sect - 1) * sz, tmps[num_sect - 1], last_sect_len * sizeof(VALUE_TYPE));
 241         }
 242     }
 243
 244     for (INDEX_TYPE idx = 0; idx < num_sect; idx++) {
 245         free(stack_tmps[idx]);
 246     }
 247 }
 248 #endif
 249
 250 // returns an array of indexes (of length count) giving the indexes 0 - count-1, as sorted by the comparator block
 251 CFIndex *CFSortIndexes(CFIndex count, CFOptionFlags opts, CFComparisonResult (^cmp)(CFIndex, CFIndex)) {
 252     if (count < 1) return NULL;
 253     if (INTPTR_MAX / sizeof(CFIndex) < count) return NULL;
 254 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED
 255     int32_t ncores = 0;
 256     if (opts & kCFSortConcurrent) {
 257         int32_t mib[2] = {CTL_HW, HW_AVAILCPU};
 258         size_t len = sizeof(ncores);
 259         sysctl(mib, 2, &ncores, &len, NULL, 0);
 260         if (count < 160 || ncores < 2) {
 261             opts = (opts & ~kCFSortConcurrent);
 262         } else if (count < 640 && 2 < ncores) {
 263             ncores = 2;
 264         } else if (count < 3200 && 4 < ncores) {
 265             ncores = 4;
 266         } else if (count < 16000 && 8 < ncores) {
 267             ncores = 8;
 268         }
 269         if (16 < ncores) {
 270             ncores = 16;
 271         }
 272     }
 273     CFIndex *idxs = malloc_zone_memalign(malloc_default_zone(), 64, count * sizeof(CFIndex));
 274     if (!idxs) return NULL;
 275     if (count <= 65536) {
 276         for (CFIndex idx = 0; idx < count; idx++) idxs[idx] = idx;
 277     } else {
 278         /* Specifically hard-coded to 8; the count has to be very large before more chunks and/or cores is worthwhile. */
 279         CFIndex sz = ((((size_t)count + 15) / 16) * 16) / 8;
 280         dispatch_apply(8, dispatch_get_concurrent_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT), ^(size_t n) {
 281                 CFIndex idx = n * sz, lim = __CFMin(idx + sz, count);
 282                 for (; idx < lim; idx++) idxs[idx] = idx;
 283             });
 284     }
 285     if (opts & kCFSortConcurrent) {
 286         __CFSortIndexesN(idxs, count, ncores, cmp); // naturally stable
 287         return idxs;
 288     }
 289 #else
 290     CFIndex *idxs = (CFIndex *)malloc(count * sizeof(CFIndex));
 291     if (!idxs) return NULL;
 292     for (CFIndex idx = 0; idx < count; idx++) idxs[idx] = idx;
 293 #endif
 294     STACK_BUFFER_DECL(VALUE_TYPE, local, count <= 16384 ? count : 1);
 295     VALUE_TYPE *tmp = (count <= 16384) ? local : (VALUE_TYPE *)malloc(count * sizeof(VALUE_TYPE));
 296     __CFSimpleMergeSort(idxs, count, tmp, cmp); // naturally stable
 297     if (local != tmp) free(tmp);
 298     return idxs;
 299 }
 300
 301 /* Comparator is passed the address of the values. */
 302 void CFQSortArray(void *list, CFIndex count, CFIndex elementSize, CFComparatorFunction comparator, void *context) {
 303     if (count < 1 || elementSize < 1) return;
 304     CFIndex *indexes = CFSortIndexes(count, 0, ^(CFIndex a, CFIndex b) { return comparator((char *)list + a * elementSize, (char *)list + b * elementSize, context); }); // naturally stable
 305     void *store = malloc(count * elementSize);
 306     for (CFIndex idx = 0; idx < count; idx++) {
 307         if (sizeof(uintptr_t) == elementSize) {
 308             uintptr_t *a = (uintptr_t *)list + indexes[idx];
 309             uintptr_t *b = (uintptr_t *)store + idx;
 310             *b = *a;
 311         } else {
 312             memmove((char *)store + idx * elementSize, (char *)list + indexes[idx] * elementSize, elementSize);
 313         }
 314     }
 315     // no swapping or modification of the original list has occurred until this point
 316     objc_memmove_collectable(list, store, count * elementSize);
 317     free(store);
 318     free(indexes);
 319 }
 320
 321 /* Comparator is passed the address of the values. */
 322 void CFMergeSortArray(void *list, CFIndex count, CFIndex elementSize, CFComparatorFunction comparator, void *context) {
 323     if (count < 1 || elementSize < 1) return;
 324     CFIndex *indexes = CFSortIndexes(count, kCFSortStable, ^(CFIndex a, CFIndex b) { return comparator((char *)list + a * elementSize, (char *)list + b * elementSize, context); }); // naturally stable
 325     void *store = malloc(count * elementSize);
 326     for (CFIndex idx = 0; idx < count; idx++) {
 327         if (sizeof(uintptr_t) == elementSize) {
 328             uintptr_t *a = (uintptr_t *)list + indexes[idx];
 329             uintptr_t *b = (uintptr_t *)store + idx;
 330             *b = *a;
 331         } else {
 332             memmove((char *)store + idx * elementSize, (char *)list + indexes[idx] * elementSize, elementSize);
 333         }
 334     }
 335     // no swapping or modification of the original list has occurred until this point
 336     objc_memmove_collectable(list, store, count * elementSize);
 337     free(store);
 338     free(indexes);
 339 }
 340
 341