CFBasicHash.c

   1 /*
   2  * Copyright (c) 2014 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 /*      CFBasicHash.m
  25         Copyright (c) 2008-2013, Apple Inc. All rights reserved.
  26         Responsibility: Christopher Kane
  27 */
  28
  29 #import "CFBasicHash.h"
  30 #import <CoreFoundation/CFRuntime.h>
  31 #import <CoreFoundation/CFSet.h>
  32 #import <Block.h>
  33 #import <math.h>
  34 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED
  35 #import <dispatch/dispatch.h>
  36 #endif
  37
  38 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED
  39 #define __SetLastAllocationEventName(A, B) do { if (__CFOASafe && (A)) __CFSetLastAllocationEventName(A, B); } while (0)
  40 #else
  41 #define __SetLastAllocationEventName(A, B) do { } while (0)
  42 #endif
  43
  44 #define __AssignWithWriteBarrier(location, value) objc_assign_strongCast((id)value, (id *)location)
  45
  46 #define ENABLE_DTRACE_PROBES 0
  47 #define ENABLE_MEMORY_COUNTERS 0
  48
  49 #if defined(DTRACE_PROBES_DISABLED) && DTRACE_PROBES_DISABLED
  50 #undef ENABLE_DTRACE_PROBES
  51 #define ENABLE_DTRACE_PROBES 0
  52 #endif
  53
  54 /*
  55 // dtrace -h -s foo.d
  56 // Note: output then changed by casts of the arguments
  57 // dtrace macros last generated 2010-09-08 on 10.7 prerelease (11A259)
  58
  59 provider Cocoa_HashTable {
  60         probe hash_key(unsigned long table, unsigned long key, unsigned long hash);
  61         probe test_equal(unsigned long table, unsigned long key1, unsigned long key2);
  62         probe probing_start(unsigned long table, unsigned long num_buckets);
  63         probe probe_empty(unsigned long table, unsigned long idx);
  64         probe probe_deleted(unsigned long table, unsigned long idx);
  65         probe probe_valid(unsigned long table, unsigned long idx);
  66         probe probing_end(unsigned long table, unsigned long num_probes);
  67         probe rehash_start(unsigned long table, unsigned long num_buckets, unsigned long total_size);
  68         probe rehash_end(unsigned long table, unsigned long num_buckets, unsigned long total_size);
  69 };
  70
  71 #pragma D attributes Unstable/Unstable/Common provider Cocoa_HashTable provider
  72 #pragma D attributes Private/Private/Unknown provider Cocoa_HashTable module
  73 #pragma D attributes Private/Private/Unknown provider Cocoa_HashTable function
  74 #pragma D attributes Unstable/Unstable/Common provider Cocoa_HashTable name
  75 #pragma D attributes Unstable/Unstable/Common provider Cocoa_HashTable args
  76 */
  77
  78 #if ENABLE_DTRACE_PROBES
  79
  80 #define COCOA_HASHTABLE_STABILITY "___dtrace_stability$Cocoa_HashTable$v1$4_4_5_1_1_0_1_1_0_4_4_5_4_4_5"
  81
  82 #define COCOA_HASHTABLE_TYPEDEFS "___dtrace_typedefs$Cocoa_HashTable$v2"
  83
  84 #define COCOA_HASHTABLE_REHASH_END(arg0, arg1, arg2) \
  85 do { \
  86         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
  87         __dtrace_probe$Cocoa_HashTable$rehash_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \
  88         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
  89 } while (0)
  90 #define COCOA_HASHTABLE_REHASH_END_ENABLED() \
  91         ({ int _r = __dtrace_isenabled$Cocoa_HashTable$rehash_end$v1(); \
  92                 __asm__ volatile(""); \
  93                 _r; })
  94 #define COCOA_HASHTABLE_REHASH_START(arg0, arg1, arg2) \
  95 do { \
  96         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
  97         __dtrace_probe$Cocoa_HashTable$rehash_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \
  98         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
  99 } while (0)
 100 #define COCOA_HASHTABLE_REHASH_START_ENABLED() \
 101         ({ int _r = __dtrace_isenabled$Cocoa_HashTable$rehash_start$v1(); \
 102                 __asm__ volatile(""); \
 103                 _r; })
 104 #define COCOA_HASHTABLE_HASH_KEY(arg0, arg1, arg2) \
 105 do { \
 106         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 107         __dtrace_probe$Cocoa_HashTable$hash_key$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \
 108         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 109 } while (0)
 110 #define COCOA_HASHTABLE_HASH_KEY_ENABLED() \
 111         ({ int _r = __dtrace_isenabled$Cocoa_HashTable$hash_key$v1(); \
 112                 __asm__ volatile(""); \
 113                 _r; })
 114 #define COCOA_HASHTABLE_PROBE_DELETED(arg0, arg1) \
 115 do { \
 116         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 117         __dtrace_probe$Cocoa_HashTable$probe_deleted$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 118         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 119 } while (0)
 120 #define COCOA_HASHTABLE_PROBE_DELETED_ENABLED() \
 121         ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probe_deleted$v1(); \
 122                 __asm__ volatile(""); \
 123                 _r; })
 124 #define COCOA_HASHTABLE_PROBE_EMPTY(arg0, arg1) \
 125 do { \
 126         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 127         __dtrace_probe$Cocoa_HashTable$probe_empty$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 128         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 129 } while (0)
 130 #define COCOA_HASHTABLE_PROBE_EMPTY_ENABLED() \
 131         ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probe_empty$v1(); \
 132                 __asm__ volatile(""); \
 133                 _r; })
 134 #define COCOA_HASHTABLE_PROBE_VALID(arg0, arg1) \
 135 do { \
 136         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 137         __dtrace_probe$Cocoa_HashTable$probe_valid$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 138         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 139 } while (0)
 140 #define COCOA_HASHTABLE_PROBE_VALID_ENABLED() \
 141         ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probe_valid$v1(); \
 142                 __asm__ volatile(""); \
 143                 _r; })
 144 #define COCOA_HASHTABLE_PROBING_END(arg0, arg1) \
 145 do { \
 146         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 147         __dtrace_probe$Cocoa_HashTable$probing_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 148         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 149 } while (0)
 150 #define COCOA_HASHTABLE_PROBING_END_ENABLED() \
 151         ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probing_end$v1(); \
 152                 __asm__ volatile(""); \
 153                 _r; })
 154 #define COCOA_HASHTABLE_PROBING_START(arg0, arg1) \
 155 do { \
 156         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 157         __dtrace_probe$Cocoa_HashTable$probing_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \
 158         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 159 } while (0)
 160 #define COCOA_HASHTABLE_PROBING_START_ENABLED() \
 161         ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probing_start$v1(); \
 162                 __asm__ volatile(""); \
 163                 _r; })
 164 #define COCOA_HASHTABLE_TEST_EQUAL(arg0, arg1, arg2) \
 165 do { \
 166         __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \
 167         __dtrace_probe$Cocoa_HashTable$test_equal$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \
 168         __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \
 169 } while (0)
 170 #define COCOA_HASHTABLE_TEST_EQUAL_ENABLED() \
 171         ({ int _r = __dtrace_isenabled$Cocoa_HashTable$test_equal$v1(); \
 172                 __asm__ volatile(""); \
 173                 _r; })
 174
 175 extern void __dtrace_probe$Cocoa_HashTable$hash_key$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long);
 176 extern int __dtrace_isenabled$Cocoa_HashTable$hash_key$v1(void);
 177 extern void __dtrace_probe$Cocoa_HashTable$probe_deleted$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 178 extern int __dtrace_isenabled$Cocoa_HashTable$probe_deleted$v1(void);
 179 extern void __dtrace_probe$Cocoa_HashTable$probe_empty$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 180 extern int __dtrace_isenabled$Cocoa_HashTable$probe_empty$v1(void);
 181 extern void __dtrace_probe$Cocoa_HashTable$probe_valid$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 182 extern int __dtrace_isenabled$Cocoa_HashTable$probe_valid$v1(void);
 183 extern void __dtrace_probe$Cocoa_HashTable$probing_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 184 extern int __dtrace_isenabled$Cocoa_HashTable$probing_end$v1(void);
 185 extern void __dtrace_probe$Cocoa_HashTable$probing_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long);
 186 extern int __dtrace_isenabled$Cocoa_HashTable$probing_start$v1(void);
 187 extern void __dtrace_probe$Cocoa_HashTable$rehash_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long);
 188 extern int __dtrace_isenabled$Cocoa_HashTable$rehash_end$v1(void);
 189 extern void __dtrace_probe$Cocoa_HashTable$rehash_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long);
 190 extern int __dtrace_isenabled$Cocoa_HashTable$rehash_start$v1(void);
 191 extern void __dtrace_probe$Cocoa_HashTable$test_equal$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long);
 192 extern int __dtrace_isenabled$Cocoa_HashTable$test_equal$v1(void);
 193
 194 #else
 195
 196 #define COCOA_HASHTABLE_REHASH_END(arg0, arg1, arg2) do {} while (0)
 197 #define COCOA_HASHTABLE_REHASH_END_ENABLED() 0
 198 #define COCOA_HASHTABLE_REHASH_START(arg0, arg1, arg2) do {} while (0)
 199 #define COCOA_HASHTABLE_REHASH_START_ENABLED() 0
 200 #define COCOA_HASHTABLE_HASH_KEY(arg0, arg1, arg2) do {} while (0)
 201 #define COCOA_HASHTABLE_HASH_KEY_ENABLED() 0
 202 #define COCOA_HASHTABLE_PROBE_DELETED(arg0, arg1) do {} while (0)
 203 #define COCOA_HASHTABLE_PROBE_DELETED_ENABLED() 0
 204 #define COCOA_HASHTABLE_PROBE_EMPTY(arg0, arg1) do {} while (0)
 205 #define COCOA_HASHTABLE_PROBE_EMPTY_ENABLED() 0
 206 #define COCOA_HASHTABLE_PROBE_VALID(arg0, arg1) do {} while (0)
 207 #define COCOA_HASHTABLE_PROBE_VALID_ENABLED() 0
 208 #define COCOA_HASHTABLE_PROBING_END(arg0, arg1) do {} while (0)
 209 #define COCOA_HASHTABLE_PROBING_END_ENABLED() 0
 210 #define COCOA_HASHTABLE_PROBING_START(arg0, arg1) do {} while (0)
 211 #define COCOA_HASHTABLE_PROBING_START_ENABLED() 0
 212 #define COCOA_HASHTABLE_TEST_EQUAL(arg0, arg1, arg2) do {} while (0)
 213 #define COCOA_HASHTABLE_TEST_EQUAL_ENABLED() 0
 214
 215 #endif
 216
 217
 218 #if !defined(__LP64__)
 219 #define __LP64__ 0
 220 #endif
 221
 222 // Prime numbers. Values above 100 have been adjusted up so that the
 223 // malloced block size will be just below a multiple of 512; values
 224 // above 1200 have been adjusted up to just below a multiple of 4096.
 225 static const uintptr_t __CFBasicHashTableSizes[64] = {
 226     0, 3, 7, 13, 23, 41, 71, 127, 191, 251, 383, 631, 1087, 1723,
 227     2803, 4523, 7351, 11959, 19447, 31231, 50683, 81919, 132607,
 228     214519, 346607, 561109, 907759, 1468927, 2376191, 3845119,
 229     6221311, 10066421, 16287743, 26354171, 42641881, 68996069,
 230     111638519, 180634607, 292272623, 472907251,
 231 #if __LP64__
 232     765180413UL, 1238087663UL, 2003267557UL, 3241355263UL, 5244622819UL,
 233 #if 0
 234     8485977589UL, 13730600407UL, 22216578047UL, 35947178479UL,
 235     58163756537UL, 94110934997UL, 152274691561UL, 246385626107UL,
 236     398660317687UL, 645045943807UL, 1043706260983UL, 1688752204787UL,
 237     2732458465769UL, 4421210670577UL, 7153669136377UL,
 238     11574879807461UL, 18728548943849UL, 30303428750843UL
 239 #endif
 240 #endif
 241 };
 242
 243 static const uintptr_t __CFBasicHashTableCapacities[64] = {
 244     0, 3, 6, 11, 19, 32, 52, 85, 118, 155, 237, 390, 672, 1065,
 245     1732, 2795, 4543, 7391, 12019, 19302, 31324, 50629, 81956,
 246     132580, 214215, 346784, 561026, 907847, 1468567, 2376414,
 247     3844982, 6221390, 10066379, 16287773, 26354132, 42641916,
 248     68996399, 111638327, 180634415, 292272755,
 249 #if __LP64__
 250     472907503UL, 765180257UL, 1238087439UL, 2003267722UL, 3241355160UL,
 251 #if 0
 252     5244622578UL, 8485977737UL, 13730600347UL, 22216578100UL,
 253     35947178453UL, 58163756541UL, 94110935011UL, 152274691274UL,
 254     246385626296UL, 398660317578UL, 645045943559UL, 1043706261135UL,
 255     1688752204693UL, 2732458465840UL, 4421210670552UL,
 256     7153669136706UL, 11574879807265UL, 18728548943682UL
 257 #endif
 258 #endif
 259 };
 260
 261 // Primitive roots for the primes above
 262 static const uintptr_t __CFBasicHashPrimitiveRoots[64] = {
 263     0, 2, 3, 2, 5, 6, 7, 3, 19, 6, 5, 3, 3, 3,
 264     2, 5, 6, 3, 3, 6, 2, 3, 3,
 265     3, 5, 10, 3, 3, 22, 3,
 266     3, 3, 5, 2, 22, 2,
 267     11, 5, 5, 2,
 268 #if __LP64__
 269     3, 10, 2, 3, 10,
 270     2, 3, 5, 3,
 271     3, 2, 7, 2,
 272     3, 3, 3, 2,
 273     3, 5, 5,
 274     2, 3, 2
 275 #endif
 276 };
 277
 278 CF_INLINE void *__CFBasicHashAllocateMemory(CFConstBasicHashRef ht, CFIndex count, CFIndex elem_size, Boolean strong, Boolean compactable) {
 279     CFAllocatorRef allocator = CFGetAllocator(ht);
 280     void *new_mem = NULL;
 281     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 282         new_mem = auto_zone_allocate_object(objc_collectableZone(), count * elem_size, strong ? (compactable ? AUTO_POINTERS_ONLY : AUTO_MEMORY_SCANNED) : AUTO_UNSCANNED, false, false);
 283     } else {
 284         new_mem = CFAllocatorAllocate(allocator, count * elem_size, 0);
 285     }
 286     return new_mem;
 287 }
 288
 289 CF_INLINE void *__CFBasicHashAllocateMemory2(CFAllocatorRef allocator, CFIndex count, CFIndex elem_size, Boolean strong, Boolean compactable) {
 290     void *new_mem = NULL;
 291     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 292         new_mem = auto_zone_allocate_object(objc_collectableZone(), count * elem_size, strong ? (compactable ? AUTO_POINTERS_ONLY : AUTO_MEMORY_SCANNED) : AUTO_UNSCANNED, false, false);
 293     } else {
 294         new_mem = CFAllocatorAllocate(allocator, count * elem_size, 0);
 295     }
 296     return new_mem;
 297 }
 298
 299 #define __CFBasicHashSubABZero 0xa7baadb1
 300 #define __CFBasicHashSubABOne 0xa5baadb9
 301
 302 typedef union {
 303     uintptr_t neutral;
 304     id strong;
 305     id weak;
 306 } CFBasicHashValue;
 307
 308 struct __CFBasicHash {
 309     CFRuntimeBase base;
 310     struct { // 192 bits
 311         uint16_t mutations;
 312         uint8_t hash_style:2;
 313         uint8_t keys_offset:1;
 314         uint8_t counts_offset:2;
 315         uint8_t counts_width:2;
 316         uint8_t hashes_offset:2;
 317         uint8_t strong_values:1;
 318         uint8_t strong_keys:1;
 319         uint8_t weak_values:1;
 320         uint8_t weak_keys:1;
 321         uint8_t int_values:1;
 322         uint8_t int_keys:1;
 323         uint8_t indirect_keys:1;
 324         uint32_t used_buckets;      /* number of used buckets */
 325         uint64_t deleted:16;
 326         uint64_t num_buckets_idx:8; /* index to number of buckets */
 327         uint64_t __kret:10;
 328         uint64_t __vret:10;
 329         uint64_t __krel:10;
 330         uint64_t __vrel:10;
 331         uint64_t __:1;
 332         uint64_t null_rc:1;
 333         uint64_t fast_grow:1;
 334         uint64_t finalized:1;
 335         uint64_t __kdes:10;
 336         uint64_t __vdes:10;
 337         uint64_t __kequ:10;
 338         uint64_t __vequ:10;
 339         uint64_t __khas:10;
 340         uint64_t __kget:10;
 341     } bits;
 342     void *pointers[1];
 343 };
 344
 345 static void *CFBasicHashCallBackPtrs[(1UL << 10)];
 346 static int32_t CFBasicHashCallBackPtrsCount = 0;
 347
 348 static int32_t CFBasicHashGetPtrIndex(void *ptr) {
 349     static dispatch_once_t once;
 350     dispatch_once(&once, ^{
 351         CFBasicHashCallBackPtrs[0] = NULL;
 352         CFBasicHashCallBackPtrs[1] = (void *)CFCopyDescription;
 353         CFBasicHashCallBackPtrs[2] = (void *)__CFTypeCollectionRelease;
 354         CFBasicHashCallBackPtrs[3] = (void *)__CFTypeCollectionRetain;
 355         CFBasicHashCallBackPtrs[4] = (void *)CFEqual;
 356         CFBasicHashCallBackPtrs[5] = (void *)CFHash;
 357         CFBasicHashCallBackPtrs[6] = (void *)__CFStringCollectionCopy;
 358         CFBasicHashCallBackPtrs[7] = NULL;
 359         CFBasicHashCallBackPtrsCount = 8;
 360     });
 361
 362     // The uniquing here is done locklessly for best performance, and in
 363     // a way that will keep multiple threads from stomping each other's
 364     // newly registered values, but may result in multiple slots
 365     // containing the same pointer value.
 366
 367     int32_t idx;
 368     for (idx = 0; idx < CFBasicHashCallBackPtrsCount; idx++) {
 369         if (CFBasicHashCallBackPtrs[idx] == ptr) return idx;
 370     }
 371
 372     if (1000 < CFBasicHashCallBackPtrsCount) HALT;
 373     idx = OSAtomicIncrement32(&CFBasicHashCallBackPtrsCount); // returns new value
 374     CFBasicHashCallBackPtrs[idx - 1] = ptr;
 375     return idx - 1;
 376 }
 377
 378 CF_PRIVATE Boolean CFBasicHashHasStrongValues(CFConstBasicHashRef ht) {
 379 #if DEPLOYMENT_TARGET_MACOSX
 380     return ht->bits.strong_values ? true : false;
 381 #else
 382     return false;
 383 #endif
 384 }
 385
 386 CF_PRIVATE Boolean CFBasicHashHasStrongKeys(CFConstBasicHashRef ht) {
 387 #if DEPLOYMENT_TARGET_MACOSX
 388     return ht->bits.strong_keys ? true : false;
 389 #else
 390     return false;
 391 #endif
 392 }
 393
 394 CF_INLINE Boolean __CFBasicHashHasWeakValues(CFConstBasicHashRef ht) {
 395 #if DEPLOYMENT_TARGET_MACOSX
 396     return ht->bits.weak_values ? true : false;
 397 #else
 398     return false;
 399 #endif
 400 }
 401
 402 CF_INLINE Boolean __CFBasicHashHasWeakKeys(CFConstBasicHashRef ht) {
 403 #if DEPLOYMENT_TARGET_MACOSX
 404     return ht->bits.weak_keys ? true : false;
 405 #else
 406     return false;
 407 #endif
 408 }
 409
 410 CF_INLINE Boolean __CFBasicHashHasHashCache(CFConstBasicHashRef ht) {
 411 #if DEPLOYMENT_TARGET_MACOSX
 412     return ht->bits.hashes_offset ? true : false;
 413 #else
 414     return false;
 415 #endif
 416 }
 417
 418 CF_INLINE uintptr_t __CFBasicHashImportValue(CFConstBasicHashRef ht, uintptr_t stack_value) {
 419     uintptr_t (*func)(CFAllocatorRef, uintptr_t) = (uintptr_t (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vret];
 420     if (!func || ht->bits.null_rc) return stack_value;
 421     CFAllocatorRef alloc = CFGetAllocator(ht);
 422     return func(alloc, stack_value);
 423 }
 424
 425 CF_INLINE uintptr_t __CFBasicHashImportKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 426     uintptr_t (*func)(CFAllocatorRef, uintptr_t) = (uintptr_t (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kret];
 427     if (!func || ht->bits.null_rc) return stack_key;
 428     CFAllocatorRef alloc = CFGetAllocator(ht);
 429     return func(alloc, stack_key);
 430 }
 431
 432 CF_INLINE void __CFBasicHashEjectValue(CFConstBasicHashRef ht, uintptr_t stack_value) {
 433     void (*func)(CFAllocatorRef, uintptr_t) = (void (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vrel];
 434     if (!func || ht->bits.null_rc) return;
 435     CFAllocatorRef alloc = CFGetAllocator(ht);
 436     func(alloc, stack_value);
 437 }
 438
 439 CF_INLINE void __CFBasicHashEjectKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 440     void (*func)(CFAllocatorRef, uintptr_t) = (void (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__krel];
 441     if (!func || ht->bits.null_rc) return;
 442     CFAllocatorRef alloc = CFGetAllocator(ht);
 443     func(alloc, stack_key);
 444 }
 445
 446 CF_INLINE CFStringRef __CFBasicHashDescValue(CFConstBasicHashRef ht, uintptr_t stack_value) {
 447     CFStringRef (*func)(uintptr_t) = (CFStringRef (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vdes];
 448     if (!func) return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)stack_value);
 449     return func(stack_value);
 450 }
 451
 452 CF_INLINE CFStringRef __CFBasicHashDescKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 453     CFStringRef (*func)(uintptr_t) = (CFStringRef (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kdes];
 454     if (!func) return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)stack_key);
 455     return func(stack_key);
 456 }
 457
 458 CF_INLINE Boolean __CFBasicHashTestEqualValue(CFConstBasicHashRef ht, uintptr_t stack_value_a, uintptr_t stack_value_b) {
 459     Boolean (*func)(uintptr_t, uintptr_t) = (Boolean (*)(uintptr_t, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vequ];
 460     if (!func) return (stack_value_a == stack_value_b);
 461     return func(stack_value_a, stack_value_b);
 462 }
 463
 464 CF_INLINE Boolean __CFBasicHashTestEqualKey(CFConstBasicHashRef ht, uintptr_t in_coll_key, uintptr_t stack_key) {
 465     COCOA_HASHTABLE_TEST_EQUAL(ht, in_coll_key, stack_key);
 466     Boolean (*func)(uintptr_t, uintptr_t) = (Boolean (*)(uintptr_t, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kequ];
 467     if (!func) return (in_coll_key == stack_key);
 468     return func(in_coll_key, stack_key);
 469 }
 470
 471 CF_INLINE CFHashCode __CFBasicHashHashKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 472     CFHashCode (*func)(uintptr_t) = (CFHashCode (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__khas];
 473     CFHashCode hash_code = func ? func(stack_key) : stack_key;
 474     COCOA_HASHTABLE_HASH_KEY(ht, stack_key, hash_code);
 475     return hash_code;
 476 }
 477
 478 CF_INLINE uintptr_t __CFBasicHashGetIndirectKey(CFConstBasicHashRef ht, uintptr_t coll_key) {
 479     uintptr_t (*func)(uintptr_t) = (uintptr_t (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kget];
 480     if (!func) return coll_key;
 481     return func(coll_key);
 482 }
 483
 484 CF_INLINE CFBasicHashValue *__CFBasicHashGetValues(CFConstBasicHashRef ht) {
 485     return (CFBasicHashValue *)ht->pointers[0];
 486 }
 487
 488 CF_INLINE void __CFBasicHashSetValues(CFBasicHashRef ht, CFBasicHashValue *ptr) {
 489     __AssignWithWriteBarrier(&ht->pointers[0], ptr);
 490 }
 491
 492 CF_INLINE CFBasicHashValue *__CFBasicHashGetKeys(CFConstBasicHashRef ht) {
 493     return (CFBasicHashValue *)ht->pointers[ht->bits.keys_offset];
 494 }
 495
 496 CF_INLINE void __CFBasicHashSetKeys(CFBasicHashRef ht, CFBasicHashValue *ptr) {
 497     __AssignWithWriteBarrier(&ht->pointers[ht->bits.keys_offset], ptr);
 498 }
 499
 500 CF_INLINE void *__CFBasicHashGetCounts(CFConstBasicHashRef ht) {
 501     return (void *)ht->pointers[ht->bits.counts_offset];
 502 }
 503
 504 CF_INLINE void __CFBasicHashSetCounts(CFBasicHashRef ht, void *ptr) {
 505     __AssignWithWriteBarrier(&ht->pointers[ht->bits.counts_offset], ptr);
 506 }
 507
 508 CF_INLINE uintptr_t __CFBasicHashGetValue(CFConstBasicHashRef ht, CFIndex idx) {
 509     uintptr_t val = __CFBasicHashGetValues(ht)[idx].neutral;
 510     if (__CFBasicHashSubABZero == val) return 0UL;
 511     if (__CFBasicHashSubABOne == val) return ~0UL;
 512     return val;
 513 }
 514
 515 CF_INLINE void __CFBasicHashSetValue(CFBasicHashRef ht, CFIndex idx, uintptr_t stack_value, Boolean ignoreOld, Boolean literal) {
 516     CFBasicHashValue *valuep = &(__CFBasicHashGetValues(ht)[idx]);
 517     uintptr_t old_value = ignoreOld ? 0 : valuep->neutral;
 518     if (!literal) {
 519         if (0UL == stack_value) stack_value = __CFBasicHashSubABZero;
 520         if (~0UL == stack_value) stack_value = __CFBasicHashSubABOne;
 521     }
 522     if (CFBasicHashHasStrongValues(ht)) valuep->strong = (id)stack_value; else valuep->neutral = stack_value;
 523     if (!ignoreOld) {
 524         if (!(old_value == 0UL || old_value == ~0UL)) {
 525             if (__CFBasicHashSubABZero == old_value) old_value = 0UL;
 526             if (__CFBasicHashSubABOne == old_value) old_value = ~0UL;
 527             __CFBasicHashEjectValue(ht, old_value);
 528         }
 529     }
 530 }
 531
 532 CF_INLINE uintptr_t __CFBasicHashGetKey(CFConstBasicHashRef ht, CFIndex idx) {
 533     if (ht->bits.keys_offset) {
 534         uintptr_t key = __CFBasicHashGetKeys(ht)[idx].neutral;
 535         if (__CFBasicHashSubABZero == key) return 0UL;
 536         if (__CFBasicHashSubABOne == key) return ~0UL;
 537         return key;
 538     }
 539     if (ht->bits.indirect_keys) {
 540         uintptr_t stack_value = __CFBasicHashGetValue(ht, idx);
 541         return __CFBasicHashGetIndirectKey(ht, stack_value);
 542     }
 543     return __CFBasicHashGetValue(ht, idx);
 544 }
 545
 546 CF_INLINE void __CFBasicHashSetKey(CFBasicHashRef ht, CFIndex idx, uintptr_t stack_key, Boolean ignoreOld, Boolean literal) {
 547     if (0 == ht->bits.keys_offset) HALT;
 548     CFBasicHashValue *keyp = &(__CFBasicHashGetKeys(ht)[idx]);
 549     uintptr_t old_key = ignoreOld ? 0 : keyp->neutral;
 550     if (!literal) {
 551         if (0UL == stack_key) stack_key = __CFBasicHashSubABZero;
 552         if (~0UL == stack_key) stack_key = __CFBasicHashSubABOne;
 553     }
 554     if (CFBasicHashHasStrongKeys(ht)) keyp->strong = (id)stack_key; else keyp->neutral = stack_key;
 555     if (!ignoreOld) {
 556         if (!(old_key == 0UL || old_key == ~0UL)) {
 557             if (__CFBasicHashSubABZero == old_key) old_key = 0UL;
 558             if (__CFBasicHashSubABOne == old_key) old_key = ~0UL;
 559             __CFBasicHashEjectKey(ht, old_key);
 560         }
 561     }
 562 }
 563
 564 CF_INLINE uintptr_t __CFBasicHashIsEmptyOrDeleted(CFConstBasicHashRef ht, CFIndex idx) {
 565     uintptr_t stack_value = __CFBasicHashGetValues(ht)[idx].neutral;
 566     return (0UL == stack_value || ~0UL == stack_value);
 567 }
 568
 569 CF_INLINE uintptr_t __CFBasicHashIsDeleted(CFConstBasicHashRef ht, CFIndex idx) {
 570     uintptr_t stack_value = __CFBasicHashGetValues(ht)[idx].neutral;
 571     return (~0UL == stack_value);
 572 }
 573
 574 CF_INLINE uintptr_t __CFBasicHashGetSlotCount(CFConstBasicHashRef ht, CFIndex idx) {
 575     void *counts = __CFBasicHashGetCounts(ht);
 576     switch (ht->bits.counts_width) {
 577     case 0: return ((uint8_t *)counts)[idx];
 578     case 1: return ((uint16_t *)counts)[idx];
 579     case 2: return ((uint32_t *)counts)[idx];
 580     case 3: return ((uint64_t *)counts)[idx];
 581     }
 582     return 0;
 583 }
 584
 585 CF_INLINE void __CFBasicHashBumpCounts(CFBasicHashRef ht) {
 586     void *counts = __CFBasicHashGetCounts(ht);
 587     CFAllocatorRef allocator = CFGetAllocator(ht);
 588     switch (ht->bits.counts_width) {
 589     case 0: {
 590         uint8_t *counts08 = (uint8_t *)counts;
 591         ht->bits.counts_width = 1;
 592         CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 593         uint16_t *counts16 = (uint16_t *)__CFBasicHashAllocateMemory(ht, num_buckets, 2, false, false);
 594         if (!counts16) HALT;
 595         __SetLastAllocationEventName(counts16, "CFBasicHash (count-store)");
 596         for (CFIndex idx2 = 0; idx2 < num_buckets; idx2++) {
 597             counts16[idx2] = counts08[idx2];
 598         }
 599         __CFBasicHashSetCounts(ht, counts16);
 600         if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 601             CFAllocatorDeallocate(allocator, counts08);
 602         }
 603         break;
 604     }
 605     case 1: {
 606         uint16_t *counts16 = (uint16_t *)counts;
 607         ht->bits.counts_width = 2;
 608         CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 609         uint32_t *counts32 = (uint32_t *)__CFBasicHashAllocateMemory(ht, num_buckets, 4, false, false);
 610         if (!counts32) HALT;
 611         __SetLastAllocationEventName(counts32, "CFBasicHash (count-store)");
 612         for (CFIndex idx2 = 0; idx2 < num_buckets; idx2++) {
 613             counts32[idx2] = counts16[idx2];
 614         }
 615         __CFBasicHashSetCounts(ht, counts32);
 616          if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 617             CFAllocatorDeallocate(allocator, counts16);
 618         }
 619         break;
 620     }
 621     case 2: {
 622         uint32_t *counts32 = (uint32_t *)counts;
 623         ht->bits.counts_width = 3;
 624         CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 625         uint64_t *counts64 = (uint64_t *)__CFBasicHashAllocateMemory(ht, num_buckets, 8, false, false);
 626         if (!counts64) HALT;
 627         __SetLastAllocationEventName(counts64, "CFBasicHash (count-store)");
 628         for (CFIndex idx2 = 0; idx2 < num_buckets; idx2++) {
 629             counts64[idx2] = counts32[idx2];
 630         }
 631         __CFBasicHashSetCounts(ht, counts64);
 632          if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 633             CFAllocatorDeallocate(allocator, counts32);
 634         }
 635         break;
 636     }
 637     case 3: {
 638         HALT;
 639         break;
 640     }
 641     }
 642 }
 643
 644 static void __CFBasicHashIncSlotCount(CFBasicHashRef ht, CFIndex idx) {
 645     void *counts = __CFBasicHashGetCounts(ht);
 646     switch (ht->bits.counts_width) {
 647     case 0: {
 648         uint8_t *counts08 = (uint8_t *)counts;
 649         uint8_t val = counts08[idx];
 650         if (val < INT8_MAX) {
 651             counts08[idx] = val + 1;
 652             return;
 653         }
 654         __CFBasicHashBumpCounts(ht);
 655         __CFBasicHashIncSlotCount(ht, idx);
 656         break;
 657     }
 658     case 1: {
 659         uint16_t *counts16 = (uint16_t *)counts;
 660         uint16_t val = counts16[idx];
 661         if (val < INT16_MAX) {
 662             counts16[idx] = val + 1;
 663             return;
 664         }
 665         __CFBasicHashBumpCounts(ht);
 666         __CFBasicHashIncSlotCount(ht, idx);
 667         break;
 668     }
 669     case 2: {
 670         uint32_t *counts32 = (uint32_t *)counts;
 671         uint32_t val = counts32[idx];
 672         if (val < INT32_MAX) {
 673             counts32[idx] = val + 1;
 674             return;
 675         }
 676         __CFBasicHashBumpCounts(ht);
 677         __CFBasicHashIncSlotCount(ht, idx);
 678         break;
 679     }
 680     case 3: {
 681         uint64_t *counts64 = (uint64_t *)counts;
 682         uint64_t val = counts64[idx];
 683         if (val < INT64_MAX) {
 684             counts64[idx] = val + 1;
 685             return;
 686         }
 687         __CFBasicHashBumpCounts(ht);
 688         __CFBasicHashIncSlotCount(ht, idx);
 689         break;
 690     }
 691     }
 692 }
 693
 694 CF_INLINE void __CFBasicHashDecSlotCount(CFBasicHashRef ht, CFIndex idx) {
 695     void *counts = __CFBasicHashGetCounts(ht);
 696     switch (ht->bits.counts_width) {
 697     case 0: ((uint8_t  *)counts)[idx]--; return;
 698     case 1: ((uint16_t *)counts)[idx]--; return;
 699     case 2: ((uint32_t *)counts)[idx]--; return;
 700     case 3: ((uint64_t *)counts)[idx]--; return;
 701     }
 702 }
 703
 704 CF_INLINE uintptr_t *__CFBasicHashGetHashes(CFConstBasicHashRef ht) {
 705     return (uintptr_t *)ht->pointers[ht->bits.hashes_offset];
 706 }
 707
 708 CF_INLINE void __CFBasicHashSetHashes(CFBasicHashRef ht, uintptr_t *ptr) {
 709     __AssignWithWriteBarrier(&ht->pointers[ht->bits.hashes_offset], ptr);
 710 }
 711
 712
 713 // to expose the load factor, expose this function to customization
 714 CF_INLINE CFIndex __CFBasicHashGetCapacityForNumBuckets(CFConstBasicHashRef ht, CFIndex num_buckets_idx) {
 715     return __CFBasicHashTableCapacities[num_buckets_idx];
 716 }
 717
 718 CF_INLINE CFIndex __CFBasicHashGetNumBucketsIndexForCapacity(CFConstBasicHashRef ht, CFIndex capacity) {
 719     for (CFIndex idx = 0; idx < 64; idx++) {
 720         if (capacity <= __CFBasicHashGetCapacityForNumBuckets(ht, idx)) return idx;
 721     }
 722     HALT;
 723     return 0;
 724 }
 725
 726 CF_PRIVATE CFIndex CFBasicHashGetNumBuckets(CFConstBasicHashRef ht) {
 727     return __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 728 }
 729
 730 CF_PRIVATE CFIndex CFBasicHashGetCapacity(CFConstBasicHashRef ht) {
 731     return __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx);
 732 }
 733
 734 // In returned struct, .count is zero if the bucket is empty or deleted,
 735 // and the .weak_key field indicates which. .idx is either the index of
 736 // the found bucket or the index of the bucket which should be filled by
 737 // an add operation. For a set or multiset, the .weak_key and .weak_value
 738 // are the same.
 739 CF_PRIVATE CFBasicHashBucket CFBasicHashGetBucket(CFConstBasicHashRef ht, CFIndex idx) {
 740     CFBasicHashBucket result;
 741     result.idx = idx;
 742     if (__CFBasicHashIsEmptyOrDeleted(ht, idx)) {
 743         result.count = 0;
 744         result.weak_value = 0;
 745         result.weak_key = 0;
 746     } else {
 747         result.count = (ht->bits.counts_offset) ? __CFBasicHashGetSlotCount(ht, idx) : 1;
 748         result.weak_value = __CFBasicHashGetValue(ht, idx);
 749         result.weak_key = __CFBasicHashGetKey(ht, idx);
 750     }
 751     return result;
 752 }
 753
 754 #if defined(__arm__)
 755 static uintptr_t __CFBasicHashFold(uintptr_t dividend, uint8_t idx) {
 756     switch (idx) {
 757     case 1: return dividend % 3;
 758     case 2: return dividend % 7;
 759     case 3: return dividend % 13;
 760     case 4: return dividend % 23;
 761     case 5: return dividend % 41;
 762     case 6: return dividend % 71;
 763     case 7: return dividend % 127;
 764     case 8: return dividend % 191;
 765     case 9: return dividend % 251;
 766     case 10: return dividend % 383;
 767     case 11: return dividend % 631;
 768     case 12: return dividend % 1087;
 769     case 13: return dividend % 1723;
 770     case 14: return dividend % 2803;
 771     case 15: return dividend % 4523;
 772     case 16: return dividend % 7351;
 773     case 17: return dividend % 11959;
 774     case 18: return dividend % 19447;
 775     case 19: return dividend % 31231;
 776     case 20: return dividend % 50683;
 777     case 21: return dividend % 81919;
 778     case 22: return dividend % 132607;
 779     case 23: return dividend % 214519;
 780     case 24: return dividend % 346607;
 781     case 25: return dividend % 561109;
 782     case 26: return dividend % 907759;
 783     case 27: return dividend % 1468927;
 784     case 28: return dividend % 2376191;
 785     case 29: return dividend % 3845119;
 786     case 30: return dividend % 6221311;
 787     case 31: return dividend % 10066421;
 788     case 32: return dividend % 16287743;
 789     case 33: return dividend % 26354171;
 790     case 34: return dividend % 42641881;
 791     case 35: return dividend % 68996069;
 792     case 36: return dividend % 111638519;
 793     case 37: return dividend % 180634607;
 794     case 38: return dividend % 292272623;
 795     case 39: return dividend % 472907251;
 796     }
 797     HALT;
 798     return ~0;
 799 }
 800 #endif
 801
 802
 803 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Linear
 804 #define FIND_BUCKET_HASH_STYLE          1
 805 #define FIND_BUCKET_FOR_REHASH          0
 806 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 807 #include "CFBasicHashFindBucket.m"
 808
 809 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Linear_NoCollision
 810 #define FIND_BUCKET_HASH_STYLE          1
 811 #define FIND_BUCKET_FOR_REHASH          1
 812 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 813 #include "CFBasicHashFindBucket.m"
 814
 815 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Linear_Indirect
 816 #define FIND_BUCKET_HASH_STYLE          1
 817 #define FIND_BUCKET_FOR_REHASH          0
 818 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 819 #include "CFBasicHashFindBucket.m"
 820
 821 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Linear_Indirect_NoCollision
 822 #define FIND_BUCKET_HASH_STYLE          1
 823 #define FIND_BUCKET_FOR_REHASH          1
 824 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 825 #include "CFBasicHashFindBucket.m"
 826
 827 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Double
 828 #define FIND_BUCKET_HASH_STYLE          2
 829 #define FIND_BUCKET_FOR_REHASH          0
 830 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 831 #include "CFBasicHashFindBucket.m"
 832
 833 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Double_NoCollision
 834 #define FIND_BUCKET_HASH_STYLE          2
 835 #define FIND_BUCKET_FOR_REHASH          1
 836 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 837 #include "CFBasicHashFindBucket.m"
 838
 839 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Double_Indirect
 840 #define FIND_BUCKET_HASH_STYLE          2
 841 #define FIND_BUCKET_FOR_REHASH          0
 842 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 843 #include "CFBasicHashFindBucket.m"
 844
 845 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Double_Indirect_NoCollision
 846 #define FIND_BUCKET_HASH_STYLE          2
 847 #define FIND_BUCKET_FOR_REHASH          1
 848 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 849 #include "CFBasicHashFindBucket.m"
 850
 851 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Exponential
 852 #define FIND_BUCKET_HASH_STYLE          3
 853 #define FIND_BUCKET_FOR_REHASH          0
 854 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 855 #include "CFBasicHashFindBucket.m"
 856
 857 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Exponential_NoCollision
 858 #define FIND_BUCKET_HASH_STYLE          3
 859 #define FIND_BUCKET_FOR_REHASH          1
 860 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 861 #include "CFBasicHashFindBucket.m"
 862
 863 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Exponential_Indirect
 864 #define FIND_BUCKET_HASH_STYLE          3
 865 #define FIND_BUCKET_FOR_REHASH          0
 866 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 867 #include "CFBasicHashFindBucket.m"
 868
 869 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Exponential_Indirect_NoCollision
 870 #define FIND_BUCKET_HASH_STYLE          3
 871 #define FIND_BUCKET_FOR_REHASH          1
 872 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 873 #include "CFBasicHashFindBucket.m"
 874
 875
 876 CF_INLINE CFBasicHashBucket __CFBasicHashFindBucket(CFConstBasicHashRef ht, uintptr_t stack_key) {
 877     if (0 == ht->bits.num_buckets_idx) {
 878         CFBasicHashBucket result = {kCFNotFound, 0UL, 0UL, 0};
 879         return result;
 880     }
 881     if (ht->bits.indirect_keys) {
 882         switch (ht->bits.hash_style) {
 883         case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear_Indirect(ht, stack_key);
 884         case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double_Indirect(ht, stack_key);
 885         case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential_Indirect(ht, stack_key);
 886         }
 887     } else {
 888         switch (ht->bits.hash_style) {
 889         case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear(ht, stack_key);
 890         case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double(ht, stack_key);
 891         case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential(ht, stack_key);
 892         }
 893     }
 894     HALT;
 895     CFBasicHashBucket result = {kCFNotFound, 0UL, 0UL, 0};
 896     return result;
 897 }
 898
 899 CF_INLINE CFIndex __CFBasicHashFindBucket_NoCollision(CFConstBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash) {
 900     if (0 == ht->bits.num_buckets_idx) {
 901         return kCFNotFound;
 902     }
 903     if (ht->bits.indirect_keys) {
 904         switch (ht->bits.hash_style) {
 905         case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear_Indirect_NoCollision(ht, stack_key, key_hash);
 906         case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double_Indirect_NoCollision(ht, stack_key, key_hash);
 907         case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential_Indirect_NoCollision(ht, stack_key, key_hash);
 908         }
 909     } else {
 910         switch (ht->bits.hash_style) {
 911         case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear_NoCollision(ht, stack_key, key_hash);
 912         case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double_NoCollision(ht, stack_key, key_hash);
 913         case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential_NoCollision(ht, stack_key, key_hash);
 914         }
 915     }
 916     HALT;
 917     return kCFNotFound;
 918 }
 919
 920 CF_PRIVATE CFBasicHashBucket CFBasicHashFindBucket(CFConstBasicHashRef ht, uintptr_t stack_key) {
 921     if (__CFBasicHashSubABZero == stack_key || __CFBasicHashSubABOne == stack_key) {
 922         CFBasicHashBucket result = {kCFNotFound, 0UL, 0UL, 0};
 923         return result;
 924     }
 925     return __CFBasicHashFindBucket(ht, stack_key);
 926 }
 927
 928 CF_PRIVATE void CFBasicHashSuppressRC(CFBasicHashRef ht) {
 929     ht->bits.null_rc = 1;
 930 }
 931
 932 CF_PRIVATE void CFBasicHashUnsuppressRC(CFBasicHashRef ht) {
 933     ht->bits.null_rc = 0;
 934 }
 935
 936 CF_PRIVATE CFOptionFlags CFBasicHashGetFlags(CFConstBasicHashRef ht) {
 937     CFOptionFlags flags = (ht->bits.hash_style << 13);
 938     if (CFBasicHashHasStrongValues(ht)) flags |= kCFBasicHashStrongValues;
 939     if (CFBasicHashHasStrongKeys(ht)) flags |= kCFBasicHashStrongKeys;
 940     if (ht->bits.fast_grow) flags |= kCFBasicHashAggressiveGrowth;
 941     if (ht->bits.keys_offset) flags |= kCFBasicHashHasKeys;
 942     if (ht->bits.counts_offset) flags |= kCFBasicHashHasCounts;
 943     if (__CFBasicHashHasHashCache(ht)) flags |= kCFBasicHashHasHashCache;
 944     return flags;
 945 }
 946
 947 CF_PRIVATE CFIndex CFBasicHashGetCount(CFConstBasicHashRef ht) {
 948     if (ht->bits.counts_offset) {
 949         CFIndex total = 0L;
 950         CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 951         for (CFIndex idx = 0; idx < cnt; idx++) {
 952             total += __CFBasicHashGetSlotCount(ht, idx);
 953         }
 954         return total;
 955     }
 956     return (CFIndex)ht->bits.used_buckets;
 957 }
 958
 959 CF_PRIVATE CFIndex CFBasicHashGetCountOfKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 960     if (__CFBasicHashSubABZero == stack_key || __CFBasicHashSubABOne == stack_key) {
 961         return 0L;
 962     }
 963     if (0L == ht->bits.used_buckets) {
 964         return 0L;
 965     }
 966     return __CFBasicHashFindBucket(ht, stack_key).count;
 967 }
 968
 969 CF_PRIVATE CFIndex CFBasicHashGetCountOfValue(CFConstBasicHashRef ht, uintptr_t stack_value) {
 970     if (__CFBasicHashSubABZero == stack_value) {
 971         return 0L;
 972     }
 973     if (0L == ht->bits.used_buckets) {
 974         return 0L;
 975     }
 976     if (!(ht->bits.keys_offset)) {
 977         return __CFBasicHashFindBucket(ht, stack_value).count;
 978     }
 979     __block CFIndex total = 0L;
 980     CFBasicHashApply(ht, ^(CFBasicHashBucket bkt) {
 981             if ((stack_value == bkt.weak_value) || __CFBasicHashTestEqualValue(ht, bkt.weak_value, stack_value)) total += bkt.count;
 982             return (Boolean)true;
 983         });
 984     return total;
 985 }
 986
 987 CF_PRIVATE Boolean CFBasicHashesAreEqual(CFConstBasicHashRef ht1, CFConstBasicHashRef ht2) {
 988     CFIndex cnt1 = CFBasicHashGetCount(ht1);
 989     if (cnt1 != CFBasicHashGetCount(ht2)) return false;
 990     if (0 == cnt1) return true;
 991     __block Boolean equal = true;
 992     CFBasicHashApply(ht1, ^(CFBasicHashBucket bkt1) {
 993             CFBasicHashBucket bkt2 = __CFBasicHashFindBucket(ht2, bkt1.weak_key);
 994             if (bkt1.count != bkt2.count) {
 995                 equal = false;
 996                 return (Boolean)false;
 997             }
 998             if ((ht1->bits.keys_offset) && (bkt1.weak_value != bkt2.weak_value) && !__CFBasicHashTestEqualValue(ht1, bkt1.weak_value, bkt2.weak_value)) {
 999                 equal = false;
1000                 return (Boolean)false;
1001             }
1002             return (Boolean)true;
1003         });
1004     return equal;
1005 }
1006
1007 CF_PRIVATE void CFBasicHashApply(CFConstBasicHashRef ht, Boolean (^block)(CFBasicHashBucket)) {
1008     CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1009     for (CFIndex idx = 0; 0 < used && idx < cnt; idx++) {
1010         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
1011         if (0 < bkt.count) {
1012             if (!block(bkt)) {
1013                 return;
1014             }
1015             used--;
1016         }
1017     }
1018 }
1019
1020 CF_PRIVATE void CFBasicHashApplyIndexed(CFConstBasicHashRef ht, CFRange range, Boolean (^block)(CFBasicHashBucket)) {
1021     if (range.length < 0) HALT;
1022     if (range.length == 0) return;
1023     CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1024     if (cnt < range.location + range.length) HALT;
1025     for (CFIndex idx = 0; idx < range.length; idx++) {
1026         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, range.location + idx);
1027         if (0 < bkt.count) {
1028             if (!block(bkt)) {
1029                 return;
1030             }
1031         }
1032     }
1033 }
1034
1035 CF_PRIVATE void CFBasicHashGetElements(CFConstBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_keys) {
1036     CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1037     CFIndex offset = 0;
1038     for (CFIndex idx = 0; 0 < used && idx < cnt && offset < bufferslen; idx++) {
1039         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
1040         if (0 < bkt.count) {
1041             used--;
1042             for (CFIndex cnt = bkt.count; cnt-- && offset < bufferslen;) {
1043                 if (weak_values) { weak_values[offset] = bkt.weak_value; }
1044                 if (weak_keys) { weak_keys[offset] = bkt.weak_key; }
1045                 offset++;
1046             }
1047         }
1048     }
1049 }
1050
1051 CF_PRIVATE unsigned long __CFBasicHashFastEnumeration(CFConstBasicHashRef ht, struct __objcFastEnumerationStateEquivalent2 *state, void *stackbuffer, unsigned long count) {
1052     /* copy as many as count items over */
1053     if (0 == state->state) {        /* first time */
1054         state->mutationsPtr = (unsigned long *)&ht->bits;
1055     }
1056     state->itemsPtr = (unsigned long *)stackbuffer;
1057     CFIndex cntx = 0;
1058     CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1059     for (CFIndex idx = (CFIndex)state->state; 0 < used && idx < cnt && cntx < (CFIndex)count; idx++) {
1060         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
1061         if (0 < bkt.count) {
1062             state->itemsPtr[cntx++] = (unsigned long)bkt.weak_key;
1063             used--;
1064         }
1065         state->state++;
1066     }
1067     return cntx;
1068 }
1069
1070 #if ENABLE_MEMORY_COUNTERS
1071 static volatile int64_t __CFBasicHashTotalCount = 0ULL;
1072 static volatile int64_t __CFBasicHashTotalSize = 0ULL;
1073 static volatile int64_t __CFBasicHashPeakCount = 0ULL;
1074 static volatile int64_t __CFBasicHashPeakSize = 0ULL;
1075 static volatile int32_t __CFBasicHashSizes[64] = {0};
1076 #endif
1077
1078 static void __CFBasicHashDrain(CFBasicHashRef ht, Boolean forFinalization) {
1079 #if ENABLE_MEMORY_COUNTERS
1080     OSAtomicAdd64Barrier(-1 * (int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1081 #endif
1082
1083     CFIndex old_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1084
1085     CFAllocatorRef allocator = CFGetAllocator(ht);
1086     Boolean nullify = (!forFinalization || !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
1087
1088     CFBasicHashValue *old_values = NULL, *old_keys = NULL;
1089     void *old_counts = NULL;
1090     uintptr_t *old_hashes = NULL;
1091
1092     old_values = __CFBasicHashGetValues(ht);
1093     if (nullify) __CFBasicHashSetValues(ht, NULL);
1094     if (ht->bits.keys_offset) {
1095         old_keys = __CFBasicHashGetKeys(ht);
1096         if (nullify) __CFBasicHashSetKeys(ht, NULL);
1097     }
1098     if (ht->bits.counts_offset) {
1099         old_counts = __CFBasicHashGetCounts(ht);
1100         if (nullify) __CFBasicHashSetCounts(ht, NULL);
1101     }
1102     if (__CFBasicHashHasHashCache(ht)) {
1103         old_hashes = __CFBasicHashGetHashes(ht);
1104         if (nullify) __CFBasicHashSetHashes(ht, NULL);
1105     }
1106
1107     if (nullify) {
1108         ht->bits.mutations++;
1109         ht->bits.num_buckets_idx = 0;
1110         ht->bits.used_buckets = 0;
1111         ht->bits.deleted = 0;
1112     }
1113
1114         for (CFIndex idx = 0; idx < old_num_buckets; idx++) {
1115             uintptr_t stack_value = old_values[idx].neutral;
1116             if (stack_value != 0UL && stack_value != ~0UL) {
1117                 uintptr_t old_value = stack_value;
1118                 if (__CFBasicHashSubABZero == old_value) old_value = 0UL;
1119                 if (__CFBasicHashSubABOne == old_value) old_value = ~0UL;
1120                 __CFBasicHashEjectValue(ht, old_value);
1121                 if (old_keys) {
1122                     uintptr_t old_key = old_keys[idx].neutral;
1123                     if (__CFBasicHashSubABZero == old_key) old_key = 0UL;
1124                     if (__CFBasicHashSubABOne == old_key) old_key = ~0UL;
1125                     __CFBasicHashEjectKey(ht, old_key);
1126                 }
1127             }
1128         }
1129
1130     if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
1131         CFAllocatorDeallocate(allocator, old_values);
1132         CFAllocatorDeallocate(allocator, old_keys);
1133         CFAllocatorDeallocate(allocator, old_counts);
1134         CFAllocatorDeallocate(allocator, old_hashes);
1135     }
1136
1137 #if ENABLE_MEMORY_COUNTERS
1138     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1139     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1140 #endif
1141 }
1142
1143 static void __CFBasicHashRehash(CFBasicHashRef ht, CFIndex newItemCount) {
1144 #if ENABLE_MEMORY_COUNTERS
1145     OSAtomicAdd64Barrier(-1 * (int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1146     OSAtomicAdd32Barrier(-1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1147 #endif
1148
1149     if (COCOA_HASHTABLE_REHASH_START_ENABLED()) COCOA_HASHTABLE_REHASH_START(ht, CFBasicHashGetNumBuckets(ht), CFBasicHashGetSize(ht, true));
1150
1151     CFIndex new_num_buckets_idx = ht->bits.num_buckets_idx;
1152     if (0 != newItemCount) {
1153         if (newItemCount < 0) newItemCount = 0;
1154         CFIndex new_capacity_req = ht->bits.used_buckets + newItemCount;
1155         new_num_buckets_idx = __CFBasicHashGetNumBucketsIndexForCapacity(ht, new_capacity_req);
1156         if (1 == newItemCount && ht->bits.fast_grow) {
1157             new_num_buckets_idx++;
1158         }
1159     }
1160
1161     CFIndex new_num_buckets = __CFBasicHashTableSizes[new_num_buckets_idx];
1162     CFIndex old_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1163
1164     CFBasicHashValue *new_values = NULL, *new_keys = NULL;
1165     void *new_counts = NULL;
1166     uintptr_t *new_hashes = NULL;
1167
1168     if (0 < new_num_buckets) {
1169         new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), CFBasicHashHasStrongValues(ht), 0);
1170         if (!new_values) HALT;
1171         __SetLastAllocationEventName(new_values, "CFBasicHash (value-store)");
1172         memset(new_values, 0, new_num_buckets * sizeof(CFBasicHashValue));
1173         if (ht->bits.keys_offset) {
1174             new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), CFBasicHashHasStrongKeys(ht), 0);
1175             if (!new_keys) HALT;
1176             __SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)");
1177             memset(new_keys, 0, new_num_buckets * sizeof(CFBasicHashValue));
1178         }
1179         if (ht->bits.counts_offset) {
1180             new_counts = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, (1 << ht->bits.counts_width), false, false);
1181             if (!new_counts) HALT;
1182             __SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)");
1183             memset(new_counts, 0, new_num_buckets * (1 << ht->bits.counts_width));
1184         }
1185         if (__CFBasicHashHasHashCache(ht)) {
1186             new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false, false);
1187             if (!new_hashes) HALT;
1188             __SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)");
1189             memset(new_hashes, 0, new_num_buckets * sizeof(uintptr_t));
1190         }
1191     }
1192
1193     ht->bits.num_buckets_idx = new_num_buckets_idx;
1194     ht->bits.deleted = 0;
1195
1196     CFBasicHashValue *old_values = NULL, *old_keys = NULL;
1197     void *old_counts = NULL;
1198     uintptr_t *old_hashes = NULL;
1199
1200     old_values = __CFBasicHashGetValues(ht);
1201     __CFBasicHashSetValues(ht, new_values);
1202     if (ht->bits.keys_offset) {
1203         old_keys = __CFBasicHashGetKeys(ht);
1204         __CFBasicHashSetKeys(ht, new_keys);
1205     }
1206     if (ht->bits.counts_offset) {
1207         old_counts = __CFBasicHashGetCounts(ht);
1208         __CFBasicHashSetCounts(ht, new_counts);
1209     }
1210     if (__CFBasicHashHasHashCache(ht)) {
1211         old_hashes = __CFBasicHashGetHashes(ht);
1212         __CFBasicHashSetHashes(ht, new_hashes);
1213     }
1214
1215     if (0 < old_num_buckets) {
1216         for (CFIndex idx = 0; idx < old_num_buckets; idx++) {
1217             uintptr_t stack_value = old_values[idx].neutral;
1218             if (stack_value != 0UL && stack_value != ~0UL) {
1219                 if (__CFBasicHashSubABZero == stack_value) stack_value = 0UL;
1220                 if (__CFBasicHashSubABOne == stack_value) stack_value = ~0UL;
1221                 uintptr_t stack_key = stack_value;
1222                 if (ht->bits.keys_offset) {
1223                     stack_key = old_keys[idx].neutral;
1224                     if (__CFBasicHashSubABZero == stack_key) stack_key = 0UL;
1225                     if (__CFBasicHashSubABOne == stack_key) stack_key = ~0UL;
1226                 }
1227                 if (ht->bits.indirect_keys) {
1228                     stack_key = __CFBasicHashGetIndirectKey(ht, stack_value);
1229                 }
1230                 CFIndex bkt_idx = __CFBasicHashFindBucket_NoCollision(ht, stack_key, old_hashes ? old_hashes[idx] : 0UL);
1231                 __CFBasicHashSetValue(ht, bkt_idx, stack_value, false, false);
1232                 if (old_keys) {
1233                     __CFBasicHashSetKey(ht, bkt_idx, stack_key, false, false);
1234                 }
1235                 if (old_counts) {
1236                     switch (ht->bits.counts_width) {
1237                     case 0: ((uint8_t *)new_counts)[bkt_idx] = ((uint8_t *)old_counts)[idx]; break;
1238                     case 1: ((uint16_t *)new_counts)[bkt_idx] = ((uint16_t *)old_counts)[idx]; break;
1239                     case 2: ((uint32_t *)new_counts)[bkt_idx] = ((uint32_t *)old_counts)[idx]; break;
1240                     case 3: ((uint64_t *)new_counts)[bkt_idx] = ((uint64_t *)old_counts)[idx]; break;
1241                     }
1242                 }
1243                 if (old_hashes) {
1244                     new_hashes[bkt_idx] = old_hashes[idx];
1245                 }
1246             }
1247         }
1248     }
1249
1250     CFAllocatorRef allocator = CFGetAllocator(ht);
1251     if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
1252         CFAllocatorDeallocate(allocator, old_values);
1253         CFAllocatorDeallocate(allocator, old_keys);
1254         CFAllocatorDeallocate(allocator, old_counts);
1255         CFAllocatorDeallocate(allocator, old_hashes);
1256     }
1257
1258     if (COCOA_HASHTABLE_REHASH_END_ENABLED()) COCOA_HASHTABLE_REHASH_END(ht, CFBasicHashGetNumBuckets(ht), CFBasicHashGetSize(ht, true));
1259
1260 #if ENABLE_MEMORY_COUNTERS
1261     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), &__CFBasicHashTotalSize);
1262     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1263     OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1264 #endif
1265 }
1266
1267 CF_PRIVATE void CFBasicHashSetCapacity(CFBasicHashRef ht, CFIndex capacity) {
1268     if (!CFBasicHashIsMutable(ht)) HALT;
1269     if (ht->bits.used_buckets < capacity) {
1270         ht->bits.mutations++;
1271         __CFBasicHashRehash(ht, capacity - ht->bits.used_buckets);
1272     }
1273 }
1274
1275 static void __CFBasicHashAddValue(CFBasicHashRef ht, CFIndex bkt_idx, uintptr_t stack_key, uintptr_t stack_value) {
1276     ht->bits.mutations++;
1277     if (CFBasicHashGetCapacity(ht) < ht->bits.used_buckets + 1) {
1278         __CFBasicHashRehash(ht, 1);
1279         bkt_idx = __CFBasicHashFindBucket_NoCollision(ht, stack_key, 0);
1280     } else if (__CFBasicHashIsDeleted(ht, bkt_idx)) {
1281         ht->bits.deleted--;
1282     }
1283     uintptr_t key_hash = 0;
1284     if (__CFBasicHashHasHashCache(ht)) {
1285         key_hash = __CFBasicHashHashKey(ht, stack_key);
1286     }
1287     stack_value = __CFBasicHashImportValue(ht, stack_value);
1288     if (ht->bits.keys_offset) {
1289         stack_key = __CFBasicHashImportKey(ht, stack_key);
1290     }
1291     __CFBasicHashSetValue(ht, bkt_idx, stack_value, false, false);
1292     if (ht->bits.keys_offset) {
1293         __CFBasicHashSetKey(ht, bkt_idx, stack_key, false, false);
1294     }
1295     if (ht->bits.counts_offset) {
1296         __CFBasicHashIncSlotCount(ht, bkt_idx);
1297     }
1298     if (__CFBasicHashHasHashCache(ht)) {
1299         __CFBasicHashGetHashes(ht)[bkt_idx] = key_hash;
1300     }
1301     ht->bits.used_buckets++;
1302 }
1303
1304 static void __CFBasicHashReplaceValue(CFBasicHashRef ht, CFIndex bkt_idx, uintptr_t stack_key, uintptr_t stack_value) {
1305     ht->bits.mutations++;
1306     stack_value = __CFBasicHashImportValue(ht, stack_value);
1307     if (ht->bits.keys_offset) {
1308         stack_key = __CFBasicHashImportKey(ht, stack_key);
1309     }
1310     __CFBasicHashSetValue(ht, bkt_idx, stack_value, false, false);
1311     if (ht->bits.keys_offset) {
1312         __CFBasicHashSetKey(ht, bkt_idx, stack_key, false, false);
1313     }
1314 }
1315
1316 static void __CFBasicHashRemoveValue(CFBasicHashRef ht, CFIndex bkt_idx) {
1317     ht->bits.mutations++;
1318     __CFBasicHashSetValue(ht, bkt_idx, ~0UL, false, true);
1319     if (ht->bits.keys_offset) {
1320         __CFBasicHashSetKey(ht, bkt_idx, ~0UL, false, true);
1321     }
1322     if (ht->bits.counts_offset) {
1323         __CFBasicHashDecSlotCount(ht, bkt_idx);
1324     }
1325     if (__CFBasicHashHasHashCache(ht)) {
1326         __CFBasicHashGetHashes(ht)[bkt_idx] = 0;
1327     }
1328     ht->bits.used_buckets--;
1329     ht->bits.deleted++;
1330     Boolean do_shrink = false;
1331     if (ht->bits.fast_grow) { // == slow shrink
1332         do_shrink = (5 < ht->bits.num_buckets_idx && ht->bits.used_buckets < __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx - 5));
1333     } else {
1334         do_shrink = (2 < ht->bits.num_buckets_idx && ht->bits.used_buckets < __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx - 2));
1335     }
1336     if (do_shrink) {
1337         __CFBasicHashRehash(ht, -1);
1338         return;
1339     }
1340     do_shrink = (0 == ht->bits.deleted); // .deleted roll-over
1341     CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1342     do_shrink = do_shrink || ((20 <= num_buckets) && (num_buckets / 4 <= ht->bits.deleted));
1343     if (do_shrink) {
1344         __CFBasicHashRehash(ht, 0);
1345     }
1346 }
1347
1348 CF_PRIVATE Boolean CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
1349     if (!CFBasicHashIsMutable(ht)) HALT;
1350     if (__CFBasicHashSubABZero == stack_key) HALT;
1351     if (__CFBasicHashSubABOne == stack_key) HALT;
1352     if (__CFBasicHashSubABZero == stack_value) HALT;
1353     if (__CFBasicHashSubABOne == stack_value) HALT;
1354     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1355     if (0 < bkt.count) {
1356         ht->bits.mutations++;
1357         if (ht->bits.counts_offset && bkt.count < LONG_MAX) { // if not yet as large as a CFIndex can be... otherwise clamp and do nothing
1358             __CFBasicHashIncSlotCount(ht, bkt.idx);
1359             return true;
1360         }
1361     } else {
1362         __CFBasicHashAddValue(ht, bkt.idx, stack_key, stack_value);
1363         return true;
1364     }
1365     return false;
1366 }
1367
1368 CF_PRIVATE void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
1369     if (!CFBasicHashIsMutable(ht)) HALT;
1370     if (__CFBasicHashSubABZero == stack_key) HALT;
1371     if (__CFBasicHashSubABOne == stack_key) HALT;
1372     if (__CFBasicHashSubABZero == stack_value) HALT;
1373     if (__CFBasicHashSubABOne == stack_value) HALT;
1374     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1375     if (0 < bkt.count) {
1376         __CFBasicHashReplaceValue(ht, bkt.idx, stack_key, stack_value);
1377     }
1378 }
1379
1380 CF_PRIVATE void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
1381     if (!CFBasicHashIsMutable(ht)) HALT;
1382     if (__CFBasicHashSubABZero == stack_key) HALT;
1383     if (__CFBasicHashSubABOne == stack_key) HALT;
1384     if (__CFBasicHashSubABZero == stack_value) HALT;
1385     if (__CFBasicHashSubABOne == stack_value) HALT;
1386     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1387     if (0 < bkt.count) {
1388         __CFBasicHashReplaceValue(ht, bkt.idx, stack_key, stack_value);
1389     } else {
1390         __CFBasicHashAddValue(ht, bkt.idx, stack_key, stack_value);
1391     }
1392 }
1393
1394 CF_PRIVATE CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key) {
1395     if (!CFBasicHashIsMutable(ht)) HALT;
1396     if (__CFBasicHashSubABZero == stack_key || __CFBasicHashSubABOne == stack_key) return 0;
1397     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1398     if (1 < bkt.count) {
1399         ht->bits.mutations++;
1400         if (ht->bits.counts_offset && bkt.count < LONG_MAX) { // if not as large as a CFIndex can be... otherwise clamp and do nothing
1401             __CFBasicHashDecSlotCount(ht, bkt.idx);
1402         }
1403     } else if (0 < bkt.count) {
1404         __CFBasicHashRemoveValue(ht, bkt.idx);
1405     }
1406     return bkt.count;
1407 }
1408
1409 CF_PRIVATE CFIndex CFBasicHashRemoveValueAtIndex(CFBasicHashRef ht, CFIndex idx) {
1410     if (!CFBasicHashIsMutable(ht)) HALT;
1411     CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
1412     if (1 < bkt.count) {
1413         ht->bits.mutations++;
1414         if (ht->bits.counts_offset && bkt.count < LONG_MAX) { // if not as large as a CFIndex can be... otherwise clamp and do nothing
1415             __CFBasicHashDecSlotCount(ht, bkt.idx);
1416         }
1417     } else if (0 < bkt.count) {
1418         __CFBasicHashRemoveValue(ht, bkt.idx);
1419     }
1420     return bkt.count;
1421 }
1422
1423 CF_PRIVATE void CFBasicHashRemoveAllValues(CFBasicHashRef ht) {
1424     if (!CFBasicHashIsMutable(ht)) HALT;
1425     if (0 == ht->bits.num_buckets_idx) return;
1426     __CFBasicHashDrain(ht, false);
1427 }
1428
1429 CF_PRIVATE Boolean CFBasicHashAddIntValueAndInc(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t int_value) {
1430     if (!CFBasicHashIsMutable(ht)) HALT;
1431     if (__CFBasicHashSubABZero == stack_key) HALT;
1432     if (__CFBasicHashSubABOne == stack_key) HALT;
1433     if (__CFBasicHashSubABZero == int_value) HALT;
1434     if (__CFBasicHashSubABOne == int_value) HALT;
1435     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1436     if (0 < bkt.count) {
1437         ht->bits.mutations++;
1438     } else {
1439         // must rehash before renumbering
1440         if (CFBasicHashGetCapacity(ht) < ht->bits.used_buckets + 1) {
1441             __CFBasicHashRehash(ht, 1);
1442             bkt.idx = __CFBasicHashFindBucket_NoCollision(ht, stack_key, 0);
1443         }
1444         CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1445         for (CFIndex idx = 0; idx < cnt; idx++) {
1446             if (!__CFBasicHashIsEmptyOrDeleted(ht, idx)) {
1447                 uintptr_t stack_value = __CFBasicHashGetValue(ht, idx);
1448                 if (int_value <= stack_value) {
1449                     stack_value++;
1450                     __CFBasicHashSetValue(ht, idx, stack_value, true, false);
1451                     ht->bits.mutations++;
1452                 }
1453             }
1454         }
1455         __CFBasicHashAddValue(ht, bkt.idx, stack_key, int_value);
1456         return true;
1457     }
1458     return false;
1459 }
1460
1461 CF_PRIVATE void CFBasicHashRemoveIntValueAndDec(CFBasicHashRef ht, uintptr_t int_value) {
1462     if (!CFBasicHashIsMutable(ht)) HALT;
1463     if (__CFBasicHashSubABZero == int_value) HALT;
1464     if (__CFBasicHashSubABOne == int_value) HALT;
1465     uintptr_t bkt_idx = ~0UL;
1466     CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1467     for (CFIndex idx = 0; idx < cnt; idx++) {
1468         if (!__CFBasicHashIsEmptyOrDeleted(ht, idx)) {
1469             uintptr_t stack_value = __CFBasicHashGetValue(ht, idx);
1470             if (int_value == stack_value) {
1471                 bkt_idx = idx;
1472             }
1473             if (int_value < stack_value) {
1474                 stack_value--;
1475                 __CFBasicHashSetValue(ht, idx, stack_value, true, false);
1476                 ht->bits.mutations++;
1477             }
1478         }
1479     }
1480     __CFBasicHashRemoveValue(ht, bkt_idx);
1481 }
1482
1483 CF_PRIVATE size_t CFBasicHashGetSize(CFConstBasicHashRef ht, Boolean total) {
1484     size_t size = sizeof(struct __CFBasicHash);
1485     if (ht->bits.keys_offset) size += sizeof(CFBasicHashValue *);
1486     if (ht->bits.counts_offset) size += sizeof(void *);
1487     if (__CFBasicHashHasHashCache(ht)) size += sizeof(uintptr_t *);
1488     if (total) {
1489         CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1490         if (0 < num_buckets) {
1491             size += malloc_size(__CFBasicHashGetValues(ht));
1492             if (ht->bits.keys_offset) size += malloc_size(__CFBasicHashGetKeys(ht));
1493             if (ht->bits.counts_offset) size += malloc_size(__CFBasicHashGetCounts(ht));
1494             if (__CFBasicHashHasHashCache(ht)) size += malloc_size(__CFBasicHashGetHashes(ht));
1495         }
1496     }
1497     return size;
1498 }
1499
1500 CF_PRIVATE CFStringRef CFBasicHashCopyDescription(CFConstBasicHashRef ht, Boolean detailed, CFStringRef prefix, CFStringRef entryPrefix, Boolean describeElements) {
1501     CFMutableStringRef result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
1502     CFStringAppendFormat(result, NULL, CFSTR("%@{type = %s %s%s, count = %ld,\n"), prefix, (CFBasicHashIsMutable(ht) ? "mutable" : "immutable"), ((ht->bits.counts_offset) ? "multi" : ""), ((ht->bits.keys_offset) ? "dict" : "set"), CFBasicHashGetCount(ht));
1503     if (detailed) {
1504         const char *cb_type = "custom";
1505         CFStringAppendFormat(result, NULL, CFSTR("%@hash cache = %s, strong values = %s, strong keys = %s, cb = %s,\n"), prefix, (__CFBasicHashHasHashCache(ht) ? "yes" : "no"), (CFBasicHashHasStrongValues(ht) ? "yes" : "no"), (CFBasicHashHasStrongKeys(ht) ? "yes" : "no"), cb_type);
1506         CFStringAppendFormat(result, NULL, CFSTR("%@num bucket index = %d, num buckets = %ld, capacity = %ld, num buckets used = %u,\n"), prefix, ht->bits.num_buckets_idx, CFBasicHashGetNumBuckets(ht), (long)CFBasicHashGetCapacity(ht), ht->bits.used_buckets);
1507         CFStringAppendFormat(result, NULL, CFSTR("%@counts width = %d, finalized = %s,\n"), prefix,((ht->bits.counts_offset) ? (1 << ht->bits.counts_width) : 0), (ht->bits.finalized ? "yes" : "no"));
1508         CFStringAppendFormat(result, NULL, CFSTR("%@num mutations = %ld, num deleted = %ld, size = %ld, total size = %ld,\n"), prefix, (long)ht->bits.mutations, (long)ht->bits.deleted, CFBasicHashGetSize(ht, false), CFBasicHashGetSize(ht, true));
1509         CFStringAppendFormat(result, NULL, CFSTR("%@values ptr = %p, keys ptr = %p, counts ptr = %p, hashes ptr = %p,\n"), prefix, __CFBasicHashGetValues(ht), ((ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : NULL), ((ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht) : NULL), (__CFBasicHashHasHashCache(ht) ? __CFBasicHashGetHashes(ht) : NULL));
1510     }
1511     CFStringAppendFormat(result, NULL, CFSTR("%@entries =>\n"), prefix);
1512     CFBasicHashApply(ht, ^(CFBasicHashBucket bkt) {
1513             CFStringRef vDesc = NULL, kDesc = NULL;
1514             if (!describeElements) {
1515                 vDesc = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)bkt.weak_value);
1516                 if (ht->bits.keys_offset) {
1517                     kDesc = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)bkt.weak_key);
1518                 }
1519             } else {
1520                 vDesc = __CFBasicHashDescValue(ht, bkt.weak_value);
1521                 if (ht->bits.keys_offset) {
1522                     kDesc = __CFBasicHashDescKey(ht, bkt.weak_key);
1523                 }
1524             }
1525             if (ht->bits.keys_offset && ht->bits.counts_offset) {
1526                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ = %@ (%ld)\n"), entryPrefix, bkt.idx, kDesc, vDesc, bkt.count);
1527             } else if (ht->bits.keys_offset) {
1528                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ = %@\n"), entryPrefix, bkt.idx, kDesc, vDesc);
1529             } else if (ht->bits.counts_offset) {
1530                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ (%ld)\n"), entryPrefix, bkt.idx, vDesc, bkt.count);
1531             } else {
1532                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@\n"), entryPrefix, bkt.idx, vDesc);
1533             }
1534             if (kDesc) CFRelease(kDesc);
1535             if (vDesc) CFRelease(vDesc);
1536             return (Boolean)true;
1537         });
1538     CFStringAppendFormat(result, NULL, CFSTR("%@}\n"), prefix);
1539     return result;
1540 }
1541
1542 CF_PRIVATE void CFBasicHashShow(CFConstBasicHashRef ht) {
1543     CFStringRef str = CFBasicHashCopyDescription(ht, true, CFSTR(""), CFSTR("\t"), false);
1544     CFShow(str);
1545     CFRelease(str);
1546 }
1547
1548 CF_PRIVATE Boolean __CFBasicHashEqual(CFTypeRef cf1, CFTypeRef cf2) {
1549     CFBasicHashRef ht1 = (CFBasicHashRef)cf1;
1550     CFBasicHashRef ht2 = (CFBasicHashRef)cf2;
1551 //#warning this used to require that the key and value equal callbacks were pointer identical
1552     return CFBasicHashesAreEqual(ht1, ht2);
1553 }
1554
1555 CF_PRIVATE CFHashCode __CFBasicHashHash(CFTypeRef cf) {
1556     CFBasicHashRef ht = (CFBasicHashRef)cf;
1557     return CFBasicHashGetCount(ht);
1558 }
1559
1560 CF_PRIVATE CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf) {
1561     CFBasicHashRef ht = (CFBasicHashRef)cf;
1562     CFStringRef desc = CFBasicHashCopyDescription(ht, false, CFSTR(""), CFSTR("\t"), true);
1563     CFStringRef result = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<CFBasicHash %p [%p]>%@"), cf, CFGetAllocator(cf), desc);
1564     CFRelease(desc);
1565     return result;
1566 }
1567
1568 CF_PRIVATE void __CFBasicHashDeallocate(CFTypeRef cf) {
1569     CFBasicHashRef ht = (CFBasicHashRef)cf;
1570     if (ht->bits.finalized) HALT;
1571     ht->bits.finalized = 1;
1572     __CFBasicHashDrain(ht, true);
1573 #if ENABLE_MEMORY_COUNTERS
1574     OSAtomicAdd64Barrier(-1, &__CFBasicHashTotalCount);
1575     OSAtomicAdd32Barrier(-1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1576 #endif
1577 }
1578
1579 static CFTypeID __kCFBasicHashTypeID = _kCFRuntimeNotATypeID;
1580
1581 static const CFRuntimeClass __CFBasicHashClass = {
1582     _kCFRuntimeScannedObject,
1583     "CFBasicHash",
1584     NULL,        // init
1585     NULL,        // copy
1586     __CFBasicHashDeallocate,
1587     __CFBasicHashEqual,
1588     __CFBasicHashHash,
1589     NULL,        //
1590     __CFBasicHashCopyDescription
1591 };
1592
1593 CF_PRIVATE CFTypeID CFBasicHashGetTypeID(void) {
1594     if (_kCFRuntimeNotATypeID == __kCFBasicHashTypeID) __kCFBasicHashTypeID = _CFRuntimeRegisterClass(&__CFBasicHashClass);
1595     return __kCFBasicHashTypeID;
1596 }
1597
1598 CF_PRIVATE CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb) {
1599     size_t size = sizeof(struct __CFBasicHash) - sizeof(CFRuntimeBase);
1600     if (flags & kCFBasicHashHasKeys) size += sizeof(CFBasicHashValue *); // keys
1601     if (flags & kCFBasicHashHasCounts) size += sizeof(void *); // counts
1602     if (flags & kCFBasicHashHasHashCache) size += sizeof(uintptr_t *); // hashes
1603     CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL);
1604     if (NULL == ht) return NULL;
1605
1606     ht->bits.finalized = 0;
1607     ht->bits.hash_style = (flags >> 13) & 0x3;
1608     ht->bits.fast_grow = (flags & kCFBasicHashAggressiveGrowth) ? 1 : 0;
1609     ht->bits.counts_width = 0;
1610     ht->bits.strong_values = (flags & kCFBasicHashStrongValues) ? 1 : 0;
1611     ht->bits.strong_keys = (flags & kCFBasicHashStrongKeys) ? 1 : 0;
1612     ht->bits.weak_values = (flags & kCFBasicHashWeakValues) ? 1 : 0;
1613     ht->bits.weak_keys = (flags & kCFBasicHashWeakKeys) ? 1 : 0;
1614     ht->bits.int_values = (flags & kCFBasicHashIntegerValues) ? 1 : 0;
1615     ht->bits.int_keys = (flags & kCFBasicHashIntegerKeys) ? 1 : 0;
1616     ht->bits.indirect_keys = (flags & kCFBasicHashIndirectKeys) ? 1 : 0;
1617     ht->bits.num_buckets_idx = 0;
1618     ht->bits.used_buckets = 0;
1619     ht->bits.deleted = 0;
1620     ht->bits.mutations = 1;
1621
1622     if (ht->bits.strong_values && ht->bits.weak_values) HALT;
1623     if (ht->bits.strong_values && ht->bits.int_values) HALT;
1624     if (ht->bits.strong_keys && ht->bits.weak_keys) HALT;
1625     if (ht->bits.strong_keys && ht->bits.int_keys) HALT;
1626     if (ht->bits.weak_values && ht->bits.int_values) HALT;
1627     if (ht->bits.weak_keys && ht->bits.int_keys) HALT;
1628     if (ht->bits.indirect_keys && ht->bits.strong_keys) HALT;
1629     if (ht->bits.indirect_keys && ht->bits.weak_keys) HALT;
1630     if (ht->bits.indirect_keys && ht->bits.int_keys) HALT;
1631
1632     uint64_t offset = 1;
1633     ht->bits.keys_offset = (flags & kCFBasicHashHasKeys) ? offset++ : 0;
1634     ht->bits.counts_offset = (flags & kCFBasicHashHasCounts) ? offset++ : 0;
1635     ht->bits.hashes_offset = (flags & kCFBasicHashHasHashCache) ? offset++ : 0;
1636
1637 #if DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_EMBEDDED_MINI
1638     ht->bits.hashes_offset = 0;
1639     ht->bits.strong_values = 0;
1640     ht->bits.strong_keys = 0;
1641     ht->bits.weak_values = 0;
1642     ht->bits.weak_keys = 0;
1643 #endif
1644
1645     ht->bits.__kret = CFBasicHashGetPtrIndex((void *)cb->retainKey);
1646     ht->bits.__vret = CFBasicHashGetPtrIndex((void *)cb->retainValue);
1647     ht->bits.__krel = CFBasicHashGetPtrIndex((void *)cb->releaseKey);
1648     ht->bits.__vrel = CFBasicHashGetPtrIndex((void *)cb->releaseValue);
1649     ht->bits.__kdes = CFBasicHashGetPtrIndex((void *)cb->copyKeyDescription);
1650     ht->bits.__vdes = CFBasicHashGetPtrIndex((void *)cb->copyValueDescription);
1651     ht->bits.__kequ = CFBasicHashGetPtrIndex((void *)cb->equateKeys);
1652     ht->bits.__vequ = CFBasicHashGetPtrIndex((void *)cb->equateValues);
1653     ht->bits.__khas = CFBasicHashGetPtrIndex((void *)cb->hashKey);
1654     ht->bits.__kget = CFBasicHashGetPtrIndex((void *)cb->getIndirectKey);
1655
1656     for (CFIndex idx = 0; idx < offset; idx++) {
1657         ht->pointers[idx] = NULL;
1658     }
1659
1660 #if ENABLE_MEMORY_COUNTERS
1661     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1662     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1663     int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount);
1664     while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount));
1665     OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1666 #endif
1667
1668     return ht;
1669 }
1670
1671 CF_PRIVATE CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFConstBasicHashRef src_ht) {
1672     size_t size = CFBasicHashGetSize(src_ht, false) - sizeof(CFRuntimeBase);
1673     CFIndex new_num_buckets = __CFBasicHashTableSizes[src_ht->bits.num_buckets_idx];
1674     CFBasicHashValue *new_values = NULL, *new_keys = NULL;
1675     void *new_counts = NULL;
1676     uintptr_t *new_hashes = NULL;
1677
1678     if (0 < new_num_buckets) {
1679         Boolean strongValues = CFBasicHashHasStrongValues(src_ht) && !(kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
1680         Boolean strongKeys = CFBasicHashHasStrongKeys(src_ht) && !(kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
1681         new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, sizeof(CFBasicHashValue), strongValues, 0);
1682         if (!new_values) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1683         __SetLastAllocationEventName(new_values, "CFBasicHash (value-store)");
1684         if (src_ht->bits.keys_offset) {
1685             new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, sizeof(CFBasicHashValue), strongKeys, false);
1686             if (!new_keys) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1687             __SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)");
1688         }
1689         if (src_ht->bits.counts_offset) {
1690             new_counts = (uintptr_t *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, (1 << src_ht->bits.counts_width), false, false);
1691             if (!new_counts) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1692             __SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)");
1693         }
1694         if (__CFBasicHashHasHashCache(src_ht)) {
1695             new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, sizeof(uintptr_t), false, false);
1696             if (!new_hashes) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1697             __SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)");
1698         }
1699     }
1700
1701     CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL);
1702     if (NULL == ht) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1703
1704     memmove((uint8_t *)ht + sizeof(CFRuntimeBase), (uint8_t *)src_ht + sizeof(CFRuntimeBase), sizeof(ht->bits));
1705     if (kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
1706         ht->bits.strong_values = 0;
1707         ht->bits.strong_keys = 0;
1708         ht->bits.weak_values = 0;
1709         ht->bits.weak_keys = 0;
1710     }
1711     ht->bits.finalized = 0;
1712     ht->bits.mutations = 1;
1713
1714     if (0 == new_num_buckets) {
1715 #if ENABLE_MEMORY_COUNTERS
1716         int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1717         while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1718         int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount);
1719         while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount));
1720         OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1721 #endif
1722         return ht;
1723     }
1724
1725     CFBasicHashValue *old_values = NULL, *old_keys = NULL;
1726     void *old_counts = NULL;
1727     uintptr_t *old_hashes = NULL;
1728
1729     old_values = __CFBasicHashGetValues(src_ht);
1730     if (src_ht->bits.keys_offset) {
1731         old_keys = __CFBasicHashGetKeys(src_ht);
1732     }
1733     if (src_ht->bits.counts_offset) {
1734         old_counts = __CFBasicHashGetCounts(src_ht);
1735     }
1736     if (__CFBasicHashHasHashCache(src_ht)) {
1737         old_hashes = __CFBasicHashGetHashes(src_ht);
1738     }
1739
1740     __CFBasicHashSetValues(ht, new_values);
1741     if (new_keys) {
1742         __CFBasicHashSetKeys(ht, new_keys);
1743     }
1744     if (new_counts) {
1745         __CFBasicHashSetCounts(ht, new_counts);
1746     }
1747     if (new_hashes) {
1748         __CFBasicHashSetHashes(ht, new_hashes);
1749     }
1750
1751     for (CFIndex idx = 0; idx < new_num_buckets; idx++) {
1752         uintptr_t stack_value = old_values[idx].neutral;
1753         if (stack_value != 0UL && stack_value != ~0UL) {
1754             uintptr_t old_value = stack_value;
1755             if (__CFBasicHashSubABZero == old_value) old_value = 0UL;
1756             if (__CFBasicHashSubABOne == old_value) old_value = ~0UL;
1757             __CFBasicHashSetValue(ht, idx, __CFBasicHashImportValue(ht, old_value), true, false);
1758             if (new_keys) {
1759                 uintptr_t old_key = old_keys[idx].neutral;
1760                 if (__CFBasicHashSubABZero == old_key) old_key = 0UL;
1761                 if (__CFBasicHashSubABOne == old_key) old_key = ~0UL;
1762                 __CFBasicHashSetKey(ht, idx, __CFBasicHashImportKey(ht, old_key), true, false);
1763             }
1764         } else {
1765             __CFBasicHashSetValue(ht, idx, stack_value, true, true);
1766             if (new_keys) {
1767                 __CFBasicHashSetKey(ht, idx, stack_value, true, true);
1768             }
1769         }
1770     }
1771     if (new_counts) memmove(new_counts, old_counts, new_num_buckets * (1 << ht->bits.counts_width));
1772     if (new_hashes) memmove(new_hashes, old_hashes, new_num_buckets * sizeof(uintptr_t));
1773
1774 #if ENABLE_MEMORY_COUNTERS
1775     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1776     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1777     int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount);
1778     while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount));
1779     OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1780 #endif
1781
1782     return ht;
1783 }
1784
1785