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