Collections.subproj/CFTree.c

   1 /*
   2  * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /*      CFTree.c
  26         Copyright 1998-2002, Apple, Inc. All rights reserved.
  27         Responsibility: Christopher Kane
  28 */
  29
  30 #include <CoreFoundation/CFTree.h>
  31 #include "CFInternal.h"
  32 #include "CFUtilities.h"
  33
  34 struct __CFTreeCallBacks {
  35     CFTreeRetainCallBack                retain;
  36     CFTreeReleaseCallBack               release;
  37     CFTreeCopyDescriptionCallBack       copyDescription;
  38 };
  39
  40 struct __CFTree {
  41     CFRuntimeBase _base;
  42     CFTreeRef _parent;  /* Not retained */
  43     CFTreeRef _sibling; /* Not retained */
  44     CFTreeRef _child;   /* All children get a retain from the parent */
  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._info, 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 = %u, context = %@}"), cf, allocator, CFTreeGetChildCount(tree), contextDesc);
 101     return result;
 102 }
 103
 104 static void __CFTreeDeallocate(CFTypeRef cf) {
 105     CFTreeRef tree = (CFTreeRef)cf;
 106     const struct __CFTreeCallBacks *cb;
 107     CFTreeRemoveAllChildren(tree);
 108     cb = __CFTreeGetCallBacks(tree);
 109     if (NULL != cb->release) {
 110         INVOKE_CALLBACK1(cb->release, tree->_info);
 111     }
 112     if (__kCFTreeHasCustomCallBacks == __CFTreeGetCallBacksType(tree)) {
 113         CFAllocatorDeallocate(CFGetAllocator(tree), tree->_callbacks);
 114     }
 115 }
 116
 117 static CFTypeID __kCFTreeTypeID = _kCFRuntimeNotATypeID;
 118
 119 static const CFRuntimeClass __CFTreeClass = {
 120     0,
 121     "CFTree",
 122     NULL,       // init
 123     NULL,       // copy
 124     __CFTreeDeallocate,
 125     NULL,       // equal
 126     NULL,       // hash
 127     NULL,       //
 128     __CFTreeCopyDescription
 129 };
 130
 131 __private_extern__ void __CFTreeInitialize(void) {
 132     __kCFTreeTypeID = _CFRuntimeRegisterClass(&__CFTreeClass);
 133 }
 134
 135 CFTypeID CFTreeGetTypeID(void) {
 136     return __kCFTreeTypeID;
 137 }
 138
 139 CFTreeRef CFTreeCreate(CFAllocatorRef allocator, const CFTreeContext *context) {
 140     CFTreeRef memory;
 141     uint32_t size;
 142
 143     CFAssert1(NULL != context, __kCFLogAssertion, "%s(): pointer to context may not be NULL", __PRETTY_FUNCTION__);
 144     CFAssert1(0 == context->version, __kCFLogAssertion, "%s(): context version not initialized to 0", __PRETTY_FUNCTION__);
 145     size = sizeof(struct __CFTree) - sizeof(CFRuntimeBase);
 146     memory = (CFTreeRef)_CFRuntimeCreateInstance(allocator, __kCFTreeTypeID, size, NULL);
 147     if (NULL == memory) {
 148         return NULL;
 149     }
 150     memory->_parent = NULL;
 151     memory->_sibling = NULL;
 152     memory->_child = NULL;
 153
 154     /* Start the context off in a recognizable state */
 155     __CFBitfieldSetValue(memory->_base._info, 1, 0, __kCFTreeHasNullCallBacks);
 156     CFTreeSetContext(memory, context);
 157     return memory;
 158 }
 159
 160 CFIndex CFTreeGetChildCount(CFTreeRef tree) {
 161     SInt32 cnt = 0;
 162     __CFGenericValidateType(tree, __kCFTreeTypeID);
 163     tree = tree->_child;
 164     while (NULL != tree) {
 165         cnt++;
 166         tree = tree->_sibling;
 167     }
 168     return cnt;
 169 }
 170
 171 CFTreeRef CFTreeGetParent(CFTreeRef tree) {
 172     __CFGenericValidateType(tree, __kCFTreeTypeID);
 173     return tree->_parent;
 174 }
 175
 176 CFTreeRef CFTreeGetNextSibling(CFTreeRef tree) {
 177     __CFGenericValidateType(tree, __kCFTreeTypeID);
 178     return tree->_sibling;
 179 }
 180
 181 CFTreeRef CFTreeGetFirstChild(CFTreeRef tree) {
 182     __CFGenericValidateType(tree, __kCFTreeTypeID);
 183     return tree->_child;
 184 }
 185
 186 CFTreeRef CFTreeFindRoot(CFTreeRef tree) {
 187     __CFGenericValidateType(tree, __kCFTreeTypeID);
 188     while (NULL != tree->_parent) {
 189         tree = tree->_parent;
 190     }
 191     return tree;
 192 }
 193
 194 void CFTreeGetContext(CFTreeRef tree, CFTreeContext *context) {
 195     const struct __CFTreeCallBacks *cb;
 196     __CFGenericValidateType(tree, __kCFTreeTypeID);
 197     CFAssert1(0 == context->version, __kCFLogAssertion, "%s(): context version not initialized to 0", __PRETTY_FUNCTION__);
 198     cb = __CFTreeGetCallBacks(tree);
 199     context->version = 0;
 200     context->info = tree->_info;
 201 #if defined(__ppc__)
 202     context->retain = (void *)((uintptr_t)cb->retain & ~0x3);
 203     context->release = (void *)((uintptr_t)cb->release & ~0x3);
 204     context->copyDescription = (void *)((uintptr_t)cb->copyDescription & ~0x3);
 205 #else
 206     context->retain = cb->retain;
 207     context->release = cb->release;
 208     context->copyDescription = cb->copyDescription;
 209 #endif
 210 }
 211
 212 void CFTreeSetContext(CFTreeRef tree, const CFTreeContext *context) {
 213     uint32_t newtype, oldtype = __CFTreeGetCallBacksType(tree);
 214     struct __CFTreeCallBacks *oldcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
 215     struct __CFTreeCallBacks *newcb;
 216     void *oldinfo = tree->_info;
 217
 218     if (__CFTreeCallBacksMatchNull(context)) {
 219         newtype = __kCFTreeHasNullCallBacks;
 220     } else if (__CFTreeCallBacksMatchCFType(context)) {
 221         newtype = __kCFTreeHasCFTypeCallBacks;
 222     } else {
 223         newtype = __kCFTreeHasCustomCallBacks;
 224         tree->_callbacks = CFAllocatorAllocate(CFGetAllocator(tree), sizeof(struct __CFTreeCallBacks), 0);
 225         if (__CFOASafe) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (callbacks)");
 226         tree->_callbacks->retain = context->retain;
 227         tree->_callbacks->release = context->release;
 228         tree->_callbacks->copyDescription = context->copyDescription;
 229         FAULT_CALLBACK((void **)&(tree->_callbacks->retain));
 230         FAULT_CALLBACK((void **)&(tree->_callbacks->release));
 231         FAULT_CALLBACK((void **)&(tree->_callbacks->copyDescription));
 232     }
 233     __CFBitfieldSetValue(tree->_base._info, 1, 0, newtype);
 234     newcb = (struct __CFTreeCallBacks *)__CFTreeGetCallBacks(tree);
 235     if (NULL != newcb->retain) {
 236         tree->_info = (void *)INVOKE_CALLBACK1(newcb->retain, context->info);
 237     } else {
 238         tree->_info = context->info;
 239     }
 240     if (NULL != oldcb->release) {
 241         INVOKE_CALLBACK1(oldcb->release, oldinfo);
 242     }
 243     if (oldtype == __kCFTreeHasCustomCallBacks) {
 244         CFAllocatorDeallocate(CFGetAllocator(tree), oldcb);
 245     }
 246 }
 247
 248 #if 0
 249 CFTreeRef CFTreeFindNextSibling(CFTreeRef tree, const void *info) {
 250     __CFGenericValidateType(tree, __kCFTreeTypeID);
 251     tree = tree->_sibling;
 252     while (NULL != tree) {
 253         if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
 254             return tree;
 255         }
 256         tree = tree->_sibling;
 257     }
 258     return NULL;
 259 }
 260
 261 CFTreeRef CFTreeFindFirstChild(CFTreeRef tree, const void *info) {
 262     __CFGenericValidateType(tree, __kCFTreeTypeID);
 263     tree = tree->_child;
 264     while (NULL != tree) {
 265         if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->_context.info))) {
 266             return tree;
 267         }
 268         tree = tree->_sibling;
 269     }
 270     return NULL;
 271 }
 272
 273 CFTreeRef CFTreeFind(CFTreeRef tree, const void *info) {
 274     __CFGenericValidateType(tree, __kCFTreeTypeID);
 275     if (info == tree->_context.info || (tree->_context.equal && tree->_context.equal(info, tree->info))) {
 276         return tree;
 277     }
 278     tree = tree->_child;
 279     while (NULL != tree) {
 280         CFTreeRef found = CFTreeFind(tree, info);
 281         if (NULL != found) {
 282             return found;
 283         }
 284         tree = tree->_sibling;
 285     }
 286     return NULL;
 287 }
 288 #endif
 289
 290 CFTreeRef CFTreeGetChildAtIndex(CFTreeRef tree, CFIndex idx) {
 291     __CFGenericValidateType(tree, __kCFTreeTypeID);
 292     tree = tree->_child;
 293     while (NULL != tree) {
 294         if (0 == idx) return tree;
 295         idx--;
 296         tree = tree->_sibling;
 297     }
 298     return NULL;
 299 }
 300
 301 void CFTreeGetChildren(CFTreeRef tree, CFTreeRef *children) {
 302     __CFGenericValidateType(tree, __kCFTreeTypeID);
 303     tree = tree->_child;
 304     while (NULL != tree) {
 305         *children++ = tree;
 306         tree = tree->_sibling;
 307     }
 308 }
 309
 310 void CFTreeApplyFunctionToChildren(CFTreeRef tree, CFTreeApplierFunction applier, void *context) {
 311     __CFGenericValidateType(tree, __kCFTreeTypeID);
 312     CFAssert1(NULL != applier, __kCFLogAssertion, "%s(): pointer to applier function may not be NULL", __PRETTY_FUNCTION__);
 313     tree = tree->_child;
 314     while (NULL != tree) {
 315         applier(tree, context);
 316         tree = tree->_sibling;
 317     }
 318 }
 319
 320 void CFTreePrependChild(CFTreeRef tree, CFTreeRef newChild) {
 321     __CFGenericValidateType(tree, __kCFTreeTypeID);
 322     __CFGenericValidateType(newChild, __kCFTreeTypeID);
 323     CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 324     CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 325     CFRetain(newChild);
 326     newChild->_parent = tree;
 327     newChild->_sibling = tree->_child;
 328     tree->_child = newChild;
 329 }
 330
 331 void CFTreeAppendChild(CFTreeRef tree, CFTreeRef newChild) {
 332     __CFGenericValidateType(tree, __kCFTreeTypeID);
 333     __CFGenericValidateType(newChild, __kCFTreeTypeID);
 334     CFAssert1(NULL == newChild->_parent, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 335     CFAssert1(NULL == newChild->_sibling, __kCFLogAssertion, "%s(): must remove newChild from previous parent first", __PRETTY_FUNCTION__);
 336     if (newChild->_parent) {
 337         HALT;
 338     }
 339     CFRetain(newChild);
 340     newChild->_parent = tree;
 341     newChild->_sibling = NULL;
 342     if (!tree->_child) {
 343         tree->_child = newChild;
 344     } else {
 345         CFTreeRef child;
 346         for (child = tree->_child; child->_sibling; child = child->_sibling)
 347             ;
 348         child->_sibling = newChild;
 349     }
 350 }
 351
 352 void CFTreeInsertSibling(CFTreeRef tree, CFTreeRef newSibling) {
 353     __CFGenericValidateType(tree, __kCFTreeTypeID);
 354     __CFGenericValidateType(newSibling, __kCFTreeTypeID);
 355     CFAssert1(NULL != tree->_parent, __kCFLogAssertion, "%s(): tree must have a parent", __PRETTY_FUNCTION__);
 356     CFAssert1(NULL == newSibling->_parent, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
 357     CFAssert1(NULL == newSibling->_sibling, __kCFLogAssertion, "%s(): must remove newSibling from previous parent first", __PRETTY_FUNCTION__);
 358     CFRetain(newSibling);
 359     newSibling->_parent = tree->_parent;
 360     newSibling->_sibling = tree->_sibling;
 361     tree->_sibling = newSibling;
 362 }
 363
 364 void CFTreeRemove(CFTreeRef tree) {
 365     __CFGenericValidateType(tree, __kCFTreeTypeID);
 366     if (NULL != tree->_parent) {
 367         if (tree == tree->_parent->_child) {
 368             tree->_parent->_child = tree->_sibling;
 369         } else {
 370             CFTreeRef prevSibling = NULL;
 371             for (prevSibling = tree->_parent->_child; prevSibling; prevSibling = prevSibling->_sibling) {
 372                 if (prevSibling->_sibling == tree) {
 373                     prevSibling->_sibling = tree->_sibling;
 374                     break;
 375                 }
 376             }
 377         }
 378         tree->_parent = NULL;
 379         tree->_sibling = NULL;
 380         CFRelease(tree);
 381     }
 382 }
 383
 384 void CFTreeRemoveAllChildren(CFTreeRef tree) {
 385     CFTreeRef nextChild;
 386     __CFGenericValidateType(tree, __kCFTreeTypeID);
 387     nextChild = tree->_child;
 388     tree->_child = NULL;
 389     while (NULL != nextChild) {
 390         CFTreeRef nextSibling = nextChild->_sibling;
 391         nextChild->_parent = NULL;
 392         nextChild->_sibling = NULL;
 393         CFRelease(nextChild);
 394         nextChild = nextSibling;
 395     }
 396 }
 397
 398 struct _tcompareContext {
 399     CFComparatorFunction func;
 400     void *context;
 401 };
 402
 403 static CFComparisonResult __CFTreeCompareValues(const void *v1, const void *v2, struct _tcompareContext *context) {
 404     const void **val1 = (const void **)v1;
 405     const void **val2 = (const void **)v2;
 406     return (CFComparisonResult)(INVOKE_CALLBACK3(context->func, *val1, *val2, context->context));
 407 }
 408
 409 void CFTreeSortChildren(CFTreeRef tree, CFComparatorFunction comparator, void *context) {
 410     CFIndex children;
 411     __CFGenericValidateType(tree, __kCFTreeTypeID);
 412     CFAssert1(NULL != comparator, __kCFLogAssertion, "%s(): pointer to comparator function may not be NULL", __PRETTY_FUNCTION__);
 413     children = CFTreeGetChildCount(tree);
 414     if (1 < children) {
 415         CFIndex idx;
 416         CFTreeRef nextChild;
 417         struct _tcompareContext ctx;
 418         CFTreeRef *list, buffer[128];
 419
 420         list = (children < 128) ? buffer : CFAllocatorAllocate(kCFAllocatorDefault, children * sizeof(CFTreeRef), 0);
 421         if (__CFOASafe && list != buffer) __CFSetLastAllocationEventName(tree->_callbacks, "CFTree (temp)");
 422         nextChild = tree->_child;
 423         for (idx = 0; NULL != nextChild; idx++) {
 424             list[idx] = nextChild;
 425             nextChild = nextChild->_sibling;
 426         }
 427
 428         ctx.func = comparator;
 429         ctx.context = context;
 430         CFQSortArray(list, children, sizeof(CFTreeRef), (CFComparatorFunction)__CFTreeCompareValues, &ctx);
 431
 432         tree->_child = list[0];
 433         for (idx = 1; idx < children; idx++) {
 434             list[idx - 1]->_sibling = list[idx];
 435         }
 436         list[idx - 1]->_sibling = NULL;
 437         if (list != buffer) CFAllocatorDeallocate(kCFAllocatorDefault, list);
 438     }
 439 }
 440