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/*	CFTree.c
25	Copyright (c) 1998-2013, Apple Inc. All rights reserved.
26	Responsibility: Christopher Kane
27*/
28
29#include <CoreFoundation/CFTree.h>
30#include "CFInternal.h"
31#include <CoreFoundation/CFPriv.h>
32
33struct __CFTreeCallBacks {
34    CFTreeRetainCallBack		retain;
35    CFTreeReleaseCallBack		release;
36    CFTreeCopyDescriptionCallBack	copyDescription;
37};
38
39struct __CFTree {
40    CFRuntimeBase _base;
41    CFTreeRef _parent;	/* Not retained */
42    CFTreeRef _sibling;	/* Not retained */
43    CFTreeRef _child;	/* All children get a retain from the parent */
44    CFTreeRef _rightmostChild;	/* Not retained */
45    /* This is the context, exploded.
46     * Currently the only valid version is 0, so we do not store that.
47     * _callbacks initialized if not a special form. */
48    void *_info;
49    struct __CFTreeCallBacks *_callbacks;
50};
51
52static const struct __CFTreeCallBacks __kCFTypeTreeCallBacks = {CFRetain, CFRelease, CFCopyDescription};
53static const struct __CFTreeCallBacks __kCFNullTreeCallBacks = {NULL, NULL, NULL};
54
55enum {          /* Bits 0-1 */
56    __kCFTreeHasNullCallBacks = 0,
57    __kCFTreeHasCFTypeCallBacks = 1,
58    __kCFTreeHasCustomCallBacks = 3    /* callbacks pointed to by _callbacks */
59};
60
61CF_INLINE uint32_t __CFTreeGetCallBacksType(CFTreeRef tree) {
62    return (__CFBitfieldGetValue(tree->_base._cfinfo[CF_INFO_BITS], 1, 0));
63}
64
65CF_INLINE const struct __CFTreeCallBacks *__CFTreeGetCallBacks(CFTreeRef tree) {
66    switch (__CFTreeGetCallBacksType(tree)) {
67    case __kCFTreeHasNullCallBacks:
68	return &__kCFNullTreeCallBacks;
69    case __kCFTreeHasCFTypeCallBacks:
70	return &__kCFTypeTreeCallBacks;
71    case __kCFTreeHasCustomCallBacks:
72	break;
73    }
74    return tree->_callbacks;
75}
76
77CF_INLINE bool __CFTreeCallBacksMatchNull(const CFTreeContext *c) {
78    return (NULL == c || (c->retain == NULL && c->release == NULL && c->copyDescription == NULL));
79}
80
81CF_INLINE bool __CFTreeCallBacksMatchCFType(const CFTreeContext *c) {
82    return (NULL != c && (c->retain == CFRetain && c->release == CFRelease && c->copyDescription == CFCopyDescription));
83}
84
85static CFStringRef __CFTreeCopyDescription(CFTypeRef cf) {
86    CFTreeRef tree = (CFTreeRef)cf;
87    CFMutableStringRef result;
88    CFStringRef contextDesc = NULL;
89    const struct __CFTreeCallBacks *cb;
90    CFAllocatorRef allocator;
91    allocator = CFGetAllocator(tree);
92    result = CFStringCreateMutable(allocator, 0);
93    cb = __CFTreeGetCallBacks(tree);
94    if (NULL != cb->copyDescription) {
95	contextDesc = (CFStringRef)INVOKE_CALLBACK1(cb->copyDescription, tree->_info);
96    }
97    if (NULL == contextDesc) {
98	contextDesc = CFStringCreateWithFormat(allocator, NULL, CFSTR("<CFTree context %p>"), tree->_info);
99    }
100    CFStringAppendFormat(result, NULL, CFSTR("<CFTree %p [%p]>{children = %lu, context = %@}"), cf, allocator, (unsigned long)CFTreeGetChildCount(tree), contextDesc);
101    if (contextDesc) CFRelease(contextDesc);
102    return result;
103}
104
105static void __CFTreeDeallocate(CFTypeRef cf) {
106    CFTreeRef tree = (CFTreeRef)cf;
107    const struct __CFTreeCallBacks *cb;
108#if DEPLOYMENT_TARGET_MACOSX
109    CFAllocatorRef allocator = __CFGetAllocator(tree);
110    if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
111        // GC:  keep the tree intact during finalization.
112        CFTreeRemoveAllChildren(tree);
113    }
114#endif
115    cb = __CFTreeGetCallBacks(tree);
116    if (NULL != cb->release) {
117        INVOKE_CALLBACK1(cb->release, tree->_info);
118    }
119    if (__kCFTreeHasCustomCallBacks == __CFTreeGetCallBacksType(tree)) {
120        _CFAllocatorDeallocateGC(CFGetAllocator(tree), tree->_callbacks);
121    }
122}
123
124
125static CFTypeID __kCFTreeTypeID = _kCFRuntimeNotATypeID;
126
127static const CFRuntimeClass __CFTreeClass = {
128    _kCFRuntimeScannedObject,
129    "CFTree",
130    NULL,	// init
131    NULL,	// copy
132    __CFTreeDeallocate,
133    NULL,	// equal
134    NULL,	// hash
135    NULL,	//
136    __CFTreeCopyDescription
137};
138
139CF_PRIVATE void __CFTreeInitialize(void) {
140    __kCFTreeTypeID = _CFRuntimeRegisterClass(&__CFTreeClass);
141}
142
143CFTypeID CFTreeGetTypeID(void) {
144    return __kCFTreeTypeID;
145}
146
147CFTreeRef CFTreeCreate(CFAllocatorRef allocator, const CFTreeContext *context) {
148    CFTreeRef memory;
149    uint32_t size;
150
151    CFAssert1(NULL != context, __kCFLogAssertion, "%s(): pointer to context may not be NULL", __PRETTY_FUNCTION__);
152    CFAssert1(0 == context->version, __kCFLogAssertion, "%s(): context version not initialized to 0", __PRETTY_FUNCTION__);
153    size = sizeof(struct __CFTree) - sizeof(CFRuntimeBase);
154    memory = (CFTreeRef)_CFRuntimeCreateInstance(allocator, __kCFTreeTypeID, size, NULL);
155    if (NULL == memory) {
156	return NULL;
157    }
158    memory->_parent = NULL;
159    memory->_sibling = NULL;
160    memory->_child = NULL;
161    memory->_rightmostChild = NULL;
162
163    /* Start the context off in a recognizable state */
164    __CFBitfieldSetValue(memory->_base._cfinfo[CF_INFO_BITS], 1, 0, __kCFTreeHasNullCallBacks);
165    CFTreeSetContext(memory, context);
166    return memory;
167}
168
169CFIndex CFTreeGetChildCount(CFTreeRef tree) {
170    SInt32 cnt = 0;
171    __CFGenericValidateType(tree, __kCFTreeTypeID);
172    tree = tree->_child;
173    while (NULL != tree) {
174	cnt++;
175	tree = tree->_sibling;
176    }
177    return cnt;
178}
179
180CFTreeRef CFTreeGetParent(CFTreeRef tree) {
181    __CFGenericValidateType(tree, __kCFTreeTypeID);
182    return tree->_parent;
183}
184
185CFTreeRef CFTreeGetNextSibling(CFTreeRef tree) {
186    __CFGenericValidateType(tree, __kCFTreeTypeID);
187    return tree->_sibling;
188}
189
190CFTreeRef CFTreeGetFirstChild(CFTreeRef tree) {
191    __CFGenericValidateType(tree, __kCFTreeTypeID);
192    return tree->_child;
193}
194
195CFTreeRef CFTreeFindRoot(CFTreeRef tree) {
196    __CFGenericValidateType(tree, __kCFTreeTypeID);
197    while (NULL != tree->_parent) {
198	tree = tree->_parent;
199    }
200    return tree;
201}
202
203void CFTreeGetContext(CFTreeRef tree, CFTreeContext *context) {
204    const struct __CFTreeCallBacks *cb;
205    __CFGenericValidateType(tree, __kCFTreeTypeID);
206    CFAssert1(0 == context->version, __kCFLogAssertion, "%s(): context version not initialized to 0", __PRETTY_FUNCTION__);
207    cb = __CFTreeGetCallBacks(tree);
208    context->version = 0;
209    context->info = tree->_info;
210    context->retain = cb->retain;
211    context->release = cb->release;
212    context->copyDescription = cb->copyDescription;
213    UNFAULT_CALLBACK(context->retain);
214    UNFAULT_CALLBACK(context->release);
215    UNFAULT_CALLBACK(context->copyDescription);
216}
217
218void CFTreeSetContext(CFTreeRef tree, const CFTreeContext *context) {
219    uint32_t newtype, oldtype = __CFTreeGetCallBacksType(tree);
220    struct __CFTreeCallBacks *oldcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
221    struct __CFTreeCallBacks *newcb;
222    void *oldinfo = tree->_info;
223    CFAllocatorRef allocator = CFGetAllocator(tree);
224
225    if (__CFTreeCallBacksMatchNull(context)) {
226        newtype = __kCFTreeHasNullCallBacks;
227    } else if (__CFTreeCallBacksMatchCFType(context)) {
228        newtype = __kCFTreeHasCFTypeCallBacks;
229    } else {
230        newtype = __kCFTreeHasCustomCallBacks;
231        __CFAssignWithWriteBarrier((void **)&tree->_callbacks, _CFAllocatorAllocateGC(allocator, sizeof(struct __CFTreeCallBacks), 0));
232        if (__CFOASafe) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (callbacks)");
233        tree->_callbacks->retain = context->retain;
234        tree->_callbacks->release = context->release;
235        tree->_callbacks->copyDescription = context->copyDescription;
236        FAULT_CALLBACK((void **)&(tree->_callbacks->retain));
237        FAULT_CALLBACK((void **)&(tree->_callbacks->release));
238        FAULT_CALLBACK((void **)&(tree->_callbacks->copyDescription));
239    }
240    __CFBitfieldSetValue(tree->_base._cfinfo[CF_INFO_BITS], 1, 0, newtype);
241    newcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
242    if (NULL != newcb->retain) {
243        tree->_info = (void *)INVOKE_CALLBACK1(newcb->retain, context->info);
244    } else {
245        __CFAssignWithWriteBarrier((void **)&tree->_info, context->info);
246    }
247    if (NULL != oldcb->release) {
248        INVOKE_CALLBACK1(oldcb->release, oldinfo);
249    }
250    if (oldtype == __kCFTreeHasCustomCallBacks) {
251        _CFAllocatorDeallocateGC(allocator, oldcb);
252    }
253}
254
255#if 0
256CFTreeRef CFTreeFindNextSibling(CFTreeRef tree, const void *info) {
257    __CFGenericValidateType(tree, __kCFTreeTypeID);
258    tree = tree->_sibling;
259    while (NULL != tree) {
260	if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
261	    return tree;
262	}
263	tree = tree->_sibling;
264    }
265    return NULL;
266}
267
268CFTreeRef CFTreeFindFirstChild(CFTreeRef tree, const void *info) {
269    __CFGenericValidateType(tree, __kCFTreeTypeID);
270    tree = tree->_child;
271    while (NULL != tree) {
272	if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
273	    return tree;
274	}
275	tree = tree->_sibling;
276    }
277    return NULL;
278}
279
280CFTreeRef CFTreeFind(CFTreeRef tree, const void *info) {
281    __CFGenericValidateType(tree, __kCFTreeTypeID);
282    if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->info))) {
283	return tree;
284    }
285    tree = tree->_child;
286    while (NULL != tree) {
287	CFTreeRef found = CFTreeFind(tree, info);
288	if (NULL != found) {
289	    return found;
290	}
291	tree = tree->_sibling;
292    }
293    return NULL;
294}
295#endif
296
297CFTreeRef CFTreeGetChildAtIndex(CFTreeRef tree, CFIndex idx) {
298    __CFGenericValidateType(tree, __kCFTreeTypeID);
299    tree = tree->_child;
300    while (NULL != tree) {
301	if (0 == idx) return tree;
302	idx--;
303	tree = tree->_sibling;
304    }
305    return NULL;
306}
307
308void CFTreeGetChildren(CFTreeRef tree, CFTreeRef *children) {
309    __CFGenericValidateType(tree, __kCFTreeTypeID);
310    tree = tree->_child;
311    while (NULL != tree) {
312	*children++ = tree;
313	tree = tree->_sibling;
314    }
315}
316
317void CFTreeApplyFunctionToChildren(CFTreeRef tree, CFTreeApplierFunction applier, void *context) {
318    __CFGenericValidateType(tree, __kCFTreeTypeID);
319    CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
320    tree = tree->_child;
321    while (NULL != tree) {
322	applier(tree, context);
323	tree = tree->_sibling;
324    }
325}
326
327void CFTreePrependChild(CFTreeRef tree, CFTreeRef newChild) {
328    __CFGenericValidateType(tree, __kCFTreeTypeID);
329    __CFGenericValidateType(newChild, __kCFTreeTypeID);
330    CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
331    CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
332    if (!kCFUseCollectableAllocator) CFRetain(newChild);
333    __CFAssignWithWriteBarrier((void **)&newChild->_parent, tree);
334    __CFAssignWithWriteBarrier((void **)&newChild->_sibling, tree->_child);
335    if (!tree->_child) {
336        __CFAssignWithWriteBarrier((void **)&tree->_rightmostChild, newChild);
337    }
338    __CFAssignWithWriteBarrier((void **)&tree->_child, newChild);
339}
340
341void CFTreeAppendChild(CFTreeRef tree, CFTreeRef newChild) {
342    CFAllocatorRef allocator;
343    __CFGenericValidateType(tree, __kCFTreeTypeID);
344    __CFGenericValidateType(newChild, __kCFTreeTypeID);
345    CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
346    CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
347    if (newChild->_parent) {
348        HALT;
349    }
350    if (!kCFUseCollectableAllocator) CFRetain(newChild);
351    allocator = CFGetAllocator(tree);
352    __CFAssignWithWriteBarrier((void **)&newChild->_parent, tree);
353    newChild->_sibling = NULL;
354    if (!tree->_child) {
355        __CFAssignWithWriteBarrier((void **)&tree->_child, newChild);
356    } else {
357        __CFAssignWithWriteBarrier((void **)&tree->_rightmostChild->_sibling, newChild);
358    }
359    __CFAssignWithWriteBarrier((void **)&tree->_rightmostChild, newChild);
360}
361
362void CFTreeInsertSibling(CFTreeRef tree, CFTreeRef newSibling) {
363    CFAllocatorRef allocator;
364    __CFGenericValidateType(tree, __kCFTreeTypeID);
365    __CFGenericValidateType(newSibling, __kCFTreeTypeID);
366    CFAssert1(NULL != tree->_parent, __kCFLogAssertion, "%s(): tree must have a parent", __PRETTY_FUNCTION__);
367    CFAssert1(NULL == newSibling->_parent, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
368    CFAssert1(NULL == newSibling->_sibling, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
369    if (!kCFUseCollectableAllocator) CFRetain(newSibling);
370    allocator = CFGetAllocator(tree);
371    __CFAssignWithWriteBarrier((void **)&newSibling->_parent, tree->_parent);
372    __CFAssignWithWriteBarrier((void **)&newSibling->_sibling, tree->_sibling);
373    __CFAssignWithWriteBarrier((void **)&tree->_sibling, newSibling);
374    if (tree->_parent) {
375        if (tree->_parent->_rightmostChild == tree) {
376            __CFAssignWithWriteBarrier((void **)&tree->_parent->_rightmostChild, newSibling);
377        }
378    }
379}
380
381void CFTreeRemove(CFTreeRef tree) {
382    __CFGenericValidateType(tree, __kCFTreeTypeID);
383    if (NULL != tree->_parent) {
384	if (tree == tree->_parent->_child) {
385            __CFAssignWithWriteBarrier((void **)&tree->_parent->_child, tree->_sibling);
386            if (tree->_sibling == NULL) {
387                tree->_parent->_rightmostChild = NULL;
388            }
389	} else {
390	    CFTreeRef prevSibling = NULL;
391	    for (prevSibling = tree->_parent->_child; prevSibling; prevSibling = prevSibling->_sibling) {
392		if (prevSibling->_sibling == tree) {
393                    __CFAssignWithWriteBarrier((void **)&prevSibling->_sibling, tree->_sibling);
394                    if (tree->_parent->_rightmostChild == tree) {
395                        __CFAssignWithWriteBarrier((void **)&tree->_parent->_rightmostChild, prevSibling);
396                    }
397		    break;
398		}
399	    }
400	}
401	tree->_parent = NULL;
402	tree->_sibling = NULL;
403        if (!kCFUseCollectableAllocator) CFRelease(tree);
404    }
405}
406
407void CFTreeRemoveAllChildren(CFTreeRef tree) {
408    CFTreeRef nextChild;
409    __CFGenericValidateType(tree, __kCFTreeTypeID);
410    nextChild = tree->_child;
411    tree->_child = NULL;
412    tree->_rightmostChild = NULL;
413    while (NULL != nextChild) {
414	CFTreeRef nextSibling = nextChild->_sibling;
415	nextChild->_parent = NULL;
416	nextChild->_sibling = NULL;
417        if (!kCFUseCollectableAllocator) CFRelease(nextChild);
418	nextChild = nextSibling;
419    }
420}
421
422struct _tcompareContext {
423    CFComparatorFunction func;
424    void *context;
425};
426
427static CFComparisonResult __CFTreeCompareValues(const void *v1, const void *v2, struct _tcompareContext *context) {
428    const void **val1 = (const void **)v1;
429    const void **val2 = (const void **)v2;
430    return (CFComparisonResult)(INVOKE_CALLBACK3(context->func, *val1, *val2, context->context));
431}
432
433void CFTreeSortChildren(CFTreeRef tree, CFComparatorFunction comparator, void *context) {
434    CFIndex children;
435    __CFGenericValidateType(tree, __kCFTreeTypeID);
436    CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__);
437    children = CFTreeGetChildCount(tree);
438    if (1 < children) {
439        CFIndex idx;
440        CFTreeRef nextChild;
441        struct _tcompareContext ctx;
442        CFTreeRef *list, buffer[128];
443
444        list = (children < 128) ? buffer : (CFTreeRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, children * sizeof(CFTreeRef), 0); // XXX_PCB GC OK
445	if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (temp)");
446        nextChild = tree->_child;
447        for (idx = 0; NULL != nextChild; idx++) {
448            list[idx] = nextChild;
449            nextChild = nextChild->_sibling;
450        }
451
452        ctx.func = comparator;
453        ctx.context = context;
454        CFQSortArray(list, children, sizeof(CFTreeRef), (CFComparatorFunction)__CFTreeCompareValues, &ctx);
455
456        __CFAssignWithWriteBarrier((void **)&tree->_child, list[0]);
457        for (idx = 1; idx < children; idx++) {
458            __CFAssignWithWriteBarrier((void **)&list[idx - 1]->_sibling, list[idx]);
459        }
460        list[idx - 1]->_sibling = NULL;
461        tree->_rightmostChild = list[children - 1];
462        if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list); // XXX_PCB GC OK
463    }
464}
465
466