CFTree.c

   1 /*
   2  * Copyright (c) 2015 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-2014, 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 CFTypeID CFTreeGetTypeID(void) {
 140     static dispatch_once_t initOnce;
 141     dispatch_once(&initOnce, ^{ __kCFTreeTypeID = _CFRuntimeRegisterClass(&__CFTreeClass); });
 142     return __kCFTreeTypeID;
 143 }
 144
 145 CFTreeRef CFTreeCreate(CFAllocatorRef allocator, const CFTreeContext *context) {
 146     CFTreeRef memory;
 147     uint32_t size;
 148
 149     CFAssert1(NULL != context, __kCFLogAssertion, "%s(): pointer to context may not be NULL", __PRETTY_FUNCTION__);
 150     CFAssert1(0 == context->version, __kCFLogAssertion, "%s(): context version not initialized to 0", __PRETTY_FUNCTION__);
 151     size = sizeof(struct __CFTree) - sizeof(CFRuntimeBase);
 152     memory = (CFTreeRef)_CFRuntimeCreateInstance(allocator, CFTreeGetTypeID(), size, NULL);
 153     if (NULL == memory) {
 154         return NULL;
 155     }
 156     memory->_parent = NULL;
 157     memory->_sibling = NULL;
 158     memory->_child = NULL;
 159     memory->_rightmostChild = NULL;
 160
 161     /* Start the context off in a recognizable state */
 162     __CFBitfieldSetValue(memory->_base._cfinfo[CF_INFO_BITS], 1, 0, __kCFTreeHasNullCallBacks);
 163     CFTreeSetContext(memory, context);
 164     return memory;
 165 }
 166
 167 CFIndex CFTreeGetChildCount(CFTreeRef tree) {
 168     SInt32 cnt = 0;
 169     __CFGenericValidateType(tree, CFTreeGetTypeID());
 170     tree = tree->_child;
 171     while (NULL != tree) {
 172         cnt++;
 173         tree = tree->_sibling;
 174     }
 175     return cnt;
 176 }
 177
 178 CFTreeRef CFTreeGetParent(CFTreeRef tree) {
 179     __CFGenericValidateType(tree, CFTreeGetTypeID());
 180     return tree->_parent;
 181 }
 182
 183 CFTreeRef CFTreeGetNextSibling(CFTreeRef tree) {
 184     __CFGenericValidateType(tree, CFTreeGetTypeID());
 185     return tree->_sibling;
 186 }
 187
 188 CFTreeRef CFTreeGetFirstChild(CFTreeRef tree) {
 189     __CFGenericValidateType(tree, CFTreeGetTypeID());
 190     return tree->_child;
 191 }
 192
 193 CFTreeRef CFTreeFindRoot(CFTreeRef tree) {
 194     __CFGenericValidateType(tree, CFTreeGetTypeID());
 195     while (NULL != tree->_parent) {
 196         tree = tree->_parent;
 197     }
 198     return tree;
 199 }
 200
 201 void CFTreeGetContext(CFTreeRef tree, CFTreeContext *context) {
 202     const struct __CFTreeCallBacks *cb;
 203     __CFGenericValidateType(tree, CFTreeGetTypeID());
 204     CFAssert1(0 == context->version, __kCFLogAssertion, "%s(): context version not initialized to 0", __PRETTY_FUNCTION__);
 205     cb = __CFTreeGetCallBacks(tree);
 206     context->version = 0;
 207     context->info = tree->_info;
 208     context->retain = cb->retain;
 209     context->release = cb->release;
 210     context->copyDescription = cb->copyDescription;
 211     UNFAULT_CALLBACK(context->retain);
 212     UNFAULT_CALLBACK(context->release);
 213     UNFAULT_CALLBACK(context->copyDescription);
 214 }
 215
 216 void CFTreeSetContext(CFTreeRef tree, const CFTreeContext *context) {
 217     uint32_t newtype, oldtype = __CFTreeGetCallBacksType(tree);
 218     struct __CFTreeCallBacks *oldcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
 219     struct __CFTreeCallBacks *newcb;
 220     void *oldinfo = tree->_info;
 221     CFAllocatorRef allocator = CFGetAllocator(tree);
 222
 223     if (__CFTreeCallBacksMatchNull(context)) {
 224         newtype = __kCFTreeHasNullCallBacks;
 225     } else if (__CFTreeCallBacksMatchCFType(context)) {
 226         newtype = __kCFTreeHasCFTypeCallBacks;
 227     } else {
 228         newtype = __kCFTreeHasCustomCallBacks;
 229         __CFAssignWithWriteBarrier((void **)&tree->_callbacks, _CFAllocatorAllocateGC(allocator, sizeof(struct __CFTreeCallBacks), 0));
 230         if (__CFOASafe) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (callbacks)");
 231         tree->_callbacks->retain = context->retain;
 232         tree->_callbacks->release = context->release;
 233         tree->_callbacks->copyDescription = context->copyDescription;
 234         FAULT_CALLBACK((void **)&(tree->_callbacks->retain));
 235         FAULT_CALLBACK((void **)&(tree->_callbacks->release));
 236         FAULT_CALLBACK((void **)&(tree->_callbacks->copyDescription));
 237     }
 238     __CFBitfieldSetValue(tree->_base._cfinfo[CF_INFO_BITS], 1, 0, newtype);
 239     newcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
 240     if (NULL != newcb->retain) {
 241         tree->_info = (void *)INVOKE_CALLBACK1(newcb->retain, context->info);
 242     } else {
 243         __CFAssignWithWriteBarrier((void **)&tree->_info, context->info);
 244     }
 245     if (NULL != oldcb->release) {
 246         INVOKE_CALLBACK1(oldcb->release, oldinfo);
 247     }
 248     if (oldtype == __kCFTreeHasCustomCallBacks) {
 249         _CFAllocatorDeallocateGC(allocator, oldcb);
 250     }
 251 }
 252
 253 #if 0
 254 CFTreeRef CFTreeFindNextSibling(CFTreeRef tree, const void *info) {
 255     __CFGenericValidateType(tree, CFTreeGetTypeID());
 256     tree = tree->_sibling;
 257     while (NULL != tree) {
 258         if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
 259             return tree;
 260         }
 261         tree = tree->_sibling;
 262     }
 263     return NULL;
 264 }
 265
 266 CFTreeRef CFTreeFindFirstChild(CFTreeRef tree, const void *info) {
 267     __CFGenericValidateType(tree, CFTreeGetTypeID());
 268     tree = tree->_child;
 269     while (NULL != tree) {
 270         if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
 271             return tree;
 272         }
 273         tree = tree->_sibling;
 274     }
 275     return NULL;
 276 }
 277
 278 CFTreeRef CFTreeFind(CFTreeRef tree, const void *info) {
 279     __CFGenericValidateType(tree, CFTreeGetTypeID());
 280     if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->info))) {
 281         return tree;
 282     }
 283     tree = tree->_child;
 284     while (NULL != tree) {
 285         CFTreeRef found = CFTreeFind(tree, info);
 286         if (NULL != found) {
 287             return found;
 288         }
 289         tree = tree->_sibling;
 290     }
 291     return NULL;
 292 }
 293 #endif
 294
 295 CFTreeRef CFTreeGetChildAtIndex(CFTreeRef tree, CFIndex idx) {
 296     __CFGenericValidateType(tree, CFTreeGetTypeID());
 297     tree = tree->_child;
 298     while (NULL != tree) {
 299         if (0 == idx) return tree;
 300         idx--;
 301         tree = tree->_sibling;
 302     }
 303     return NULL;
 304 }
 305
 306 void CFTreeGetChildren(CFTreeRef tree, CFTreeRef *children) {
 307     __CFGenericValidateType(tree, CFTreeGetTypeID());
 308     tree = tree->_child;
 309     while (NULL != tree) {
 310         *children++ = tree;
 311         tree = tree->_sibling;
 312     }
 313 }
 314
 315 void CFTreeApplyFunctionToChildren(CFTreeRef tree, CFTreeApplierFunction applier, void *context) {
 316     __CFGenericValidateType(tree, CFTreeGetTypeID());
 317     CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
 318     tree = tree->_child;
 319     while (NULL != tree) {
 320         applier(tree, context);
 321         tree = tree->_sibling;
 322     }
 323 }
 324
 325 void CFTreePrependChild(CFTreeRef tree, CFTreeRef newChild) {
 326     __CFGenericValidateType(tree, CFTreeGetTypeID());
 327     __CFGenericValidateType(newChild, CFTreeGetTypeID());
 328     CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 329     CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 330     if (!kCFUseCollectableAllocator) CFRetain(newChild);
 331     __CFAssignWithWriteBarrier((void **)&newChild->_parent, tree);
 332     __CFAssignWithWriteBarrier((void **)&newChild->_sibling, tree->_child);
 333     if (!tree->_child) {
 334         __CFAssignWithWriteBarrier((void **)&tree->_rightmostChild, newChild);
 335     }
 336     __CFAssignWithWriteBarrier((void **)&tree->_child, newChild);
 337 }
 338
 339 void CFTreeAppendChild(CFTreeRef tree, CFTreeRef newChild) {
 340     CFAllocatorRef allocator;
 341     __CFGenericValidateType(tree, CFTreeGetTypeID());
 342     __CFGenericValidateType(newChild, CFTreeGetTypeID());
 343     CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 344     CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 345     if (newChild->_parent) {
 346         HALT;
 347     }
 348     if (!kCFUseCollectableAllocator) CFRetain(newChild);
 349     allocator = CFGetAllocator(tree);
 350     __CFAssignWithWriteBarrier((void **)&newChild->_parent, tree);
 351     newChild->_sibling = NULL;
 352     if (!tree->_child) {
 353         __CFAssignWithWriteBarrier((void **)&tree->_child, newChild);
 354     } else {
 355         __CFAssignWithWriteBarrier((void **)&tree->_rightmostChild->_sibling, newChild);
 356     }
 357     __CFAssignWithWriteBarrier((void **)&tree->_rightmostChild, newChild);
 358 }
 359
 360 void CFTreeInsertSibling(CFTreeRef tree, CFTreeRef newSibling) {
 361     CFAllocatorRef allocator;
 362     __CFGenericValidateType(tree, CFTreeGetTypeID());
 363     __CFGenericValidateType(newSibling, CFTreeGetTypeID());
 364     CFAssert1(NULL != tree->_parent, __kCFLogAssertion, "%s(): tree must have a parent", __PRETTY_FUNCTION__);
 365     CFAssert1(NULL == newSibling->_parent, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
 366     CFAssert1(NULL == newSibling->_sibling, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
 367     if (!kCFUseCollectableAllocator) CFRetain(newSibling);
 368     allocator = CFGetAllocator(tree);
 369     __CFAssignWithWriteBarrier((void **)&newSibling->_parent, tree->_parent);
 370     __CFAssignWithWriteBarrier((void **)&newSibling->_sibling, tree->_sibling);
 371     __CFAssignWithWriteBarrier((void **)&tree->_sibling, newSibling);
 372     if (tree->_parent) {
 373         if (tree->_parent->_rightmostChild == tree) {
 374             __CFAssignWithWriteBarrier((void **)&tree->_parent->_rightmostChild, newSibling);
 375         }
 376     }
 377 }
 378
 379 void CFTreeRemove(CFTreeRef tree) {
 380     __CFGenericValidateType(tree, CFTreeGetTypeID());
 381     if (NULL != tree->_parent) {
 382         if (tree == tree->_parent->_child) {
 383             __CFAssignWithWriteBarrier((void **)&tree->_parent->_child, tree->_sibling);
 384             if (tree->_sibling == NULL) {
 385                 tree->_parent->_rightmostChild = NULL;
 386             }
 387         } else {
 388             CFTreeRef prevSibling = NULL;
 389             for (prevSibling = tree->_parent->_child; prevSibling; prevSibling = prevSibling->_sibling) {
 390                 if (prevSibling->_sibling == tree) {
 391                     __CFAssignWithWriteBarrier((void **)&prevSibling->_sibling, tree->_sibling);
 392                     if (tree->_parent->_rightmostChild == tree) {
 393                         __CFAssignWithWriteBarrier((void **)&tree->_parent->_rightmostChild, prevSibling);
 394                     }
 395                     break;
 396                 }
 397             }
 398         }
 399         tree->_parent = NULL;
 400         tree->_sibling = NULL;
 401         if (!kCFUseCollectableAllocator) CFRelease(tree);
 402     }
 403 }
 404
 405 void CFTreeRemoveAllChildren(CFTreeRef tree) {
 406     CFTreeRef nextChild;
 407     __CFGenericValidateType(tree, CFTreeGetTypeID());
 408     nextChild = tree->_child;
 409     tree->_child = NULL;
 410     tree->_rightmostChild = NULL;
 411     while (NULL != nextChild) {
 412         CFTreeRef nextSibling = nextChild->_sibling;
 413         nextChild->_parent = NULL;
 414         nextChild->_sibling = NULL;
 415         if (!kCFUseCollectableAllocator) CFRelease(nextChild);
 416         nextChild = nextSibling;
 417     }
 418 }
 419
 420 struct _tcompareContext {
 421     CFComparatorFunction func;
 422     void *context;
 423 };
 424
 425 static CFComparisonResult __CFTreeCompareValues(const void *v1, const void *v2, struct _tcompareContext *context) {
 426     const void **val1 = (const void **)v1;
 427     const void **val2 = (const void **)v2;
 428     return (CFComparisonResult)(INVOKE_CALLBACK3(context->func, *val1, *val2, context->context));
 429 }
 430
 431 void CFTreeSortChildren(CFTreeRef tree, CFComparatorFunction comparator, void *context) {
 432     CFIndex children;
 433     __CFGenericValidateType(tree, CFTreeGetTypeID());
 434     CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__);
 435     children = CFTreeGetChildCount(tree);
 436     if (1 < children) {
 437         CFIndex idx;
 438         CFTreeRef nextChild;
 439         struct _tcompareContext ctx;
 440         CFTreeRef *list, buffer[128];
 441
 442         list = (children < 128) ? buffer : (CFTreeRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, children * sizeof(CFTreeRef), 0); // XXX_PCB GC OK
 443         if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (temp)");
 444         nextChild = tree->_child;
 445         for (idx = 0; NULL != nextChild; idx++) {
 446             list[idx] = nextChild;
 447             nextChild = nextChild->_sibling;
 448         }
 449
 450         ctx.func = comparator;
 451         ctx.context = context;
 452         CFQSortArray(list, children, sizeof(CFTreeRef), (CFComparatorFunction)__CFTreeCompareValues, &ctx);
 453
 454         __CFAssignWithWriteBarrier((void **)&tree->_child, list[0]);
 455         for (idx = 1; idx < children; idx++) {
 456             __CFAssignWithWriteBarrier((void **)&list[idx - 1]->_sibling, list[idx]);
 457         }
 458         list[idx - 1]->_sibling = NULL;
 459         tree->_rightmostChild = list[children - 1];
 460         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list); // XXX_PCB GC OK
 461     }
 462 }
 463