Collections.subproj/CFBinaryHeap.c

   1 /*
   2  * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /*      CFBinaryHeap.c
  26         Copyright 1998-2002, Apple, Inc. All rights reserved.
  27         Responsibility: Christopher Kane
  28 */
  29
  30 #include <CoreFoundation/CFBinaryHeap.h>
  31 #include "CFUtilities.h"
  32 #include "CFInternal.h"
  33
  34 const CFBinaryHeapCallBacks kCFStringBinaryHeapCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, (CFComparisonResult (*)(const void *, const void *, void *))CFStringCompare};
  35
  36 struct __CFBinaryHeapBucket {
  37     void *_item;
  38 };
  39
  40 CF_INLINE CFIndex __CFBinaryHeapRoundUpCapacity(CFIndex capacity) {
  41     if (capacity < 4) return 4;
  42     return (1 << (CFLog2(capacity) + 1));
  43 }
  44
  45 CF_INLINE CFIndex __CFBinaryHeapNumBucketsForCapacity(CFIndex capacity) {
  46     return capacity;
  47 }
  48
  49 struct __CFBinaryHeap {
  50     CFRuntimeBase _base;
  51     CFIndex _count;     /* number of objects */
  52     CFIndex _capacity;  /* maximum number of objects */
  53     CFBinaryHeapCallBacks _callbacks;
  54     CFBinaryHeapCompareContext _context;
  55     struct __CFBinaryHeapBucket *_buckets;
  56 };
  57
  58 CF_INLINE CFIndex __CFBinaryHeapCount(CFBinaryHeapRef heap) {
  59     return heap->_count;
  60 }
  61
  62 CF_INLINE void __CFBinaryHeapSetCount(CFBinaryHeapRef heap, CFIndex v) {
  63     /* for a CFBinaryHeap, _bucketsUsed == _count */
  64 }
  65
  66 CF_INLINE CFIndex __CFBinaryHeapCapacity(CFBinaryHeapRef heap) {
  67     return heap->_capacity;
  68 }
  69
  70 CF_INLINE void __CFBinaryHeapSetCapacity(CFBinaryHeapRef heap, CFIndex v) {
  71     /* for a CFBinaryHeap, _bucketsNum == _capacity */
  72 }
  73
  74 CF_INLINE CFIndex __CFBinaryHeapNumBucketsUsed(CFBinaryHeapRef heap) {
  75     return heap->_count;
  76 }
  77
  78 CF_INLINE void __CFBinaryHeapSetNumBucketsUsed(CFBinaryHeapRef heap, CFIndex v) {
  79     heap->_count = v;
  80 }
  81
  82 CF_INLINE CFIndex __CFBinaryHeapNumBuckets(CFBinaryHeapRef heap) {
  83     return heap->_capacity;
  84 }
  85
  86 CF_INLINE void __CFBinaryHeapSetNumBuckets(CFBinaryHeapRef heap, CFIndex v) {
  87     heap->_capacity = v;
  88 }
  89
  90 enum {
  91     kCFBinaryHeapImmutable = 0x0,               /* unchangable and fixed capacity; default */
  92     kCFBinaryHeapMutable = 0x1,         /* changeable and variable capacity */
  93     kCFBinaryHeapFixedMutable = 0x3     /* changeable and fixed capacity */
  94 };
  95
  96 CF_INLINE UInt32 __CFBinaryHeapMutableVariety(const void *cf) {
  97     return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_info, 3, 2);
  98 }
  99
 100 CF_INLINE void __CFBinaryHeapSetMutableVariety(void *cf, UInt32 v) {
 101     __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_info, 3, 2, v);
 102 }
 103
 104 CF_INLINE UInt32 __CFBinaryHeapMutableVarietyFromFlags(UInt32 flags) {
 105     return __CFBitfieldGetValue(flags, 1, 0);
 106 }
 107
 108 static bool __CFBinaryHeapEqual(CFTypeRef cf1, CFTypeRef cf2) {
 109     CFBinaryHeapRef heap1 = (CFBinaryHeapRef)cf1;
 110     CFBinaryHeapRef heap2 = (CFBinaryHeapRef)cf2;
 111     CFComparisonResult (*compare)(const void *, const void *, void *);
 112     CFIndex idx;
 113     CFIndex cnt;
 114     const void **list1, **list2, *buffer[256];
 115     cnt = __CFBinaryHeapCount(heap1);
 116     if (cnt != __CFBinaryHeapCount(heap2)) return false;
 117     compare = heap1->_callbacks.compare;
 118     if (compare != heap2->_callbacks.compare) return false;
 119     if (0 == cnt) return true;  /* after function comparison */
 120     list1 = (cnt <= 128) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * cnt * sizeof(void *), 0);
 121     if (__CFOASafe && list1 != buffer) __CFSetLastAllocationEventName(list1, "CFBinaryHeap (temp)");
 122     list2 = (cnt <= 128) ? buffer + 128 : list1 + cnt;
 123     CFBinaryHeapGetValues(heap1, list1);
 124     CFBinaryHeapGetValues(heap2, list2);
 125     for (idx = 0; idx < cnt; idx++) {
 126         const void *val1 = list1[idx];
 127         const void *val2 = list2[idx];
 128 // CF: which context info should be passed in? both?
 129 // CF: if the context infos are not equal, should the heaps not be equal?
 130         if (val1 != val2 && compare && !compare(val1, val2, heap1->_context.info)) return false;
 131     }
 132     if (list1 != buffer) CFAllocatorDeallocate(CFGetAllocator(heap1), list1);
 133     return true;
 134 }
 135
 136 static UInt32 __CFBinaryHeapHash(CFTypeRef cf) {
 137     CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
 138     return __CFBinaryHeapCount(heap);
 139 }
 140
 141 static CFStringRef __CFBinaryHeapCopyDescription(CFTypeRef cf) {
 142     CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
 143     CFMutableStringRef result;
 144     CFIndex idx;
 145     CFIndex cnt;
 146     const void **list, *buffer[256];
 147     cnt = __CFBinaryHeapCount(heap);
 148     result = CFStringCreateMutable(CFGetAllocator(heap), 0);
 149     CFStringAppendFormat(result, NULL, CFSTR("<CFBinaryHeap %p [%p]>{count = %u, capacity = %u, objects = (\n"), cf, CFGetAllocator(heap), cnt, __CFBinaryHeapCapacity(heap));
 150     list = (cnt <= 128) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, cnt * sizeof(void *), 0);
 151     if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(list, "CFBinaryHeap (temp)");
 152     CFBinaryHeapGetValues(heap, list);
 153     for (idx = 0; idx < cnt; idx++) {
 154         CFStringRef desc = NULL;
 155         const void *item = list[idx];
 156         if (NULL != heap->_callbacks.copyDescription) {
 157             desc = heap->_callbacks.copyDescription(item);
 158         }
 159         if (NULL != desc) {
 160             CFStringAppendFormat(result, NULL, CFSTR("\t%u : %s\n"), idx, desc);
 161             CFRelease(desc);
 162         } else {
 163             CFStringAppendFormat(result, NULL, CFSTR("\t%u : <0x%x>\n"), idx, (UInt32)item);
 164         }
 165     }
 166     CFStringAppend(result, CFSTR(")}"));
 167     if (list != buffer) CFAllocatorDeallocate(CFGetAllocator(heap), list);
 168     return result;
 169 }
 170
 171 static void __CFBinaryHeapDeallocate(CFTypeRef cf) {
 172     CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
 173     CFAllocatorRef allocator = CFGetAllocator(heap);
 174 // CF: should make the heap mutable here first, a la CFArrayDeallocate
 175     CFBinaryHeapRemoveAllValues(heap);
 176 // CF: does not release the context info
 177     if (__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable) {
 178         CFAllocatorDeallocate(allocator, heap->_buckets);
 179     }
 180 }
 181
 182 static CFTypeID __kCFBinaryHeapTypeID = _kCFRuntimeNotATypeID;
 183
 184 static const CFRuntimeClass __CFBinaryHeapClass = {
 185     0,
 186     "CFBinaryHeap",
 187     NULL,       // init
 188     NULL,       // copy
 189     __CFBinaryHeapDeallocate,
 190     (void *)__CFBinaryHeapEqual,
 191     __CFBinaryHeapHash,
 192     NULL,       //
 193     __CFBinaryHeapCopyDescription
 194 };
 195
 196 __private_extern__ void __CFBinaryHeapInitialize(void) {
 197     __kCFBinaryHeapTypeID = _CFRuntimeRegisterClass(&__CFBinaryHeapClass);
 198 }
 199
 200 CFTypeID CFBinaryHeapGetTypeID(void) {
 201     return __kCFBinaryHeapTypeID;
 202 }
 203
 204 static CFBinaryHeapRef __CFBinaryHeapInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const void **values, CFIndex numValues, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) {
 205 // CF: does not copy the compareContext argument into the object
 206     CFBinaryHeapRef memory;
 207     CFIndex idx;
 208     CFIndex size;
 209
 210     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 211     CFAssert3(kCFBinaryHeapFixedMutable != __CFBinaryHeapMutableVarietyFromFlags(flags) || numValues <= capacity, __kCFLogAssertion, "%s(): for fixed-mutable type, capacity (%d) must be greater than or equal to number of initial elements (%d)", __PRETTY_FUNCTION__, capacity, numValues);
 212     CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
 213     size = sizeof(struct __CFBinaryHeap) - sizeof(CFRuntimeBase);
 214     if (__CFBinaryHeapMutableVarietyFromFlags(flags) != kCFBinaryHeapMutable)
 215         size += sizeof(struct __CFBinaryHeapBucket) * __CFBinaryHeapNumBucketsForCapacity(capacity);
 216     memory = (CFBinaryHeapRef)_CFRuntimeCreateInstance(allocator, __kCFBinaryHeapTypeID, size, NULL);
 217     if (NULL == memory) {
 218         return NULL;
 219     }
 220     switch (__CFBinaryHeapMutableVarietyFromFlags(flags)) {
 221     case kCFBinaryHeapMutable:
 222         __CFBinaryHeapSetCapacity(memory, __CFBinaryHeapRoundUpCapacity(1));
 223         __CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(__CFBinaryHeapRoundUpCapacity(1)));
 224         memory->_buckets = CFAllocatorAllocate(allocator, __CFBinaryHeapNumBuckets(memory) * sizeof(struct __CFBinaryHeapBucket), 0);
 225         if (__CFOASafe) __CFSetLastAllocationEventName(memory->_buckets, "CFBinaryHeap (store)");
 226         if (NULL == memory->_buckets) {
 227             CFRelease(memory);
 228             return NULL;
 229         }
 230         break;
 231     case kCFBinaryHeapFixedMutable:
 232     case kCFBinaryHeapImmutable:
 233         /* Don't round up capacity */
 234         __CFBinaryHeapSetCapacity(memory, capacity);
 235         __CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(capacity));
 236         memory->_buckets = (struct __CFBinaryHeapBucket *)((int8_t *)memory + sizeof(struct __CFBinaryHeap));
 237         break;
 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 (__CFBinaryHeapMutableVarietyFromFlags(flags) != kCFBinaryHeapMutable) {
 253         __CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapFixedMutable);
 254     } else {
 255         __CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapMutable);
 256     }
 257     for (idx = 0; idx < numValues; idx++) {
 258         CFBinaryHeapAddValue(memory, values[idx]);
 259     }
 260     __CFBinaryHeapSetMutableVariety(memory, __CFBinaryHeapMutableVarietyFromFlags(flags));
 261     return memory;
 262 }
 263
 264 CFBinaryHeapRef CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) {
 265    return __CFBinaryHeapInit(allocator, (0 == capacity) ? kCFBinaryHeapMutable : kCFBinaryHeapFixedMutable, capacity, NULL, 0, callBacks, compareContext);
 266 }
 267
 268 CFBinaryHeapRef CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap) {
 269    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 270     return __CFBinaryHeapInit(allocator, (0 == capacity) ? kCFBinaryHeapMutable : kCFBinaryHeapFixedMutable, capacity, (const void **)heap->_buckets, __CFBinaryHeapCount(heap), &(heap->_callbacks), &(heap->_context));
 271 }
 272
 273 CFIndex CFBinaryHeapGetCount(CFBinaryHeapRef heap) {
 274     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 275     return __CFBinaryHeapCount(heap);
 276 }
 277
 278 CFIndex CFBinaryHeapGetCountOfValue(CFBinaryHeapRef heap, const void *value) {
 279     CFComparisonResult (*compare)(const void *, const void *, void *);
 280     CFIndex idx;
 281     CFIndex cnt = 0, length;
 282     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 283     compare = heap->_callbacks.compare;
 284     length = __CFBinaryHeapCount(heap);
 285     for (idx = 0; idx < length; idx++) {
 286         const void *item = heap->_buckets[idx]._item;
 287         if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
 288             cnt++;
 289         }
 290     }
 291     return cnt;
 292 }
 293
 294 Boolean CFBinaryHeapContainsValue(CFBinaryHeapRef heap, const void *value) {
 295     CFComparisonResult (*compare)(const void *, const void *, void *);
 296     CFIndex idx;
 297     CFIndex length;
 298     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 299     compare = heap->_callbacks.compare;
 300     length = __CFBinaryHeapCount(heap);
 301     for (idx = 0; idx < length; idx++) {
 302         const void *item = heap->_buckets[idx]._item;
 303         if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
 304             return true;
 305         }
 306     }
 307     return false;
 308 }
 309
 310 const void *CFBinaryHeapGetMinimum(CFBinaryHeapRef heap) {
 311     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 312     CFAssert1(0 < __CFBinaryHeapCount(heap), __kCFLogAssertion, "%s(): binary heap is empty", __PRETTY_FUNCTION__);
 313     return (0 < __CFBinaryHeapCount(heap)) ? heap->_buckets[0]._item : NULL;
 314 }
 315
 316 Boolean CFBinaryHeapGetMinimumIfPresent(CFBinaryHeapRef heap, const void **value) {
 317     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 318     if (0 == __CFBinaryHeapCount(heap)) return false;
 319     if (NULL != value) *value = heap->_buckets[0]._item;
 320     return true;
 321 }
 322
 323 void CFBinaryHeapGetValues(CFBinaryHeapRef heap, const void **values) {
 324     CFBinaryHeapRef heapCopy;
 325     CFIndex idx;
 326     CFIndex cnt;
 327     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 328     CFAssert1(NULL != values, __kCFLogAssertion, "%s(): pointer to values may not be NULL", __PRETTY_FUNCTION__);
 329     cnt = __CFBinaryHeapCount(heap);
 330     if (0 == cnt) return;
 331     heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
 332     idx = 0;
 333     while (0 < __CFBinaryHeapCount(heapCopy)) {
 334         const void *value = CFBinaryHeapGetMinimum(heapCopy);
 335         CFBinaryHeapRemoveMinimumValue(heapCopy);
 336         values[idx++] = value;
 337     }
 338     CFRelease(heapCopy);
 339 }
 340
 341 void CFBinaryHeapApplyFunction(CFBinaryHeapRef heap, CFBinaryHeapApplierFunction applier, void *context) {
 342     CFBinaryHeapRef heapCopy;
 343     CFIndex cnt;
 344     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 345     CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
 346     cnt = __CFBinaryHeapCount(heap);
 347     if (0 == cnt) return;
 348     heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
 349     while (0 < __CFBinaryHeapCount(heapCopy)) {
 350         const void *value = CFBinaryHeapGetMinimum(heapCopy);
 351         CFBinaryHeapRemoveMinimumValue(heapCopy);
 352         applier(value, context);
 353     }
 354     CFRelease(heapCopy);
 355 }
 356
 357 static void __CFBinaryHeapGrow(CFBinaryHeapRef heap, CFIndex numNewValues) {
 358     CFIndex oldCount = __CFBinaryHeapCount(heap);
 359     CFIndex capacity = __CFBinaryHeapRoundUpCapacity(oldCount + numNewValues);
 360     __CFBinaryHeapSetCapacity(heap, capacity);
 361     __CFBinaryHeapSetNumBuckets(heap, __CFBinaryHeapNumBucketsForCapacity(capacity));
 362     heap->_buckets = CFAllocatorReallocate(CFGetAllocator(heap), heap->_buckets, __CFBinaryHeapNumBuckets(heap) * sizeof(struct __CFBinaryHeapBucket), 0);
 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     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 371     CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable || __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
 372     switch (__CFBinaryHeapMutableVariety(heap)) {
 373     case kCFBinaryHeapMutable:
 374         if (__CFBinaryHeapNumBucketsUsed(heap) == __CFBinaryHeapCapacity(heap))
 375             __CFBinaryHeapGrow(heap, 1);
 376         break;
 377     case kCFBinaryHeapFixedMutable:
 378         CFAssert1(__CFBinaryHeapCount(heap) < __CFBinaryHeapCapacity(heap), __kCFLogAssertion, "%s(): fixed-capacity binary heap is full", __PRETTY_FUNCTION__);
 379         break;
 380     }
 381     cnt = __CFBinaryHeapCount(heap);
 382     idx = cnt;
 383     __CFBinaryHeapSetNumBucketsUsed(heap, cnt + 1);
 384     __CFBinaryHeapSetCount(heap, cnt + 1);
 385     pidx = (idx - 1) >> 1;
 386     while (0 < idx) {
 387         void *item = heap->_buckets[pidx]._item;
 388         if (kCFCompareGreaterThan != heap->_callbacks.compare(item, value, heap->_context.info)) break;
 389         heap->_buckets[idx]._item = item;
 390         idx = pidx;
 391         pidx = (idx - 1) >> 1;
 392     }
 393     if (heap->_callbacks.retain) {
 394         heap->_buckets[idx]._item = (void *)heap->_callbacks.retain(CFGetAllocator(heap), (void *)value);
 395     } else {
 396         heap->_buckets[idx]._item = (void *)value;
 397     }
 398 }
 399
 400 void CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap) {
 401     void *val;
 402     CFIndex idx, cidx;
 403     CFIndex cnt;
 404     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 405     CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable || __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
 406     cnt = __CFBinaryHeapCount(heap);
 407     if (0 == cnt) return;
 408     idx = 0;
 409     __CFBinaryHeapSetNumBucketsUsed(heap, cnt - 1);
 410     __CFBinaryHeapSetCount(heap, cnt - 1);
 411     if (heap->_callbacks.release)
 412         heap->_callbacks.release(CFGetAllocator(heap), 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 (kCFCompareGreaterThan == heap->_callbacks.compare(item, item2, heap->_context.info)) {
 420                 cidx++;
 421                 item = item2;
 422             }
 423         }
 424         if (kCFCompareGreaterThan == heap->_callbacks.compare(item, val, heap->_context.info)) break;
 425         heap->_buckets[idx]._item = item;
 426         idx = cidx;
 427         cidx = (idx << 1) + 1;
 428     }
 429     heap->_buckets[idx]._item = val;
 430 }
 431
 432 void CFBinaryHeapRemoveAllValues(CFBinaryHeapRef heap) {
 433     CFIndex idx;
 434     CFIndex cnt;
 435     __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
 436     CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable || __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
 437     cnt = __CFBinaryHeapCount(heap);
 438     if (heap->_callbacks.release)
 439         for (idx = 0; idx < cnt; idx++)
 440             heap->_callbacks.release(CFGetAllocator(heap), heap->_buckets[idx]._item);
 441     __CFBinaryHeapSetNumBucketsUsed(heap, 0);
 442     __CFBinaryHeapSetCount(heap, 0);
 443 }
 444