CFBinaryHeap.c

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