| /* CFSortFunctions.c |
| Copyright (c) 1999-2016, Apple Inc. and the Swift project authors |
| |
| Portions Copyright (c) 2014-2016 Apple Inc. and the Swift project authors |
| Licensed under Apache License v2.0 with Runtime Library Exception |
| See http://swift.org/LICENSE.txt for license information |
| See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| Responsibility: Christopher Kane |
| */ |
| |
| #include <CoreFoundation/CFBase.h> |
| #include "CFInternal.h" |
| #if __HAS_DISPATCH__ |
| #include <dispatch/dispatch.h> |
| #if (DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED) && __has_include(<dispatch/private.h>) |
| #include <dispatch/private.h> |
| #endif |
| #endif |
| #include "CFLogUtilities.h" |
| #include "CFInternal.h" |
| |
| #if __has_include(<checkint.h>) |
| #include <checkint.h> |
| #else |
| enum { |
| CHECKINT_NO_ERROR = 0, |
| CHECKINT_OVERFLOW_ERROR = (1 << 0), |
| CHECKINT_TYPE_ERROR = (1 << 1) |
| }; |
| |
| #define __check_int32_add(x, y, err) (x + y) |
| #define __check_uint32_add(x, y, err) (x + y) |
| #define __check_int64_add(x, y, err) (x + y) |
| #define __check_uint64_add(x, y, err) (x + y) |
| |
| #define __check_int32_sub(x, y, err) (x - y) |
| #define __check_uint32_sub(x, y, err) (x - y) |
| #define __check_int64_sub(x, y, err) (x - y) |
| #define __check_uint64_sub(x, y, err) (x - y) |
| |
| #define __check_int32_mul(x, y, err) (x * y) |
| #define __check_uint32_mul(x, y, err) (x * y) |
| #define __check_int64_mul(x, y, err) (x * y) |
| #define __check_uint64_mul(x, y, err) (x * y) |
| |
| #define __check_int32_div(x, y, err) (x / y) |
| #define __check_uint32_div(x, y, err) (x / y) |
| #define __check_int64_div(x, y, err) (x / y) |
| #define __check_uint64_div(x, y, err) (x / y) |
| |
| #define __checkint_int64_mul(x, y, err) __check_int64_mul(x, y, err) |
| #define __checkint_int32_mul(x, y, err) __check_int32_mul(x, y, err) |
| #define __checkint_uint64_add(x, y, err) __check_uint64_add(x, y, err) |
| #define __checkint_uint32_add(x, y, err) __check_uint32_add(x, y, err) |
| |
| #endif |
| |
| enum { |
| kCFSortConcurrent = (1 << 0), |
| kCFSortStable = (1 << 4), |
| }; |
| |
| typedef CFIndex VALUE_TYPE; |
| typedef CFIndex INDEX_TYPE; |
| typedef CFComparisonResult CMP_RESULT_TYPE; |
| typedef CMP_RESULT_TYPE (^COMPARATOR_BLOCK)(VALUE_TYPE, VALUE_TYPE); |
| |
| /* |
| Number of elements in a list and expected number of compares, |
| when the initial short-circuiting compare is not done. |
| 1 0 |
| 2 1 |
| 3 2.667 |
| 4 4.667 |
| 5 7.167 |
| 6 9.833 |
| 7 12.733 |
| 8 15.733 |
| 9 19.167 |
| 10 22.667 |
| 11 26.2857 |
| 12 29.9524 |
| */ |
| |
| static void __CFSimpleMerge(VALUE_TYPE listp[], INDEX_TYPE cnt1, INDEX_TYPE cnt2, VALUE_TYPE tmp[], COMPARATOR_BLOCK cmp) { |
| if (cnt1 <= 0 || cnt2 <= 0) return; |
| // if the last element of listp1 <= the first of listp2, lists are already ordered |
| if (16 < cnt1 + cnt2 && cmp(listp[cnt1 - 1], listp[cnt1]) <= 0) return; |
| |
| INDEX_TYPE idx = 0, idx1 = 0, idx2 = cnt1; |
| for (;;) { |
| if (cnt1 <= idx1) { |
| while (idx--) { |
| listp[idx] = tmp[idx]; |
| } |
| return; |
| } |
| if (cnt1 + cnt2 <= idx2) { |
| for (INDEX_TYPE t = cnt1 + cnt2 - 1; idx <= t; t--) { |
| listp[t] = listp[t - cnt2]; |
| } |
| while (idx--) { |
| listp[idx] = tmp[idx]; |
| } |
| return; |
| } |
| VALUE_TYPE v1 = listp[idx1], v2 = listp[idx2]; |
| if (cmp(v1, v2) <= 0) { |
| tmp[idx] = v1; |
| idx1++; |
| } else { |
| tmp[idx] = v2; |
| idx2++; |
| } |
| idx++; |
| } |
| } |
| |
| static void __CFSimpleMergeSort(VALUE_TYPE listp[], INDEX_TYPE cnt, VALUE_TYPE tmp[], COMPARATOR_BLOCK cmp) { |
| if (cnt < 2) { |
| /* do nothing */ |
| } else if (2 == cnt) { |
| VALUE_TYPE v0 = listp[0], v1 = listp[1]; |
| if (0 < cmp(v0, v1)) { |
| listp[0] = v1; |
| listp[1] = v0; |
| } |
| } else if (3 == cnt) { |
| VALUE_TYPE v0 = listp[0], v1 = listp[1], v2 = listp[2], vt; |
| if (0 < cmp(v0, v1)) { |
| vt = v0; |
| v0 = v1; |
| v1 = vt; |
| } |
| if (0 < cmp(v1, v2)) { |
| vt = v1; |
| v1 = v2; |
| v2 = vt; |
| if (0 < cmp(v0, v1)) { |
| vt = v0; |
| v0 = v1; |
| v1 = vt; |
| } |
| } |
| listp[0] = v0; |
| listp[1] = v1; |
| listp[2] = v2; |
| } else { |
| INDEX_TYPE half_cnt = cnt / 2; |
| __CFSimpleMergeSort(listp, half_cnt, tmp, cmp); |
| __CFSimpleMergeSort(listp + half_cnt, cnt - half_cnt, tmp, cmp); |
| __CFSimpleMerge(listp, half_cnt, cnt - half_cnt, tmp, cmp); |
| } |
| } |
| |
| #if __HAS_DISPATCH__ |
| |
| // if !right, put the cnt1 smallest values in tmp, else put the cnt2 largest values in tmp |
| static void __CFSortIndexesNMerge(VALUE_TYPE listp1[], INDEX_TYPE cnt1, VALUE_TYPE listp2[], INDEX_TYPE cnt2, VALUE_TYPE tmp[], size_t right, COMPARATOR_BLOCK cmp) { |
| // if the last element of listp1 <= the first of listp2, lists are already ordered |
| if (16 < cnt1 + cnt2 && cmp(listp1[cnt1 - 1], listp2[0]) <= 0) { |
| memmove(tmp, (right ? listp2 : listp1), (right ? cnt2 : cnt1) * sizeof(VALUE_TYPE)); |
| return; |
| } |
| |
| if (right) { |
| VALUE_TYPE *listp1_end = listp1; |
| VALUE_TYPE *listp2_end = listp2; |
| VALUE_TYPE *tmp_end = tmp; |
| listp1 += cnt1 - 1; |
| listp2 += cnt2 - 1; |
| tmp += cnt2; |
| while (tmp_end < tmp) { |
| tmp--; |
| if (listp2 < listp2_end) { |
| listp1--; |
| *tmp = *listp1; |
| } else if (listp1 < listp1_end) { |
| listp2--; |
| *tmp = *listp2; |
| } else { |
| VALUE_TYPE v1 = *listp1, v2 = *listp2; |
| CMP_RESULT_TYPE res = cmp(v1, v2); |
| if (res <= 0) { |
| *tmp = v2; |
| listp2--; |
| } else { |
| *tmp = v1; |
| listp1--; |
| } |
| } |
| } |
| } else { |
| VALUE_TYPE *listp1_end = listp1 + cnt1; |
| VALUE_TYPE *listp2_end = listp2 + cnt2; |
| VALUE_TYPE *tmp_end = tmp + cnt1; |
| while (tmp < tmp_end) { |
| if (listp2_end <= listp2) { |
| *tmp = *listp1; |
| listp1++; |
| } else if (listp1_end <= listp1) { |
| *tmp = *listp2; |
| listp2++; |
| } else { |
| VALUE_TYPE v1 = *listp1, v2 = *listp2; |
| CMP_RESULT_TYPE res = cmp(v1, v2); |
| if (res <= 0) { |
| *tmp = v1; |
| listp1++; |
| } else { |
| *tmp = v2; |
| listp2++; |
| } |
| } |
| tmp++; |
| } |
| } |
| } |
| |
| /* Merging algorithm based on |
| "A New Parallel Sorting Algorithm based on Odd-Even Mergesort", Ezequiel Herruzo, et al |
| */ |
| static void __CFSortIndexesN(VALUE_TYPE listp[], INDEX_TYPE count, int32_t ncores, CMP_RESULT_TYPE (^cmp)(INDEX_TYPE, INDEX_TYPE)) { |
| /* Divide the array up into up to ncores, multiple-of-16-sized, chunks */ |
| INDEX_TYPE sz = ((((count + ncores - 1) / ncores) + 15) / 16) * 16; |
| INDEX_TYPE num_sect = (count + sz - 1) / sz; |
| INDEX_TYPE last_sect_len = count + sz - sz * num_sect; |
| |
| STACK_BUFFER_DECL(VALUE_TYPE *, stack_tmps, num_sect); |
| for (INDEX_TYPE idx = 0; idx < num_sect; idx++) { |
| stack_tmps[idx] = (VALUE_TYPE *)malloc(sz * sizeof(VALUE_TYPE)); |
| } |
| VALUE_TYPE **tmps = stack_tmps; |
| |
| dispatch_queue_t q = __CFDispatchQueueGetGenericMatchingCurrent(); |
| dispatch_apply(num_sect, q, ^(size_t sect) { |
| INDEX_TYPE sect_len = (sect < num_sect - 1) ? sz : last_sect_len; |
| __CFSimpleMergeSort(listp + sect * sz, sect_len, tmps[sect], cmp); // naturally stable |
| }); |
| |
| INDEX_TYPE even_phase_cnt = ((num_sect / 2) * 2); |
| INDEX_TYPE odd_phase_cnt = (((num_sect - 1) / 2) * 2); |
| for (INDEX_TYPE idx = 0; idx < (num_sect + 1) / 2; idx++) { |
| dispatch_apply(even_phase_cnt, q, ^(size_t sect) { // merge even |
| size_t right = sect & (size_t)0x1; |
| VALUE_TYPE *left_base = listp + sect * sz - (right ? sz : 0); |
| VALUE_TYPE *right_base = listp + sect * sz + (right ? 0 : sz); |
| INDEX_TYPE sect2_len = (sect + 1 + (right ? 0 : 1) == num_sect) ? last_sect_len : sz; |
| __CFSortIndexesNMerge(left_base, sz, right_base, sect2_len, tmps[sect], right, cmp); |
| }); |
| if (num_sect & 0x1) { |
| memmove(tmps[num_sect - 1], listp + (num_sect - 1) * sz, last_sect_len * sizeof(VALUE_TYPE)); |
| } |
| dispatch_apply(odd_phase_cnt, q, ^(size_t sect) { // merge odd |
| size_t right = sect & (size_t)0x1; |
| VALUE_TYPE *left_base = tmps[sect + (right ? 0 : 1)]; |
| VALUE_TYPE *right_base = tmps[sect + (right ? 1 : 2)]; |
| INDEX_TYPE sect2_len = (sect + 1 + (right ? 1 : 2) == num_sect) ? last_sect_len : sz; |
| __CFSortIndexesNMerge(left_base, sz, right_base, sect2_len, listp + sect * sz + sz, right, cmp); |
| }); |
| memmove(listp + 0 * sz, tmps[0], sz * sizeof(VALUE_TYPE)); |
| if (!(num_sect & 0x1)) { |
| memmove(listp + (num_sect - 1) * sz, tmps[num_sect - 1], last_sect_len * sizeof(VALUE_TYPE)); |
| } |
| } |
| |
| for (INDEX_TYPE idx = 0; idx < num_sect; idx++) { |
| free(stack_tmps[idx]); |
| } |
| } |
| #endif |
| |
| // fills an array of indexes (of length count) giving the indexes 0 - count-1, as sorted by the comparator block |
| void CFSortIndexes(CFIndex *indexBuffer, CFIndex count, CFOptionFlags opts, CFComparisonResult (^cmp)(CFIndex, CFIndex)) { |
| if (count < 1) return; |
| if (INTPTR_MAX / sizeof(CFIndex) < count) return; |
| int32_t ncores = 0; |
| if (opts & kCFSortConcurrent) { |
| ncores = __CFActiveProcessorCount(); |
| if (count < 160 || ncores < 2) { |
| opts = (opts & ~kCFSortConcurrent); |
| } else if (count < 640 && 2 < ncores) { |
| ncores = 2; |
| } else if (count < 3200 && 4 < ncores) { |
| ncores = 4; |
| } else if (count < 16000 && 8 < ncores) { |
| ncores = 8; |
| } |
| if (16 < ncores) { |
| ncores = 16; |
| } |
| } |
| #if __HAS_DISPATCH__ |
| if (count <= 65536) { |
| for (CFIndex idx = 0; idx < count; idx++) indexBuffer[idx] = idx; |
| } else { |
| /* Specifically hard-coded to 8; the count has to be very large before more chunks and/or cores is worthwhile. */ |
| CFIndex sz = ((((size_t)count + 15) / 16) * 16) / 8; |
| dispatch_apply(8, __CFDispatchQueueGetGenericMatchingCurrent(), ^(size_t n) { |
| CFIndex idx = n * sz, lim = __CFMin(idx + sz, count); |
| for (; idx < lim; idx++) indexBuffer[idx] = idx; |
| }); |
| } |
| #else |
| for (CFIndex idx = 0; idx < count; idx++) indexBuffer[idx] = idx; |
| #endif |
| #if __HAS_DISPATCH__ |
| if (opts & kCFSortConcurrent) { |
| __CFSortIndexesN(indexBuffer, count, ncores, cmp); // naturally stable |
| return; |
| } |
| #endif |
| STACK_BUFFER_DECL(VALUE_TYPE, local, count <= 4096 ? count : 1); |
| VALUE_TYPE *tmp = (count <= 4096) ? local : (VALUE_TYPE *)malloc(count * sizeof(VALUE_TYPE)); |
| __CFSimpleMergeSort(indexBuffer, count, tmp, cmp); // naturally stable |
| if (local != tmp) free(tmp); |
| } |
| |
| typedef CF_ENUM(uint8_t, _CFOverflowResult) { |
| _CFOverflowResultOK = 0, |
| _CFOverflowResultNegativeParameters, |
| _CFOverflowResultOverflows, |
| }; |
| |
| // Overflow utilities for positive integers |
| CF_INLINE _CFOverflowResult _CFIntegerProductWouldOverflow(CFIndex si_a, CFIndex si_b) { |
| _CFOverflowResult result = _CFOverflowResultOK; |
| if (si_a < 0 || si_b < 0) { |
| // we explicitly only implement a subset of the overflow checking, so report failure if out of domain |
| result = _CFOverflowResultNegativeParameters; |
| } else { |
| int32_t err = CHECKINT_NO_ERROR; |
| #if __LP64__ |
| __checkint_int64_mul(si_a, si_b, &err); |
| #else |
| __checkint_int32_mul(si_a, si_b, &err); |
| #endif |
| if (err != CHECKINT_NO_ERROR) { |
| result = _CFOverflowResultOverflows; |
| } |
| } |
| return result; |
| } |
| CF_INLINE _CFOverflowResult _CFPointerSumWouldOverflow(void *p, size_t n) { |
| _CFOverflowResult result = _CFOverflowResultOK; |
| int32_t err = CHECKINT_NO_ERROR; |
| #if __LP64__ |
| __checkint_uint64_add((uint64_t)p, (uint64_t)n, &err); |
| #else |
| __checkint_uint32_add((uint32_t)p, (uint32_t)n, &err); |
| #endif |
| if (err != CHECKINT_NO_ERROR) { |
| result = _CFOverflowResultOverflows; |
| } |
| return result; |
| } |
| |
| /* Comparator is passed the address of the values. */ |
| void CFQSortArray(void *list, CFIndex count, CFIndex elementSize, CFComparatorFunction comparator, void *context) { |
| if (count < 2 || elementSize < 1) return; |
| _CFOverflowResult overflowResult = _CFIntegerProductWouldOverflow(count, elementSize); |
| if (overflowResult != _CFOverflowResultOK) { |
| CFLog(kCFLogLevelError, CFSTR("Unable to qsort array - count: %ld elementSize: %ld product overflows"), (long)count, (long)elementSize); |
| CRSetCrashLogMessage("qsort - count/elementSize overflow"); |
| HALT; |
| } |
| overflowResult = _CFPointerSumWouldOverflow(list, count * elementSize); |
| if (overflowResult != _CFOverflowResultOK) { |
| CFLog(kCFLogLevelError, CFSTR("Unable to qsort array - list: %lu count: %ld elementSize: %ld - array access overflows"), (unsigned long)list, (long)count, (long)elementSize); |
| CRSetCrashLogMessage("qsort - array access overflow"); |
| HALT; |
| } |
| STACK_BUFFER_DECL(CFIndex, locali, count <= 4096 ? count : 1); |
| CFIndex *indexes = (count <= 4096) ? locali : (CFIndex *)malloc(count * sizeof(CFIndex)); |
| if (indexes == NULL) { |
| CFLog(kCFLogLevelError, CFSTR("unable to qsort array - malloc failed")); |
| CRSetCrashLogMessage("qsort - malloc failed"); |
| HALT; |
| } |
| CFSortIndexes(indexes, count, 0, ^(CFIndex a, CFIndex b) { return comparator((char *)list + a * elementSize, (char *)list + b * elementSize, context); }); |
| STACK_BUFFER_DECL(uint8_t, locals, count <= (16 * 1024 / elementSize) ? count * elementSize : 1); |
| void *store = (count <= (16 * 1024 / elementSize)) ? locals : malloc(count * elementSize); |
| overflowResult = _CFPointerSumWouldOverflow(store, count * elementSize); |
| if (overflowResult != _CFOverflowResultOK) { |
| CFLog(kCFLogLevelError, CFSTR("Unable to qsort array - list: %lu count: %ld elementSize: %ld array - store overflows"), (unsigned long)list, (long)count, (long)elementSize); |
| CRSetCrashLogMessage("qsort - array storage overflow"); |
| HALT; |
| } |
| for (CFIndex idx = 0; idx < count; idx++) { |
| if (sizeof(uintptr_t) == elementSize) { |
| uintptr_t *a = (uintptr_t *)list + indexes[idx]; |
| uintptr_t *b = (uintptr_t *)store + idx; |
| *b = *a; |
| } else { |
| memmove((char *)store + idx * elementSize, (char *)list + indexes[idx] * elementSize, elementSize); |
| } |
| } |
| // no swapping or modification of the original list has occurred until this point |
| memmove(list, store, count * elementSize); |
| if (locals != store) free(store); |
| if (locali != indexes) free(indexes); |
| } |
| |
| /* Comparator is passed the address of the values. */ |
| void CFMergeSortArray(void *list, CFIndex count, CFIndex elementSize, CFComparatorFunction comparator, void *context) { |
| if (count < 2 || elementSize < 1) return; |
| _CFOverflowResult overflowResult = _CFIntegerProductWouldOverflow(count, elementSize); |
| if (overflowResult != _CFOverflowResultOK) { |
| CFLog(kCFLogLevelError, CFSTR("Unable to mergesort array - count: %ld elementSize: %ld overflows"), (long)count, (long)elementSize); |
| CRSetCrashLogMessage("merge sort - count/elementSize overflow"); |
| HALT; |
| } |
| overflowResult = _CFPointerSumWouldOverflow(list, count * elementSize); |
| if (overflowResult != _CFOverflowResultOK) { |
| CFLog(kCFLogLevelError, CFSTR("Unable to mergesort array - list: %lu count: %ld elementSize: %ld - array access overflows"), (unsigned long)list, (long)count, (long)elementSize); |
| CRSetCrashLogMessage("merge sort - array access overflow"); |
| HALT; |
| } |
| STACK_BUFFER_DECL(CFIndex, locali, count <= 4096 ? count : 1); |
| CFIndex *indexes = (count <= 4096) ? locali : (CFIndex *)malloc(count * sizeof(CFIndex)); |
| if (indexes == NULL) { |
| CFLog(kCFLogLevelError, CFSTR("unable to mergesort array - malloc failed")); |
| CRSetCrashLogMessage("merge sort - malloc failure"); |
| HALT; |
| } |
| CFSortIndexes(indexes, count, kCFSortStable, ^(CFIndex a, CFIndex b) { return comparator((char *)list + a * elementSize, (char *)list + b * elementSize, context); }); |
| STACK_BUFFER_DECL(uint8_t, locals, count <= (16 * 1024 / elementSize) ? count * elementSize : 1); |
| void *store = (count <= (16 * 1024 / elementSize)) ? locals : malloc(count * elementSize); |
| overflowResult = _CFPointerSumWouldOverflow(store, count * elementSize); |
| if (overflowResult != _CFOverflowResultOK) { |
| CFLog(kCFLogLevelError, CFSTR("Unable to mergesort array - list: %lu count: %ld elementSize: %ld - array store overflows"), (unsigned long)list, (long)count, (long)elementSize); |
| CRSetCrashLogMessage("merge sort - overflow array storage"); |
| HALT; |
| } |
| for (CFIndex idx = 0; idx < count; idx++) { |
| if (sizeof(uintptr_t) == elementSize) { |
| uintptr_t *a = (uintptr_t *)list + indexes[idx]; |
| uintptr_t *b = (uintptr_t *)store + idx; |
| *b = *a; |
| } else { |
| memmove((char *)store + idx * elementSize, (char *)list + indexes[idx] * elementSize, elementSize); |
| } |
| } |
| // no swapping or modification of the original list has occurred until this point |
| memmove(list, store, count * elementSize); |
| if (locals != store) free(store); |
| if (locali != indexes) free(indexes); |
| } |
| |
| |
