Collections.subproj/CFTree.c

   1 /*
   2  * Copyright (c) 2005 Apple Computer, 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 "CFUtilitiesPriv.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._info, 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._info, 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 #if defined(__ppc__)
 210     context->retain = (void *)((uintptr_t)cb->retain & ~0x3);
 211     context->release = (void *)((uintptr_t)cb->release & ~0x3);
 212     context->copyDescription = (void *)((uintptr_t)cb->copyDescription & ~0x3);
 213 #else
 214     context->retain = cb->retain;
 215     context->release = cb->release;
 216     context->copyDescription = cb->copyDescription;
 217 #endif
 218 }
 219
 220 void CFTreeSetContext(CFTreeRef tree, const CFTreeContext *context) {
 221     uint32_t newtype, oldtype = __CFTreeGetCallBacksType(tree);
 222     struct __CFTreeCallBacks *oldcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
 223     struct __CFTreeCallBacks *newcb;
 224     void *oldinfo = tree->_info;
 225     CFAllocatorRef allocator = CFGetAllocator(tree);
 226
 227     if (__CFTreeCallBacksMatchNull(context)) {
 228         newtype = __kCFTreeHasNullCallBacks;
 229     } else if (__CFTreeCallBacksMatchCFType(context)) {
 230         newtype = __kCFTreeHasCFTypeCallBacks;
 231     } else {
 232         newtype = __kCFTreeHasCustomCallBacks;
 233         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_callbacks, _CFAllocatorAllocateGC(allocator, sizeof(struct __CFTreeCallBacks), 0));
 234         if (__CFOASafe) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (callbacks)");
 235         tree->_callbacks->retain = context->retain;
 236         tree->_callbacks->release = context->release;
 237         tree->_callbacks->copyDescription = context->copyDescription;
 238         FAULT_CALLBACK((void **)&(tree->_callbacks->retain));
 239         FAULT_CALLBACK((void **)&(tree->_callbacks->release));
 240         FAULT_CALLBACK((void **)&(tree->_callbacks->copyDescription));
 241     }
 242     __CFBitfieldSetValue(tree->_base._info, 1, 0, newtype);
 243     newcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
 244     if (NULL != newcb->retain) {
 245         tree->_info = (void *)INVOKE_CALLBACK1(newcb->retain, context->info);
 246     } else {
 247         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_info, context->info);
 248     }
 249     if (NULL != oldcb->release) {
 250         INVOKE_CALLBACK1(oldcb->release, oldinfo);
 251     }
 252     if (oldtype == __kCFTreeHasCustomCallBacks) {
 253         _CFAllocatorDeallocateGC(allocator, oldcb);
 254     }
 255 }
 256
 257 #if 0
 258 CFTreeRef CFTreeFindNextSibling(CFTreeRef tree, const void *info) {
 259     __CFGenericValidateType(tree, __kCFTreeTypeID);
 260     tree = tree->_sibling;
 261     while (NULL != tree) {
 262         if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
 263             return tree;
 264         }
 265         tree = tree->_sibling;
 266     }
 267     return NULL;
 268 }
 269
 270 CFTreeRef CFTreeFindFirstChild(CFTreeRef tree, const void *info) {
 271     __CFGenericValidateType(tree, __kCFTreeTypeID);
 272     tree = tree->_child;
 273     while (NULL != tree) {
 274         if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
 275             return tree;
 276         }
 277         tree = tree->_sibling;
 278     }
 279     return NULL;
 280 }
 281
 282 CFTreeRef CFTreeFind(CFTreeRef tree, const void *info) {
 283     __CFGenericValidateType(tree, __kCFTreeTypeID);
 284     if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->info))) {
 285         return tree;
 286     }
 287     tree = tree->_child;
 288     while (NULL != tree) {
 289         CFTreeRef found = CFTreeFind(tree, info);
 290         if (NULL != found) {
 291             return found;
 292         }
 293         tree = tree->_sibling;
 294     }
 295     return NULL;
 296 }
 297 #endif
 298
 299 CFTreeRef CFTreeGetChildAtIndex(CFTreeRef tree, CFIndex idx) {
 300     __CFGenericValidateType(tree, __kCFTreeTypeID);
 301     tree = tree->_child;
 302     while (NULL != tree) {
 303         if (0 == idx) return tree;
 304         idx--;
 305         tree = tree->_sibling;
 306     }
 307     return NULL;
 308 }
 309
 310 void CFTreeGetChildren(CFTreeRef tree, CFTreeRef *children) {
 311     __CFGenericValidateType(tree, __kCFTreeTypeID);
 312     tree = tree->_child;
 313     while (NULL != tree) {
 314         *children++ = tree;
 315         tree = tree->_sibling;
 316     }
 317 }
 318
 319 void CFTreeApplyFunctionToChildren(CFTreeRef tree, CFTreeApplierFunction applier, void *context) {
 320     __CFGenericValidateType(tree, __kCFTreeTypeID);
 321     CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
 322     tree = tree->_child;
 323     while (NULL != tree) {
 324         applier(tree, context);
 325         tree = tree->_sibling;
 326     }
 327 }
 328
 329 void CFTreePrependChild(CFTreeRef tree, CFTreeRef newChild) {
 330     CFAllocatorRef allocator = CFGetAllocator(tree);
 331     __CFGenericValidateType(tree, __kCFTreeTypeID);
 332     __CFGenericValidateType(newChild, __kCFTreeTypeID);
 333     CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 334     CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 335     _CFRetainGC(newChild);
 336     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newChild, newChild->_parent, tree);
 337     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newChild, newChild->_sibling, tree->_child);
 338     if (!tree->_child) {
 339         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_rightmostChild, newChild);
 340     }
 341     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_child, newChild);
 342 }
 343
 344 void CFTreeAppendChild(CFTreeRef tree, CFTreeRef newChild) {
 345     CFAllocatorRef allocator;
 346     __CFGenericValidateType(tree, __kCFTreeTypeID);
 347     __CFGenericValidateType(newChild, __kCFTreeTypeID);
 348     CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 349     CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 350     if (newChild->_parent) {
 351         HALT;
 352     }
 353     _CFRetainGC(newChild);
 354     allocator = CFGetAllocator(tree);
 355     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newChild, newChild->_parent, tree);
 356     newChild->_sibling = NULL;
 357     if (!tree->_child) {
 358         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_child, newChild);
 359     } else {
 360         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_rightmostChild, tree->_rightmostChild->_sibling, newChild);
 361     }
 362     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_rightmostChild, newChild);
 363 }
 364
 365 void CFTreeInsertSibling(CFTreeRef tree, CFTreeRef newSibling) {
 366     CFAllocatorRef allocator;
 367     __CFGenericValidateType(tree, __kCFTreeTypeID);
 368     __CFGenericValidateType(newSibling, __kCFTreeTypeID);
 369     CFAssert1(NULL != tree->_parent, __kCFLogAssertion, "%s(): tree must have a parent", __PRETTY_FUNCTION__);
 370     CFAssert1(NULL == newSibling->_parent, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
 371     CFAssert1(NULL == newSibling->_sibling, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
 372     _CFRetainGC(newSibling);
 373     allocator = CFGetAllocator(tree);
 374     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newSibling, newSibling->_parent, tree->_parent);
 375     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, newSibling, newSibling->_sibling, tree->_sibling);
 376     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_sibling, newSibling);
 377     if (tree->_parent) {
 378         if (tree->_parent->_rightmostChild == tree) {
 379             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_parent, tree->_parent->_rightmostChild, newSibling);
 380         }
 381     }
 382 }
 383
 384 void CFTreeRemove(CFTreeRef tree) {
 385     __CFGenericValidateType(tree, __kCFTreeTypeID);
 386     if (NULL != tree->_parent) {
 387         CFAllocatorRef allocator = CFGetAllocator(tree);
 388         if (tree == tree->_parent->_child) {
 389             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_parent, tree->_parent->_child, tree->_sibling);
 390             if (tree->_sibling == NULL) {
 391                 tree->_parent->_rightmostChild = NULL;
 392             }
 393         } else {
 394             CFTreeRef prevSibling = NULL;
 395             for (prevSibling = tree->_parent->_child; prevSibling; prevSibling = prevSibling->_sibling) {
 396                 if (prevSibling->_sibling == tree) {
 397                     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, prevSibling, prevSibling->_sibling, tree->_sibling);
 398                     if (tree->_parent->_rightmostChild == tree) {
 399                         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree->_parent, tree->_parent->_rightmostChild, prevSibling);
 400                     }
 401                     break;
 402                 }
 403             }
 404         }
 405         tree->_parent = NULL;
 406         tree->_sibling = NULL;
 407         _CFReleaseGC(tree);
 408     }
 409 }
 410
 411 void CFTreeRemoveAllChildren(CFTreeRef tree) {
 412     CFTreeRef nextChild;
 413     __CFGenericValidateType(tree, __kCFTreeTypeID);
 414     nextChild = tree->_child;
 415     tree->_child = NULL;
 416     tree->_rightmostChild = NULL;
 417     while (NULL != nextChild) {
 418         CFTreeRef nextSibling = nextChild->_sibling;
 419         nextChild->_parent = NULL;
 420         nextChild->_sibling = NULL;
 421         _CFReleaseGC(nextChild);
 422         nextChild = nextSibling;
 423     }
 424 }
 425
 426 struct _tcompareContext {
 427     CFComparatorFunction func;
 428     void *context;
 429 };
 430
 431 static CFComparisonResult __CFTreeCompareValues(const void *v1, const void *v2, struct _tcompareContext *context) {
 432     const void **val1 = (const void **)v1;
 433     const void **val2 = (const void **)v2;
 434     return (CFComparisonResult)(INVOKE_CALLBACK3(context->func, *val1, *val2, context->context));
 435 }
 436
 437 void CFTreeSortChildren(CFTreeRef tree, CFComparatorFunction comparator, void *context) {
 438     CFIndex children;
 439     __CFGenericValidateType(tree, __kCFTreeTypeID);
 440     CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__);
 441     children = CFTreeGetChildCount(tree);
 442     if (1 < children) {
 443         CFIndex idx;
 444         CFTreeRef nextChild;
 445         struct _tcompareContext ctx;
 446         CFTreeRef *list, buffer[128];
 447         CFAllocatorRef allocator = __CFGetAllocator(tree);
 448
 449         list = (children < 128) ? buffer : CFAllocatorAllocate(kCFAllocatorDefault, children * sizeof(CFTreeRef), 0); // XXX_PCB GC OK
 450         if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (temp)");
 451         nextChild = tree->_child;
 452         for (idx = 0; NULL != nextChild; idx++) {
 453             list[idx] = nextChild;
 454             nextChild = nextChild->_sibling;
 455         }
 456
 457         ctx.func = comparator;
 458         ctx.context = context;
 459         CFQSortArray(list, children, sizeof(CFTreeRef), (CFComparatorFunction)__CFTreeCompareValues, &ctx);
 460
 461         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, tree, tree->_child, list[0]);
 462         for (idx = 1; idx < children; idx++) {
 463             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, list[idx - 1], list[idx - 1]->_sibling, list[idx]);
 464         }
 465         list[idx - 1]->_sibling = NULL;
 466         tree->_rightmostChild = list[children - 1];
 467         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorDefault, list); // XXX_PCB GC OK
 468     }
 469 }
 470