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

/*
 * Copyright (c) 2005 Apple Computer, 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@
 */
/*	CFTree.c
	Copyright 1998-2002, Apple, Inc. All rights reserved.
	Responsibility: Christopher Kane
*/

#include <CoreFoundation/CFTree.h>
#include "CFInternal.h"
#include "CFUtilitiesPriv.h"

struct __CFTreeCallBacks {
    CFTreeRetainCallBack		retain;
    CFTreeReleaseCallBack		release;	
    CFTreeCopyDescriptionCallBack	copyDescription;
};

struct __CFTree {
    CFRuntimeBase _base;
    CFTreeRef _parent;	/* Not retained */
    CFTreeRef _sibling;	/* Not retained */
    CFTreeRef _child;	/* All children get a retain from the parent */
    CFTreeRef _rightmostChild;	/* Not retained */
    /* This is the context, exploded.
     * Currently the only valid version is 0, so we do not store that.
     * _callbacks initialized if not a special form. */
    void *_info;
    struct __CFTreeCallBacks *_callbacks;
};

static const struct __CFTreeCallBacks __kCFTypeTreeCallBacks = {CFRetain, CFRelease, CFCopyDescription};
static const struct __CFTreeCallBacks __kCFNullTreeCallBacks = {NULL, NULL, NULL};

enum {          /* Bits 0-1 */
    __kCFTreeHasNullCallBacks = 0,
    __kCFTreeHasCFTypeCallBacks = 1,
    __kCFTreeHasCustomCallBacks = 3    /* callbacks pointed to by _callbacks */
};

CF_INLINE uint32_t __CFTreeGetCallBacksType(CFTreeRef tree) {
    return (__CFBitfieldGetValue(tree->_base._info, 1, 0));
}

CF_INLINE const struct __CFTreeCallBacks *__CFTreeGetCallBacks(CFTreeRef tree) {
    switch (__CFTreeGetCallBacksType(tree)) {
    case __kCFTreeHasNullCallBacks:
	return &__kCFNullTreeCallBacks;
    case __kCFTreeHasCFTypeCallBacks:
	return &__kCFTypeTreeCallBacks;
    case __kCFTreeHasCustomCallBacks:
	break;
    }
    return tree->_callbacks;
}

CF_INLINE bool __CFTreeCallBacksMatchNull(const CFTreeContext *c) {
    return (NULL == c || (c->retain == NULL && c->release == NULL && c->copyDescription == NULL));
}   

CF_INLINE bool __CFTreeCallBacksMatchCFType(const CFTreeContext *c) {
    return (NULL != c && (c->retain == CFRetain && c->release == CFRelease && c->copyDescription == CFCopyDescription));
}   

static CFStringRef __CFTreeCopyDescription(CFTypeRef cf) {
    CFTreeRef tree = (CFTreeRef)cf;
    CFMutableStringRef result;
    CFStringRef contextDesc = NULL;
    Boolean safeToReleaseContextDesc = true;
    const struct __CFTreeCallBacks *cb;
    CFAllocatorRef allocator;
    allocator = CFGetAllocator(tree);
    result = CFStringCreateMutable(allocator, 0);
    cb = __CFTreeGetCallBacks(tree);
    if (NULL != cb->copyDescription) {
	contextDesc = (CFStringRef)INVOKE_CALLBACK1(cb->copyDescription, tree->_info);
	safeToReleaseContextDesc = _CFExecutableLinkedOnOrAfter(CFSystemVersionTiger);    // Because it came from elsewhere, only free it compatibly (3593254)
    }
    if (NULL == contextDesc) {
	contextDesc = CFStringCreateWithFormat(allocator, NULL, CFSTR("<CFTree context %p>"), tree->_info);
    }
    CFStringAppendFormat(result, NULL, CFSTR("<CFTree %p [%p]>{children = %u, context = %@}"), cf, allocator, CFTreeGetChildCount(tree), contextDesc);
    if (contextDesc && safeToReleaseContextDesc) CFRelease(contextDesc);
    return result;
}

static void __CFTreeDeallocate(CFTypeRef cf) {
    CFTreeRef tree = (CFTreeRef)cf;
    const struct __CFTreeCallBacks *cb;
    CFAllocatorRef allocator = __CFGetAllocator(tree);
    if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
        // GC:  keep the tree intact during finalization.
        CFTreeRemoveAllChildren(tree);
    }
    cb = __CFTreeGetCallBacks(tree);
    if (NULL != cb->release) {
        INVOKE_CALLBACK1(cb->release, tree->_info);
    }
    if (__kCFTreeHasCustomCallBacks == __CFTreeGetCallBacksType(tree)) {
        _CFAllocatorDeallocateGC(CFGetAllocator(tree), tree->_callbacks);
    }
}


static CFTypeID __kCFTreeTypeID = _kCFRuntimeNotATypeID;

static const CFRuntimeClass __CFTreeClass = {
    _kCFRuntimeScannedObject,
    "CFTree",
    NULL,	// init
    NULL,	// copy
    __CFTreeDeallocate,
    NULL,	// equal
    NULL,	// hash
    NULL,	// 
    __CFTreeCopyDescription
};

__private_extern__ void __CFTreeInitialize(void) {
    __kCFTreeTypeID = _CFRuntimeRegisterClass(&__CFTreeClass);
}

CFTypeID CFTreeGetTypeID(void) {
    return __kCFTreeTypeID;
}

CFTreeRef CFTreeCreate(CFAllocatorRef allocator, const CFTreeContext *context) {
    CFTreeRef memory;
    uint32_t size;

    CFAssert1(NULL != context, __kCFLogAssertion, "%s(): pointer to context may not be NULL", __PRETTY_FUNCTION__);
    CFAssert1(0 == context->version, __kCFLogAssertion, "%s(): context version not initialized to 0", __PRETTY_FUNCTION__);
    size = sizeof(struct __CFTree) - sizeof(CFRuntimeBase);
    memory = (CFTreeRef)_CFRuntimeCreateInstance(allocator, __kCFTreeTypeID, size, NULL);
    if (NULL == memory) {
	return NULL;
    }
    memory->_parent = NULL;
    memory->_sibling = NULL;
    memory->_child = NULL;
    memory->_rightmostChild = NULL;

    /* Start the context off in a recognizable state */
    __CFBitfieldSetValue(memory->_base._info, 1, 0, __kCFTreeHasNullCallBacks);
    CFTreeSetContext(memory, context);
    return memory;
}

CFIndex CFTreeGetChildCount(CFTreeRef tree) {
    SInt32 cnt = 0;
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    tree = tree->_child;
    while (NULL != tree) {
	cnt++;
	tree = tree->_sibling;
    }
    return cnt;
}

CFTreeRef CFTreeGetParent(CFTreeRef tree) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    return tree->_parent;
}

CFTreeRef CFTreeGetNextSibling(CFTreeRef tree) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    return tree->_sibling;
}

CFTreeRef CFTreeGetFirstChild(CFTreeRef tree) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    return tree->_child;
}

CFTreeRef CFTreeFindRoot(CFTreeRef tree) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    while (NULL != tree->_parent) {
	tree = tree->_parent;
    }
    return tree;
}

void CFTreeGetContext(CFTreeRef tree, CFTreeContext *context) {
    const struct __CFTreeCallBacks *cb;
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    CFAssert1(0 == context->version, __kCFLogAssertion, "%s(): context version not initialized to 0", __PRETTY_FUNCTION__);
    cb = __CFTreeGetCallBacks(tree);
    context->version = 0;
    context->info = tree->_info;
#if defined(__ppc__)
    context->retain = (void *)((uintptr_t)cb->retain & ~0x3);
    context->release = (void *)((uintptr_t)cb->release & ~0x3);
    context->copyDescription = (void *)((uintptr_t)cb->copyDescription & ~0x3);
#else
    context->retain = cb->retain;
    context->release = cb->release;
    context->copyDescription = cb->copyDescription;
#endif
}

void CFTreeSetContext(CFTreeRef tree, const CFTreeContext *context) {
    uint32_t newtype, oldtype = __CFTreeGetCallBacksType(tree);
    struct __CFTreeCallBacks *oldcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
    struct __CFTreeCallBacks *newcb;
    void *oldinfo = tree->_info;
    CFAllocatorRef allocator = CFGetAllocator(tree);
    
    if (__CFTreeCallBacksMatchNull(context)) {
        newtype = __kCFTreeHasNullCallBacks;
    } else if (__CFTreeCallBacksMatchCFType(context)) {
        newtype = __kCFTreeHasCFTypeCallBacks;
    } else {
        newtype = __kCFTreeHasCustomCallBacks;
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_callbacks, _CFAllocatorAllocateGC(allocator, sizeof(struct __CFTreeCallBacks), 0));
        if (__CFOASafe) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (callbacks)");
        tree->_callbacks->retain = context->retain;
        tree->_callbacks->release = context->release;
        tree->_callbacks->copyDescription = context->copyDescription;
        FAULT_CALLBACK((void **)&(tree->_callbacks->retain));
        FAULT_CALLBACK((void **)&(tree->_callbacks->release));
        FAULT_CALLBACK((void **)&(tree->_callbacks->copyDescription));
    }
    __CFBitfieldSetValue(tree->_base._info, 1, 0, newtype);
    newcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
    if (NULL != newcb->retain) {
        tree->_info = (void *)INVOKE_CALLBACK1(newcb->retain, context->info);
    } else {
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_info, context->info);
    }
    if (NULL != oldcb->release) {
        INVOKE_CALLBACK1(oldcb->release, oldinfo);
    }
    if (oldtype == __kCFTreeHasCustomCallBacks) {
        _CFAllocatorDeallocateGC(allocator, oldcb);
    }
}

#if 0
CFTreeRef CFTreeFindNextSibling(CFTreeRef tree, const void *info) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    tree = tree->_sibling;
    while (NULL != tree) {
	if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
	    return tree;
	}
	tree = tree->_sibling;
    }
    return NULL;
}

CFTreeRef CFTreeFindFirstChild(CFTreeRef tree, const void *info) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    tree = tree->_child;
    while (NULL != tree) {
	if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
	    return tree;
	}
	tree = tree->_sibling;
    }
    return NULL;
}

CFTreeRef CFTreeFind(CFTreeRef tree, const void *info) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->info))) {
	return tree;
    }
    tree = tree->_child;
    while (NULL != tree) {
	CFTreeRef found = CFTreeFind(tree, info);
	if (NULL != found) {
	    return found;
	}
	tree = tree->_sibling;
    }
    return NULL;
}
#endif

CFTreeRef CFTreeGetChildAtIndex(CFTreeRef tree, CFIndex idx) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    tree = tree->_child;
    while (NULL != tree) {
	if (0 == idx) return tree;
	idx--;
	tree = tree->_sibling;
    }
    return NULL;
}

void CFTreeGetChildren(CFTreeRef tree, CFTreeRef *children) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    tree = tree->_child;
    while (NULL != tree) {
	*children++ = tree;
	tree = tree->_sibling;
    }
}

void CFTreeApplyFunctionToChildren(CFTreeRef tree, CFTreeApplierFunction applier, void *context) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
    tree = tree->_child;
    while (NULL != tree) {
	applier(tree, context);
	tree = tree->_sibling;
    }
}

void CFTreePrependChild(CFTreeRef tree, CFTreeRef newChild) {
    CFAllocatorRef allocator = CFGetAllocator(tree);
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    __CFGenericValidateType(newChild, __kCFTreeTypeID);
    CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
    CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
    _CFRetainGC(newChild);
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newChild, newChild->_parent, tree);
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newChild, newChild->_sibling, tree->_child);
    if (!tree->_child) {
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_rightmostChild, newChild);
    }
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_child, newChild);
}

void CFTreeAppendChild(CFTreeRef tree, CFTreeRef newChild) {
    CFAllocatorRef allocator;
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    __CFGenericValidateType(newChild, __kCFTreeTypeID);
    CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
    CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
    if (newChild->_parent) {
        HALT;
    }
    _CFRetainGC(newChild);
    allocator = CFGetAllocator(tree);
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newChild, newChild->_parent, tree);
    newChild->_sibling = NULL;
    if (!tree->_child) {
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_child, newChild);
    } else {
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_rightmostChild, tree->_rightmostChild->_sibling, newChild);
    }
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_rightmostChild, newChild);
}

void CFTreeInsertSibling(CFTreeRef tree, CFTreeRef newSibling) {
    CFAllocatorRef allocator;
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    __CFGenericValidateType(newSibling, __kCFTreeTypeID);
    CFAssert1(NULL != tree->_parent, __kCFLogAssertion, "%s(): tree must have a parent", __PRETTY_FUNCTION__);
    CFAssert1(NULL == newSibling->_parent, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
    CFAssert1(NULL == newSibling->_sibling, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
    _CFRetainGC(newSibling);
    allocator = CFGetAllocator(tree);
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newSibling, newSibling->_parent, tree->_parent);
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newSibling, newSibling->_sibling, tree->_sibling);
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_sibling, newSibling);
    if (tree->_parent) {
        if (tree->_parent->_rightmostChild == tree) {
            CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_parent, tree->_parent->_rightmostChild, newSibling);
        }
    }
}

void CFTreeRemove(CFTreeRef tree) {
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    if (NULL != tree->_parent) {
        CFAllocatorRef allocator = CFGetAllocator(tree);
	if (tree == tree->_parent->_child) {
            CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_parent, tree->_parent->_child, tree->_sibling);
            if (tree->_sibling == NULL) {
                tree->_parent->_rightmostChild = NULL;
            }
	} else {
	    CFTreeRef prevSibling = NULL;
	    for (prevSibling = tree->_parent->_child; prevSibling; prevSibling = prevSibling->_sibling) {
		if (prevSibling->_sibling == tree) {
                    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, prevSibling, prevSibling->_sibling, tree->_sibling);
                    if (tree->_parent->_rightmostChild == tree) {
                        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_parent, tree->_parent->_rightmostChild, prevSibling);
                    }
		    break;
		}
	    }
	}
	tree->_parent = NULL;
	tree->_sibling = NULL;
        _CFReleaseGC(tree);
    }
}

void CFTreeRemoveAllChildren(CFTreeRef tree) {
    CFTreeRef nextChild;
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    nextChild = tree->_child;
    tree->_child = NULL;
    tree->_rightmostChild = NULL;
    while (NULL != nextChild) {
	CFTreeRef nextSibling = nextChild->_sibling;
	nextChild->_parent = NULL;
	nextChild->_sibling = NULL;
	_CFReleaseGC(nextChild);
	nextChild = nextSibling;
    }
}

struct _tcompareContext {
    CFComparatorFunction func;
    void *context;
};

static CFComparisonResult __CFTreeCompareValues(const void *v1, const void *v2, struct _tcompareContext *context) {
    const void **val1 = (const void **)v1;
    const void **val2 = (const void **)v2;
    return (CFComparisonResult)(INVOKE_CALLBACK3(context->func, *val1, *val2, context->context));
}

void CFTreeSortChildren(CFTreeRef tree, CFComparatorFunction comparator, void *context) {
    CFIndex children;
    __CFGenericValidateType(tree, __kCFTreeTypeID);
    CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__);
    children = CFTreeGetChildCount(tree);
    if (1 < children) {
        CFIndex idx;
        CFTreeRef nextChild;
        struct _tcompareContext ctx;
        CFTreeRef *list, buffer[128];
        CFAllocatorRef allocator = __CFGetAllocator(tree);

        list = (children < 128) ? buffer : CFAllocatorAllocate(kCFAllocatorDefault, children * sizeof(CFTreeRef), 0); // XXX_PCB GC OK
	if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (temp)");
        nextChild = tree->_child;
        for (idx = 0; NULL != nextChild; idx++) {
            list[idx] = nextChild;
            nextChild = nextChild->_sibling;
        }

        ctx.func = comparator;
        ctx.context = context;
        CFQSortArray(list, children, sizeof(CFTreeRef), (CFComparatorFunction)__CFTreeCompareValues, &ctx);

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