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