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