CFBasicHash.c

   1 /*
   2  * Copyright (c) 2015 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-2014, 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 __CFBasicHashHasHashCache(CFConstBasicHashRef ht) {
 395 #if DEPLOYMENT_TARGET_MACOSX
 396     return ht->bits.hashes_offset ? true : false;
 397 #else
 398     return false;
 399 #endif
 400 }
 401
 402 CF_INLINE uintptr_t __CFBasicHashImportValue(CFConstBasicHashRef ht, uintptr_t stack_value) {
 403     uintptr_t (*func)(CFAllocatorRef, uintptr_t) = (uintptr_t (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vret];
 404     if (!func || ht->bits.null_rc) return stack_value;
 405     CFAllocatorRef alloc = CFGetAllocator(ht);
 406     return func(alloc, stack_value);
 407 }
 408
 409 CF_INLINE uintptr_t __CFBasicHashImportKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 410     uintptr_t (*func)(CFAllocatorRef, uintptr_t) = (uintptr_t (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kret];
 411     if (!func || ht->bits.null_rc) return stack_key;
 412     CFAllocatorRef alloc = CFGetAllocator(ht);
 413     return func(alloc, stack_key);
 414 }
 415
 416 CF_INLINE void __CFBasicHashEjectValue(CFConstBasicHashRef ht, uintptr_t stack_value) {
 417     void (*func)(CFAllocatorRef, uintptr_t) = (void (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vrel];
 418     if (!func || ht->bits.null_rc) return;
 419     CFAllocatorRef alloc = CFGetAllocator(ht);
 420     func(alloc, stack_value);
 421 }
 422
 423 CF_INLINE void __CFBasicHashEjectKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 424     void (*func)(CFAllocatorRef, uintptr_t) = (void (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__krel];
 425     if (!func || ht->bits.null_rc) return;
 426     CFAllocatorRef alloc = CFGetAllocator(ht);
 427     func(alloc, stack_key);
 428 }
 429
 430 CF_INLINE CFStringRef __CFBasicHashDescValue(CFConstBasicHashRef ht, uintptr_t stack_value) {
 431     CFStringRef (*func)(uintptr_t) = (CFStringRef (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vdes];
 432     if (!func) return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)stack_value);
 433     return func(stack_value);
 434 }
 435
 436 CF_INLINE CFStringRef __CFBasicHashDescKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 437     CFStringRef (*func)(uintptr_t) = (CFStringRef (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kdes];
 438     if (!func) return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)stack_key);
 439     return func(stack_key);
 440 }
 441
 442 CF_INLINE Boolean __CFBasicHashTestEqualValue(CFConstBasicHashRef ht, uintptr_t stack_value_a, uintptr_t stack_value_b) {
 443     Boolean (*func)(uintptr_t, uintptr_t) = (Boolean (*)(uintptr_t, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vequ];
 444     if (!func) return (stack_value_a == stack_value_b);
 445     return func(stack_value_a, stack_value_b);
 446 }
 447
 448 CF_INLINE Boolean __CFBasicHashTestEqualKey(CFConstBasicHashRef ht, uintptr_t in_coll_key, uintptr_t stack_key) {
 449     COCOA_HASHTABLE_TEST_EQUAL(ht, in_coll_key, stack_key);
 450     Boolean (*func)(uintptr_t, uintptr_t) = (Boolean (*)(uintptr_t, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kequ];
 451     if (!func) return (in_coll_key == stack_key);
 452     return func(in_coll_key, stack_key);
 453 }
 454
 455 CF_INLINE CFHashCode __CFBasicHashHashKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 456     CFHashCode (*func)(uintptr_t) = (CFHashCode (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__khas];
 457     CFHashCode hash_code = func ? func(stack_key) : stack_key;
 458     COCOA_HASHTABLE_HASH_KEY(ht, stack_key, hash_code);
 459     return hash_code;
 460 }
 461
 462 CF_INLINE uintptr_t __CFBasicHashGetIndirectKey(CFConstBasicHashRef ht, uintptr_t coll_key) {
 463     uintptr_t (*func)(uintptr_t) = (uintptr_t (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kget];
 464     if (!func) return coll_key;
 465     return func(coll_key);
 466 }
 467
 468 CF_INLINE CFBasicHashValue *__CFBasicHashGetValues(CFConstBasicHashRef ht) {
 469     return (CFBasicHashValue *)ht->pointers[0];
 470 }
 471
 472 CF_INLINE void __CFBasicHashSetValues(CFBasicHashRef ht, CFBasicHashValue *ptr) {
 473     __AssignWithWriteBarrier(&ht->pointers[0], ptr);
 474 }
 475
 476 CF_INLINE CFBasicHashValue *__CFBasicHashGetKeys(CFConstBasicHashRef ht) {
 477     return (CFBasicHashValue *)ht->pointers[ht->bits.keys_offset];
 478 }
 479
 480 CF_INLINE void __CFBasicHashSetKeys(CFBasicHashRef ht, CFBasicHashValue *ptr) {
 481     __AssignWithWriteBarrier(&ht->pointers[ht->bits.keys_offset], ptr);
 482 }
 483
 484 CF_INLINE void *__CFBasicHashGetCounts(CFConstBasicHashRef ht) {
 485     return (void *)ht->pointers[ht->bits.counts_offset];
 486 }
 487
 488 CF_INLINE void __CFBasicHashSetCounts(CFBasicHashRef ht, void *ptr) {
 489     __AssignWithWriteBarrier(&ht->pointers[ht->bits.counts_offset], ptr);
 490 }
 491
 492 CF_INLINE uintptr_t __CFBasicHashGetValue(CFConstBasicHashRef ht, CFIndex idx) {
 493     uintptr_t val = __CFBasicHashGetValues(ht)[idx].neutral;
 494     if (__CFBasicHashSubABZero == val) return 0UL;
 495     if (__CFBasicHashSubABOne == val) return ~0UL;
 496     return val;
 497 }
 498
 499 CF_INLINE void __CFBasicHashSetValue(CFBasicHashRef ht, CFIndex idx, uintptr_t stack_value, Boolean ignoreOld, Boolean literal) {
 500     CFBasicHashValue *valuep = &(__CFBasicHashGetValues(ht)[idx]);
 501     uintptr_t old_value = ignoreOld ? 0 : valuep->neutral;
 502     if (!literal) {
 503         if (0UL == stack_value) stack_value = __CFBasicHashSubABZero;
 504         if (~0UL == stack_value) stack_value = __CFBasicHashSubABOne;
 505     }
 506     if (CFBasicHashHasStrongValues(ht)) valuep->strong = (id)stack_value; else valuep->neutral = stack_value;
 507     if (!ignoreOld) {
 508         if (!(old_value == 0UL || old_value == ~0UL)) {
 509             if (__CFBasicHashSubABZero == old_value) old_value = 0UL;
 510             if (__CFBasicHashSubABOne == old_value) old_value = ~0UL;
 511             __CFBasicHashEjectValue(ht, old_value);
 512         }
 513     }
 514 }
 515
 516 CF_INLINE uintptr_t __CFBasicHashGetKey(CFConstBasicHashRef ht, CFIndex idx) {
 517     if (ht->bits.keys_offset) {
 518         uintptr_t key = __CFBasicHashGetKeys(ht)[idx].neutral;
 519         if (__CFBasicHashSubABZero == key) return 0UL;
 520         if (__CFBasicHashSubABOne == key) return ~0UL;
 521         return key;
 522     }
 523     if (ht->bits.indirect_keys) {
 524         uintptr_t stack_value = __CFBasicHashGetValue(ht, idx);
 525         return __CFBasicHashGetIndirectKey(ht, stack_value);
 526     }
 527     return __CFBasicHashGetValue(ht, idx);
 528 }
 529
 530 CF_INLINE void __CFBasicHashSetKey(CFBasicHashRef ht, CFIndex idx, uintptr_t stack_key, Boolean ignoreOld, Boolean literal) {
 531     if (0 == ht->bits.keys_offset) HALT;
 532     CFBasicHashValue *keyp = &(__CFBasicHashGetKeys(ht)[idx]);
 533     uintptr_t old_key = ignoreOld ? 0 : keyp->neutral;
 534     if (!literal) {
 535         if (0UL == stack_key) stack_key = __CFBasicHashSubABZero;
 536         if (~0UL == stack_key) stack_key = __CFBasicHashSubABOne;
 537     }
 538     if (CFBasicHashHasStrongKeys(ht)) keyp->strong = (id)stack_key; else keyp->neutral = stack_key;
 539     if (!ignoreOld) {
 540         if (!(old_key == 0UL || old_key == ~0UL)) {
 541             if (__CFBasicHashSubABZero == old_key) old_key = 0UL;
 542             if (__CFBasicHashSubABOne == old_key) old_key = ~0UL;
 543             __CFBasicHashEjectKey(ht, old_key);
 544         }
 545     }
 546 }
 547
 548 CF_INLINE uintptr_t __CFBasicHashIsEmptyOrDeleted(CFConstBasicHashRef ht, CFIndex idx) {
 549     uintptr_t stack_value = __CFBasicHashGetValues(ht)[idx].neutral;
 550     return (0UL == stack_value || ~0UL == stack_value);
 551 }
 552
 553 CF_INLINE uintptr_t __CFBasicHashIsDeleted(CFConstBasicHashRef ht, CFIndex idx) {
 554     uintptr_t stack_value = __CFBasicHashGetValues(ht)[idx].neutral;
 555     return (~0UL == stack_value);
 556 }
 557
 558 CF_INLINE uintptr_t __CFBasicHashGetSlotCount(CFConstBasicHashRef ht, CFIndex idx) {
 559     void *counts = __CFBasicHashGetCounts(ht);
 560     switch (ht->bits.counts_width) {
 561     case 0: return ((uint8_t *)counts)[idx];
 562     case 1: return ((uint16_t *)counts)[idx];
 563     case 2: return ((uint32_t *)counts)[idx];
 564     case 3: return ((uint64_t *)counts)[idx];
 565     }
 566     return 0;
 567 }
 568
 569 CF_INLINE void __CFBasicHashBumpCounts(CFBasicHashRef ht) {
 570     void *counts = __CFBasicHashGetCounts(ht);
 571     CFAllocatorRef allocator = CFGetAllocator(ht);
 572     switch (ht->bits.counts_width) {
 573     case 0: {
 574         uint8_t *counts08 = (uint8_t *)counts;
 575         ht->bits.counts_width = 1;
 576         CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 577         uint16_t *counts16 = (uint16_t *)__CFBasicHashAllocateMemory(ht, num_buckets, 2, false, false);
 578         if (!counts16) HALT;
 579         __SetLastAllocationEventName(counts16, "CFBasicHash (count-store)");
 580         for (CFIndex idx2 = 0; idx2 < num_buckets; idx2++) {
 581             counts16[idx2] = counts08[idx2];
 582         }
 583         __CFBasicHashSetCounts(ht, counts16);
 584         if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 585             CFAllocatorDeallocate(allocator, counts08);
 586         }
 587         break;
 588     }
 589     case 1: {
 590         uint16_t *counts16 = (uint16_t *)counts;
 591         ht->bits.counts_width = 2;
 592         CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 593         uint32_t *counts32 = (uint32_t *)__CFBasicHashAllocateMemory(ht, num_buckets, 4, false, false);
 594         if (!counts32) HALT;
 595         __SetLastAllocationEventName(counts32, "CFBasicHash (count-store)");
 596         for (CFIndex idx2 = 0; idx2 < num_buckets; idx2++) {
 597             counts32[idx2] = counts16[idx2];
 598         }
 599         __CFBasicHashSetCounts(ht, counts32);
 600          if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 601             CFAllocatorDeallocate(allocator, counts16);
 602         }
 603         break;
 604     }
 605     case 2: {
 606         uint32_t *counts32 = (uint32_t *)counts;
 607         ht->bits.counts_width = 3;
 608         CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 609         uint64_t *counts64 = (uint64_t *)__CFBasicHashAllocateMemory(ht, num_buckets, 8, false, false);
 610         if (!counts64) HALT;
 611         __SetLastAllocationEventName(counts64, "CFBasicHash (count-store)");
 612         for (CFIndex idx2 = 0; idx2 < num_buckets; idx2++) {
 613             counts64[idx2] = counts32[idx2];
 614         }
 615         __CFBasicHashSetCounts(ht, counts64);
 616          if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 617             CFAllocatorDeallocate(allocator, counts32);
 618         }
 619         break;
 620     }
 621     case 3: {
 622         HALT;
 623         break;
 624     }
 625     }
 626 }
 627
 628 static void __CFBasicHashIncSlotCount(CFBasicHashRef ht, CFIndex idx) {
 629     void *counts = __CFBasicHashGetCounts(ht);
 630     switch (ht->bits.counts_width) {
 631     case 0: {
 632         uint8_t *counts08 = (uint8_t *)counts;
 633         uint8_t val = counts08[idx];
 634         if (val < INT8_MAX) {
 635             counts08[idx] = val + 1;
 636             return;
 637         }
 638         __CFBasicHashBumpCounts(ht);
 639         __CFBasicHashIncSlotCount(ht, idx);
 640         break;
 641     }
 642     case 1: {
 643         uint16_t *counts16 = (uint16_t *)counts;
 644         uint16_t val = counts16[idx];
 645         if (val < INT16_MAX) {
 646             counts16[idx] = val + 1;
 647             return;
 648         }
 649         __CFBasicHashBumpCounts(ht);
 650         __CFBasicHashIncSlotCount(ht, idx);
 651         break;
 652     }
 653     case 2: {
 654         uint32_t *counts32 = (uint32_t *)counts;
 655         uint32_t val = counts32[idx];
 656         if (val < INT32_MAX) {
 657             counts32[idx] = val + 1;
 658             return;
 659         }
 660         __CFBasicHashBumpCounts(ht);
 661         __CFBasicHashIncSlotCount(ht, idx);
 662         break;
 663     }
 664     case 3: {
 665         uint64_t *counts64 = (uint64_t *)counts;
 666         uint64_t val = counts64[idx];
 667         if (val < INT64_MAX) {
 668             counts64[idx] = val + 1;
 669             return;
 670         }
 671         __CFBasicHashBumpCounts(ht);
 672         __CFBasicHashIncSlotCount(ht, idx);
 673         break;
 674     }
 675     }
 676 }
 677
 678 CF_INLINE void __CFBasicHashDecSlotCount(CFBasicHashRef ht, CFIndex idx) {
 679     void *counts = __CFBasicHashGetCounts(ht);
 680     switch (ht->bits.counts_width) {
 681     case 0: ((uint8_t  *)counts)[idx]--; return;
 682     case 1: ((uint16_t *)counts)[idx]--; return;
 683     case 2: ((uint32_t *)counts)[idx]--; return;
 684     case 3: ((uint64_t *)counts)[idx]--; return;
 685     }
 686 }
 687
 688 CF_INLINE uintptr_t *__CFBasicHashGetHashes(CFConstBasicHashRef ht) {
 689     return (uintptr_t *)ht->pointers[ht->bits.hashes_offset];
 690 }
 691
 692 CF_INLINE void __CFBasicHashSetHashes(CFBasicHashRef ht, uintptr_t *ptr) {
 693     __AssignWithWriteBarrier(&ht->pointers[ht->bits.hashes_offset], ptr);
 694 }
 695
 696
 697 // to expose the load factor, expose this function to customization
 698 CF_INLINE CFIndex __CFBasicHashGetCapacityForNumBuckets(CFConstBasicHashRef ht, CFIndex num_buckets_idx) {
 699     return __CFBasicHashTableCapacities[num_buckets_idx];
 700 }
 701
 702 CF_INLINE CFIndex __CFBasicHashGetNumBucketsIndexForCapacity(CFConstBasicHashRef ht, CFIndex capacity) {
 703     for (CFIndex idx = 0; idx < 64; idx++) {
 704         if (capacity <= __CFBasicHashGetCapacityForNumBuckets(ht, idx)) return idx;
 705     }
 706     HALT;
 707     return 0;
 708 }
 709
 710 CF_PRIVATE CFIndex CFBasicHashGetNumBuckets(CFConstBasicHashRef ht) {
 711     return __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 712 }
 713
 714 CF_PRIVATE CFIndex CFBasicHashGetCapacity(CFConstBasicHashRef ht) {
 715     return __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx);
 716 }
 717
 718 // In returned struct, .count is zero if the bucket is empty or deleted,
 719 // and the .weak_key field indicates which. .idx is either the index of
 720 // the found bucket or the index of the bucket which should be filled by
 721 // an add operation. For a set or multiset, the .weak_key and .weak_value
 722 // are the same.
 723 CF_PRIVATE CFBasicHashBucket CFBasicHashGetBucket(CFConstBasicHashRef ht, CFIndex idx) {
 724     CFBasicHashBucket result;
 725     result.idx = idx;
 726     if (__CFBasicHashIsEmptyOrDeleted(ht, idx)) {
 727         result.count = 0;
 728         result.weak_value = 0;
 729         result.weak_key = 0;
 730     } else {
 731         result.count = (ht->bits.counts_offset) ? __CFBasicHashGetSlotCount(ht, idx) : 1;
 732         result.weak_value = __CFBasicHashGetValue(ht, idx);
 733         result.weak_key = __CFBasicHashGetKey(ht, idx);
 734     }
 735     return result;
 736 }
 737
 738 #if defined(__arm__)
 739 static uintptr_t __CFBasicHashFold(uintptr_t dividend, uint8_t idx) {
 740     switch (idx) {
 741     case 1: return dividend % 3;
 742     case 2: return dividend % 7;
 743     case 3: return dividend % 13;
 744     case 4: return dividend % 23;
 745     case 5: return dividend % 41;
 746     case 6: return dividend % 71;
 747     case 7: return dividend % 127;
 748     case 8: return dividend % 191;
 749     case 9: return dividend % 251;
 750     case 10: return dividend % 383;
 751     case 11: return dividend % 631;
 752     case 12: return dividend % 1087;
 753     case 13: return dividend % 1723;
 754     case 14: return dividend % 2803;
 755     case 15: return dividend % 4523;
 756     case 16: return dividend % 7351;
 757     case 17: return dividend % 11959;
 758     case 18: return dividend % 19447;
 759     case 19: return dividend % 31231;
 760     case 20: return dividend % 50683;
 761     case 21: return dividend % 81919;
 762     case 22: return dividend % 132607;
 763     case 23: return dividend % 214519;
 764     case 24: return dividend % 346607;
 765     case 25: return dividend % 561109;
 766     case 26: return dividend % 907759;
 767     case 27: return dividend % 1468927;
 768     case 28: return dividend % 2376191;
 769     case 29: return dividend % 3845119;
 770     case 30: return dividend % 6221311;
 771     case 31: return dividend % 10066421;
 772     case 32: return dividend % 16287743;
 773     case 33: return dividend % 26354171;
 774     case 34: return dividend % 42641881;
 775     case 35: return dividend % 68996069;
 776     case 36: return dividend % 111638519;
 777     case 37: return dividend % 180634607;
 778     case 38: return dividend % 292272623;
 779     case 39: return dividend % 472907251;
 780     }
 781     HALT;
 782     return ~0;
 783 }
 784 #endif
 785
 786
 787 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Linear
 788 #define FIND_BUCKET_HASH_STYLE          1
 789 #define FIND_BUCKET_FOR_REHASH          0
 790 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 791 #include "CFBasicHashFindBucket.m"
 792
 793 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Linear_NoCollision
 794 #define FIND_BUCKET_HASH_STYLE          1
 795 #define FIND_BUCKET_FOR_REHASH          1
 796 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 797 #include "CFBasicHashFindBucket.m"
 798
 799 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Linear_Indirect
 800 #define FIND_BUCKET_HASH_STYLE          1
 801 #define FIND_BUCKET_FOR_REHASH          0
 802 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 803 #include "CFBasicHashFindBucket.m"
 804
 805 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Linear_Indirect_NoCollision
 806 #define FIND_BUCKET_HASH_STYLE          1
 807 #define FIND_BUCKET_FOR_REHASH          1
 808 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 809 #include "CFBasicHashFindBucket.m"
 810
 811 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Double
 812 #define FIND_BUCKET_HASH_STYLE          2
 813 #define FIND_BUCKET_FOR_REHASH          0
 814 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 815 #include "CFBasicHashFindBucket.m"
 816
 817 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Double_NoCollision
 818 #define FIND_BUCKET_HASH_STYLE          2
 819 #define FIND_BUCKET_FOR_REHASH          1
 820 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 821 #include "CFBasicHashFindBucket.m"
 822
 823 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Double_Indirect
 824 #define FIND_BUCKET_HASH_STYLE          2
 825 #define FIND_BUCKET_FOR_REHASH          0
 826 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 827 #include "CFBasicHashFindBucket.m"
 828
 829 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Double_Indirect_NoCollision
 830 #define FIND_BUCKET_HASH_STYLE          2
 831 #define FIND_BUCKET_FOR_REHASH          1
 832 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 833 #include "CFBasicHashFindBucket.m"
 834
 835 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Exponential
 836 #define FIND_BUCKET_HASH_STYLE          3
 837 #define FIND_BUCKET_FOR_REHASH          0
 838 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 839 #include "CFBasicHashFindBucket.m"
 840
 841 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Exponential_NoCollision
 842 #define FIND_BUCKET_HASH_STYLE          3
 843 #define FIND_BUCKET_FOR_REHASH          1
 844 #define FIND_BUCKET_FOR_INDIRECT_KEY    0
 845 #include "CFBasicHashFindBucket.m"
 846
 847 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Exponential_Indirect
 848 #define FIND_BUCKET_HASH_STYLE          3
 849 #define FIND_BUCKET_FOR_REHASH          0
 850 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 851 #include "CFBasicHashFindBucket.m"
 852
 853 #define FIND_BUCKET_NAME                ___CFBasicHashFindBucket_Exponential_Indirect_NoCollision
 854 #define FIND_BUCKET_HASH_STYLE          3
 855 #define FIND_BUCKET_FOR_REHASH          1
 856 #define FIND_BUCKET_FOR_INDIRECT_KEY    1
 857 #include "CFBasicHashFindBucket.m"
 858
 859
 860 CF_INLINE CFBasicHashBucket __CFBasicHashFindBucket(CFConstBasicHashRef ht, uintptr_t stack_key) {
 861     if (0 == ht->bits.num_buckets_idx) {
 862         CFBasicHashBucket result = {kCFNotFound, 0UL, 0UL, 0};
 863         return result;
 864     }
 865     if (ht->bits.indirect_keys) {
 866         switch (ht->bits.hash_style) {
 867         case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear_Indirect(ht, stack_key);
 868         case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double_Indirect(ht, stack_key);
 869         case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential_Indirect(ht, stack_key);
 870         }
 871     } else {
 872         switch (ht->bits.hash_style) {
 873         case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear(ht, stack_key);
 874         case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double(ht, stack_key);
 875         case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential(ht, stack_key);
 876         }
 877     }
 878     HALT;
 879     CFBasicHashBucket result = {kCFNotFound, 0UL, 0UL, 0};
 880     return result;
 881 }
 882
 883 CF_INLINE CFIndex __CFBasicHashFindBucket_NoCollision(CFConstBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash) {
 884     if (0 == ht->bits.num_buckets_idx) {
 885         return kCFNotFound;
 886     }
 887     if (ht->bits.indirect_keys) {
 888         switch (ht->bits.hash_style) {
 889         case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear_Indirect_NoCollision(ht, stack_key, key_hash);
 890         case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double_Indirect_NoCollision(ht, stack_key, key_hash);
 891         case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential_Indirect_NoCollision(ht, stack_key, key_hash);
 892         }
 893     } else {
 894         switch (ht->bits.hash_style) {
 895         case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear_NoCollision(ht, stack_key, key_hash);
 896         case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double_NoCollision(ht, stack_key, key_hash);
 897         case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential_NoCollision(ht, stack_key, key_hash);
 898         }
 899     }
 900     HALT;
 901     return kCFNotFound;
 902 }
 903
 904 CF_PRIVATE CFBasicHashBucket CFBasicHashFindBucket(CFConstBasicHashRef ht, uintptr_t stack_key) {
 905     if (__CFBasicHashSubABZero == stack_key || __CFBasicHashSubABOne == stack_key) {
 906         CFBasicHashBucket result = {kCFNotFound, 0UL, 0UL, 0};
 907         return result;
 908     }
 909     return __CFBasicHashFindBucket(ht, stack_key);
 910 }
 911
 912 CF_PRIVATE void CFBasicHashSuppressRC(CFBasicHashRef ht) {
 913     ht->bits.null_rc = 1;
 914 }
 915
 916 CF_PRIVATE void CFBasicHashUnsuppressRC(CFBasicHashRef ht) {
 917     ht->bits.null_rc = 0;
 918 }
 919
 920 CF_PRIVATE CFOptionFlags CFBasicHashGetFlags(CFConstBasicHashRef ht) {
 921     CFOptionFlags flags = (ht->bits.hash_style << 13);
 922     if (CFBasicHashHasStrongValues(ht)) flags |= kCFBasicHashStrongValues;
 923     if (CFBasicHashHasStrongKeys(ht)) flags |= kCFBasicHashStrongKeys;
 924     if (ht->bits.fast_grow) flags |= kCFBasicHashAggressiveGrowth;
 925     if (ht->bits.keys_offset) flags |= kCFBasicHashHasKeys;
 926     if (ht->bits.counts_offset) flags |= kCFBasicHashHasCounts;
 927     if (__CFBasicHashHasHashCache(ht)) flags |= kCFBasicHashHasHashCache;
 928     return flags;
 929 }
 930
 931 CF_PRIVATE CFIndex CFBasicHashGetCount(CFConstBasicHashRef ht) {
 932     if (ht->bits.counts_offset) {
 933         CFIndex total = 0L;
 934         CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 935         for (CFIndex idx = 0; idx < cnt; idx++) {
 936             total += __CFBasicHashGetSlotCount(ht, idx);
 937         }
 938         return total;
 939     }
 940     return (CFIndex)ht->bits.used_buckets;
 941 }
 942
 943 CF_PRIVATE CFIndex CFBasicHashGetCountOfKey(CFConstBasicHashRef ht, uintptr_t stack_key) {
 944     if (__CFBasicHashSubABZero == stack_key || __CFBasicHashSubABOne == stack_key) {
 945         return 0L;
 946     }
 947     if (0L == ht->bits.used_buckets) {
 948         return 0L;
 949     }
 950     return __CFBasicHashFindBucket(ht, stack_key).count;
 951 }
 952
 953 CF_PRIVATE CFIndex CFBasicHashGetCountOfValue(CFConstBasicHashRef ht, uintptr_t stack_value) {
 954     if (__CFBasicHashSubABZero == stack_value) {
 955         return 0L;
 956     }
 957     if (0L == ht->bits.used_buckets) {
 958         return 0L;
 959     }
 960     if (!(ht->bits.keys_offset)) {
 961         return __CFBasicHashFindBucket(ht, stack_value).count;
 962     }
 963     __block CFIndex total = 0L;
 964     CFBasicHashApply(ht, ^(CFBasicHashBucket bkt) {
 965             if ((stack_value == bkt.weak_value) || __CFBasicHashTestEqualValue(ht, bkt.weak_value, stack_value)) total += bkt.count;
 966             return (Boolean)true;
 967         });
 968     return total;
 969 }
 970
 971 CF_PRIVATE Boolean CFBasicHashesAreEqual(CFConstBasicHashRef ht1, CFConstBasicHashRef ht2) {
 972     CFIndex cnt1 = CFBasicHashGetCount(ht1);
 973     if (cnt1 != CFBasicHashGetCount(ht2)) return false;
 974     if (0 == cnt1) return true;
 975     __block Boolean equal = true;
 976     CFBasicHashApply(ht1, ^(CFBasicHashBucket bkt1) {
 977             CFBasicHashBucket bkt2 = __CFBasicHashFindBucket(ht2, bkt1.weak_key);
 978             if (bkt1.count != bkt2.count) {
 979                 equal = false;
 980                 return (Boolean)false;
 981             }
 982             if ((ht1->bits.keys_offset) && (bkt1.weak_value != bkt2.weak_value) && !__CFBasicHashTestEqualValue(ht1, bkt1.weak_value, bkt2.weak_value)) {
 983                 equal = false;
 984                 return (Boolean)false;
 985             }
 986             return (Boolean)true;
 987         });
 988     return equal;
 989 }
 990
 991 CF_PRIVATE void CFBasicHashApply(CFConstBasicHashRef ht, Boolean (^block)(CFBasicHashBucket)) {
 992     CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
 993     for (CFIndex idx = 0; 0 < used && idx < cnt; idx++) {
 994         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
 995         if (0 < bkt.count) {
 996             if (!block(bkt)) {
 997                 return;
 998             }
 999             used--;
1000         }
1001     }
1002 }
1003
1004 CF_PRIVATE void CFBasicHashApplyIndexed(CFConstBasicHashRef ht, CFRange range, Boolean (^block)(CFBasicHashBucket)) {
1005     if (range.length < 0) HALT;
1006     if (range.length == 0) return;
1007     CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1008     if (cnt < range.location + range.length) HALT;
1009     for (CFIndex idx = 0; idx < range.length; idx++) {
1010         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, range.location + idx);
1011         if (0 < bkt.count) {
1012             if (!block(bkt)) {
1013                 return;
1014             }
1015         }
1016     }
1017 }
1018
1019 CF_PRIVATE void CFBasicHashGetElements(CFConstBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_keys) {
1020     CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1021     CFIndex offset = 0;
1022     for (CFIndex idx = 0; 0 < used && idx < cnt && offset < bufferslen; idx++) {
1023         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
1024         if (0 < bkt.count) {
1025             used--;
1026             for (CFIndex cnt = bkt.count; cnt-- && offset < bufferslen;) {
1027                 if (weak_values) { weak_values[offset] = bkt.weak_value; }
1028                 if (weak_keys) { weak_keys[offset] = bkt.weak_key; }
1029                 offset++;
1030             }
1031         }
1032     }
1033 }
1034
1035 CF_PRIVATE unsigned long __CFBasicHashFastEnumeration(CFConstBasicHashRef ht, struct __objcFastEnumerationStateEquivalent2 *state, void *stackbuffer, unsigned long count) {
1036     /* copy as many as count items over */
1037     if (0 == state->state) {        /* first time */
1038         state->mutationsPtr = (unsigned long *)&ht->bits;
1039     }
1040     state->itemsPtr = (unsigned long *)stackbuffer;
1041     CFIndex cntx = 0;
1042     CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1043     for (CFIndex idx = (CFIndex)state->state; 0 < used && idx < cnt && cntx < (CFIndex)count; idx++) {
1044         CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
1045         if (0 < bkt.count) {
1046             state->itemsPtr[cntx++] = (unsigned long)bkt.weak_key;
1047             used--;
1048         }
1049         state->state++;
1050     }
1051     return cntx;
1052 }
1053
1054 #if ENABLE_MEMORY_COUNTERS
1055 static volatile int64_t __CFBasicHashTotalCount = 0ULL;
1056 static volatile int64_t __CFBasicHashTotalSize = 0ULL;
1057 static volatile int64_t __CFBasicHashPeakCount = 0ULL;
1058 static volatile int64_t __CFBasicHashPeakSize = 0ULL;
1059 static volatile int32_t __CFBasicHashSizes[64] = {0};
1060 #endif
1061
1062 static void __CFBasicHashDrain(CFBasicHashRef ht, Boolean forFinalization) {
1063 #if ENABLE_MEMORY_COUNTERS
1064     OSAtomicAdd64Barrier(-1 * (int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1065 #endif
1066
1067     CFIndex old_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1068
1069     CFAllocatorRef allocator = CFGetAllocator(ht);
1070     Boolean nullify = (!forFinalization || !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
1071
1072     CFBasicHashValue *old_values = NULL, *old_keys = NULL;
1073     void *old_counts = NULL;
1074     uintptr_t *old_hashes = NULL;
1075
1076     old_values = __CFBasicHashGetValues(ht);
1077     if (nullify) __CFBasicHashSetValues(ht, NULL);
1078     if (ht->bits.keys_offset) {
1079         old_keys = __CFBasicHashGetKeys(ht);
1080         if (nullify) __CFBasicHashSetKeys(ht, NULL);
1081     }
1082     if (ht->bits.counts_offset) {
1083         old_counts = __CFBasicHashGetCounts(ht);
1084         if (nullify) __CFBasicHashSetCounts(ht, NULL);
1085     }
1086     if (__CFBasicHashHasHashCache(ht)) {
1087         old_hashes = __CFBasicHashGetHashes(ht);
1088         if (nullify) __CFBasicHashSetHashes(ht, NULL);
1089     }
1090
1091     if (nullify) {
1092         ht->bits.mutations++;
1093         ht->bits.num_buckets_idx = 0;
1094         ht->bits.used_buckets = 0;
1095         ht->bits.deleted = 0;
1096     }
1097
1098         for (CFIndex idx = 0; idx < old_num_buckets; idx++) {
1099             uintptr_t stack_value = old_values[idx].neutral;
1100             if (stack_value != 0UL && stack_value != ~0UL) {
1101                 uintptr_t old_value = stack_value;
1102                 if (__CFBasicHashSubABZero == old_value) old_value = 0UL;
1103                 if (__CFBasicHashSubABOne == old_value) old_value = ~0UL;
1104                 __CFBasicHashEjectValue(ht, old_value);
1105                 if (old_keys) {
1106                     uintptr_t old_key = old_keys[idx].neutral;
1107                     if (__CFBasicHashSubABZero == old_key) old_key = 0UL;
1108                     if (__CFBasicHashSubABOne == old_key) old_key = ~0UL;
1109                     __CFBasicHashEjectKey(ht, old_key);
1110                 }
1111             }
1112         }
1113
1114     if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
1115         CFAllocatorDeallocate(allocator, old_values);
1116         CFAllocatorDeallocate(allocator, old_keys);
1117         CFAllocatorDeallocate(allocator, old_counts);
1118         CFAllocatorDeallocate(allocator, old_hashes);
1119     }
1120
1121 #if ENABLE_MEMORY_COUNTERS
1122     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1123     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1124 #endif
1125 }
1126
1127 static void __CFBasicHashRehash(CFBasicHashRef ht, CFIndex newItemCount) {
1128 #if ENABLE_MEMORY_COUNTERS
1129     OSAtomicAdd64Barrier(-1 * (int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1130     OSAtomicAdd32Barrier(-1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1131 #endif
1132
1133     if (COCOA_HASHTABLE_REHASH_START_ENABLED()) COCOA_HASHTABLE_REHASH_START(ht, CFBasicHashGetNumBuckets(ht), CFBasicHashGetSize(ht, true));
1134
1135     CFIndex new_num_buckets_idx = ht->bits.num_buckets_idx;
1136     if (0 != newItemCount) {
1137         if (newItemCount < 0) newItemCount = 0;
1138         CFIndex new_capacity_req = ht->bits.used_buckets + newItemCount;
1139         new_num_buckets_idx = __CFBasicHashGetNumBucketsIndexForCapacity(ht, new_capacity_req);
1140         if (1 == newItemCount && ht->bits.fast_grow) {
1141             new_num_buckets_idx++;
1142         }
1143     }
1144
1145     CFIndex new_num_buckets = __CFBasicHashTableSizes[new_num_buckets_idx];
1146     CFIndex old_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1147
1148     CFBasicHashValue *new_values = NULL, *new_keys = NULL;
1149     void *new_counts = NULL;
1150     uintptr_t *new_hashes = NULL;
1151
1152     if (0 < new_num_buckets) {
1153         new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), CFBasicHashHasStrongValues(ht), 0);
1154         if (!new_values) HALT;
1155         __SetLastAllocationEventName(new_values, "CFBasicHash (value-store)");
1156         memset(new_values, 0, new_num_buckets * sizeof(CFBasicHashValue));
1157         if (ht->bits.keys_offset) {
1158             new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), CFBasicHashHasStrongKeys(ht), 0);
1159             if (!new_keys) HALT;
1160             __SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)");
1161             memset(new_keys, 0, new_num_buckets * sizeof(CFBasicHashValue));
1162         }
1163         if (ht->bits.counts_offset) {
1164             new_counts = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, (1 << ht->bits.counts_width), false, false);
1165             if (!new_counts) HALT;
1166             __SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)");
1167             memset(new_counts, 0, new_num_buckets * (1 << ht->bits.counts_width));
1168         }
1169         if (__CFBasicHashHasHashCache(ht)) {
1170             new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false, false);
1171             if (!new_hashes) HALT;
1172             __SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)");
1173             memset(new_hashes, 0, new_num_buckets * sizeof(uintptr_t));
1174         }
1175     }
1176
1177     ht->bits.num_buckets_idx = new_num_buckets_idx;
1178     ht->bits.deleted = 0;
1179
1180     CFBasicHashValue *old_values = NULL, *old_keys = NULL;
1181     void *old_counts = NULL;
1182     uintptr_t *old_hashes = NULL;
1183
1184     old_values = __CFBasicHashGetValues(ht);
1185     __CFBasicHashSetValues(ht, new_values);
1186     if (ht->bits.keys_offset) {
1187         old_keys = __CFBasicHashGetKeys(ht);
1188         __CFBasicHashSetKeys(ht, new_keys);
1189     }
1190     if (ht->bits.counts_offset) {
1191         old_counts = __CFBasicHashGetCounts(ht);
1192         __CFBasicHashSetCounts(ht, new_counts);
1193     }
1194     if (__CFBasicHashHasHashCache(ht)) {
1195         old_hashes = __CFBasicHashGetHashes(ht);
1196         __CFBasicHashSetHashes(ht, new_hashes);
1197     }
1198
1199     if (0 < old_num_buckets) {
1200         for (CFIndex idx = 0; idx < old_num_buckets; idx++) {
1201             uintptr_t stack_value = old_values[idx].neutral;
1202             if (stack_value != 0UL && stack_value != ~0UL) {
1203                 if (__CFBasicHashSubABZero == stack_value) stack_value = 0UL;
1204                 if (__CFBasicHashSubABOne == stack_value) stack_value = ~0UL;
1205                 uintptr_t stack_key = stack_value;
1206                 if (ht->bits.keys_offset) {
1207                     stack_key = old_keys[idx].neutral;
1208                     if (__CFBasicHashSubABZero == stack_key) stack_key = 0UL;
1209                     if (__CFBasicHashSubABOne == stack_key) stack_key = ~0UL;
1210                 }
1211                 if (ht->bits.indirect_keys) {
1212                     stack_key = __CFBasicHashGetIndirectKey(ht, stack_value);
1213                 }
1214                 CFIndex bkt_idx = __CFBasicHashFindBucket_NoCollision(ht, stack_key, old_hashes ? old_hashes[idx] : 0UL);
1215                 __CFBasicHashSetValue(ht, bkt_idx, stack_value, false, false);
1216                 if (old_keys) {
1217                     __CFBasicHashSetKey(ht, bkt_idx, stack_key, false, false);
1218                 }
1219                 if (old_counts) {
1220                     switch (ht->bits.counts_width) {
1221                     case 0: ((uint8_t *)new_counts)[bkt_idx] = ((uint8_t *)old_counts)[idx]; break;
1222                     case 1: ((uint16_t *)new_counts)[bkt_idx] = ((uint16_t *)old_counts)[idx]; break;
1223                     case 2: ((uint32_t *)new_counts)[bkt_idx] = ((uint32_t *)old_counts)[idx]; break;
1224                     case 3: ((uint64_t *)new_counts)[bkt_idx] = ((uint64_t *)old_counts)[idx]; break;
1225                     }
1226                 }
1227                 if (old_hashes) {
1228                     new_hashes[bkt_idx] = old_hashes[idx];
1229                 }
1230             }
1231         }
1232     }
1233
1234     CFAllocatorRef allocator = CFGetAllocator(ht);
1235     if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
1236         CFAllocatorDeallocate(allocator, old_values);
1237         CFAllocatorDeallocate(allocator, old_keys);
1238         CFAllocatorDeallocate(allocator, old_counts);
1239         CFAllocatorDeallocate(allocator, old_hashes);
1240     }
1241
1242     if (COCOA_HASHTABLE_REHASH_END_ENABLED()) COCOA_HASHTABLE_REHASH_END(ht, CFBasicHashGetNumBuckets(ht), CFBasicHashGetSize(ht, true));
1243
1244 #if ENABLE_MEMORY_COUNTERS
1245     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), &__CFBasicHashTotalSize);
1246     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1247     OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1248 #endif
1249 }
1250
1251 CF_PRIVATE void CFBasicHashSetCapacity(CFBasicHashRef ht, CFIndex capacity) {
1252     if (!CFBasicHashIsMutable(ht)) HALT;
1253     if (ht->bits.used_buckets < capacity) {
1254         ht->bits.mutations++;
1255         __CFBasicHashRehash(ht, capacity - ht->bits.used_buckets);
1256     }
1257 }
1258
1259 static void __CFBasicHashAddValue(CFBasicHashRef ht, CFIndex bkt_idx, uintptr_t stack_key, uintptr_t stack_value) {
1260     ht->bits.mutations++;
1261     if (CFBasicHashGetCapacity(ht) < ht->bits.used_buckets + 1) {
1262         __CFBasicHashRehash(ht, 1);
1263         bkt_idx = __CFBasicHashFindBucket_NoCollision(ht, stack_key, 0);
1264     } else if (__CFBasicHashIsDeleted(ht, bkt_idx)) {
1265         ht->bits.deleted--;
1266     }
1267     uintptr_t key_hash = 0;
1268     if (__CFBasicHashHasHashCache(ht)) {
1269         key_hash = __CFBasicHashHashKey(ht, stack_key);
1270     }
1271     stack_value = __CFBasicHashImportValue(ht, stack_value);
1272     if (ht->bits.keys_offset) {
1273         stack_key = __CFBasicHashImportKey(ht, stack_key);
1274     }
1275     __CFBasicHashSetValue(ht, bkt_idx, stack_value, false, false);
1276     if (ht->bits.keys_offset) {
1277         __CFBasicHashSetKey(ht, bkt_idx, stack_key, false, false);
1278     }
1279     if (ht->bits.counts_offset) {
1280         __CFBasicHashIncSlotCount(ht, bkt_idx);
1281     }
1282     if (__CFBasicHashHasHashCache(ht)) {
1283         __CFBasicHashGetHashes(ht)[bkt_idx] = key_hash;
1284     }
1285     ht->bits.used_buckets++;
1286 }
1287
1288 static void __CFBasicHashReplaceValue(CFBasicHashRef ht, CFIndex bkt_idx, uintptr_t stack_key, uintptr_t stack_value) {
1289     ht->bits.mutations++;
1290     stack_value = __CFBasicHashImportValue(ht, stack_value);
1291     if (ht->bits.keys_offset) {
1292         stack_key = __CFBasicHashImportKey(ht, stack_key);
1293     }
1294     __CFBasicHashSetValue(ht, bkt_idx, stack_value, false, false);
1295     if (ht->bits.keys_offset) {
1296         __CFBasicHashSetKey(ht, bkt_idx, stack_key, false, false);
1297     }
1298 }
1299
1300 static void __CFBasicHashRemoveValue(CFBasicHashRef ht, CFIndex bkt_idx) {
1301     ht->bits.mutations++;
1302     __CFBasicHashSetValue(ht, bkt_idx, ~0UL, false, true);
1303     if (ht->bits.keys_offset) {
1304         __CFBasicHashSetKey(ht, bkt_idx, ~0UL, false, true);
1305     }
1306     if (ht->bits.counts_offset) {
1307         __CFBasicHashDecSlotCount(ht, bkt_idx);
1308     }
1309     if (__CFBasicHashHasHashCache(ht)) {
1310         __CFBasicHashGetHashes(ht)[bkt_idx] = 0;
1311     }
1312     ht->bits.used_buckets--;
1313     ht->bits.deleted++;
1314     Boolean do_shrink = false;
1315     if (ht->bits.fast_grow) { // == slow shrink
1316         do_shrink = (5 < ht->bits.num_buckets_idx && ht->bits.used_buckets < __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx - 5));
1317     } else {
1318         do_shrink = (2 < ht->bits.num_buckets_idx && ht->bits.used_buckets < __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx - 2));
1319     }
1320     if (do_shrink) {
1321         __CFBasicHashRehash(ht, -1);
1322         return;
1323     }
1324     do_shrink = (0 == ht->bits.deleted); // .deleted roll-over
1325     CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1326     do_shrink = do_shrink || ((20 <= num_buckets) && (num_buckets / 4 <= ht->bits.deleted));
1327     if (do_shrink) {
1328         __CFBasicHashRehash(ht, 0);
1329     }
1330 }
1331
1332 CF_PRIVATE Boolean CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
1333     if (!CFBasicHashIsMutable(ht)) HALT;
1334     if (__CFBasicHashSubABZero == stack_key) HALT;
1335     if (__CFBasicHashSubABOne == stack_key) HALT;
1336     if (__CFBasicHashSubABZero == stack_value) HALT;
1337     if (__CFBasicHashSubABOne == stack_value) HALT;
1338     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1339     if (0 < bkt.count) {
1340         ht->bits.mutations++;
1341         if (ht->bits.counts_offset && bkt.count < LONG_MAX) { // if not yet as large as a CFIndex can be... otherwise clamp and do nothing
1342             __CFBasicHashIncSlotCount(ht, bkt.idx);
1343             return true;
1344         }
1345     } else {
1346         __CFBasicHashAddValue(ht, bkt.idx, stack_key, stack_value);
1347         return true;
1348     }
1349     return false;
1350 }
1351
1352 CF_PRIVATE void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
1353     if (!CFBasicHashIsMutable(ht)) HALT;
1354     if (__CFBasicHashSubABZero == stack_key) HALT;
1355     if (__CFBasicHashSubABOne == stack_key) HALT;
1356     if (__CFBasicHashSubABZero == stack_value) HALT;
1357     if (__CFBasicHashSubABOne == stack_value) HALT;
1358     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1359     if (0 < bkt.count) {
1360         __CFBasicHashReplaceValue(ht, bkt.idx, stack_key, stack_value);
1361     }
1362 }
1363
1364 CF_PRIVATE void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
1365     if (!CFBasicHashIsMutable(ht)) HALT;
1366     if (__CFBasicHashSubABZero == stack_key) HALT;
1367     if (__CFBasicHashSubABOne == stack_key) HALT;
1368     if (__CFBasicHashSubABZero == stack_value) HALT;
1369     if (__CFBasicHashSubABOne == stack_value) HALT;
1370     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1371     if (0 < bkt.count) {
1372         __CFBasicHashReplaceValue(ht, bkt.idx, stack_key, stack_value);
1373     } else {
1374         __CFBasicHashAddValue(ht, bkt.idx, stack_key, stack_value);
1375     }
1376 }
1377
1378 CF_PRIVATE CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key) {
1379     if (!CFBasicHashIsMutable(ht)) HALT;
1380     if (__CFBasicHashSubABZero == stack_key || __CFBasicHashSubABOne == stack_key) return 0;
1381     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1382     if (1 < bkt.count) {
1383         ht->bits.mutations++;
1384         if (ht->bits.counts_offset && bkt.count < LONG_MAX) { // if not as large as a CFIndex can be... otherwise clamp and do nothing
1385             __CFBasicHashDecSlotCount(ht, bkt.idx);
1386         }
1387     } else if (0 < bkt.count) {
1388         __CFBasicHashRemoveValue(ht, bkt.idx);
1389     }
1390     return bkt.count;
1391 }
1392
1393 CF_PRIVATE CFIndex CFBasicHashRemoveValueAtIndex(CFBasicHashRef ht, CFIndex idx) {
1394     if (!CFBasicHashIsMutable(ht)) HALT;
1395     CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx);
1396     if (1 < bkt.count) {
1397         ht->bits.mutations++;
1398         if (ht->bits.counts_offset && bkt.count < LONG_MAX) { // if not as large as a CFIndex can be... otherwise clamp and do nothing
1399             __CFBasicHashDecSlotCount(ht, bkt.idx);
1400         }
1401     } else if (0 < bkt.count) {
1402         __CFBasicHashRemoveValue(ht, bkt.idx);
1403     }
1404     return bkt.count;
1405 }
1406
1407 CF_PRIVATE void CFBasicHashRemoveAllValues(CFBasicHashRef ht) {
1408     if (!CFBasicHashIsMutable(ht)) HALT;
1409     if (0 == ht->bits.num_buckets_idx) return;
1410     __CFBasicHashDrain(ht, false);
1411 }
1412
1413 CF_PRIVATE Boolean CFBasicHashAddIntValueAndInc(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t int_value) {
1414     if (!CFBasicHashIsMutable(ht)) HALT;
1415     if (__CFBasicHashSubABZero == stack_key) HALT;
1416     if (__CFBasicHashSubABOne == stack_key) HALT;
1417     if (__CFBasicHashSubABZero == int_value) HALT;
1418     if (__CFBasicHashSubABOne == int_value) HALT;
1419     CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
1420     if (0 < bkt.count) {
1421         ht->bits.mutations++;
1422     } else {
1423         // must rehash before renumbering
1424         if (CFBasicHashGetCapacity(ht) < ht->bits.used_buckets + 1) {
1425             __CFBasicHashRehash(ht, 1);
1426             bkt.idx = __CFBasicHashFindBucket_NoCollision(ht, stack_key, 0);
1427         }
1428         CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1429         for (CFIndex idx = 0; idx < cnt; idx++) {
1430             if (!__CFBasicHashIsEmptyOrDeleted(ht, idx)) {
1431                 uintptr_t stack_value = __CFBasicHashGetValue(ht, idx);
1432                 if (int_value <= stack_value) {
1433                     stack_value++;
1434                     __CFBasicHashSetValue(ht, idx, stack_value, true, false);
1435                     ht->bits.mutations++;
1436                 }
1437             }
1438         }
1439         __CFBasicHashAddValue(ht, bkt.idx, stack_key, int_value);
1440         return true;
1441     }
1442     return false;
1443 }
1444
1445 CF_PRIVATE void CFBasicHashRemoveIntValueAndDec(CFBasicHashRef ht, uintptr_t int_value) {
1446     if (!CFBasicHashIsMutable(ht)) HALT;
1447     if (__CFBasicHashSubABZero == int_value) HALT;
1448     if (__CFBasicHashSubABOne == int_value) HALT;
1449     uintptr_t bkt_idx = ~0UL;
1450     CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1451     for (CFIndex idx = 0; idx < cnt; idx++) {
1452         if (!__CFBasicHashIsEmptyOrDeleted(ht, idx)) {
1453             uintptr_t stack_value = __CFBasicHashGetValue(ht, idx);
1454             if (int_value == stack_value) {
1455                 bkt_idx = idx;
1456             }
1457             if (int_value < stack_value) {
1458                 stack_value--;
1459                 __CFBasicHashSetValue(ht, idx, stack_value, true, false);
1460                 ht->bits.mutations++;
1461             }
1462         }
1463     }
1464     __CFBasicHashRemoveValue(ht, bkt_idx);
1465 }
1466
1467 CF_PRIVATE size_t CFBasicHashGetSize(CFConstBasicHashRef ht, Boolean total) {
1468     size_t size = sizeof(struct __CFBasicHash);
1469     if (ht->bits.keys_offset) size += sizeof(CFBasicHashValue *);
1470     if (ht->bits.counts_offset) size += sizeof(void *);
1471     if (__CFBasicHashHasHashCache(ht)) size += sizeof(uintptr_t *);
1472     if (total) {
1473         CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
1474         if (0 < num_buckets) {
1475             size += malloc_size(__CFBasicHashGetValues(ht));
1476             if (ht->bits.keys_offset) size += malloc_size(__CFBasicHashGetKeys(ht));
1477             if (ht->bits.counts_offset) size += malloc_size(__CFBasicHashGetCounts(ht));
1478             if (__CFBasicHashHasHashCache(ht)) size += malloc_size(__CFBasicHashGetHashes(ht));
1479         }
1480     }
1481     return size;
1482 }
1483
1484 CF_PRIVATE CFStringRef CFBasicHashCopyDescription(CFConstBasicHashRef ht, Boolean detailed, CFStringRef prefix, CFStringRef entryPrefix, Boolean describeElements) {
1485     CFMutableStringRef result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
1486     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));
1487     if (detailed) {
1488         const char *cb_type = "custom";
1489         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);
1490         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);
1491         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"));
1492         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));
1493         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));
1494     }
1495     CFStringAppendFormat(result, NULL, CFSTR("%@entries =>\n"), prefix);
1496     CFBasicHashApply(ht, ^(CFBasicHashBucket bkt) {
1497             CFStringRef vDesc = NULL, kDesc = NULL;
1498             if (!describeElements) {
1499                 vDesc = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)bkt.weak_value);
1500                 if (ht->bits.keys_offset) {
1501                     kDesc = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)bkt.weak_key);
1502                 }
1503             } else {
1504                 vDesc = __CFBasicHashDescValue(ht, bkt.weak_value);
1505                 if (ht->bits.keys_offset) {
1506                     kDesc = __CFBasicHashDescKey(ht, bkt.weak_key);
1507                 }
1508             }
1509             if (ht->bits.keys_offset && ht->bits.counts_offset) {
1510                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ = %@ (%ld)\n"), entryPrefix, bkt.idx, kDesc, vDesc, bkt.count);
1511             } else if (ht->bits.keys_offset) {
1512                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ = %@\n"), entryPrefix, bkt.idx, kDesc, vDesc);
1513             } else if (ht->bits.counts_offset) {
1514                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ (%ld)\n"), entryPrefix, bkt.idx, vDesc, bkt.count);
1515             } else {
1516                 CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@\n"), entryPrefix, bkt.idx, vDesc);
1517             }
1518             if (kDesc) CFRelease(kDesc);
1519             if (vDesc) CFRelease(vDesc);
1520             return (Boolean)true;
1521         });
1522     CFStringAppendFormat(result, NULL, CFSTR("%@}\n"), prefix);
1523     return result;
1524 }
1525
1526 CF_PRIVATE void CFBasicHashShow(CFConstBasicHashRef ht) {
1527     CFStringRef str = CFBasicHashCopyDescription(ht, true, CFSTR(""), CFSTR("\t"), false);
1528     CFShow(str);
1529     CFRelease(str);
1530 }
1531
1532 CF_PRIVATE Boolean __CFBasicHashEqual(CFTypeRef cf1, CFTypeRef cf2) {
1533     CFBasicHashRef ht1 = (CFBasicHashRef)cf1;
1534     CFBasicHashRef ht2 = (CFBasicHashRef)cf2;
1535 //#warning this used to require that the key and value equal callbacks were pointer identical
1536     return CFBasicHashesAreEqual(ht1, ht2);
1537 }
1538
1539 CF_PRIVATE CFHashCode __CFBasicHashHash(CFTypeRef cf) {
1540     CFBasicHashRef ht = (CFBasicHashRef)cf;
1541     return CFBasicHashGetCount(ht);
1542 }
1543
1544 CF_PRIVATE CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf) {
1545     CFBasicHashRef ht = (CFBasicHashRef)cf;
1546     CFStringRef desc = CFBasicHashCopyDescription(ht, false, CFSTR(""), CFSTR("\t"), true);
1547     CFStringRef result = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<CFBasicHash %p [%p]>%@"), cf, CFGetAllocator(cf), desc);
1548     CFRelease(desc);
1549     return result;
1550 }
1551
1552 CF_PRIVATE void __CFBasicHashDeallocate(CFTypeRef cf) {
1553     CFBasicHashRef ht = (CFBasicHashRef)cf;
1554     if (ht->bits.finalized) HALT;
1555     ht->bits.finalized = 1;
1556     __CFBasicHashDrain(ht, true);
1557 #if ENABLE_MEMORY_COUNTERS
1558     OSAtomicAdd64Barrier(-1, &__CFBasicHashTotalCount);
1559     OSAtomicAdd32Barrier(-1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1560 #endif
1561 }
1562
1563 static CFTypeID __kCFBasicHashTypeID = _kCFRuntimeNotATypeID;
1564
1565 static const CFRuntimeClass __CFBasicHashClass = {
1566     _kCFRuntimeScannedObject,
1567     "CFBasicHash",
1568     NULL,        // init
1569     NULL,        // copy
1570     __CFBasicHashDeallocate,
1571     __CFBasicHashEqual,
1572     __CFBasicHashHash,
1573     NULL,        //
1574     __CFBasicHashCopyDescription
1575 };
1576
1577 CF_PRIVATE CFTypeID CFBasicHashGetTypeID(void) {
1578     static dispatch_once_t initOnce;
1579     dispatch_once(&initOnce, ^{ __kCFBasicHashTypeID = _CFRuntimeRegisterClass(&__CFBasicHashClass); });
1580     return __kCFBasicHashTypeID;
1581 }
1582
1583 CF_PRIVATE CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb) {
1584     size_t size = sizeof(struct __CFBasicHash) - sizeof(CFRuntimeBase);
1585     if (flags & kCFBasicHashHasKeys) size += sizeof(CFBasicHashValue *); // keys
1586     if (flags & kCFBasicHashHasCounts) size += sizeof(void *); // counts
1587     if (flags & kCFBasicHashHasHashCache) size += sizeof(uintptr_t *); // hashes
1588     CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL);
1589     if (NULL == ht) return NULL;
1590
1591     ht->bits.finalized = 0;
1592     ht->bits.hash_style = (flags >> 13) & 0x3;
1593     ht->bits.fast_grow = (flags & kCFBasicHashAggressiveGrowth) ? 1 : 0;
1594     ht->bits.counts_width = 0;
1595     ht->bits.strong_values = (flags & kCFBasicHashStrongValues) ? 1 : 0;
1596     ht->bits.strong_keys = (flags & kCFBasicHashStrongKeys) ? 1 : 0;
1597     ht->bits.weak_values = (flags & kCFBasicHashWeakValues) ? 1 : 0;
1598     ht->bits.weak_keys = (flags & kCFBasicHashWeakKeys) ? 1 : 0;
1599     ht->bits.int_values = (flags & kCFBasicHashIntegerValues) ? 1 : 0;
1600     ht->bits.int_keys = (flags & kCFBasicHashIntegerKeys) ? 1 : 0;
1601     ht->bits.indirect_keys = (flags & kCFBasicHashIndirectKeys) ? 1 : 0;
1602     ht->bits.num_buckets_idx = 0;
1603     ht->bits.used_buckets = 0;
1604     ht->bits.deleted = 0;
1605     ht->bits.mutations = 1;
1606
1607     if (ht->bits.strong_values && ht->bits.weak_values) HALT;
1608     if (ht->bits.strong_values && ht->bits.int_values) HALT;
1609     if (ht->bits.strong_keys && ht->bits.weak_keys) HALT;
1610     if (ht->bits.strong_keys && ht->bits.int_keys) HALT;
1611     if (ht->bits.weak_values && ht->bits.int_values) HALT;
1612     if (ht->bits.weak_keys && ht->bits.int_keys) HALT;
1613     if (ht->bits.indirect_keys && ht->bits.strong_keys) HALT;
1614     if (ht->bits.indirect_keys && ht->bits.weak_keys) HALT;
1615     if (ht->bits.indirect_keys && ht->bits.int_keys) HALT;
1616
1617     uint64_t offset = 1;
1618     ht->bits.keys_offset = (flags & kCFBasicHashHasKeys) ? offset++ : 0;
1619     ht->bits.counts_offset = (flags & kCFBasicHashHasCounts) ? offset++ : 0;
1620     ht->bits.hashes_offset = (flags & kCFBasicHashHasHashCache) ? offset++ : 0;
1621
1622 #if DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_EMBEDDED_MINI
1623     ht->bits.hashes_offset = 0;
1624     ht->bits.strong_values = 0;
1625     ht->bits.strong_keys = 0;
1626     ht->bits.weak_values = 0;
1627     ht->bits.weak_keys = 0;
1628 #endif
1629
1630     ht->bits.__kret = CFBasicHashGetPtrIndex((void *)cb->retainKey);
1631     ht->bits.__vret = CFBasicHashGetPtrIndex((void *)cb->retainValue);
1632     ht->bits.__krel = CFBasicHashGetPtrIndex((void *)cb->releaseKey);
1633     ht->bits.__vrel = CFBasicHashGetPtrIndex((void *)cb->releaseValue);
1634     ht->bits.__kdes = CFBasicHashGetPtrIndex((void *)cb->copyKeyDescription);
1635     ht->bits.__vdes = CFBasicHashGetPtrIndex((void *)cb->copyValueDescription);
1636     ht->bits.__kequ = CFBasicHashGetPtrIndex((void *)cb->equateKeys);
1637     ht->bits.__vequ = CFBasicHashGetPtrIndex((void *)cb->equateValues);
1638     ht->bits.__khas = CFBasicHashGetPtrIndex((void *)cb->hashKey);
1639     ht->bits.__kget = CFBasicHashGetPtrIndex((void *)cb->getIndirectKey);
1640
1641     for (CFIndex idx = 0; idx < offset; idx++) {
1642         ht->pointers[idx] = NULL;
1643     }
1644
1645 #if ENABLE_MEMORY_COUNTERS
1646     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1647     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1648     int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount);
1649     while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount));
1650     OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1651 #endif
1652
1653     return ht;
1654 }
1655
1656 CF_PRIVATE CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFConstBasicHashRef src_ht) {
1657     size_t size = CFBasicHashGetSize(src_ht, false) - sizeof(CFRuntimeBase);
1658     CFIndex new_num_buckets = __CFBasicHashTableSizes[src_ht->bits.num_buckets_idx];
1659     CFBasicHashValue *new_values = NULL, *new_keys = NULL;
1660     void *new_counts = NULL;
1661     uintptr_t *new_hashes = NULL;
1662
1663     if (0 < new_num_buckets) {
1664         Boolean strongValues = CFBasicHashHasStrongValues(src_ht) && !(kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
1665         Boolean strongKeys = CFBasicHashHasStrongKeys(src_ht) && !(kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
1666         new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, sizeof(CFBasicHashValue), strongValues, 0);
1667         if (!new_values) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1668         __SetLastAllocationEventName(new_values, "CFBasicHash (value-store)");
1669         if (src_ht->bits.keys_offset) {
1670             new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, sizeof(CFBasicHashValue), strongKeys, false);
1671             if (!new_keys) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1672             __SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)");
1673         }
1674         if (src_ht->bits.counts_offset) {
1675             new_counts = (uintptr_t *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, (1 << src_ht->bits.counts_width), false, false);
1676             if (!new_counts) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1677             __SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)");
1678         }
1679         if (__CFBasicHashHasHashCache(src_ht)) {
1680             new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, sizeof(uintptr_t), false, false);
1681             if (!new_hashes) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1682             __SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)");
1683         }
1684     }
1685
1686     CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL);
1687     if (NULL == ht) return NULL; // in this unusual circumstance, leak previously allocated blocks for now
1688
1689     memmove((uint8_t *)ht + sizeof(CFRuntimeBase), (uint8_t *)src_ht + sizeof(CFRuntimeBase), sizeof(ht->bits));
1690     if (kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
1691         ht->bits.strong_values = 0;
1692         ht->bits.strong_keys = 0;
1693         ht->bits.weak_values = 0;
1694         ht->bits.weak_keys = 0;
1695     }
1696     ht->bits.finalized = 0;
1697     ht->bits.mutations = 1;
1698
1699     if (0 == new_num_buckets) {
1700 #if ENABLE_MEMORY_COUNTERS
1701         int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1702         while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1703         int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount);
1704         while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount));
1705         OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1706 #endif
1707         return ht;
1708     }
1709
1710     CFBasicHashValue *old_values = NULL, *old_keys = NULL;
1711     void *old_counts = NULL;
1712     uintptr_t *old_hashes = NULL;
1713
1714     old_values = __CFBasicHashGetValues(src_ht);
1715     if (src_ht->bits.keys_offset) {
1716         old_keys = __CFBasicHashGetKeys(src_ht);
1717     }
1718     if (src_ht->bits.counts_offset) {
1719         old_counts = __CFBasicHashGetCounts(src_ht);
1720     }
1721     if (__CFBasicHashHasHashCache(src_ht)) {
1722         old_hashes = __CFBasicHashGetHashes(src_ht);
1723     }
1724
1725     __CFBasicHashSetValues(ht, new_values);
1726     if (new_keys) {
1727         __CFBasicHashSetKeys(ht, new_keys);
1728     }
1729     if (new_counts) {
1730         __CFBasicHashSetCounts(ht, new_counts);
1731     }
1732     if (new_hashes) {
1733         __CFBasicHashSetHashes(ht, new_hashes);
1734     }
1735
1736     for (CFIndex idx = 0; idx < new_num_buckets; idx++) {
1737         uintptr_t stack_value = old_values[idx].neutral;
1738         if (stack_value != 0UL && stack_value != ~0UL) {
1739             uintptr_t old_value = stack_value;
1740             if (__CFBasicHashSubABZero == old_value) old_value = 0UL;
1741             if (__CFBasicHashSubABOne == old_value) old_value = ~0UL;
1742             __CFBasicHashSetValue(ht, idx, __CFBasicHashImportValue(ht, old_value), true, false);
1743             if (new_keys) {
1744                 uintptr_t old_key = old_keys[idx].neutral;
1745                 if (__CFBasicHashSubABZero == old_key) old_key = 0UL;
1746                 if (__CFBasicHashSubABOne == old_key) old_key = ~0UL;
1747                 __CFBasicHashSetKey(ht, idx, __CFBasicHashImportKey(ht, old_key), true, false);
1748             }
1749         } else {
1750             __CFBasicHashSetValue(ht, idx, stack_value, true, true);
1751             if (new_keys) {
1752                 __CFBasicHashSetKey(ht, idx, stack_value, true, true);
1753             }
1754         }
1755     }
1756     if (new_counts) memmove(new_counts, old_counts, new_num_buckets * (1 << ht->bits.counts_width));
1757     if (new_hashes) memmove(new_hashes, old_hashes, new_num_buckets * sizeof(uintptr_t));
1758
1759 #if ENABLE_MEMORY_COUNTERS
1760     int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize);
1761     while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize));
1762     int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount);
1763     while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount));
1764     OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]);
1765 #endif
1766
1767     return ht;
1768 }
1769
1770