CFTree.c

   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
  33 struct __CFTreeCallBacks {
  34     CFTreeRetainCallBack                retain;
  35     CFTreeReleaseCallBack               release;
  36     CFTreeCopyDescriptionCallBack       copyDescription;
  37 };
  38
  39 struct __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
  52 static const struct __CFTreeCallBacks __kCFTypeTreeCallBacks = {CFRetain, CFRelease, CFCopyDescription};
  53 static const struct __CFTreeCallBacks __kCFNullTreeCallBacks = {NULL, NULL, NULL};
  54
  55 enum {          /* Bits 0-1 */
  56     __kCFTreeHasNullCallBacks = 0,
  57     __kCFTreeHasCFTypeCallBacks = 1,
  58     __kCFTreeHasCustomCallBacks = 3    /* callbacks pointed to by _callbacks */
  59 };
  60
  61 CF_INLINE uint32_t __CFTreeGetCallBacksType(CFTreeRef tree) {
  62     return (__CFBitfieldGetValue(tree->_base._cfinfo[CF_INFO_BITS], 1, 0));
  63 }
  64
  65 CF_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
  77 CF_INLINE bool __CFTreeCallBacksMatchNull(const CFTreeContext *c) {
  78     return (NULL == c || (c->retain == NULL && c->release == NULL && c->copyDescription == NULL));
  79 }
  80
  81 CF_INLINE bool __CFTreeCallBacksMatchCFType(const CFTreeContext *c) {
  82     return (NULL != c && (c->retain == CFRetain && c->release == CFRelease && c->copyDescription == CFCopyDescription));
  83 }
  84
  85 static 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
 105 static 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
 125 static CFTypeID __kCFTreeTypeID = _kCFRuntimeNotATypeID;
 126
 127 static 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
 139 CF_PRIVATE void __CFTreeInitialize(void) {
 140     __kCFTreeTypeID = _CFRuntimeRegisterClass(&__CFTreeClass);
 141 }
 142
 143 CFTypeID CFTreeGetTypeID(void) {
 144     return __kCFTreeTypeID;
 145 }
 146
 147 CFTreeRef 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
 169 CFIndex 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
 180 CFTreeRef CFTreeGetParent(CFTreeRef tree) {
 181     __CFGenericValidateType(tree, __kCFTreeTypeID);
 182     return tree->_parent;
 183 }
 184
 185 CFTreeRef CFTreeGetNextSibling(CFTreeRef tree) {
 186     __CFGenericValidateType(tree, __kCFTreeTypeID);
 187     return tree->_sibling;
 188 }
 189
 190 CFTreeRef CFTreeGetFirstChild(CFTreeRef tree) {
 191     __CFGenericValidateType(tree, __kCFTreeTypeID);
 192     return tree->_child;
 193 }
 194
 195 CFTreeRef CFTreeFindRoot(CFTreeRef tree) {
 196     __CFGenericValidateType(tree, __kCFTreeTypeID);
 197     while (NULL != tree->_parent) {
 198         tree = tree->_parent;
 199     }
 200     return tree;
 201 }
 202
 203 void 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
 218 void 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
 256 CFTreeRef 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
 268 CFTreeRef 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
 280 CFTreeRef 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
 297 CFTreeRef 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
 308 void 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
 317 void 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
 327 void 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
 341 void 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
 362 void 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
 381 void 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
 407 void 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
 422 struct _tcompareContext {
 423     CFComparatorFunction func;
 424     void *context;
 425 };
 426
 427 static 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
 433 void 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