Collections.subproj/CFDictionary.c

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