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