CFBinaryHeap.c

   1 /*
   2  * Copyright (c) 2008 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 1998-2002, Apple, Inc. All rights reserved.
  25         Responsibility: Christopher Kane
  26 */
  27
  28 #include <CoreFoundation/CFBinaryHeap.h>
  29 #include "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         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, memory, 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     __CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapMutable);
 258     for (idx = 0; idx < numValues; idx++) {
 259         CFBinaryHeapAddValue(memory, values[idx]);
 260     }
 261     __CFBinaryHeapSetMutableVariety(memory, __CFBinaryHeapMutableVarietyFromFlags(flags));
 262     if (compareContext) memcpy(&memory->_context, compareContext, sizeof(CFBinaryHeapCompareContext));
 263     return memory;
 264 }
 265
 266 CFBinaryHeapRef CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) {
 267    return __CFBinaryHeapInit(allocator, kCFBinaryHeapMutable, capacity, NULL, 0, callBacks, compareContext);
 268 }
 269
 270 CFBinaryHeapRef CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap) {
 271    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 272     return __CFBinaryHeapInit(allocator, kCFBinaryHeapMutable, capacity, (const void **)heap->_buckets, __CFBinaryHeapCount(heap), &(heap->_callbacks), &(heap->_context));
 273 }
 274
 275 CFIndex CFBinaryHeapGetCount(CFBinaryHeapRef heap) {
 276     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 277     return __CFBinaryHeapCount(heap);
 278 }
 279
 280 CFIndex CFBinaryHeapGetCountOfValue(CFBinaryHeapRef heap, const void *value) {
 281     CFComparisonResult (*compare)(const void *, const void *, void *);
 282     CFIndex idx;
 283     CFIndex cnt = 0, length;
 284     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 285     compare = heap->_callbacks.compare;
 286     length = __CFBinaryHeapCount(heap);
 287     for (idx = 0; idx < length; idx++) {
 288         const void *item = heap->_buckets[idx]._item;
 289         if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
 290             cnt++;
 291         }
 292     }
 293     return cnt;
 294 }
 295
 296 Boolean CFBinaryHeapContainsValue(CFBinaryHeapRef heap, const void *value) {
 297     CFComparisonResult (*compare)(const void *, const void *, void *);
 298     CFIndex idx;
 299     CFIndex length;
 300     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 301     compare = heap->_callbacks.compare;
 302     length = __CFBinaryHeapCount(heap);
 303     for (idx = 0; idx < length; idx++) {
 304         const void *item = heap->_buckets[idx]._item;
 305         if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
 306             return true;
 307         }
 308     }
 309     return false;
 310 }
 311
 312 const void *CFBinaryHeapGetMinimum(CFBinaryHeapRef heap) {
 313     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 314     CFAssert1(0 < __CFBinaryHeapCount(heap), __kCFLogAssertion, "%s(): binary heap is empty", __PRETTY_FUNCTION__);
 315     return (0 < __CFBinaryHeapCount(heap)) ? heap->_buckets[0]._item : NULL;
 316 }
 317
 318 Boolean CFBinaryHeapGetMinimumIfPresent(CFBinaryHeapRef heap, const void **value) {
 319     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 320     if (0 == __CFBinaryHeapCount(heap)) return false;
 321     if (NULL != value) __CFObjCStrongAssign(heap->_buckets[0]._item, value);
 322     return true;
 323 }
 324
 325 void CFBinaryHeapGetValues(CFBinaryHeapRef heap, const void **values) {
 326     CFBinaryHeapRef heapCopy;
 327     CFIndex idx;
 328     CFIndex cnt;
 329     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 330     CFAssert1(NULL != values, __kCFLogAssertion, "%s(): pointer to values may not be NULL", __PRETTY_FUNCTION__);
 331     cnt = __CFBinaryHeapCount(heap);
 332     if (0 == cnt) return;
 333     if (CF_USING_COLLECTABLE_MEMORY) {
 334         // GC: speculatively issue a write-barrier on the copied to buffers (3743553).
 335         __CFObjCWriteBarrierRange(values, cnt * sizeof(void *));
 336     }
 337     heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
 338     idx = 0;
 339     while (0 < __CFBinaryHeapCount(heapCopy)) {
 340         const void *value = CFBinaryHeapGetMinimum(heapCopy);
 341         CFBinaryHeapRemoveMinimumValue(heapCopy);
 342         values[idx++] = value;
 343     }
 344     CFRelease(heapCopy);
 345 }
 346
 347 void CFBinaryHeapApplyFunction(CFBinaryHeapRef heap, CFBinaryHeapApplierFunction applier, void *context) {
 348     CFBinaryHeapRef heapCopy;
 349     CFIndex cnt;
 350     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 351     CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
 352     cnt = __CFBinaryHeapCount(heap);
 353     if (0 == cnt) return;
 354     heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
 355     while (0 < __CFBinaryHeapCount(heapCopy)) {
 356         const void *value = CFBinaryHeapGetMinimum(heapCopy);
 357         CFBinaryHeapRemoveMinimumValue(heapCopy);
 358         applier(value, context);
 359     }
 360     CFRelease(heapCopy);
 361 }
 362
 363 static void __CFBinaryHeapGrow(CFBinaryHeapRef heap, CFIndex numNewValues) {
 364     CFIndex oldCount = __CFBinaryHeapCount(heap);
 365     CFIndex capacity = __CFBinaryHeapRoundUpCapacity(oldCount + numNewValues);
 366     CFAllocatorRef allocator = CFGetAllocator(heap);
 367     __CFBinaryHeapSetCapacity(heap, capacity);
 368     __CFBinaryHeapSetNumBuckets(heap, __CFBinaryHeapNumBucketsForCapacity(capacity));
 369     void *buckets = _CFAllocatorReallocateGC(allocator, heap->_buckets, __CFBinaryHeapNumBuckets(heap) * sizeof(struct __CFBinaryHeapBucket), isStrongMemory_Heap(heap) ? __kCFAllocatorGCScannedMemory : 0);
 370     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap, heap->_buckets, buckets);
 371     if (__CFOASafe) __CFSetLastAllocationEventName(heap->_buckets, "CFBinaryHeap (store)");
 372     if (NULL == heap->_buckets) HALT;
 373 }
 374
 375 void CFBinaryHeapAddValue(CFBinaryHeapRef heap, const void *value) {
 376     CFIndex idx, pidx;
 377     CFIndex cnt;
 378     CFAllocatorRef allocator = CFGetAllocator(heap);
 379     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 380     switch (__CFBinaryHeapMutableVariety(heap)) {
 381     case kCFBinaryHeapMutable:
 382         if (__CFBinaryHeapNumBucketsUsed(heap) == __CFBinaryHeapCapacity(heap))
 383             __CFBinaryHeapGrow(heap, 1);
 384         break;
 385     }
 386     cnt = __CFBinaryHeapCount(heap);
 387     idx = cnt;
 388     __CFBinaryHeapSetNumBucketsUsed(heap, cnt + 1);
 389     __CFBinaryHeapSetCount(heap, cnt + 1);
 390     pidx = (idx - 1) >> 1;
 391     while (0 < idx) {
 392         void *item = heap->_buckets[pidx]._item;
 393         if (kCFCompareGreaterThan != heap->_callbacks.compare(item, value, heap->_context.info)) break;
 394         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, heap->_buckets[idx]._item, item);
 395         idx = pidx;
 396         pidx = (idx - 1) >> 1;
 397     }
 398     if (heap->_callbacks.retain) {
 399         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, heap->_buckets[idx]._item, (void *)heap->_callbacks.retain(allocator, (void *)value));
 400     } else {
 401         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, heap->_buckets[idx]._item, (void *)value);
 402     }
 403 }
 404
 405 void CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap) {
 406     void *val;
 407     CFIndex idx, cidx;
 408     CFIndex cnt;
 409     CFAllocatorRef allocator;
 410     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 411     cnt = __CFBinaryHeapCount(heap);
 412     if (0 == cnt) return;
 413     idx = 0;
 414     __CFBinaryHeapSetNumBucketsUsed(heap, cnt - 1);
 415     __CFBinaryHeapSetCount(heap, cnt - 1);
 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 (kCFCompareGreaterThan == heap->_callbacks.compare(item, item2, heap->_context.info)) {
 426                 cidx++;
 427                 item = item2;
 428             }
 429         }
 430         if (kCFCompareGreaterThan == heap->_callbacks.compare(item, val, heap->_context.info)) break;
 431         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, heap->_buckets[idx]._item, item);
 432         idx = cidx;
 433         cidx = (idx << 1) + 1;
 434     }
 435     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, 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