+++ /dev/null
-/*
- * 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
- }
-}
-
projects / apple / cf.git / blobdiff