CFSortFunctions.c
1 /* CFSortFunctions.c 2 Copyright (c) 1999-2019, Apple Inc. and the Swift project authors 3 4 Portions Copyright (c) 2014-2019, Apple Inc. and the Swift project authors 5 Licensed under Apache License v2.0 with Runtime Library Exception 6 See http://swift.org/LICENSE.txt for license information 7 See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors 8 Responsibility: Michael LeHew 9 */ 10 11 #include <CoreFoundation/CFBase.h> 12 #include "CFInternal.h" 13 #if __HAS_DISPATCH__ 14 #include <dispatch/dispatch.h> 15 #if TARGET_OS_MAC && __has_include(<dispatch/private.h>) 16 #include <dispatch/private.h> 17 #else 18 #define DISPATCH_APPLY_CURRENT_ROOT_QUEUE ((dispatch_queue_t _Nonnull)0) 19 #endif // TARGET_OS_MAC && __has_include(<dispatch/private.h>) 20 #endif // __HAS_DISPATCH__ 21 #include "CFLogUtilities.h" 22 #include "CFInternal.h" 23 #include "CFOverflow.h" 24 25 #if __has_include(<checkint.h>) 26 #include <checkint.h> 27 #else 28 enum { 29 CHECKINT_NO_ERROR = 0, 30 CHECKINT_OVERFLOW_ERROR = (1 << 0), 31 CHECKINT_TYPE_ERROR = (1 << 1) 32 }; 33 34 #define __check_int32_add(x, y, err) (x + y) 35 #define __check_uint32_add(x, y, err) (x + y) 36 #define __check_int64_add(x, y, err) (x + y) 37 #define __check_uint64_add(x, y, err) (x + y) 38 39 #define __check_int32_sub(x, y, err) (x - y) 40 #define __check_uint32_sub(x, y, err) (x - y) 41 #define __check_int64_sub(x, y, err) (x - y) 42 #define __check_uint64_sub(x, y, err) (x - y) 43 44 #define __check_int32_mul(x, y, err) (x * y) 45 #define __check_uint32_mul(x, y, err) (x * y) 46 #define __check_int64_mul(x, y, err) (x * y) 47 #define __check_uint64_mul(x, y, err) (x * y) 48 49 #define __check_int32_div(x, y, err) (x / y) 50 #define __check_uint32_div(x, y, err) (x / y) 51 #define __check_int64_div(x, y, err) (x / y) 52 #define __check_uint64_div(x, y, err) (x / y) 53 54 #define __checkint_int64_mul(x, y, err) (x * y) 55 #define __checkint_uint64_add(x, y, err) (x + y) 56 #define __checkint_int32_mul(x,y,err) (x * y) 57 #define __checkint_uint32_add(x,y,err) (x + y) 58 59 #endif 60 61 enum { 62 kCFSortConcurrent = (1 << 0), 63 kCFSortStable = (1 << 4), 64 }; 65 66 typedef CFIndex VALUE_TYPE; 67 typedef CFIndex INDEX_TYPE; 68 typedef CFComparisonResult CMP_RESULT_TYPE; 69 typedef CMP_RESULT_TYPE (^COMPARATOR_BLOCK)(VALUE_TYPE, VALUE_TYPE); 70 71 /* 72 Number of elements in a list and expected number of compares, 73 when the initial short-circuiting compare is not done. 74 1 0 75 2 1 76 3 2.667 77 4 4.667 78 5 7.167 79 6 9.833 80 7 12.733 81 8 15.733 82 9 19.167 83 10 22.667 84 11 26.2857 85 12 29.9524 86 */ 87 88 static void __CFSimpleMerge(VALUE_TYPE listp[], INDEX_TYPE cnt1, INDEX_TYPE cnt2, VALUE_TYPE tmp[], COMPARATOR_BLOCK cmp) { 89 if (cnt1 <= 0 || cnt2 <= 0) return; 90 // if the last element of listp1 <= the first of listp2, lists are already ordered 91 if (16 < cnt1 + cnt2 && cmp(listp[cnt1 - 1], listp[cnt1]) <= 0) return; 92 93 INDEX_TYPE idx = 0, idx1 = 0, idx2 = cnt1; 94 for (;;) { 95 if (cnt1 <= idx1) { 96 while (idx--) { 97 listp[idx] = tmp[idx]; 98 } 99 return; 100 } 101 if (cnt1 + cnt2 <= idx2) { 102 for (INDEX_TYPE t = cnt1 + cnt2 - 1; idx <= t; t--) { 103 listp[t] = listp[t - cnt2]; 104 } 105 while (idx--) { 106 listp[idx] = tmp[idx]; 107 } 108 return; 109 } 110 VALUE_TYPE v1 = listp[idx1], v2 = listp[idx2]; 111 if (cmp(v1, v2) <= 0) { 112 tmp[idx] = v1; 113 idx1++; 114 } else { 115 tmp[idx] = v2; 116 idx2++; 117 } 118 idx++; 119 } 120 } 121 122 static void __CFSimpleMergeSort(VALUE_TYPE listp[], INDEX_TYPE cnt, VALUE_TYPE tmp[], COMPARATOR_BLOCK cmp) { 123 if (cnt < 2) { 124 /* do nothing */ 125 } else if (2 == cnt) { 126 VALUE_TYPE v0 = listp[0], v1 = listp[1]; 127 if (0 < cmp(v0, v1)) { 128 listp[0] = v1; 129 listp[1] = v0; 130 } 131 } else if (3 == cnt) { 132 VALUE_TYPE v0 = listp[0], v1 = listp[1], v2 = listp[2], vt; 133 if (0 < cmp(v0, v1)) { 134 vt = v0; 135 v0 = v1; 136 v1 = vt; 137 } 138 if (0 < cmp(v1, v2)) { 139 vt = v1; 140 v1 = v2; 141 v2 = vt; 142 if (0 < cmp(v0, v1)) { 143 vt = v0; 144 v0 = v1; 145 v1 = vt; 146 } 147 } 148 listp[0] = v0; 149 listp[1] = v1; 150 listp[2] = v2; 151 } else { 152 INDEX_TYPE half_cnt = cnt / 2; 153 __CFSimpleMergeSort(listp, half_cnt, tmp, cmp); 154 __CFSimpleMergeSort(listp + half_cnt, cnt - half_cnt, tmp, cmp); 155 __CFSimpleMerge(listp, half_cnt, cnt - half_cnt, tmp, cmp); 156 } 157 } 158 159 #if __HAS_DISPATCH__ 160 161 // if !right, put the cnt1 smallest values in tmp, else put the cnt2 largest values in tmp 162 static void __CFSortIndexesNMerge(VALUE_TYPE listp1[], INDEX_TYPE cnt1, VALUE_TYPE listp2[], INDEX_TYPE cnt2, VALUE_TYPE tmp[], size_t right, COMPARATOR_BLOCK cmp) { 163 // if the last element of listp1 <= the first of listp2, lists are already ordered 164 if (16 < cnt1 + cnt2 && cmp(listp1[cnt1 - 1], listp2[0]) <= 0) { 165 memmove(tmp, (right ? listp2 : listp1), (right ? cnt2 : cnt1) * sizeof(VALUE_TYPE)); 166 return; 167 } 168 169 if (right) { 170 VALUE_TYPE *listp1_end = listp1; 171 VALUE_TYPE *listp2_end = listp2; 172 VALUE_TYPE *tmp_end = tmp; 173 listp1 += cnt1 - 1; 174 listp2 += cnt2 - 1; 175 tmp += cnt2; 176 while (tmp_end < tmp) { 177 tmp--; 178 if (listp2 < listp2_end) { 179 listp1--; 180 *tmp = *listp1; 181 } else if (listp1 < listp1_end) { 182 listp2--; 183 *tmp = *listp2; 184 } else { 185 VALUE_TYPE v1 = *listp1, v2 = *listp2; 186 CMP_RESULT_TYPE res = cmp(v1, v2); 187 if (res <= 0) { 188 *tmp = v2; 189 listp2--; 190 } else { 191 *tmp = v1; 192 listp1--; 193 } 194 } 195 } 196 } else { 197 VALUE_TYPE *listp1_end = listp1 + cnt1; 198 VALUE_TYPE *listp2_end = listp2 + cnt2; 199 VALUE_TYPE *tmp_end = tmp + cnt1; 200 while (tmp < tmp_end) { 201 if (listp2_end <= listp2) { 202 *tmp = *listp1; 203 listp1++; 204 } else if (listp1_end <= listp1) { 205 *tmp = *listp2; 206 listp2++; 207 } else { 208 VALUE_TYPE v1 = *listp1, v2 = *listp2; 209 CMP_RESULT_TYPE res = cmp(v1, v2); 210 if (res <= 0) { 211 *tmp = v1; 212 listp1++; 213 } else { 214 *tmp = v2; 215 listp2++; 216 } 217 } 218 tmp++; 219 } 220 } 221 } 222 223 /* Merging algorithm based on 224 "A New Parallel Sorting Algorithm based on Odd-Even Mergesort", Ezequiel Herruzo, et al 225 */ 226 static void __CFSortIndexesN(VALUE_TYPE listp[], INDEX_TYPE count, int32_t ncores, CMP_RESULT_TYPE (^cmp)(INDEX_TYPE, INDEX_TYPE)) { 227 /* Divide the array up into up to ncores, multiple-of-16-sized, chunks */ 228 INDEX_TYPE sz = ((((count + ncores - 1) / ncores) + 15) / 16) * 16; 229 INDEX_TYPE num_sect = (count + sz - 1) / sz; 230 INDEX_TYPE last_sect_len = count + sz - sz * num_sect; 231 232 STACK_BUFFER_DECL(VALUE_TYPE *, stack_tmps, num_sect); 233 for (INDEX_TYPE idx = 0; idx < num_sect; idx++) { 234 stack_tmps[idx] = (VALUE_TYPE *)malloc(sz * sizeof(VALUE_TYPE)); 235 } 236 VALUE_TYPE **tmps = stack_tmps; 237 238 dispatch_apply(num_sect, DISPATCH_APPLY_AUTO, ^(size_t sect) { 239 INDEX_TYPE sect_len = (sect < num_sect - 1) ? sz : last_sect_len; 240 __CFSimpleMergeSort(listp + sect * sz, sect_len, tmps[sect], cmp); // naturally stable 241 }); 242 243 INDEX_TYPE even_phase_cnt = ((num_sect / 2) * 2); 244 INDEX_TYPE odd_phase_cnt = (((num_sect - 1) / 2) * 2); 245 for (INDEX_TYPE idx = 0; idx < (num_sect + 1) / 2; idx++) { 246 dispatch_apply(even_phase_cnt, DISPATCH_APPLY_AUTO, ^(size_t sect) { // merge even 247 size_t right = sect & (size_t)0x1; 248 VALUE_TYPE *left_base = listp + sect * sz - (right ? sz : 0); 249 VALUE_TYPE *right_base = listp + sect * sz + (right ? 0 : sz); 250 INDEX_TYPE sect2_len = (sect + 1 + (right ? 0 : 1) == num_sect) ? last_sect_len : sz; 251 __CFSortIndexesNMerge(left_base, sz, right_base, sect2_len, tmps[sect], right, cmp); 252 }); 253 if (num_sect & 0x1) { 254 memmove(tmps[num_sect - 1], listp + (num_sect - 1) * sz, last_sect_len * sizeof(VALUE_TYPE)); 255 } 256 dispatch_apply(odd_phase_cnt, DISPATCH_APPLY_AUTO, ^(size_t sect) { // merge odd 257 size_t right = sect & (size_t)0x1; 258 VALUE_TYPE *left_base = tmps[sect + (right ? 0 : 1)]; 259 VALUE_TYPE *right_base = tmps[sect + (right ? 1 : 2)]; 260 INDEX_TYPE sect2_len = (sect + 1 + (right ? 1 : 2) == num_sect) ? last_sect_len : sz; 261 __CFSortIndexesNMerge(left_base, sz, right_base, sect2_len, listp + sect * sz + sz, right, cmp); 262 }); 263 memmove(listp + 0 * sz, tmps[0], sz * sizeof(VALUE_TYPE)); 264 if (!(num_sect & 0x1)) { 265 memmove(listp + (num_sect - 1) * sz, tmps[num_sect - 1], last_sect_len * sizeof(VALUE_TYPE)); 266 } 267 } 268 269 for (INDEX_TYPE idx = 0; idx < num_sect; idx++) { 270 free(stack_tmps[idx]); 271 } 272 } 273 #endif 274 275 #if DEPLOYMENT_RUNTIME_SWIFT 276 #define _CF_SORT_INDEXES_EXPORT CF_CROSS_PLATFORM_EXPORT 277 #else 278 #define _CF_SORT_INDEXES_EXPORT 279 #endif 280 281 // fills an array of indexes (of length count) giving the indexes 0 - count-1, as sorted by the comparator block 282 _CF_SORT_INDEXES_EXPORT void CFSortIndexes(CFIndex *indexBuffer, CFIndex count, CFOptionFlags opts, CFComparisonResult (^cmp)(CFIndex, CFIndex)) { 283 if (count < 1) return; 284 if (INTPTR_MAX / sizeof(CFIndex) < count) { 285 CRSetCrashLogMessage("Size of array to be sorted is too big"); 286 HALT; 287 } 288 int32_t ncores = 0; 289 if (opts & kCFSortConcurrent) { 290 ncores = __CFActiveProcessorCount(); 291 if (count < 160 || ncores < 2) { 292 opts = (opts & ~kCFSortConcurrent); 293 } else if (count < 640 && 2 < ncores) { 294 ncores = 2; 295 } else if (count < 3200 && 4 < ncores) { 296 ncores = 4; 297 } else if (count < 16000 && 8 < ncores) { 298 ncores = 8; 299 } 300 if (16 < ncores) { 301 ncores = 16; 302 } 303 } 304 #if __HAS_DISPATCH__ 305 if (count <= 65536) { 306 for (CFIndex idx = 0; idx < count; idx++) indexBuffer[idx] = idx; 307 } else { 308 /* Specifically hard-coded to 8; the count has to be very large before more chunks and/or cores is worthwhile. */ 309 dispatch_queue_t q = dispatch_queue_create(__CF_QUEUE_NAME("NSSortIndexes"), DISPATCH_QUEUE_CONCURRENT); 310 CFIndex sz = ((((size_t)count + 15) / 16) * 16) / 8; 311 dispatch_apply(8, DISPATCH_APPLY_AUTO, ^(size_t n) { 312 CFIndex idx = n * sz, lim = __CFMin(idx + sz, count); 313 for (; idx < lim; idx++) indexBuffer[idx] = idx; 314 }); 315 dispatch_release(q); 316 } 317 #else 318 for (CFIndex idx = 0; idx < count; idx++) indexBuffer[idx] = idx; 319 #endif 320 #if __HAS_DISPATCH__ 321 if (opts & kCFSortConcurrent) { 322 __CFSortIndexesN(indexBuffer, count, ncores, cmp); // naturally stable 323 return; 324 } 325 #endif 326 STACK_BUFFER_DECL(VALUE_TYPE, local, count <= 4096 ? count : 1); 327 VALUE_TYPE *tmp = (count <= 4096) ? local : (VALUE_TYPE *)malloc(count * sizeof(VALUE_TYPE)); 328 __CFSimpleMergeSort(indexBuffer, count, tmp, cmp); // naturally stable 329 if (local != tmp) free(tmp); 330 } 331 332 /* Comparator is passed the address of the values. */ 333 void CFQSortArray(void *list, CFIndex count, CFIndex elementSize, CFComparatorFunction comparator, void *context) { 334 if (count < 2 || elementSize < 1) return; 335 _CFOverflowResult overflowResult = _CFPositiveIntegerProductWouldOverflow(count, elementSize, NULL); 336 if (overflowResult != _CFOverflowResultOK) { 337 CFLog(kCFLogLevelError, CFSTR("Unable to qsort array - count: %ld elementSize: %ld product overflows"), (long)count, (long)elementSize); 338 CRSetCrashLogMessage("qsort - count/elementSize overflow"); 339 HALT; 340 } 341 overflowResult = _CFPointerSumWouldOverflow(list, count * elementSize, NULL); 342 if (overflowResult != _CFOverflowResultOK) { 343 CFLog(kCFLogLevelError, CFSTR("Unable to qsort array - list: %lu count: %ld elementSize: %ld - array access overflows"), (unsigned long)list, (long)count, (long)elementSize); 344 CRSetCrashLogMessage("qsort - array access overflow"); 345 HALT; 346 } 347 STACK_BUFFER_DECL(CFIndex, locali, count <= 4096 ? count : 1); 348 CFIndex *indexes = (count <= 4096) ? locali : (CFIndex *)malloc(count * sizeof(CFIndex)); 349 if (indexes == NULL) { 350 CFLog(kCFLogLevelError, CFSTR("unable to qsort array - malloc failed")); 351 CRSetCrashLogMessage("qsort - malloc failed"); 352 HALT; 353 } 354 CFSortIndexes(indexes, count, 0, ^(CFIndex a, CFIndex b) { return comparator((char *)list + a * elementSize, (char *)list + b * elementSize, context); }); 355 STACK_BUFFER_DECL(uint8_t, locals, count <= (16 * 1024 / elementSize) ? count * elementSize : 1); 356 void *store = (count <= (16 * 1024 / elementSize)) ? locals : malloc(count * elementSize); 357 overflowResult = _CFPointerSumWouldOverflow(store, count * elementSize, NULL); 358 if (overflowResult != _CFOverflowResultOK) { 359 CFLog(kCFLogLevelError, CFSTR("Unable to qsort array - list: %lu count: %ld elementSize: %ld array - store overflows"), (unsigned long)list, (long)count, (long)elementSize); 360 CRSetCrashLogMessage("qsort - array storage overflow"); 361 HALT; 362 } 363 for (CFIndex idx = 0; idx < count; idx++) { 364 if (sizeof(uintptr_t) == elementSize) { 365 uintptr_t *a = (uintptr_t *)list + indexes[idx]; 366 uintptr_t *b = (uintptr_t *)store + idx; 367 *b = *a; 368 } else { 369 memmove((char *)store + idx * elementSize, (char *)list + indexes[idx] * elementSize, elementSize); 370 } 371 } 372 // no swapping or modification of the original list has occurred until this point 373 memmove(list, store, count * elementSize); 374 if (locals != store) free(store); 375 if (locali != indexes) free(indexes); 376 } 377 378 /* Comparator is passed the address of the values. */ 379 void CFMergeSortArray(void *list, CFIndex count, CFIndex elementSize, CFComparatorFunction comparator, void *context) { 380 if (count < 2 || elementSize < 1) return; 381 _CFOverflowResult overflowResult = _CFPositiveIntegerProductWouldOverflow(count, elementSize, NULL); 382 if (overflowResult != _CFOverflowResultOK) { 383 CFLog(kCFLogLevelError, CFSTR("Unable to mergesort array - count: %ld elementSize: %ld overflows"), (long)count, (long)elementSize); 384 CRSetCrashLogMessage("merge sort - count/elementSize overflow"); 385 HALT; 386 } 387 overflowResult = _CFPointerSumWouldOverflow(list, count * elementSize, NULL); 388 if (overflowResult != _CFOverflowResultOK) { 389 CFLog(kCFLogLevelError, CFSTR("Unable to mergesort array - list: %lu count: %ld elementSize: %ld - array access overflows"), (unsigned long)list, (long)count, (long)elementSize); 390 CRSetCrashLogMessage("merge sort - array access overflow"); 391 HALT; 392 } 393 STACK_BUFFER_DECL(CFIndex, locali, count <= 4096 ? count : 1); 394 CFIndex *indexes = (count <= 4096) ? locali : (CFIndex *)malloc(count * sizeof(CFIndex)); 395 if (indexes == NULL) { 396 CFLog(kCFLogLevelError, CFSTR("unable to mergesort array - malloc failed")); 397 CRSetCrashLogMessage("merge sort - malloc failure"); 398 HALT; 399 } 400 CFSortIndexes(indexes, count, kCFSortStable, ^(CFIndex a, CFIndex b) { return comparator((char *)list + a * elementSize, (char *)list + b * elementSize, context); }); 401 STACK_BUFFER_DECL(uint8_t, locals, count <= (16 * 1024 / elementSize) ? count * elementSize : 1); 402 void *store = (count <= (16 * 1024 / elementSize)) ? locals : malloc(count * elementSize); 403 overflowResult = _CFPointerSumWouldOverflow(store, count * elementSize, NULL); 404 if (overflowResult != _CFOverflowResultOK) { 405 CFLog(kCFLogLevelError, CFSTR("Unable to mergesort array - list: %lu count: %ld elementSize: %ld - array store overflows"), (unsigned long)list, (long)count, (long)elementSize); 406 CRSetCrashLogMessage("merge sort - overflow array storage"); 407 HALT; 408 } 409 for (CFIndex idx = 0; idx < count; idx++) { 410 if (sizeof(uintptr_t) == elementSize) { 411 uintptr_t *a = (uintptr_t *)list + indexes[idx]; 412 uintptr_t *b = (uintptr_t *)store + idx; 413 *b = *a; 414 } else { 415 memmove((char *)store + idx * elementSize, (char *)list + indexes[idx] * elementSize, elementSize); 416 } 417 } 418 // no swapping or modification of the original list has occurred until this point 419 memmove(list, store, count * elementSize); 420 if (locals != store) free(store); 421 if (locali != indexes) free(indexes); 422 } 423 424