Collections.subproj/CFDictionary.c

   1 /*
   2  * Copyright (c) 2005 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*      CFDictionary.c
  24         Copyright 1998-2002, Apple, Inc. All rights reserved.
  25         Responsibility: Christopher Kane
  26 */
  27
  28 #include <CoreFoundation/CFDictionary.h>
  29 #include "CFInternal.h"
  30
  31 const CFDictionaryKeyCallBacks kCFTypeDictionaryKeyCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  32 const CFDictionaryKeyCallBacks kCFCopyStringDictionaryKeyCallBacks = {0, (void *)CFStringCreateCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  33 const CFDictionaryValueCallBacks kCFTypeDictionaryValueCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual};
  34 static const CFDictionaryKeyCallBacks __kCFNullDictionaryKeyCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
  35 static const CFDictionaryValueCallBacks __kCFNullDictionaryValueCallBacks = {0, NULL, NULL, NULL, NULL};
  36
  37 static const uint32_t __CFDictionaryCapacities[42] = {
  38     4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
  39     15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
  40     3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
  41     228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
  42 };
  43
  44 static const uint32_t __CFDictionaryBuckets[42] = {     // primes
  45     5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
  46     24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
  47     4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
  48     370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
  49 };
  50
  51 CF_INLINE CFIndex __CFDictionaryRoundUpCapacity(CFIndex capacity) {
  52     CFIndex idx;
  53     for (idx = 0; idx < 42 && __CFDictionaryCapacities[idx] < (uint32_t)capacity; idx++);
  54     if (42 <= idx) HALT;
  55     return __CFDictionaryCapacities[idx];
  56 }
  57
  58 CF_INLINE CFIndex __CFDictionaryNumBucketsForCapacity(CFIndex capacity) {
  59     CFIndex idx;
  60     for (idx = 0; idx < 42 && __CFDictionaryCapacities[idx] < (uint32_t)capacity; idx++);
  61     if (42 <= idx) HALT;
  62     return __CFDictionaryBuckets[idx];
  63 }
  64
  65 enum {          /* Bits 1-0 */
  66     __kCFDictionaryImmutable = 0,       /* unchangable and fixed capacity */
  67     __kCFDictionaryMutable = 1,         /* changeable and variable capacity */
  68     __kCFDictionaryFixedMutable = 3     /* changeable and fixed capacity */
  69 };
  70
  71 enum {          /* Bits 5-4 (value), 3-2 (key) */
  72     __kCFDictionaryHasNullCallBacks = 0,
  73     __kCFDictionaryHasCFTypeCallBacks = 1,
  74     __kCFDictionaryHasCustomCallBacks = 3       /* callbacks are at end of header */
  75 };
  76
  77 // Under GC, we fudge the key/value memory in two ways
  78 // First, if we had null callbacks or null for both retain/release, we use unscanned memory
  79 // This means that if people were doing addValue:[xxx new] and never removing, well, that doesn't work
  80 //
  81 // Second, if we notice standard retain/release implementations we substitute scanned memory
  82 // and zero out the retain/release callbacks.  This is fine, but when copying we need to restore them
  83
  84 enum {
  85     __kCFDictionaryRestoreKeys =       (1 << 0),
  86     __kCFDictionaryRestoreValues =     (1 << 1),
  87     __kCFDictionaryRestoreStringKeys = (1 << 2),
  88     __kCFDictionaryWeakKeys =          (1 << 3),
  89     __kCFDictionaryWeakValues =        (1 << 4)
  90 };
  91
  92 struct __CFDictionary {
  93     CFRuntimeBase _base;
  94     CFIndex _count;             /* number of values */
  95     CFIndex _capacity;          /* maximum number of values */
  96     CFIndex _bucketsNum;        /* number of slots */
  97     uintptr_t _marker;
  98     void *_context;             /* private */
  99     CFIndex _deletes;
 100     CFOptionFlags _xflags;      /* bits for GC */
 101     const void **_keys;         /* can be NULL if not allocated yet */
 102     const void **_values;       /* can be NULL if not allocated yet */
 103 };
 104
 105 /* Bits 1-0 of the base reserved bits are used for mutability variety */
 106 /* Bits 3-2 of the base reserved bits are used for key callback indicator bits */
 107 /* Bits 5-4 of the base reserved bits are used for value callback indicator bits */
 108 /* Bit 6 is special KVO actions bit */
 109
 110 CF_INLINE CFIndex __CFDictionaryGetType(CFDictionaryRef dict) {
 111     return __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 1, 0);
 112 }
 113
 114 CF_INLINE CFIndex __CFDictionaryGetSizeOfType(CFIndex t) {
 115     CFIndex size = sizeof(struct __CFDictionary);
 116     if (__CFBitfieldGetValue(t, 3, 2) == __kCFDictionaryHasCustomCallBacks) {
 117         size += sizeof(CFDictionaryKeyCallBacks);
 118     }
 119     if (__CFBitfieldGetValue(t, 5, 4) == __kCFDictionaryHasCustomCallBacks) {
 120         size += sizeof(CFDictionaryValueCallBacks);
 121     }
 122     return size;
 123 }
 124
 125 CF_INLINE const CFDictionaryKeyCallBacks *__CFDictionaryGetKeyCallBacks(CFDictionaryRef dict) {
 126     CFDictionaryKeyCallBacks *result = NULL;
 127     switch (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
 128     case __kCFDictionaryHasNullCallBacks:
 129         return &__kCFNullDictionaryKeyCallBacks;
 130     case __kCFDictionaryHasCFTypeCallBacks:
 131         return &kCFTypeDictionaryKeyCallBacks;
 132     case __kCFDictionaryHasCustomCallBacks:
 133         break;
 134     }
 135     result = (CFDictionaryKeyCallBacks *)((uint8_t *)dict + sizeof(struct __CFDictionary));
 136     return result;
 137 }
 138
 139 CF_INLINE bool __CFDictionaryKeyCallBacksMatchNull(const CFDictionaryKeyCallBacks *c) {
 140     return (NULL == c ||
 141         (c->retain == __kCFNullDictionaryKeyCallBacks.retain &&
 142          c->release == __kCFNullDictionaryKeyCallBacks.release &&
 143          c->copyDescription == __kCFNullDictionaryKeyCallBacks.copyDescription &&
 144          c->equal == __kCFNullDictionaryKeyCallBacks.equal &&
 145          c->hash == __kCFNullDictionaryKeyCallBacks.hash));
 146 }
 147
 148 CF_INLINE bool __CFDictionaryKeyCallBacksMatchCFType(const CFDictionaryKeyCallBacks *c) {
 149     return (&kCFTypeDictionaryKeyCallBacks == c ||
 150         (c->retain == kCFTypeDictionaryKeyCallBacks.retain &&
 151          c->release == kCFTypeDictionaryKeyCallBacks.release &&
 152          c->copyDescription == kCFTypeDictionaryKeyCallBacks.copyDescription &&
 153          c->equal == kCFTypeDictionaryKeyCallBacks.equal &&
 154          c->hash == kCFTypeDictionaryKeyCallBacks.hash));
 155 }
 156
 157 CF_INLINE const CFDictionaryValueCallBacks *__CFDictionaryGetValueCallBacks(CFDictionaryRef dict) {
 158     CFDictionaryValueCallBacks *result = NULL;
 159     switch (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 5, 4)) {
 160     case __kCFDictionaryHasNullCallBacks:
 161         return &__kCFNullDictionaryValueCallBacks;
 162     case __kCFDictionaryHasCFTypeCallBacks:
 163         return &kCFTypeDictionaryValueCallBacks;
 164     case __kCFDictionaryHasCustomCallBacks:
 165         break;
 166     }
 167     if (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2) == __kCFDictionaryHasCustomCallBacks) {
 168         result = (CFDictionaryValueCallBacks *)((uint8_t *)dict + sizeof(struct __CFDictionary) + sizeof(CFDictionaryKeyCallBacks));
 169     } else {
 170         result = (CFDictionaryValueCallBacks *)((uint8_t *)dict + sizeof(struct __CFDictionary));
 171     }
 172     return result;
 173 }
 174
 175 CF_INLINE bool __CFDictionaryValueCallBacksMatchNull(const CFDictionaryValueCallBacks *c) {
 176     return (NULL == c ||
 177         (c->retain == __kCFNullDictionaryValueCallBacks.retain &&
 178          c->release == __kCFNullDictionaryValueCallBacks.release &&
 179          c->copyDescription == __kCFNullDictionaryValueCallBacks.copyDescription &&
 180          c->equal == __kCFNullDictionaryValueCallBacks.equal));
 181 }
 182
 183 CF_INLINE bool __CFDictionaryValueCallBacksMatchCFType(const CFDictionaryValueCallBacks *c) {
 184     return (&kCFTypeDictionaryValueCallBacks == c ||
 185         (c->retain == kCFTypeDictionaryValueCallBacks.retain &&
 186          c->release == kCFTypeDictionaryValueCallBacks.release &&
 187          c->copyDescription == kCFTypeDictionaryValueCallBacks.copyDescription &&
 188          c->equal == kCFTypeDictionaryValueCallBacks.equal));
 189 }
 190
 191 CFIndex _CFDictionaryGetKVOBit(CFDictionaryRef dict) {
 192     return __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 6, 6);
 193 }
 194
 195 void _CFDictionarySetKVOBit(CFDictionaryRef dict, CFIndex bit) {
 196     __CFBitfieldSetValue(((CFRuntimeBase *)dict)->_info, 6, 6, (bit & 0x1));
 197 }
 198
 199 CF_INLINE bool _CFDictionaryIsSplit(CFDictionaryRef dict) {
 200     return ((dict->_xflags & (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) != 0);
 201 }
 202
 203
 204 #define CF_OBJC_KVO_WILLCHANGE(obj, sel)
 205 #define CF_OBJC_KVO_DIDCHANGE(obj, sel)
 206
 207
 208
 209 static CFIndex __CFDictionaryFindBuckets1a(CFDictionaryRef dict, const void *key) {
 210     CFHashCode keyHash = (CFHashCode)key;
 211     const void **keys = dict->_keys;
 212     uintptr_t marker = dict->_marker;
 213     CFIndex probe = keyHash % dict->_bucketsNum;
 214     CFIndex probeskip = 1;      // See RemoveValue() for notes before changing this value
 215     CFIndex start = probe;
 216     for (;;) {
 217         uintptr_t currKey = (uintptr_t)keys[probe];
 218         if (marker == currKey) {                /* empty */
 219             return kCFNotFound;
 220         } else if (~marker == currKey) {        /* deleted */
 221             /* do nothing */
 222         } else if (currKey == (uintptr_t)key) {
 223             return probe;
 224         }
 225         probe = probe + probeskip;
 226         // This alternative to probe % buckets assumes that
 227         // probeskip is always positive and less than the
 228         // number of buckets.
 229         if (dict->_bucketsNum <= probe) {
 230             probe -= dict->_bucketsNum;
 231         }
 232         if (start == probe) {
 233             return kCFNotFound;
 234         }
 235     }
 236 }
 237
 238 static CFIndex __CFDictionaryFindBuckets1b(CFDictionaryRef dict, const void *key) {
 239     const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
 240     CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, dict->_context) : (CFHashCode)key;
 241     const void **keys = dict->_keys;
 242     uintptr_t marker = dict->_marker;
 243     CFIndex probe = keyHash % dict->_bucketsNum;
 244     CFIndex probeskip = 1;      // See RemoveValue() for notes before changing this value
 245     CFIndex start = probe;
 246     for (;;) {
 247         uintptr_t currKey = (uintptr_t)keys[probe];
 248         if (marker == currKey) {                /* empty */
 249             return kCFNotFound;
 250         } else if (~marker == currKey) {        /* deleted */
 251             /* do nothing */
 252         } else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))cb->equal, (void *)currKey, key, dict->_context))) {
 253             return probe;
 254         }
 255         probe = probe + probeskip;
 256         // This alternative to probe % buckets assumes that
 257         // probeskip is always positive and less than the
 258         // number of buckets.
 259         if (dict->_bucketsNum <= probe) {
 260             probe -= dict->_bucketsNum;
 261         }
 262         if (start == probe) {
 263             return kCFNotFound;
 264         }
 265     }
 266 }
 267
 268 static void __CFDictionaryFindBuckets2(CFDictionaryRef dict, const void *key, CFIndex *match, CFIndex *nomatch) {
 269     const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
 270     CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, dict->_context) : (CFHashCode)key;
 271     const void **keys = dict->_keys;
 272     uintptr_t marker = dict->_marker;
 273     CFIndex probe = keyHash % dict->_bucketsNum;
 274     CFIndex probeskip = 1;      // See RemoveValue() for notes before changing this value
 275     CFIndex start = probe;
 276     *match = kCFNotFound;
 277     *nomatch = kCFNotFound;
 278     for (;;) {
 279         uintptr_t currKey = (uintptr_t)keys[probe];
 280         if (marker == currKey) {                /* empty */
 281             if (nomatch) *nomatch = probe;
 282             return;
 283         } else if (~marker == currKey) {        /* deleted */
 284             if (nomatch) {
 285                 *nomatch = probe;
 286                 nomatch = NULL;
 287             }
 288         } else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))cb->equal, (void *)currKey, key, dict->_context))) {
 289             *match = probe;
 290             return;
 291         }
 292         probe = probe + probeskip;
 293         // This alternative to probe % buckets assumes that
 294         // probeskip is always positive and less than the
 295         // number of buckets.
 296         if (dict->_bucketsNum <= probe) {
 297             probe -= dict->_bucketsNum;
 298         }
 299         if (start == probe) {
 300             return;
 301         }
 302     }
 303 }
 304
 305 static void __CFDictionaryFindNewMarker(CFDictionaryRef dict) {
 306     const void **keys = dict->_keys;
 307     uintptr_t newMarker;
 308     CFIndex idx, nbuckets;
 309     bool hit;
 310
 311     nbuckets = dict->_bucketsNum;
 312     newMarker = dict->_marker;
 313     do {
 314         newMarker--;
 315         hit = false;
 316         for (idx = 0; idx < nbuckets; idx++) {
 317             if (newMarker == (uintptr_t)keys[idx] || ~newMarker == (uintptr_t)keys[idx]) {
 318                 hit = true;
 319                 break;
 320             }
 321         }
 322     } while (hit);
 323     for (idx = 0; idx < nbuckets; idx++) {
 324         if (dict->_marker == (uintptr_t)keys[idx]) {
 325             keys[idx] = (const void *)newMarker;
 326         } else if (~dict->_marker == (uintptr_t)keys[idx]) {
 327             keys[idx] = (const void *)~newMarker;
 328         }
 329     }
 330     ((struct __CFDictionary *)dict)->_marker = newMarker;
 331 }
 332
 333 static bool __CFDictionaryEqual(CFTypeRef cf1, CFTypeRef cf2) {
 334     CFDictionaryRef dict1 = (CFDictionaryRef)cf1;
 335     CFDictionaryRef dict2 = (CFDictionaryRef)cf2;
 336     const CFDictionaryKeyCallBacks *cb1, *cb2;
 337     const CFDictionaryValueCallBacks *vcb1, *vcb2;
 338     const void **keys;
 339     CFIndex idx, nbuckets;
 340     if (dict1 == dict2) return true;
 341     if (dict1->_count != dict2->_count) return false;
 342     cb1 = __CFDictionaryGetKeyCallBacks(dict1);
 343     cb2 = __CFDictionaryGetKeyCallBacks(dict2);
 344     if (cb1->equal != cb2->equal) return false;
 345     vcb1 = __CFDictionaryGetValueCallBacks(dict1);
 346     vcb2 = __CFDictionaryGetValueCallBacks(dict2);
 347     if (vcb1->equal != vcb2->equal) return false;
 348     if (0 == dict1->_count) return true; /* after function comparison! */
 349     keys = dict1->_keys;
 350     nbuckets = dict1->_bucketsNum;
 351     for (idx = 0; idx < nbuckets; idx++) {
 352         if (dict1->_marker != (uintptr_t)keys[idx] && ~dict1->_marker != (uintptr_t)keys[idx]) {
 353             const void *value;
 354             if (!CFDictionaryGetValueIfPresent(dict2, keys[idx], &value)) return false;
 355             if (dict1->_values[idx] != value && vcb1->equal && !INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))vcb1->equal, dict1->_values[idx], value, dict1->_context)) {
 356                 return false;
 357             }
 358         }
 359     }
 360     return true;
 361 }
 362
 363 static CFHashCode __CFDictionaryHash(CFTypeRef cf) {
 364     CFDictionaryRef dict = (CFDictionaryRef)cf;
 365     return dict->_count;
 366 }
 367
 368 static CFStringRef __CFDictionaryCopyDescription(CFTypeRef cf) {
 369     CFDictionaryRef dict = (CFDictionaryRef)cf;
 370     CFAllocatorRef allocator;
 371     const CFDictionaryKeyCallBacks *cb;
 372     const CFDictionaryValueCallBacks *vcb;
 373     const void **keys;
 374     CFIndex idx, nbuckets;
 375     CFMutableStringRef result;
 376     cb = __CFDictionaryGetKeyCallBacks(dict);
 377     vcb = __CFDictionaryGetValueCallBacks(dict);
 378     keys = dict->_keys;
 379     nbuckets = dict->_bucketsNum;
 380     allocator = CFGetAllocator(dict);
 381     result = CFStringCreateMutable(allocator, 0);
 382     switch (__CFDictionaryGetType(dict)) {
 383     case __kCFDictionaryImmutable:
 384         CFStringAppendFormat(result, NULL, CFSTR("<CFDictionary %p [%p]>{type = immutable, count = %u, capacity = %u, pairs = (\n"), cf, allocator, dict->_count, dict->_capacity);
 385         break;
 386     case __kCFDictionaryFixedMutable:
 387         CFStringAppendFormat(result, NULL, CFSTR("<CFDictionary %p [%p]>{type = fixed-mutable, count = %u, capacity = %u, pairs = (\n"), cf, allocator, dict->_count, dict->_capacity);
 388         break;
 389     case __kCFDictionaryMutable:
 390         CFStringAppendFormat(result, NULL, CFSTR("<CFDictionary %p [%p]>{type = mutable, count = %u, capacity = %u, pairs = (\n"), cf, allocator, dict->_count, dict->_capacity);
 391         break;
 392     }
 393     for (idx = 0; idx < nbuckets; idx++) {
 394         if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
 395             CFStringRef kDesc = NULL, vDesc = NULL;
 396             if (NULL != cb->copyDescription) {
 397                 kDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))cb->copyDescription), keys[idx], dict->_context);
 398             }
 399             if (NULL != vcb->copyDescription) {
 400                 vDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))vcb->copyDescription), dict->_values[idx], dict->_context);
 401             }
 402             if (NULL != kDesc && NULL != vDesc) {
 403                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = %@\n"), idx, kDesc, vDesc);
 404                 CFRelease(kDesc);
 405                 CFRelease(vDesc);
 406             } else if (NULL != kDesc) {
 407                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = <%p>\n"), idx, kDesc, dict->_values[idx]);
 408                 CFRelease(kDesc);
 409             } else if (NULL != vDesc) {
 410                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = %@\n"), idx, keys[idx], vDesc);
 411                 CFRelease(vDesc);
 412             } else {
 413                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = <%p>\n"), idx, keys[idx], dict->_values[idx]);
 414             }
 415         }
 416     }
 417     CFStringAppend(result, CFSTR(")}"));
 418     return result;
 419 }
 420
 421 static void __CFDictionaryDeallocate(CFTypeRef cf) {
 422     CFMutableDictionaryRef dict = (CFMutableDictionaryRef)cf;
 423     CFAllocatorRef allocator = __CFGetAllocator(dict);
 424     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 425         const CFDictionaryKeyCallBacks *kcb = __CFDictionaryGetKeyCallBacks(dict);
 426         const CFDictionaryValueCallBacks *vcb = __CFDictionaryGetValueCallBacks(dict);
 427         if (kcb->retain == NULL && kcb->release == NULL && vcb->retain == NULL && vcb->release == NULL)
 428             return; // XXX_PCB keep dictionary intact during finalization.
 429     }
 430     if (__CFDictionaryGetType(dict) == __kCFDictionaryImmutable) {
 431         __CFBitfieldSetValue(((CFRuntimeBase *)dict)->_info, 1, 0, __kCFDictionaryFixedMutable);
 432     }
 433
 434     const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
 435     const CFDictionaryValueCallBacks *vcb = __CFDictionaryGetValueCallBacks(dict);
 436     if (vcb->release || cb->release) {
 437         const void **keys = dict->_keys;
 438         CFIndex idx, nbuckets = dict->_bucketsNum;
 439         for (idx = 0; idx < nbuckets; idx++) {
 440             if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
 441                 const void *oldkey = keys[idx];
 442                 if (vcb->release) {
 443                     INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[idx], dict->_context);
 444                 }
 445                 if (cb->release) {
 446                     INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, oldkey, dict->_context);
 447                 }
 448             }
 449         }
 450     }
 451
 452     if (__CFDictionaryGetType(dict) == __kCFDictionaryMutable && dict->_keys) {
 453         _CFAllocatorDeallocateGC(allocator, dict->_keys);
 454         if (_CFDictionaryIsSplit(dict)) {   // iff GC, split allocations
 455             _CFAllocatorDeallocateGC(allocator, dict->_values);
 456         }
 457         dict->_keys = NULL;
 458         dict->_values = NULL;
 459     }
 460 }
 461
 462 /*
 463  * When running under GC, we suss up dictionaries with standard string copy to hold
 464  * onto everything, including the copies of incoming keys, in strong memory without retain counts.
 465  * This is the routine that makes that copy.
 466  * Not for inputs of constant strings we'll get a constant string back, and so the result
 467  * is not guaranteed to be from the auto zone, hence the call to CFRelease since it will figure
 468  * out where the refcount really is.
 469  */
 470 static CFStringRef _CFStringCreateCopyCollected(CFAllocatorRef allocator, CFStringRef theString) {
 471     return CFMakeCollectable(CFStringCreateCopy(NULL, theString));
 472 }
 473
 474 static CFTypeID __kCFDictionaryTypeID = _kCFRuntimeNotATypeID;
 475
 476 static const CFRuntimeClass __CFDictionaryClass = {
 477     _kCFRuntimeScannedObject,
 478     "CFDictionary",
 479     NULL,       // init
 480     NULL,       // copy
 481     __CFDictionaryDeallocate,
 482     (void *)__CFDictionaryEqual,
 483     __CFDictionaryHash,
 484     NULL,       //
 485     __CFDictionaryCopyDescription
 486 };
 487
 488 __private_extern__ void __CFDictionaryInitialize(void) {
 489     __kCFDictionaryTypeID = _CFRuntimeRegisterClass(&__CFDictionaryClass);
 490 }
 491
 492 CFTypeID CFDictionaryGetTypeID(void) {
 493     return __kCFDictionaryTypeID;
 494 }
 495
 496 static CFDictionaryRef __CFDictionaryInit(CFAllocatorRef allocator, uint32_t flags, CFIndex capacity, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
 497     struct __CFDictionary *memory;
 498     uint32_t size;
 499     CFIndex idx;
 500     __CFBitfieldSetValue(flags, 31, 2, 0);
 501     CFDictionaryKeyCallBacks nonRetainingKeyCallbacks;
 502     CFDictionaryValueCallBacks nonRetainingValueCallbacks;
 503     CFOptionFlags xflags = 0;
 504     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 505         // preserve NULL for key or value CB, otherwise fix up.
 506         if (!keyCallBacks || (keyCallBacks->retain == NULL && keyCallBacks->release == NULL)) {
 507             xflags = __kCFDictionaryWeakKeys;
 508         }
 509         else {
 510             if (keyCallBacks->retain == __CFTypeCollectionRetain && keyCallBacks->release == __CFTypeCollectionRelease) {
 511                 // copy everything
 512                 nonRetainingKeyCallbacks = *keyCallBacks;
 513                 nonRetainingKeyCallbacks.retain = NULL;
 514                 nonRetainingKeyCallbacks.release = NULL;
 515                 keyCallBacks = &nonRetainingKeyCallbacks;
 516                 xflags = __kCFDictionaryRestoreKeys;
 517             }
 518             else if (keyCallBacks->retain == CFStringCreateCopy && keyCallBacks->release == __CFTypeCollectionRelease) {
 519                 // copy everything
 520                 nonRetainingKeyCallbacks = *keyCallBacks;
 521                 nonRetainingKeyCallbacks.retain = (void *)_CFStringCreateCopyCollected;   // XXX fix with better cast
 522                 nonRetainingKeyCallbacks.release = NULL;
 523                 keyCallBacks = &nonRetainingKeyCallbacks;
 524                 xflags = (__kCFDictionaryRestoreKeys | __kCFDictionaryRestoreStringKeys);
 525             }
 526         }
 527         if (!valueCallBacks || (valueCallBacks->retain == NULL && valueCallBacks->release == NULL)) {
 528             xflags |= __kCFDictionaryWeakValues;
 529         }
 530         else {
 531             if (valueCallBacks->retain == __CFTypeCollectionRetain && valueCallBacks->release == __CFTypeCollectionRelease) {
 532                 nonRetainingValueCallbacks = *valueCallBacks;
 533                 nonRetainingValueCallbacks.retain = NULL;
 534                 nonRetainingValueCallbacks.release = NULL;
 535                 valueCallBacks = &nonRetainingValueCallbacks;
 536                 xflags |= __kCFDictionaryRestoreValues;
 537             }
 538         }
 539     }
 540     if (__CFDictionaryKeyCallBacksMatchNull(keyCallBacks)) {
 541         __CFBitfieldSetValue(flags, 3, 2, __kCFDictionaryHasNullCallBacks);
 542     } else if (__CFDictionaryKeyCallBacksMatchCFType(keyCallBacks)) {
 543         __CFBitfieldSetValue(flags, 3, 2, __kCFDictionaryHasCFTypeCallBacks);
 544     } else {
 545         __CFBitfieldSetValue(flags, 3, 2, __kCFDictionaryHasCustomCallBacks);
 546     }
 547     if (__CFDictionaryValueCallBacksMatchNull(valueCallBacks)) {
 548         __CFBitfieldSetValue(flags, 5, 4, __kCFDictionaryHasNullCallBacks);
 549     } else if (__CFDictionaryValueCallBacksMatchCFType(valueCallBacks)) {
 550         __CFBitfieldSetValue(flags, 5, 4, __kCFDictionaryHasCFTypeCallBacks);
 551     } else {
 552         __CFBitfieldSetValue(flags, 5, 4, __kCFDictionaryHasCustomCallBacks);
 553     }
 554     size = __CFDictionaryGetSizeOfType(flags) - sizeof(CFRuntimeBase);
 555     switch (__CFBitfieldGetValue(flags, 1, 0)) {
 556     case __kCFDictionaryImmutable:
 557     case __kCFDictionaryFixedMutable:
 558         size += 2 * __CFDictionaryNumBucketsForCapacity(capacity) * sizeof(const void *);
 559         break;
 560     case __kCFDictionaryMutable:
 561         break;
 562     }
 563     memory = (struct __CFDictionary *)_CFRuntimeCreateInstance(allocator, __kCFDictionaryTypeID, size, NULL);
 564     if (NULL == memory) {
 565         return NULL;
 566     }
 567     __CFBitfieldSetValue(memory->_base._info, 6, 0, flags);
 568     memory->_count = 0;
 569     memory->_marker = (uintptr_t)0xa1b1c1d3;
 570     memory->_context = NULL;
 571     memory->_deletes = 0;
 572     memory->_xflags = xflags;
 573     switch (__CFBitfieldGetValue(flags, 1, 0)) {
 574     case __kCFDictionaryImmutable:
 575         // GC note: we can't support weak part of mixed weak/strong in fixed case, we treat it as strong XXX blaine
 576         if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)
 577                 && (xflags & (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) == (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) { // if both weak, don't scan
 578             auto_zone_set_layout_type(__CFCollectableZone, memory, AUTO_OBJECT_UNSCANNED);
 579         }
 580         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFDictionary (immutable)");
 581         memory->_capacity = capacity;   /* Don't round up capacity */
 582         memory->_bucketsNum = __CFDictionaryNumBucketsForCapacity(memory->_capacity);
 583         memory->_keys = (const void **)((uint8_t *)memory + __CFDictionaryGetSizeOfType(flags));
 584         memory->_values = (const void **)(memory->_keys + memory->_bucketsNum);
 585         for (idx = memory->_bucketsNum; idx--;) {
 586             memory->_keys[idx] = (const void *)memory->_marker;
 587         }
 588         break;
 589     case __kCFDictionaryFixedMutable:
 590         // GC note: we can't support weak part of mixed weak/strong in fixed case, we treat it as strong XXX blaine
 591         if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)
 592                 && (xflags & (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) == (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) { // if both weak, don't scan
 593             auto_zone_set_layout_type(__CFCollectableZone, memory, AUTO_OBJECT_UNSCANNED);
 594         }
 595         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFDictionary (mutable-fixed)");
 596         memory->_capacity = capacity;   /* Don't round up capacity */
 597         memory->_bucketsNum = __CFDictionaryNumBucketsForCapacity(memory->_capacity);
 598         memory->_keys = (const void **)((uint8_t *)memory + __CFDictionaryGetSizeOfType(flags));
 599         memory->_values = (const void **)(memory->_keys + memory->_bucketsNum);
 600         for (idx = memory->_bucketsNum; idx--;) {
 601             memory->_keys[idx] = (const void *)memory->_marker;
 602         }
 603         break;
 604     case __kCFDictionaryMutable:
 605         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFDictionary (mutable-variable)");
 606         memory->_capacity = __CFDictionaryRoundUpCapacity(1);
 607         memory->_bucketsNum = 0;
 608         memory->_keys = NULL;
 609         memory->_values = NULL;
 610         break;
 611     }
 612     if (__kCFDictionaryHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
 613         CFDictionaryKeyCallBacks *cb = (CFDictionaryKeyCallBacks *)__CFDictionaryGetKeyCallBacks((CFDictionaryRef)memory);
 614         *cb = *keyCallBacks;
 615         FAULT_CALLBACK((void **)&(cb->retain));
 616         FAULT_CALLBACK((void **)&(cb->release));
 617         FAULT_CALLBACK((void **)&(cb->copyDescription));
 618         FAULT_CALLBACK((void **)&(cb->equal));
 619         FAULT_CALLBACK((void **)&(cb->hash));
 620     }
 621     if (__kCFDictionaryHasCustomCallBacks == __CFBitfieldGetValue(flags, 5, 4)) {
 622         CFDictionaryValueCallBacks *vcb = (CFDictionaryValueCallBacks *)__CFDictionaryGetValueCallBacks((CFDictionaryRef)memory);
 623         *vcb = *valueCallBacks;
 624         FAULT_CALLBACK((void **)&(vcb->retain));
 625         FAULT_CALLBACK((void **)&(vcb->release));
 626         FAULT_CALLBACK((void **)&(vcb->copyDescription));
 627         FAULT_CALLBACK((void **)&(vcb->equal));
 628     }
 629     return (CFDictionaryRef)memory;
 630 }
 631
 632 CFDictionaryRef CFDictionaryCreate(CFAllocatorRef allocator, const void **keys, const void **values, CFIndex numValues, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
 633     CFDictionaryRef result;
 634     uint32_t flags;
 635     CFIndex idx;
 636     CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
 637     result = __CFDictionaryInit(allocator, __kCFDictionaryImmutable, numValues, keyCallBacks, valueCallBacks);
 638     flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
 639     if (flags == __kCFDictionaryImmutable) {
 640         // tweak flags so that we can add our immutable values
 641         __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFDictionaryFixedMutable);
 642     }
 643     for (idx = 0; idx < numValues; idx++) {
 644         CFDictionaryAddValue((CFMutableDictionaryRef)result, keys[idx], values[idx]);
 645     }
 646     __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
 647     return result;
 648 }
 649
 650 CFMutableDictionaryRef CFDictionaryCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
 651     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 652     return (CFMutableDictionaryRef)__CFDictionaryInit(allocator, (0 == capacity) ? __kCFDictionaryMutable : __kCFDictionaryFixedMutable, capacity, keyCallBacks, valueCallBacks);
 653 }
 654
 655 static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues);
 656
 657 // This creates a dictionary which is for CFTypes or NSObjects, with an ownership transfer --
 658 // the dictionary does not take a retain, and the caller does not need to release the inserted objects.
 659 // The incoming objects must also be collectable if allocated out of a collectable allocator.
 660 CFDictionaryRef _CFDictionaryCreate_ex(CFAllocatorRef allocator, bool mutable, const void **keys, const void **values, CFIndex numValues) {
 661     CFDictionaryRef result;
 662     void *bucketsBase;
 663     uint32_t flags;
 664     CFIndex idx;
 665     result = __CFDictionaryInit(allocator, mutable ? __kCFDictionaryMutable : __kCFDictionaryImmutable, numValues, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
 666     flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
 667     if (!mutable) {
 668         __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFDictionaryFixedMutable);
 669     }
 670     if (mutable) {
 671         if (result->_count == result->_capacity || NULL == result->_keys) {
 672             __CFDictionaryGrow((CFMutableDictionaryRef)result, numValues);
 673         }
 674     }
 675     // GC:  since kCFTypeDictionaryKeyCallBacks & kCFTypeDictionaryValueCallBacks are used, the keys
 676     // and values will be allocated contiguously.
 677     bool collectableContainer = CF_IS_COLLECTABLE_ALLOCATOR(allocator);
 678     bucketsBase = (collectableContainer ? auto_zone_base_pointer(__CFCollectableZone, result->_keys) : NULL);
 679     for (idx = 0; idx < numValues; idx++) {
 680         CFIndex match, nomatch;
 681         const void *newKey;
 682         __CFDictionaryFindBuckets2(result, keys[idx], &match, &nomatch);
 683         if (kCFNotFound != match) {
 684             if (!collectableContainer) CFRelease(result->_values[match]);
 685             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, bucketsBase, result->_values[match], values[idx]);
 686             // GC: generation(_values) <= generation(values), but added for completeness.
 687         } else {
 688             newKey = keys[idx];
 689             if (result->_marker == (uintptr_t)newKey || ~result->_marker == (uintptr_t)newKey) {
 690                 __CFDictionaryFindNewMarker(result);
 691             }
 692             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, bucketsBase, result->_keys[nomatch], newKey);
 693             CF_WRITE_BARRIER_BASE_ASSIGN(allocator, bucketsBase, result->_values[nomatch], values[idx]);
 694             // GC: generation(_keys/_values) <= generation(keys/values), but added for completeness.
 695             ((CFMutableDictionaryRef)result)->_count++;
 696         }
 697     }
 698     __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
 699     return result;
 700 }
 701
 702 CFDictionaryRef CFDictionaryCreateCopy(CFAllocatorRef allocator, CFDictionaryRef dict) {
 703     CFDictionaryRef result;
 704     const CFDictionaryKeyCallBacks *cb;
 705     const CFDictionaryValueCallBacks *vcb;
 706     CFIndex numValues = CFDictionaryGetCount(dict);
 707     const void **list, *buffer[256];
 708     const void **vlist, *vbuffer[256];
 709     list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
 710     if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFDictionary (temp)");
 711     vlist = (numValues <= 256) ? vbuffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
 712     if (vlist != vbuffer && __CFOASafe) __CFSetLastAllocationEventName(vlist, "CFDictionary (temp)");
 713     CFDictionaryGetKeysAndValues(dict, list, vlist);
 714     CFDictionaryKeyCallBacks patchedKeyCB;
 715     CFDictionaryValueCallBacks patchedValueCB;
 716     if (CF_IS_OBJC(__kCFDictionaryTypeID, dict)) {
 717         cb = &kCFTypeDictionaryKeyCallBacks;
 718         vcb = &kCFTypeDictionaryValueCallBacks;
 719     }
 720     else {
 721         cb = __CFDictionaryGetKeyCallBacks(dict);
 722         vcb = __CFDictionaryGetValueCallBacks(dict);
 723         if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 724             if (dict->_xflags & __kCFDictionaryRestoreKeys) {
 725                 patchedKeyCB = *cb;    // copy
 726                 cb = &patchedKeyCB;    // reset to copy
 727                 patchedKeyCB.retain = (dict->_xflags & __kCFDictionaryRestoreStringKeys) ? CFStringCreateCopy : __CFTypeCollectionRetain;
 728                 patchedKeyCB.release = __CFTypeCollectionRelease;
 729             }
 730             if (dict->_xflags & __kCFDictionaryRestoreValues) {
 731                 patchedValueCB = *vcb;    // copy
 732                 vcb = &patchedValueCB;    // reset to copy
 733                 patchedValueCB.retain = __CFTypeCollectionRetain;
 734                 patchedValueCB.release = __CFTypeCollectionRelease;
 735             }
 736         }
 737     }
 738     result = CFDictionaryCreate(allocator, list, vlist, numValues, cb, vcb);
 739     if (list != buffer) CFAllocatorDeallocate(allocator, list); // GC OK
 740     if (vlist != vbuffer) CFAllocatorDeallocate(allocator, vlist); // GC OK
 741     return result;
 742 }
 743
 744 CFMutableDictionaryRef CFDictionaryCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFDictionaryRef dict) {
 745     CFMutableDictionaryRef result;
 746     const CFDictionaryKeyCallBacks *cb;
 747     const CFDictionaryValueCallBacks *vcb;
 748     CFIndex idx, numValues = CFDictionaryGetCount(dict);
 749     const void **list, *buffer[256];
 750     const void **vlist, *vbuffer[256];
 751     CFAssert3(0 == capacity || numValues <= capacity, __kCFLogAssertion, "%s(): for fixed-mutable dicts, capacity (%d) must be greater than or equal to initial number of values (%d)", __PRETTY_FUNCTION__, capacity, numValues);
 752     list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
 753     if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFDictionary (temp)");
 754     vlist = (numValues <= 256) ? vbuffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
 755     if (vlist != vbuffer && __CFOASafe) __CFSetLastAllocationEventName(vlist, "CFDictionary (temp)");
 756     CFDictionaryGetKeysAndValues(dict, list, vlist);
 757     CFDictionaryKeyCallBacks patchedKeyCB;
 758     CFDictionaryValueCallBacks patchedValueCB;
 759     if (CF_IS_OBJC(__kCFDictionaryTypeID, dict)) {
 760         cb = &kCFTypeDictionaryKeyCallBacks;
 761         vcb = &kCFTypeDictionaryValueCallBacks;
 762     }
 763     else {
 764         cb = __CFDictionaryGetKeyCallBacks(dict);
 765         vcb = __CFDictionaryGetValueCallBacks(dict);
 766         if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 767             if (dict->_xflags & __kCFDictionaryRestoreKeys) {
 768                 patchedKeyCB = *cb;    // copy
 769                 cb = &patchedKeyCB;    // reset to copy
 770                 patchedKeyCB.retain = (dict->_xflags & __kCFDictionaryRestoreStringKeys) ? CFStringCreateCopy : __CFTypeCollectionRetain;
 771                 patchedKeyCB.release = __CFTypeCollectionRelease;
 772             }
 773             if (dict->_xflags & __kCFDictionaryRestoreValues) {
 774                 patchedValueCB = *vcb;    // copy
 775                 vcb = &patchedValueCB;    // reset to copy
 776                 patchedValueCB.retain = __CFTypeCollectionRetain;
 777                 patchedValueCB.release = __CFTypeCollectionRelease;
 778             }
 779         }
 780     }
 781     result = CFDictionaryCreateMutable(allocator, capacity, cb, vcb);
 782     if (0 == capacity) _CFDictionarySetCapacity(result, numValues);
 783     for (idx = 0; idx < numValues; idx++) {
 784         CFDictionaryAddValue(result, list[idx], vlist[idx]);
 785     }
 786     if (list != buffer) CFAllocatorDeallocate(allocator, list); // XXX_PCB GC OK
 787     if (vlist != vbuffer) CFAllocatorDeallocate(allocator, vlist); // XXX_PCB GC OK
 788     return result;
 789 }
 790
 791
 792
 793 // Used by NSMapTables and KVO
 794 void _CFDictionarySetContext(CFDictionaryRef dict, void *context) {
 795     CFAllocatorRef allocator = CFGetAllocator(dict);
 796     CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_context, context);
 797 }
 798
 799 void *_CFDictionaryGetContext(CFDictionaryRef dict) {
 800     return ((struct __CFDictionary *)dict)->_context;
 801 }
 802
 803 CFIndex CFDictionaryGetCount(CFDictionaryRef dict) {
 804     CF_OBJC_FUNCDISPATCH0(__kCFDictionaryTypeID, CFIndex, dict, "count");
 805     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 806     return dict->_count;
 807 }
 808
 809 CFIndex CFDictionaryGetCountOfKey(CFDictionaryRef dict, const void *key) {
 810     CFIndex match;
 811     CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, CFIndex, dict, "countForKey:", key);
 812     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 813     if (0 == dict->_count) return 0;
 814     if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
 815         match = __CFDictionaryFindBuckets1a(dict, key);
 816     } else {
 817         match = __CFDictionaryFindBuckets1b(dict, key);
 818     }
 819     return (kCFNotFound != match ? 1 : 0);
 820 }
 821
 822 CFIndex CFDictionaryGetCountOfValue(CFDictionaryRef dict, const void *value) {
 823     const void **keys;
 824     const CFDictionaryValueCallBacks *vcb;
 825     CFIndex idx, cnt = 0, nbuckets;
 826     CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, CFIndex, dict, "countForObject:", value);
 827     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 828     if (0 == dict->_count) return 0;
 829     keys = dict->_keys;
 830     nbuckets = dict->_bucketsNum;
 831     vcb = __CFDictionaryGetValueCallBacks(dict);
 832     for (idx = 0; idx < nbuckets; idx++) {
 833         if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
 834             if ((dict->_values[idx] == value) || (vcb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))vcb->equal, dict->_values[idx], value, dict->_context))) {
 835                 cnt++;
 836             }
 837         }
 838     }
 839     return cnt;
 840 }
 841
 842 Boolean CFDictionaryContainsKey(CFDictionaryRef dict, const void *key) {
 843     CFIndex match;
 844     CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, char, dict, "containsKey:", key);
 845     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 846     if (0 == dict->_count) return false;
 847     if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
 848         match = __CFDictionaryFindBuckets1a(dict, key);
 849     } else {
 850         match = __CFDictionaryFindBuckets1b(dict, key);
 851     }
 852     return (kCFNotFound != match ? true : false);
 853 }
 854
 855 Boolean CFDictionaryContainsValue(CFDictionaryRef dict, const void *value) {
 856     const void **keys;
 857     const CFDictionaryValueCallBacks *vcb;
 858     CFIndex idx, nbuckets;
 859     CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, char, dict, "containsObject:", value);
 860     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 861     if (0 == dict->_count) return false;
 862     keys = dict->_keys;
 863     nbuckets = dict->_bucketsNum;
 864     vcb = __CFDictionaryGetValueCallBacks(dict);
 865     for (idx = 0; idx < nbuckets; idx++) {
 866         if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
 867             if ((dict->_values[idx] == value) || (vcb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))vcb->equal, dict->_values[idx], value, dict->_context))) {
 868                 return true;
 869             }
 870         }
 871     }
 872     return false;
 873 }
 874
 875 const void *CFDictionaryGetValue(CFDictionaryRef dict, const void *key) {
 876     CFIndex match;
 877     CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, const void *, dict, "objectForKey:", key);
 878     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 879     if (0 == dict->_count) return NULL;
 880     if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
 881         match = __CFDictionaryFindBuckets1a(dict, key);
 882     } else {
 883         match = __CFDictionaryFindBuckets1b(dict, key);
 884     }
 885     return (kCFNotFound != match ? dict->_values[match] : NULL);
 886 }
 887
 888 Boolean CFDictionaryGetValueIfPresent(CFDictionaryRef dict, const void *key, const void **value) {
 889     CFIndex match;
 890     CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, char, dict, "_getValue:forKey:", (void * *)value, key);
 891     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 892     if (0 == dict->_count) return false;
 893     if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
 894         match = __CFDictionaryFindBuckets1a(dict, key);
 895     } else {
 896         match = __CFDictionaryFindBuckets1b(dict, key);
 897     }
 898     return (kCFNotFound != match ? ((value ? __CFObjCStrongAssign(dict->_values[match], value) : NULL), true) : false);
 899 }
 900
 901 bool CFDictionaryGetKeyIfPresent(CFDictionaryRef dict, const void *key, const void **actualkey) {
 902     CFIndex match;
 903 //#warning CF: not toll-free bridged
 904     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 905     if (0 == dict->_count) return false;
 906     if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
 907         match = __CFDictionaryFindBuckets1a(dict, key);
 908     } else {
 909         match = __CFDictionaryFindBuckets1b(dict, key);
 910     }
 911     return (kCFNotFound != match ? ((actualkey ? __CFObjCStrongAssign(dict->_keys[match], actualkey) : NULL), true) : false);
 912 }
 913
 914 void CFDictionaryGetKeysAndValues(CFDictionaryRef dict, const void **keys, const void **values) {
 915     CFIndex idx, cnt, nbuckets;
 916     CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "getObjects:andKeys:", (void * *)values, (void * *)keys);
 917     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 918     if (CF_USING_COLLECTABLE_MEMORY) {
 919         // GC: speculatively issue a write-barrier on the copied to buffers (3743553).
 920         __CFObjCWriteBarrierRange(keys, dict->_count * sizeof(void *));
 921         __CFObjCWriteBarrierRange(values, dict->_count * sizeof(void *));
 922     }
 923     nbuckets = dict->_bucketsNum;
 924     for (idx = 0; idx < nbuckets; idx++) {
 925         if (dict->_marker != (uintptr_t)dict->_keys[idx] && ~dict->_marker != (uintptr_t)dict->_keys[idx]) {
 926             for (cnt = 1; cnt--;) {
 927                 if (keys) *keys++ = dict->_keys[idx];
 928                 if (values) *values++ = dict->_values[idx];
 929             }
 930         }
 931     }
 932 }
 933
 934 void CFDictionaryApplyFunction(CFDictionaryRef dict, CFDictionaryApplierFunction applier, void *context) {
 935     const void **keys;
 936     CFIndex idx, cnt, nbuckets;
 937     FAULT_CALLBACK((void **)&(applier));
 938     CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "_apply:context:", applier, context);
 939     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
 940     keys = dict->_keys;
 941     nbuckets = dict->_bucketsNum;
 942     for (idx = 0; idx < nbuckets; idx++) {
 943         if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
 944             for (cnt = 1; cnt--;) {
 945                 INVOKE_CALLBACK3(applier, keys[idx], dict->_values[idx], context);
 946             }
 947         }
 948     }
 949 }
 950
 951 static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues) {
 952     const void **oldkeys = dict->_keys;
 953     const void **oldvalues = dict->_values;
 954     CFIndex idx, oldnbuckets = dict->_bucketsNum;
 955     CFIndex oldCount = dict->_count;
 956     CFAllocatorRef allocator = __CFGetAllocator(dict), keysAllocator, valuesAllocator;
 957     void *keysBase, *valuesBase;
 958     dict->_capacity = __CFDictionaryRoundUpCapacity(oldCount + numNewValues);
 959     dict->_bucketsNum = __CFDictionaryNumBucketsForCapacity(dict->_capacity);
 960     dict->_deletes = 0;
 961     if (_CFDictionaryIsSplit(dict)) {   // iff GC, use split memory sometimes unscanned memory
 962         unsigned weakOrStrong = (dict->_xflags & __kCFDictionaryWeakKeys) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED;
 963         void *mem = _CFAllocatorAllocateGC(allocator, dict->_bucketsNum * sizeof(const void *), weakOrStrong);
 964         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_keys, mem);
 965         keysAllocator = (dict->_xflags & __kCFDictionaryWeakKeys) ? kCFAllocatorNull : allocator;  // GC: avoids write-barrier in weak case.
 966         keysBase = mem;
 967
 968         weakOrStrong = (dict->_xflags & __kCFDictionaryWeakValues) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED;
 969         mem = _CFAllocatorAllocateGC(allocator, dict->_bucketsNum * sizeof(const void *), weakOrStrong);
 970         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_values, mem);
 971         valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator; // GC: avoids write-barrier in weak case.
 972         valuesBase = mem;
 973     } else {
 974         CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_keys, _CFAllocatorAllocateGC(allocator, 2 * dict->_bucketsNum * sizeof(const void *), AUTO_MEMORY_SCANNED));
 975         dict->_values = (const void **)(dict->_keys + dict->_bucketsNum);
 976         keysAllocator = valuesAllocator = allocator;
 977         keysBase = valuesBase = dict->_keys;
 978     }
 979     if (NULL == dict->_keys || NULL == dict->_values) HALT;
 980     if (__CFOASafe) __CFSetLastAllocationEventName(dict->_keys, "CFDictionary (store)");
 981     for (idx = dict->_bucketsNum; idx--;) {
 982         dict->_keys[idx] = (const void *)dict->_marker;
 983         dict->_values[idx] = 0;
 984     }
 985     if (NULL == oldkeys) return;
 986     for (idx = 0; idx < oldnbuckets; idx++) {
 987         if (dict->_marker != (uintptr_t)oldkeys[idx] && ~dict->_marker != (uintptr_t)oldkeys[idx]) {
 988             CFIndex match, nomatch;
 989             __CFDictionaryFindBuckets2(dict, oldkeys[idx], &match, &nomatch);
 990             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], dict->_keys[match]);
 991             if (kCFNotFound != nomatch) {
 992                 CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, dict->_keys[nomatch], oldkeys[idx]);
 993                 CF_WRITE_BARRIER_BASE_ASSIGN(valuesAllocator, valuesBase, dict->_values[nomatch], oldvalues[idx]);
 994             }
 995         }
 996     }
 997     CFAssert1(dict->_count == oldCount, __kCFLogAssertion, "%s(): dict count differs after rehashing; error", __PRETTY_FUNCTION__);
 998     _CFAllocatorDeallocateGC(allocator, oldkeys);
 999     if (_CFDictionaryIsSplit(dict)) _CFAllocatorDeallocateGC(allocator, oldvalues);
1000 }
1001
1002 // This function is for Foundation's benefit; no one else should use it.
1003 void _CFDictionarySetCapacity(CFMutableDictionaryRef dict, CFIndex cap) {
1004     if (CF_IS_OBJC(__kCFDictionaryTypeID, dict)) return;
1005 #if defined(DEBUG)
1006     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1007     CFAssert1(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable && __CFDictionaryGetType(dict) != __kCFDictionaryFixedMutable, __kCFLogAssertion, "%s(): dict is immutable or fixed-mutable", __PRETTY_FUNCTION__);
1008     CFAssert3(dict->_count <= cap, __kCFLogAssertion, "%s(): desired capacity (%d) is less than count (%d)", __PRETTY_FUNCTION__, cap, dict->_count);
1009 #endif
1010     __CFDictionaryGrow(dict, cap - dict->_count);
1011 }
1012
1013
1014 void CFDictionaryAddValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
1015     CFIndex match, nomatch;
1016     const CFDictionaryKeyCallBacks *cb;
1017     const CFDictionaryValueCallBacks *vcb;
1018     const void *newKey, *newValue;
1019     CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "_addObject:forKey:", value, key);
1020     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1021     switch (__CFDictionaryGetType(dict)) {
1022     case __kCFDictionaryMutable:
1023         if (dict->_count == dict->_capacity || NULL == dict->_keys) {
1024             __CFDictionaryGrow(dict, 1);
1025         }
1026         break;
1027     case __kCFDictionaryFixedMutable:
1028         CFAssert3(dict->_count < dict->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity dict %p (capacity = %d)", __PRETTY_FUNCTION__, dict, dict->_capacity);
1029         break;
1030     default:
1031         CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
1032         break;
1033     }
1034     __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
1035     if (kCFNotFound != match) {
1036     } else {
1037         CFAllocatorRef allocator = __CFGetAllocator(dict);
1038         CFAllocatorRef keysAllocator = (dict->_xflags & __kCFDictionaryWeakKeys) ? kCFAllocatorNull : allocator;
1039         CFAllocatorRef valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator;
1040         cb = __CFDictionaryGetKeyCallBacks(dict);
1041         vcb = __CFDictionaryGetValueCallBacks(dict);
1042         if (cb->retain) {
1043             newKey = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, key, dict->_context);
1044         } else {
1045             newKey = key;
1046         }
1047         if (vcb->retain) {
1048             newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), allocator, value, dict->_context);
1049         } else {
1050             newValue = value;
1051         }
1052         if (dict->_marker == (uintptr_t)newKey || ~dict->_marker == (uintptr_t)newKey) {
1053             __CFDictionaryFindNewMarker(dict);
1054         }
1055         CF_OBJC_KVO_WILLCHANGE(dict, key);
1056         CF_WRITE_BARRIER_ASSIGN(keysAllocator, dict->_keys[nomatch], newKey);
1057         CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[nomatch], newValue);
1058         dict->_count++;
1059         CF_OBJC_KVO_DIDCHANGE(dict, key);
1060     }
1061 }
1062
1063 void CFDictionaryReplaceValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
1064     CFIndex match;
1065     const CFDictionaryValueCallBacks *vcb;
1066     const void *newValue;
1067     CFAllocatorRef allocator, valuesAllocator;
1068     CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "_replaceObject:forKey:", value, key);
1069     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1070     switch (__CFDictionaryGetType(dict)) {
1071     case __kCFDictionaryMutable:
1072     case __kCFDictionaryFixedMutable:
1073         break;
1074     default:
1075         CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
1076         break;
1077     }
1078     if (0 == dict->_count) return;
1079     if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
1080         match = __CFDictionaryFindBuckets1a(dict, key);
1081     } else {
1082         match = __CFDictionaryFindBuckets1b(dict, key);
1083     }
1084     if (kCFNotFound == match) return;
1085     vcb = __CFDictionaryGetValueCallBacks(dict);
1086     allocator = __CFGetAllocator(dict);
1087     valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator;
1088     if (vcb->retain) {
1089         newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), allocator, value, dict->_context);
1090     } else {
1091         newValue = value;
1092     }
1093     CF_OBJC_KVO_WILLCHANGE(dict, key);
1094     if (vcb->release) {
1095         INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[match], dict->_context);
1096     }
1097     CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[match], newValue);
1098     CF_OBJC_KVO_DIDCHANGE(dict, key);
1099 }
1100
1101 void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
1102     CFIndex match, nomatch;
1103     const CFDictionaryKeyCallBacks *cb;
1104     const CFDictionaryValueCallBacks *vcb;
1105     const void *newKey, *newValue;
1106     CFAllocatorRef allocator, keysAllocator, valuesAllocator;
1107     CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "setObject:forKey:", value, key);
1108     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1109     switch (__CFDictionaryGetType(dict)) {
1110     case __kCFDictionaryMutable:
1111         if (dict->_count == dict->_capacity || NULL == dict->_keys) {
1112             __CFDictionaryGrow(dict, 1);
1113         }
1114         break;
1115     case __kCFDictionaryFixedMutable:
1116         break;
1117     default:
1118         CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
1119         break;
1120     }
1121     __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
1122     vcb = __CFDictionaryGetValueCallBacks(dict);
1123     allocator = __CFGetAllocator(dict);
1124     keysAllocator = (dict->_xflags & __kCFDictionaryWeakKeys) ? kCFAllocatorNull : allocator;
1125     valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator;
1126     if (vcb->retain) {
1127         newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), allocator, value, dict->_context);
1128     } else {
1129         newValue = value;
1130     }
1131     if (kCFNotFound != match) {
1132         CF_OBJC_KVO_WILLCHANGE(dict, key);
1133         if (vcb->release) {
1134             INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[match], dict->_context);
1135         }
1136         CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[match], newValue);
1137         CF_OBJC_KVO_DIDCHANGE(dict, key);
1138     } else {
1139         CFAssert3(__kCFDictionaryFixedMutable != __CFDictionaryGetType(dict) || dict->_count < dict->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity dict %p (capacity = %d)", __PRETTY_FUNCTION__, dict, dict->_capacity);
1140         cb = __CFDictionaryGetKeyCallBacks(dict);
1141         if (cb->retain) {
1142             newKey = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, key, dict->_context);
1143         } else {
1144             newKey = key;
1145         }
1146         if (dict->_marker == (uintptr_t)newKey || ~dict->_marker == (uintptr_t)newKey) {
1147             __CFDictionaryFindNewMarker(dict);
1148         }
1149         CF_OBJC_KVO_WILLCHANGE(dict, key);
1150         CF_WRITE_BARRIER_ASSIGN(keysAllocator, dict->_keys[nomatch], newKey);
1151         CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[nomatch], newValue);
1152         dict->_count++;
1153         CF_OBJC_KVO_DIDCHANGE(dict, key);
1154     }
1155 }
1156
1157 void CFDictionaryRemoveValue(CFMutableDictionaryRef dict, const void *key) {
1158     CFIndex match;
1159     const CFDictionaryKeyCallBacks *cb;
1160     const CFDictionaryValueCallBacks *vcb;
1161     CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, void, dict, "removeObjectForKey:", key);
1162     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1163     switch (__CFDictionaryGetType(dict)) {
1164     case __kCFDictionaryMutable:
1165     case __kCFDictionaryFixedMutable:
1166         break;
1167     default:
1168         CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
1169         break;
1170     }
1171     if (0 == dict->_count) return;
1172     if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
1173         match = __CFDictionaryFindBuckets1a(dict, key);
1174     } else {
1175         match = __CFDictionaryFindBuckets1b(dict, key);
1176     }
1177     if (kCFNotFound == match) return;
1178     if (1) {
1179         cb = __CFDictionaryGetKeyCallBacks(dict);
1180         vcb = __CFDictionaryGetValueCallBacks(dict);
1181         const void *oldkey = dict->_keys[match];
1182         CFAllocatorRef allocator = CFGetAllocator(dict);
1183         CF_OBJC_KVO_WILLCHANGE(dict, oldkey);
1184         if (vcb->release) {
1185             INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[match], dict->_context);
1186         }
1187         dict->_keys[match] = (const void *)~dict->_marker;
1188         dict->_values[match] = 0;
1189         dict->_count--;
1190         CF_OBJC_KVO_DIDCHANGE(dict, oldkey);
1191         if (cb->release) {
1192             INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(dict), oldkey, dict->_context);
1193         }
1194         dict->_deletes++;
1195         // _CFDictionaryDecrementValue() below has this same code.
1196         if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (dict->_bucketsNum < 4 * dict->_deletes || (512 < dict->_capacity && 3.236067 * dict->_count < dict->_capacity))) {
1197             // 3.236067 == 2 * golden_mean; this comes about because we're trying to resize down
1198             // when the count is less than 2 capacities smaller, but not right away when count
1199             // is just less than 2 capacities smaller, because an add would then force growth;
1200             // well, the ratio between one capacity and the previous is close to the golden
1201             // mean currently, so (cap / m / m) would be two smaller; but so we're not close,
1202             // we take the average of that and the prior cap (cap / m / m / m). Well, after one
1203             // does the algebra, and uses the convenient fact that m^(x+2) = m^(x+1) + m^x if m
1204             // is the golden mean, this reduces to cap / 2m for the threshold. In general, the
1205             // possible threshold constant is 1 / (2 * m^k), k = 0, 1, 2, ... under this scheme.
1206             // Rehash; currently only for mutable-variable dictionaries
1207             __CFDictionaryGrow(dict, 0);
1208         } else {
1209             // When the probeskip == 1 always and only, a DELETED slot followed by an EMPTY slot
1210             // can be converted to an EMPTY slot.  By extension, a chain of DELETED slots followed
1211             // by an EMPTY slot can be converted to EMPTY slots, which is what we do here.
1212             // _CFDictionaryDecrementValue() below has this same code.
1213             if (match < dict->_bucketsNum - 1 && dict->_keys[match + 1] == (const void *)dict->_marker) {
1214                 while (0 <= match && dict->_keys[match] == (const void *)~dict->_marker) {
1215                     dict->_keys[match] = (const void *)dict->_marker;
1216                     dict->_deletes--;
1217                     match--;
1218                 }
1219             }
1220         }
1221     }
1222 }
1223
1224 void CFDictionaryRemoveAllValues(CFMutableDictionaryRef dict) {
1225     const void **keys;
1226     const CFDictionaryKeyCallBacks *cb;
1227     const CFDictionaryValueCallBacks *vcb;
1228     CFAllocatorRef allocator;
1229     CFIndex idx, nbuckets;
1230     CF_OBJC_FUNCDISPATCH0(__kCFDictionaryTypeID, void, dict, "removeAllObjects");
1231     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1232     switch (__CFDictionaryGetType(dict)) {
1233     case __kCFDictionaryMutable:
1234     case __kCFDictionaryFixedMutable:
1235         break;
1236     default:
1237         CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
1238         break;
1239     }
1240     if (0 == dict->_count) return;
1241     keys = dict->_keys;
1242     nbuckets = dict->_bucketsNum;
1243     cb = __CFDictionaryGetKeyCallBacks(dict);
1244     vcb = __CFDictionaryGetValueCallBacks(dict);
1245     allocator = __CFGetAllocator(dict);
1246     for (idx = 0; idx < nbuckets; idx++) {
1247         if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
1248             const void *oldkey = keys[idx];
1249             CF_OBJC_KVO_WILLCHANGE(dict, oldkey);
1250             if (vcb->release) {
1251                 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[idx], dict->_context);
1252             }
1253             keys[idx] = (const void *)~dict->_marker;
1254             dict->_values[idx] = 0;
1255             dict->_count--;
1256             CF_OBJC_KVO_DIDCHANGE(dict, oldkey);
1257             if (cb->release) {
1258                 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, oldkey, dict->_context);
1259             }
1260         }
1261     }
1262     // XXX need memset here
1263     for (idx = 0; idx < nbuckets; idx++) {
1264         keys[idx] = (const void *)dict->_marker;
1265         dict->_values[idx] = 0;
1266     }
1267     dict->_count = 0;
1268     dict->_deletes = 0;
1269     if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (512 < dict->_capacity)) {
1270         __CFDictionaryGrow(dict, 256);
1271     }
1272 }
1273
1274 void _CFDictionaryIncrementValue(CFMutableDictionaryRef dict, const void *key) {
1275     CFIndex match, nomatch;
1276
1277     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1278     CFAssert1(__CFDictionaryGetType(dict) == __kCFDictionaryMutable, __kCFLogAssertion, "%s(): invalid dict type passed to increment operation", __PRETTY_FUNCTION__);
1279     CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
1280     CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 5, 4), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
1281
1282     match = kCFNotFound;
1283     if (NULL != dict->_keys) {
1284         __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
1285     }
1286     if (kCFNotFound != match) {
1287         if (dict->_values[match] != (void *)UINT_MAX) {
1288             dict->_values[match] = (void *)((uintptr_t)dict->_values[match] + 1);
1289         }
1290     } else {
1291         if (dict->_marker == (uintptr_t)key || ~dict->_marker == (uintptr_t)key) {
1292             __CFDictionaryFindNewMarker(dict);
1293         }
1294         if (dict->_count == dict->_capacity || NULL == dict->_keys) {
1295             __CFDictionaryGrow(dict, 1);
1296             __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
1297         }
1298         dict->_keys[nomatch] = key;
1299         dict->_values[nomatch] = (void *)1;
1300         dict->_count++;
1301     }
1302 }
1303
1304 int _CFDictionaryDecrementValue(CFMutableDictionaryRef dict, const void *key) {
1305     CFIndex match;
1306
1307     __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1308     CFAssert1(__CFDictionaryGetType(dict) == __kCFDictionaryMutable, __kCFLogAssertion, "%s(): invalid dict type passed to increment operation", __PRETTY_FUNCTION__);
1309     CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
1310     CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 5, 4), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
1311
1312     if (0 == dict->_count) return -1;
1313     match = __CFDictionaryFindBuckets1a(dict, key);
1314     if (kCFNotFound == match) return -1;
1315     if (1 == (uintptr_t)dict->_values[match]) {
1316         dict->_count--;
1317         dict->_values[match] = 0;
1318         dict->_keys[match] = (const void *)~dict->_marker;
1319         dict->_deletes++;
1320         if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (dict->_bucketsNum < 4 * dict->_deletes || (512 < dict->_capacity && 3.236067 * dict->_count < dict->_capacity))) {
1321             __CFDictionaryGrow(dict, 0);
1322         } else {
1323             if (match < dict->_bucketsNum - 1 && dict->_keys[match + 1] == (const void *)dict->_marker) {
1324                 while (0 <= match && dict->_keys[match] == (const void *)~dict->_marker) {
1325                     dict->_keys[match] = (const void *)dict->_marker;
1326                     dict->_deletes--;
1327                     match--;
1328                 }
1329             }
1330         }
1331         return 0;
1332     } else if (dict->_values[match] != (void *)UINT_MAX) {
1333         dict->_values[match] = (void *)((uintptr_t)dict->_values[match] - 1);
1334     }
1335     return 1;
1336 }
1337