[apple/cf.git] / CFBinaryHeap.c

/*
 * Copyright (c) 2015 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-2014, 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 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 = %lu, capacity = %lu, objects = (\n"), cf, CFGetAllocator(heap), (unsigned long)cnt, (unsigned long)__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%lu : %@\n"), (unsigned long)idx, desc);
	    CFRelease(desc);
	} else {
	    CFStringAppendFormat(result, NULL, CFSTR("\t%lu : <%p>\n"), (unsigned long)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
};

CFTypeID CFBinaryHeapGetTypeID(void) {
    static dispatch_once_t initOnce;
    dispatch_once(&initOnce, ^{ __kCFBinaryHeapTypeID = _CFRuntimeRegisterClass(&__CFBinaryHeapClass); });
    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, CFBinaryHeapGetTypeID(), 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, CFBinaryHeapGetTypeID());
    return __CFBinaryHeapInit(allocator, kCFBinaryHeapMutable, capacity, (const void **)heap->_buckets, __CFBinaryHeapCount(heap), &(heap->_callbacks), &(heap->_context));
}

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