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