Collections.subproj/CFBag.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 /*      CFBag.c
  24         Copyright 1998-2002, Apple, Inc. All rights reserved.
  25         Responsibility: Christopher Kane
  26 */
  27
  28 #include <CoreFoundation/CFBag.h>
  29 #include "CFInternal.h"
  30
  31 const CFBagCallBacks kCFTypeBagCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  32 const CFBagCallBacks kCFCopyStringBagCallBacks = {0, (void *)CFStringCreateCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  33 static const CFBagCallBacks __kCFNullBagCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
  34
  35
  36 static const uint32_t __CFBagCapacities[42] = {
  37     4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
  38     15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
  39     3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
  40     228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
  41 };
  42
  43 static const uint32_t __CFBagBuckets[42] = {    // primes
  44     5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
  45     24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
  46     4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
  47     370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
  48 };
  49
  50 CF_INLINE CFIndex __CFBagRoundUpCapacity(CFIndex capacity) {
  51     CFIndex idx;
  52     for (idx = 0; idx < 42 && __CFBagCapacities[idx] < (uint32_t)capacity; idx++);
  53     if (42 <= idx) HALT;
  54     return __CFBagCapacities[idx];
  55 }
  56
  57 CF_INLINE CFIndex __CFBagNumBucketsForCapacity(CFIndex capacity) {
  58     CFIndex idx;
  59     for (idx = 0; idx < 42 && __CFBagCapacities[idx] < (uint32_t)capacity; idx++);
  60     if (42 <= idx) HALT;
  61     return __CFBagBuckets[idx];
  62 }
  63
  64 enum {          /* Bits 1-0 */
  65     __kCFBagImmutable = 0,              /* unchangable and fixed capacity */
  66     __kCFBagMutable = 1,                /* changeable and variable capacity */
  67     __kCFBagFixedMutable = 3            /* changeable and fixed capacity */
  68 };
  69
  70 enum {          /* Bits 3-2 */
  71     __kCFBagHasNullCallBacks = 0,
  72     __kCFBagHasCFTypeCallBacks = 1,
  73     __kCFBagHasCustomCallBacks = 3      /* callbacks are at end of header */
  74 };
  75
  76 enum {          /* Bit 4 */
  77     __kCFCollectionIsWeak = 0,
  78     __kCFCollectionIsStrong = 1,
  79 };
  80
  81
  82 struct __CFBagBucket {
  83     const void *_key;
  84     CFIndex _count;
  85 };
  86
  87 struct __CFBag {
  88     CFRuntimeBase _base;
  89     CFIndex _count;             /* number of values */
  90     CFIndex _capacity;          /* maximum number of values */
  91     CFIndex _bucketsUsed;       /* number of slots used */
  92     CFIndex _bucketsNum;        /* number of slots */
  93     const void *_emptyMarker;
  94     const void *_deletedMarker;
  95     void *_context;             /* private */
  96     struct __CFBagBucket *_buckets;     /* can be NULL if not allocated yet */
  97 };
  98
  99 CF_INLINE bool __CFBagBucketIsEmpty(CFBagRef bag, const struct __CFBagBucket *bucket) {
 100     return (bag->_emptyMarker == bucket->_key);
 101 }
 102
 103 CF_INLINE bool __CFBagBucketIsDeleted(CFBagRef bag, const struct __CFBagBucket *bucket) {
 104     return (bag->_deletedMarker == bucket->_key);
 105 }
 106
 107 CF_INLINE bool __CFBagBucketIsOccupied(CFBagRef bag, const struct __CFBagBucket *bucket) {
 108     return (bag->_emptyMarker != bucket->_key && bag->_deletedMarker != bucket->_key);
 109 }
 110
 111 /* Bits 1-0 of the base reserved bits are used for mutability variety */
 112 /* Bits 3-2 of the base reserved bits are used for callback indicator bits */
 113 /* Bits 4-5 are used by GC */
 114
 115 static bool isStrongMemory(CFTypeRef collection) {
 116     return  ! __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_info, 4, 4);
 117 }
 118
 119 static bool needsRestore(CFTypeRef collection) {
 120     return __CFBitfieldGetValue(((const CFRuntimeBase *)collection)->_info, 5, 5);
 121 }
 122
 123
 124 CF_INLINE CFIndex __CFBagGetType(CFBagRef bag) {
 125     return __CFBitfieldGetValue(((const CFRuntimeBase *)bag)->_info, 1, 0);
 126 }
 127
 128 CF_INLINE CFIndex __CFBagGetSizeOfType(CFIndex t) {
 129     CFIndex size = sizeof(struct __CFBag);
 130     if (__CFBitfieldGetValue(t, 3, 2) == __kCFBagHasCustomCallBacks) {
 131         size += sizeof(CFBagCallBacks);
 132     }
 133     return size;
 134 }
 135
 136 CF_INLINE const CFBagCallBacks *__CFBagGetCallBacks(CFBagRef bag) {
 137     CFBagCallBacks *result = NULL;
 138     switch (__CFBitfieldGetValue(((const CFRuntimeBase *)bag)->_info, 3, 2)) {
 139     case __kCFBagHasNullCallBacks:
 140         return &__kCFNullBagCallBacks;
 141     case __kCFBagHasCFTypeCallBacks:
 142         return &kCFTypeBagCallBacks;
 143     case __kCFBagHasCustomCallBacks:
 144         break;
 145     }
 146     result = (CFBagCallBacks *)((uint8_t *)bag + sizeof(struct __CFBag));
 147     return result;
 148 }
 149
 150 CF_INLINE bool __CFBagCallBacksMatchNull(const CFBagCallBacks *c) {
 151     return (NULL == c ||
 152         (c->retain == __kCFNullBagCallBacks.retain &&
 153          c->release == __kCFNullBagCallBacks.release &&
 154          c->copyDescription == __kCFNullBagCallBacks.copyDescription &&
 155          c->equal == __kCFNullBagCallBacks.equal &&
 156          c->hash == __kCFNullBagCallBacks.hash));
 157 }
 158
 159 CF_INLINE bool __CFBagCallBacksMatchCFType(const CFBagCallBacks *c) {
 160     return (&kCFTypeBagCallBacks == c ||
 161         (c->retain == kCFTypeBagCallBacks.retain &&
 162          c->release == kCFTypeBagCallBacks.release &&
 163          c->copyDescription == kCFTypeBagCallBacks.copyDescription &&
 164          c->equal == kCFTypeBagCallBacks.equal &&
 165          c->hash == kCFTypeBagCallBacks.hash));
 166 }
 167
 168
 169 static void __CFBagFindBuckets1(CFBagRef bag, const void *key, struct __CFBagBucket **match) {
 170     const CFBagCallBacks *cb = __CFBagGetCallBacks(bag);
 171     struct __CFBagBucket *buckets = bag->_buckets;
 172     CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, bag->_context) : (CFHashCode)key;
 173     UInt32 start = keyHash % bag->_bucketsNum;
 174     UInt32 probe = start;
 175     UInt32 probeskip = 1;
 176     *match = NULL;
 177     for (;;) {
 178         struct __CFBagBucket *currentBucket = buckets + probe;
 179         if (__CFBagBucketIsEmpty(bag, currentBucket)) {
 180             return;
 181         } else if (__CFBagBucketIsDeleted(bag, currentBucket)) {
 182             /* do nothing */
 183         } else if (currentBucket->_key == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void *))cb->equal, currentBucket->_key, key, bag->_context))) {
 184             *match = currentBucket;
 185             return;
 186         }
 187         probe = (probe + probeskip) % bag->_bucketsNum;
 188         if (start == probe) return;
 189     }
 190 }
 191
 192 static void __CFBagFindBuckets2(CFBagRef bag, const void *key, struct __CFBagBucket **match, struct __CFBagBucket **nomatch) {
 193     const CFBagCallBacks *cb = __CFBagGetCallBacks(bag);
 194     struct __CFBagBucket *buckets = bag->_buckets;
 195     CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, bag->_context) : (CFHashCode)key;
 196     UInt32 start = keyHash % bag->_bucketsNum;
 197     UInt32 probe = start;
 198     UInt32 probeskip = 1;
 199     *match = NULL;
 200     *nomatch = NULL;
 201     for (;;) {
 202         struct __CFBagBucket *currentBucket = buckets + probe;
 203         if (__CFBagBucketIsEmpty(bag, currentBucket)) {
 204             if (!*nomatch) *nomatch = currentBucket;
 205             return;
 206         } else if (__CFBagBucketIsDeleted(bag, currentBucket)) {
 207             if (!*nomatch) *nomatch = currentBucket;
 208         } else if (!*match && (currentBucket->_key == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void *))cb->equal, currentBucket->_key, key, bag->_context)))) {
 209             *match = currentBucket;
 210             return;
 211         }
 212         probe = (probe + probeskip) % bag->_bucketsNum;
 213         if (start == probe) return;
 214     }
 215 }
 216
 217 static void __CFBagFindNewEmptyMarker(CFBagRef bag) {
 218     struct __CFBagBucket *buckets;
 219     const void *newEmpty;
 220     bool hit;
 221     CFIndex idx, nbuckets;
 222     buckets = bag->_buckets;
 223     nbuckets = bag->_bucketsNum;
 224     newEmpty = bag->_emptyMarker;
 225     do {
 226         (intptr_t)newEmpty -= 2;
 227         hit = false;
 228         for (idx = 0; idx < nbuckets; idx++) {
 229             if (newEmpty == buckets[idx]._key) {
 230                 hit = true;
 231                 break;
 232             }
 233         }
 234     } while (hit);
 235     for (idx = 0; idx < nbuckets; idx++) {
 236         if (bag->_emptyMarker == buckets[idx]._key) {
 237             buckets[idx]._key = newEmpty;
 238         }
 239     }
 240     ((struct __CFBag *)bag)->_emptyMarker = newEmpty;
 241 }
 242
 243 static void __CFBagFindNewDeletedMarker(CFBagRef bag) {
 244     struct __CFBagBucket *buckets;
 245     const void *newDeleted;
 246     bool hit;
 247     CFIndex idx, nbuckets;
 248     buckets = bag->_buckets;
 249     nbuckets = bag->_bucketsNum;
 250     newDeleted = bag->_deletedMarker;
 251     do {
 252         (intptr_t)newDeleted += 2;
 253         hit = false;
 254         for (idx = 0; idx < nbuckets; idx++) {
 255             if (newDeleted == buckets[idx]._key) {
 256                 hit = true;
 257                 break;
 258             }
 259         }
 260     } while (hit);
 261     for (idx = 0; idx < nbuckets; idx++) {
 262         if (bag->_deletedMarker == buckets[idx]._key) {
 263             buckets[idx]._key = newDeleted;
 264         }
 265     }
 266     ((struct __CFBag *)bag)->_deletedMarker = newDeleted;
 267 }
 268
 269 static bool __CFBagEqual(CFTypeRef cf1, CFTypeRef cf2) {
 270     CFBagRef bag1 = (CFBagRef)cf1;
 271     CFBagRef bag2 = (CFBagRef)cf2;
 272     const CFBagCallBacks *cb1, *cb2;
 273     const struct __CFBagBucket *buckets;
 274     CFIndex idx, nbuckets;
 275     if (bag1 == bag2) return true;
 276     if (bag1->_count != bag2->_count) return false;
 277     cb1 = __CFBagGetCallBacks(bag1);
 278     cb2 = __CFBagGetCallBacks(bag2);
 279     if (cb1->equal != cb2->equal) return false;
 280     if (0 == bag1->_count) return true; /* after function comparison! */
 281     buckets = bag1->_buckets;
 282     nbuckets = bag1->_bucketsNum;
 283     for (idx = 0; idx < nbuckets; idx++) {
 284         if (__CFBagBucketIsOccupied(bag1, &buckets[idx])) {
 285             if (buckets[idx]._count != CFBagGetCountOfValue(bag2, buckets[idx]._key)) {
 286                 return false;
 287             }
 288         }
 289     }
 290     return true;
 291 }
 292
 293 static CFHashCode __CFBagHash(CFTypeRef cf) {
 294     CFBagRef bag = (CFBagRef)cf;
 295     return bag->_count;
 296 }
 297
 298 static CFStringRef __CFBagCopyDescription(CFTypeRef cf) {
 299     CFBagRef bag = (CFBagRef)cf;
 300     const CFBagCallBacks *cb;
 301     const struct __CFBagBucket *buckets;
 302     CFIndex idx, nbuckets;
 303     CFMutableStringRef result;
 304     cb = __CFBagGetCallBacks(bag);
 305     buckets = bag->_buckets;
 306     nbuckets = bag->_bucketsNum;
 307     result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
 308     CFStringAppendFormat(result, NULL, CFSTR("<CFBag %p [%p]>{count = %u, capacity = %u, values = (\n"), bag, CFGetAllocator(bag), bag->_count, bag->_capacity);
 309     for (idx = 0; idx < nbuckets; idx++) {
 310         if (__CFBagBucketIsOccupied(bag, &buckets[idx])) {
 311             CFStringRef desc = NULL;
 312             if (NULL != cb->copyDescription) {
 313                 desc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))cb->copyDescription), buckets[idx]._key, bag->_context);
 314             }
 315             if (NULL != desc) {
 316                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ (%d)\n"), idx, desc, buckets[idx]._count);
 317                 CFRelease(desc);
 318             } else {
 319                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> (%d)\n"), idx, buckets[idx]._key, buckets[idx]._count);
 320             }
 321         }
 322     }
 323     CFStringAppend(result, CFSTR(")}"));
 324     return result;
 325 }
 326
 327 static void __CFBagDeallocate(CFTypeRef cf) {
 328     CFMutableBagRef bag = (CFMutableBagRef)cf;
 329     CFAllocatorRef allocator = CFGetAllocator(bag);
 330     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 331         const CFBagCallBacks *cb = __CFBagGetCallBacks(bag);
 332         if (cb->retain == NULL && cb->release == NULL)
 333             return; // XXX_PCB keep bag intact during finalization.
 334     }
 335     if (__CFBagGetType(bag) == __kCFBagImmutable) {
 336         __CFBitfieldSetValue(((CFRuntimeBase *)bag)->_info, 1, 0, __kCFBagFixedMutable);
 337     }
 338     CFBagRemoveAllValues(bag);
 339     if (__CFBagGetType(bag) == __kCFBagMutable && bag->_buckets) {
 340         _CFAllocatorDeallocateGC(allocator, bag->_buckets);
 341     }
 342 }
 343
 344 static CFTypeID __kCFBagTypeID = _kCFRuntimeNotATypeID;
 345
 346 static const CFRuntimeClass __CFBagClass = {
 347     _kCFRuntimeScannedObject,
 348     "CFBag",
 349     NULL,       // init
 350     NULL,       // copy
 351     __CFBagDeallocate,
 352     (void *)__CFBagEqual,
 353     __CFBagHash,
 354     NULL,       //
 355     __CFBagCopyDescription
 356 };
 357
 358 __private_extern__ void __CFBagInitialize(void) {
 359     __kCFBagTypeID = _CFRuntimeRegisterClass(&__CFBagClass);
 360 }
 361
 362 CFTypeID CFBagGetTypeID(void) {
 363     return __kCFBagTypeID;
 364 }
 365
 366 static CFBagRef __CFBagInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const CFBagCallBacks *callBacks) {
 367     struct __CFBag *memory;
 368     UInt32 size;
 369     CFIndex idx;
 370     CFBagCallBacks nonRetainingCallbacks;
 371     __CFBitfieldSetValue(flags, 31, 2, 0);
 372     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 373         if (!callBacks || (callBacks->retain == NULL && callBacks->release == NULL)) {
 374             __CFBitfieldSetValue(flags, 4, 4, 1); // setWeak
 375         }
 376         else {
 377             if (callBacks->retain == __CFTypeCollectionRetain && callBacks->release == __CFTypeCollectionRelease) {
 378                 nonRetainingCallbacks = *callBacks;
 379                 nonRetainingCallbacks.retain = NULL;
 380                 nonRetainingCallbacks.release = NULL;
 381                 callBacks = &nonRetainingCallbacks;
 382                 __CFBitfieldSetValue(flags, 5, 5, 1); // setNeedsRestore
 383             }
 384         }
 385     }
 386     if (__CFBagCallBacksMatchNull(callBacks)) {
 387         __CFBitfieldSetValue(flags, 3, 2, __kCFBagHasNullCallBacks);
 388     } else if (__CFBagCallBacksMatchCFType(callBacks)) {
 389         __CFBitfieldSetValue(flags, 3, 2, __kCFBagHasCFTypeCallBacks);
 390     } else {
 391         __CFBitfieldSetValue(flags, 3, 2, __kCFBagHasCustomCallBacks);
 392     }
 393     size = __CFBagGetSizeOfType(flags) - sizeof(CFRuntimeBase);
 394     switch (__CFBitfieldGetValue(flags, 1, 0)) {
 395     case __kCFBagImmutable:
 396     case __kCFBagFixedMutable:
 397         size += __CFBagNumBucketsForCapacity(capacity) * sizeof(struct __CFBagBucket);
 398         break;
 399     case __kCFBagMutable:
 400         break;
 401     }
 402     memory = (struct __CFBag *)_CFRuntimeCreateInstance(allocator, __kCFBagTypeID, size, NULL);
 403     if (NULL == memory) {
 404         return NULL;
 405     }
 406     __CFBitfieldSetValue(memory->_base._info, 6, 0, flags);
 407     memory->_count = 0;
 408     memory->_bucketsUsed = 0;
 409     memory->_emptyMarker = (const void *)0xa1b1c1d3;
 410     memory->_deletedMarker = (const void *)0xa1b1c1d5;
 411     memory->_context = NULL;
 412     switch (__CFBitfieldGetValue(flags, 1, 0)) {
 413     case __kCFBagImmutable:
 414         if (!isStrongMemory(memory)) {  // if weak, don't scan
 415             auto_zone_set_layout_type(__CFCollectableZone, memory, AUTO_OBJECT_UNSCANNED);
 416         }
 417         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFBag (immutable)");
 418         memory->_capacity = capacity;   /* Don't round up capacity */
 419         memory->_bucketsNum = __CFBagNumBucketsForCapacity(memory->_capacity);
 420         memory->_buckets = (struct __CFBagBucket *)((uint8_t *)memory + __CFBagGetSizeOfType(flags));
 421         for (idx = memory->_bucketsNum; idx--;) {
 422             memory->_buckets[idx]._key = memory->_emptyMarker;
 423         }
 424         break;
 425     case __kCFBagFixedMutable:
 426         if (!isStrongMemory(memory)) {  // if weak, don't scan
 427             auto_zone_set_layout_type(__CFCollectableZone, memory, AUTO_OBJECT_UNSCANNED);
 428         }
 429         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFBag (mutable-fixed)");
 430         memory->_capacity = capacity;   /* Don't round up capacity */
 431         memory->_bucketsNum = __CFBagNumBucketsForCapacity(memory->_capacity);
 432         memory->_buckets = (struct __CFBagBucket *)((uint8_t *)memory + __CFBagGetSizeOfType(flags));
 433         for (idx = memory->_bucketsNum; idx--;) {
 434             memory->_buckets[idx]._key = memory->_emptyMarker;
 435         }
 436         break;
 437     case __kCFBagMutable:
 438         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFBag (mutable-variable)");
 439         memory->_capacity = __CFBagRoundUpCapacity(1);
 440         memory->_bucketsNum = 0;
 441         memory->_buckets = NULL;
 442         break;
 443     }
 444     if (__kCFBagHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
 445         const CFBagCallBacks *cb = __CFBagGetCallBacks((CFBagRef)memory);
 446         *(CFBagCallBacks *)cb = *callBacks;
 447         FAULT_CALLBACK((void **)&(cb->retain));
 448         FAULT_CALLBACK((void **)&(cb->release));
 449         FAULT_CALLBACK((void **)&(cb->copyDescription));
 450         FAULT_CALLBACK((void **)&(cb->equal));
 451         FAULT_CALLBACK((void **)&(cb->hash));
 452     }
 453     return (CFBagRef)memory;
 454 }
 455
 456 CFBagRef CFBagCreate(CFAllocatorRef allocator, const void **values, CFIndex numValues, const CFBagCallBacks *callBacks) {
 457     CFBagRef result;
 458     UInt32 flags;
 459     CFIndex idx;
 460     CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
 461     result = __CFBagInit(allocator, __kCFBagImmutable, numValues, callBacks);
 462     flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
 463     if (flags == __kCFBagImmutable) {
 464         __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFBagFixedMutable);
 465     }
 466     for (idx = 0; idx < numValues; idx++) {
 467         CFBagAddValue((CFMutableBagRef)result, values[idx]);
 468     }
 469     __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
 470     return result;
 471 }
 472
 473 CFMutableBagRef CFBagCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFBagCallBacks *callBacks) {
 474     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 475     return (CFMutableBagRef)__CFBagInit(allocator, (0 == capacity) ? __kCFBagMutable : __kCFBagFixedMutable, capacity, callBacks);
 476 }
 477
 478 CFBagRef CFBagCreateCopy(CFAllocatorRef allocator, CFBagRef bag) {
 479     CFBagRef result;
 480     const CFBagCallBacks *cb;
 481     CFIndex numValues = CFBagGetCount(bag);
 482     const void **list, *buffer[256];
 483     list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
 484     if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFBag (temp)");
 485     CFBagGetValues(bag, list);
 486     CFBagCallBacks patchedCB;
 487     if (CF_IS_OBJC(__kCFBagTypeID, bag)) {
 488         cb = &kCFTypeBagCallBacks;
 489     }
 490     else {
 491         cb = __CFBagGetCallBacks(bag);
 492         if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 493             if (needsRestore(bag)) {
 494                 patchedCB = *cb;    // copy
 495                 cb = &patchedCB;    // reset to copy
 496                 patchedCB.retain = __CFTypeCollectionRetain;
 497                 patchedCB.release = __CFTypeCollectionRelease;
 498             }
 499         }
 500     }
 501     result = CFBagCreate(allocator, list, numValues, cb);
 502     if (list != buffer) CFAllocatorDeallocate(allocator, list); // XXX_PCB GC OK
 503     return result;
 504 }
 505
 506 CFMutableBagRef CFBagCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFBagRef bag) {
 507     CFMutableBagRef result;
 508     const CFBagCallBacks *cb;
 509     CFIndex idx, numValues = CFBagGetCount(bag);
 510     const void **list, *buffer[256];
 511     CFAssert3(0 == capacity || numValues <= capacity, __kCFLogAssertion, "%s(): for fixed-mutable bags, capacity (%d) must be greater than or equal to initial number of values (%d)", __PRETTY_FUNCTION__, capacity, numValues);
 512     list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
 513     if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFBag (temp)");
 514     CFBagGetValues(bag, list);
 515     CFBagCallBacks patchedCB;
 516     if (CF_IS_OBJC(__kCFBagTypeID, bag)) {
 517         cb = &kCFTypeBagCallBacks;
 518     }
 519     else {
 520         cb = __CFBagGetCallBacks(bag);
 521         if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 522             if (needsRestore(bag)) {
 523                 patchedCB = *cb;    // copy
 524                 cb = &patchedCB;    // reset to copy
 525                 patchedCB.retain = __CFTypeCollectionRetain;
 526                 patchedCB.release = __CFTypeCollectionRelease;
 527             }
 528         }
 529     }
 530     result = CFBagCreateMutable(allocator, capacity, cb);
 531     if (0 == capacity) _CFBagSetCapacity(result, numValues);
 532     for (idx = 0; idx < numValues; idx++) {
 533         CFBagAddValue(result, list[idx]);
 534     }
 535     if (list != buffer) CFAllocatorDeallocate(allocator, list); // GC OK
 536     return result;
 537 }
 538
 539
 540 void _CFBagSetContext(CFBagRef bag, void *context) {
 541     CFAllocatorRef allocator = CFGetAllocator(bag);
 542     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, bag, bag->_context, context);
 543 }
 544
 545 CFIndex CFBagGetCount(CFBagRef bag) {
 546     __CFGenericValidateType(bag, __kCFBagTypeID);
 547     return bag->_count;
 548 }
 549
 550 CFIndex CFBagGetCountOfValue(CFBagRef bag, const void *value) {
 551     struct __CFBagBucket *match;
 552     __CFGenericValidateType(bag, __kCFBagTypeID);
 553     if (0 == bag->_count) return 0;
 554     __CFBagFindBuckets1(bag, value, &match);
 555     return (match ? match->_count : 0);
 556 }
 557
 558 Boolean CFBagContainsValue(CFBagRef bag, const void *value) {
 559     struct __CFBagBucket *match;
 560     __CFGenericValidateType(bag, __kCFBagTypeID);
 561     if (0 == bag->_count) return false;
 562     __CFBagFindBuckets1(bag, value, &match);
 563     return (match ? true : false);
 564 }
 565
 566 const void *CFBagGetValue(CFBagRef bag, const void *value) {
 567     struct __CFBagBucket *match;
 568     __CFGenericValidateType(bag, __kCFBagTypeID);
 569     if (0 == bag->_count) return NULL;
 570     __CFBagFindBuckets1(bag, value, &match);
 571     return (match ? match->_key : NULL);
 572 }
 573
 574 Boolean CFBagGetValueIfPresent(CFBagRef bag, const void *candidate, const void **value) {
 575     struct __CFBagBucket *match;
 576     __CFGenericValidateType(bag, __kCFBagTypeID);
 577     if (0 == bag->_count) return false;
 578     __CFBagFindBuckets1(bag, candidate, &match);
 579     return (match ? ((value ? __CFObjCStrongAssign(match->_key, value) : NULL), true) : false);
 580 }
 581
 582 void CFBagGetValues(CFBagRef bag, const void **values) {
 583     struct __CFBagBucket *buckets;
 584     CFIndex idx, cnt, nbuckets;
 585     __CFGenericValidateType(bag, __kCFBagTypeID);
 586     if (CF_USING_COLLECTABLE_MEMORY) {
 587         // GC: speculatively issue a write-barrier on the copied to buffers (3743553).
 588         __CFObjCWriteBarrierRange(values, bag->_count * sizeof(void *));
 589     }
 590     buckets = bag->_buckets;
 591     nbuckets = bag->_bucketsNum;
 592     for (idx = 0; idx < nbuckets; idx++) {
 593         if (__CFBagBucketIsOccupied(bag, &buckets[idx])) {
 594             for (cnt = buckets[idx]._count; cnt--;) {
 595                 if (values) *values++ = buckets[idx]._key;
 596             }
 597         }
 598     }
 599 }
 600
 601 void CFBagApplyFunction(CFBagRef bag, CFBagApplierFunction applier, void *context) {
 602     struct __CFBagBucket *buckets;
 603     CFIndex idx, cnt, nbuckets;
 604     FAULT_CALLBACK((void **)&(applier));
 605     __CFGenericValidateType(bag, __kCFBagTypeID);
 606     buckets = bag->_buckets;
 607     nbuckets = bag->_bucketsNum;
 608     for (idx = 0; idx < nbuckets; idx++) {
 609         if (__CFBagBucketIsOccupied(bag, &buckets[idx])) {
 610             for (cnt = buckets[idx]._count; cnt--;) {
 611                 INVOKE_CALLBACK2(applier, buckets[idx]._key, context);
 612             }
 613         }
 614     }
 615 }
 616
 617 static void __CFBagGrow(CFMutableBagRef bag, CFIndex numNewValues) {
 618     struct __CFBagBucket *oldbuckets = bag->_buckets;
 619     CFIndex idx, oldnbuckets = bag->_bucketsNum;
 620     CFIndex oldCount = bag->_count;
 621     CFAllocatorRef allocator = CFGetAllocator(bag);
 622     bag->_capacity = __CFBagRoundUpCapacity(oldCount + numNewValues);
 623     bag->_bucketsNum = __CFBagNumBucketsForCapacity(bag->_capacity);
 624     void *bucket = _CFAllocatorAllocateGC(allocator, bag->_bucketsNum * sizeof(struct __CFBagBucket), isStrongMemory(bag) ? AUTO_MEMORY_SCANNED : AUTO_MEMORY_UNSCANNED);
 625     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, bag, bag->_buckets, bucket);
 626     if (__CFOASafe) __CFSetLastAllocationEventName(bag->_buckets, "CFBag (store)");
 627     if (NULL == bag->_buckets) HALT;
 628     for (idx = bag->_bucketsNum; idx--;) {
 629         bag->_buckets[idx]._key = bag->_emptyMarker;
 630     }
 631     if (NULL == oldbuckets) return;
 632     for (idx = 0; idx < oldnbuckets; idx++) {
 633         if (__CFBagBucketIsOccupied(bag, &oldbuckets[idx])) {
 634             struct __CFBagBucket *match, *nomatch;
 635             __CFBagFindBuckets2(bag, oldbuckets[idx]._key, &match, &nomatch);
 636             CFAssert3(!match, __kCFLogAssertion, "%s(): two values (%p, %p) now hash to the same slot; mutable value changed while in table or hash value is not immutable", __PRETTY_FUNCTION__, oldbuckets[idx]._key, match->_key);
 637             if (nomatch) {
 638                 CF_WRITE_BARRIER_ASSIGN(allocator, nomatch->_key, oldbuckets[idx]._key);
 639                 nomatch->_count = oldbuckets[idx]._count;
 640             }
 641         }
 642     }
 643     CFAssert1(bag->_count == oldCount, __kCFLogAssertion, "%s(): bag count differs after rehashing; error", __PRETTY_FUNCTION__);
 644     _CFAllocatorDeallocateGC(CFGetAllocator(bag), oldbuckets);
 645 }
 646
 647 // This function is for Foundation's benefit; no one else should use it.
 648 void _CFBagSetCapacity(CFMutableBagRef bag, CFIndex cap) {
 649     if (CF_IS_OBJC(__kCFBagTypeID, bag)) return;
 650 #if defined(DEBUG)
 651     __CFGenericValidateType(bag, __kCFBagTypeID);
 652     CFAssert1(__CFBagGetType(bag) != __kCFBagImmutable && __CFBagGetType(bag) != __kCFBagFixedMutable, __kCFLogAssertion, "%s(): bag is immutable or fixed-mutable", __PRETTY_FUNCTION__);
 653     CFAssert3(bag->_count <= cap, __kCFLogAssertion, "%s(): desired capacity (%d) is less than count (%d)", __PRETTY_FUNCTION__, cap, bag->_count);
 654 #endif
 655     __CFBagGrow(bag, cap - bag->_count);
 656 }
 657
 658 void CFBagAddValue(CFMutableBagRef bag, const void *value) {
 659     struct __CFBagBucket *match, *nomatch;
 660     CFAllocatorRef allocator;
 661     const CFBagCallBacks *cb;
 662     const void *newValue;
 663     __CFGenericValidateType(bag, __kCFBagTypeID);
 664     switch (__CFBagGetType(bag)) {
 665     case __kCFBagMutable:
 666         if (bag->_bucketsUsed == bag->_capacity || NULL == bag->_buckets) {
 667             __CFBagGrow(bag, 1);
 668         }
 669         break;
 670     case __kCFBagFixedMutable:
 671         CFAssert3(bag->_count < bag->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity bag %p (capacity = %d)", __PRETTY_FUNCTION__, bag, bag->_capacity);
 672         break;
 673     default:
 674         CFAssert2(__CFBagGetType(bag) != __kCFBagImmutable, __kCFLogAssertion, "%s(): immutable bag %p passed to mutating operation", __PRETTY_FUNCTION__, bag);
 675         break;
 676     }
 677     __CFBagFindBuckets2(bag, value, &match, &nomatch);
 678     if (match) {
 679         match->_count++; bag->_count++;
 680     } else {
 681         allocator = CFGetAllocator(bag);
 682         cb = __CFBagGetCallBacks(bag);
 683         if (cb->retain) {
 684             newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, value, bag->_context);
 685         } else {
 686             newValue = value;
 687         }
 688         if (bag->_emptyMarker == newValue) {
 689             __CFBagFindNewEmptyMarker(bag);
 690         }
 691         if (bag->_deletedMarker == newValue) {
 692             __CFBagFindNewDeletedMarker(bag);
 693         }
 694         CF_WRITE_BARRIER_ASSIGN(allocator, nomatch->_key, newValue);
 695         nomatch->_count = 1;
 696         bag->_bucketsUsed++;
 697         bag->_count++;
 698     }
 699 }
 700
 701 void CFBagReplaceValue(CFMutableBagRef bag, const void *value) {
 702     struct __CFBagBucket *match;
 703     CFAllocatorRef allocator;
 704     const CFBagCallBacks *cb;
 705     const void *newValue;
 706     __CFGenericValidateType(bag, __kCFBagTypeID);
 707     switch (__CFBagGetType(bag)) {
 708     case __kCFBagMutable:
 709     case __kCFBagFixedMutable:
 710         break;
 711     default:
 712         CFAssert2(__CFBagGetType(bag) != __kCFBagImmutable, __kCFLogAssertion, "%s(): immutable bag %p passed to mutating operation", __PRETTY_FUNCTION__, bag);
 713         break;
 714     }
 715     if (0 == bag->_count) return;
 716     __CFBagFindBuckets1(bag, value, &match);
 717     if (!match) return;
 718     allocator = CFGetAllocator(bag);
 719     cb = __CFBagGetCallBacks(bag);
 720     if (cb->retain) {
 721         newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, value, bag->_context);
 722     } else {
 723         newValue = value;
 724     }
 725     if (cb->release) {
 726         INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, match->_key, bag->_context);
 727         match->_key = bag->_deletedMarker;
 728     }
 729     if (bag->_emptyMarker == newValue) {
 730         __CFBagFindNewEmptyMarker(bag);
 731     }
 732     if (bag->_deletedMarker == newValue) {
 733         __CFBagFindNewDeletedMarker(bag);
 734     }
 735     CF_WRITE_BARRIER_ASSIGN(allocator, match->_key, newValue);
 736 }
 737
 738 void CFBagSetValue(CFMutableBagRef bag, const void *value) {
 739     struct __CFBagBucket *match, *nomatch;
 740     CFAllocatorRef allocator;
 741     const CFBagCallBacks *cb;
 742     const void *newValue;
 743     __CFGenericValidateType(bag, __kCFBagTypeID);
 744     switch (__CFBagGetType(bag)) {
 745     case __kCFBagMutable:
 746         if (bag->_bucketsUsed == bag->_capacity || NULL == bag->_buckets) {
 747             __CFBagGrow(bag, 1);
 748         }
 749         break;
 750     case __kCFBagFixedMutable:
 751         break;
 752     default:
 753         CFAssert2(__CFBagGetType(bag) != __kCFBagImmutable, __kCFLogAssertion, "%s(): immutable bag %p passed to mutating operation", __PRETTY_FUNCTION__, bag);
 754         break;
 755     }
 756     __CFBagFindBuckets2(bag, value, &match, &nomatch);
 757     allocator = CFGetAllocator(bag);
 758     cb = __CFBagGetCallBacks(bag);
 759     if (cb->retain) {
 760         newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, value, bag->_context);
 761     } else {
 762         newValue = value;
 763     }
 764     if (match) {
 765         if (cb->release) {
 766             INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, match->_key, bag->_context);
 767             match->_key = bag->_deletedMarker;
 768         }
 769         if (bag->_emptyMarker == newValue) {
 770             __CFBagFindNewEmptyMarker(bag);
 771         }
 772         if (bag->_deletedMarker == newValue) {
 773             __CFBagFindNewDeletedMarker(bag);
 774         }
 775         CF_WRITE_BARRIER_ASSIGN(allocator, match->_key, newValue);
 776     } else {
 777         CFAssert3(__kCFBagFixedMutable != __CFBagGetType(bag) || bag->_count < bag->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity bag %p (capacity = %d)", __PRETTY_FUNCTION__, bag, bag->_capacity);
 778         if (bag->_emptyMarker == newValue) {
 779             __CFBagFindNewEmptyMarker(bag);
 780         }
 781         if (bag->_deletedMarker == newValue) {
 782             __CFBagFindNewDeletedMarker(bag);
 783         }
 784         CF_WRITE_BARRIER_ASSIGN(allocator, nomatch->_key, newValue);
 785         nomatch->_count = 1;
 786         bag->_bucketsUsed++;
 787         bag->_count++;
 788     }
 789 }
 790
 791 void CFBagRemoveValue(CFMutableBagRef bag, const void *value) {
 792     struct __CFBagBucket *match;
 793     const CFBagCallBacks *cb;
 794     __CFGenericValidateType(bag, __kCFBagTypeID);
 795     switch (__CFBagGetType(bag)) {
 796     case __kCFBagMutable:
 797     case __kCFBagFixedMutable:
 798         break;
 799     default:
 800         CFAssert2(__CFBagGetType(bag) != __kCFBagImmutable, __kCFLogAssertion, "%s(): immutable bag %p passed to mutating operation", __PRETTY_FUNCTION__, bag);
 801         break;
 802     }
 803     if (0 == bag->_count) return;
 804     __CFBagFindBuckets1(bag, value, &match);
 805     if (!match) return;
 806     match->_count--; bag->_count--;
 807     if (0 == match->_count) {
 808         cb = __CFBagGetCallBacks(bag);
 809         if (cb->release) {
 810             INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), CFGetAllocator(bag), match->_key, bag->_context);
 811         }
 812         match->_key = bag->_deletedMarker;
 813         bag->_bucketsUsed--;
 814     }
 815 }
 816
 817 void CFBagRemoveAllValues(CFMutableBagRef bag) {
 818     struct __CFBagBucket *buckets;
 819     const CFBagCallBacks *cb;
 820     CFAllocatorRef allocator;
 821     CFIndex idx, nbuckets;
 822     __CFGenericValidateType(bag, __kCFBagTypeID);
 823     switch (__CFBagGetType(bag)) {
 824     case __kCFBagMutable:
 825     case __kCFBagFixedMutable:
 826         break;
 827     default:
 828         CFAssert2(__CFBagGetType(bag) != __kCFBagImmutable, __kCFLogAssertion, "%s(): immutable bag %p passed to mutating operation", __PRETTY_FUNCTION__, bag);
 829         break;
 830     }
 831     if (0 == bag->_count) return;
 832     buckets = bag->_buckets;
 833     nbuckets = bag->_bucketsNum;
 834     cb = __CFBagGetCallBacks(bag);
 835     allocator = CFGetAllocator(bag);
 836     for (idx = 0; idx < nbuckets; idx++) {
 837         if (__CFBagBucketIsOccupied(bag, &buckets[idx])) {
 838             if (cb->release) {
 839                 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, buckets[idx]._key, bag->_context);
 840             }
 841             buckets[idx]._key = bag->_emptyMarker;
 842             buckets[idx]._count = 0;
 843         }
 844     }
 845     bag->_bucketsUsed = 0;
 846     bag->_count = 0;
 847 }
 848