[apple/cf.git] / Collections.subproj / CFBinaryHeap.c

/*
 * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * 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 "CFUtilities.h"
#include "CFInternal.h"

const CFBinaryHeapCallBacks kCFStringBinaryHeapCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, (CFComparisonResult (*)(const void *, const void *, void *))CFStringCompare};

struct __CFBinaryHeapBucket {
    void *_item;
};

CF_INLINE CFIndex __CFBinaryHeapRoundUpCapacity(CFIndex capacity) {
    if (capacity < 4) return 4;
    return (1 << (CFLog2(capacity) + 1));
}

CF_INLINE CFIndex __CFBinaryHeapNumBucketsForCapacity(CFIndex capacity) {
    return capacity;
}

struct __CFBinaryHeap {
    CFRuntimeBase _base;
    CFIndex _count;	/* number of objects */
    CFIndex _capacity;	/* maximum number of objects */
    CFBinaryHeapCallBacks _callbacks;
    CFBinaryHeapCompareContext _context;
    struct __CFBinaryHeapBucket *_buckets;
};

CF_INLINE CFIndex __CFBinaryHeapCount(CFBinaryHeapRef heap) {
    return heap->_count;
}

CF_INLINE void __CFBinaryHeapSetCount(CFBinaryHeapRef heap, CFIndex v) {
    /* for a CFBinaryHeap, _bucketsUsed == _count */
}

CF_INLINE CFIndex __CFBinaryHeapCapacity(CFBinaryHeapRef heap) {
    return heap->_capacity;
}

CF_INLINE void __CFBinaryHeapSetCapacity(CFBinaryHeapRef heap, CFIndex v) {
    /* for a CFBinaryHeap, _bucketsNum == _capacity */
}

CF_INLINE CFIndex __CFBinaryHeapNumBucketsUsed(CFBinaryHeapRef heap) {
    return heap->_count;
}

CF_INLINE void __CFBinaryHeapSetNumBucketsUsed(CFBinaryHeapRef heap, CFIndex v) {
    heap->_count = v;
}

CF_INLINE CFIndex __CFBinaryHeapNumBuckets(CFBinaryHeapRef heap) {
    return heap->_capacity;
}

CF_INLINE void __CFBinaryHeapSetNumBuckets(CFBinaryHeapRef heap, CFIndex v) {
    heap->_capacity = v;
}

enum {
    kCFBinaryHeapImmutable = 0x0,		/* unchangable and fixed capacity; default */
    kCFBinaryHeapMutable = 0x1,		/* changeable and variable capacity */
    kCFBinaryHeapFixedMutable = 0x3	/* changeable and fixed capacity */
};

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

CF_INLINE void __CFBinaryHeapSetMutableVariety(void *cf, UInt32 v) {
    __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_info, 3, 2, v);
}

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

static bool __CFBinaryHeapEqual(CFTypeRef cf1, CFTypeRef cf2) {
    CFBinaryHeapRef heap1 = (CFBinaryHeapRef)cf1;
    CFBinaryHeapRef heap2 = (CFBinaryHeapRef)cf2;
    CFComparisonResult (*compare)(const void *, const void *, void *);
    CFIndex idx;
    CFIndex cnt;
    const void **list1, **list2, *buffer[256];
    cnt = __CFBinaryHeapCount(heap1);
    if (cnt != __CFBinaryHeapCount(heap2)) return false;
    compare = heap1->_callbacks.compare;
    if (compare != heap2->_callbacks.compare) return false;
    if (0 == cnt) return true;	/* after function comparison */
    list1 = (cnt <= 128) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * cnt * sizeof(void *), 0);
    if (__CFOASafe && list1 != buffer) __CFSetLastAllocationEventName(list1, "CFBinaryHeap (temp)");
    list2 = (cnt <= 128) ? buffer + 128 : list1 + cnt;
    CFBinaryHeapGetValues(heap1, list1);
    CFBinaryHeapGetValues(heap2, list2);
    for (idx = 0; idx < cnt; idx++) {
	const void *val1 = list1[idx];
	const void *val2 = list2[idx];
// CF: which context info should be passed in? both?
// CF: if the context infos are not equal, should the heaps not be equal?
	if (val1 != val2 && compare && !compare(val1, val2, heap1->_context.info)) return false;
    }
    if (list1 != buffer) CFAllocatorDeallocate(CFGetAllocator(heap1), list1);
    return true;
}

static UInt32 __CFBinaryHeapHash(CFTypeRef cf) {
    CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
    return __CFBinaryHeapCount(heap);
}

static CFStringRef __CFBinaryHeapCopyDescription(CFTypeRef cf) {
    CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
    CFMutableStringRef result;
    CFIndex idx;
    CFIndex cnt;
    const void **list, *buffer[256];
    cnt = __CFBinaryHeapCount(heap);
    result = CFStringCreateMutable(CFGetAllocator(heap), 0);
    CFStringAppendFormat(result, NULL, CFSTR("<CFBinaryHeap %p [%p]>{count = %u, capacity = %u, objects = (\n"), cf, CFGetAllocator(heap), cnt, __CFBinaryHeapCapacity(heap));
    list = (cnt <= 128) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, cnt * sizeof(void *), 0);
    if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(list, "CFBinaryHeap (temp)");
    CFBinaryHeapGetValues(heap, list);
    for (idx = 0; idx < cnt; idx++) {
	CFStringRef desc = NULL;
	const void *item = list[idx];
	if (NULL != heap->_callbacks.copyDescription) {
	    desc = heap->_callbacks.copyDescription(item);
	}
	if (NULL != desc) {
	    CFStringAppendFormat(result, NULL, CFSTR("\t%u : %s\n"), idx, desc);
	    CFRelease(desc);
	} else {
	    CFStringAppendFormat(result, NULL, CFSTR("\t%u : <0x%x>\n"), idx, (UInt32)item);
	}
    }
    CFStringAppend(result, CFSTR(")}"));
    if (list != buffer) CFAllocatorDeallocate(CFGetAllocator(heap), list);
    return result;
}

static void __CFBinaryHeapDeallocate(CFTypeRef cf) {
    CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
    CFAllocatorRef allocator = CFGetAllocator(heap);
// CF: should make the heap mutable here first, a la CFArrayDeallocate
    CFBinaryHeapRemoveAllValues(heap);
// CF: does not release the context info
    if (__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable) {
	CFAllocatorDeallocate(allocator, heap->_buckets);
    }
}

static CFTypeID __kCFBinaryHeapTypeID = _kCFRuntimeNotATypeID;

static const CFRuntimeClass __CFBinaryHeapClass = {
    0,
    "CFBinaryHeap",
    NULL,	// init
    NULL,	// copy
    __CFBinaryHeapDeallocate,
    (void *)__CFBinaryHeapEqual,
    __CFBinaryHeapHash,
    NULL,	// 
    __CFBinaryHeapCopyDescription
};

__private_extern__ void __CFBinaryHeapInitialize(void) {
    __kCFBinaryHeapTypeID = _CFRuntimeRegisterClass(&__CFBinaryHeapClass);
}

CFTypeID CFBinaryHeapGetTypeID(void) {
    return __kCFBinaryHeapTypeID;
}

static CFBinaryHeapRef __CFBinaryHeapInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const void **values, CFIndex numValues, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) {
// CF: does not copy the compareContext argument into the object
    CFBinaryHeapRef memory;
    CFIndex idx;
    CFIndex size;

    CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
    CFAssert3(kCFBinaryHeapFixedMutable != __CFBinaryHeapMutableVarietyFromFlags(flags) || numValues <= capacity, __kCFLogAssertion, "%s(): for fixed-mutable type, capacity (%d) must be greater than or equal to number of initial elements (%d)", __PRETTY_FUNCTION__, capacity, numValues);
    CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
    size = sizeof(struct __CFBinaryHeap) - sizeof(CFRuntimeBase);
    if (__CFBinaryHeapMutableVarietyFromFlags(flags) != kCFBinaryHeapMutable)
	size += sizeof(struct __CFBinaryHeapBucket) * __CFBinaryHeapNumBucketsForCapacity(capacity);
    memory = (CFBinaryHeapRef)_CFRuntimeCreateInstance(allocator, __kCFBinaryHeapTypeID, size, NULL);
    if (NULL == memory) {
	return NULL;
    }
    switch (__CFBinaryHeapMutableVarietyFromFlags(flags)) {
    case kCFBinaryHeapMutable:
	__CFBinaryHeapSetCapacity(memory, __CFBinaryHeapRoundUpCapacity(1));
	__CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(__CFBinaryHeapRoundUpCapacity(1)));
	memory->_buckets = CFAllocatorAllocate(allocator, __CFBinaryHeapNumBuckets(memory) * sizeof(struct __CFBinaryHeapBucket), 0);
	if (__CFOASafe) __CFSetLastAllocationEventName(memory->_buckets, "CFBinaryHeap (store)");
	if (NULL == memory->_buckets) {
	    CFRelease(memory);
	    return NULL;
	}
	break;
    case kCFBinaryHeapFixedMutable:
    case kCFBinaryHeapImmutable:
	/* Don't round up capacity */
	__CFBinaryHeapSetCapacity(memory, capacity);
	__CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(capacity));
	memory->_buckets = (struct __CFBinaryHeapBucket *)((int8_t *)memory + sizeof(struct __CFBinaryHeap));
	break;
    }
    __CFBinaryHeapSetNumBucketsUsed(memory, 0);
    __CFBinaryHeapSetCount(memory, 0);
    if (NULL != callBacks) {
	memory->_callbacks.retain = callBacks->retain;
	memory->_callbacks.release = callBacks->release;
	memory->_callbacks.copyDescription = callBacks->copyDescription;
	memory->_callbacks.compare = callBacks->compare;
    } else {
	memory->_callbacks.retain = 0;
	memory->_callbacks.release = 0;
	memory->_callbacks.copyDescription = 0;
	memory->_callbacks.compare = 0;
    }
    if (__CFBinaryHeapMutableVarietyFromFlags(flags) != kCFBinaryHeapMutable) {
        __CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapFixedMutable);
    } else {
        __CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapMutable);
    }
    for (idx = 0; idx < numValues; idx++) {
	CFBinaryHeapAddValue(memory, values[idx]);
    }
    __CFBinaryHeapSetMutableVariety(memory, __CFBinaryHeapMutableVarietyFromFlags(flags));
    return memory;
}

CFBinaryHeapRef CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext) {
   return __CFBinaryHeapInit(allocator, (0 == capacity) ? kCFBinaryHeapMutable : kCFBinaryHeapFixedMutable, capacity, NULL, 0, callBacks, compareContext);
}

CFBinaryHeapRef CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap) {
   __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    return __CFBinaryHeapInit(allocator, (0 == capacity) ? kCFBinaryHeapMutable : kCFBinaryHeapFixedMutable, capacity, (const void **)heap->_buckets, __CFBinaryHeapCount(heap), &(heap->_callbacks), &(heap->_context));
}

CFIndex CFBinaryHeapGetCount(CFBinaryHeapRef heap) {
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    return __CFBinaryHeapCount(heap);
}

CFIndex CFBinaryHeapGetCountOfValue(CFBinaryHeapRef heap, const void *value) {
    CFComparisonResult (*compare)(const void *, const void *, void *);
    CFIndex idx;
    CFIndex cnt = 0, length;
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    compare = heap->_callbacks.compare;
    length = __CFBinaryHeapCount(heap);
    for (idx = 0; idx < length; idx++) {
	const void *item = heap->_buckets[idx]._item;
	if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
	    cnt++;
	}
    }
    return cnt;
}

Boolean CFBinaryHeapContainsValue(CFBinaryHeapRef heap, const void *value) {
    CFComparisonResult (*compare)(const void *, const void *, void *);
    CFIndex idx;
    CFIndex length;
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    compare = heap->_callbacks.compare;
    length = __CFBinaryHeapCount(heap);
    for (idx = 0; idx < length; idx++) {
	const void *item = heap->_buckets[idx]._item;
	if (value == item || (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
	    return true;
	}
    }
    return false;
}

const void *CFBinaryHeapGetMinimum(CFBinaryHeapRef heap) {
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    CFAssert1(0 < __CFBinaryHeapCount(heap), __kCFLogAssertion, "%s(): binary heap is empty", __PRETTY_FUNCTION__);
    return (0 < __CFBinaryHeapCount(heap)) ? heap->_buckets[0]._item : NULL;
}

Boolean CFBinaryHeapGetMinimumIfPresent(CFBinaryHeapRef heap, const void **value) {
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    if (0 == __CFBinaryHeapCount(heap)) return false;
    if (NULL != value) *value = heap->_buckets[0]._item;
    return true;
}

void CFBinaryHeapGetValues(CFBinaryHeapRef heap, const void **values) {
    CFBinaryHeapRef heapCopy;
    CFIndex idx;
    CFIndex cnt;
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    CFAssert1(NULL != values, __kCFLogAssertion, "%s(): pointer to values may not be NULL", __PRETTY_FUNCTION__);
    cnt = __CFBinaryHeapCount(heap);
    if (0 == cnt) return;
    heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
    idx = 0;
    while (0 < __CFBinaryHeapCount(heapCopy)) {
	const void *value = CFBinaryHeapGetMinimum(heapCopy);
	CFBinaryHeapRemoveMinimumValue(heapCopy);
	values[idx++] = value;
    }
    CFRelease(heapCopy);
}

void CFBinaryHeapApplyFunction(CFBinaryHeapRef heap, CFBinaryHeapApplierFunction applier, void *context) {
    CFBinaryHeapRef heapCopy;
    CFIndex cnt;
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
    cnt = __CFBinaryHeapCount(heap);
    if (0 == cnt) return;
    heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
    while (0 < __CFBinaryHeapCount(heapCopy)) {
	const void *value = CFBinaryHeapGetMinimum(heapCopy);
	CFBinaryHeapRemoveMinimumValue(heapCopy);
	applier(value, context);
    }
    CFRelease(heapCopy);
}

static void __CFBinaryHeapGrow(CFBinaryHeapRef heap, CFIndex numNewValues) {
    CFIndex oldCount = __CFBinaryHeapCount(heap);
    CFIndex capacity = __CFBinaryHeapRoundUpCapacity(oldCount + numNewValues);
    __CFBinaryHeapSetCapacity(heap, capacity);
    __CFBinaryHeapSetNumBuckets(heap, __CFBinaryHeapNumBucketsForCapacity(capacity));
    heap->_buckets = CFAllocatorReallocate(CFGetAllocator(heap), heap->_buckets, __CFBinaryHeapNumBuckets(heap) * sizeof(struct __CFBinaryHeapBucket), 0);
    if (__CFOASafe) __CFSetLastAllocationEventName(heap->_buckets, "CFBinaryHeap (store)");
    if (NULL == heap->_buckets) HALT;
}

void CFBinaryHeapAddValue(CFBinaryHeapRef heap, const void *value) {
    CFIndex idx, pidx;
    CFIndex cnt;
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable || __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
    switch (__CFBinaryHeapMutableVariety(heap)) {
    case kCFBinaryHeapMutable:
	if (__CFBinaryHeapNumBucketsUsed(heap) == __CFBinaryHeapCapacity(heap))
	    __CFBinaryHeapGrow(heap, 1);
	break;
    case kCFBinaryHeapFixedMutable:
	CFAssert1(__CFBinaryHeapCount(heap) < __CFBinaryHeapCapacity(heap), __kCFLogAssertion, "%s(): fixed-capacity binary heap is full", __PRETTY_FUNCTION__);
	break;
    }
    cnt = __CFBinaryHeapCount(heap);
    idx = cnt;
    __CFBinaryHeapSetNumBucketsUsed(heap, cnt + 1);
    __CFBinaryHeapSetCount(heap, cnt + 1);
    pidx = (idx - 1) >> 1;
    while (0 < idx) {
	void *item = heap->_buckets[pidx]._item;
	if (kCFCompareGreaterThan != heap->_callbacks.compare(item, value, heap->_context.info)) break;
	heap->_buckets[idx]._item = item;
	idx = pidx;
	pidx = (idx - 1) >> 1;
    }
    if (heap->_callbacks.retain) {
	heap->_buckets[idx]._item = (void *)heap->_callbacks.retain(CFGetAllocator(heap), (void *)value);
    } else {
	heap->_buckets[idx]._item = (void *)value;
    }
}

void CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap) {
    void *val;
    CFIndex idx, cidx;
    CFIndex cnt;
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable || __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
    cnt = __CFBinaryHeapCount(heap);
    if (0 == cnt) return;
    idx = 0;
    __CFBinaryHeapSetNumBucketsUsed(heap, cnt - 1);
    __CFBinaryHeapSetCount(heap, cnt - 1);
    if (heap->_callbacks.release)
	heap->_callbacks.release(CFGetAllocator(heap), 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;
	heap->_buckets[idx]._item = item;
	idx = cidx;
	cidx = (idx << 1) + 1;
    }
    heap->_buckets[idx]._item = val;
}

void CFBinaryHeapRemoveAllValues(CFBinaryHeapRef heap) {
    CFIndex idx;
    CFIndex cnt;
    __CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
    CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable || __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
    cnt = __CFBinaryHeapCount(heap);
    if (heap->_callbacks.release)
	for (idx = 0; idx < cnt; idx++)
	    heap->_callbacks.release(CFGetAllocator(heap), heap->_buckets[idx]._item);
    __CFBinaryHeapSetNumBucketsUsed(heap, 0);
    __CFBinaryHeapSetCount(heap, 0);
}
Commit	Line	Data
9ce05555 A	1	/*
	2	* Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
	6	* Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
	7	*
	8	* This file contains Original Code and/or Modifications of Original Code
	9	* as defined in and that are subject to the Apple Public Source License
	10	* Version 2.0 (the 'License'). You may not use this file except in
	11	* compliance with the License. Please obtain a copy of the License at
	12	* http://www.opensource.apple.com/apsl/ and read it before using this
	13	* file.
	14	*
	15	* The Original Code and all software distributed under the License are
	16	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	17	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	18	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	19	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	20	* Please see the License for the specific language governing rights and
	21	* limitations under the License.
	22	*
	23	* @APPLE_LICENSE_HEADER_END@
	24	*/
	25	/* CFBinaryHeap.c
	26	Copyright 1998-2002, Apple, Inc. All rights reserved.
	27	Responsibility: Christopher Kane
	28	*/
	29
	30	#include <CoreFoundation/CFBinaryHeap.h>
	31	#include "CFUtilities.h"
	32	#include "CFInternal.h"
	33
	34	const CFBinaryHeapCallBacks kCFStringBinaryHeapCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, (CFComparisonResult ()(const void , const void , void ))CFStringCompare};
	35
	36	struct __CFBinaryHeapBucket {
	37	void *_item;
	38	};
	39
	40	CF_INLINE CFIndex __CFBinaryHeapRoundUpCapacity(CFIndex capacity) {
	41	if (capacity < 4) return 4;
	42	return (1 << (CFLog2(capacity) + 1));
	43	}
	44
	45	CF_INLINE CFIndex __CFBinaryHeapNumBucketsForCapacity(CFIndex capacity) {
	46	return capacity;
	47	}
	48
	49	struct __CFBinaryHeap {
	50	CFRuntimeBase _base;
	51	CFIndex _count; /* number of objects */
	52	CFIndex _capacity; /* maximum number of objects */
	53	CFBinaryHeapCallBacks _callbacks;
	54	CFBinaryHeapCompareContext _context;
	55	struct __CFBinaryHeapBucket *_buckets;
	56	};
	57
	58	CF_INLINE CFIndex __CFBinaryHeapCount(CFBinaryHeapRef heap) {
	59	return heap->_count;
	60	}
	61
	62	CF_INLINE void __CFBinaryHeapSetCount(CFBinaryHeapRef heap, CFIndex v) {
	63	/* for a CFBinaryHeap, _bucketsUsed == _count */
	64	}
65
66	CF_INLINE CFIndex __CFBinaryHeapCapacity(CFBinaryHeapRef heap) {
67	return heap->_capacity;
68	}
69
70	CF_INLINE void __CFBinaryHeapSetCapacity(CFBinaryHeapRef heap, CFIndex v) {
71	/* for a CFBinaryHeap, _bucketsNum == _capacity */
72	}
73
74	CF_INLINE CFIndex __CFBinaryHeapNumBucketsUsed(CFBinaryHeapRef heap) {
75	return heap->_count;
76	}
77
78	CF_INLINE void __CFBinaryHeapSetNumBucketsUsed(CFBinaryHeapRef heap, CFIndex v) {
79	heap->_count = v;
80	}
81
82	CF_INLINE CFIndex __CFBinaryHeapNumBuckets(CFBinaryHeapRef heap) {
83	return heap->_capacity;
84	}
85
86	CF_INLINE void __CFBinaryHeapSetNumBuckets(CFBinaryHeapRef heap, CFIndex v) {
87	heap->_capacity = v;
88	}
89
90	enum {
91	kCFBinaryHeapImmutable = 0x0, /* unchangable and fixed capacity; default */
92	kCFBinaryHeapMutable = 0x1, /* changeable and variable capacity */
93	kCFBinaryHeapFixedMutable = 0x3 /* changeable and fixed capacity */
94	};
95
96	CF_INLINE UInt32 __CFBinaryHeapMutableVariety(const void *cf) {
97	return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_info, 3, 2);
98	}
99
100	CF_INLINE void __CFBinaryHeapSetMutableVariety(void *cf, UInt32 v) {
101	__CFBitfieldSetValue(((CFRuntimeBase *)cf)->_info, 3, 2, v);
102	}
103
104	CF_INLINE UInt32 __CFBinaryHeapMutableVarietyFromFlags(UInt32 flags) {
105	return __CFBitfieldGetValue(flags, 1, 0);
106	}
107
108	static bool __CFBinaryHeapEqual(CFTypeRef cf1, CFTypeRef cf2) {
109	CFBinaryHeapRef heap1 = (CFBinaryHeapRef)cf1;
110	CFBinaryHeapRef heap2 = (CFBinaryHeapRef)cf2;
111	CFComparisonResult (compare)(const void , const void , void );
112	CFIndex idx;
113	CFIndex cnt;
114	const void list1, list2, *buffer[256];
115	cnt = __CFBinaryHeapCount(heap1);
116	if (cnt != __CFBinaryHeapCount(heap2)) return false;
117	compare = heap1->_callbacks.compare;
118	if (compare != heap2->_callbacks.compare) return false;
119	if (0 == cnt) return true; /* after function comparison */
120	list1 = (cnt <= 128) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, 2 * cnt * sizeof(void *), 0);
121	if (__CFOASafe && list1 != buffer) __CFSetLastAllocationEventName(list1, "CFBinaryHeap (temp)");
122	list2 = (cnt <= 128) ? buffer + 128 : list1 + cnt;
123	CFBinaryHeapGetValues(heap1, list1);
124	CFBinaryHeapGetValues(heap2, list2);
125	for (idx = 0; idx < cnt; idx++) {
126	const void *val1 = list1[idx];
127	const void *val2 = list2[idx];
128	// CF: which context info should be passed in? both?
129	// CF: if the context infos are not equal, should the heaps not be equal?
130	if (val1 != val2 && compare && !compare(val1, val2, heap1->_context.info)) return false;
131	}
132	if (list1 != buffer) CFAllocatorDeallocate(CFGetAllocator(heap1), list1);
133	return true;
134	}
135
136	static UInt32 __CFBinaryHeapHash(CFTypeRef cf) {
137	CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
138	return __CFBinaryHeapCount(heap);
139	}
140
141	static CFStringRef __CFBinaryHeapCopyDescription(CFTypeRef cf) {
142	CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
143	CFMutableStringRef result;
144	CFIndex idx;
145	CFIndex cnt;
146	const void *list, buffer[256];
147	cnt = __CFBinaryHeapCount(heap);
148	result = CFStringCreateMutable(CFGetAllocator(heap), 0);
149	CFStringAppendFormat(result, NULL, CFSTR("<CFBinaryHeap %p [%p]>{count = %u, capacity = %u, objects = (\n"), cf, CFGetAllocator(heap), cnt, __CFBinaryHeapCapacity(heap));
150	list = (cnt <= 128) ? buffer : CFAllocatorAllocate(kCFAllocatorSystemDefault, cnt * sizeof(void *), 0);
151	if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(list, "CFBinaryHeap (temp)");
152	CFBinaryHeapGetValues(heap, list);
153	for (idx = 0; idx < cnt; idx++) {
154	CFStringRef desc = NULL;
155	const void *item = list[idx];
156	if (NULL != heap->_callbacks.copyDescription) {
157	desc = heap->_callbacks.copyDescription(item);
158	}
159	if (NULL != desc) {
160	CFStringAppendFormat(result, NULL, CFSTR("\t%u : %s\n"), idx, desc);
161	CFRelease(desc);
162	} else {
163	CFStringAppendFormat(result, NULL, CFSTR("\t%u : <0x%x>\n"), idx, (UInt32)item);
164	}
165	}
166	CFStringAppend(result, CFSTR(")}"));
167	if (list != buffer) CFAllocatorDeallocate(CFGetAllocator(heap), list);
168	return result;
169	}
170
171	static void __CFBinaryHeapDeallocate(CFTypeRef cf) {
172	CFBinaryHeapRef heap = (CFBinaryHeapRef)cf;
173	CFAllocatorRef allocator = CFGetAllocator(heap);
174	// CF: should make the heap mutable here first, a la CFArrayDeallocate
175	CFBinaryHeapRemoveAllValues(heap);
176	// CF: does not release the context info
177	if (__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable) {
178	CFAllocatorDeallocate(allocator, heap->_buckets);
179	}
180	}
181
182	static CFTypeID __kCFBinaryHeapTypeID = _kCFRuntimeNotATypeID;
183
184	static const CFRuntimeClass __CFBinaryHeapClass = {
185	0,
186	"CFBinaryHeap",
187	NULL, // init
188	NULL, // copy
189	__CFBinaryHeapDeallocate,
190	(void *)__CFBinaryHeapEqual,
191	__CFBinaryHeapHash,
192	NULL, //
193	__CFBinaryHeapCopyDescription
194	};
195
196	__private_extern__ void __CFBinaryHeapInitialize(void) {
197	__kCFBinaryHeapTypeID = _CFRuntimeRegisterClass(&__CFBinaryHeapClass);
198	}
199
200	CFTypeID CFBinaryHeapGetTypeID(void) {
201	return __kCFBinaryHeapTypeID;
202	}
203
204	static CFBinaryHeapRef __CFBinaryHeapInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const void *values, CFIndex numValues, const CFBinaryHeapCallBacks callBacks, const CFBinaryHeapCompareContext *compareContext) {
205	// CF: does not copy the compareContext argument into the object
206	CFBinaryHeapRef memory;
207	CFIndex idx;
208	CFIndex size;
209
210	CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
211	CFAssert3(kCFBinaryHeapFixedMutable != __CFBinaryHeapMutableVarietyFromFlags(flags) \|\| numValues <= capacity, __kCFLogAssertion, "%s(): for fixed-mutable type, capacity (%d) must be greater than or equal to number of initial elements (%d)", __PRETTY_FUNCTION__, capacity, numValues);
212	CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
213	size = sizeof(struct __CFBinaryHeap) - sizeof(CFRuntimeBase);
214	if (__CFBinaryHeapMutableVarietyFromFlags(flags) != kCFBinaryHeapMutable)
215	size += sizeof(struct __CFBinaryHeapBucket) * __CFBinaryHeapNumBucketsForCapacity(capacity);
216	memory = (CFBinaryHeapRef)_CFRuntimeCreateInstance(allocator, __kCFBinaryHeapTypeID, size, NULL);
217	if (NULL == memory) {
218	return NULL;
219	}
220	switch (__CFBinaryHeapMutableVarietyFromFlags(flags)) {
221	case kCFBinaryHeapMutable:
222	__CFBinaryHeapSetCapacity(memory, __CFBinaryHeapRoundUpCapacity(1));
223	__CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(__CFBinaryHeapRoundUpCapacity(1)));
224	memory->_buckets = CFAllocatorAllocate(allocator, __CFBinaryHeapNumBuckets(memory) * sizeof(struct __CFBinaryHeapBucket), 0);
225	if (__CFOASafe) __CFSetLastAllocationEventName(memory->_buckets, "CFBinaryHeap (store)");
226	if (NULL == memory->_buckets) {
227	CFRelease(memory);
228	return NULL;
229	}
230	break;
231	case kCFBinaryHeapFixedMutable:
232	case kCFBinaryHeapImmutable:
233	/* Don't round up capacity */
234	__CFBinaryHeapSetCapacity(memory, capacity);
235	__CFBinaryHeapSetNumBuckets(memory, __CFBinaryHeapNumBucketsForCapacity(capacity));
236	memory->_buckets = (struct __CFBinaryHeapBucket )((int8_t )memory + sizeof(struct __CFBinaryHeap));
237	break;
238	}
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	}
252	if (__CFBinaryHeapMutableVarietyFromFlags(flags) != kCFBinaryHeapMutable) {
253	__CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapFixedMutable);
254	} else {
255	__CFBinaryHeapSetMutableVariety(memory, kCFBinaryHeapMutable);
256	}
257	for (idx = 0; idx < numValues; idx++) {
258	CFBinaryHeapAddValue(memory, values[idx]);
259	}
260	__CFBinaryHeapSetMutableVariety(memory, __CFBinaryHeapMutableVarietyFromFlags(flags));
261	return memory;
262	}
263
264	CFBinaryHeapRef CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks callBacks, const CFBinaryHeapCompareContext compareContext) {
265	return __CFBinaryHeapInit(allocator, (0 == capacity) ? kCFBinaryHeapMutable : kCFBinaryHeapFixedMutable, capacity, NULL, 0, callBacks, compareContext);
266	}
267
268	CFBinaryHeapRef CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap) {
269	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
270	return __CFBinaryHeapInit(allocator, (0 == capacity) ? kCFBinaryHeapMutable : kCFBinaryHeapFixedMutable, capacity, (const void **)heap->_buckets, __CFBinaryHeapCount(heap), &(heap->_callbacks), &(heap->_context));
271	}
272
273	CFIndex CFBinaryHeapGetCount(CFBinaryHeapRef heap) {
274	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
275	return __CFBinaryHeapCount(heap);
276	}
277
278	CFIndex CFBinaryHeapGetCountOfValue(CFBinaryHeapRef heap, const void *value) {
279	CFComparisonResult (compare)(const void , const void , void );
280	CFIndex idx;
281	CFIndex cnt = 0, length;
282	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
283	compare = heap->_callbacks.compare;
284	length = __CFBinaryHeapCount(heap);
285	for (idx = 0; idx < length; idx++) {
286	const void *item = heap->_buckets[idx]._item;
287	if (value == item \|\| (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
288	cnt++;
289	}
290	}
291	return cnt;
292	}
293
294	Boolean CFBinaryHeapContainsValue(CFBinaryHeapRef heap, const void *value) {
295	CFComparisonResult (compare)(const void , const void , void );
296	CFIndex idx;
297	CFIndex length;
298	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
299	compare = heap->_callbacks.compare;
300	length = __CFBinaryHeapCount(heap);
301	for (idx = 0; idx < length; idx++) {
302	const void *item = heap->_buckets[idx]._item;
303	if (value == item \|\| (compare && kCFCompareEqualTo == compare(value, item, heap->_context.info))) {
304	return true;
305	}
306	}
307	return false;
308	}
309
310	const void *CFBinaryHeapGetMinimum(CFBinaryHeapRef heap) {
311	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
312	CFAssert1(0 < __CFBinaryHeapCount(heap), __kCFLogAssertion, "%s(): binary heap is empty", __PRETTY_FUNCTION__);
313	return (0 < __CFBinaryHeapCount(heap)) ? heap->_buckets[0]._item : NULL;
314	}
315
316	Boolean CFBinaryHeapGetMinimumIfPresent(CFBinaryHeapRef heap, const void **value) {
317	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
318	if (0 == __CFBinaryHeapCount(heap)) return false;
319	if (NULL != value) *value = heap->_buckets[0]._item;
320	return true;
321	}
322
323	void CFBinaryHeapGetValues(CFBinaryHeapRef heap, const void **values) {
324	CFBinaryHeapRef heapCopy;
325	CFIndex idx;
326	CFIndex cnt;
327	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
328	CFAssert1(NULL != values, __kCFLogAssertion, "%s(): pointer to values may not be NULL", __PRETTY_FUNCTION__);
329	cnt = __CFBinaryHeapCount(heap);
330	if (0 == cnt) return;
331	heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
332	idx = 0;
333	while (0 < __CFBinaryHeapCount(heapCopy)) {
334	const void *value = CFBinaryHeapGetMinimum(heapCopy);
335	CFBinaryHeapRemoveMinimumValue(heapCopy);
336	values[idx++] = value;
337	}
338	CFRelease(heapCopy);
339	}
340
341	void CFBinaryHeapApplyFunction(CFBinaryHeapRef heap, CFBinaryHeapApplierFunction applier, void *context) {
342	CFBinaryHeapRef heapCopy;
343	CFIndex cnt;
344	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
345	CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
346	cnt = __CFBinaryHeapCount(heap);
347	if (0 == cnt) return;
348	heapCopy = CFBinaryHeapCreateCopy(CFGetAllocator(heap), cnt, heap);
349	while (0 < __CFBinaryHeapCount(heapCopy)) {
350	const void *value = CFBinaryHeapGetMinimum(heapCopy);
351	CFBinaryHeapRemoveMinimumValue(heapCopy);
352	applier(value, context);
353	}
354	CFRelease(heapCopy);
355	}
356
357	static void __CFBinaryHeapGrow(CFBinaryHeapRef heap, CFIndex numNewValues) {
358	CFIndex oldCount = __CFBinaryHeapCount(heap);
359	CFIndex capacity = __CFBinaryHeapRoundUpCapacity(oldCount + numNewValues);
360	__CFBinaryHeapSetCapacity(heap, capacity);
361	__CFBinaryHeapSetNumBuckets(heap, __CFBinaryHeapNumBucketsForCapacity(capacity));
362	heap->_buckets = CFAllocatorReallocate(CFGetAllocator(heap), heap->_buckets, __CFBinaryHeapNumBuckets(heap) * sizeof(struct __CFBinaryHeapBucket), 0);
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;
370	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
371	CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable \|\| __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
372	switch (__CFBinaryHeapMutableVariety(heap)) {
373	case kCFBinaryHeapMutable:
374	if (__CFBinaryHeapNumBucketsUsed(heap) == __CFBinaryHeapCapacity(heap))
375	__CFBinaryHeapGrow(heap, 1);
376	break;
377	case kCFBinaryHeapFixedMutable:
378	CFAssert1(__CFBinaryHeapCount(heap) < __CFBinaryHeapCapacity(heap), __kCFLogAssertion, "%s(): fixed-capacity binary heap is full", __PRETTY_FUNCTION__);
379	break;
380	}
381	cnt = __CFBinaryHeapCount(heap);
382	idx = cnt;
383	__CFBinaryHeapSetNumBucketsUsed(heap, cnt + 1);
384	__CFBinaryHeapSetCount(heap, cnt + 1);
385	pidx = (idx - 1) >> 1;
386	while (0 < idx) {
387	void *item = heap->_buckets[pidx]._item;
388	if (kCFCompareGreaterThan != heap->_callbacks.compare(item, value, heap->_context.info)) break;
389	heap->_buckets[idx]._item = item;
390	idx = pidx;
391	pidx = (idx - 1) >> 1;
392	}
393	if (heap->_callbacks.retain) {
394	heap->_buckets[idx]._item = (void )heap->_callbacks.retain(CFGetAllocator(heap), (void )value);
395	} else {
396	heap->_buckets[idx]._item = (void *)value;
397	}
398	}
399
400	void CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap) {
401	void *val;
402	CFIndex idx, cidx;
403	CFIndex cnt;
404	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
405	CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable \|\| __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
406	cnt = __CFBinaryHeapCount(heap);
407	if (0 == cnt) return;
408	idx = 0;
409	__CFBinaryHeapSetNumBucketsUsed(heap, cnt - 1);
410	__CFBinaryHeapSetCount(heap, cnt - 1);
411	if (heap->_callbacks.release)
412	heap->_callbacks.release(CFGetAllocator(heap), heap->_buckets[idx]._item);
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;
419	if (kCFCompareGreaterThan == heap->_callbacks.compare(item, item2, heap->_context.info)) {
420	cidx++;
421	item = item2;
422	}
423	}
424	if (kCFCompareGreaterThan == heap->_callbacks.compare(item, val, heap->_context.info)) break;
425	heap->_buckets[idx]._item = item;
426	idx = cidx;
427	cidx = (idx << 1) + 1;
428	}
429	heap->_buckets[idx]._item = val;
430	}
431
432	void CFBinaryHeapRemoveAllValues(CFBinaryHeapRef heap) {
433	CFIndex idx;
434	CFIndex cnt;
435	__CFGenericValidateType(heap, __kCFBinaryHeapTypeID);
436	CFAssert1(__CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapMutable \|\| __CFBinaryHeapMutableVariety(heap) == kCFBinaryHeapFixedMutable, __kCFLogAssertion, "%s(): binary heap is immutable", __PRETTY_FUNCTION__);
437	cnt = __CFBinaryHeapCount(heap);
438	if (heap->_callbacks.release)
439	for (idx = 0; idx < cnt; idx++)
440	heap->_callbacks.release(CFGetAllocator(heap), heap->_buckets[idx]._item);
441	__CFBinaryHeapSetNumBucketsUsed(heap, 0);
442	__CFBinaryHeapSetCount(heap, 0);
443	}
444