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