| /* CFBasicHash.m |
| Copyright (c) 2008-2016, Apple Inc. and the Swift project authors |
| |
| Portions Copyright (c) 2014-2016 Apple Inc. and the Swift project authors |
| Licensed under Apache License v2.0 with Runtime Library Exception |
| See http://swift.org/LICENSE.txt for license information |
| See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| Responsibility: Christopher Kane |
| */ |
| |
| #include "CFBasicHash.h" |
| #include <CoreFoundation/CFRuntime.h> |
| #include <CoreFoundation/CFSet.h> |
| #include <Block.h> |
| #include <math.h> |
| #if __HAS_DISPATCH__ |
| #include <dispatch/dispatch.h> |
| #endif |
| |
| #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED |
| #define __SetLastAllocationEventName(A, B) do { if (__CFOASafe && (A)) __CFSetLastAllocationEventName(A, B); } while (0) |
| #else |
| #define __SetLastAllocationEventName(A, B) do { } while (0) |
| #endif |
| |
| #define __AssignWithWriteBarrier(location, value) do { *location = value; } while (0) |
| |
| #define ENABLE_DTRACE_PROBES 0 |
| #define ENABLE_MEMORY_COUNTERS 0 |
| |
| #if defined(DTRACE_PROBES_DISABLED) && DTRACE_PROBES_DISABLED |
| #undef ENABLE_DTRACE_PROBES |
| #define ENABLE_DTRACE_PROBES 0 |
| #endif |
| |
| /* |
| // dtrace -h -s foo.d |
| // Note: output then changed by casts of the arguments |
| // dtrace macros last generated 2010-09-08 on 10.7 prerelease (11A259) |
| |
| provider Cocoa_HashTable { |
| probe hash_key(unsigned long table, unsigned long key, unsigned long hash); |
| probe test_equal(unsigned long table, unsigned long key1, unsigned long key2); |
| probe probing_start(unsigned long table, unsigned long num_buckets); |
| probe probe_empty(unsigned long table, unsigned long idx); |
| probe probe_deleted(unsigned long table, unsigned long idx); |
| probe probe_valid(unsigned long table, unsigned long idx); |
| probe probing_end(unsigned long table, unsigned long num_probes); |
| probe rehash_start(unsigned long table, unsigned long num_buckets, unsigned long total_size); |
| probe rehash_end(unsigned long table, unsigned long num_buckets, unsigned long total_size); |
| }; |
| |
| #pragma D attributes Unstable/Unstable/Common provider Cocoa_HashTable provider |
| #pragma D attributes Private/Private/Unknown provider Cocoa_HashTable module |
| #pragma D attributes Private/Private/Unknown provider Cocoa_HashTable function |
| #pragma D attributes Unstable/Unstable/Common provider Cocoa_HashTable name |
| #pragma D attributes Unstable/Unstable/Common provider Cocoa_HashTable args |
| */ |
| |
| #if ENABLE_DTRACE_PROBES |
| |
| #define COCOA_HASHTABLE_STABILITY "___dtrace_stability$Cocoa_HashTable$v1$4_4_5_1_1_0_1_1_0_4_4_5_4_4_5" |
| |
| #define COCOA_HASHTABLE_TYPEDEFS "___dtrace_typedefs$Cocoa_HashTable$v2" |
| |
| #define COCOA_HASHTABLE_REHASH_END(arg0, arg1, arg2) \ |
| do { \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \ |
| __dtrace_probe$Cocoa_HashTable$rehash_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \ |
| } while (0) |
| #define COCOA_HASHTABLE_REHASH_END_ENABLED() \ |
| ({ int _r = __dtrace_isenabled$Cocoa_HashTable$rehash_end$v1(); \ |
| __asm__ volatile(""); \ |
| _r; }) |
| #define COCOA_HASHTABLE_REHASH_START(arg0, arg1, arg2) \ |
| do { \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \ |
| __dtrace_probe$Cocoa_HashTable$rehash_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \ |
| } while (0) |
| #define COCOA_HASHTABLE_REHASH_START_ENABLED() \ |
| ({ int _r = __dtrace_isenabled$Cocoa_HashTable$rehash_start$v1(); \ |
| __asm__ volatile(""); \ |
| _r; }) |
| #define COCOA_HASHTABLE_HASH_KEY(arg0, arg1, arg2) \ |
| do { \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \ |
| __dtrace_probe$Cocoa_HashTable$hash_key$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \ |
| } while (0) |
| #define COCOA_HASHTABLE_HASH_KEY_ENABLED() \ |
| ({ int _r = __dtrace_isenabled$Cocoa_HashTable$hash_key$v1(); \ |
| __asm__ volatile(""); \ |
| _r; }) |
| #define COCOA_HASHTABLE_PROBE_DELETED(arg0, arg1) \ |
| do { \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \ |
| __dtrace_probe$Cocoa_HashTable$probe_deleted$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \ |
| } while (0) |
| #define COCOA_HASHTABLE_PROBE_DELETED_ENABLED() \ |
| ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probe_deleted$v1(); \ |
| __asm__ volatile(""); \ |
| _r; }) |
| #define COCOA_HASHTABLE_PROBE_EMPTY(arg0, arg1) \ |
| do { \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \ |
| __dtrace_probe$Cocoa_HashTable$probe_empty$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \ |
| } while (0) |
| #define COCOA_HASHTABLE_PROBE_EMPTY_ENABLED() \ |
| ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probe_empty$v1(); \ |
| __asm__ volatile(""); \ |
| _r; }) |
| #define COCOA_HASHTABLE_PROBE_VALID(arg0, arg1) \ |
| do { \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \ |
| __dtrace_probe$Cocoa_HashTable$probe_valid$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \ |
| } while (0) |
| #define COCOA_HASHTABLE_PROBE_VALID_ENABLED() \ |
| ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probe_valid$v1(); \ |
| __asm__ volatile(""); \ |
| _r; }) |
| #define COCOA_HASHTABLE_PROBING_END(arg0, arg1) \ |
| do { \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \ |
| __dtrace_probe$Cocoa_HashTable$probing_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \ |
| } while (0) |
| #define COCOA_HASHTABLE_PROBING_END_ENABLED() \ |
| ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probing_end$v1(); \ |
| __asm__ volatile(""); \ |
| _r; }) |
| #define COCOA_HASHTABLE_PROBING_START(arg0, arg1) \ |
| do { \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \ |
| __dtrace_probe$Cocoa_HashTable$probing_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1)); \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \ |
| } while (0) |
| #define COCOA_HASHTABLE_PROBING_START_ENABLED() \ |
| ({ int _r = __dtrace_isenabled$Cocoa_HashTable$probing_start$v1(); \ |
| __asm__ volatile(""); \ |
| _r; }) |
| #define COCOA_HASHTABLE_TEST_EQUAL(arg0, arg1, arg2) \ |
| do { \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_TYPEDEFS); \ |
| __dtrace_probe$Cocoa_HashTable$test_equal$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67((unsigned long)(arg0), (unsigned long)(arg1), (unsigned long)(arg2)); \ |
| __asm__ volatile(".reference " COCOA_HASHTABLE_STABILITY); \ |
| } while (0) |
| #define COCOA_HASHTABLE_TEST_EQUAL_ENABLED() \ |
| ({ int _r = __dtrace_isenabled$Cocoa_HashTable$test_equal$v1(); \ |
| __asm__ volatile(""); \ |
| _r; }) |
| |
| extern void __dtrace_probe$Cocoa_HashTable$hash_key$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long); |
| extern int __dtrace_isenabled$Cocoa_HashTable$hash_key$v1(void); |
| extern void __dtrace_probe$Cocoa_HashTable$probe_deleted$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long); |
| extern int __dtrace_isenabled$Cocoa_HashTable$probe_deleted$v1(void); |
| extern void __dtrace_probe$Cocoa_HashTable$probe_empty$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long); |
| extern int __dtrace_isenabled$Cocoa_HashTable$probe_empty$v1(void); |
| extern void __dtrace_probe$Cocoa_HashTable$probe_valid$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long); |
| extern int __dtrace_isenabled$Cocoa_HashTable$probe_valid$v1(void); |
| extern void __dtrace_probe$Cocoa_HashTable$probing_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long); |
| extern int __dtrace_isenabled$Cocoa_HashTable$probing_end$v1(void); |
| extern void __dtrace_probe$Cocoa_HashTable$probing_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long); |
| extern int __dtrace_isenabled$Cocoa_HashTable$probing_start$v1(void); |
| extern void __dtrace_probe$Cocoa_HashTable$rehash_end$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long); |
| extern int __dtrace_isenabled$Cocoa_HashTable$rehash_end$v1(void); |
| extern void __dtrace_probe$Cocoa_HashTable$rehash_start$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long); |
| extern int __dtrace_isenabled$Cocoa_HashTable$rehash_start$v1(void); |
| extern void __dtrace_probe$Cocoa_HashTable$test_equal$v1$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67$756e7369676e6564206c6f6e67(unsigned long, unsigned long, unsigned long); |
| extern int __dtrace_isenabled$Cocoa_HashTable$test_equal$v1(void); |
| |
| #else |
| |
| #define COCOA_HASHTABLE_REHASH_END(arg0, arg1, arg2) do {} while (0) |
| #define COCOA_HASHTABLE_REHASH_END_ENABLED() 0 |
| #define COCOA_HASHTABLE_REHASH_START(arg0, arg1, arg2) do {} while (0) |
| #define COCOA_HASHTABLE_REHASH_START_ENABLED() 0 |
| #define COCOA_HASHTABLE_HASH_KEY(arg0, arg1, arg2) do {} while (0) |
| #define COCOA_HASHTABLE_HASH_KEY_ENABLED() 0 |
| #define COCOA_HASHTABLE_PROBE_DELETED(arg0, arg1) do {} while (0) |
| #define COCOA_HASHTABLE_PROBE_DELETED_ENABLED() 0 |
| #define COCOA_HASHTABLE_PROBE_EMPTY(arg0, arg1) do {} while (0) |
| #define COCOA_HASHTABLE_PROBE_EMPTY_ENABLED() 0 |
| #define COCOA_HASHTABLE_PROBE_VALID(arg0, arg1) do {} while (0) |
| #define COCOA_HASHTABLE_PROBE_VALID_ENABLED() 0 |
| #define COCOA_HASHTABLE_PROBING_END(arg0, arg1) do {} while (0) |
| #define COCOA_HASHTABLE_PROBING_END_ENABLED() 0 |
| #define COCOA_HASHTABLE_PROBING_START(arg0, arg1) do {} while (0) |
| #define COCOA_HASHTABLE_PROBING_START_ENABLED() 0 |
| #define COCOA_HASHTABLE_TEST_EQUAL(arg0, arg1, arg2) do {} while (0) |
| #define COCOA_HASHTABLE_TEST_EQUAL_ENABLED() 0 |
| |
| #endif |
| |
| |
| #if !defined(__LP64__) |
| #define __LP64__ 0 |
| #endif |
| |
| // Prime numbers. Values above 100 have been adjusted up so that the |
| // malloced block size will be just below a multiple of 512; values |
| // above 1200 have been adjusted up to just below a multiple of 4096. |
| static const uintptr_t __CFBasicHashTableSizes[64] = { |
| 0, 3, 7, 13, 23, 41, 71, 127, 191, 251, 383, 631, 1087, 1723, |
| 2803, 4523, 7351, 11959, 19447, 31231, 50683, 81919, 132607, |
| 214519, 346607, 561109, 907759, 1468927, 2376191, 3845119, |
| 6221311, 10066421, 16287743, 26354171, 42641881, 68996069, |
| 111638519, 180634607, 292272623, 472907251, |
| #if __LP64__ |
| 765180413UL, 1238087663UL, 2003267557UL, 3241355263UL, 5244622819UL, |
| #if 0 |
| 8485977589UL, 13730600407UL, 22216578047UL, 35947178479UL, |
| 58163756537UL, 94110934997UL, 152274691561UL, 246385626107UL, |
| 398660317687UL, 645045943807UL, 1043706260983UL, 1688752204787UL, |
| 2732458465769UL, 4421210670577UL, 7153669136377UL, |
| 11574879807461UL, 18728548943849UL, 30303428750843UL |
| #endif |
| #endif |
| }; |
| |
| static const uintptr_t __CFBasicHashTableCapacities[64] = { |
| 0, 3, 6, 11, 19, 32, 52, 85, 118, 155, 237, 390, 672, 1065, |
| 1732, 2795, 4543, 7391, 12019, 19302, 31324, 50629, 81956, |
| 132580, 214215, 346784, 561026, 907847, 1468567, 2376414, |
| 3844982, 6221390, 10066379, 16287773, 26354132, 42641916, |
| 68996399, 111638327, 180634415, 292272755, |
| #if __LP64__ |
| 472907503UL, 765180257UL, 1238087439UL, 2003267722UL, 3241355160UL, |
| #if 0 |
| 5244622578UL, 8485977737UL, 13730600347UL, 22216578100UL, |
| 35947178453UL, 58163756541UL, 94110935011UL, 152274691274UL, |
| 246385626296UL, 398660317578UL, 645045943559UL, 1043706261135UL, |
| 1688752204693UL, 2732458465840UL, 4421210670552UL, |
| 7153669136706UL, 11574879807265UL, 18728548943682UL |
| #endif |
| #endif |
| }; |
| |
| // Primitive roots for the primes above |
| static const uintptr_t __CFBasicHashPrimitiveRoots[64] = { |
| 0, 2, 3, 2, 5, 6, 7, 3, 19, 6, 5, 3, 3, 3, |
| 2, 5, 6, 3, 3, 6, 2, 3, 3, |
| 3, 5, 10, 3, 3, 22, 3, |
| 3, 3, 5, 2, 22, 2, |
| 11, 5, 5, 2, |
| #if __LP64__ |
| 3, 10, 2, 3, 10, |
| 2, 3, 5, 3, |
| 3, 2, 7, 2, |
| 3, 3, 3, 2, |
| 3, 5, 5, |
| 2, 3, 2 |
| #endif |
| }; |
| |
| CF_INLINE void *__CFBasicHashAllocateMemory(CFConstBasicHashRef ht, CFIndex count, CFIndex elem_size, Boolean strong, Boolean compactable) { |
| return CFAllocatorAllocate(CFGetAllocator(ht), count * elem_size, 0); |
| } |
| |
| CF_INLINE void *__CFBasicHashAllocateMemory2(CFAllocatorRef allocator, CFIndex count, CFIndex elem_size, Boolean strong, Boolean compactable) { |
| return CFAllocatorAllocate(allocator, count * elem_size, 0); |
| } |
| |
| #define __CFBasicHashSubABZero 0xa7baadb1 |
| #define __CFBasicHashSubABOne 0xa5baadb9 |
| |
| typedef union { |
| uintptr_t neutral; |
| id strong; |
| id weak; |
| } CFBasicHashValue; |
| |
| struct __CFBasicHash { |
| CFRuntimeBase base; |
| struct { // 192 bits |
| uint16_t mutations; |
| uint16_t hash_style:2; |
| uint16_t keys_offset:1; |
| uint16_t counts_offset:2; |
| uint16_t counts_width:2; |
| uint16_t hashes_offset:2; |
| uint16_t strong_values:1; |
| uint16_t strong_keys:1; |
| uint16_t weak_values:1; |
| uint16_t weak_keys:1; |
| uint16_t int_values:1; |
| uint16_t int_keys:1; |
| uint16_t indirect_keys:1; |
| uint32_t used_buckets; /* number of used buckets */ |
| uint64_t deleted:16; |
| uint64_t num_buckets_idx:8; /* index to number of buckets */ |
| uint64_t __kret:10; |
| uint64_t __vret:10; |
| uint64_t __krel:10; |
| uint64_t __vrel:10; |
| uint64_t __:1; |
| uint64_t null_rc:1; |
| uint64_t fast_grow:1; |
| uint64_t finalized:1; |
| uint64_t __kdes:10; |
| uint64_t __vdes:10; |
| uint64_t __kequ:10; |
| uint64_t __vequ:10; |
| uint64_t __khas:10; |
| uint64_t __kget:10; |
| } bits; |
| void *pointers[1]; |
| }; |
| |
| static void *CFBasicHashCallBackPtrs[(1UL << 10)]; |
| static int32_t CFBasicHashCallBackPtrsCount = 0; |
| |
| static int32_t CFBasicHashGetPtrIndex(void *ptr) { |
| static dispatch_once_t once; |
| dispatch_once(&once, ^{ |
| CFBasicHashCallBackPtrs[0] = NULL; |
| CFBasicHashCallBackPtrs[1] = (void *)CFCopyDescription; |
| CFBasicHashCallBackPtrs[2] = (void *)__CFTypeCollectionRelease; |
| CFBasicHashCallBackPtrs[3] = (void *)__CFTypeCollectionRetain; |
| CFBasicHashCallBackPtrs[4] = (void *)CFEqual; |
| CFBasicHashCallBackPtrs[5] = (void *)CFHash; |
| CFBasicHashCallBackPtrs[6] = (void *)__CFStringCollectionCopy; |
| CFBasicHashCallBackPtrs[7] = NULL; |
| CFBasicHashCallBackPtrsCount = 8; |
| }); |
| |
| // The uniquing here is done locklessly for best performance, and in |
| // a way that will keep multiple threads from stomping each other's |
| // newly registered values, but may result in multiple slots |
| // containing the same pointer value. |
| |
| int32_t idx; |
| for (idx = 0; idx < CFBasicHashCallBackPtrsCount; idx++) { |
| if (CFBasicHashCallBackPtrs[idx] == ptr) return idx; |
| } |
| |
| if (1000 < CFBasicHashCallBackPtrsCount) HALT; |
| idx = OSAtomicIncrement32(&CFBasicHashCallBackPtrsCount); // returns new value |
| CFBasicHashCallBackPtrs[idx - 1] = ptr; |
| return idx - 1; |
| } |
| |
| CF_PRIVATE Boolean CFBasicHashHasStrongValues(CFConstBasicHashRef ht) { |
| #if DEPLOYMENT_TARGET_MACOSX |
| return ht->bits.strong_values ? true : false; |
| #else |
| return false; |
| #endif |
| } |
| |
| CF_PRIVATE Boolean CFBasicHashHasStrongKeys(CFConstBasicHashRef ht) { |
| #if DEPLOYMENT_TARGET_MACOSX |
| return ht->bits.strong_keys ? true : false; |
| #else |
| return false; |
| #endif |
| } |
| |
| CF_INLINE Boolean __CFBasicHashHasHashCache(CFConstBasicHashRef ht) { |
| #if DEPLOYMENT_TARGET_MACOSX |
| return ht->bits.hashes_offset ? true : false; |
| #else |
| return false; |
| #endif |
| } |
| |
| CF_INLINE uintptr_t __CFBasicHashImportValue(CFConstBasicHashRef ht, uintptr_t stack_value) { |
| uintptr_t (*func)(CFAllocatorRef, uintptr_t) = (uintptr_t (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vret]; |
| if (!func || ht->bits.null_rc) return stack_value; |
| CFAllocatorRef alloc = CFGetAllocator(ht); |
| return func(alloc, stack_value); |
| } |
| |
| CF_INLINE uintptr_t __CFBasicHashImportKey(CFConstBasicHashRef ht, uintptr_t stack_key) { |
| uintptr_t (*func)(CFAllocatorRef, uintptr_t) = (uintptr_t (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kret]; |
| if (!func || ht->bits.null_rc) return stack_key; |
| CFAllocatorRef alloc = CFGetAllocator(ht); |
| return func(alloc, stack_key); |
| } |
| |
| CF_INLINE void __CFBasicHashEjectValue(CFConstBasicHashRef ht, uintptr_t stack_value) { |
| void (*func)(CFAllocatorRef, uintptr_t) = (void (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vrel]; |
| if (!func || ht->bits.null_rc) return; |
| CFAllocatorRef alloc = CFGetAllocator(ht); |
| func(alloc, stack_value); |
| } |
| |
| CF_INLINE void __CFBasicHashEjectKey(CFConstBasicHashRef ht, uintptr_t stack_key) { |
| void (*func)(CFAllocatorRef, uintptr_t) = (void (*)(CFAllocatorRef, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__krel]; |
| if (!func || ht->bits.null_rc) return; |
| CFAllocatorRef alloc = CFGetAllocator(ht); |
| func(alloc, stack_key); |
| } |
| |
| CF_INLINE CFStringRef __CFBasicHashDescValue(CFConstBasicHashRef ht, uintptr_t stack_value) CF_RETURNS_RETAINED { |
| CFStringRef (*func)(uintptr_t) = (CFStringRef (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vdes]; |
| if (!func) return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)stack_value); |
| return func(stack_value); |
| } |
| |
| CF_INLINE CFStringRef __CFBasicHashDescKey(CFConstBasicHashRef ht, uintptr_t stack_key) CF_RETURNS_RETAINED { |
| CFStringRef (*func)(uintptr_t) = (CFStringRef (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kdes]; |
| if (!func) return CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)stack_key); |
| return func(stack_key); |
| } |
| |
| CF_INLINE Boolean __CFBasicHashTestEqualValue(CFConstBasicHashRef ht, uintptr_t stack_value_a, uintptr_t stack_value_b) { |
| Boolean (*func)(uintptr_t, uintptr_t) = (Boolean (*)(uintptr_t, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__vequ]; |
| if (!func) return (stack_value_a == stack_value_b); |
| return func(stack_value_a, stack_value_b); |
| } |
| |
| CF_INLINE Boolean __CFBasicHashTestEqualKey(CFConstBasicHashRef ht, uintptr_t in_coll_key, uintptr_t stack_key) { |
| COCOA_HASHTABLE_TEST_EQUAL(ht, in_coll_key, stack_key); |
| Boolean (*func)(uintptr_t, uintptr_t) = (Boolean (*)(uintptr_t, uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kequ]; |
| if (!func) return (in_coll_key == stack_key); |
| return func(in_coll_key, stack_key); |
| } |
| |
| CF_INLINE CFHashCode __CFBasicHashHashKey(CFConstBasicHashRef ht, uintptr_t stack_key) { |
| CFHashCode (*func)(uintptr_t) = (CFHashCode (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__khas]; |
| CFHashCode hash_code = func ? func(stack_key) : stack_key; |
| COCOA_HASHTABLE_HASH_KEY(ht, stack_key, hash_code); |
| return hash_code; |
| } |
| |
| CF_INLINE uintptr_t __CFBasicHashGetIndirectKey(CFConstBasicHashRef ht, uintptr_t coll_key) { |
| uintptr_t (*func)(uintptr_t) = (uintptr_t (*)(uintptr_t))CFBasicHashCallBackPtrs[ht->bits.__kget]; |
| if (!func) return coll_key; |
| return func(coll_key); |
| } |
| |
| CF_INLINE CFBasicHashValue *__CFBasicHashGetValues(CFConstBasicHashRef ht) { |
| return (CFBasicHashValue *)ht->pointers[0]; |
| } |
| |
| CF_INLINE void __CFBasicHashSetValues(CFBasicHashRef ht, CFBasicHashValue *ptr) { |
| __AssignWithWriteBarrier(&ht->pointers[0], ptr); |
| } |
| |
| CF_INLINE CFBasicHashValue *__CFBasicHashGetKeys(CFConstBasicHashRef ht) { |
| return (CFBasicHashValue *)ht->pointers[ht->bits.keys_offset]; |
| } |
| |
| CF_INLINE void __CFBasicHashSetKeys(CFBasicHashRef ht, CFBasicHashValue *ptr) { |
| __AssignWithWriteBarrier(&ht->pointers[ht->bits.keys_offset], ptr); |
| } |
| |
| CF_INLINE void *__CFBasicHashGetCounts(CFConstBasicHashRef ht) { |
| return (void *)ht->pointers[ht->bits.counts_offset]; |
| } |
| |
| CF_INLINE void __CFBasicHashSetCounts(CFBasicHashRef ht, void *ptr) { |
| __AssignWithWriteBarrier(&ht->pointers[ht->bits.counts_offset], ptr); |
| } |
| |
| CF_INLINE uintptr_t __CFBasicHashGetValue(CFConstBasicHashRef ht, CFIndex idx) { |
| uintptr_t val = __CFBasicHashGetValues(ht)[idx].neutral; |
| if (__CFBasicHashSubABZero == val) return 0UL; |
| if (__CFBasicHashSubABOne == val) return ~0UL; |
| return val; |
| } |
| |
| CF_INLINE void __CFBasicHashSetValue(CFBasicHashRef ht, CFIndex idx, uintptr_t stack_value, Boolean ignoreOld, Boolean literal) { |
| CFBasicHashValue *valuep = &(__CFBasicHashGetValues(ht)[idx]); |
| uintptr_t old_value = ignoreOld ? 0 : valuep->neutral; |
| if (!literal) { |
| if (0UL == stack_value) stack_value = __CFBasicHashSubABZero; |
| if (~0UL == stack_value) stack_value = __CFBasicHashSubABOne; |
| } |
| if (CFBasicHashHasStrongValues(ht)) valuep->strong = (id)stack_value; else valuep->neutral = stack_value; |
| if (!ignoreOld) { |
| if (!(old_value == 0UL || old_value == ~0UL)) { |
| if (__CFBasicHashSubABZero == old_value) old_value = 0UL; |
| if (__CFBasicHashSubABOne == old_value) old_value = ~0UL; |
| __CFBasicHashEjectValue(ht, old_value); |
| } |
| } |
| } |
| |
| CF_INLINE uintptr_t __CFBasicHashGetKey(CFConstBasicHashRef ht, CFIndex idx) { |
| if (ht->bits.keys_offset) { |
| uintptr_t key = __CFBasicHashGetKeys(ht)[idx].neutral; |
| if (__CFBasicHashSubABZero == key) return 0UL; |
| if (__CFBasicHashSubABOne == key) return ~0UL; |
| return key; |
| } |
| if (ht->bits.indirect_keys) { |
| uintptr_t stack_value = __CFBasicHashGetValue(ht, idx); |
| return __CFBasicHashGetIndirectKey(ht, stack_value); |
| } |
| return __CFBasicHashGetValue(ht, idx); |
| } |
| |
| CF_INLINE void __CFBasicHashSetKey(CFBasicHashRef ht, CFIndex idx, uintptr_t stack_key, Boolean ignoreOld, Boolean literal) { |
| if (0 == ht->bits.keys_offset) HALT; |
| CFBasicHashValue *keyp = &(__CFBasicHashGetKeys(ht)[idx]); |
| uintptr_t old_key = ignoreOld ? 0 : keyp->neutral; |
| if (!literal) { |
| if (0UL == stack_key) stack_key = __CFBasicHashSubABZero; |
| if (~0UL == stack_key) stack_key = __CFBasicHashSubABOne; |
| } |
| if (CFBasicHashHasStrongKeys(ht)) keyp->strong = (id)stack_key; else keyp->neutral = stack_key; |
| if (!ignoreOld) { |
| if (!(old_key == 0UL || old_key == ~0UL)) { |
| if (__CFBasicHashSubABZero == old_key) old_key = 0UL; |
| if (__CFBasicHashSubABOne == old_key) old_key = ~0UL; |
| __CFBasicHashEjectKey(ht, old_key); |
| } |
| } |
| } |
| |
| CF_INLINE uintptr_t __CFBasicHashIsEmptyOrDeleted(CFConstBasicHashRef ht, CFIndex idx) { |
| uintptr_t stack_value = __CFBasicHashGetValues(ht)[idx].neutral; |
| return (0UL == stack_value || ~0UL == stack_value); |
| } |
| |
| CF_INLINE uintptr_t __CFBasicHashIsDeleted(CFConstBasicHashRef ht, CFIndex idx) { |
| uintptr_t stack_value = __CFBasicHashGetValues(ht)[idx].neutral; |
| return (~0UL == stack_value); |
| } |
| |
| CF_INLINE uintptr_t __CFBasicHashGetSlotCount(CFConstBasicHashRef ht, CFIndex idx) { |
| void *counts = __CFBasicHashGetCounts(ht); |
| switch (ht->bits.counts_width) { |
| case 0: return ((uint8_t *)counts)[idx]; |
| case 1: return ((uint16_t *)counts)[idx]; |
| case 2: return ((uint32_t *)counts)[idx]; |
| case 3: return ((uint64_t *)counts)[idx]; |
| } |
| return 0; |
| } |
| |
| CF_INLINE void __CFBasicHashBumpCounts(CFBasicHashRef ht) { |
| void *counts = __CFBasicHashGetCounts(ht); |
| CFAllocatorRef allocator = CFGetAllocator(ht); |
| switch (ht->bits.counts_width) { |
| case 0: { |
| uint8_t *counts08 = (uint8_t *)counts; |
| ht->bits.counts_width = 1; |
| CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| uint16_t *counts16 = (uint16_t *)__CFBasicHashAllocateMemory(ht, num_buckets, 2, false, false); |
| if (!counts16) HALT; |
| __SetLastAllocationEventName(counts16, "CFBasicHash (count-store)"); |
| for (CFIndex idx2 = 0; idx2 < num_buckets; idx2++) { |
| counts16[idx2] = counts08[idx2]; |
| } |
| __CFBasicHashSetCounts(ht, counts16); |
| CFAllocatorDeallocate(allocator, counts08); |
| break; |
| } |
| case 1: { |
| uint16_t *counts16 = (uint16_t *)counts; |
| ht->bits.counts_width = 2; |
| CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| uint32_t *counts32 = (uint32_t *)__CFBasicHashAllocateMemory(ht, num_buckets, 4, false, false); |
| if (!counts32) HALT; |
| __SetLastAllocationEventName(counts32, "CFBasicHash (count-store)"); |
| for (CFIndex idx2 = 0; idx2 < num_buckets; idx2++) { |
| counts32[idx2] = counts16[idx2]; |
| } |
| __CFBasicHashSetCounts(ht, counts32); |
| CFAllocatorDeallocate(allocator, counts16); |
| break; |
| } |
| case 2: { |
| uint32_t *counts32 = (uint32_t *)counts; |
| ht->bits.counts_width = 3; |
| CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| uint64_t *counts64 = (uint64_t *)__CFBasicHashAllocateMemory(ht, num_buckets, 8, false, false); |
| if (!counts64) HALT; |
| __SetLastAllocationEventName(counts64, "CFBasicHash (count-store)"); |
| for (CFIndex idx2 = 0; idx2 < num_buckets; idx2++) { |
| counts64[idx2] = counts32[idx2]; |
| } |
| __CFBasicHashSetCounts(ht, counts64); |
| CFAllocatorDeallocate(allocator, counts32); |
| break; |
| } |
| case 3: { |
| HALT; |
| break; |
| } |
| } |
| } |
| |
| static void __CFBasicHashIncSlotCount(CFBasicHashRef ht, CFIndex idx) { |
| void *counts = __CFBasicHashGetCounts(ht); |
| switch (ht->bits.counts_width) { |
| case 0: { |
| uint8_t *counts08 = (uint8_t *)counts; |
| uint8_t val = counts08[idx]; |
| if (val < INT8_MAX) { |
| counts08[idx] = val + 1; |
| return; |
| } |
| __CFBasicHashBumpCounts(ht); |
| __CFBasicHashIncSlotCount(ht, idx); |
| break; |
| } |
| case 1: { |
| uint16_t *counts16 = (uint16_t *)counts; |
| uint16_t val = counts16[idx]; |
| if (val < INT16_MAX) { |
| counts16[idx] = val + 1; |
| return; |
| } |
| __CFBasicHashBumpCounts(ht); |
| __CFBasicHashIncSlotCount(ht, idx); |
| break; |
| } |
| case 2: { |
| uint32_t *counts32 = (uint32_t *)counts; |
| uint32_t val = counts32[idx]; |
| if (val < INT32_MAX) { |
| counts32[idx] = val + 1; |
| return; |
| } |
| __CFBasicHashBumpCounts(ht); |
| __CFBasicHashIncSlotCount(ht, idx); |
| break; |
| } |
| case 3: { |
| uint64_t *counts64 = (uint64_t *)counts; |
| uint64_t val = counts64[idx]; |
| if (val < INT64_MAX) { |
| counts64[idx] = val + 1; |
| return; |
| } |
| __CFBasicHashBumpCounts(ht); |
| __CFBasicHashIncSlotCount(ht, idx); |
| break; |
| } |
| } |
| } |
| |
| CF_INLINE void __CFBasicHashDecSlotCount(CFBasicHashRef ht, CFIndex idx) { |
| void *counts = __CFBasicHashGetCounts(ht); |
| switch (ht->bits.counts_width) { |
| case 0: ((uint8_t *)counts)[idx]--; return; |
| case 1: ((uint16_t *)counts)[idx]--; return; |
| case 2: ((uint32_t *)counts)[idx]--; return; |
| case 3: ((uint64_t *)counts)[idx]--; return; |
| } |
| } |
| |
| CF_INLINE uintptr_t *__CFBasicHashGetHashes(CFConstBasicHashRef ht) { |
| return (uintptr_t *)ht->pointers[ht->bits.hashes_offset]; |
| } |
| |
| CF_INLINE void __CFBasicHashSetHashes(CFBasicHashRef ht, uintptr_t *ptr) { |
| __AssignWithWriteBarrier(&ht->pointers[ht->bits.hashes_offset], ptr); |
| } |
| |
| |
| // to expose the load factor, expose this function to customization |
| CF_INLINE CFIndex __CFBasicHashGetCapacityForNumBuckets(CFConstBasicHashRef ht, CFIndex num_buckets_idx) { |
| return __CFBasicHashTableCapacities[num_buckets_idx]; |
| } |
| |
| CF_INLINE CFIndex __CFBasicHashGetNumBucketsIndexForCapacity(CFConstBasicHashRef ht, CFIndex capacity) { |
| for (CFIndex idx = 0; idx < 64; idx++) { |
| if (capacity <= __CFBasicHashGetCapacityForNumBuckets(ht, idx)) return idx; |
| } |
| HALT; |
| return 0; |
| } |
| |
| CF_PRIVATE CFIndex CFBasicHashGetNumBuckets(CFConstBasicHashRef ht) { |
| return __CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| } |
| |
| CF_PRIVATE CFIndex CFBasicHashGetCapacity(CFConstBasicHashRef ht) { |
| return __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx); |
| } |
| |
| // In returned struct, .count is zero if the bucket is empty or deleted, |
| // and the .weak_key field indicates which. .idx is either the index of |
| // the found bucket or the index of the bucket which should be filled by |
| // an add operation. For a set or multiset, the .weak_key and .weak_value |
| // are the same. |
| CF_PRIVATE CFBasicHashBucket CFBasicHashGetBucket(CFConstBasicHashRef ht, CFIndex idx) { |
| CFBasicHashBucket result; |
| result.idx = idx; |
| if (__CFBasicHashIsEmptyOrDeleted(ht, idx)) { |
| result.count = 0; |
| result.weak_value = 0; |
| result.weak_key = 0; |
| } else { |
| result.count = (ht->bits.counts_offset) ? __CFBasicHashGetSlotCount(ht, idx) : 1; |
| result.weak_value = __CFBasicHashGetValue(ht, idx); |
| result.weak_key = __CFBasicHashGetKey(ht, idx); |
| } |
| return result; |
| } |
| |
| #if defined(__arm__) |
| static uintptr_t __CFBasicHashFold(uintptr_t dividend, uint8_t idx) { |
| switch (idx) { |
| case 1: return dividend % 3; |
| case 2: return dividend % 7; |
| case 3: return dividend % 13; |
| case 4: return dividend % 23; |
| case 5: return dividend % 41; |
| case 6: return dividend % 71; |
| case 7: return dividend % 127; |
| case 8: return dividend % 191; |
| case 9: return dividend % 251; |
| case 10: return dividend % 383; |
| case 11: return dividend % 631; |
| case 12: return dividend % 1087; |
| case 13: return dividend % 1723; |
| case 14: return dividend % 2803; |
| case 15: return dividend % 4523; |
| case 16: return dividend % 7351; |
| case 17: return dividend % 11959; |
| case 18: return dividend % 19447; |
| case 19: return dividend % 31231; |
| case 20: return dividend % 50683; |
| case 21: return dividend % 81919; |
| case 22: return dividend % 132607; |
| case 23: return dividend % 214519; |
| case 24: return dividend % 346607; |
| case 25: return dividend % 561109; |
| case 26: return dividend % 907759; |
| case 27: return dividend % 1468927; |
| case 28: return dividend % 2376191; |
| case 29: return dividend % 3845119; |
| case 30: return dividend % 6221311; |
| case 31: return dividend % 10066421; |
| case 32: return dividend % 16287743; |
| case 33: return dividend % 26354171; |
| case 34: return dividend % 42641881; |
| case 35: return dividend % 68996069; |
| case 36: return dividend % 111638519; |
| case 37: return dividend % 180634607; |
| case 38: return dividend % 292272623; |
| case 39: return dividend % 472907251; |
| } |
| HALT; |
| return ~0; |
| } |
| #endif |
| |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Linear |
| #define FIND_BUCKET_HASH_STYLE 1 |
| #define FIND_BUCKET_FOR_REHASH 0 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 0 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Linear_NoCollision |
| #define FIND_BUCKET_HASH_STYLE 1 |
| #define FIND_BUCKET_FOR_REHASH 1 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 0 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Linear_Indirect |
| #define FIND_BUCKET_HASH_STYLE 1 |
| #define FIND_BUCKET_FOR_REHASH 0 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 1 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Linear_Indirect_NoCollision |
| #define FIND_BUCKET_HASH_STYLE 1 |
| #define FIND_BUCKET_FOR_REHASH 1 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 1 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Double |
| #define FIND_BUCKET_HASH_STYLE 2 |
| #define FIND_BUCKET_FOR_REHASH 0 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 0 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Double_NoCollision |
| #define FIND_BUCKET_HASH_STYLE 2 |
| #define FIND_BUCKET_FOR_REHASH 1 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 0 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Double_Indirect |
| #define FIND_BUCKET_HASH_STYLE 2 |
| #define FIND_BUCKET_FOR_REHASH 0 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 1 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Double_Indirect_NoCollision |
| #define FIND_BUCKET_HASH_STYLE 2 |
| #define FIND_BUCKET_FOR_REHASH 1 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 1 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Exponential |
| #define FIND_BUCKET_HASH_STYLE 3 |
| #define FIND_BUCKET_FOR_REHASH 0 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 0 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Exponential_NoCollision |
| #define FIND_BUCKET_HASH_STYLE 3 |
| #define FIND_BUCKET_FOR_REHASH 1 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 0 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Exponential_Indirect |
| #define FIND_BUCKET_HASH_STYLE 3 |
| #define FIND_BUCKET_FOR_REHASH 0 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 1 |
| #include "CFBasicHashFindBucket.m" |
| |
| #define FIND_BUCKET_NAME ___CFBasicHashFindBucket_Exponential_Indirect_NoCollision |
| #define FIND_BUCKET_HASH_STYLE 3 |
| #define FIND_BUCKET_FOR_REHASH 1 |
| #define FIND_BUCKET_FOR_INDIRECT_KEY 1 |
| #include "CFBasicHashFindBucket.m" |
| |
| |
| CF_INLINE CFBasicHashBucket __CFBasicHashFindBucket(CFConstBasicHashRef ht, uintptr_t stack_key) { |
| if (0 == ht->bits.num_buckets_idx) { |
| CFBasicHashBucket result = {kCFNotFound, 0UL, 0UL, 0}; |
| return result; |
| } |
| if (ht->bits.indirect_keys) { |
| switch (ht->bits.hash_style) { |
| case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear_Indirect(ht, stack_key); |
| case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double_Indirect(ht, stack_key); |
| case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential_Indirect(ht, stack_key); |
| } |
| } else { |
| switch (ht->bits.hash_style) { |
| case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear(ht, stack_key); |
| case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double(ht, stack_key); |
| case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential(ht, stack_key); |
| } |
| } |
| HALT; |
| CFBasicHashBucket result = {kCFNotFound, 0UL, 0UL, 0}; |
| return result; |
| } |
| |
| CF_INLINE CFIndex __CFBasicHashFindBucket_NoCollision(CFConstBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash) { |
| if (0 == ht->bits.num_buckets_idx) { |
| return kCFNotFound; |
| } |
| if (ht->bits.indirect_keys) { |
| switch (ht->bits.hash_style) { |
| case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear_Indirect_NoCollision(ht, stack_key, key_hash); |
| case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double_Indirect_NoCollision(ht, stack_key, key_hash); |
| case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential_Indirect_NoCollision(ht, stack_key, key_hash); |
| } |
| } else { |
| switch (ht->bits.hash_style) { |
| case __kCFBasicHashLinearHashingValue: return ___CFBasicHashFindBucket_Linear_NoCollision(ht, stack_key, key_hash); |
| case __kCFBasicHashDoubleHashingValue: return ___CFBasicHashFindBucket_Double_NoCollision(ht, stack_key, key_hash); |
| case __kCFBasicHashExponentialHashingValue: return ___CFBasicHashFindBucket_Exponential_NoCollision(ht, stack_key, key_hash); |
| } |
| } |
| HALT; |
| return kCFNotFound; |
| } |
| |
| CF_PRIVATE CFBasicHashBucket CFBasicHashFindBucket(CFConstBasicHashRef ht, uintptr_t stack_key) { |
| if (__CFBasicHashSubABZero == stack_key || __CFBasicHashSubABOne == stack_key) { |
| CFBasicHashBucket result = {kCFNotFound, 0UL, 0UL, 0}; |
| return result; |
| } |
| return __CFBasicHashFindBucket(ht, stack_key); |
| } |
| |
| CF_PRIVATE void CFBasicHashSuppressRC(CFBasicHashRef ht) { |
| ht->bits.null_rc = 1; |
| } |
| |
| CF_PRIVATE void CFBasicHashUnsuppressRC(CFBasicHashRef ht) { |
| ht->bits.null_rc = 0; |
| } |
| |
| CF_PRIVATE CFOptionFlags CFBasicHashGetFlags(CFConstBasicHashRef ht) { |
| CFOptionFlags flags = (ht->bits.hash_style << 13); |
| if (CFBasicHashHasStrongValues(ht)) flags |= kCFBasicHashStrongValues; |
| if (CFBasicHashHasStrongKeys(ht)) flags |= kCFBasicHashStrongKeys; |
| if (ht->bits.fast_grow) flags |= kCFBasicHashAggressiveGrowth; |
| if (ht->bits.keys_offset) flags |= kCFBasicHashHasKeys; |
| if (ht->bits.counts_offset) flags |= kCFBasicHashHasCounts; |
| if (__CFBasicHashHasHashCache(ht)) flags |= kCFBasicHashHasHashCache; |
| return flags; |
| } |
| |
| CF_PRIVATE CFIndex CFBasicHashGetCount(CFConstBasicHashRef ht) { |
| if (ht->bits.counts_offset) { |
| CFIndex total = 0L; |
| CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| for (CFIndex idx = 0; idx < cnt; idx++) { |
| total += __CFBasicHashGetSlotCount(ht, idx); |
| } |
| return total; |
| } |
| return (CFIndex)ht->bits.used_buckets; |
| } |
| |
| CF_PRIVATE CFIndex CFBasicHashGetCountOfKey(CFConstBasicHashRef ht, uintptr_t stack_key) { |
| if (__CFBasicHashSubABZero == stack_key || __CFBasicHashSubABOne == stack_key) { |
| return 0L; |
| } |
| if (0L == ht->bits.used_buckets) { |
| return 0L; |
| } |
| return __CFBasicHashFindBucket(ht, stack_key).count; |
| } |
| |
| CF_PRIVATE CFIndex CFBasicHashGetCountOfValue(CFConstBasicHashRef ht, uintptr_t stack_value) { |
| if (__CFBasicHashSubABZero == stack_value) { |
| return 0L; |
| } |
| if (0L == ht->bits.used_buckets) { |
| return 0L; |
| } |
| if (!(ht->bits.keys_offset)) { |
| return __CFBasicHashFindBucket(ht, stack_value).count; |
| } |
| __block CFIndex total = 0L; |
| CFBasicHashApply(ht, ^(CFBasicHashBucket bkt) { |
| if ((stack_value == bkt.weak_value) || __CFBasicHashTestEqualValue(ht, bkt.weak_value, stack_value)) total += bkt.count; |
| return (Boolean)true; |
| }); |
| return total; |
| } |
| |
| CF_PRIVATE Boolean CFBasicHashesAreEqual(CFConstBasicHashRef ht1, CFConstBasicHashRef ht2) { |
| CFIndex cnt1 = CFBasicHashGetCount(ht1); |
| if (cnt1 != CFBasicHashGetCount(ht2)) return false; |
| if (0 == cnt1) return true; |
| __block Boolean equal = true; |
| CFBasicHashApply(ht1, ^(CFBasicHashBucket bkt1) { |
| CFBasicHashBucket bkt2 = __CFBasicHashFindBucket(ht2, bkt1.weak_key); |
| if (bkt1.count != bkt2.count) { |
| equal = false; |
| return (Boolean)false; |
| } |
| if ((ht1->bits.keys_offset) && (bkt1.weak_value != bkt2.weak_value) && !__CFBasicHashTestEqualValue(ht1, bkt1.weak_value, bkt2.weak_value)) { |
| equal = false; |
| return (Boolean)false; |
| } |
| return (Boolean)true; |
| }); |
| return equal; |
| } |
| |
| CF_PRIVATE void CFBasicHashApply(CFConstBasicHashRef ht, Boolean (^block)(CFBasicHashBucket)) { |
| CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| for (CFIndex idx = 0; 0 < used && idx < cnt; idx++) { |
| CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx); |
| if (0 < bkt.count) { |
| if (!block(bkt)) { |
| return; |
| } |
| used--; |
| } |
| } |
| } |
| |
| CF_PRIVATE void CFBasicHashApplyIndexed(CFConstBasicHashRef ht, CFRange range, Boolean (^block)(CFBasicHashBucket)) { |
| if (range.length < 0) HALT; |
| if (range.length == 0) return; |
| CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| if (cnt < range.location + range.length) HALT; |
| for (CFIndex idx = 0; idx < range.length; idx++) { |
| CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, range.location + idx); |
| if (0 < bkt.count) { |
| if (!block(bkt)) { |
| return; |
| } |
| } |
| } |
| } |
| |
| CF_PRIVATE void CFBasicHashGetElements(CFConstBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_keys) { |
| CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| CFIndex offset = 0; |
| for (CFIndex idx = 0; 0 < used && idx < cnt && offset < bufferslen; idx++) { |
| CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx); |
| if (0 < bkt.count) { |
| used--; |
| for (CFIndex cnt = bkt.count; cnt-- && offset < bufferslen;) { |
| if (weak_values) { weak_values[offset] = bkt.weak_value; } |
| if (weak_keys) { weak_keys[offset] = bkt.weak_key; } |
| offset++; |
| } |
| } |
| } |
| } |
| |
| CF_PRIVATE unsigned long __CFBasicHashFastEnumeration(CFConstBasicHashRef ht, struct __objcFastEnumerationStateEquivalent2 *state, void *stackbuffer, unsigned long count) { |
| /* copy as many as count items over */ |
| if (0 == state->state) { /* first time */ |
| state->mutationsPtr = (unsigned long *)&ht->bits; |
| } |
| state->itemsPtr = (unsigned long *)stackbuffer; |
| CFIndex cntx = 0; |
| CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| for (CFIndex idx = (CFIndex)state->state; 0 < used && idx < cnt && cntx < (CFIndex)count; idx++) { |
| CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx); |
| if (0 < bkt.count) { |
| state->itemsPtr[cntx++] = (unsigned long)bkt.weak_key; |
| used--; |
| } |
| state->state++; |
| } |
| return cntx; |
| } |
| |
| #if ENABLE_MEMORY_COUNTERS |
| static volatile int64_t __CFBasicHashTotalCount = 0ULL; |
| static volatile int64_t __CFBasicHashTotalSize = 0ULL; |
| static volatile int64_t __CFBasicHashPeakCount = 0ULL; |
| static volatile int64_t __CFBasicHashPeakSize = 0ULL; |
| static volatile int32_t __CFBasicHashSizes[64] = {0}; |
| #endif |
| |
| static void __CFBasicHashDrain(CFBasicHashRef ht) { |
| #if ENABLE_MEMORY_COUNTERS |
| OSAtomicAdd64Barrier(-1 * (int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize); |
| #endif |
| |
| CFIndex old_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| |
| CFAllocatorRef allocator = CFGetAllocator(ht); |
| |
| CFBasicHashValue *old_values = NULL, *old_keys = NULL; |
| void *old_counts = NULL; |
| uintptr_t *old_hashes = NULL; |
| |
| old_values = __CFBasicHashGetValues(ht); |
| __CFBasicHashSetValues(ht, NULL); |
| if (ht->bits.keys_offset) { |
| old_keys = __CFBasicHashGetKeys(ht); |
| __CFBasicHashSetKeys(ht, NULL); |
| } |
| if (ht->bits.counts_offset) { |
| old_counts = __CFBasicHashGetCounts(ht); |
| __CFBasicHashSetCounts(ht, NULL); |
| } |
| if (__CFBasicHashHasHashCache(ht)) { |
| old_hashes = __CFBasicHashGetHashes(ht); |
| __CFBasicHashSetHashes(ht, NULL); |
| } |
| |
| ht->bits.mutations++; |
| ht->bits.num_buckets_idx = 0; |
| ht->bits.used_buckets = 0; |
| ht->bits.deleted = 0; |
| |
| for (CFIndex idx = 0; idx < old_num_buckets; idx++) { |
| uintptr_t stack_value = old_values[idx].neutral; |
| if (stack_value != 0UL && stack_value != ~0UL) { |
| uintptr_t old_value = stack_value; |
| if (__CFBasicHashSubABZero == old_value) old_value = 0UL; |
| if (__CFBasicHashSubABOne == old_value) old_value = ~0UL; |
| __CFBasicHashEjectValue(ht, old_value); |
| if (old_keys) { |
| uintptr_t old_key = old_keys[idx].neutral; |
| if (__CFBasicHashSubABZero == old_key) old_key = 0UL; |
| if (__CFBasicHashSubABOne == old_key) old_key = ~0UL; |
| __CFBasicHashEjectKey(ht, old_key); |
| } |
| } |
| } |
| |
| CFAllocatorDeallocate(allocator, old_values); |
| CFAllocatorDeallocate(allocator, old_keys); |
| CFAllocatorDeallocate(allocator, old_counts); |
| CFAllocatorDeallocate(allocator, old_hashes); |
| |
| #if ENABLE_MEMORY_COUNTERS |
| int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize); |
| while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize)); |
| #endif |
| } |
| |
| static void __CFBasicHashRehash(CFBasicHashRef ht, CFIndex newItemCount) { |
| #if ENABLE_MEMORY_COUNTERS |
| OSAtomicAdd64Barrier(-1 * (int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize); |
| OSAtomicAdd32Barrier(-1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]); |
| #endif |
| |
| if (COCOA_HASHTABLE_REHASH_START_ENABLED()) COCOA_HASHTABLE_REHASH_START(ht, CFBasicHashGetNumBuckets(ht), CFBasicHashGetSize(ht, true)); |
| |
| CFIndex new_num_buckets_idx = ht->bits.num_buckets_idx; |
| if (0 != newItemCount) { |
| if (newItemCount < 0) newItemCount = 0; |
| CFIndex new_capacity_req = ht->bits.used_buckets + newItemCount; |
| new_num_buckets_idx = __CFBasicHashGetNumBucketsIndexForCapacity(ht, new_capacity_req); |
| if (1 == newItemCount && ht->bits.fast_grow) { |
| new_num_buckets_idx++; |
| } |
| } |
| |
| CFIndex new_num_buckets = __CFBasicHashTableSizes[new_num_buckets_idx]; |
| CFIndex old_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| |
| CFBasicHashValue *new_values = NULL, *new_keys = NULL; |
| void *new_counts = NULL; |
| uintptr_t *new_hashes = NULL; |
| |
| if (0 < new_num_buckets) { |
| new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), CFBasicHashHasStrongValues(ht), 0); |
| if (!new_values) HALT; |
| __SetLastAllocationEventName(new_values, "CFBasicHash (value-store)"); |
| memset(new_values, 0, new_num_buckets * sizeof(CFBasicHashValue)); |
| if (ht->bits.keys_offset) { |
| new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), CFBasicHashHasStrongKeys(ht), 0); |
| if (!new_keys) HALT; |
| __SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)"); |
| memset(new_keys, 0, new_num_buckets * sizeof(CFBasicHashValue)); |
| } |
| if (ht->bits.counts_offset) { |
| new_counts = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, (1 << ht->bits.counts_width), false, false); |
| if (!new_counts) HALT; |
| __SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)"); |
| memset(new_counts, 0, new_num_buckets * (1 << ht->bits.counts_width)); |
| } |
| if (__CFBasicHashHasHashCache(ht)) { |
| new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false, false); |
| if (!new_hashes) HALT; |
| __SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)"); |
| memset(new_hashes, 0, new_num_buckets * sizeof(uintptr_t)); |
| } |
| } |
| |
| ht->bits.num_buckets_idx = new_num_buckets_idx; |
| ht->bits.deleted = 0; |
| |
| CFBasicHashValue *old_values = NULL, *old_keys = NULL; |
| void *old_counts = NULL; |
| uintptr_t *old_hashes = NULL; |
| |
| old_values = __CFBasicHashGetValues(ht); |
| __CFBasicHashSetValues(ht, new_values); |
| if (ht->bits.keys_offset) { |
| old_keys = __CFBasicHashGetKeys(ht); |
| __CFBasicHashSetKeys(ht, new_keys); |
| } |
| if (ht->bits.counts_offset) { |
| old_counts = __CFBasicHashGetCounts(ht); |
| __CFBasicHashSetCounts(ht, new_counts); |
| } |
| if (__CFBasicHashHasHashCache(ht)) { |
| old_hashes = __CFBasicHashGetHashes(ht); |
| __CFBasicHashSetHashes(ht, new_hashes); |
| } |
| |
| if (0 < old_num_buckets) { |
| for (CFIndex idx = 0; idx < old_num_buckets; idx++) { |
| uintptr_t stack_value = old_values[idx].neutral; |
| if (stack_value != 0UL && stack_value != ~0UL) { |
| if (__CFBasicHashSubABZero == stack_value) stack_value = 0UL; |
| if (__CFBasicHashSubABOne == stack_value) stack_value = ~0UL; |
| uintptr_t stack_key = stack_value; |
| if (ht->bits.keys_offset) { |
| stack_key = old_keys[idx].neutral; |
| if (__CFBasicHashSubABZero == stack_key) stack_key = 0UL; |
| if (__CFBasicHashSubABOne == stack_key) stack_key = ~0UL; |
| } |
| if (ht->bits.indirect_keys) { |
| stack_key = __CFBasicHashGetIndirectKey(ht, stack_value); |
| } |
| CFIndex bkt_idx = __CFBasicHashFindBucket_NoCollision(ht, stack_key, old_hashes ? old_hashes[idx] : 0UL); |
| __CFBasicHashSetValue(ht, bkt_idx, stack_value, false, false); |
| if (old_keys) { |
| __CFBasicHashSetKey(ht, bkt_idx, stack_key, false, false); |
| } |
| if (old_counts && new_counts) { |
| switch (ht->bits.counts_width) { |
| case 0: ((uint8_t *)new_counts)[bkt_idx] = ((uint8_t *)old_counts)[idx]; break; |
| case 1: ((uint16_t *)new_counts)[bkt_idx] = ((uint16_t *)old_counts)[idx]; break; |
| case 2: ((uint32_t *)new_counts)[bkt_idx] = ((uint32_t *)old_counts)[idx]; break; |
| case 3: ((uint64_t *)new_counts)[bkt_idx] = ((uint64_t *)old_counts)[idx]; break; |
| } |
| } |
| if (old_hashes && new_hashes) { |
| new_hashes[bkt_idx] = old_hashes[idx]; |
| } |
| } |
| } |
| } |
| |
| CFAllocatorRef allocator = CFGetAllocator(ht); |
| CFAllocatorDeallocate(allocator, old_values); |
| CFAllocatorDeallocate(allocator, old_keys); |
| CFAllocatorDeallocate(allocator, old_counts); |
| CFAllocatorDeallocate(allocator, old_hashes); |
| |
| if (COCOA_HASHTABLE_REHASH_END_ENABLED()) COCOA_HASHTABLE_REHASH_END(ht, CFBasicHashGetNumBuckets(ht), CFBasicHashGetSize(ht, true)); |
| |
| #if ENABLE_MEMORY_COUNTERS |
| int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), &__CFBasicHashTotalSize); |
| while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize)); |
| OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]); |
| #endif |
| } |
| |
| CF_PRIVATE void CFBasicHashSetCapacity(CFBasicHashRef ht, CFIndex capacity) { |
| if (!CFBasicHashIsMutable(ht)) HALT; |
| if (ht->bits.used_buckets < capacity) { |
| ht->bits.mutations++; |
| __CFBasicHashRehash(ht, capacity - ht->bits.used_buckets); |
| } |
| } |
| |
| static void __CFBasicHashAddValue(CFBasicHashRef ht, CFIndex bkt_idx, uintptr_t stack_key, uintptr_t stack_value) { |
| ht->bits.mutations++; |
| if (CFBasicHashGetCapacity(ht) < ht->bits.used_buckets + 1) { |
| __CFBasicHashRehash(ht, 1); |
| bkt_idx = __CFBasicHashFindBucket_NoCollision(ht, stack_key, 0); |
| } else if (__CFBasicHashIsDeleted(ht, bkt_idx)) { |
| ht->bits.deleted--; |
| } |
| uintptr_t key_hash = 0; |
| if (__CFBasicHashHasHashCache(ht)) { |
| key_hash = __CFBasicHashHashKey(ht, stack_key); |
| } |
| stack_value = __CFBasicHashImportValue(ht, stack_value); |
| if (ht->bits.keys_offset) { |
| stack_key = __CFBasicHashImportKey(ht, stack_key); |
| } |
| __CFBasicHashSetValue(ht, bkt_idx, stack_value, false, false); |
| if (ht->bits.keys_offset) { |
| __CFBasicHashSetKey(ht, bkt_idx, stack_key, false, false); |
| } |
| if (ht->bits.counts_offset) { |
| __CFBasicHashIncSlotCount(ht, bkt_idx); |
| } |
| if (__CFBasicHashHasHashCache(ht)) { |
| __CFBasicHashGetHashes(ht)[bkt_idx] = key_hash; |
| } |
| ht->bits.used_buckets++; |
| } |
| |
| static void __CFBasicHashReplaceValue(CFBasicHashRef ht, CFIndex bkt_idx, uintptr_t stack_key, uintptr_t stack_value) { |
| ht->bits.mutations++; |
| stack_value = __CFBasicHashImportValue(ht, stack_value); |
| if (ht->bits.keys_offset) { |
| stack_key = __CFBasicHashImportKey(ht, stack_key); |
| } |
| __CFBasicHashSetValue(ht, bkt_idx, stack_value, false, false); |
| if (ht->bits.keys_offset) { |
| __CFBasicHashSetKey(ht, bkt_idx, stack_key, false, false); |
| } |
| } |
| |
| static void __CFBasicHashRemoveValue(CFBasicHashRef ht, CFIndex bkt_idx) { |
| ht->bits.mutations++; |
| __CFBasicHashSetValue(ht, bkt_idx, ~0UL, false, true); |
| if (ht->bits.keys_offset) { |
| __CFBasicHashSetKey(ht, bkt_idx, ~0UL, false, true); |
| } |
| if (ht->bits.counts_offset) { |
| __CFBasicHashDecSlotCount(ht, bkt_idx); |
| } |
| if (__CFBasicHashHasHashCache(ht)) { |
| __CFBasicHashGetHashes(ht)[bkt_idx] = 0; |
| } |
| ht->bits.used_buckets--; |
| ht->bits.deleted++; |
| Boolean do_shrink = false; |
| if (ht->bits.fast_grow) { // == slow shrink |
| do_shrink = (5 < ht->bits.num_buckets_idx && ht->bits.used_buckets < __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx - 5)); |
| } else { |
| do_shrink = (2 < ht->bits.num_buckets_idx && ht->bits.used_buckets < __CFBasicHashGetCapacityForNumBuckets(ht, ht->bits.num_buckets_idx - 2)); |
| } |
| if (do_shrink) { |
| __CFBasicHashRehash(ht, -1); |
| return; |
| } |
| do_shrink = (0 == ht->bits.deleted); // .deleted roll-over |
| CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| do_shrink = do_shrink || ((20 <= num_buckets) && (num_buckets / 4 <= ht->bits.deleted)); |
| if (do_shrink) { |
| __CFBasicHashRehash(ht, 0); |
| } |
| } |
| |
| CF_PRIVATE Boolean CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) { |
| if (!CFBasicHashIsMutable(ht)) HALT; |
| if (__CFBasicHashSubABZero == stack_key) HALT; |
| if (__CFBasicHashSubABOne == stack_key) HALT; |
| if (__CFBasicHashSubABZero == stack_value) HALT; |
| if (__CFBasicHashSubABOne == stack_value) HALT; |
| CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key); |
| if (0 < bkt.count) { |
| ht->bits.mutations++; |
| if (ht->bits.counts_offset && bkt.count < LONG_MAX) { // if not yet as large as a CFIndex can be... otherwise clamp and do nothing |
| __CFBasicHashIncSlotCount(ht, bkt.idx); |
| return true; |
| } |
| } else { |
| __CFBasicHashAddValue(ht, bkt.idx, stack_key, stack_value); |
| return true; |
| } |
| return false; |
| } |
| |
| CF_PRIVATE void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) { |
| if (!CFBasicHashIsMutable(ht)) HALT; |
| if (__CFBasicHashSubABZero == stack_key) HALT; |
| if (__CFBasicHashSubABOne == stack_key) HALT; |
| if (__CFBasicHashSubABZero == stack_value) HALT; |
| if (__CFBasicHashSubABOne == stack_value) HALT; |
| CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key); |
| if (0 < bkt.count) { |
| __CFBasicHashReplaceValue(ht, bkt.idx, stack_key, stack_value); |
| } |
| } |
| |
| CF_PRIVATE void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) { |
| if (!CFBasicHashIsMutable(ht)) HALT; |
| if (__CFBasicHashSubABZero == stack_key) HALT; |
| if (__CFBasicHashSubABOne == stack_key) HALT; |
| if (__CFBasicHashSubABZero == stack_value) HALT; |
| if (__CFBasicHashSubABOne == stack_value) HALT; |
| CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key); |
| if (0 < bkt.count) { |
| __CFBasicHashReplaceValue(ht, bkt.idx, stack_key, stack_value); |
| } else { |
| __CFBasicHashAddValue(ht, bkt.idx, stack_key, stack_value); |
| } |
| } |
| |
| CF_PRIVATE CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key) { |
| if (!CFBasicHashIsMutable(ht)) HALT; |
| if (__CFBasicHashSubABZero == stack_key || __CFBasicHashSubABOne == stack_key) return 0; |
| CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key); |
| if (1 < bkt.count) { |
| ht->bits.mutations++; |
| if (ht->bits.counts_offset && bkt.count < LONG_MAX) { // if not as large as a CFIndex can be... otherwise clamp and do nothing |
| __CFBasicHashDecSlotCount(ht, bkt.idx); |
| } |
| } else if (0 < bkt.count) { |
| __CFBasicHashRemoveValue(ht, bkt.idx); |
| } |
| return bkt.count; |
| } |
| |
| CF_PRIVATE CFIndex CFBasicHashRemoveValueAtIndex(CFBasicHashRef ht, CFIndex idx) { |
| if (!CFBasicHashIsMutable(ht)) HALT; |
| CFBasicHashBucket bkt = CFBasicHashGetBucket(ht, idx); |
| if (1 < bkt.count) { |
| ht->bits.mutations++; |
| if (ht->bits.counts_offset && bkt.count < LONG_MAX) { // if not as large as a CFIndex can be... otherwise clamp and do nothing |
| __CFBasicHashDecSlotCount(ht, bkt.idx); |
| } |
| } else if (0 < bkt.count) { |
| __CFBasicHashRemoveValue(ht, bkt.idx); |
| } |
| return bkt.count; |
| } |
| |
| CF_PRIVATE void CFBasicHashRemoveAllValues(CFBasicHashRef ht) { |
| if (!CFBasicHashIsMutable(ht)) HALT; |
| if (0 == ht->bits.num_buckets_idx) return; |
| __CFBasicHashDrain(ht); |
| } |
| |
| CF_PRIVATE Boolean CFBasicHashAddIntValueAndInc(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t int_value) { |
| if (!CFBasicHashIsMutable(ht)) HALT; |
| if (__CFBasicHashSubABZero == stack_key) HALT; |
| if (__CFBasicHashSubABOne == stack_key) HALT; |
| if (__CFBasicHashSubABZero == int_value) HALT; |
| if (__CFBasicHashSubABOne == int_value) HALT; |
| CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key); |
| if (0 < bkt.count) { |
| ht->bits.mutations++; |
| } else { |
| // must rehash before renumbering |
| if (CFBasicHashGetCapacity(ht) < ht->bits.used_buckets + 1) { |
| __CFBasicHashRehash(ht, 1); |
| bkt.idx = __CFBasicHashFindBucket_NoCollision(ht, stack_key, 0); |
| } |
| CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| for (CFIndex idx = 0; idx < cnt; idx++) { |
| if (!__CFBasicHashIsEmptyOrDeleted(ht, idx)) { |
| uintptr_t stack_value = __CFBasicHashGetValue(ht, idx); |
| if (int_value <= stack_value) { |
| stack_value++; |
| __CFBasicHashSetValue(ht, idx, stack_value, true, false); |
| ht->bits.mutations++; |
| } |
| } |
| } |
| __CFBasicHashAddValue(ht, bkt.idx, stack_key, int_value); |
| return true; |
| } |
| return false; |
| } |
| |
| CF_PRIVATE void CFBasicHashRemoveIntValueAndDec(CFBasicHashRef ht, uintptr_t int_value) { |
| if (!CFBasicHashIsMutable(ht)) HALT; |
| if (__CFBasicHashSubABZero == int_value) HALT; |
| if (__CFBasicHashSubABOne == int_value) HALT; |
| uintptr_t bkt_idx = ~0UL; |
| CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| for (CFIndex idx = 0; idx < cnt; idx++) { |
| if (!__CFBasicHashIsEmptyOrDeleted(ht, idx)) { |
| uintptr_t stack_value = __CFBasicHashGetValue(ht, idx); |
| if (int_value == stack_value) { |
| bkt_idx = idx; |
| } |
| if (int_value < stack_value) { |
| stack_value--; |
| __CFBasicHashSetValue(ht, idx, stack_value, true, false); |
| ht->bits.mutations++; |
| } |
| } |
| } |
| __CFBasicHashRemoveValue(ht, bkt_idx); |
| } |
| |
| CF_PRIVATE size_t CFBasicHashGetSize(CFConstBasicHashRef ht, Boolean total) { |
| size_t size = sizeof(struct __CFBasicHash); |
| if (ht->bits.keys_offset) size += sizeof(CFBasicHashValue *); |
| if (ht->bits.counts_offset) size += sizeof(void *); |
| if (__CFBasicHashHasHashCache(ht)) size += sizeof(uintptr_t *); |
| if (total) { |
| CFIndex num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx]; |
| if (0 < num_buckets) { |
| size += malloc_size(__CFBasicHashGetValues(ht)); |
| if (ht->bits.keys_offset) size += malloc_size(__CFBasicHashGetKeys(ht)); |
| if (ht->bits.counts_offset) size += malloc_size(__CFBasicHashGetCounts(ht)); |
| if (__CFBasicHashHasHashCache(ht)) size += malloc_size(__CFBasicHashGetHashes(ht)); |
| } |
| } |
| return size; |
| } |
| |
| CF_PRIVATE CFStringRef CFBasicHashCopyDescription(CFConstBasicHashRef ht, Boolean detailed, CFStringRef prefix, CFStringRef entryPrefix, Boolean describeElements) { |
| CFMutableStringRef result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0); |
| 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)); |
| if (detailed) { |
| const char *cb_type = "custom"; |
| 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); |
| 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); |
| 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")); |
| 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)); |
| 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)); |
| } |
| CFStringAppendFormat(result, NULL, CFSTR("%@entries =>\n"), prefix); |
| CFBasicHashApply(ht, ^(CFBasicHashBucket bkt) { |
| CFStringRef vDesc = NULL, kDesc = NULL; |
| if (!describeElements) { |
| vDesc = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)bkt.weak_value); |
| if (ht->bits.keys_offset) { |
| kDesc = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (void *)bkt.weak_key); |
| } |
| } else { |
| vDesc = __CFBasicHashDescValue(ht, bkt.weak_value); |
| if (ht->bits.keys_offset) { |
| kDesc = __CFBasicHashDescKey(ht, bkt.weak_key); |
| } |
| } |
| if (ht->bits.keys_offset && ht->bits.counts_offset) { |
| CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ = %@ (%ld)\n"), entryPrefix, bkt.idx, kDesc, vDesc, bkt.count); |
| } else if (ht->bits.keys_offset) { |
| CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ = %@\n"), entryPrefix, bkt.idx, kDesc, vDesc); |
| } else if (ht->bits.counts_offset) { |
| CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@ (%ld)\n"), entryPrefix, bkt.idx, vDesc, bkt.count); |
| } else { |
| CFStringAppendFormat(result, NULL, CFSTR("%@%ld : %@\n"), entryPrefix, bkt.idx, vDesc); |
| } |
| if (kDesc) CFRelease(kDesc); |
| if (vDesc) CFRelease(vDesc); |
| return (Boolean)true; |
| }); |
| CFStringAppendFormat(result, NULL, CFSTR("%@}\n"), prefix); |
| return result; |
| } |
| |
| CF_PRIVATE void CFBasicHashShow(CFConstBasicHashRef ht) { |
| CFStringRef str = CFBasicHashCopyDescription(ht, true, CFSTR(""), CFSTR("\t"), false); |
| CFShow(str); |
| CFRelease(str); |
| } |
| |
| CF_PRIVATE Boolean __CFBasicHashEqual(CFTypeRef cf1, CFTypeRef cf2) { |
| CFBasicHashRef ht1 = (CFBasicHashRef)cf1; |
| CFBasicHashRef ht2 = (CFBasicHashRef)cf2; |
| //#warning this used to require that the key and value equal callbacks were pointer identical |
| return CFBasicHashesAreEqual(ht1, ht2); |
| } |
| |
| CF_PRIVATE CFHashCode __CFBasicHashHash(CFTypeRef cf) { |
| CFBasicHashRef ht = (CFBasicHashRef)cf; |
| return CFBasicHashGetCount(ht); |
| } |
| |
| CF_PRIVATE CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf) { |
| CFBasicHashRef ht = (CFBasicHashRef)cf; |
| CFStringRef desc = CFBasicHashCopyDescription(ht, false, CFSTR(""), CFSTR("\t"), true); |
| CFStringRef result = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<CFBasicHash %p [%p]>%@"), cf, CFGetAllocator(cf), desc); |
| CFRelease(desc); |
| return result; |
| } |
| |
| CF_PRIVATE void __CFBasicHashDeallocate(CFTypeRef cf) { |
| CFBasicHashRef ht = (CFBasicHashRef)cf; |
| if (ht->bits.finalized) HALT; |
| ht->bits.finalized = 1; |
| __CFBasicHashDrain(ht); |
| #if ENABLE_MEMORY_COUNTERS |
| OSAtomicAdd64Barrier(-1, &__CFBasicHashTotalCount); |
| OSAtomicAdd32Barrier(-1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]); |
| #endif |
| } |
| |
| static CFTypeID __kCFBasicHashTypeID = _kCFRuntimeNotATypeID; |
| |
| static const CFRuntimeClass __CFBasicHashClass = { |
| _kCFRuntimeScannedObject, |
| "CFBasicHash", |
| NULL, // init |
| NULL, // copy |
| __CFBasicHashDeallocate, |
| __CFBasicHashEqual, |
| __CFBasicHashHash, |
| NULL, // |
| __CFBasicHashCopyDescription |
| }; |
| |
| CF_PRIVATE CFTypeID CFBasicHashGetTypeID(void) { |
| static dispatch_once_t initOnce; |
| dispatch_once(&initOnce, ^{ __kCFBasicHashTypeID = _CFRuntimeRegisterClass(&__CFBasicHashClass); }); |
| return __kCFBasicHashTypeID; |
| } |
| |
| CF_PRIVATE CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb) { |
| size_t size = sizeof(struct __CFBasicHash) - sizeof(CFRuntimeBase); |
| if (flags & kCFBasicHashHasKeys) size += sizeof(CFBasicHashValue *); // keys |
| if (flags & kCFBasicHashHasCounts) size += sizeof(void *); // counts |
| if (flags & kCFBasicHashHasHashCache) size += sizeof(uintptr_t *); // hashes |
| CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL); |
| if (NULL == ht) return NULL; |
| |
| ht->bits.finalized = 0; |
| ht->bits.hash_style = (flags >> 13) & 0x3; |
| ht->bits.fast_grow = (flags & kCFBasicHashAggressiveGrowth) ? 1 : 0; |
| ht->bits.counts_width = 0; |
| ht->bits.strong_values = (flags & kCFBasicHashStrongValues) ? 1 : 0; |
| ht->bits.strong_keys = (flags & kCFBasicHashStrongKeys) ? 1 : 0; |
| ht->bits.weak_values = (flags & kCFBasicHashWeakValues) ? 1 : 0; |
| ht->bits.weak_keys = (flags & kCFBasicHashWeakKeys) ? 1 : 0; |
| ht->bits.int_values = (flags & kCFBasicHashIntegerValues) ? 1 : 0; |
| ht->bits.int_keys = (flags & kCFBasicHashIntegerKeys) ? 1 : 0; |
| ht->bits.indirect_keys = (flags & kCFBasicHashIndirectKeys) ? 1 : 0; |
| ht->bits.num_buckets_idx = 0; |
| ht->bits.used_buckets = 0; |
| ht->bits.deleted = 0; |
| ht->bits.mutations = 1; |
| |
| if (ht->bits.strong_values && ht->bits.weak_values) HALT; |
| if (ht->bits.strong_values && ht->bits.int_values) HALT; |
| if (ht->bits.strong_keys && ht->bits.weak_keys) HALT; |
| if (ht->bits.strong_keys && ht->bits.int_keys) HALT; |
| if (ht->bits.weak_values && ht->bits.int_values) HALT; |
| if (ht->bits.weak_keys && ht->bits.int_keys) HALT; |
| if (ht->bits.indirect_keys && ht->bits.strong_keys) HALT; |
| if (ht->bits.indirect_keys && ht->bits.weak_keys) HALT; |
| if (ht->bits.indirect_keys && ht->bits.int_keys) HALT; |
| |
| uint64_t offset = 1; |
| ht->bits.keys_offset = (flags & kCFBasicHashHasKeys) ? offset++ : 0; |
| ht->bits.counts_offset = (flags & kCFBasicHashHasCounts) ? offset++ : 0; |
| ht->bits.hashes_offset = (flags & kCFBasicHashHasHashCache) ? offset++ : 0; |
| |
| #if DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_EMBEDDED_MINI |
| ht->bits.hashes_offset = 0; |
| ht->bits.strong_values = 0; |
| ht->bits.strong_keys = 0; |
| ht->bits.weak_values = 0; |
| ht->bits.weak_keys = 0; |
| #endif |
| |
| ht->bits.__kret = CFBasicHashGetPtrIndex((void *)cb->retainKey); |
| ht->bits.__vret = CFBasicHashGetPtrIndex((void *)cb->retainValue); |
| ht->bits.__krel = CFBasicHashGetPtrIndex((void *)cb->releaseKey); |
| ht->bits.__vrel = CFBasicHashGetPtrIndex((void *)cb->releaseValue); |
| ht->bits.__kdes = CFBasicHashGetPtrIndex((void *)cb->copyKeyDescription); |
| ht->bits.__vdes = CFBasicHashGetPtrIndex((void *)cb->copyValueDescription); |
| ht->bits.__kequ = CFBasicHashGetPtrIndex((void *)cb->equateKeys); |
| ht->bits.__vequ = CFBasicHashGetPtrIndex((void *)cb->equateValues); |
| ht->bits.__khas = CFBasicHashGetPtrIndex((void *)cb->hashKey); |
| ht->bits.__kget = CFBasicHashGetPtrIndex((void *)cb->getIndirectKey); |
| |
| for (CFIndex idx = 0; idx < offset; idx++) { |
| ht->pointers[idx] = NULL; |
| } |
| |
| #if ENABLE_MEMORY_COUNTERS |
| int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize); |
| while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize)); |
| int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount); |
| while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount)); |
| OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]); |
| #endif |
| |
| return ht; |
| } |
| |
| CF_PRIVATE CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFConstBasicHashRef src_ht) { |
| size_t size = CFBasicHashGetSize(src_ht, false) - sizeof(CFRuntimeBase); |
| CFIndex new_num_buckets = __CFBasicHashTableSizes[src_ht->bits.num_buckets_idx]; |
| CFBasicHashValue *new_values = NULL, *new_keys = NULL; |
| void *new_counts = NULL; |
| uintptr_t *new_hashes = NULL; |
| |
| if (0 < new_num_buckets) { |
| Boolean strongValues = CFBasicHashHasStrongValues(src_ht); |
| Boolean strongKeys = CFBasicHashHasStrongKeys(src_ht); |
| new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, sizeof(CFBasicHashValue), strongValues, 0); |
| if (!new_values) return NULL; // in this unusual circumstance, leak previously allocated blocks for now |
| __SetLastAllocationEventName(new_values, "CFBasicHash (value-store)"); |
| if (src_ht->bits.keys_offset) { |
| new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, sizeof(CFBasicHashValue), strongKeys, false); |
| if (!new_keys) return NULL; // in this unusual circumstance, leak previously allocated blocks for now |
| __SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)"); |
| } |
| if (src_ht->bits.counts_offset) { |
| new_counts = (uintptr_t *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, (1 << src_ht->bits.counts_width), false, false); |
| if (!new_counts) return NULL; // in this unusual circumstance, leak previously allocated blocks for now |
| __SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)"); |
| } |
| if (__CFBasicHashHasHashCache(src_ht)) { |
| new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory2(allocator, new_num_buckets, sizeof(uintptr_t), false, false); |
| if (!new_hashes) return NULL; // in this unusual circumstance, leak previously allocated blocks for now |
| __SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)"); |
| } |
| } |
| |
| CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL); |
| if (NULL == ht) return NULL; // in this unusual circumstance, leak previously allocated blocks for now |
| |
| memmove((uint8_t *)ht + sizeof(CFRuntimeBase), (uint8_t *)src_ht + sizeof(CFRuntimeBase), sizeof(ht->bits)); |
| ht->bits.finalized = 0; |
| ht->bits.mutations = 1; |
| |
| if (0 == new_num_buckets) { |
| #if ENABLE_MEMORY_COUNTERS |
| int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize); |
| while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize)); |
| int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount); |
| while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount)); |
| OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]); |
| #endif |
| return ht; |
| } |
| |
| CFBasicHashValue *old_values = NULL, *old_keys = NULL; |
| void *old_counts = NULL; |
| uintptr_t *old_hashes = NULL; |
| |
| old_values = __CFBasicHashGetValues(src_ht); |
| if (src_ht->bits.keys_offset) { |
| old_keys = __CFBasicHashGetKeys(src_ht); |
| } |
| if (src_ht->bits.counts_offset) { |
| old_counts = __CFBasicHashGetCounts(src_ht); |
| } |
| if (__CFBasicHashHasHashCache(src_ht)) { |
| old_hashes = __CFBasicHashGetHashes(src_ht); |
| } |
| |
| __CFBasicHashSetValues(ht, new_values); |
| if (new_keys) { |
| __CFBasicHashSetKeys(ht, new_keys); |
| } |
| if (new_counts) { |
| __CFBasicHashSetCounts(ht, new_counts); |
| } |
| if (new_hashes) { |
| __CFBasicHashSetHashes(ht, new_hashes); |
| } |
| |
| for (CFIndex idx = 0; idx < new_num_buckets; idx++) { |
| uintptr_t stack_value = old_values[idx].neutral; |
| if (stack_value != 0UL && stack_value != ~0UL) { |
| uintptr_t old_value = stack_value; |
| if (__CFBasicHashSubABZero == old_value) old_value = 0UL; |
| if (__CFBasicHashSubABOne == old_value) old_value = ~0UL; |
| __CFBasicHashSetValue(ht, idx, __CFBasicHashImportValue(ht, old_value), true, false); |
| if (new_keys) { |
| uintptr_t old_key = old_keys[idx].neutral; |
| if (__CFBasicHashSubABZero == old_key) old_key = 0UL; |
| if (__CFBasicHashSubABOne == old_key) old_key = ~0UL; |
| __CFBasicHashSetKey(ht, idx, __CFBasicHashImportKey(ht, old_key), true, false); |
| } |
| } else { |
| __CFBasicHashSetValue(ht, idx, stack_value, true, true); |
| if (new_keys) { |
| __CFBasicHashSetKey(ht, idx, stack_value, true, true); |
| } |
| } |
| } |
| if (new_counts) memmove(new_counts, old_counts, new_num_buckets * (1 << ht->bits.counts_width)); |
| if (new_hashes) memmove(new_hashes, old_hashes, new_num_buckets * sizeof(uintptr_t)); |
| |
| #if ENABLE_MEMORY_COUNTERS |
| int64_t size_now = OSAtomicAdd64Barrier((int64_t) CFBasicHashGetSize(ht, true), & __CFBasicHashTotalSize); |
| while (__CFBasicHashPeakSize < size_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakSize, size_now, & __CFBasicHashPeakSize)); |
| int64_t count_now = OSAtomicAdd64Barrier(1, & __CFBasicHashTotalCount); |
| while (__CFBasicHashPeakCount < count_now && !OSAtomicCompareAndSwap64Barrier(__CFBasicHashPeakCount, count_now, & __CFBasicHashPeakCount)); |
| OSAtomicAdd32Barrier(1, &__CFBasicHashSizes[ht->bits.num_buckets_idx]); |
| #endif |
| |
| return ht; |
| } |
| |
| |
