CFBasicHash.m

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