CFBinaryHeap.c

   1 /*
   2  * Copyright (c) 2012 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-2011, 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 bool isWeakMemory_Heap(CFTypeRef collection) {
 100     return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_cfinfo[CF_INFO_BITS], 4, 4) != 0;
 101 }
 102
 103 CF_INLINE UInt32 __CFBinaryHeapMutableVariety(const void *cf) {
 104     return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2);
 105 }
 106
 107 CF_INLINE void __CFBinaryHeapSetMutableVariety(void *cf, UInt32 v) {
 108     __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2, v);
 109 }
 110
 111 CF_INLINE UInt32 __CFBinaryHeapMutableVarietyFromFlags(UInt32 flags) {
 112     return __CFBitfieldGetValue(flags, 1, 0);
 113 }
 114
 115 static 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
 146 static CFHashCode __CFBinaryHeapHash(CFTypeRef cf) {
 147     CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
 148     return __CFBinaryHeapCount(heap);
 149 }
 150
 151 static 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 = %u, capacity = %u, objects = (\n"), cf, CFGetAllocator(heap), cnt, __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%u : %@\n"), idx, desc);
 171             CFRelease(desc);
 172         } else {
 173             CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, item);
 174         }
 175     }
 176     CFStringAppend(result, CFSTR(")}"));
 177     if (list != buffer) CFAllocatorDeallocate(CFGetAllocator(heap), list); // GC OK
 178     return result;
 179 }
 180
 181 static 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
 196 static CFTypeID __kCFBinaryHeapTypeID = _kCFRuntimeNotATypeID;
 197
 198 static 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
 210 __private_extern__ void __CFBinaryHeapInitialize(void) {
 211     __kCFBinaryHeapTypeID = _CFRuntimeRegisterClass(&__CFBinaryHeapClass);
 212 }
 213
 214 CFTypeID CFBinaryHeapGetTypeID(void) {
 215     return __kCFBinaryHeapTypeID;
 216 }
 217
 218 static 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
 268 CFBinaryHeapRef CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) {
 269    return __CFBinaryHeapInit(allocator, kCFBinaryHeapMutable, capacity, NULL, 0, callBacks, compareContext);
 270 }
 271
 272 CFBinaryHeapRef 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
 277 CFIndex CFBinaryHeapGetCount(CFBinaryHeapRef heap) {
 278     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 279     return __CFBinaryHeapCount(heap);
 280 }
 281
 282 CFIndex 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
 298 Boolean 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
 314 const 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
 320 Boolean 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
 327 void 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
 345 void 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
 361 static 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
 373 void 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
 404 void 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
 438 void 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