/ CFBinaryHeap.c
CFBinaryHeap.c
1 /* 2 * Copyright (c) 2015 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 24 /* CFBinaryHeap.c 25 Copyright (c) 1998-2014, Apple Inc. All rights reserved. 26 Responsibility: Christopher Kane 27 */ 28 29 #include <CoreFoundation/CFBinaryHeap.h> 30 #include <CoreFoundation/CFPriv.h> 31 #include "CFInternal.h" 32 33 const CFBinaryHeapCallBacks kCFStringBinaryHeapCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, (CFComparisonResult (*)(const void *, const void *, void *))CFStringCompare}; 34 35 struct __CFBinaryHeapBucket { 36 void *_item; 37 }; 38 39 CF_INLINE CFIndex __CFBinaryHeapRoundUpCapacity(CFIndex capacity) { 40 if (capacity < 4) return 4; 41 return (1 << flsl(capacity)); 42 } 43 44 CF_INLINE CFIndex __CFBinaryHeapNumBucketsForCapacity(CFIndex capacity) { 45 return capacity; 46 } 47 48 struct __CFBinaryHeap { 49 CFRuntimeBase _base; 50 CFIndex _count; /* number of objects */ 51 CFIndex _capacity; /* maximum number of objects */ 52 CFBinaryHeapCallBacks _callbacks; 53 CFBinaryHeapCompareContext _context; 54 struct __CFBinaryHeapBucket *_buckets; 55 }; 56 57 CF_INLINE CFIndex __CFBinaryHeapCount(CFBinaryHeapRef heap) { 58 return heap->_count; 59 } 60 61 CF_INLINE void __CFBinaryHeapSetCount(CFBinaryHeapRef heap, CFIndex v) { 62 /* for a CFBinaryHeap, _bucketsUsed == _count */ 63 } 64 65 CF_INLINE CFIndex __CFBinaryHeapCapacity(CFBinaryHeapRef heap) { 66 return heap->_capacity; 67 } 68 69 CF_INLINE void __CFBinaryHeapSetCapacity(CFBinaryHeapRef heap, CFIndex v) { 70 /* for a CFBinaryHeap, _bucketsNum == _capacity */ 71 } 72 73 CF_INLINE CFIndex __CFBinaryHeapNumBucketsUsed(CFBinaryHeapRef heap) { 74 return heap->_count; 75 } 76 77 CF_INLINE void __CFBinaryHeapSetNumBucketsUsed(CFBinaryHeapRef heap, CFIndex v) { 78 heap->_count = v; 79 } 80 81 CF_INLINE CFIndex __CFBinaryHeapNumBuckets(CFBinaryHeapRef heap) { 82 return heap->_capacity; 83 } 84 85 CF_INLINE void __CFBinaryHeapSetNumBuckets(CFBinaryHeapRef heap, CFIndex v) { 86 heap->_capacity = v; 87 } 88 89 enum { /* bits 1-0 */ 90 kCFBinaryHeapMutable = 0x1, /* changeable and variable capacity */ 91 }; 92 93 /* Bits 4-5 are used by GC */ 94 95 CF_INLINE bool isStrongMemory_Heap(CFTypeRef collection) { 96 return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_cfinfo[CF_INFO_BITS], 4, 4) == 0; 97 } 98 99 CF_INLINE UInt32 __CFBinaryHeapMutableVariety(const void *cf) { 100 return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2); 101 } 102 103 CF_INLINE void __CFBinaryHeapSetMutableVariety(void *cf, UInt32 v) { 104 __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2, v); 105 } 106 107 CF_INLINE UInt32 __CFBinaryHeapMutableVarietyFromFlags(UInt32 flags) { 108 return __CFBitfieldGetValue(flags, 1, 0); 109 } 110 111 static Boolean __CFBinaryHeapEqual(CFTypeRef cf1, CFTypeRef cf2) { 112 CFBinaryHeapRef heap1 = (CFBinaryHeapRef)cf1; 113 CFBinaryHeapRef heap2 = (CFBinaryHeapRef)cf2; 114 CFComparisonResult (*compare)(const void *, const void *, void *); 115 CFIndex idx; 116 CFIndex cnt; 117 const void **list1, **list2, *buffer[256]; 118 cnt = __CFBinaryHeapCount(heap1); 119 if (cnt != __CFBinaryHeapCount(heap2)) return false; 120 compare = heap1->_callbacks.compare; 121 if (compare != heap2->_callbacks.compare) return false; 122 if (0 == cnt) return true; /* after function comparison */ 123 list1 = (cnt <= 128) ? (const void **)buffer : (const void **)CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * cnt * sizeof(void *), 0); // GC OK 124 if (__CFOASafe && list1 != buffer) __CFSetLastAllocationEventName(list1, "CFBinaryHeap (temp)"); 125 list2 = (cnt <= 128) ? buffer + 128 : list1 + cnt; 126 CFBinaryHeapGetValues(heap1, list1); 127 CFBinaryHeapGetValues(heap2, list2); 128 for (idx = 0; idx < cnt; idx++) { 129 const void *val1 = list1[idx]; 130 const void *val2 = list2[idx]; 131 // CF: which context info should be passed in? both? 132 // CF: if the context infos are not equal, should the heaps not be equal? 133 if (val1 != val2) { 134 if (NULL == compare) return false; 135 if (!compare(val1, val2, heap1->_context.info)) return false; 136 } 137 } 138 if (list1 != buffer) CFAllocatorDeallocate(CFGetAllocator(heap1), list1); // GC OK 139 return true; 140 } 141 142 static CFHashCode __CFBinaryHeapHash(CFTypeRef cf) { 143 CFBinaryHeapRef heap = (CFBinaryHeapRef)cf; 144 return __CFBinaryHeapCount(heap); 145 } 146 147 static CFStringRef __CFBinaryHeapCopyDescription(CFTypeRef cf) { 148 CFBinaryHeapRef heap = (CFBinaryHeapRef)cf; 149 CFMutableStringRef result; 150 CFIndex idx; 151 CFIndex cnt; 152 const void **list, *buffer[256]; 153 cnt = __CFBinaryHeapCount(heap); 154 result = CFStringCreateMutable(CFGetAllocator(heap), 0); 155 CFStringAppendFormat(result, NULL, CFSTR("<CFBinaryHeap %p [%p]>{count = %lu, capacity = %lu, objects = (\n"), cf, CFGetAllocator(heap), (unsigned long)cnt, (unsigned long)__CFBinaryHeapCapacity(heap)); 156 list = (cnt <= 128) ? (const void **)buffer : (const void **)CFAllocatorAllocate(kCFAllocatorSystemDefault, cnt * sizeof(void *), 0); // GC OK 157 if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(list, "CFBinaryHeap (temp)"); 158 CFBinaryHeapGetValues(heap, list); 159 for (idx = 0; idx < cnt; idx++) { 160 CFStringRef desc = NULL; 161 const void *item = list[idx]; 162 if (NULL != heap->_callbacks.copyDescription) { 163 desc = heap->_callbacks.copyDescription(item); 164 } 165 if (NULL != desc) { 166 CFStringAppendFormat(result, NULL, CFSTR("\t%lu : %@\n"), (unsigned long)idx, desc); 167 CFRelease(desc); 168 } else { 169 CFStringAppendFormat(result, NULL, CFSTR("\t%lu : <%p>\n"), (unsigned long)idx, item); 170 } 171 } 172 CFStringAppend(result, CFSTR(")}")); 173 if (list != buffer) CFAllocatorDeallocate(CFGetAllocator(heap), list); // GC OK 174 return result; 175 } 176 177 static void __CFBinaryHeapDeallocate(CFTypeRef cf) { 178 CFBinaryHeapRef heap = (CFBinaryHeapRef)cf; 179 CFAllocatorRef allocator = CFGetAllocator(heap); 180 if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) { 181 if (heap->_callbacks.retain == NULL && heap->_callbacks.release == NULL) 182 return; // GC: keep heap intact during finalization. 183 } 184 // CF: should make the heap mutable here first, a la CFArrayDeallocate 185 CFBinaryHeapRemoveAllValues(heap); 186 // CF: does not release the context info 187 if (__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable) { 188 _CFAllocatorDeallocateGC(allocator, heap->_buckets); 189 } 190 } 191 192 static CFTypeID __kCFBinaryHeapTypeID = _kCFRuntimeNotATypeID; 193 194 static const CFRuntimeClass __CFBinaryHeapClass = { 195 _kCFRuntimeScannedObject, 196 "CFBinaryHeap", 197 NULL, // init 198 NULL, // copy 199 __CFBinaryHeapDeallocate, 200 __CFBinaryHeapEqual, 201 __CFBinaryHeapHash, 202 NULL, // 203 __CFBinaryHeapCopyDescription 204 }; 205 206 CFTypeID CFBinaryHeapGetTypeID(void) { 207 static dispatch_once_t initOnce; 208 dispatch_once(&initOnce, ^{ __kCFBinaryHeapTypeID = _CFRuntimeRegisterClass(&__CFBinaryHeapClass); }); 209 return __kCFBinaryHeapTypeID; 210 } 211 212 static CFBinaryHeapRef __CFBinaryHeapInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const void **values, CFIndex numValues, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) { 213 CFBinaryHeapRef memory; 214 CFIndex idx; 215 CFIndex size; 216 217 CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity); 218 CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues); 219 size = sizeof(struct __CFBinaryHeap) - sizeof(CFRuntimeBase); 220 if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) { 221 if (!callBacks || (callBacks->retain == NULL && callBacks->release == NULL)) { 222 __CFBitfieldSetValue(flags, 4, 4, 1); // setWeak 223 } 224 } 225 226 memory = (CFBinaryHeapRef)_CFRuntimeCreateInstance(allocator, CFBinaryHeapGetTypeID(), size, NULL); 227 if (NULL == memory) { 228 return NULL; 229 } 230 __CFBinaryHeapSetCapacity(memory, __CFBinaryHeapRoundUpCapacity(1)); 231 __CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(__CFBinaryHeapRoundUpCapacity(1))); 232 void *buckets = _CFAllocatorAllocateGC(allocator, __CFBinaryHeapNumBuckets(memory) * sizeof(struct __CFBinaryHeapBucket), isStrongMemory_Heap(memory) ? __kCFAllocatorGCScannedMemory : 0); 233 __CFAssignWithWriteBarrier((void **)&memory->_buckets, buckets); 234 if (__CFOASafe) __CFSetLastAllocationEventName(memory->_buckets, "CFBinaryHeap (store)"); 235 if (NULL == memory->_buckets) { 236 CFRelease(memory); 237 return NULL; 238 } 239 __CFBinaryHeapSetNumBucketsUsed(memory, 0); 240 __CFBinaryHeapSetCount(memory, 0); 241 if (NULL != callBacks) { 242 memory->_callbacks.retain = callBacks->retain; 243 memory->_callbacks.release = callBacks->release; 244 memory->_callbacks.copyDescription = callBacks->copyDescription; 245 memory->_callbacks.compare = callBacks->compare; 246 } else { 247 memory->_callbacks.retain = 0; 248 memory->_callbacks.release = 0; 249 memory->_callbacks.copyDescription = 0; 250 memory->_callbacks.compare = 0; 251 } 252 if (compareContext) memcpy(&memory->_context, compareContext, sizeof(CFBinaryHeapCompareContext)); 253 // CF: retain info for proper operation 254 __CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapMutable); 255 for (idx = 0; idx < numValues; idx++) { 256 CFBinaryHeapAddValue(memory, values[idx]); 257 } 258 __CFBinaryHeapSetMutableVariety(memory, __CFBinaryHeapMutableVarietyFromFlags(flags)); 259 return memory; 260 } 261 262 CFBinaryHeapRef CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) { 263 return __CFBinaryHeapInit(allocator, kCFBinaryHeapMutable, capacity, NULL, 0, callBacks, compareContext); 264 } 265 266 CFBinaryHeapRef CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap) { 267 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 268 return __CFBinaryHeapInit(allocator, kCFBinaryHeapMutable, capacity, (const void **)heap->_buckets, __CFBinaryHeapCount(heap), &(heap->_callbacks), &(heap->_context)); 269 } 270 271 CFIndex CFBinaryHeapGetCount(CFBinaryHeapRef heap) { 272 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 273 return __CFBinaryHeapCount(heap); 274 } 275 276 CFIndex CFBinaryHeapGetCountOfValue(CFBinaryHeapRef heap, const void *value) { 277 CFComparisonResult (*compare)(const void *, const void *, void *); 278 CFIndex idx; 279 CFIndex cnt = 0, length; 280 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 281 compare = heap->_callbacks.compare; 282 length = __CFBinaryHeapCount(heap); 283 for (idx = 0; idx < length; idx++) { 284 const void *item = heap->_buckets[idx]._item; 285 if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) { 286 cnt++; 287 } 288 } 289 return cnt; 290 } 291 292 Boolean CFBinaryHeapContainsValue(CFBinaryHeapRef heap, const void *value) { 293 CFComparisonResult (*compare)(const void *, const void *, void *); 294 CFIndex idx; 295 CFIndex length; 296 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 297 compare = heap->_callbacks.compare; 298 length = __CFBinaryHeapCount(heap); 299 for (idx = 0; idx < length; idx++) { 300 const void *item = heap->_buckets[idx]._item; 301 if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) { 302 return true; 303 } 304 } 305 return false; 306 } 307 308 const void *CFBinaryHeapGetMinimum(CFBinaryHeapRef heap) { 309 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 310 CFAssert1(0 < __CFBinaryHeapCount(heap), __kCFLogAssertion, "%s(): binary heap is empty", __PRETTY_FUNCTION__); 311 return (0 < __CFBinaryHeapCount(heap)) ? heap->_buckets[0]._item : NULL; 312 } 313 314 Boolean CFBinaryHeapGetMinimumIfPresent(CFBinaryHeapRef heap, const void **value) { 315 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 316 if (0 == __CFBinaryHeapCount(heap)) return false; 317 if (NULL != value) __CFAssignWithWriteBarrier((void **)value, heap->_buckets[0]._item); 318 return true; 319 } 320 321 void CFBinaryHeapGetValues(CFBinaryHeapRef heap, const void **values) { 322 CFBinaryHeapRef heapCopy; 323 CFIndex idx; 324 CFIndex cnt; 325 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 326 CFAssert1(NULL != values, __kCFLogAssertion, "%s(): pointer to values may not be NULL", __PRETTY_FUNCTION__); 327 cnt = __CFBinaryHeapCount(heap); 328 if (0 == cnt) return; 329 heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap); 330 idx = 0; 331 while (0 < __CFBinaryHeapCount(heapCopy)) { 332 const void *value = CFBinaryHeapGetMinimum(heapCopy); 333 CFBinaryHeapRemoveMinimumValue(heapCopy); 334 values[idx++] = value; 335 } 336 CFRelease(heapCopy); 337 } 338 339 void CFBinaryHeapApplyFunction(CFBinaryHeapRef heap, CFBinaryHeapApplierFunction applier, void *context) { 340 CFBinaryHeapRef heapCopy; 341 CFIndex cnt; 342 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 343 CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__); 344 cnt = __CFBinaryHeapCount(heap); 345 if (0 == cnt) return; 346 heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap); 347 while (0 < __CFBinaryHeapCount(heapCopy)) { 348 const void *value = CFBinaryHeapGetMinimum(heapCopy); 349 CFBinaryHeapRemoveMinimumValue(heapCopy); 350 applier(value, context); 351 } 352 CFRelease(heapCopy); 353 } 354 355 static void __CFBinaryHeapGrow(CFBinaryHeapRef heap, CFIndex numNewValues) { 356 CFIndex oldCount = __CFBinaryHeapCount(heap); 357 CFIndex capacity = __CFBinaryHeapRoundUpCapacity(oldCount + numNewValues); 358 CFAllocatorRef allocator = CFGetAllocator(heap); 359 __CFBinaryHeapSetCapacity(heap, capacity); 360 __CFBinaryHeapSetNumBuckets(heap, __CFBinaryHeapNumBucketsForCapacity(capacity)); 361 void *buckets = _CFAllocatorReallocateGC(allocator, heap->_buckets, __CFBinaryHeapNumBuckets(heap) * sizeof(struct __CFBinaryHeapBucket), isStrongMemory_Heap(heap) ? __kCFAllocatorGCScannedMemory : 0); 362 __CFAssignWithWriteBarrier((void **)&heap->_buckets, buckets); 363 if (__CFOASafe) __CFSetLastAllocationEventName(heap->_buckets, "CFBinaryHeap (store)"); 364 if (NULL == heap->_buckets) HALT; 365 } 366 367 void CFBinaryHeapAddValue(CFBinaryHeapRef heap, const void *value) { 368 CFIndex idx, pidx; 369 CFIndex cnt; 370 CFAllocatorRef allocator = CFGetAllocator(heap); 371 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 372 switch (__CFBinaryHeapMutableVariety(heap)) { 373 case kCFBinaryHeapMutable: 374 if (__CFBinaryHeapNumBucketsUsed(heap) == __CFBinaryHeapCapacity(heap)) 375 __CFBinaryHeapGrow(heap, 1); 376 break; 377 } 378 cnt = __CFBinaryHeapCount(heap); 379 idx = cnt; 380 __CFBinaryHeapSetNumBucketsUsed(heap, cnt + 1); 381 __CFBinaryHeapSetCount(heap, cnt + 1); 382 CFComparisonResult (*compare)(const void *, const void *, void *) = heap->_callbacks.compare; 383 pidx = (idx - 1) >> 1; 384 while (0 < idx) { 385 void *item = heap->_buckets[pidx]._item; 386 if ((!compare && item <= value) || (compare && kCFCompareGreaterThan != compare(item, value, heap->_context.info))) break; 387 __CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, item); 388 idx = pidx; 389 pidx = (idx - 1) >> 1; 390 } 391 if (heap->_callbacks.retain) { 392 __CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, (void *)heap->_callbacks.retain(allocator, (void *)value)); 393 } else { 394 __CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, (void *)value); 395 } 396 } 397 398 void CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap) { 399 void *val; 400 CFIndex idx, cidx; 401 CFIndex cnt; 402 CFAllocatorRef allocator; 403 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 404 cnt = __CFBinaryHeapCount(heap); 405 if (0 == cnt) return; 406 idx = 0; 407 __CFBinaryHeapSetNumBucketsUsed(heap, cnt - 1); 408 __CFBinaryHeapSetCount(heap, cnt - 1); 409 CFComparisonResult (*compare)(const void *, const void *, void *) = heap->_callbacks.compare; 410 allocator = CFGetAllocator(heap); 411 if (heap->_callbacks.release) 412 heap->_callbacks.release(allocator, heap->_buckets[idx]._item); 413 val = heap->_buckets[cnt - 1]._item; 414 cidx = (idx << 1) + 1; 415 while (cidx < __CFBinaryHeapCount(heap)) { 416 void *item = heap->_buckets[cidx]._item; 417 if (cidx + 1 < __CFBinaryHeapCount(heap)) { 418 void *item2 = heap->_buckets[cidx + 1]._item; 419 if ((!compare && item > item2) || (compare && kCFCompareGreaterThan == compare(item, item2, heap->_context.info))) { 420 cidx++; 421 item = item2; 422 } 423 } 424 if ((!compare && item > val) || (compare && kCFCompareGreaterThan == compare(item, val, heap->_context.info))) break; 425 __CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, item); 426 idx = cidx; 427 cidx = (idx << 1) + 1; 428 } 429 __CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, val); 430 } 431 432 void CFBinaryHeapRemoveAllValues(CFBinaryHeapRef heap) { 433 CFIndex idx; 434 CFIndex cnt; 435 __CFGenericValidateType(heap, CFBinaryHeapGetTypeID()); 436 cnt = __CFBinaryHeapCount(heap); 437 if (heap->_callbacks.release) 438 for (idx = 0; idx < cnt; idx++) 439 heap->_callbacks.release(CFGetAllocator(heap), heap->_buckets[idx]._item); 440 __CFBinaryHeapSetNumBucketsUsed(heap, 0); 441 __CFBinaryHeapSetCount(heap, 0); 442 } 443