Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

460 lines (413 sloc) 18.404 kb
/*
* 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);
}
Jump to Line
Something went wrong with that request. Please try again.