X-Git-Url: https://git.saurik.com/apple/cf.git/blobdiff_plain/47a9ab1f151d80a00a045f81937ddac81c51a463..bd5b749cf7786ae858ab372fc8f64179736c6515:/Collections.subproj/CFBinaryHeap.c?ds=sidebyside

diff --git a/Collections.subproj/CFBinaryHeap.c b/Collections.subproj/CFBinaryHeap.c
deleted file mode 100644
index 3f7e9eb..0000000
--- a/Collections.subproj/CFBinaryHeap.c
+++ /dev/null
@@ -1,486 +0,0 @@
-/*
- * Copyright (c) 2005 Apple Computer, Inc. All rights reserved.
- *
- * @APPLE_LICENSE_HEADER_START@
- * 
- * This file contains Original Code and/or Modifications of Original Code
- * as defined in and that are subject to the Apple Public Source License
- * Version 2.0 (the 'License'). You may not use this file except in
- * compliance with the License. Please obtain a copy of the License at
- * http://www.opensource.apple.com/apsl/ and read it before using this
- * file.
- * 
- * The Original Code and all software distributed under the License are
- * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
- * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
- * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
- * Please see the License for the specific language governing rights and
- * limitations under the License.
- * 
- * @APPLE_LICENSE_HEADER_END@
- */
-/*	CFBinaryHeap.c
-	Copyright 1998-2002, Apple, Inc. All rights reserved.
-	Responsibility: Christopher Kane
-*/
-
-#include <CoreFoundation/CFBinaryHeap.h>
-#include "CFUtilitiesPriv.h"
-#include "CFInternal.h"
-
-const CFBinaryHeapCallBacks kCFStringBinaryHeapCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, (CFComparisonResult (*)(const void *, const void *, void *))CFStringCompare};
-
-struct __CFBinaryHeapBucket {
-    void *_item;
-};
-
-CF_INLINE CFIndex __CFBinaryHeapRoundUpCapacity(CFIndex capacity) {
-    if (capacity < 4) return 4;
-    return (1 << (CFLog2(capacity) + 1));
-}
-
-CF_INLINE CFIndex __CFBinaryHeapNumBucketsForCapacity(CFIndex capacity) {
-    return capacity;
-}
-
-struct __CFBinaryHeap {
-    CFRuntimeBase _base;
-    CFIndex _count;	/* number of objects */
-    CFIndex _capacity;	/* maximum number of objects */
-    CFBinaryHeapCallBacks _callbacks;
-    CFBinaryHeapCompareContext _context;
-    struct __CFBinaryHeapBucket *_buckets;
-};
-
-CF_INLINE CFIndex __CFBinaryHeapCount(CFBinaryHeapRef heap) {
-    return heap->_count;
-}
-
-CF_INLINE void __CFBinaryHeapSetCount(CFBinaryHeapRef heap, CFIndex v) {
-    /* for a CFBinaryHeap, _bucketsUsed == _count */
-}
-
-CF_INLINE CFIndex __CFBinaryHeapCapacity(CFBinaryHeapRef heap) {
-    return heap->_capacity;
-}
-
-CF_INLINE void __CFBinaryHeapSetCapacity(CFBinaryHeapRef heap, CFIndex v) {
-    /* for a CFBinaryHeap, _bucketsNum == _capacity */
-}
-
-CF_INLINE CFIndex __CFBinaryHeapNumBucketsUsed(CFBinaryHeapRef heap) {
-    return heap->_count;
-}
-
-CF_INLINE void __CFBinaryHeapSetNumBucketsUsed(CFBinaryHeapRef heap, CFIndex v) {
-    heap->_count = v;
-}
-
-CF_INLINE CFIndex __CFBinaryHeapNumBuckets(CFBinaryHeapRef heap) {
-    return heap->_capacity;
-}
-
-CF_INLINE void __CFBinaryHeapSetNumBuckets(CFBinaryHeapRef heap, CFIndex v) {
-    heap->_capacity = v;
-}
-
-enum {      /* bits 1-0 */
-    kCFBinaryHeapImmutable = 0x0,       /* unchangable and fixed capacity; default */
-    kCFBinaryHeapMutable = 0x1,		/* changeable and variable capacity */
-    kCFBinaryHeapFixedMutable = 0x3	/* changeable and fixed capacity */
-};
-
-/* Bits 4-5 are used by GC */
-
-CF_INLINE bool isStrongMemory(CFTypeRef collection) {
-    return  ! __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_info, 4, 4);
-}
-
-CF_INLINE bool needsRestore(CFTypeRef collection) {
-    return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_info, 5, 5);
-}
-
-
-CF_INLINE UInt32 __CFBinaryHeapMutableVariety(const void *cf) {
-    return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_info, 3, 2);
-}
-
-CF_INLINE void __CFBinaryHeapSetMutableVariety(void *cf, UInt32 v) {
-    __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_info, 3, 2, v);
-}
-
-CF_INLINE UInt32 __CFBinaryHeapMutableVarietyFromFlags(UInt32 flags) {
-    return __CFBitfieldGetValue(flags, 1, 0);
-}
-
-static bool __CFBinaryHeapEqual(CFTypeRef cf1, CFTypeRef cf2) {
-    CFBinaryHeapRef heap1 = (CFBinaryHeapRef)cf1;
-    CFBinaryHeapRef heap2 = (CFBinaryHeapRef)cf2;
-    CFComparisonResult (*compare)(const void *, const void *, void *);
-    CFIndex idx;
-    CFIndex cnt;
-    const void **list1, **list2, *buffer[256];
-    cnt = __CFBinaryHeapCount(heap1);
-    if (cnt != __CFBinaryHeapCount(heap2)) return false;
-    compare = heap1->_callbacks.compare;
-    if (compare != heap2->_callbacks.compare) return false;
-    if (0 == cnt) return true;	/* after function comparison */
-    list1 = (cnt <= 128) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * cnt * sizeof(void *), 0); // GC OK
-    if (__CFOASafe && list1 != buffer) __CFSetLastAllocationEventName(list1, "CFBinaryHeap (temp)");
-    list2 = (cnt <= 128) ? buffer + 128 : list1 + cnt;
-    CFBinaryHeapGetValues(heap1, list1);
-    CFBinaryHeapGetValues(heap2, list2);
-    for (idx = 0; idx < cnt; idx++) {
-	const void *val1 = list1[idx];
-	const void *val2 = list2[idx];
-// CF: which context info should be passed in? both?
-// CF: if the context infos are not equal, should the heaps not be equal?
-	if (val1 != val2 && compare && !compare(val1, val2, heap1->_context.info)) return false;
-    }
-    if (list1 != buffer) CFAllocatorDeallocate(CFGetAllocator(heap1), list1); // GC OK
-    return true;
-}
-
-static UInt32 __CFBinaryHeapHash(CFTypeRef cf) {
-    CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
-    return __CFBinaryHeapCount(heap);
-}
-
-static CFStringRef __CFBinaryHeapCopyDescription(CFTypeRef cf) {
-    CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
-    CFMutableStringRef result;
-    CFIndex idx;
-    CFIndex cnt;
-    const void **list, *buffer[256];
-    cnt = __CFBinaryHeapCount(heap);
-    result = CFStringCreateMutable(CFGetAllocator(heap), 0);
-    CFStringAppendFormat(result, NULL, CFSTR("<CFBinaryHeap %p [%p]>{count = %u, capacity = %u, objects = (\n"), cf, CFGetAllocator(heap), cnt, __CFBinaryHeapCapacity(heap));
-    list = (cnt <= 128) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, cnt * sizeof(void *), 0); // GC OK
-    if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(list, "CFBinaryHeap (temp)");
-    CFBinaryHeapGetValues(heap, list);
-    for (idx = 0; idx < cnt; idx++) {
-	CFStringRef desc = NULL;
-	const void *item = list[idx];
-	if (NULL != heap->_callbacks.copyDescription) {
-	    desc = heap->_callbacks.copyDescription(item);
-	}
-	if (NULL != desc) {
-	    CFStringAppendFormat(result, NULL, CFSTR("\t%u : %s\n"), idx, desc);
-	    CFRelease(desc);
-	} else {
-	    CFStringAppendFormat(result, NULL, CFSTR("\t%u : <0x%x>\n"), idx, (UInt32)item);
-	}
-    }
-    CFStringAppend(result, CFSTR(")}"));
-    if (list != buffer) CFAllocatorDeallocate(CFGetAllocator(heap), list); // GC OK
-    return result;
-}
-
-static void __CFBinaryHeapDeallocate(CFTypeRef cf) {
-    CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
-    CFAllocatorRef allocator = CFGetAllocator(heap);
-    if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
-	if (heap->_callbacks.retain == NULL && heap->_callbacks.release == NULL)
-	    return; // GC: keep heap intact during finalization.
-    }
-// CF: should make the heap mutable here first, a la CFArrayDeallocate
-    CFBinaryHeapRemoveAllValues(heap);
-// CF: does not release the context info
-    if (__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable) {
-	_CFAllocatorDeallocateGC(allocator, heap->_buckets);
-    }
-}
-
-static CFTypeID __kCFBinaryHeapTypeID = _kCFRuntimeNotATypeID;
-
-static const CFRuntimeClass __CFBinaryHeapClass = {
-    _kCFRuntimeScannedObject,
-    "CFBinaryHeap",
-    NULL,	// init
-    NULL,	// copy
-    __CFBinaryHeapDeallocate,
-    (void *)__CFBinaryHeapEqual,
-    __CFBinaryHeapHash,
-    NULL,	// 
-    __CFBinaryHeapCopyDescription
-};
-
-__private_extern__ void __CFBinaryHeapInitialize(void) {
-    __kCFBinaryHeapTypeID = _CFRuntimeRegisterClass(&__CFBinaryHeapClass);
-}
-
-CFTypeID CFBinaryHeapGetTypeID(void) {
-    return __kCFBinaryHeapTypeID;
-}
-
-static CFBinaryHeapRef __CFBinaryHeapInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const void **values, CFIndex numValues, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) {
-// CF: does not copy the compareContext argument into the object
-    CFBinaryHeapRef memory;
-    CFIndex idx;
-    CFIndex size;
-
-    CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
-    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);
-    CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
-    size = sizeof(struct __CFBinaryHeap) - sizeof(CFRuntimeBase);
-    if (__CFBinaryHeapMutableVarietyFromFlags(flags) != kCFBinaryHeapMutable)
-	size += sizeof(struct __CFBinaryHeapBucket) * __CFBinaryHeapNumBucketsForCapacity(capacity);
-    CFBinaryHeapCallBacks nonRetainingCallbacks;
-    if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
-	if (!callBacks || (callBacks->retain == NULL && callBacks->release == NULL)) {
-	    __CFBitfieldSetValue(flags, 4, 4, 1); // setWeak
-	}
-	else {
-	    if (callBacks->retain == __CFTypeCollectionRetain && callBacks->release == __CFTypeCollectionRelease) {
-		nonRetainingCallbacks = *callBacks;
-		nonRetainingCallbacks.retain = NULL;
-		nonRetainingCallbacks.release = NULL;
-		callBacks = &nonRetainingCallbacks;
-		__CFBitfieldSetValue(flags, 5, 5, 1); // setNeedsRestore
-	    }
-	}
-    }
-
-    memory = (CFBinaryHeapRef)_CFRuntimeCreateInstance(allocator, __kCFBinaryHeapTypeID, size, NULL);
-    if (NULL == memory) {
-	return NULL;
-    }
-    switch (__CFBinaryHeapMutableVarietyFromFlags(flags)) {
-    case kCFBinaryHeapMutable:
-	__CFBinaryHeapSetCapacity(memory, __CFBinaryHeapRoundUpCapacity(1));
-	__CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(__CFBinaryHeapRoundUpCapacity(1)));
-	void *buckets = _CFAllocatorAllocateGC(allocator, __CFBinaryHeapNumBuckets(memory) * sizeof(struct __CFBinaryHeapBucket), isStrongMemory(memory) ? AUTO_MEMORY_SCANNED : AUTO_MEMORY_UNSCANNED);
-	CF_WRITE_BARRIER_BASE_ASSIGN(allocator, memory, memory->_buckets, buckets);
-	if (__CFOASafe) __CFSetLastAllocationEventName(memory->_buckets, "CFBinaryHeap (store)");
-	if (NULL == memory->_buckets) {
-	    CFRelease(memory);
-	    return NULL;
-	}
-	break;
-    case kCFBinaryHeapFixedMutable:
-    case kCFBinaryHeapImmutable:
-        if (!isStrongMemory(memory)) {  // if weak, don't scan
-            auto_zone_set_layout_type(__CFCollectableZone, memory, AUTO_OBJECT_UNSCANNED);
-        }
-	/* Don't round up capacity */
-	__CFBinaryHeapSetCapacity(memory, capacity);
-	__CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(capacity));
-	memory->_buckets = (struct __CFBinaryHeapBucket *)((int8_t *)memory + sizeof(struct __CFBinaryHeap));
-	break;
-    }
-    __CFBinaryHeapSetNumBucketsUsed(memory, 0);
-    __CFBinaryHeapSetCount(memory, 0);
-    if (NULL != callBacks) {
-	memory->_callbacks.retain = callBacks->retain;
-	memory->_callbacks.release = callBacks->release;
-	memory->_callbacks.copyDescription = callBacks->copyDescription;
-	memory->_callbacks.compare = callBacks->compare;
-    } else {
-	memory->_callbacks.retain = 0;
-	memory->_callbacks.release = 0;
-	memory->_callbacks.copyDescription = 0;
-	memory->_callbacks.compare = 0;
-    }
-    if (__CFBinaryHeapMutableVarietyFromFlags(flags) != kCFBinaryHeapMutable) {
-        __CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapFixedMutable);
-    } else {
-        __CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapMutable);
-    }
-    for (idx = 0; idx < numValues; idx++) {
-	CFBinaryHeapAddValue(memory, values[idx]);
-    }
-    __CFBinaryHeapSetMutableVariety(memory, __CFBinaryHeapMutableVarietyFromFlags(flags));
-    return memory;
-}
-
-CFBinaryHeapRef CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) {
-   return __CFBinaryHeapInit(allocator, (0 == capacity) ? kCFBinaryHeapMutable : kCFBinaryHeapFixedMutable, capacity, NULL, 0, callBacks, compareContext);
-}
-
-CFBinaryHeapRef CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap) {
-   __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    return __CFBinaryHeapInit(allocator, (0 == capacity) ? kCFBinaryHeapMutable : kCFBinaryHeapFixedMutable, capacity, (const void **)heap->_buckets, __CFBinaryHeapCount(heap), &(heap->_callbacks), &(heap->_context));
-}
-
-CFIndex CFBinaryHeapGetCount(CFBinaryHeapRef heap) {
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    return __CFBinaryHeapCount(heap);
-}
-
-CFIndex CFBinaryHeapGetCountOfValue(CFBinaryHeapRef heap, const void *value) {
-    CFComparisonResult (*compare)(const void *, const void *, void *);
-    CFIndex idx;
-    CFIndex cnt = 0, length;
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    compare = heap->_callbacks.compare;
-    length = __CFBinaryHeapCount(heap);
-    for (idx = 0; idx < length; idx++) {
-	const void *item = heap->_buckets[idx]._item;
-	if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
-	    cnt++;
-	}
-    }
-    return cnt;
-}
-
-Boolean CFBinaryHeapContainsValue(CFBinaryHeapRef heap, const void *value) {
-    CFComparisonResult (*compare)(const void *, const void *, void *);
-    CFIndex idx;
-    CFIndex length;
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    compare = heap->_callbacks.compare;
-    length = __CFBinaryHeapCount(heap);
-    for (idx = 0; idx < length; idx++) {
-	const void *item = heap->_buckets[idx]._item;
-	if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
-	    return true;
-	}
-    }
-    return false;
-}
-
-const void *CFBinaryHeapGetMinimum(CFBinaryHeapRef heap) {
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    CFAssert1(0 < __CFBinaryHeapCount(heap), __kCFLogAssertion, "%s(): binary heap is empty", __PRETTY_FUNCTION__);
-    return (0 < __CFBinaryHeapCount(heap)) ? heap->_buckets[0]._item : NULL;
-}
-
-Boolean CFBinaryHeapGetMinimumIfPresent(CFBinaryHeapRef heap, const void **value) {
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    if (0 == __CFBinaryHeapCount(heap)) return false;
-    if (NULL != value) __CFObjCStrongAssign(heap->_buckets[0]._item, value);
-    return true;
-}
-
-void CFBinaryHeapGetValues(CFBinaryHeapRef heap, const void **values) {
-    CFBinaryHeapRef heapCopy;
-    CFIndex idx;
-    CFIndex cnt;
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    CFAssert1(NULL != values, __kCFLogAssertion, "%s(): pointer to values may not be NULL", __PRETTY_FUNCTION__);
-    cnt = __CFBinaryHeapCount(heap);
-    if (0 == cnt) return;
-    if (CF_USING_COLLECTABLE_MEMORY) {
-	// GC: speculatively issue a write-barrier on the copied to buffers (3743553).
-	__CFObjCWriteBarrierRange(values, cnt * sizeof(void *));
-    }
-    heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
-    idx = 0;
-    while (0 < __CFBinaryHeapCount(heapCopy)) {
-	const void *value = CFBinaryHeapGetMinimum(heapCopy);
-	CFBinaryHeapRemoveMinimumValue(heapCopy);
-	values[idx++] = value;
-    }
-    CFRelease(heapCopy);
-}
-
-void CFBinaryHeapApplyFunction(CFBinaryHeapRef heap, CFBinaryHeapApplierFunction applier, void *context) {
-    CFBinaryHeapRef heapCopy;
-    CFIndex cnt;
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
-    cnt = __CFBinaryHeapCount(heap);
-    if (0 == cnt) return;
-    heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
-    while (0 < __CFBinaryHeapCount(heapCopy)) {
-	const void *value = CFBinaryHeapGetMinimum(heapCopy);
-	CFBinaryHeapRemoveMinimumValue(heapCopy);
-	applier(value, context);
-    }
-    CFRelease(heapCopy);
-}
-
-static void __CFBinaryHeapGrow(CFBinaryHeapRef heap, CFIndex numNewValues) {
-    CFIndex oldCount = __CFBinaryHeapCount(heap);
-    CFIndex capacity = __CFBinaryHeapRoundUpCapacity(oldCount + numNewValues);
-    CFAllocatorRef allocator = CFGetAllocator(heap);
-    __CFBinaryHeapSetCapacity(heap, capacity);
-    __CFBinaryHeapSetNumBuckets(heap, __CFBinaryHeapNumBucketsForCapacity(capacity));
-    void *buckets = _CFAllocatorReallocateGC(allocator, heap->_buckets, __CFBinaryHeapNumBuckets(heap) * sizeof(struct __CFBinaryHeapBucket), isStrongMemory(heap) ? AUTO_MEMORY_SCANNED : AUTO_MEMORY_UNSCANNED);
-    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap, heap->_buckets, buckets);
-    if (__CFOASafe) __CFSetLastAllocationEventName(heap->_buckets, "CFBinaryHeap (store)");
-    if (NULL == heap->_buckets) HALT;
-}
-
-void CFBinaryHeapAddValue(CFBinaryHeapRef heap, const void *value) {
-    CFIndex idx, pidx;
-    CFIndex cnt;
-    CFAllocatorRef allocator = CFGetAllocator(heap);
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable || __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
-    switch (__CFBinaryHeapMutableVariety(heap)) {
-    case kCFBinaryHeapMutable:
-	if (__CFBinaryHeapNumBucketsUsed(heap) == __CFBinaryHeapCapacity(heap))
-	    __CFBinaryHeapGrow(heap, 1);
-	break;
-    case kCFBinaryHeapFixedMutable:
-	CFAssert1(__CFBinaryHeapCount(heap) < __CFBinaryHeapCapacity(heap), __kCFLogAssertion, "%s(): fixed-capacity binary heap is full", __PRETTY_FUNCTION__);
-	break;
-    }
-    cnt = __CFBinaryHeapCount(heap);
-    idx = cnt;
-    __CFBinaryHeapSetNumBucketsUsed(heap, cnt + 1);
-    __CFBinaryHeapSetCount(heap, cnt + 1);
-    pidx = (idx - 1) >> 1;
-    while (0 < idx) {
-	void *item = heap->_buckets[pidx]._item;
-	if (kCFCompareGreaterThan != heap->_callbacks.compare(item, value, heap->_context.info)) break;
-	CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, heap->_buckets[idx]._item, item);
-	idx = pidx;
-	pidx = (idx - 1) >> 1;
-    }
-    if (heap->_callbacks.retain) {
-	CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, heap->_buckets[idx]._item, (void *)heap->_callbacks.retain(allocator, (void *)value));
-    } else {
-	CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, heap->_buckets[idx]._item, (void *)value);
-    }
-}
-
-void CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap) {
-    void *val;
-    CFIndex idx, cidx;
-    CFIndex cnt;
-    CFAllocatorRef allocator;
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable || __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
-    cnt = __CFBinaryHeapCount(heap);
-    if (0 == cnt) return;
-    idx = 0;
-    __CFBinaryHeapSetNumBucketsUsed(heap, cnt - 1);
-    __CFBinaryHeapSetCount(heap, cnt - 1);
-    allocator = CFGetAllocator(heap);
-    if (heap->_callbacks.release)
-	heap->_callbacks.release(allocator, heap->_buckets[idx]._item);
-    val = heap->_buckets[cnt - 1]._item;
-    cidx = (idx << 1) + 1;
-    while (cidx < __CFBinaryHeapCount(heap)) {
-	void *item = heap->_buckets[cidx]._item;
-	if (cidx + 1 < __CFBinaryHeapCount(heap)) {
-	    void *item2 = heap->_buckets[cidx + 1]._item;
-	    if (kCFCompareGreaterThan == heap->_callbacks.compare(item, item2, heap->_context.info)) {
-		cidx++;
-		item = item2;
-	    }
-	}
-	if (kCFCompareGreaterThan == heap->_callbacks.compare(item, val, heap->_context.info)) break;
-	CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, heap->_buckets[idx]._item, item);
-	idx = cidx;
-	cidx = (idx << 1) + 1;
-    }
-    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, heap->_buckets, heap->_buckets[idx]._item, val);
-}
-
-void CFBinaryHeapRemoveAllValues(CFBinaryHeapRef heap) {
-    CFIndex idx;
-    CFIndex cnt;
-    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
-    CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable || __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
-    cnt = __CFBinaryHeapCount(heap);
-    if (heap->_callbacks.release)
-	for (idx = 0; idx < cnt; idx++)
-	    heap->_callbacks.release(CFGetAllocator(heap), heap->_buckets[idx]._item);
-    __CFBinaryHeapSetNumBucketsUsed(heap, 0);
-    __CFBinaryHeapSetCount(heap, 0);
-}
-