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