CoreFoundation/CFBinaryHeap.c - nest-cam/4320010/corefoundation - Git at Google

 /*
  * Copyright (c) 2008-2009 Brent Fulgham <bfulgham@gmail.org>.  All rights reserved.
  *
  * This source code is a modified version of the CoreFoundation sources released by Apple Inc. under
  * the terms of the APSL version 2.0 (see below).
  *
  * For information about changes from the original Apple source release can be found by reviewing the
  * source control system for the project at https://sourceforge.net/svn/?group_id=246198.
  *
  * The original license information is as follows:
  *
  * Copyright (c) 2008 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 1998-2002, Apple, Inc. All rights reserved.
 	Responsibility: Christopher Kane
 */

 #include <CoreFoundation/CFBinaryHeap.h>
 #include "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 : %s\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);
 	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;
 	}
     __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;
     }
     __CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapMutable);
     for (idx = 0; idx < numValues; idx++) {
 	CFBinaryHeapAddValue(memory, values[idx]);
     }
     __CFBinaryHeapSetMutableVariety(memory, __CFBinaryHeapMutableVarietyFromFlags(flags));
     if (compareContext) memcpy(&memory->_context, compareContext, sizeof(CFBinaryHeapCompareContext));
     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) __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(heap) ? __kCFAllocatorGCScannedMemory : 0);
     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);
     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);
     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);
     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);
     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);
 }
	/*
	* Copyright (c) 2008-2009 Brent Fulgham <bfulgham@gmail.org>. All rights reserved.
	*
	* This source code is a modified version of the CoreFoundation sources released by Apple Inc. under
	* the terms of the APSL version 2.0 (see below).
	*
	* For information about changes from the original Apple source release can be found by reviewing the
	* source control system for the project at https://sourceforge.net/svn/?group_id=246198.
	*
	* The original license information is as follows:
	*
	* Copyright (c) 2008 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 1998-2002, Apple, Inc. All rights reserved.
	Responsibility: Christopher Kane
	*/

	#include <CoreFoundation/CFBinaryHeap.h>
	#include "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 : %s\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);
	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;
	}
	__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;
	}
	__CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapMutable);
	for (idx = 0; idx < numValues; idx++) {
	CFBinaryHeapAddValue(memory, values[idx]);
	}
	__CFBinaryHeapSetMutableVariety(memory, __CFBinaryHeapMutableVarietyFromFlags(flags));
	if (compareContext) memcpy(&memory->_context, compareContext, sizeof(CFBinaryHeapCompareContext));
	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) __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(heap) ? __kCFAllocatorGCScannedMemory : 0);
	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);
	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);
	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);
	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);
	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);
	}