CFTree.c

   1 /*
   2  * Copyright (c) 2008 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 /*      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"
  30 #include "CFPriv.h"
  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 */
  43     CFTreeRef _rightmostChild;  /* Not retained */
  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._cfinfo[CF_INFO_BITS], 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;
  88     Boolean safeToReleaseContextDesc = true;
  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         safeToReleaseContextDesc = _CFExecutableLinkedOnOrAfter(CFSystemVersionTiger);    // Because it came from elsewhere, only free it compatibly (3593254)
  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);
 102     if (contextDesc && safeToReleaseContextDesc) CFRelease(contextDesc);
 103     return result;
 104 }
 105
 106 static void __CFTreeDeallocate(CFTypeRef cf) {
 107     CFTreeRef tree = (CFTreeRef)cf;
 108     const struct __CFTreeCallBacks *cb;
 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     cb = __CFTreeGetCallBacks(tree);
 115     if (NULL != cb->release) {
 116         INVOKE_CALLBACK1(cb->release, tree->_info);
 117     }
 118     if (__kCFTreeHasCustomCallBacks == __CFTreeGetCallBacksType(tree)) {
 119         _CFAllocatorDeallocateGC(CFGetAllocator(tree), tree->_callbacks);
 120     }
 121 }
 122
 123
 124 static CFTypeID __kCFTreeTypeID = _kCFRuntimeNotATypeID;
 125
 126 static const CFRuntimeClass __CFTreeClass = {
 127     _kCFRuntimeScannedObject,
 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;
 160     memory->_rightmostChild = NULL;
 161
 162     /* Start the context off in a recognizable state */
 163     __CFBitfieldSetValue(memory->_base._cfinfo[CF_INFO_BITS], 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     context->retain = cb->retain;
 210     context->release = cb->release;
 211     context->copyDescription = cb->copyDescription;
 212     UNFAULT_CALLBACK(context->retain);
 213     UNFAULT_CALLBACK(context->release);
 214     UNFAULT_CALLBACK(context->copyDescription);
 215 }
 216
 217 void CFTreeSetContext(CFTreeRef tree, const CFTreeContext *context) {
 218     uint32_t newtype, oldtype = __CFTreeGetCallBacksType(tree);
 219     struct __CFTreeCallBacks *oldcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
 220     struct __CFTreeCallBacks *newcb;
 221     void *oldinfo = tree->_info;
 222     CFAllocatorRef allocator = CFGetAllocator(tree);
 223
 224     if (__CFTreeCallBacksMatchNull(context)) {
 225         newtype = __kCFTreeHasNullCallBacks;
 226     } else if (__CFTreeCallBacksMatchCFType(context)) {
 227         newtype = __kCFTreeHasCFTypeCallBacks;
 228     } else {
 229         newtype = __kCFTreeHasCustomCallBacks;
 230         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_callbacks, _CFAllocatorAllocateGC(allocator, sizeof(struct __CFTreeCallBacks), 0));
 231         if (__CFOASafe) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (callbacks)");
 232         tree->_callbacks->retain = context->retain;
 233         tree->_callbacks->release = context->release;
 234         tree->_callbacks->copyDescription = context->copyDescription;
 235         FAULT_CALLBACK((void **)&(tree->_callbacks->retain));
 236         FAULT_CALLBACK((void **)&(tree->_callbacks->release));
 237         FAULT_CALLBACK((void **)&(tree->_callbacks->copyDescription));
 238     }
 239     __CFBitfieldSetValue(tree->_base._cfinfo[CF_INFO_BITS], 1, 0, newtype);
 240     newcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
 241     if (NULL != newcb->retain) {
 242         tree->_info = (void *)INVOKE_CALLBACK1(newcb->retain, context->info);
 243     } else {
 244         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_info, context->info);
 245     }
 246     if (NULL != oldcb->release) {
 247         INVOKE_CALLBACK1(oldcb->release, oldinfo);
 248     }
 249     if (oldtype == __kCFTreeHasCustomCallBacks) {
 250         _CFAllocatorDeallocateGC(allocator, oldcb);
 251     }
 252 }
 253
 254 #if 0
 255 CFTreeRef CFTreeFindNextSibling(CFTreeRef tree, const void *info) {
 256     __CFGenericValidateType(tree, __kCFTreeTypeID);
 257     tree = tree->_sibling;
 258     while (NULL != tree) {
 259         if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
 260             return tree;
 261         }
 262         tree = tree->_sibling;
 263     }
 264     return NULL;
 265 }
 266
 267 CFTreeRef CFTreeFindFirstChild(CFTreeRef tree, const void *info) {
 268     __CFGenericValidateType(tree, __kCFTreeTypeID);
 269     tree = tree->_child;
 270     while (NULL != tree) {
 271         if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
 272             return tree;
 273         }
 274         tree = tree->_sibling;
 275     }
 276     return NULL;
 277 }
 278
 279 CFTreeRef CFTreeFind(CFTreeRef tree, const void *info) {
 280     __CFGenericValidateType(tree, __kCFTreeTypeID);
 281     if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->info))) {
 282         return tree;
 283     }
 284     tree = tree->_child;
 285     while (NULL != tree) {
 286         CFTreeRef found = CFTreeFind(tree, info);
 287         if (NULL != found) {
 288             return found;
 289         }
 290         tree = tree->_sibling;
 291     }
 292     return NULL;
 293 }
 294 #endif
 295
 296 CFTreeRef CFTreeGetChildAtIndex(CFTreeRef tree, CFIndex idx) {
 297     __CFGenericValidateType(tree, __kCFTreeTypeID);
 298     tree = tree->_child;
 299     while (NULL != tree) {
 300         if (0 == idx) return tree;
 301         idx--;
 302         tree = tree->_sibling;
 303     }
 304     return NULL;
 305 }
 306
 307 void CFTreeGetChildren(CFTreeRef tree, CFTreeRef *children) {
 308     __CFGenericValidateType(tree, __kCFTreeTypeID);
 309     tree = tree->_child;
 310     while (NULL != tree) {
 311         *children++ = tree;
 312         tree = tree->_sibling;
 313     }
 314 }
 315
 316 void CFTreeApplyFunctionToChildren(CFTreeRef tree, CFTreeApplierFunction applier, void *context) {
 317     __CFGenericValidateType(tree, __kCFTreeTypeID);
 318     CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
 319     tree = tree->_child;
 320     while (NULL != tree) {
 321         applier(tree, context);
 322         tree = tree->_sibling;
 323     }
 324 }
 325
 326 void CFTreePrependChild(CFTreeRef tree, CFTreeRef newChild) {
 327     CFAllocatorRef allocator = CFGetAllocator(tree);
 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     _CFRetainGC(newChild);
 333     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newChild, newChild->_parent, tree);
 334     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newChild, newChild->_sibling, tree->_child);
 335     if (!tree->_child) {
 336         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_rightmostChild, newChild);
 337     }
 338     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, 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     _CFRetainGC(newChild);
 351     allocator = CFGetAllocator(tree);
 352     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newChild, newChild->_parent, tree);
 353     newChild->_sibling = NULL;
 354     if (!tree->_child) {
 355         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_child, newChild);
 356     } else {
 357         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_rightmostChild, tree->_rightmostChild->_sibling, newChild);
 358     }
 359     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, 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     _CFRetainGC(newSibling);
 370     allocator = CFGetAllocator(tree);
 371     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newSibling, newSibling->_parent, tree->_parent);
 372     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newSibling, newSibling->_sibling, tree->_sibling);
 373     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_sibling, newSibling);
 374     if (tree->_parent) {
 375         if (tree->_parent->_rightmostChild == tree) {
 376             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_parent, tree->_parent->_rightmostChild, newSibling);
 377         }
 378     }
 379 }
 380
 381 void CFTreeRemove(CFTreeRef tree) {
 382     __CFGenericValidateType(tree, __kCFTreeTypeID);
 383     if (NULL != tree->_parent) {
 384         CFAllocatorRef allocator = CFGetAllocator(tree);
 385         if (tree == tree->_parent->_child) {
 386             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_parent, tree->_parent->_child, tree->_sibling);
 387             if (tree->_sibling == NULL) {
 388                 tree->_parent->_rightmostChild = NULL;
 389             }
 390         } else {
 391             CFTreeRef prevSibling = NULL;
 392             for (prevSibling = tree->_parent->_child; prevSibling; prevSibling = prevSibling->_sibling) {
 393                 if (prevSibling->_sibling == tree) {
 394                     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, prevSibling, prevSibling->_sibling, tree->_sibling);
 395                     if (tree->_parent->_rightmostChild == tree) {
 396                         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_parent, tree->_parent->_rightmostChild, prevSibling);
 397                     }
 398                     break;
 399                 }
 400             }
 401         }
 402         tree->_parent = NULL;
 403         tree->_sibling = NULL;
 404         _CFReleaseGC(tree);
 405     }
 406 }
 407
 408 void CFTreeRemoveAllChildren(CFTreeRef tree) {
 409     CFTreeRef nextChild;
 410     __CFGenericValidateType(tree, __kCFTreeTypeID);
 411     nextChild = tree->_child;
 412     tree->_child = NULL;
 413     tree->_rightmostChild = NULL;
 414     while (NULL != nextChild) {
 415         CFTreeRef nextSibling = nextChild->_sibling;
 416         nextChild->_parent = NULL;
 417         nextChild->_sibling = NULL;
 418         _CFReleaseGC(nextChild);
 419         nextChild = nextSibling;
 420     }
 421 }
 422
 423 struct _tcompareContext {
 424     CFComparatorFunction func;
 425     void *context;
 426 };
 427
 428 static CFComparisonResult __CFTreeCompareValues(const void *v1, const void *v2, struct _tcompareContext *context) {
 429     const void **val1 = (const void **)v1;
 430     const void **val2 = (const void **)v2;
 431     return (CFComparisonResult)(INVOKE_CALLBACK3(context->func, *val1, *val2, context->context));
 432 }
 433
 434 void CFTreeSortChildren(CFTreeRef tree, CFComparatorFunction comparator, void *context) {
 435     CFIndex children;
 436     __CFGenericValidateType(tree, __kCFTreeTypeID);
 437     CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__);
 438     children = CFTreeGetChildCount(tree);
 439     if (1 < children) {
 440         CFIndex idx;
 441         CFTreeRef nextChild;
 442         struct _tcompareContext ctx;
 443         CFTreeRef *list, buffer[128];
 444         CFAllocatorRef allocator = __CFGetAllocator(tree);
 445
 446         list = (children < 128) ? buffer : (CFTreeRef *)CFAllocatorAllocate(kCFAllocatorSystemDefault, children * sizeof(CFTreeRef), 0); // XXX_PCB GC OK
 447         if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (temp)");
 448         nextChild = tree->_child;
 449         for (idx = 0; NULL != nextChild; idx++) {
 450             list[idx] = nextChild;
 451             nextChild = nextChild->_sibling;
 452         }
 453
 454         ctx.func = comparator;
 455         ctx.context = context;
 456         CFQSortArray(list, children, sizeof(CFTreeRef), (CFComparatorFunction)__CFTreeCompareValues, &ctx);
 457
 458         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_child, list[0]);
 459         for (idx = 1; idx < children; idx++) {
 460             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, list[idx - 1], list[idx - 1]->_sibling, list[idx]);
 461         }
 462         list[idx - 1]->_sibling = NULL;
 463         tree->_rightmostChild = list[children - 1];
 464         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, list); // XXX_PCB GC OK
 465     }
 466 }
 467