CFBasicHash.c

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