Skip to content

/ CF

Permalink
master

CF/CFBasicHash.c

Go to file
 
 
Cannot retrieve contributors at this time
1770 lines (1605 sloc) 75.4 KB
Raw Blame
/*
* Copyright (c) 2015 Apple Inc. All rights reserved.
*
* @APPLE_LICENSE_HEADER_START@
*
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this
* file.
*
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
*
* @APPLE_LICENSE_HEADER_END@
*/
/* CFBasicHash.m
Copyright (c) 2008-2014, Apple Inc. All rights reserved.
Responsibility: Christopher Kane
*/
#import "CFBasicHash.h"
#import <CoreFoundation/CFRuntime.h>
#import <CoreFoundation/CFSet.h>
#import <Block.h>
#import <math.h>
#if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED
#import <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) objc_assign_strongCast((id)value, (id *)location)
#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) {
CFAllocatorRef allocator = CFGetAllocator(ht);
void *new_mem = NULL;
if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
new_mem = auto_zone_allocate_object(objc_collectableZone(), count * elem_size, strong ? (compactable ? AUTO_POINTERS_ONLY : AUTO_MEMORY_SCANNED) : AUTO_UNSCANNED, false, false);
} else {
new_mem = CFAllocatorAllocate(allocator, count * elem_size, 0);
}
return new_mem;
}
CF_INLINE void *__CFBasicHashAllocateMemory2(CFAllocatorRef allocator, CFIndex count, CFIndex elem_size, Boolean strong, Boolean compactable) {
void *new_mem = NULL;
if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
new_mem = auto_zone_allocate_object(objc_collectableZone(), count * elem_size, strong ? (compactable ? AUTO_POINTERS_ONLY : AUTO_MEMORY_SCANNED) : AUTO_UNSCANNED, false, false);
} else {
new_mem = CFAllocatorAllocate(allocator, count * elem_size, 0);
}
return new_mem;
}
#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;
uint8_t hash_style:2;
uint8_t keys_offset:1;
uint8_t counts_offset:2;
uint8_t counts_width:2;
uint8_t hashes_offset:2;
uint8_t strong_values:1;
uint8_t strong_keys:1;
uint8_t weak_values:1;
uint8_t weak_keys:1;
uint8_t int_values:1;
uint8_t int_keys:1;
uint8_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) {
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) {
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);
if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
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);
if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
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);
if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
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, Boolean forFinalization) {
#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);
Boolean nullify = (!forFinalization || !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
CFBasicHashValue *old_values = NULL, *old_keys = NULL;
void *old_counts = NULL;
uintptr_t *old_hashes = NULL;
old_values = __CFBasicHashGetValues(ht);
if (nullify) __CFBasicHashSetValues(ht, NULL);
if (ht->bits.keys_offset) {
old_keys = __CFBasicHashGetKeys(ht);
if (nullify) __CFBasicHashSetKeys(ht, NULL);
}
if (ht->bits.counts_offset) {
old_counts = __CFBasicHashGetCounts(ht);
if (nullify) __CFBasicHashSetCounts(ht, NULL);
}
if (__CFBasicHashHasHashCache(ht)) {
old_hashes = __CFBasicHashGetHashes(ht);
if (nullify) __CFBasicHashSetHashes(ht, NULL);
}
if (nullify) {
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);
}
}
}
if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
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) {
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[bkt_idx] = old_hashes[idx];
}
}
}
}
CFAllocatorRef allocator = CFGetAllocator(ht);
if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
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, false);
}
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, true);
#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) && !(kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
Boolean strongKeys = CFBasicHashHasStrongKeys(src_ht) && !(kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator));
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));
if (kCFUseCollectableAllocator && !CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
ht->bits.strong_values = 0;
ht->bits.strong_keys = 0;
ht->bits.weak_values = 0;
ht->bits.weak_keys = 0;
}
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;
}