[apple/cf.git] / CFBinaryHeap.c

/*
 * Copyright (c) 2011 Apple 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 (c) 1998-2011, Apple Inc. All rights reserved.
	Responsibility: Christopher Kane
*/

#include <CoreFoundation/CFBinaryHeap.h>
#include <CoreFoundation/CFPriv.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 << flsl(capacity));
}

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 */
    kCFBinaryHeapMutable = 0x1,		/* changeable and variable capacity */
};

/* Bits 4-5 are used by GC */

CF_INLINE bool isStrongMemory_Heap(CFTypeRef collection) {
    return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_cfinfo[CF_INFO_BITS], 4, 4) == 0;
}

CF_INLINE bool isWeakMemory_Heap(CFTypeRef collection) {
    return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_cfinfo[CF_INFO_BITS], 4, 4) != 0;
}

CF_INLINE UInt32 __CFBinaryHeapMutableVariety(const void *cf) {
    return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2);
}

CF_INLINE void __CFBinaryHeapSetMutableVariety(void *cf, UInt32 v) {
    __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2, v);
}

CF_INLINE UInt32 __CFBinaryHeapMutableVarietyFromFlags(UInt32 flags) {
    return __CFBitfieldGetValue(flags, 1, 0);
}

static Boolean __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) ? (const void **)buffer : (const void **)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) { 
            if (NULL == compare) return false;
            if (!compare(val1, val2, heap1->_context.info)) return false;
        }
    }
    if (list1 != buffer) CFAllocatorDeallocate(CFGetAllocator(heap1), list1); // GC OK
    return true;
}

static CFHashCode __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) ? (const void **)buffer : (const void **)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 : %@\n"), idx, desc);
	    CFRelease(desc);
	} else {
	    CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, 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,
    __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) {
    CFBinaryHeapRef memory;
    CFIndex idx;
    CFIndex size;

    CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
    CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
    size = sizeof(struct __CFBinaryHeap) - sizeof(CFRuntimeBase);
    if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
	if (!callBacks || (callBacks->retain == NULL && callBacks->release == NULL)) {
	    __CFBitfieldSetValue(flags, 4, 4, 1); // setWeak
	}
    }

    memory = (CFBinaryHeapRef)_CFRuntimeCreateInstance(allocator, __kCFBinaryHeapTypeID, size, NULL);
    if (NULL == memory) {
	return NULL;
    }
	__CFBinaryHeapSetCapacity(memory, __CFBinaryHeapRoundUpCapacity(1));
	__CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(__CFBinaryHeapRoundUpCapacity(1)));
	void *buckets = _CFAllocatorAllocateGC(allocator, __CFBinaryHeapNumBuckets(memory) * sizeof(struct __CFBinaryHeapBucket), isStrongMemory_Heap(memory) ? __kCFAllocatorGCScannedMemory : 0);
	__CFAssignWithWriteBarrier((void **)&memory->_buckets, buckets);
	if (__CFOASafe) __CFSetLastAllocationEventName(memory->_buckets, "CFBinaryHeap (store)");
	if (NULL == memory->_buckets) {
	    CFRelease(memory);
	    return NULL;
	}
    __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 (compareContext) memcpy(&memory->_context, compareContext, sizeof(CFBinaryHeapCompareContext));
// CF: retain info for proper operation
    __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, kCFBinaryHeapMutable, capacity, NULL, 0, callBacks, compareContext);
}

CFBinaryHeapRef CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap) {
   __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    return __CFBinaryHeapInit(allocator, kCFBinaryHeapMutable, 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) __CFAssignWithWriteBarrier((void **)value, heap->_buckets[0]._item);
    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;
    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(heap) ? __kCFAllocatorGCScannedMemory : 0);
    __CFAssignWithWriteBarrier((void **)&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);
    switch (__CFBinaryHeapMutableVariety(heap)) {
    case kCFBinaryHeapMutable:
	if (__CFBinaryHeapNumBucketsUsed(heap) == __CFBinaryHeapCapacity(heap))
	    __CFBinaryHeapGrow(heap, 1);
	break;
    }
    cnt = __CFBinaryHeapCount(heap);
    idx = cnt;
    __CFBinaryHeapSetNumBucketsUsed(heap, cnt + 1);
    __CFBinaryHeapSetCount(heap, cnt + 1);
    CFComparisonResult (*compare)(const void *, const void *, void *) = heap->_callbacks.compare;
    pidx = (idx - 1) >> 1;
    while (0 < idx) {
	void *item = heap->_buckets[pidx]._item;
	if ((!compare && item <= value) || (compare && kCFCompareGreaterThan != compare(item, value, heap->_context.info))) break;
	__CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, item);
	idx = pidx;
	pidx = (idx - 1) >> 1;
    }
    if (heap->_callbacks.retain) {
	__CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, (void *)heap->_callbacks.retain(allocator, (void *)value));
    } else {
	__CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, (void *)value);
    }
}

void CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap) {
    void *val;
    CFIndex idx, cidx;
    CFIndex cnt;
    CFAllocatorRef allocator;
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    cnt = __CFBinaryHeapCount(heap);
    if (0 == cnt) return;
    idx = 0;
    __CFBinaryHeapSetNumBucketsUsed(heap, cnt - 1);
    __CFBinaryHeapSetCount(heap, cnt - 1);
    CFComparisonResult (*compare)(const void *, const void *, void *) = heap->_callbacks.compare;
    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 ((!compare && item > item2) || (compare && kCFCompareGreaterThan == compare(item, item2, heap->_context.info))) {
		cidx++;
		item = item2;
	    }
	}
	if ((!compare && item > val) || (compare && kCFCompareGreaterThan == compare(item, val, heap->_context.info))) break;
	__CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, item);
	idx = cidx;
	cidx = (idx << 1) + 1;
    }
    __CFAssignWithWriteBarrier((void **)&heap->_buckets[idx]._item, val);
}

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