CFBag.c

   1 /*
   2  * Copyright (c) 2008 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*      CFBag.c
  24         Copyright 1998-2006, Apple, Inc. All rights reserved.
  25         Responsibility: Christopher Kane
  26         Machine generated from Notes/HashingCode.template
  27 */
  28
  29
  30
  31
  32 #include <CoreFoundation/CFBag.h>
  33 #include "CFInternal.h"
  34 #include <mach-o/dyld.h>
  35
  36 #define CFDictionary 0
  37 #define CFSet 0
  38 #define CFBag 0
  39 #undef CFBag
  40 #define CFBag 1
  41
  42 #if CFDictionary
  43 const CFBagKeyCallBacks kCFTypeBagKeyCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  44 const CFBagKeyCallBacks kCFCopyStringBagKeyCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  45 const CFBagValueCallBacks kCFTypeBagValueCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual};
  46 static const CFBagKeyCallBacks __kCFNullBagKeyCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
  47 static const CFBagValueCallBacks __kCFNullBagValueCallBacks = {0, NULL, NULL, NULL, NULL};
  48
  49 #define CFHashRef CFDictionaryRef
  50 #define CFMutableHashRef CFMutableDictionaryRef
  51 #define __kCFHashTypeID __kCFDictionaryTypeID
  52 #endif
  53
  54 #if CFSet
  55 const CFBagCallBacks kCFTypeBagCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  56 const CFBagCallBacks kCFCopyStringBagCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  57 static const CFBagCallBacks __kCFNullBagCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
  58
  59 #define CFBagKeyCallBacks CFBagCallBacks
  60 #define CFBagValueCallBacks CFBagCallBacks
  61 #define kCFTypeBagKeyCallBacks kCFTypeBagCallBacks
  62 #define kCFTypeBagValueCallBacks kCFTypeBagCallBacks
  63 #define __kCFNullBagKeyCallBacks __kCFNullBagCallBacks
  64 #define __kCFNullBagValueCallBacks __kCFNullBagCallBacks
  65
  66 #define CFHashRef CFSetRef
  67 #define CFMutableHashRef CFMutableSetRef
  68 #define __kCFHashTypeID __kCFSetTypeID
  69 #endif
  70
  71 #if CFBag
  72 const CFBagCallBacks kCFTypeBagCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  73 const CFBagCallBacks kCFCopyStringBagCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  74 static const CFBagCallBacks __kCFNullBagCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
  75
  76 #define CFBagKeyCallBacks CFBagCallBacks
  77 #define CFBagValueCallBacks CFBagCallBacks
  78 #define kCFTypeBagKeyCallBacks kCFTypeBagCallBacks
  79 #define kCFTypeBagValueCallBacks kCFTypeBagCallBacks
  80 #define __kCFNullBagKeyCallBacks __kCFNullBagCallBacks
  81 #define __kCFNullBagValueCallBacks __kCFNullBagCallBacks
  82
  83 #define CFHashRef CFBagRef
  84 #define CFMutableHashRef CFMutableBagRef
  85 #define __kCFHashTypeID __kCFBagTypeID
  86 #endif
  87
  88 #define GETNEWKEY(newKey, oldKey) \
  89         any_t (*kretain)(CFAllocatorRef, any_t, any_pointer_t) = \
  90           !hasBeenFinalized(hc) \
  91             ? (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))__CFBagGetKeyCallBacks(hc)->retain \
  92             : (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
  93         any_t newKey = kretain ? (any_t)INVOKE_CALLBACK3(kretain, allocator, (any_t)key, hc->_context) : (any_t)oldKey
  94
  95 #define RELEASEKEY(oldKey) \
  96         void (*krelease)(CFAllocatorRef, any_t, any_pointer_t) = \
  97           !hasBeenFinalized(hc) \
  98             ? (void (*)(CFAllocatorRef,any_t,any_pointer_t))__CFBagGetKeyCallBacks(hc)->release \
  99             : (void (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
 100         if (krelease) INVOKE_CALLBACK3(krelease, allocator, oldKey, hc->_context)
 101
 102 #if CFDictionary
 103 #define GETNEWVALUE(newValue) \
 104         any_t (*vretain)(CFAllocatorRef, any_t, any_pointer_t) = \
 105           !hasBeenFinalized(hc) \
 106             ? (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))__CFBagGetValueCallBacks(hc)->retain \
 107             : (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
 108         any_t newValue = vretain ? (any_t)INVOKE_CALLBACK3(vretain, allocator, (any_t)value, hc->_context) : (any_t)value
 109
 110 #define RELEASEVALUE(oldValue) \
 111     void (*vrelease)(CFAllocatorRef, any_t, any_pointer_t) = \
 112       !hasBeenFinalized(hc) \
 113         ? (void (*)(CFAllocatorRef,any_t,any_pointer_t))__CFBagGetValueCallBacks(hc)->release \
 114         : (void (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
 115     if (vrelease) INVOKE_CALLBACK3(vrelease, allocator, oldValue, hc->_context)
 116
 117 #endif
 118
 119 static void __CFBagHandleOutOfMemory(CFTypeRef obj, CFIndex numBytes) {
 120     CFStringRef msg = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("Attempt to allocate %ld bytes for NS/CFBag failed"), numBytes);
 121     CFBadErrorCallBack cb = _CFGetOutOfMemoryErrorCallBack();
 122     if (NULL == cb || !cb(obj, CFSTR("NS/CFBag"), msg)) {
 123         CFLog(kCFLogLevelCritical, CFSTR("%@"), msg);
 124         HALT;
 125     }
 126     CFRelease(msg);
 127 }
 128
 129
 130 // Max load is 3/4 number of buckets
 131 CF_INLINE CFIndex __CFHashRoundUpCapacity(CFIndex capacity) {
 132     return 3 * ((CFIndex)1 << (flsl((capacity - 1) / 3)));
 133 }
 134
 135 // Returns next power of two higher than the capacity
 136 // threshold for the given input capacity.
 137 CF_INLINE CFIndex __CFHashNumBucketsForCapacity(CFIndex capacity) {
 138     return 4 * ((CFIndex)1 << (flsl((capacity - 1) / 3)));
 139 }
 140
 141 enum {                /* Bits 1-0 */
 142     __kCFHashImmutable = 0,        /* unchangable and fixed capacity */
 143     __kCFHashMutable = 1,                /* changeable and variable capacity */
 144 };
 145
 146 enum {                /* Bits 5-4 (value), 3-2 (key) */
 147     __kCFHashHasNullCallBacks = 0,
 148     __kCFHashHasCFTypeCallBacks = 1,
 149     __kCFHashHasCustomCallBacks = 3        /* callbacks are at end of header */
 150 };
 151
 152 // Under GC, we fudge the key/value memory in two ways
 153 // First, if we had null callbacks or null for both retain/release, we use unscanned memory and get
 154 // standard 'dangling' references.
 155 // This means that if people were doing addValue:[xxx new] and never removing, well, that doesn't work
 156 //
 157 // Second, if we notice standard retain/release implementations we use scanned memory, and fudge the
 158 // standard callbacks to generally do nothing if the collection was allocated in GC memory. On special
 159 // CF objects, however, like those used for precious resources like video-card buffers, we do indeed
 160 // do CFRetain on input and CFRelease on output.  The tricky case is GC finalization; we need to remember
 161 // that we did the CFReleases so that subsequent collection operations, like removal, don't double CFRelease.
 162 // (In fact we don't really use CFRetain/CFRelease but go directly to the collector)
 163 //
 164
 165 enum {
 166     __kCFHashFinalized =         (1 << 7),
 167     __kCFHashWeakKeys =          (1 << 8),
 168     __kCFHashWeakValues =        (1 << 9)
 169 };
 170
 171 typedef uintptr_t any_t;
 172 typedef const void * const_any_pointer_t;
 173 typedef void * any_pointer_t;
 174
 175 struct __CFBag {
 176     CFRuntimeBase _base;
 177     CFIndex _count;             /* number of values */
 178     CFIndex _bucketsNum;        /* number of buckets */
 179     CFIndex _bucketsUsed;       /* number of used buckets */
 180     CFIndex _bucketsCap;        /* maximum number of used buckets */
 181     CFIndex _mutations;
 182     CFIndex _deletes;
 183     any_pointer_t _context;     /* private */
 184     CFOptionFlags _xflags;
 185     any_t _marker;
 186     any_t *_keys;     /* can be NULL if not allocated yet */
 187     any_t *_values;   /* can be NULL if not allocated yet */
 188 };
 189
 190 /* Bits 1-0 of the _xflags are used for mutability variety */
 191 /* Bits 3-2 of the _xflags are used for key callback indicator bits */
 192 /* Bits 5-4 of the _xflags are used for value callback indicator bits */
 193 /* Bit 6 of the _xflags is special KVO actions bit */
 194 /* Bits 7,8,9 are GC use */
 195
 196 CF_INLINE bool hasBeenFinalized(CFTypeRef collection) {
 197     return __CFBitfieldGetValue(((const struct __CFBag *)collection)->_xflags, 7, 7) != 0;
 198 }
 199
 200 CF_INLINE void markFinalized(CFTypeRef collection) {
 201     __CFBitfieldSetValue(((struct __CFBag *)collection)->_xflags, 7, 7, 1);
 202 }
 203
 204
 205 CF_INLINE CFIndex __CFHashGetType(CFHashRef hc) {
 206     return __CFBitfieldGetValue(hc->_xflags, 1, 0);
 207 }
 208
 209 CF_INLINE CFIndex __CFBagGetSizeOfType(CFIndex t) {
 210     CFIndex size = sizeof(struct __CFBag);
 211     if (__CFBitfieldGetValue(t, 3, 2) == __kCFHashHasCustomCallBacks) {
 212         size += sizeof(CFBagKeyCallBacks);
 213     }
 214     if (__CFBitfieldGetValue(t, 5, 4) == __kCFHashHasCustomCallBacks) {
 215         size += sizeof(CFBagValueCallBacks);
 216     }
 217     return size;
 218 }
 219
 220 CF_INLINE const CFBagKeyCallBacks *__CFBagGetKeyCallBacks(CFHashRef hc) {
 221     CFBagKeyCallBacks *result = NULL;
 222     switch (__CFBitfieldGetValue(hc->_xflags, 3, 2)) {
 223     case __kCFHashHasNullCallBacks:
 224         return &__kCFNullBagKeyCallBacks;
 225     case __kCFHashHasCFTypeCallBacks:
 226         return &kCFTypeBagKeyCallBacks;
 227     case __kCFHashHasCustomCallBacks:
 228         break;
 229     }
 230     result = (CFBagKeyCallBacks *)((uint8_t *)hc + sizeof(struct __CFBag));
 231     return result;
 232 }
 233
 234 CF_INLINE Boolean __CFBagKeyCallBacksMatchNull(const CFBagKeyCallBacks *c) {
 235     return (NULL == c ||
 236         (c->retain == __kCFNullBagKeyCallBacks.retain &&
 237          c->release == __kCFNullBagKeyCallBacks.release &&
 238          c->copyDescription == __kCFNullBagKeyCallBacks.copyDescription &&
 239          c->equal == __kCFNullBagKeyCallBacks.equal &&
 240          c->hash == __kCFNullBagKeyCallBacks.hash));
 241 }
 242
 243 CF_INLINE Boolean __CFBagKeyCallBacksMatchCFType(const CFBagKeyCallBacks *c) {
 244     return (&kCFTypeBagKeyCallBacks == c ||
 245         (c->retain == kCFTypeBagKeyCallBacks.retain &&
 246          c->release == kCFTypeBagKeyCallBacks.release &&
 247          c->copyDescription == kCFTypeBagKeyCallBacks.copyDescription &&
 248          c->equal == kCFTypeBagKeyCallBacks.equal &&
 249          c->hash == kCFTypeBagKeyCallBacks.hash));
 250 }
 251
 252 CF_INLINE const CFBagValueCallBacks *__CFBagGetValueCallBacks(CFHashRef hc) {
 253     CFBagValueCallBacks *result = NULL;
 254     switch (__CFBitfieldGetValue(hc->_xflags, 5, 4)) {
 255     case __kCFHashHasNullCallBacks:
 256         return &__kCFNullBagValueCallBacks;
 257     case __kCFHashHasCFTypeCallBacks:
 258         return &kCFTypeBagValueCallBacks;
 259     case __kCFHashHasCustomCallBacks:
 260         break;
 261     }
 262     if (__CFBitfieldGetValue(hc->_xflags, 3, 2) == __kCFHashHasCustomCallBacks) {
 263         result = (CFBagValueCallBacks *)((uint8_t *)hc + sizeof(struct __CFBag) + sizeof(CFBagKeyCallBacks));
 264     } else {
 265         result = (CFBagValueCallBacks *)((uint8_t *)hc + sizeof(struct __CFBag));
 266     }
 267     return result;
 268 }
 269
 270 CF_INLINE Boolean __CFBagValueCallBacksMatchNull(const CFBagValueCallBacks *c) {
 271     return (NULL == c ||
 272         (c->retain == __kCFNullBagValueCallBacks.retain &&
 273          c->release == __kCFNullBagValueCallBacks.release &&
 274          c->copyDescription == __kCFNullBagValueCallBacks.copyDescription &&
 275          c->equal == __kCFNullBagValueCallBacks.equal));
 276 }
 277
 278 CF_INLINE Boolean __CFBagValueCallBacksMatchCFType(const CFBagValueCallBacks *c) {
 279     return (&kCFTypeBagValueCallBacks == c ||
 280         (c->retain == kCFTypeBagValueCallBacks.retain &&
 281          c->release == kCFTypeBagValueCallBacks.release &&
 282          c->copyDescription == kCFTypeBagValueCallBacks.copyDescription &&
 283          c->equal == kCFTypeBagValueCallBacks.equal));
 284 }
 285
 286 CFIndex _CFBagGetKVOBit(CFHashRef hc) {
 287     return __CFBitfieldGetValue(hc->_xflags, 6, 6);
 288 }
 289
 290 void _CFBagSetKVOBit(CFHashRef hc, CFIndex bit) {
 291     __CFBitfieldSetValue(((CFMutableHashRef)hc)->_xflags, 6, 6, ((uintptr_t)bit & 0x1));
 292 }
 293
 294 CF_INLINE Boolean __CFBagShouldShrink(CFHashRef hc) {
 295     return (__kCFHashMutable == __CFHashGetType(hc)) &&
 296                 !(CF_USING_COLLECTABLE_MEMORY && auto_zone_is_finalized(__CFCollectableZone, hc)) && /* GC:  don't shrink finalizing hcs! */
 297                 (hc->_bucketsNum < 4 * hc->_deletes || (256 <= hc->_bucketsCap && hc-> _bucketsUsed < 3 * hc->_bucketsCap / 16));
 298 }
 299
 300 CF_INLINE CFIndex __CFHashGetOccurrenceCount(CFHashRef hc, CFIndex idx) {
 301 #if CFBag
 302     return hc->_values[idx];
 303 #endif
 304     return 1;
 305 }
 306
 307 CF_INLINE Boolean __CFHashKeyIsValue(CFHashRef hc, any_t key) {
 308     return (hc->_marker != key && ~hc->_marker != key) ? true : false;
 309 }
 310
 311 CF_INLINE Boolean __CFHashKeyIsMagic(CFHashRef hc, any_t key) {
 312     return (hc->_marker == key || ~hc->_marker == key) ? true : false;
 313 }
 314
 315
 316 #if !defined(CF_OBJC_KVO_WILLCHANGE)
 317 #define CF_OBJC_KVO_WILLCHANGE(obj, key)
 318 #define CF_OBJC_KVO_DIDCHANGE(obj, key)
 319 #endif
 320
 321 CF_INLINE uintptr_t __CFBagScrambleHash(uintptr_t k) {
 322 #if 0
 323     return k;
 324 #else
 325 #if __LP64__
 326     uintptr_t a = 0x4368726973746F70ULL;
 327     uintptr_t b = 0x686572204B616E65ULL;
 328 #else
 329     uintptr_t a = 0x4B616E65UL;
 330     uintptr_t b = 0x4B616E65UL;
 331 #endif
 332     uintptr_t c = 1;
 333     a += k;
 334 #if __LP64__
 335     a -= b; a -= c; a ^= (c >> 43);
 336     b -= c; b -= a; b ^= (a << 9);
 337     c -= a; c -= b; c ^= (b >> 8);
 338     a -= b; a -= c; a ^= (c >> 38);
 339     b -= c; b -= a; b ^= (a << 23);
 340     c -= a; c -= b; c ^= (b >> 5);
 341     a -= b; a -= c; a ^= (c >> 35);
 342     b -= c; b -= a; b ^= (a << 49);
 343     c -= a; c -= b; c ^= (b >> 11);
 344     a -= b; a -= c; a ^= (c >> 12);
 345     b -= c; b -= a; b ^= (a << 18);
 346     c -= a; c -= b; c ^= (b >> 22);
 347 #else
 348     a -= b; a -= c; a ^= (c >> 13);
 349     b -= c; b -= a; b ^= (a << 8);
 350     c -= a; c -= b; c ^= (b >> 13);
 351     a -= b; a -= c; a ^= (c >> 12);
 352     b -= c; b -= a; b ^= (a << 16);
 353     c -= a; c -= b; c ^= (b >> 5);
 354     a -= b; a -= c; a ^= (c >> 3);
 355     b -= c; b -= a; b ^= (a << 10);
 356     c -= a; c -= b; c ^= (b >> 15);
 357 #endif
 358     return c;
 359 #endif
 360 }
 361
 362 static CFIndex __CFBagFindBuckets1a(CFHashRef hc, any_t key) {
 363     CFHashCode keyHash = (CFHashCode)key;
 364     keyHash = __CFBagScrambleHash(keyHash);
 365     any_t *keys = hc->_keys;
 366     any_t marker = hc->_marker;
 367     CFIndex probe = keyHash & (hc->_bucketsNum - 1);
 368     CFIndex probeskip = 1;        // See RemoveValue() for notes before changing this value
 369     CFIndex start = probe;
 370     for (;;) {
 371         any_t currKey = keys[probe];
 372         if (marker == currKey) {                /* empty */
 373             return kCFNotFound;
 374         } else if (~marker == currKey) {        /* deleted */
 375             /* do nothing */
 376         } else if (currKey == key) {
 377             return probe;
 378         }
 379         probe = probe + probeskip;
 380         // This alternative to probe % buckets assumes that
 381         // probeskip is always positive and less than the
 382         // number of buckets.
 383         if (hc->_bucketsNum <= probe) {
 384             probe -= hc->_bucketsNum;
 385         }
 386         if (start == probe) {
 387             return kCFNotFound;
 388         }
 389     }
 390 }
 391
 392 static CFIndex __CFBagFindBuckets1b(CFHashRef hc, any_t key) {
 393     const CFBagKeyCallBacks *cb = __CFBagGetKeyCallBacks(hc);
 394     CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(any_t, any_pointer_t))cb->hash), key, hc->_context) : (CFHashCode)key;
 395     keyHash = __CFBagScrambleHash(keyHash);
 396     any_t *keys = hc->_keys;
 397     any_t marker = hc->_marker;
 398     CFIndex probe = keyHash & (hc->_bucketsNum - 1);
 399     CFIndex probeskip = 1;        // See RemoveValue() for notes before changing this value
 400     CFIndex start = probe;
 401     for (;;) {
 402         any_t currKey = keys[probe];
 403         if (marker == currKey) {                /* empty */
 404             return kCFNotFound;
 405         } else if (~marker == currKey) {        /* deleted */
 406             /* do nothing */
 407         } else if (currKey == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))cb->equal, currKey, key, hc->_context))) {
 408             return probe;
 409         }
 410         probe = probe + probeskip;
 411         // This alternative to probe % buckets assumes that
 412         // probeskip is always positive and less than the
 413         // number of buckets.
 414         if (hc->_bucketsNum <= probe) {
 415             probe -= hc->_bucketsNum;
 416         }
 417         if (start == probe) {
 418             return kCFNotFound;
 419         }
 420     }
 421 }
 422
 423 CF_INLINE CFIndex __CFBagFindBuckets1(CFHashRef hc, any_t key) {
 424     if (__kCFHashHasNullCallBacks == __CFBitfieldGetValue(hc->_xflags, 3, 2)) {
 425         return __CFBagFindBuckets1a(hc, key);
 426     }
 427     return __CFBagFindBuckets1b(hc, key);
 428 }
 429
 430 static void __CFBagFindBuckets2(CFHashRef hc, any_t key, CFIndex *match, CFIndex *nomatch) {
 431     const CFBagKeyCallBacks *cb = __CFBagGetKeyCallBacks(hc);
 432     CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(any_t, any_pointer_t))cb->hash), key, hc->_context) : (CFHashCode)key;
 433     keyHash = __CFBagScrambleHash(keyHash);
 434     any_t *keys = hc->_keys;
 435     any_t marker = hc->_marker;
 436     CFIndex probe = keyHash & (hc->_bucketsNum - 1);
 437     CFIndex probeskip = 1;        // See RemoveValue() for notes before changing this value
 438     CFIndex start = probe;
 439     *match = kCFNotFound;
 440     *nomatch = kCFNotFound;
 441     for (;;) {
 442         any_t currKey = keys[probe];
 443         if (marker == currKey) {                /* empty */
 444             if (nomatch) *nomatch = probe;
 445             return;
 446         } else if (~marker == currKey) {        /* deleted */
 447             if (nomatch) {
 448                 *nomatch = probe;
 449                 nomatch = NULL;
 450             }
 451         } else if (currKey == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))cb->equal, currKey, key, hc->_context))) {
 452             *match = probe;
 453             return;
 454         }
 455         probe = probe + probeskip;
 456         // This alternative to probe % buckets assumes that
 457         // probeskip is always positive and less than the
 458         // number of buckets.
 459         if (hc->_bucketsNum <= probe) {
 460             probe -= hc->_bucketsNum;
 461         }
 462         if (start == probe) {
 463             return;
 464         }
 465     }
 466 }
 467
 468 static void __CFBagFindNewMarker(CFHashRef hc) {
 469     any_t *keys = hc->_keys;
 470     any_t newMarker;
 471     CFIndex idx, nbuckets;
 472     Boolean hit;
 473
 474     nbuckets = hc->_bucketsNum;
 475     newMarker = hc->_marker;
 476     do {
 477         newMarker--;
 478         hit = false;
 479         for (idx = 0; idx < nbuckets; idx++) {
 480             if (newMarker == keys[idx] || ~newMarker == keys[idx]) {
 481                 hit = true;
 482                 break;
 483             }
 484         }
 485     } while (hit);
 486     for (idx = 0; idx < nbuckets; idx++) {
 487         if (hc->_marker == keys[idx]) {
 488             keys[idx] = newMarker;
 489         } else if (~hc->_marker == keys[idx]) {
 490             keys[idx] = ~newMarker;
 491         }
 492     }
 493     ((struct __CFBag *)hc)->_marker = newMarker;
 494 }
 495
 496 static Boolean __CFBagEqual(CFTypeRef cf1, CFTypeRef cf2) {
 497     CFHashRef hc1 = (CFHashRef)cf1;
 498     CFHashRef hc2 = (CFHashRef)cf2;
 499     const CFBagKeyCallBacks *cb1, *cb2;
 500     const CFBagValueCallBacks *vcb1, *vcb2;
 501     any_t *keys;
 502     CFIndex idx, nbuckets;
 503     if (hc1 == hc2) return true;
 504     if (hc1->_count != hc2->_count) return false;
 505     cb1 = __CFBagGetKeyCallBacks(hc1);
 506     cb2 = __CFBagGetKeyCallBacks(hc2);
 507     if (cb1->equal != cb2->equal) return false;
 508     vcb1 = __CFBagGetValueCallBacks(hc1);
 509     vcb2 = __CFBagGetValueCallBacks(hc2);
 510     if (vcb1->equal != vcb2->equal) return false;
 511     if (0 == hc1->_bucketsUsed) return true; /* after function comparison! */
 512     keys = hc1->_keys;
 513     nbuckets = hc1->_bucketsNum;
 514     for (idx = 0; idx < nbuckets; idx++) {
 515         if (hc1->_marker != keys[idx] && ~hc1->_marker != keys[idx]) {
 516 #if CFDictionary
 517             const_any_pointer_t value;
 518             if (!CFBagGetValueIfPresent(hc2, (any_pointer_t)keys[idx], &value)) return false;
 519             if (hc1->_values[idx] != (any_t)value) {
 520                 if (NULL == vcb1->equal) return false;
 521                 if (!INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))vcb1->equal, hc1->_values[idx], (any_t)value, hc1->_context)) return false;
 522             }
 523 #endif
 524 #if  CFSet
 525             const_any_pointer_t value;
 526             if (!CFBagGetValueIfPresent(hc2, (any_pointer_t)keys[idx], &value)) return false;
 527 #endif
 528 #if CFBag
 529             if (hc1->_values[idx] != CFBagGetCountOfValue(hc2, (any_pointer_t)keys[idx])) return false;
 530 #endif
 531         }
 532     }
 533     return true;
 534 }
 535
 536 static CFHashCode __CFBagHash(CFTypeRef cf) {
 537     CFHashRef hc = (CFHashRef)cf;
 538     return hc->_count;
 539 }
 540
 541 static CFStringRef __CFBagCopyDescription(CFTypeRef cf) {
 542     CFHashRef hc = (CFHashRef)cf;
 543     CFAllocatorRef allocator;
 544     const CFBagKeyCallBacks *cb;
 545     const CFBagValueCallBacks *vcb;
 546     any_t *keys;
 547     CFIndex idx, nbuckets;
 548     CFMutableStringRef result;
 549     cb = __CFBagGetKeyCallBacks(hc);
 550     vcb = __CFBagGetValueCallBacks(hc);
 551     keys = hc->_keys;
 552     nbuckets = hc->_bucketsNum;
 553     allocator = CFGetAllocator(hc);
 554     result = CFStringCreateMutable(allocator, 0);
 555     const char *type = "?";
 556     switch (__CFHashGetType(hc)) {
 557     case __kCFHashImmutable: type = "immutable"; break;
 558     case __kCFHashMutable: type = "mutable"; break;
 559     }
 560     CFStringAppendFormat(result, NULL, CFSTR("<CFBag %p [%p]>{type = %s, count = %u, capacity = %u, pairs = (\n"), cf, allocator, type, hc->_count, hc->_bucketsCap);
 561     for (idx = 0; idx < nbuckets; idx++) {
 562         if (__CFHashKeyIsValue(hc, keys[idx])) {
 563             CFStringRef kDesc = NULL, vDesc = NULL;
 564             if (NULL != cb->copyDescription) {
 565                 kDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(any_t, any_pointer_t))cb->copyDescription), keys[idx], hc->_context);
 566             }
 567             if (NULL != vcb->copyDescription) {
 568                 vDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(any_t, any_pointer_t))vcb->copyDescription), hc->_values[idx], hc->_context);
 569             }
 570 #if CFDictionary
 571             if (NULL != kDesc && NULL != vDesc) {
 572                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = %@\n"), idx, kDesc, vDesc);
 573                 CFRelease(kDesc);
 574                 CFRelease(vDesc);
 575             } else if (NULL != kDesc) {
 576                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = <%p>\n"), idx, kDesc, hc->_values[idx]);
 577                 CFRelease(kDesc);
 578             } else if (NULL != vDesc) {
 579                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = %@\n"), idx, keys[idx], vDesc);
 580                 CFRelease(vDesc);
 581             } else {
 582                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = <%p>\n"), idx, keys[idx], hc->_values[idx]);
 583             }
 584 #endif
 585 #if CFSet
 586             if (NULL != kDesc) {
 587                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@\n"), idx, kDesc);
 588                 CFRelease(kDesc);
 589             } else {
 590                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, keys[idx]);
 591             }
 592 #endif
 593 #if CFBag
 594             if (NULL != kDesc) {
 595                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ (%ld)\n"), idx, kDesc, hc->_values[idx]);
 596                 CFRelease(kDesc);
 597             } else {
 598                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> (%ld)\n"), idx, keys[idx], hc->_values[idx]);
 599             }
 600 #endif
 601         }
 602     }
 603     CFStringAppend(result, CFSTR(")}"));
 604     return result;
 605 }
 606
 607 static void __CFBagDeallocate(CFTypeRef cf) {
 608     CFMutableHashRef hc = (CFMutableHashRef)cf;
 609     CFAllocatorRef allocator = __CFGetAllocator(hc);
 610     const CFBagKeyCallBacks *cb = __CFBagGetKeyCallBacks(hc);
 611     const CFBagValueCallBacks *vcb = __CFBagGetValueCallBacks(hc);
 612
 613     // mark now in case any callout somehow tries to add an entry back in
 614     markFinalized(cf);
 615     if (vcb->release || cb->release) {
 616         any_t *keys = hc->_keys;
 617         CFIndex idx, nbuckets = hc->_bucketsNum;
 618         for (idx = 0; idx < nbuckets; idx++) {
 619             any_t oldkey = keys[idx];
 620             if (hc->_marker != oldkey && ~hc->_marker != oldkey) {
 621                 if (vcb->release) {
 622                     INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, any_t, any_pointer_t))vcb->release), allocator, hc->_values[idx], hc->_context);
 623                 }
 624                 if (cb->release) {
 625                     INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, any_t, any_pointer_t))cb->release), allocator, oldkey, hc->_context);
 626                 }
 627             }
 628         }
 629     }
 630
 631     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 632         // return early so that contents are preserved after finalization
 633         return;
 634     }
 635
 636     _CFAllocatorDeallocateGC(allocator, hc->_keys);
 637 #if CFDictionary || CFBag
 638     _CFAllocatorDeallocateGC(allocator, hc->_values);
 639 #endif
 640     hc->_keys = NULL;
 641     hc->_values = NULL;
 642     hc->_count = 0;  // GC: also zero count, so the hc will appear empty.
 643     hc->_bucketsUsed = 0;
 644     hc->_bucketsNum = 0;
 645 }
 646
 647 static CFTypeID __kCFBagTypeID = _kCFRuntimeNotATypeID;
 648
 649 static const CFRuntimeClass __CFBagClass = {
 650     _kCFRuntimeScannedObject,
 651     "CFBag",
 652     NULL,        // init
 653     NULL,        // copy
 654     __CFBagDeallocate,
 655     __CFBagEqual,
 656     __CFBagHash,
 657     NULL,        //
 658     __CFBagCopyDescription
 659 };
 660
 661 __private_extern__ void __CFBagInitialize(void) {
 662     __kCFHashTypeID = _CFRuntimeRegisterClass(&__CFBagClass);
 663 }
 664
 665 CFTypeID CFBagGetTypeID(void) {
 666     return __kCFHashTypeID;
 667 }
 668
 669 static CFMutableHashRef __CFBagInit(CFAllocatorRef allocator, CFOptionFlags flags, CFIndex capacity, const CFBagKeyCallBacks *keyCallBacks
 670 #if CFDictionary
 671 , const CFBagValueCallBacks *valueCallBacks
 672 #endif
 673 ) {
 674     struct __CFBag *hc;
 675     CFIndex size;
 676     __CFBitfieldSetValue(flags, 31, 2, 0);
 677     CFOptionFlags xflags = 0;
 678     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 679         // preserve NULL for key or value CB, otherwise fix up.
 680         if (!keyCallBacks || (keyCallBacks->retain == NULL && keyCallBacks->release == NULL)) {
 681             xflags = __kCFHashWeakKeys;
 682         }
 683 #if CFDictionary
 684         if (!valueCallBacks || (valueCallBacks->retain == NULL && valueCallBacks->release == NULL)) {
 685             xflags |= __kCFHashWeakValues;
 686         }
 687 #endif
 688 #if CFBag
 689         xflags |= __kCFHashWeakValues;
 690 #endif
 691     }
 692     if (__CFBagKeyCallBacksMatchNull(keyCallBacks)) {
 693         __CFBitfieldSetValue(flags, 3, 2, __kCFHashHasNullCallBacks);
 694     } else if (__CFBagKeyCallBacksMatchCFType(keyCallBacks)) {
 695         __CFBitfieldSetValue(flags, 3, 2, __kCFHashHasCFTypeCallBacks);
 696     } else {
 697         __CFBitfieldSetValue(flags, 3, 2, __kCFHashHasCustomCallBacks);
 698     }
 699 #if CFDictionary
 700     if (__CFBagValueCallBacksMatchNull(valueCallBacks)) {
 701         __CFBitfieldSetValue(flags, 5, 4, __kCFHashHasNullCallBacks);
 702     } else if (__CFBagValueCallBacksMatchCFType(valueCallBacks)) {
 703         __CFBitfieldSetValue(flags, 5, 4, __kCFHashHasCFTypeCallBacks);
 704     } else {
 705         __CFBitfieldSetValue(flags, 5, 4, __kCFHashHasCustomCallBacks);
 706     }
 707 #endif
 708     size = __CFBagGetSizeOfType(flags) - sizeof(CFRuntimeBase);
 709     hc = (struct __CFBag *)_CFRuntimeCreateInstance(allocator, __kCFHashTypeID, size, NULL);
 710     if (NULL == hc) {
 711         return NULL;
 712     }
 713     hc->_count = 0;
 714     hc->_bucketsUsed = 0;
 715     hc->_marker = (any_t)0xa1b1c1d3;
 716     hc->_context = NULL;
 717     hc->_deletes = 0;
 718     hc->_mutations = 1;
 719     hc->_xflags = xflags | flags;
 720     switch (__CFBitfieldGetValue(flags, 1, 0)) {
 721     case __kCFHashImmutable:
 722         if (__CFOASafe) __CFSetLastAllocationEventName(hc, "CFBag (immutable)");
 723         break;
 724     case __kCFHashMutable:
 725         if (__CFOASafe) __CFSetLastAllocationEventName(hc, "CFBag (mutable-variable)");
 726         break;
 727     }
 728     hc->_bucketsCap = __CFHashRoundUpCapacity(1);
 729     hc->_bucketsNum = 0;
 730     hc->_keys = NULL;
 731     hc->_values = NULL;
 732     if (__kCFHashHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
 733         CFBagKeyCallBacks *cb = (CFBagKeyCallBacks *)__CFBagGetKeyCallBacks((CFHashRef)hc);
 734         *cb = *keyCallBacks;
 735         FAULT_CALLBACK((void **)&(cb->retain));
 736         FAULT_CALLBACK((void **)&(cb->release));
 737         FAULT_CALLBACK((void **)&(cb->copyDescription));
 738         FAULT_CALLBACK((void **)&(cb->equal));
 739         FAULT_CALLBACK((void **)&(cb->hash));
 740     }
 741 #if CFDictionary
 742     if (__kCFHashHasCustomCallBacks == __CFBitfieldGetValue(flags, 5, 4)) {
 743         CFBagValueCallBacks *vcb = (CFBagValueCallBacks *)__CFBagGetValueCallBacks((CFHashRef)hc);
 744         *vcb = *valueCallBacks;
 745         FAULT_CALLBACK((void **)&(vcb->retain));
 746         FAULT_CALLBACK((void **)&(vcb->release));
 747         FAULT_CALLBACK((void **)&(vcb->copyDescription));
 748         FAULT_CALLBACK((void **)&(vcb->equal));
 749     }
 750 #endif
 751     return hc;
 752 }
 753
 754 #if CFDictionary
 755 CFHashRef CFBagCreate(CFAllocatorRef allocator, const_any_pointer_t *keys, const_any_pointer_t *values, CFIndex numValues, const CFBagKeyCallBacks *keyCallBacks, const CFBagValueCallBacks *valueCallBacks) {
 756 #endif
 757 #if CFSet || CFBag
 758 CFHashRef CFBagCreate(CFAllocatorRef allocator, const_any_pointer_t *keys, CFIndex numValues, const CFBagKeyCallBacks *keyCallBacks) {
 759 #endif
 760     CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%ld) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
 761 #if CFDictionary
 762     CFMutableHashRef hc = __CFBagInit(allocator, __kCFHashImmutable, numValues, keyCallBacks, valueCallBacks);
 763 #endif
 764 #if CFSet || CFBag
 765     CFMutableHashRef hc = __CFBagInit(allocator, __kCFHashImmutable, numValues, keyCallBacks);
 766 #endif
 767     __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashMutable);
 768     for (CFIndex idx = 0; idx < numValues; idx++) {
 769 #if CFDictionary
 770         CFBagAddValue(hc, keys[idx], values[idx]);
 771 #endif
 772 #if CFSet || CFBag
 773         CFBagAddValue(hc, keys[idx]);
 774 #endif
 775     }
 776     __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashImmutable);
 777     return (CFHashRef)hc;
 778 }
 779
 780 #if CFDictionary
 781 CFMutableHashRef CFBagCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFBagKeyCallBacks *keyCallBacks, const CFBagValueCallBacks *valueCallBacks) {
 782 #endif
 783 #if CFSet || CFBag
 784 CFMutableHashRef CFBagCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFBagKeyCallBacks *keyCallBacks) {
 785 #endif
 786     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%ld) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 787 #if CFDictionary
 788     CFMutableHashRef hc = __CFBagInit(allocator, __kCFHashMutable, capacity, keyCallBacks, valueCallBacks);
 789 #endif
 790 #if CFSet || CFBag
 791     CFMutableHashRef hc = __CFBagInit(allocator, __kCFHashMutable, capacity, keyCallBacks);
 792 #endif
 793     return hc;
 794 }
 795
 796 #if CFDictionary || CFSet
 797 // does not have Add semantics for Bag; it has Set semantics ... is that best?
 798 static void __CFBagGrow(CFMutableHashRef hc, CFIndex numNewValues);
 799
 800 // This creates a hc which is for CFTypes or NSObjects, with a CFRetain style ownership transfer;
 801 // the hc does not take a retain (since it claims 1), and the caller does not need to release the inserted objects (since we do it).
 802 // The incoming objects must also be collectable if allocated out of a collectable allocator - and are neither released nor retained.
 803 #if CFDictionary
 804 CFHashRef _CFBagCreate_ex(CFAllocatorRef allocator, Boolean isMutable, const_any_pointer_t *keys, const_any_pointer_t *values, CFIndex numValues) {
 805 #endif
 806 #if CFSet || CFBag
 807 CFHashRef _CFBagCreate_ex(CFAllocatorRef allocator, Boolean isMutable, const_any_pointer_t *keys, CFIndex numValues) {
 808 #endif
 809     CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%ld) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
 810 #if CFDictionary
 811     CFMutableHashRef hc = __CFBagInit(allocator, __kCFHashMutable, numValues, &kCFTypeBagKeyCallBacks, &kCFTypeBagValueCallBacks);
 812 #endif
 813 #if CFSet || CFBag
 814     CFMutableHashRef hc = __CFBagInit(allocator, __kCFHashMutable, numValues, &kCFTypeBagKeyCallBacks);
 815 #endif
 816     __CFBagGrow(hc, numValues);
 817     for (CFIndex idx = 0; idx < numValues; idx++) {
 818         CFIndex match, nomatch;
 819         __CFBagFindBuckets2(hc, (any_t)keys[idx], &match, &nomatch);
 820         if (kCFNotFound == match) {
 821             CFAllocatorRef allocator = __CFGetAllocator(hc);
 822             any_t newKey = (any_t)keys[idx];
 823             if (__CFHashKeyIsMagic(hc, newKey)) {
 824                 __CFBagFindNewMarker(hc);
 825             }
 826             if (hc->_keys[nomatch] == ~hc->_marker) {
 827                 hc->_deletes--;
 828             }
 829             CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
 830             CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[nomatch], newKey);
 831 #if CFDictionary
 832             any_t newValue = (any_t)values[idx];
 833             CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
 834             CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[nomatch], newValue);
 835 #endif
 836 #if CFBag
 837             hc->_values[nomatch] = 1;
 838 #endif
 839             hc->_bucketsUsed++;
 840             hc->_count++;
 841         } else {
 842             CFAllocatorRef allocator = __CFGetAllocator(hc);
 843 #if CFSet || CFBag
 844             any_t oldKey = hc->_keys[match];
 845             any_t newKey = (any_t)keys[idx];
 846             CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
 847             CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
 848             if (__CFHashKeyIsMagic(hc, newKey)) {
 849                 __CFBagFindNewMarker(hc);
 850             }
 851             CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], newKey);
 852             RELEASEKEY(oldKey);
 853 #endif
 854 #if CFDictionary
 855             any_t oldValue = hc->_values[match];
 856             any_t newValue = (any_t)values[idx];
 857             CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
 858             CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], newValue);
 859             RELEASEVALUE(oldValue);
 860 #endif
 861         }
 862     }
 863     if (!isMutable) __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashImmutable);
 864     return (CFHashRef)hc;
 865 }
 866 #endif
 867
 868 CFHashRef CFBagCreateCopy(CFAllocatorRef allocator, CFHashRef other) {
 869     CFMutableHashRef hc = CFBagCreateMutableCopy(allocator, CFBagGetCount(other), other);
 870     __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashImmutable);
 871     if (__CFOASafe) __CFSetLastAllocationEventName(hc, "CFBag (immutable)");
 872     return hc;
 873 }
 874
 875 CFMutableHashRef CFBagCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFHashRef other) {
 876     CFIndex numValues = CFBagGetCount(other);
 877     const_any_pointer_t *list, buffer[256];
 878     list = (numValues <= 256) ? buffer : (const_any_pointer_t *)CFAllocatorAllocate(allocator, numValues * sizeof(const_any_pointer_t), 0);
 879     if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFBag (temp)");
 880 #if CFDictionary
 881     const_any_pointer_t *vlist, vbuffer[256];
 882     vlist = (numValues <= 256) ? vbuffer : (const_any_pointer_t *)CFAllocatorAllocate(allocator, numValues * sizeof(const_any_pointer_t), 0);
 883     if (vlist != vbuffer && __CFOASafe) __CFSetLastAllocationEventName(vlist, "CFBag (temp)");
 884 #endif
 885 #if CFSet || CFBag
 886     CFBagGetValues(other, list);
 887 #endif
 888 #if CFDictionary
 889     CFBagGetKeysAndValues(other, list, vlist);
 890 #endif
 891     const CFBagKeyCallBacks *kcb;
 892     const CFBagValueCallBacks *vcb;
 893     if (CF_IS_OBJC(__kCFHashTypeID, other)) {
 894         kcb = &kCFTypeBagKeyCallBacks;
 895         vcb = &kCFTypeBagValueCallBacks;
 896     } else {
 897         kcb = __CFBagGetKeyCallBacks(other);
 898         vcb = __CFBagGetValueCallBacks(other);
 899     }
 900 #if CFDictionary
 901     CFMutableHashRef hc = __CFBagInit(allocator, __kCFHashMutable, capacity, kcb, vcb);
 902 #endif
 903 #if CFSet || CFBag
 904     CFMutableHashRef hc = __CFBagInit(allocator, __kCFHashMutable, capacity, kcb);
 905 #endif
 906     if (0 == capacity) _CFBagSetCapacity(hc, numValues);
 907     for (CFIndex idx = 0; idx < numValues; idx++) {
 908 #if CFDictionary
 909         CFBagAddValue(hc, list[idx], vlist[idx]);
 910 #endif
 911 #if CFSet || CFBag
 912         CFBagAddValue(hc, list[idx]);
 913 #endif
 914     }
 915     if (list != buffer) CFAllocatorDeallocate(allocator, list);
 916 #if CFDictionary
 917     if (vlist != vbuffer) CFAllocatorDeallocate(allocator, vlist);
 918 #endif
 919     return hc;
 920 }
 921
 922 // Used by NSHashTables/NSMapTables and KVO
 923 void _CFBagSetContext(CFHashRef hc, any_pointer_t context) {
 924     __CFGenericValidateType(hc, __kCFHashTypeID);
 925     CF_WRITE_BARRIER_BASE_ASSIGN(__CFGetAllocator(hc), hc, hc->_context, context);
 926 }
 927
 928 any_pointer_t _CFBagGetContext(CFHashRef hc) {
 929     __CFGenericValidateType(hc, __kCFHashTypeID);
 930     return hc->_context;
 931 }
 932
 933 CFIndex CFBagGetCount(CFHashRef hc) {
 934     if (CFDictionary || CFSet) CF_OBJC_FUNCDISPATCH0(__kCFHashTypeID, CFIndex, hc, "count");
 935     __CFGenericValidateType(hc, __kCFHashTypeID);
 936     return hc->_count;
 937 }
 938
 939 #if CFDictionary
 940 CFIndex CFBagGetCountOfKey(CFHashRef hc, const_any_pointer_t key) {
 941 #endif
 942 #if CFSet || CFBag
 943 CFIndex CFBagGetCountOfValue(CFHashRef hc, const_any_pointer_t key) {
 944 #endif
 945     if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, CFIndex, hc, "countForKey:", key);
 946     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, CFIndex, hc, "countForObject:", key);
 947     __CFGenericValidateType(hc, __kCFHashTypeID);
 948     if (0 == hc->_bucketsUsed) return 0;
 949     CFIndex match = __CFBagFindBuckets1(hc, (any_t)key);
 950     return (kCFNotFound != match ? __CFHashGetOccurrenceCount(hc, match) : 0);
 951 }
 952
 953 #if CFDictionary
 954 Boolean CFBagContainsKey(CFHashRef hc, const_any_pointer_t key) {
 955 #endif
 956 #if CFSet || CFBag
 957 Boolean CFBagContainsValue(CFHashRef hc, const_any_pointer_t key) {
 958 #endif
 959     if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, char, hc, "containsKey:", key);
 960     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, char, hc, "containsObject:", key);
 961     __CFGenericValidateType(hc, __kCFHashTypeID);
 962     if (0 == hc->_bucketsUsed) return false;
 963     CFIndex match = __CFBagFindBuckets1(hc, (any_t)key);
 964     return (kCFNotFound != match ? true : false);
 965 }
 966
 967 #if CFDictionary
 968 CFIndex CFBagGetCountOfValue(CFHashRef hc, const_any_pointer_t value) {
 969     CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, CFIndex, hc, "countForObject:", value);
 970     __CFGenericValidateType(hc, __kCFHashTypeID);
 971     if (0 == hc->_bucketsUsed) return 0;
 972     any_t *keys = hc->_keys;
 973     Boolean (*equal)(any_t, any_t, any_pointer_t) = (Boolean (*)(any_t, any_t, any_pointer_t))__CFBagGetValueCallBacks(hc)->equal;
 974     CFIndex cnt = 0;
 975     for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
 976         if (__CFHashKeyIsValue(hc, keys[idx])) {
 977             if ((hc->_values[idx] == (any_t)value) || (equal && INVOKE_CALLBACK3(equal, hc->_values[idx], (any_t)value, hc->_context))) {
 978                 cnt++;
 979             }
 980         }
 981     }
 982     return cnt;
 983 }
 984
 985 Boolean CFBagContainsValue(CFHashRef hc, const_any_pointer_t value) {
 986     CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, char, hc, "containsObject:", value);
 987     __CFGenericValidateType(hc, __kCFHashTypeID);
 988     if (0 == hc->_bucketsUsed) return false;
 989     any_t *keys = hc->_keys;
 990     Boolean (*equal)(any_t, any_t, any_pointer_t) = (Boolean (*)(any_t, any_t, any_pointer_t))__CFBagGetValueCallBacks(hc)->equal;
 991     for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
 992         if (__CFHashKeyIsValue(hc, keys[idx])) {
 993             if ((hc->_values[idx] == (any_t)value) || (equal && INVOKE_CALLBACK3(equal, hc->_values[idx], (any_t)value, hc->_context))) {
 994                 return true;
 995             }
 996         }
 997     }
 998     return false;
 999 }
1000 #endif
1001
1002 const_any_pointer_t CFBagGetValue(CFHashRef hc, const_any_pointer_t key) {
1003     if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, const_any_pointer_t, hc, "objectForKey:", key);
1004     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, const_any_pointer_t, hc, "member:", key);
1005     __CFGenericValidateType(hc, __kCFHashTypeID);
1006     if (0 == hc->_bucketsUsed) return 0;
1007     CFIndex match = __CFBagFindBuckets1(hc, (any_t)key);
1008     return (kCFNotFound != match ? (const_any_pointer_t)(CFDictionary ? hc->_values[match] : hc->_keys[match]) : 0);
1009 }
1010
1011 Boolean CFBagGetValueIfPresent(CFHashRef hc, const_any_pointer_t key, const_any_pointer_t *value) {
1012     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, Boolean, hc, "_getValue:forKey:", (any_t *)value, key);
1013     if (CFSet) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, Boolean, hc, "_getValue:forObj:", (any_t *)value, key);
1014     __CFGenericValidateType(hc, __kCFHashTypeID);
1015     if (0 == hc->_bucketsUsed) return false;
1016     CFIndex match = __CFBagFindBuckets1(hc, (any_t)key);
1017     return (kCFNotFound != match ? ((value ? __CFObjCStrongAssign((const_any_pointer_t)(CFDictionary ? hc->_values[match] : hc->_keys[match]), value) : 0), true) : false);
1018 }
1019
1020 #if CFDictionary
1021 Boolean CFBagGetKeyIfPresent(CFHashRef hc, const_any_pointer_t key, const_any_pointer_t *actualkey) {
1022     CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, Boolean, hc, "getActualKey:forKey:", actualkey, key);
1023     __CFGenericValidateType(hc, __kCFHashTypeID);
1024     if (0 == hc->_bucketsUsed) return false;
1025     CFIndex match = __CFBagFindBuckets1(hc, (any_t)key);
1026     return (kCFNotFound != match ? ((actualkey ? __CFObjCStrongAssign((const_any_pointer_t)hc->_keys[match], actualkey) : NULL), true) : false);
1027 }
1028 #endif
1029
1030 #if CFDictionary
1031 void CFBagGetKeysAndValues(CFHashRef hc, const_any_pointer_t *keybuf, const_any_pointer_t *valuebuf) {
1032 #endif
1033 #if CFSet || CFBag
1034 void CFBagGetValues(CFHashRef hc, const_any_pointer_t *keybuf) {
1035     const_any_pointer_t *valuebuf = 0;
1036 #endif
1037     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "getObjects:andKeys:", (any_t *)valuebuf, (any_t *)keybuf);
1038     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "getObjects:", (any_t *)keybuf);
1039     __CFGenericValidateType(hc, __kCFHashTypeID);
1040     if (CF_USING_COLLECTABLE_MEMORY) {
1041         // GC: speculatively issue a write-barrier on the copied to buffers
1042         __CFObjCWriteBarrierRange(keybuf, hc->_count * sizeof(any_t));
1043         __CFObjCWriteBarrierRange(valuebuf, hc->_count * sizeof(any_t));
1044     }
1045     any_t *keys = hc->_keys;
1046     for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1047         if (__CFHashKeyIsValue(hc, keys[idx])) {
1048             for (CFIndex cnt = __CFHashGetOccurrenceCount(hc, idx); cnt--;) {
1049                 if (keybuf) *keybuf++ = (const_any_pointer_t)keys[idx];
1050                 if (valuebuf) *valuebuf++ = (const_any_pointer_t)hc->_values[idx];
1051             }
1052         }
1053     }
1054 }
1055
1056 #if CFDictionary || CFSet
1057 unsigned long _CFBagFastEnumeration(CFHashRef hc, struct __objcFastEnumerationStateEquivalent *state, void *stackbuffer, unsigned long count) {
1058     /* copy as many as count items over */
1059     if (0 == state->state) {        /* first time */
1060         state->mutationsPtr = (unsigned long *)&hc->_mutations;
1061     }
1062     state->itemsPtr = (unsigned long *)stackbuffer;
1063     CFIndex cnt = 0;
1064     any_t *keys = hc->_keys;
1065     for (CFIndex idx = (CFIndex)state->state, nbuckets = hc->_bucketsNum; idx < nbuckets && cnt < (CFIndex)count; idx++) {
1066         if (__CFHashKeyIsValue(hc, keys[idx])) {
1067             state->itemsPtr[cnt++] = (unsigned long)keys[idx];
1068         }
1069         state->state++;
1070     }
1071     return cnt;
1072 }
1073 #endif
1074
1075 void CFBagApplyFunction(CFHashRef hc, CFBagApplierFunction applier, any_pointer_t context) {
1076     FAULT_CALLBACK((void **)&(applier));
1077     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_apply:context:", applier, context);
1078     if (CFSet) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_applyValues:context:", applier, context);
1079     __CFGenericValidateType(hc, __kCFHashTypeID);
1080     any_t *keys = hc->_keys;
1081     for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1082         if (__CFHashKeyIsValue(hc, keys[idx])) {
1083             for (CFIndex cnt = __CFHashGetOccurrenceCount(hc, idx); cnt--;) {
1084 #if CFDictionary
1085                 INVOKE_CALLBACK3(applier, (const_any_pointer_t)keys[idx], (const_any_pointer_t)hc->_values[idx], context);
1086 #endif
1087 #if CFSet || CFBag
1088                 INVOKE_CALLBACK2(applier, (const_any_pointer_t)keys[idx], context);
1089 #endif
1090             }
1091         }
1092     }
1093 }
1094
1095 static void __CFBagGrow(CFMutableHashRef hc, CFIndex numNewValues) {
1096     any_t *oldkeys = hc->_keys;
1097     any_t *oldvalues = hc->_values;
1098     CFIndex nbuckets = hc->_bucketsNum;
1099     hc->_bucketsCap = __CFHashRoundUpCapacity(hc->_bucketsUsed + numNewValues);
1100     hc->_bucketsNum = __CFHashNumBucketsForCapacity(hc->_bucketsCap);
1101     hc->_deletes = 0;
1102     CFAllocatorRef allocator = __CFGetAllocator(hc);
1103     CFOptionFlags weakOrStrong = (hc->_xflags & __kCFHashWeakKeys) ? 0 : __kCFAllocatorGCScannedMemory;
1104     any_t *mem = (any_t *)_CFAllocatorAllocateGC(allocator, hc->_bucketsNum * sizeof(any_t), weakOrStrong);
1105     if (NULL == mem) __CFBagHandleOutOfMemory(hc, hc->_bucketsNum * sizeof(any_t));
1106     if (__CFOASafe) __CFSetLastAllocationEventName(mem, "CFBag (key-store)");
1107     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, hc, hc->_keys, mem);
1108     CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;  // GC: avoids write-barrier in weak case.
1109     any_t *keysBase = mem;
1110 #if CFDictionary || CFBag
1111     weakOrStrong = (hc->_xflags & __kCFHashWeakValues) ? 0 : __kCFAllocatorGCScannedMemory;
1112     mem = (any_t *)_CFAllocatorAllocateGC(allocator, hc->_bucketsNum * sizeof(any_t), weakOrStrong);
1113     if (NULL == mem) __CFBagHandleOutOfMemory(hc, hc->_bucketsNum * sizeof(any_t));
1114     if (__CFOASafe) __CFSetLastAllocationEventName(mem, "CFBag (value-store)");
1115     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, hc, hc->_values, mem);
1116 #endif
1117 #if CFDictionary
1118     CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator; // GC: avoids write-barrier in weak case.
1119     any_t *valuesBase = mem;
1120 #endif
1121     for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1122         hc->_keys[idx] = hc->_marker;
1123 #if CFDictionary || CFBag
1124         hc->_values[idx] = 0;
1125 #endif
1126     }
1127     if (NULL == oldkeys) return;
1128     for (CFIndex idx = 0; idx < nbuckets; idx++) {
1129         if (__CFHashKeyIsValue(hc, oldkeys[idx])) {
1130             CFIndex match, nomatch;
1131             __CFBagFindBuckets2(hc, oldkeys[idx], &match, &nomatch);
1132             CFAssert3(kCFNotFound == 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__, oldkeys[idx], hc->_keys[match]);
1133             if (kCFNotFound != nomatch) {
1134                 CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, hc->_keys[nomatch], oldkeys[idx]);
1135 #if CFDictionary
1136                 CF_WRITE_BARRIER_BASE_ASSIGN(valuesAllocator, valuesBase, hc->_values[nomatch], oldvalues[idx]);
1137 #endif
1138 #if CFBag
1139                 hc->_values[nomatch] = oldvalues[idx];
1140 #endif
1141             }
1142         }
1143     }
1144     _CFAllocatorDeallocateGC(allocator, oldkeys);
1145     _CFAllocatorDeallocateGC(allocator, oldvalues);
1146 }
1147
1148 // This function is for Foundation's benefit; no one else should use it.
1149 void _CFBagSetCapacity(CFMutableHashRef hc, CFIndex cap) {
1150     if (CF_IS_OBJC(__kCFHashTypeID, hc)) return;
1151     __CFGenericValidateType(hc, __kCFHashTypeID);
1152     CFAssert1(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): collection is immutable", __PRETTY_FUNCTION__);
1153     CFAssert3(hc->_bucketsUsed <= cap, __kCFLogAssertion, "%s(): desired capacity (%ld) is less than bucket count (%ld)", __PRETTY_FUNCTION__, cap, hc->_bucketsUsed);
1154     __CFBagGrow(hc, cap - hc->_bucketsUsed);
1155 }
1156
1157
1158 #if CFDictionary
1159 void CFBagAddValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
1160 #endif
1161 #if CFSet || CFBag
1162 void CFBagAddValue(CFMutableHashRef hc, const_any_pointer_t key) {
1163     #define value 0
1164 #endif
1165     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_addObject:forKey:", value, key);
1166     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "addObject:", key);
1167     __CFGenericValidateType(hc, __kCFHashTypeID);
1168     switch (__CFHashGetType(hc)) {
1169     case __kCFHashMutable:
1170         if (hc->_bucketsUsed == hc->_bucketsCap || NULL == hc->_keys) {
1171             __CFBagGrow(hc, 1);
1172         }
1173         break;
1174     default:
1175         CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1176         break;
1177     }
1178     hc->_mutations++;
1179     CFIndex match, nomatch;
1180     __CFBagFindBuckets2(hc, (any_t)key, &match, &nomatch);
1181     if (kCFNotFound != match) {
1182 #if CFBag
1183         CF_OBJC_KVO_WILLCHANGE(hc, hc->_keys[match]);
1184         hc->_values[match]++;
1185         hc->_count++;
1186         CF_OBJC_KVO_DIDCHANGE(hc, hc->_keys[match]);
1187 #endif
1188     } else {
1189         CFAllocatorRef allocator = __CFGetAllocator(hc);
1190         GETNEWKEY(newKey, key);
1191 #if CFDictionary
1192         GETNEWVALUE(newValue);
1193 #endif
1194         if (__CFHashKeyIsMagic(hc, newKey)) {
1195             __CFBagFindNewMarker(hc);
1196         }
1197         if (hc->_keys[nomatch] == ~hc->_marker) {
1198             hc->_deletes--;
1199         }
1200         CF_OBJC_KVO_WILLCHANGE(hc, key);
1201         CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1202         CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[nomatch], newKey);
1203 #if CFDictionary
1204         CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1205         CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[nomatch], newValue);
1206 #endif
1207 #if CFBag
1208         hc->_values[nomatch] = 1;
1209 #endif
1210         hc->_bucketsUsed++;
1211         hc->_count++;
1212         CF_OBJC_KVO_DIDCHANGE(hc, key);
1213     }
1214 }
1215
1216 #if CFDictionary
1217 void CFBagReplaceValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
1218 #endif
1219 #if CFSet || CFBag
1220 void CFBagReplaceValue(CFMutableHashRef hc, const_any_pointer_t key) {
1221     #define value 0
1222 #endif
1223     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_replaceObject:forKey:", value, key);
1224     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "_replaceObject:", key);
1225     __CFGenericValidateType(hc, __kCFHashTypeID);
1226     switch (__CFHashGetType(hc)) {
1227     case __kCFHashMutable:
1228         break;
1229     default:
1230         CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1231         break;
1232     }
1233     hc->_mutations++;
1234     if (0 == hc->_bucketsUsed) return;
1235     CFIndex match = __CFBagFindBuckets1(hc, (any_t)key);
1236     if (kCFNotFound == match) return;
1237     CFAllocatorRef allocator = __CFGetAllocator(hc);
1238 #if CFSet || CFBag
1239     GETNEWKEY(newKey, key);
1240 #endif
1241 #if CFDictionary
1242     GETNEWVALUE(newValue);
1243 #endif
1244     any_t oldKey = hc->_keys[match];
1245     CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
1246 #if CFSet || CFBag
1247     CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1248     CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
1249     if (__CFHashKeyIsMagic(hc, newKey)) {
1250         __CFBagFindNewMarker(hc);
1251     }
1252     CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], newKey);
1253 #endif
1254 #if CFDictionary
1255     any_t oldValue = hc->_values[match];
1256     CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1257     CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], newValue);
1258 #endif
1259     CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
1260 #if CFSet || CFBag
1261     RELEASEKEY(oldKey);
1262 #endif
1263 #if CFDictionary
1264     RELEASEVALUE(oldValue);
1265 #endif
1266 }
1267
1268 #if CFDictionary
1269 void CFBagSetValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
1270 #endif
1271 #if CFSet || CFBag
1272 void CFBagSetValue(CFMutableHashRef hc, const_any_pointer_t key) {
1273     #define value 0
1274 #endif
1275     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "setObject:forKey:", value, key);
1276     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "_setObject:", key);
1277     __CFGenericValidateType(hc, __kCFHashTypeID);
1278     switch (__CFHashGetType(hc)) {
1279     case __kCFHashMutable:
1280         if (hc->_bucketsUsed == hc->_bucketsCap || NULL == hc->_keys) {
1281             __CFBagGrow(hc, 1);
1282         }
1283         break;
1284     default:
1285         CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1286         break;
1287     }
1288     hc->_mutations++;
1289     CFIndex match, nomatch;
1290     __CFBagFindBuckets2(hc, (any_t)key, &match, &nomatch);
1291     if (kCFNotFound == match) {
1292         CFAllocatorRef allocator = __CFGetAllocator(hc);
1293         GETNEWKEY(newKey, key);
1294 #if CFDictionary
1295         GETNEWVALUE(newValue);
1296 #endif
1297         if (__CFHashKeyIsMagic(hc, newKey)) {
1298             __CFBagFindNewMarker(hc);
1299         }
1300         if (hc->_keys[nomatch] == ~hc->_marker) {
1301             hc->_deletes--;
1302         }
1303         CF_OBJC_KVO_WILLCHANGE(hc, key);
1304         CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1305         CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[nomatch], newKey);
1306 #if CFDictionary
1307         CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1308         CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[nomatch], newValue);
1309 #endif
1310 #if CFBag
1311         hc->_values[nomatch] = 1;
1312 #endif
1313         hc->_bucketsUsed++;
1314         hc->_count++;
1315         CF_OBJC_KVO_DIDCHANGE(hc, key);
1316     } else {
1317         CFAllocatorRef allocator = __CFGetAllocator(hc);
1318 #if CFSet || CFBag
1319         GETNEWKEY(newKey, key);
1320 #endif
1321 #if CFDictionary
1322         GETNEWVALUE(newValue);
1323 #endif
1324         any_t oldKey = hc->_keys[match];
1325         CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
1326 #if CFSet || CFBag
1327         CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1328         CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
1329         if (__CFHashKeyIsMagic(hc, newKey)) {
1330             __CFBagFindNewMarker(hc);
1331         }
1332         CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], newKey);
1333 #endif
1334 #if CFDictionary
1335         any_t oldValue = hc->_values[match];
1336         CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1337         CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], newValue);
1338 #endif
1339         CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
1340 #if CFSet || CFBag
1341         RELEASEKEY(oldKey);
1342 #endif
1343 #if CFDictionary
1344         RELEASEVALUE(oldValue);
1345 #endif
1346     }
1347 }
1348
1349 void CFBagRemoveValue(CFMutableHashRef hc, const_any_pointer_t key) {
1350     if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "removeObjectForKey:", key);
1351     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "removeObject:", key);
1352     __CFGenericValidateType(hc, __kCFHashTypeID);
1353     switch (__CFHashGetType(hc)) {
1354     case __kCFHashMutable:
1355         break;
1356     default:
1357         CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1358         break;
1359     }
1360     hc->_mutations++;
1361     if (0 == hc->_bucketsUsed) return;
1362     CFIndex match = __CFBagFindBuckets1(hc, (any_t)key);
1363     if (kCFNotFound == match) return;
1364     if (1 < __CFHashGetOccurrenceCount(hc, match)) {
1365 #if CFBag
1366         CF_OBJC_KVO_WILLCHANGE(hc, hc->_keys[match]);
1367         hc->_values[match]--;
1368         hc->_count--;
1369         CF_OBJC_KVO_DIDCHANGE(hc, hc->_keys[match]);
1370 #endif
1371     } else {
1372         CFAllocatorRef allocator = __CFGetAllocator(hc);
1373         any_t oldKey = hc->_keys[match];
1374         CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
1375         CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1376         CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
1377 #if CFDictionary
1378         any_t oldValue = hc->_values[match];
1379         CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1380         CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], 0);
1381 #endif
1382 #if CFBag
1383         hc->_values[match] = 0;
1384 #endif
1385         hc->_count--;
1386         hc->_bucketsUsed--;
1387         hc->_deletes++;
1388         CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
1389         RELEASEKEY(oldKey);
1390 #if CFDictionary
1391         RELEASEVALUE(oldValue);
1392 #endif
1393         if (__CFBagShouldShrink(hc)) {
1394             __CFBagGrow(hc, 0);
1395         } else {
1396             // When the probeskip == 1 always and only, a DELETED slot followed by an EMPTY slot
1397             // can be converted to an EMPTY slot.  By extension, a chain of DELETED slots followed
1398             // by an EMPTY slot can be converted to EMPTY slots, which is what we do here.
1399             if (match < hc->_bucketsNum - 1 && hc->_keys[match + 1] == hc->_marker) {
1400                 while (0 <= match && hc->_keys[match] == ~hc->_marker) {
1401                     hc->_keys[match] = hc->_marker;
1402                     hc->_deletes--;
1403                     match--;
1404                 }
1405             }
1406         }
1407     }
1408 }
1409
1410 void CFBagRemoveAllValues(CFMutableHashRef hc) {
1411     if (CFDictionary) CF_OBJC_FUNCDISPATCH0(__kCFHashTypeID, void, hc, "removeAllObjects");
1412     if (CFSet) CF_OBJC_FUNCDISPATCH0(__kCFHashTypeID, void, hc, "removeAllObjects");
1413     __CFGenericValidateType(hc, __kCFHashTypeID);
1414     switch (__CFHashGetType(hc)) {
1415     case __kCFHashMutable:
1416         break;
1417     default:
1418         CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1419         break;
1420     }
1421     hc->_mutations++;
1422     if (0 == hc->_bucketsUsed) return;
1423     CFAllocatorRef allocator = __CFGetAllocator(hc);
1424     any_t *keys = hc->_keys;
1425     for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1426         if (__CFHashKeyIsValue(hc, keys[idx])) {
1427             any_t oldKey = keys[idx];
1428             CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
1429 #if CFDictionary || CFSet
1430             hc->_count--;
1431 #endif
1432 #if CFBag
1433             hc->_count -= hc->_values[idx];
1434 #endif
1435             CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1436             CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[idx], ~hc->_marker);
1437 #if CFDictionary
1438             any_t oldValue = hc->_values[idx];
1439             CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1440             CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[idx], 0);
1441 #endif
1442 #if CFBag
1443             hc->_values[idx] = 0;
1444 #endif
1445             hc->_bucketsUsed--;
1446             hc->_deletes++;
1447             CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
1448             RELEASEKEY(oldKey);
1449 #if CFDictionary
1450             RELEASEVALUE(oldValue);
1451 #endif
1452         }
1453     }
1454     for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1455         keys[idx] = hc->_marker;
1456     }
1457     hc->_deletes = 0;
1458     hc->_bucketsUsed = 0;
1459     hc->_count = 0;
1460     if (__CFBagShouldShrink(hc) && (256 <= hc->_bucketsCap)) {
1461         __CFBagGrow(hc, 128);
1462     }
1463 }
1464
1465 #undef CF_OBJC_KVO_WILLCHANGE
1466 #undef CF_OBJC_KVO_DIDCHANGE
1467