/*
* Copyright (c) 2009 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-2009, Apple Inc. All rights reserved.
Responsibility: Christopher Kane
*/
#import "CFBasicHash.h"
#import <CoreFoundation/CFRuntime.h>
#import <CoreFoundation/CFSet.h>
#import <Block.h>
#import <objc/objc.h>
#import <math.h>
#if DEPLOYMENT_TARGET_WINDOWS
#define __SetLastAllocationEventName(A, B) do { } while (0)
#else
#define __SetLastAllocationEventName(A, B) do { if (__CFOASafe && (A)) __CFSetLastAllocationEventName(A, B); } while (0)
#endif
#define GCRETAIN(A, B) kCFTypeSetCallBacks.retain(A, B)
#define GCRELEASE(A, B) kCFTypeSetCallBacks.release(A, B)
#define __AssignWithWriteBarrier(location, value) objc_assign_strongCast((id)value, (id *)location)
#define ENABLE_DTRACE_PROBES 0
#define ENABLE_MEMORY_COUNTERS 0
/*
// dtrace -h -s foo.d
// Note: output then changed by putting do/while around macro bodies and adding a cast of the arguments
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() \
__dtrace_isenabled$Cocoa_HashTable$rehash_end$v1()
#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() \
__dtrace_isenabled$Cocoa_HashTable$rehash_start$v1()
#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() \
__dtrace_isenabled$Cocoa_HashTable$hash_key$v1()
#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() \
__dtrace_isenabled$Cocoa_HashTable$probe_deleted$v1()
#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() \
__dtrace_isenabled$Cocoa_HashTable$probe_empty$v1()
#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() \
__dtrace_isenabled$Cocoa_HashTable$probe_valid$v1()
#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() \
__dtrace_isenabled$Cocoa_HashTable$probing_end$v1()
#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() \
__dtrace_isenabled$Cocoa_HashTable$probing_start$v1()
#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() \
__dtrace_isenabled$Cocoa_HashTable$test_equal$v1()
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$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$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
enum {
#if __LP64__
__CFBasicHashMarkerShift = 40 // 64 - 24
#else
__CFBasicHashMarkerShift = 8 // 32 - 24
#endif
};
typedef union {
uintptr_t weak;
id strong;
} CFBasicHashValue;
struct __CFBasicHash {
CFRuntimeBase base;
struct { // 128 bits
uint64_t hash_style:2;
uint64_t values2_offset:1;
uint64_t keys_offset:2;
uint64_t keys2_offset:2;
uint64_t counts_offset:3;
uint64_t orders_offset:3;
uint64_t hashes_offset:3;
uint64_t num_buckets_idx:6; /* index to number of buckets */
uint64_t used_buckets:42; /* number of used buckets */
uint64_t __0:2;
uint64_t finalized:1;
uint64_t fast_grow:1;
uint64_t strong_values:1;
uint64_t strong_values2:1;
uint64_t strong_keys:1;
uint64_t strong_keys2:1;
uint64_t marker:24;
uint64_t deleted:16;
uint64_t mutations:16;
} bits;
__strong const CFBasicHashCallbacks *callbacks;
void *pointers[1];
};
CF_INLINE CFBasicHashValue *__CFBasicHashGetValues(CFBasicHashRef ht) {
return (CFBasicHashValue *)ht->pointers[0];
}
CF_INLINE void __CFBasicHashSetValues(CFBasicHashRef ht, CFBasicHashValue *ptr) {
__AssignWithWriteBarrier(&ht->pointers[0], ptr);
}
CF_INLINE CFBasicHashValue *__CFBasicHashGetValues2(CFBasicHashRef ht) {
if (0 == ht->bits.values2_offset) HALT;
return (CFBasicHashValue *)ht->pointers[ht->bits.values2_offset];
}
CF_INLINE void __CFBasicHashSetValues2(CFBasicHashRef ht, CFBasicHashValue *ptr) {
if (0 == ht->bits.values2_offset) HALT;
__AssignWithWriteBarrier(&ht->pointers[ht->bits.values2_offset], ptr);
}
CF_INLINE CFBasicHashValue *__CFBasicHashGetKeys(CFBasicHashRef ht) {
if (0 == ht->bits.keys_offset) HALT;
return (CFBasicHashValue *)ht->pointers[ht->bits.keys_offset];
}
CF_INLINE void __CFBasicHashSetKeys(CFBasicHashRef ht, CFBasicHashValue *ptr) {
if (0 == ht->bits.keys_offset) HALT;
__AssignWithWriteBarrier(&ht->pointers[ht->bits.keys_offset], ptr);
}
CF_INLINE CFBasicHashValue *__CFBasicHashGetKeys2(CFBasicHashRef ht) {
if (0 == ht->bits.keys2_offset) HALT;
return (CFBasicHashValue *)ht->pointers[ht->bits.keys2_offset];
}
CF_INLINE void __CFBasicHashSetKeys2(CFBasicHashRef ht, CFBasicHashValue *ptr) {
if (0 == ht->bits.keys2_offset) HALT;
__AssignWithWriteBarrier(&ht->pointers[ht->bits.keys2_offset], ptr);
}
CF_INLINE uintptr_t *__CFBasicHashGetCounts(CFBasicHashRef ht) {
if (0 == ht->bits.counts_offset) HALT;
return (uintptr_t *)ht->pointers[ht->bits.counts_offset];
}
CF_INLINE void __CFBasicHashSetCounts(CFBasicHashRef ht, uintptr_t *ptr) {
if (0 == ht->bits.counts_offset) HALT;
__AssignWithWriteBarrier(&ht->pointers[ht->bits.counts_offset], ptr);
}
CF_INLINE uintptr_t *__CFBasicHashGetOrders(CFBasicHashRef ht) {
if (0 == ht->bits.orders_offset) HALT;
return (uintptr_t *)ht->pointers[ht->bits.orders_offset];
}
CF_INLINE void __CFBasicHashSetOrders(CFBasicHashRef ht, uintptr_t *ptr) {
if (0 == ht->bits.orders_offset) HALT;
__AssignWithWriteBarrier(&ht->pointers[ht->bits.orders_offset], ptr);
}
CF_INLINE uintptr_t *__CFBasicHashGetHashes(CFBasicHashRef ht) {
if (0 == ht->bits.hashes_offset) HALT;
return (uintptr_t *)ht->pointers[ht->bits.hashes_offset];
}
CF_INLINE void __CFBasicHashSetHashes(CFBasicHashRef ht, uintptr_t *ptr) {
if (0 == ht->bits.hashes_offset) HALT;
__AssignWithWriteBarrier(&ht->pointers[ht->bits.hashes_offset], ptr);
}
static uintptr_t __CFBasicHashNullCallback(CFBasicHashRef ht, uint8_t op, uintptr_t a1, uintptr_t a2, const CFBasicHashCallbacks *cb) {
switch (op) {
case kCFBasicHashCallbackOpCopyCallbacks: return (uintptr_t)&CFBasicHashNullCallbacks;
case kCFBasicHashCallbackOpFreeCallbacks: return 0;
case kCFBasicHashCallbackOpRetainValue:
case kCFBasicHashCallbackOpRetainValue2:
case kCFBasicHashCallbackOpRetainKey:
case kCFBasicHashCallbackOpRetainKey2: return a1;
case kCFBasicHashCallbackOpReleaseValue:
case kCFBasicHashCallbackOpReleaseValue2:
case kCFBasicHashCallbackOpReleaseKey:
case kCFBasicHashCallbackOpReleaseKey2: return 0;
case kCFBasicHashCallbackOpValueEqual:
case kCFBasicHashCallbackOpValue2Equal:
case kCFBasicHashCallbackOpKeyEqual:
case kCFBasicHashCallbackOpKey2Equal: return a1 == a2;
case kCFBasicHashCallbackOpHashKey:
case kCFBasicHashCallbackOpHashKey2: return a1;
case kCFBasicHashCallbackOpDescribeValue:
case kCFBasicHashCallbackOpDescribeValue2:
case kCFBasicHashCallbackOpDescribeKey:
case kCFBasicHashCallbackOpDescribeKey2: return (uintptr_t)CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("< }
return 0;
}
static uintptr_t __CFBasicHashStandardCallback(CFBasicHashRef ht, uint8_t op, uintptr_t a1, uintptr_t a2, const CFBasicHashCallbacks *cb) {
switch (op) {
case kCFBasicHashCallbackOpCopyCallbacks: return (uintptr_t)&CFBasicHashStandardCallbacks;
case kCFBasicHashCallbackOpFreeCallbacks: return 0;
case kCFBasicHashCallbackOpRetainValue: return (ht->bits.strong_values) ? (uintptr_t)GCRETAIN(kCFAllocatorSystemDefault, (CFTypeRef)a1) : (uintptr_t)CFRetain((CFTypeRef)a1);
case kCFBasicHashCallbackOpRetainValue2: return (ht->bits.strong_values2) ? (uintptr_t)GCRETAIN(kCFAllocatorSystemDefault, (CFTypeRef)a1) : (uintptr_t)CFRetain((CFTypeRef)a1);
case kCFBasicHashCallbackOpRetainKey: return (ht->bits.strong_keys) ? (uintptr_t)GCRETAIN(kCFAllocatorSystemDefault, (CFTypeRef)a1) : (uintptr_t)CFRetain((CFTypeRef)a1);
case kCFBasicHashCallbackOpRetainKey2: return (ht->bits.strong_keys2) ? (uintptr_t)GCRETAIN(kCFAllocatorSystemDefault, (CFTypeRef)a1) : (uintptr_t)CFRetain((CFTypeRef)a1);
case kCFBasicHashCallbackOpReleaseValue: if (ht->bits.strong_values) GCRELEASE(kCFAllocatorSystemDefault, (CFTypeRef)a1); else CFRelease((CFTypeRef)a1); return 0;
case kCFBasicHashCallbackOpReleaseValue2: if (ht->bits.strong_values2) GCRELEASE(kCFAllocatorSystemDefault, (CFTypeRef)a1); else CFRelease((CFTypeRef)a1); return 0;
case kCFBasicHashCallbackOpReleaseKey: if (ht->bits.strong_keys) GCRELEASE(kCFAllocatorSystemDefault, (CFTypeRef)a1); else CFRelease((CFTypeRef)a1); return 0;
case kCFBasicHashCallbackOpReleaseKey2: if (ht->bits.strong_keys2) GCRELEASE(kCFAllocatorSystemDefault, (CFTypeRef)a1); else CFRelease((CFTypeRef)a1); return 0;
case kCFBasicHashCallbackOpValueEqual:
case kCFBasicHashCallbackOpValue2Equal:
case kCFBasicHashCallbackOpKeyEqual:
case kCFBasicHashCallbackOpKey2Equal: return CFEqual((CFTypeRef)a1, (CFTypeRef)a2);
case kCFBasicHashCallbackOpHashKey:
case kCFBasicHashCallbackOpHashKey2: return (uintptr_t)CFHash((CFTypeRef)a1);
case kCFBasicHashCallbackOpDescribeValue:
case kCFBasicHashCallbackOpDescribeValue2:
case kCFBasicHashCallbackOpDescribeKey:
case kCFBasicHashCallbackOpDescribeKey2: return (uintptr_t)CFCopyDescription((CFTypeRef)a1);
}
return 0;
}
__private_extern__ const CFBasicHashCallbacks CFBasicHashNullCallbacks = {__CFBasicHashNullCallback};
__private_extern__ const CFBasicHashCallbacks CFBasicHashStandardCallbacks = {__CFBasicHashStandardCallback};
CF_INLINE uintptr_t __CFBasicHashImportValue(CFBasicHashRef ht, uintptr_t stack_value) {
return ht->callbacks->func(ht, kCFBasicHashCallbackOpRetainValue, stack_value, 0, ht->callbacks);
}
CF_INLINE uintptr_t __CFBasicHashImportValue2(CFBasicHashRef ht, uintptr_t stack_value) {
return ht->callbacks->func(ht, kCFBasicHashCallbackOpRetainValue2, stack_value, 0, ht->callbacks);
}
CF_INLINE uintptr_t __CFBasicHashImportKey(CFBasicHashRef ht, uintptr_t stack_key) {
return ht->callbacks->func(ht, kCFBasicHashCallbackOpRetainKey, stack_key, 0, ht->callbacks);
}
CF_INLINE uintptr_t __CFBasicHashImportKey2(CFBasicHashRef ht, uintptr_t stack_key) {
return ht->callbacks->func(ht, kCFBasicHashCallbackOpRetainKey2, stack_key, 0, ht->callbacks);
}
CF_INLINE void __CFBasicHashEjectValue(CFBasicHashRef ht, uintptr_t stack_value) {
ht->callbacks->func(ht, kCFBasicHashCallbackOpReleaseValue, stack_value, 0, ht->callbacks);
}
CF_INLINE void __CFBasicHashEjectValue2(CFBasicHashRef ht, uintptr_t stack_value) {
ht->callbacks->func(ht, kCFBasicHashCallbackOpReleaseValue2, stack_value, 0, ht->callbacks);
}
CF_INLINE void __CFBasicHashEjectKey(CFBasicHashRef ht, uintptr_t stack_key) {
ht->callbacks->func(ht, kCFBasicHashCallbackOpReleaseKey, stack_key, 0, ht->callbacks);
}
CF_INLINE void __CFBasicHashEjectKey2(CFBasicHashRef ht, uintptr_t stack_key) {
ht->callbacks->func(ht, kCFBasicHashCallbackOpReleaseKey2, stack_key, 0, ht->callbacks);
}
CF_INLINE Boolean __CFBasicHashTestEqualValue(CFBasicHashRef ht, uintptr_t stack_value_a, uintptr_t stack_value_b) {
return (Boolean)ht->callbacks->func(ht, kCFBasicHashCallbackOpValueEqual, stack_value_a, stack_value_b, ht->callbacks);
}
CF_INLINE Boolean __CFBasicHashTestEqualValue2(CFBasicHashRef ht, uintptr_t stack_value_a, uintptr_t stack_value_b) {
return (Boolean)ht->callbacks->func(ht, kCFBasicHashCallbackOpValue2Equal, stack_value_a, stack_value_b, ht->callbacks);
}
CF_INLINE Boolean __CFBasicHashTestEqualKey(CFBasicHashRef ht, uintptr_t stack_key_a, uintptr_t stack_key_b) {
COCOA_HASHTABLE_TEST_EQUAL(ht, stack_key_a, stack_key_b);
return (Boolean)ht->callbacks->func(ht, kCFBasicHashCallbackOpKeyEqual, stack_key_a, stack_key_b, ht->callbacks);
}
CF_INLINE Boolean __CFBasicHashTestEqualKey2(CFBasicHashRef ht, uintptr_t stack_key_a, uintptr_t stack_key_b) {
COCOA_HASHTABLE_TEST_EQUAL(ht, stack_key_a, stack_key_b);
return (Boolean)ht->callbacks->func(ht, kCFBasicHashCallbackOpKey2Equal, stack_key_a, stack_key_b, ht->callbacks);
}
CF_INLINE CFHashCode __CFBasicHashHashKey(CFBasicHashRef ht, uintptr_t stack_key) {
CFHashCode hash_code = (CFHashCode)ht->callbacks->func(ht, kCFBasicHashCallbackOpHashKey, stack_key, 0, ht->callbacks);
COCOA_HASHTABLE_HASH_KEY(ht, stack_key, hash_code);
return hash_code;
}
CF_INLINE CFHashCode __CFBasicHashHashKey2(CFBasicHashRef ht, uintptr_t stack_key) {
CFHashCode hash_code = (CFHashCode)ht->callbacks->func(ht, kCFBasicHashCallbackOpHashKey2, stack_key, 0, ht->callbacks);
COCOA_HASHTABLE_HASH_KEY(ht, stack_key, hash_code);
return hash_code;
}
CF_INLINE void *__CFBasicHashAllocateMemory(CFBasicHashRef ht, CFIndex count, CFIndex elem_size, Boolean strong) {
CFAllocatorRef allocator = CFGetAllocator(ht);
void *new_mem = NULL;
if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
new_mem = auto_zone_allocate_object(auto_zone(), count * elem_size, strong ? AUTO_MEMORY_SCANNED : AUTO_UNSCANNED, false, false);
} else {
new_mem = CFAllocatorAllocate(allocator, count * elem_size, 0);
}
if (!new_mem) HALT;
return new_mem;
}
// 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,
8485977589UL, 13730600407UL, 22216578047UL, 35947178479UL,
58163756537UL, 94110934997UL, 152274691561UL, 246385626107UL,
398660317687UL, 645045943807UL, 1043706260983UL, 1688752204787UL,
2732458465769UL, 4421210670577UL, 7153669136377UL,
11574879807461UL, 18728548943849UL, 30303428750843UL
#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
};
/* Primitive roots under 100 for the primes above
3: 2
7: 3 5
13: 2 6 7 11
23: 5 7 10 11 14 15 17 19 20 21
41: 6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
71: 7 11 13 21 22 28 31 33 35 42 44 47 52 53 55 56 59 61 62 63 65 67 68 69
127: 3 6 7 12 14 23 29 39 43 45 46 48 53 55 56 57 58 65 67 78 83 85 86 91 92 93 96 97
191: 19 21 22 28 29 33 35 42 44 47 53 56 57 58 61 62 63 71 73 74 76 83 87 88 89 91 93 94 95 99
251: 6 11 14 18 19 24 26 29 30 33 34 37 42 43 44 46 53 54 55 56 57 59 61 62 70 71 72 76 77 78 82 87 90 95 96 97 98 99
383: 5 10 11 13 15 20 22 26 30 33 35 37 39 40 41 44 45 47 52 53 59 60 61 66 70 74 77 78 79 80 82 83 85 88 89 90 91 94 95 97 99
631: 3 7 12 13 14 15 19 26 51 53 54 56 59 60 61 63 65 70 75 76 87 93 95 96 99
1087: 3 10 12 13 14 20 22 24 28 29 31 38 44 45 46 51 52 53 54 58 59 61 62 63 67 74 75 76 80 89 90 92 94 96 97 99
1723: 3 12 17 18 29 30 38 45 46 48 55 63 74 75 77 78 82 83 86 88 94 95
2803: 2 11 12 18 20 21 29 30 32 34 35 38 41 46 48 50 52 56 66 67 74 78 79 80 83 84 86 91 93 94 98 99
4523: 5 6 7 15 18 20 22 24 26 31 34 41 45 54 55 57 60 65 66 70 72 74 76 77 83 85 88 93 94 96 98
7351: 6 7 12 15 17 22 28 31 35 38 44 52 54 55 56 60 65 69 71 75 96
11959: 3 6 12 24 29 33 37 39 41 47 48 51 53 57 58 59 66 67 69 73 74 75 78 82 94 96
19447: 3 5 6 7 10 12 14 20 23 24 28 29 37 39 45 46 47 51 55 56 58 65 71 73 74 75 78 79 80 82 83 90 91 92 94 96
31231: 6 7 24 29 30 33 41 43 48 52 53 54 56 57 59 60 62 65 69 70 73 75 77 83 86
50683: 2 3 12 14 17 18 20 32 33 35 39 41 45 50 55 56 57 58 61 62 65 68 69 71 72 74 75 80 84 86 88 93 95
81919: 3 12 23 24 26 30 33 43 52 53 54 57 59 60 65 66 75 84 86 87 91 92 93 96 97
132607: 3 5 6 17 19 20 21 23 24 26 29 33 34 35 38 40 42 45 48 52 54 61 62 67 71 73 75 79 82 86 89 90 92
214519: 3 7 12 15 19 24 26 28 30 33 35 38 41 52 54 56 61 65 69 70 73 77 86 87 89 93 96 97
346607: 5 10 14 15 17 19 20 21 28 30 34 38 40 41 42 45 51 55 56 57 59 60 63 65 67 68 76 77 80 82 84 89 90 91 97
561109: 10 11 18 21 26 30 33 35 38 40 41 43 46 47 50 51 53 61 62 72 73 74 84 85 91 96
907759: 3 6 12 13 17 24 26 33 34 41 47 48 52 57 61 66 68 71 75 79 82 87 89 93 94
1468927: 3 5 6 11 20 21 22 23 24 26 35 40 42 45 48 51 52 54 58 71 73 75 77 79 86 88 90 92 93 94 95
2376191: 22 29 31 33 37 43 44 47 55 58 59 62 66 77 86 87 88 93 99
3845119: 3 11 12 13 15 23 24 30 37 42 43 44 51 52 53 54 55 57 65 73 84 86 87 88 89 92 94 96 97
6221311: 3 12 13 15 21 24 30 31 33 46 54 57 61 66 67 74 82 84 87 89 91 92 96
10066421: 3 10 11 12 17 18 19 21 23 27 39 40 41 48 50 56 58 60 61 66 68 71 72 73 74 75 76 77 83 85 86 87 92 94 95 97
16287743: 5 10 15 20 30 31 35 40 43 45 47 53 55 59 60 61 62 65 70 73 79 80 85 86 89 90 93 94 95
26354171: 2 6 7 8 10 17 18 21 22 23 24 26 30 35 38 40 50 51 53 59 62 63 66 67 68 69 71 72 74 77 78 83 84 85 87 88 90 91 96 98
42641881: 22 31 38 44 46 57 59 62 67 69 73 76 77 83 92 99
68996069: 2 3 8 10 11 12 14 15 17 18 21 26 27 32 37 38 40 43 44 46 47 48 50 53 55 56 58 60 61 62 66 67 68 69 70 72 75 77 82 84 85 87 89 90 93 98 99
111638519: 11 13 17 22 26 29 33 34 39 41 44 51 52 53 55 58 59 61 65 66 67 68 71 77 78 79 82 83 85 87 88 91 97 99
180634607: 5 10 15 19 20 23 30 31 35 37 38 40 43 45 46 47 55 57 60 62 65 69 70 74 76 79 80 85 86 89 90 92 93 94
292272623: 5 10 11 13 15 20 22 23 26 30 31 33 35 39 40 44 45 46 47 52 59 60 61 62 66 67 69 70 71 77 78 79 80 83 85 88 90 91 92 93 94 95 97 99
472907251: 2 10 12 14 17 18 29 31 37 46 50 60 61 65 68 70 78 82 84 85 90 91 94 98
765180413: 3 5 11 12 14 18 20 21 23 26 27 29 30 34 35 38 39 44 45 47 48 50 51 56 57 59 62 66 67 71 72 73 74 75 77 80 82 84 85 86 89 92 93 95 97 98 99
1238087663: 10 13 14 15 20 21 23 28 38 40 41 42 43 45 46 52 55 56 57 60 63 67 69 71 76 78 80 82 84 85 86 89 90 92
2003267557: 2 13 14 18 20 22 23 24 31 32 34 37 38 41 43 47 50 54 59 60 67 69 79 80 85 87 91 93 96
3241355263: 3 6 10 11 20 21 22 24 34 42 43 45 46 48 54 57 61 65 68 70 71 75 77 78 80 83 86 87 88 92 93 94
5244622819: 10 15 17 23 29 31 35 38 40 50 57 60 65 67 68 71 73 74 75 79 90 92 94
8485977589: 2 6 10 17 18 19 22 28 30 31 32 35 37 40 47 51 52 54 57 58 59 61 65 66 76 77 79 84 85 86 88 90 93 96 98
13730600407: 3 5 10 12 19 24 33 35 40 42 43 45 46 51 54 55 65 73 75 76 78 80 82 84 87 89 92 93 94 96
22216578047: 5 10 11 15 17 20 22 30 33 34 35 40 44 45 51 59 60 61 65 66 68 70 73 77 79 80 88 90 95 99
35947178479: 3 12 14 15 22 24 29 30 38 41 44 51 54 55 56 58 63 69 70 73 76 78 89 91 95 96 97 99
58163756537: 3 5 6 7 10 11 12 14 17 20 22 23 24 27 28 31 39 40 43 44 45 46 47 48 53 54 56 57 59 61 62 63 65 68 71 73 75 78 79 80 86 87 88 89 90 91 92 94 95 96 97 99
94110934997: 2 3 5 8 11 12 14 18 19 20 21 23 26 27 29 30 32 34 35 39 41 43 44 48 51 56 59 62 66 67 71 72 74 75 76 77 79 80 84 85 92 93 94 98 99
152274691561: 7 17 26 35 37 39 41 42 43 53 56 62 63 65 67 74 82 84 85 89 93 94
246385626107UL: 2 5 6 8 11 14 15 18 20 23 24 26 29 31 32 33 34 35 37 38 42 43 44 45 50 54 56 60 61 65 67 69 71 72 77 78 80 82 83 85 87 89 92 93 94 95 96 98 99
398660317687UL: 3 5 6 7 11 13 20 24 26 28 40 44 45 48 54 56 59 63 69 75 79 85 88 89 90 93 95 99
645045943807UL: 3 5 10 12 21 22 23 24 26 35 37 40 41 44 45 47 51 52 53 59 70 75 79 85 87 92 93 95 96 97 99
1043706260983UL: 3 7 11 24 28 29 (<= 32)
1688752204787UL: 2 5 6 7 8 13 18 20 21 22 23 24 28 32 (<= 32)
2732458465769UL: 3 6 11 12 13 15 17 19 21 22 23 24 26 27 30 31 (<= 32)
4421210670577UL: 5 (<= 9)
*/
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,
5244622578UL, 8485977737UL, 13730600347UL, 22216578100UL,
35947178453UL, 58163756541UL, 94110935011UL, 152274691274UL,
246385626296UL, 398660317578UL, 645045943559UL, 1043706261135UL,
1688752204693UL, 2732458465840UL, 4421210670552UL,
7153669136706UL, 11574879807265UL, 18728548943682UL
#endif
};
// to expose the load factor, expose this function to customization
CF_INLINE CFIndex __CFBasicHashGetCapacityForNumBuckets(CFBasicHashRef ht, CFIndex num_buckets_idx) {
return __CFBasicHashTableCapacities[num_buckets_idx];
#if 0
CFIndex num_buckets = __CFBasicHashTableSizes[num_buckets_idx];
if (num_buckets_idx < 8) {
double dep = 0.0545665730357293074; // (1 - (sqrt(5) - 1) / 2) / 7
double factor = 1.0 - (num_buckets_idx - 1) * dep;
return (CFIndex)floor(num_buckets * factor + 0.375); // 0.375 is intentional
}
double factor = 0.6180339887498948482; // (sqrt(5) - 1) / 2
return (CFIndex)floor(num_buckets * factor + 0.5);
#endif
}
CF_INLINE CFIndex __CFBasicHashGetNumBucketsIndexForCapacity(CFBasicHashRef ht, CFIndex capacity) {
for (CFIndex idx = 0; idx < 64; idx++) {
if (capacity <= __CFBasicHashGetCapacityForNumBuckets(ht, idx)) return idx;
}
HALT;
return 0;
}
__private_extern__ CFIndex CFBasicHashGetNumBuckets(CFBasicHashRef ht) {
return __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
}
__private_extern__ CFIndex CFBasicHashGetCapacity(CFBasicHashRef 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.
__private_extern__ CFBasicHashBucket CFBasicHashGetBucket(CFBasicHashRef ht, CFIndex idx) {
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
CFBasicHashBucket result;
result.idx = idx;
result.weak_value = __CFBasicHashGetValues(ht)[idx].weak;
result.weak_value2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht)[idx].weak : 0;
result.weak_key = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht)[idx].weak : result.weak_value;
result.weak_key2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht)[idx].weak : 0;
result.count = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht)[idx] : ((result.weak_key == empty || result.weak_key == deleted) ? 0 : 1);
result.order = (0 != ht->bits.orders_offset) ? __CFBasicHashGetOrders(ht)[idx] : 0;
return result;
}
// During rehashing of a mutable CFBasicHash, we know that there are no
// deleted slots and the keys have already been uniqued. When rehashing,
// if key_hash is non-0, we use it as the hash code.
static CFBasicHashBucket ___CFBasicHashFindBucket1(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash, Boolean rehashing) {
CFHashCode hash_code = key_hash ? key_hash : __CFBasicHashHashKey(ht, stack_key);
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht);
uintptr_t *hashes = (0 != ht->bits.hashes_offset) ? __CFBasicHashGetHashes(ht) : NULL;
uintptr_t num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
CFBasicHashBucket result = {kCFNotFound, deleted, 0, deleted, 0, 0, 0};
uintptr_t h1 = 0;
// Linear probing, with c = 1
// probe[0] = h1(k)
// probe[i] = (h1(k) + i * c) mod num_buckets, i = 1 .. num_buckets - 1
// h1(k) = k mod num_buckets
h1 = hash_code
COCOA_HASHTABLE_PROBING_START(ht, num_buckets);
uintptr_t probe = h1;
for (CFIndex idx = 0; idx < num_buckets; idx++) {
uintptr_t stack_curr = keys[probe].weak;
if (stack_curr == empty) {
COCOA_HASHTABLE_PROBE_EMPTY(ht, probe);
if (kCFNotFound == result.idx) {
result.idx = probe;
result.weak_value = empty;
result.weak_key = empty;
}
COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
return result;
} else if (__builtin_expect(!rehashing, 0)) {
if (stack_curr == deleted) {
COCOA_HASHTABLE_PROBE_DELETED(ht, probe);
if (kCFNotFound == result.idx) {
result.idx = probe;
}
} else {
COCOA_HASHTABLE_PROBE_VALID(ht, probe);
if (stack_curr == stack_key || ((!hashes || hashes[probe] == hash_code) && __CFBasicHashTestEqualKey(ht, stack_curr, stack_key))) {
COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
result.idx = probe;
result.weak_value = (0 != ht->bits.keys_offset) ? __CFBasicHashGetValues(ht)[probe].weak : stack_curr;
result.weak_value2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht)[probe].weak : 0;
result.weak_key = stack_curr;
result.weak_key2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht)[probe].weak : 0;
result.count = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht)[probe] : 1;
result.order = (0 != ht->bits.orders_offset) ? __CFBasicHashGetOrders(ht)[probe] : 1;
return result;
}
}
}
// Linear probing, with c = 1
probe += 1;
if (__builtin_expect(num_buckets <= probe, 0)) {
probe -= num_buckets;
}
}
COCOA_HASHTABLE_PROBING_END(ht, num_buckets);
return result; // all buckets full or deleted, return first deleted element which was found
}
static CFBasicHashBucket ___CFBasicHashFindBucket2(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash, Boolean rehashing) {
CFHashCode hash_code = key_hash ? key_hash : __CFBasicHashHashKey(ht, stack_key);
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht);
uintptr_t *hashes = (0 != ht->bits.hashes_offset) ? __CFBasicHashGetHashes(ht) : NULL;
uintptr_t num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
CFBasicHashBucket result = {kCFNotFound, deleted, 0, deleted, 0, 0, 0};
uintptr_t h1 = 0, h2 = 0;
// Double hashing
// probe[0] = h1(k)
// probe[i] = (h1(k) + i * h2(k)) mod num_buckets, i = 1 .. num_buckets - 1
// h1(k) = k mod num_buckets
// h2(k) = floor(k / num_buckets) mod num_buckets
h1 = hash_code h2 = (hash_code / num_buckets) if (0 == h2) h2 = num_buckets - 1;
COCOA_HASHTABLE_PROBING_START(ht, num_buckets);
uintptr_t probe = h1;
for (CFIndex idx = 0; idx < num_buckets; idx++) {
uintptr_t stack_curr = keys[probe].weak;
if (stack_curr == empty) {
COCOA_HASHTABLE_PROBE_EMPTY(ht, probe);
if (kCFNotFound == result.idx) {
result.idx = probe;
result.weak_value = empty;
result.weak_key = empty;
}
COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
return result;
} else if (__builtin_expect(!rehashing, 0)) {
if (stack_curr == deleted) {
COCOA_HASHTABLE_PROBE_DELETED(ht, probe);
if (kCFNotFound == result.idx) {
result.idx = probe;
}
} else {
COCOA_HASHTABLE_PROBE_VALID(ht, probe);
if (stack_curr == stack_key || ((!hashes || hashes[probe] == hash_code) && __CFBasicHashTestEqualKey(ht, stack_curr, stack_key))) {
COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
result.idx = probe;
result.weak_value = (0 != ht->bits.keys_offset) ? __CFBasicHashGetValues(ht)[probe].weak : stack_curr;
result.weak_value2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht)[probe].weak : 0;
result.weak_key = stack_curr;
result.weak_key2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht)[probe].weak : 0;
result.count = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht)[probe] : 1;
result.order = (0 != ht->bits.orders_offset) ? __CFBasicHashGetOrders(ht)[probe] : 1;
return result;
}
}
}
// Double hashing
probe += h2;
if (__builtin_expect(num_buckets <= probe, 1)) {
probe -= num_buckets;
}
}
COCOA_HASHTABLE_PROBING_END(ht, num_buckets);
return result; // all buckets full or deleted, return first deleted element which was found
}
static CFBasicHashBucket ___CFBasicHashFindBucket3(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash, Boolean rehashing) {
CFHashCode hash_code = key_hash ? key_hash : __CFBasicHashHashKey(ht, stack_key);
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht);
uintptr_t *hashes = (0 != ht->bits.hashes_offset) ? __CFBasicHashGetHashes(ht) : NULL;
uintptr_t num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
CFBasicHashBucket result = {kCFNotFound, deleted, 0, deleted, 0, 0, 0};
uintptr_t h1 = 0, h2 = 0, pr = 0;
// Improved exponential hashing
// probe[0] = h1(k)
// probe[i] = (h1(k) + pr(k)^i * h2(k)) mod num_buckets, i = 1 .. num_buckets - 1
// h1(k) = k mod num_buckets
// h2(k) = floor(k / num_buckets) mod num_buckets
// note: h2(k) has the effect of rotating the sequence if it is constant
// note: pr(k) is any primitive root of num_buckets, varying this gives different sequences
h1 = hash_code h2 = (hash_code / num_buckets) if (0 == h2) h2 = num_buckets - 1;
pr = __CFBasicHashPrimitiveRoots[ht->bits.num_buckets_idx];
COCOA_HASHTABLE_PROBING_START(ht, num_buckets);
uintptr_t probe = h1, acc = pr;
for (CFIndex idx = 0; idx < num_buckets; idx++) {
uintptr_t stack_curr = keys[probe].weak;
if (stack_curr == empty) {
COCOA_HASHTABLE_PROBE_EMPTY(ht, probe);
if (kCFNotFound == result.idx) {
result.idx = probe;
result.weak_value = empty;
result.weak_key = empty;
}
COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
return result;
} else if (__builtin_expect(!rehashing, 0)) {
if (stack_curr == deleted) {
COCOA_HASHTABLE_PROBE_DELETED(ht, probe);
if (kCFNotFound == result.idx) {
result.idx = probe;
}
} else {
COCOA_HASHTABLE_PROBE_VALID(ht, probe);
if (stack_curr == stack_key || ((!hashes || hashes[probe] == hash_code) && __CFBasicHashTestEqualKey(ht, stack_curr, stack_key))) {
COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
result.idx = probe;
result.weak_value = (0 != ht->bits.keys_offset) ? __CFBasicHashGetValues(ht)[probe].weak : stack_curr;
result.weak_value2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht)[probe].weak : 0;
result.weak_key = stack_curr;
result.weak_key2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht)[probe].weak : 0;
result.count = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht)[probe] : 1;
result.order = (0 != ht->bits.orders_offset) ? __CFBasicHashGetOrders(ht)[probe] : 1;
return result;
}
}
}
// Improved exponential hashing
probe = h1 + h2 * acc;
if (__builtin_expect(num_buckets <= probe, 1)) {
probe = probe }
acc = acc * pr;
if (__builtin_expect(num_buckets <= acc, 1)) {
acc = acc }
}
COCOA_HASHTABLE_PROBING_END(ht, num_buckets);
return result; // all buckets full or deleted, return first deleted element which was found
}
CF_INLINE CFBasicHashBucket ___CFBasicHashFindBucket(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t key_hash, Boolean rehashing) {
switch (ht->bits.hash_style) {
case __kCFBasicHashLinearHashingValue:
return ___CFBasicHashFindBucket1(ht, stack_key, 0, rehashing);
case __kCFBasicHashDoubleHashingValue:
return ___CFBasicHashFindBucket2(ht, stack_key, 0, rehashing);
case __kCFBasicHashExponentialHashingValue:
return ___CFBasicHashFindBucket3(ht, stack_key, 0, rehashing);
}
HALT;
CFBasicHashBucket result = {kCFNotFound, 0, 0, 0};
return result;
}
CF_INLINE CFBasicHashBucket __CFBasicHashFindBucket(CFBasicHashRef ht, uintptr_t stack_key) {
if (0 == ht->bits.num_buckets_idx) {
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift);
CFBasicHashBucket result = {kCFNotFound, empty, empty, 0};
return result;
}
return ___CFBasicHashFindBucket(ht, stack_key, 0, false);
}
__private_extern__ CFBasicHashBucket CFBasicHashFindBucket(CFBasicHashRef ht, uintptr_t stack_key) {
return __CFBasicHashFindBucket(ht, stack_key);
}
__private_extern__ CFOptionFlags CFBasicHashGetFlags(CFBasicHashRef ht) {
CFOptionFlags flags = (ht->bits.hash_style << 13);
if (ht->bits.strong_values) flags |= kCFBasicHashStrongValues;
if (ht->bits.strong_values2) flags |= kCFBasicHashStrongValues2;
if (ht->bits.strong_keys) flags |= kCFBasicHashStrongKeys;
if (ht->bits.strong_keys2) flags |= kCFBasicHashStrongKeys2;
if (ht->bits.fast_grow) flags |= kCFBasicHashAggressiveGrowth;
if (ht->bits.values2_offset) flags |= kCFBasicHashHasValues2;
if (ht->bits.keys_offset) flags |= kCFBasicHashHasKeys;
if (ht->bits.keys2_offset) flags |= kCFBasicHashHasKeys2;
if (ht->bits.counts_offset) flags |= kCFBasicHashHasCounts;
if (ht->bits.orders_offset) flags |= kCFBasicHashHasOrder;
if (ht->bits.hashes_offset) flags |= kCFBasicHashHasHashCache;
return flags;
}
__private_extern__ CFIndex CFBasicHashGetCount(CFBasicHashRef ht) {
if (0 != ht->bits.counts_offset) {
CFIndex total = 0L;
CFIndex cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
uintptr_t *counts = __CFBasicHashGetCounts(ht);
for (CFIndex idx = 0; idx < cnt; idx++) {
total += counts[idx];
}
return total;
}
return (CFIndex)ht->bits.used_buckets;
}
__private_extern__ CFIndex CFBasicHashGetCountOfKey(CFBasicHashRef ht, uintptr_t stack_key) {
if (0L == ht->bits.used_buckets) {
return 0L;
}
return __CFBasicHashFindBucket(ht, stack_key).count;
}
__private_extern__ CFIndex CFBasicHashGetCountOfValue(CFBasicHashRef ht, uintptr_t stack_value) {
if (0L == ht->bits.used_buckets) {
return 0L;
}
if (!(0 != 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;
}
__private_extern__ Boolean CFBasicHashesAreEqual(CFBasicHashRef ht1, CFBasicHashRef 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 ((0 != 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;
}
__private_extern__ void CFBasicHashApply(CFBasicHashRef 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--;
}
}
}
__private_extern__ void CFBasicHashGetElements(CFBasicHashRef ht, CFIndex bufferslen, uintptr_t *weak_values, uintptr_t *weak_values2, uintptr_t *weak_keys, uintptr_t *weak_keys2) {
CFIndex used = (CFIndex)ht->bits.used_buckets, cnt = (CFIndex)__CFBasicHashTableSizes[ht->bits.num_buckets_idx];
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
CFBasicHashValue *values = __CFBasicHashGetValues(ht);
CFBasicHashValue *values2 = (0 != ht->bits.values2_offset) ? __CFBasicHashGetValues2(ht) : NULL;
CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : NULL;
CFBasicHashValue *keys2 = (0 != ht->bits.keys2_offset) ? __CFBasicHashGetKeys2(ht) : NULL;
uintptr_t *counts = (0 != ht->bits.counts_offset) ? __CFBasicHashGetCounts(ht) : NULL;
CFIndex offset = 0;
for (CFIndex idx = 0; 0 < used && idx < cnt && offset < bufferslen; idx++) {
uintptr_t weak_key = keys ? keys[idx].weak : values[idx].weak;
uintptr_t count = counts ? counts[idx] : ((weak_key == empty || weak_key == deleted) ? 0 : 1);
if (0 < count) {
used--;
for (CFIndex cnt = count; cnt-- && offset < bufferslen;) {
if (weak_values) { weak_values[offset] = values[idx].weak; }
if (weak_values2) { weak_values2[offset] = values2 ? values2[idx].weak : 0; }
if (weak_keys) { weak_keys[offset] = weak_key; }
if (weak_keys2) { weak_keys2[offset] = keys2 ? keys2[idx].weak : 0; }
offset++;
}
}
}
}
__private_extern__ unsigned long __CFBasicHashFastEnumeration(CFBasicHashRef 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 + (__LP64__ ? 1 : 3);
}
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
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
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_values2 = NULL, *old_keys = NULL, *old_keys2 = NULL;
uintptr_t *old_counts = NULL, *old_orders = NULL, *old_hashes = NULL;
old_values = __CFBasicHashGetValues(ht);
if (nullify) __CFBasicHashSetValues(ht, NULL);
if (0 != ht->bits.values2_offset) {
old_values2 = __CFBasicHashGetValues2(ht);
if (nullify) __CFBasicHashSetValues2(ht, NULL);
}
if (0 != ht->bits.keys_offset) {
old_keys = __CFBasicHashGetKeys(ht);
if (nullify) __CFBasicHashSetKeys(ht, NULL);
}
if (0 != ht->bits.keys2_offset) {
old_keys2 = __CFBasicHashGetKeys2(ht);
if (nullify) __CFBasicHashSetKeys2(ht, NULL);
}
if (0 != ht->bits.counts_offset) {
old_counts = __CFBasicHashGetCounts(ht);
if (nullify) __CFBasicHashSetCounts(ht, NULL);
}
if (0 != ht->bits.orders_offset) {
old_orders = __CFBasicHashGetOrders(ht);
if (nullify) __CFBasicHashSetOrders(ht, NULL);
}
if (0 != ht->bits.hashes_offset) {
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.marker = 0;
ht->bits.deleted = 0;
}
if (ht->callbacks != &CFBasicHashNullCallbacks) {
CFBasicHashValue *keys = old_keys ? old_keys : old_values;
for (CFIndex idx = 0; idx < old_num_buckets; idx++) {
uintptr_t stack_key = keys[idx].weak;
if (stack_key != empty && stack_key != deleted) {
__CFBasicHashEjectValue(ht, old_values[idx].weak);
if (old_values2) {
__CFBasicHashEjectValue2(ht, old_values2[idx].weak);
}
if (old_keys) {
__CFBasicHashEjectKey(ht, old_keys[idx].weak);
}
if (old_keys2) {
__CFBasicHashEjectKey2(ht, old_keys2[idx].weak);
}
}
}
}
if (forFinalization) {
ht->callbacks->func(ht, kCFBasicHashCallbackOpFreeCallbacks, (uintptr_t)allocator, 0, ht->callbacks);
}
if (!CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
CFAllocatorDeallocate(allocator, old_values);
CFAllocatorDeallocate(allocator, old_values2);
CFAllocatorDeallocate(allocator, old_keys);
CFAllocatorDeallocate(allocator, old_keys2);
CFAllocatorDeallocate(allocator, old_counts);
CFAllocatorDeallocate(allocator, old_orders);
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_values2 = NULL, *new_keys = NULL, *new_keys2 = NULL;
uintptr_t *new_counts = NULL, *new_orders = NULL, *new_hashes = NULL;
if (0 < new_num_buckets) {
new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_values);
__SetLastAllocationEventName(new_values, "CFBasicHash (value-store)");
if (0 != ht->bits.values2_offset) {
new_values2 = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_values2);
__SetLastAllocationEventName(new_values2, "CFBasicHash (value2-store)");
}
if (0 != ht->bits.keys_offset) {
new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_keys);
__SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)");
}
if (0 != ht->bits.keys2_offset) {
new_keys2 = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_keys2);
__SetLastAllocationEventName(new_keys2, "CFBasicHash (key2-store)");
}
if (0 != ht->bits.counts_offset) {
new_counts = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
__SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)");
memset(new_counts, 0, new_num_buckets * sizeof(uintptr_t));
}
if (0 != ht->bits.orders_offset) {
new_orders = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
__SetLastAllocationEventName(new_orders, "CFBasicHash (order-store)");
memset(new_orders, 0, new_num_buckets * sizeof(uintptr_t));
}
if (0 != ht->bits.hashes_offset) {
new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
__SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)");
memset(new_hashes, 0, new_num_buckets * sizeof(uintptr_t));
}
}
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
// if we knew the allocations were coming from already-cleared memory, and the marker was still 0, we could skip all this next stuff
for (CFIndex idx = 0; idx < new_num_buckets; idx++) {
if (ht->bits.strong_values) new_values[idx].strong = (id)empty; else new_values[idx].weak = empty;
if (new_values2) {
if (ht->bits.strong_values2) new_values2[idx].strong = (id)empty; else new_values2[idx].weak = empty;
}
if (new_keys) {
if (ht->bits.strong_keys) new_keys[idx].strong = (id)empty; else new_keys[idx].weak = empty;
}
if (new_keys2) {
if (ht->bits.strong_keys2) new_keys2[idx].strong = (id)empty; else new_keys2[idx].weak = empty;
}
}
ht->bits.num_buckets_idx = new_num_buckets_idx;
ht->bits.deleted = 0;
CFBasicHashValue *old_values = NULL, *old_values2 = NULL, *old_keys = NULL, *old_keys2 = NULL;
uintptr_t *old_counts = NULL, *old_orders = NULL, *old_hashes = NULL;
old_values = __CFBasicHashGetValues(ht);
__CFBasicHashSetValues(ht, new_values);
if (0 != ht->bits.values2_offset) {
old_values2 = __CFBasicHashGetValues2(ht);
__CFBasicHashSetValues2(ht, new_values2);
}
if (0 != ht->bits.keys_offset) {
old_keys = __CFBasicHashGetKeys(ht);
__CFBasicHashSetKeys(ht, new_keys);
}
if (0 != ht->bits.keys2_offset) {
old_keys2 = __CFBasicHashGetKeys2(ht);
__CFBasicHashSetKeys2(ht, new_keys2);
}
if (0 != ht->bits.counts_offset) {
old_counts = __CFBasicHashGetCounts(ht);
__CFBasicHashSetCounts(ht, new_counts);
}
if (0 != ht->bits.orders_offset) {
old_orders = __CFBasicHashGetOrders(ht);
__CFBasicHashSetOrders(ht, new_orders);
}
if (0 != ht->bits.hashes_offset) {
old_hashes = __CFBasicHashGetHashes(ht);
__CFBasicHashSetHashes(ht, new_hashes);
}
if (0 < old_num_buckets) {
CFBasicHashValue *keys = old_keys ? old_keys : old_values;
for (CFIndex idx = 0; idx < old_num_buckets; idx++) {
uintptr_t stack_key = keys[idx].weak;
if (stack_key != empty && stack_key != deleted) {
CFBasicHashBucket bkt = ___CFBasicHashFindBucket(ht, stack_key, old_hashes ? old_hashes[idx] : 0, true);
uintptr_t stack_value = old_values[idx].weak;
if (ht->bits.strong_values) new_values[bkt.idx].strong = (id)stack_value; else new_values[bkt.idx].weak = stack_value;
if (old_values2) {
if (ht->bits.strong_values2) new_values2[bkt.idx].strong = (id)old_values2[idx].weak; else new_values2[bkt.idx].weak = old_values2[idx].weak;
}
if (old_keys) {
if (ht->bits.strong_keys) new_keys[bkt.idx].strong = (id)stack_key; else new_keys[bkt.idx].weak = stack_key;
}
if (old_keys2) {
if (ht->bits.strong_keys2) new_keys2[bkt.idx].strong = (id)old_keys2[idx].weak; else new_keys2[bkt.idx].weak = old_keys2[idx].weak;
}
if (old_counts) {
new_counts[bkt.idx] = old_counts[idx];
}
if (old_orders) {
new_orders[bkt.idx] = old_orders[idx];
}
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_values2);
CFAllocatorDeallocate(allocator, old_keys);
CFAllocatorDeallocate(allocator, old_keys2);
CFAllocatorDeallocate(allocator, old_counts);
CFAllocatorDeallocate(allocator, old_orders);
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
}
__private_extern__ 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 __CFBasicHashFindNewMarker(CFBasicHashRef ht, uintptr_t stack_key) {
uintptr_t marker = ht->bits.marker;
uintptr_t empty = (marker << __CFBasicHashMarkerShift), deleted = ~empty;
CFBasicHashValue *keys = (0 != ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht);
Boolean strong = (0 != ht->bits.keys_offset) ? ht->bits.strong_keys : ht->bits.strong_values;
CFIndex cnt = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
if (0 == marker) marker = 4096;
again:;
marker++;
if ((1UL << 26) <= marker) HALT;
uintptr_t new_empty = (marker << __CFBasicHashMarkerShift), new_deleted = ~new_empty;
if (stack_key == new_empty || stack_key == new_deleted) {
goto again;
}
for (CFIndex idx = 0; idx < cnt; idx++) {
uintptr_t stack_curr = strong ? (uintptr_t)keys[idx].strong : keys[idx].weak;
if (stack_curr == new_empty || stack_curr == new_deleted) {
goto again;
}
}
for (CFIndex idx = 0; idx < cnt; idx++) {
uintptr_t stack_curr = strong ? (uintptr_t)keys[idx].strong : keys[idx].weak;
if (stack_curr == empty) {
if (strong) keys[idx].strong = (id)new_empty; else keys[idx].weak = new_empty;
} else if (stack_curr == deleted) {
if (strong) keys[idx].strong = (id)new_deleted; else keys[idx].weak = new_deleted;
}
}
ht->bits.marker = marker;
}
static void __CFBasicHashAddValue(CFBasicHashRef ht, CFBasicHashBucket bkt, uintptr_t stack_key, uintptr_t stack_key2, uintptr_t stack_value, uintptr_t stack_value2) {
ht->bits.mutations++;
stack_value = __CFBasicHashImportValue(ht, stack_value);
if (0 != ht->bits.keys_offset) {
stack_key = __CFBasicHashImportKey(ht, stack_key);
} else {
stack_key = stack_value;
}
if (0 != ht->bits.values2_offset) {
stack_value2 = __CFBasicHashImportValue2(ht, stack_value2);
}
if (0 != ht->bits.keys2_offset) {
stack_key2 = __CFBasicHashImportKey2(ht, stack_key2);
}
if (CFBasicHashGetCapacity(ht) < ht->bits.used_buckets + 1) {
__CFBasicHashRehash(ht, 1);
bkt = ___CFBasicHashFindBucket(ht, stack_key, 0, true);
}
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
if (bkt.weak_key == deleted) {
ht->bits.deleted--;
}
if (stack_key == empty || stack_key == deleted) {
__CFBasicHashFindNewMarker(ht, stack_key);
}
CFBasicHashValue *value = &(__CFBasicHashGetValues(ht)[bkt.idx]);
if (ht->bits.strong_values) value->strong = (id)stack_value; else value->weak = stack_value;
if (0 != ht->bits.values2_offset) {
CFBasicHashValue *value2 = &(__CFBasicHashGetValues2(ht)[bkt.idx]);
if (ht->bits.strong_values2) value2->strong = (id)stack_value2; else value2->weak = stack_value2;
}
if (0 != ht->bits.keys_offset) {
CFBasicHashValue *key = &(__CFBasicHashGetKeys(ht)[bkt.idx]);
if (ht->bits.strong_keys) key->strong = (id)stack_key; else key->weak = stack_key;
}
if (0 != ht->bits.keys2_offset) {
CFBasicHashValue *key2 = &(__CFBasicHashGetKeys2(ht)[bkt.idx]);
if (ht->bits.strong_keys2) key2->strong = (id)stack_key2; else key2->weak = stack_key2;
}
if (0 != ht->bits.counts_offset) {
__CFBasicHashGetCounts(ht)[bkt.idx] = 1;
}
if (0 != ht->bits.orders_offset) {
__CFBasicHashGetOrders(ht)[bkt.idx] = 0;
}
if (ht->bits.hashes_offset) {
__CFBasicHashGetHashes(ht)[bkt.idx] = __CFBasicHashHashKey(ht, stack_key);
}
ht->bits.used_buckets++;
}
static void __CFBasicHashReplaceValue(CFBasicHashRef ht, CFBasicHashBucket bkt, uintptr_t stack_key, uintptr_t stack_key2, uintptr_t stack_value, uintptr_t stack_value2) {
ht->bits.mutations++;
stack_value = __CFBasicHashImportValue(ht, stack_value);
if (0 != ht->bits.keys_offset) {
stack_key = __CFBasicHashImportKey(ht, stack_key);
} else {
stack_key = stack_value;
}
if (0 != ht->bits.values2_offset) {
stack_value2 = __CFBasicHashImportValue2(ht, stack_value2);
}
if (0 != ht->bits.keys2_offset) {
stack_key2 = __CFBasicHashImportKey2(ht, stack_key2);
}
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
if (stack_key == empty || stack_key == deleted) {
__CFBasicHashFindNewMarker(ht, stack_key);
}
CFBasicHashValue *value = &(__CFBasicHashGetValues(ht)[bkt.idx]);
uintptr_t old_value = value->weak;
if (ht->bits.strong_values) value->strong = (id)stack_value; else value->weak = stack_value;
__CFBasicHashEjectValue(ht, old_value);
if (0 != ht->bits.values2_offset) {
CFBasicHashValue *value2 = &(__CFBasicHashGetValues2(ht)[bkt.idx]);
uintptr_t old_value2 = value2->weak;
if (ht->bits.strong_values2) value2->strong = (id)stack_value2; else value2->weak = stack_value2;
__CFBasicHashEjectValue2(ht, old_value2);
}
if (0 != ht->bits.keys_offset) {
CFBasicHashValue *key = &(__CFBasicHashGetKeys(ht)[bkt.idx]);
uintptr_t old_key = key->weak;
if (ht->bits.strong_keys) key->strong = (id)stack_key; else key->weak = stack_key;
__CFBasicHashEjectKey(ht, old_key);
}
if (0 != ht->bits.keys2_offset) {
CFBasicHashValue *key2 = &(__CFBasicHashGetKeys2(ht)[bkt.idx]);
uintptr_t old_key2 = key2->weak;
if (ht->bits.strong_keys2) key2->strong = (id)stack_key2; else key2->weak = stack_key2;
__CFBasicHashEjectKey2(ht, old_key2);
}
}
static void __CFBasicHashRemoveValue(CFBasicHashRef ht, CFBasicHashBucket bkt, uintptr_t stack_key, uintptr_t stack_key2) {
ht->bits.mutations++;
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
CFBasicHashValue *value = &(__CFBasicHashGetValues(ht)[bkt.idx]);
uintptr_t old_value = value->weak;
if (ht->bits.strong_values) value->strong = (id)deleted; else value->weak = deleted;
__CFBasicHashEjectValue(ht, old_value);
if (0 != ht->bits.values2_offset) {
CFBasicHashValue *value2 = &(__CFBasicHashGetValues2(ht)[bkt.idx]);
uintptr_t old_value2 = value2->weak;
if (ht->bits.strong_values2) value2->strong = (id)deleted; else value2->weak = deleted;
__CFBasicHashEjectValue2(ht, old_value2);
}
if (0 != ht->bits.keys_offset) {
CFBasicHashValue *key = &(__CFBasicHashGetKeys(ht)[bkt.idx]);
uintptr_t old_key = key->weak;
if (ht->bits.strong_keys) key->strong = (id)deleted; else key->weak = deleted;
__CFBasicHashEjectKey(ht, old_key);
}
if (0 != ht->bits.keys2_offset) {
CFBasicHashValue *key2 = &(__CFBasicHashGetKeys2(ht)[bkt.idx]);
uintptr_t old_key2 = key2->weak;
if (ht->bits.strong_keys2) key2->strong = (id)deleted; else key2->weak = deleted;
__CFBasicHashEjectKey2(ht, old_key2);
}
if (0 != ht->bits.counts_offset) {
__CFBasicHashGetCounts(ht)[bkt.idx] = 0;
}
if (0 != ht->bits.orders_offset) {
__CFBasicHashGetOrders(ht)[bkt.idx] = 0;
}
if (ht->bits.hashes_offset) {
__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);
}
}
__private_extern__ void CFBasicHashAddValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
if (!CFBasicHashIsMutable(ht)) HALT;
CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
if (0 < bkt.count) {
ht->bits.mutations++;
if (0 != ht->bits.counts_offset) {
__CFBasicHashGetCounts(ht)[bkt.idx]++;
}
} else {
__CFBasicHashAddValue(ht, bkt, stack_key, 0, stack_value, 0);
}
}
__private_extern__ void CFBasicHashReplaceValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
if (!CFBasicHashIsMutable(ht)) HALT;
CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
if (0 < bkt.count) {
__CFBasicHashReplaceValue(ht, bkt, stack_key, 0, stack_value, 0);
}
}
__private_extern__ void CFBasicHashSetValue(CFBasicHashRef ht, uintptr_t stack_key, uintptr_t stack_value) {
if (!CFBasicHashIsMutable(ht)) HALT;
CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
if (0 < bkt.count) {
__CFBasicHashReplaceValue(ht, bkt, stack_key, 0, stack_value, 0);
} else {
__CFBasicHashAddValue(ht, bkt, stack_key, 0, stack_value, 0);
}
}
__private_extern__ CFIndex CFBasicHashRemoveValue(CFBasicHashRef ht, uintptr_t stack_key) {
if (!CFBasicHashIsMutable(ht)) HALT;
CFBasicHashBucket bkt = __CFBasicHashFindBucket(ht, stack_key);
if (1 < bkt.count) {
ht->bits.mutations++;
if (0 != ht->bits.counts_offset) {
__CFBasicHashGetCounts(ht)[bkt.idx]--;
}
} else if (0 < bkt.count) {
__CFBasicHashRemoveValue(ht, bkt, stack_key, 0);
}
return bkt.count;
}
__private_extern__ void CFBasicHashRemoveAllValues(CFBasicHashRef ht) {
if (!CFBasicHashIsMutable(ht)) HALT;
if (0 == ht->bits.num_buckets_idx) return;
__CFBasicHashDrain(ht, false);
}
__private_extern__ size_t CFBasicHashGetSize(CFBasicHashRef ht, Boolean total) {
size_t size = sizeof(struct __CFBasicHash);
if (0 != ht->bits.values2_offset) size += sizeof(CFBasicHashValue *);
if (0 != ht->bits.keys_offset) size += sizeof(CFBasicHashValue *);
if (0 != ht->bits.keys2_offset) size += sizeof(CFBasicHashValue *);
if (0 != ht->bits.counts_offset) size += sizeof(uintptr_t *);
if (0 != ht->bits.orders_offset) size += sizeof(uintptr_t *);
if (0 != ht->bits.hashes_offset) 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 (0 != ht->bits.values2_offset) size += malloc_size(__CFBasicHashGetValues2(ht));
if (0 != ht->bits.keys_offset) size += malloc_size(__CFBasicHashGetKeys(ht));
if (0 != ht->bits.keys2_offset) size += malloc_size(__CFBasicHashGetKeys2(ht));
if (0 != ht->bits.counts_offset) size += malloc_size(__CFBasicHashGetCounts(ht));
if (0 != ht->bits.orders_offset) size += malloc_size(__CFBasicHashGetOrders(ht));
if (0 != ht->bits.hashes_offset) size += malloc_size(__CFBasicHashGetHashes(ht));
size += malloc_size((void *)ht->callbacks);
}
}
return size;
}
__private_extern__ CFStringRef CFBasicHashCopyDescription(CFBasicHashRef ht, Boolean detailed, CFStringRef prefix, CFStringRef entryPrefix, Boolean describeElements) {
CFMutableStringRef result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
CFStringAppendFormat(result, NULL, CFSTR(" if (detailed) {
const char *cb_type = "custom";
if (&CFBasicHashNullCallbacks == ht->callbacks) {
cb_type = "null";
} else if (&CFBasicHashStandardCallbacks == ht->callbacks) {
cb_type = "standard";
}
CFStringAppendFormat(result, NULL, CFSTR(" CFStringAppendFormat(result, NULL, CFSTR(" uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
CFStringAppendFormat(result, NULL, CFSTR(" CFStringAppendFormat(result, NULL, CFSTR(" CFStringAppendFormat(result, NULL, CFSTR(" }
CFStringAppendFormat(result, NULL, CFSTR(" CFBasicHashApply(ht, ^(CFBasicHashBucket bkt) {
CFStringRef vDesc = NULL, kDesc = NULL;
CFBasicHashCallbackType cb = ht->callbacks->func;
if (!describeElements) cb = __CFBasicHashNullCallback;
vDesc = (CFStringRef)cb(ht, kCFBasicHashCallbackOpDescribeValue, bkt.weak_value, 0, ht->callbacks);
if (0 != ht->bits.keys_offset) {
kDesc = (CFStringRef)cb(ht, kCFBasicHashCallbackOpDescribeKey, bkt.weak_key, 0, ht->callbacks);
}
if ((0 != ht->bits.keys_offset) && (0 != ht->bits.counts_offset)) {
CFStringAppendFormat(result, NULL, CFSTR(" } else if (0 != ht->bits.keys_offset) {
CFStringAppendFormat(result, NULL, CFSTR(" } else if (0 != ht->bits.counts_offset) {
CFStringAppendFormat(result, NULL, CFSTR(" } else {
CFStringAppendFormat(result, NULL, CFSTR(" }
if (kDesc) CFRelease(kDesc);
if (vDesc) CFRelease(vDesc);
return (Boolean)true;
});
CFStringAppendFormat(result, NULL, CFSTR(" return result;
}
__private_extern__ void CFBasicHashShow(CFBasicHashRef ht) {
CFStringRef str = CFBasicHashCopyDescription(ht, true, CFSTR(""), CFSTR("\t"), false);
CFShow(str);
CFRelease(str);
}
__private_extern__ 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);
}
__private_extern__ CFHashCode __CFBasicHashHash(CFTypeRef cf) {
CFBasicHashRef ht = (CFBasicHashRef)cf;
return CFBasicHashGetCount(ht);
}
__private_extern__ CFStringRef __CFBasicHashCopyDescription(CFTypeRef cf) {
CFBasicHashRef ht = (CFBasicHashRef)cf;
CFStringRef desc = CFBasicHashCopyDescription(ht, false, CFSTR(""), CFSTR("\t"), true);
CFStringRef result = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<CFBasicHash CFRelease(desc);
return result;
}
__private_extern__ 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
};
__private_extern__ CFTypeID CFBasicHashGetTypeID(void) {
if (_kCFRuntimeNotATypeID == __kCFBasicHashTypeID) __kCFBasicHashTypeID = _CFRuntimeRegisterClass(&__CFBasicHashClass);
return __kCFBasicHashTypeID;
}
CFBasicHashRef CFBasicHashCreate(CFAllocatorRef allocator, CFOptionFlags flags, const CFBasicHashCallbacks *cb) {
size_t size = sizeof(struct __CFBasicHash) - sizeof(CFRuntimeBase);
if (flags & kCFBasicHashHasValues2) size += sizeof(CFBasicHashValue *); // values2
if (flags & kCFBasicHashHasKeys) size += sizeof(CFBasicHashValue *); // keys
if (flags & kCFBasicHashHasKeys2) size += sizeof(CFBasicHashValue *); // keys2
if (flags & kCFBasicHashHasCounts) size += sizeof(uintptr_t *); // counts
if (flags & kCFBasicHashHasOrder) size += sizeof(uintptr_t *); // order
if (flags & kCFBasicHashHasHashCache) size += sizeof(uintptr_t *); // hashes
CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL);
if (NULL == ht) HALT;
ht->bits.finalized = 0;
ht->bits.strong_values = (flags & kCFBasicHashStrongValues) ? 1 : 0;
ht->bits.strong_values2 = 0;
ht->bits.strong_keys = (flags & kCFBasicHashStrongKeys) ? 1 : 0;
ht->bits.strong_keys2 = 0;
ht->bits.hash_style = (flags >> 13) & 0x3;
ht->bits.fast_grow = (flags & kCFBasicHashAggressiveGrowth) ? 1 : 0;
ht->bits.__0 = 0;
ht->bits.num_buckets_idx = 0;
ht->bits.used_buckets = 0;
ht->bits.marker = 0;
ht->bits.deleted = 0;
ht->bits.mutations = 1;
uint64_t offset = 1;
ht->bits.values2_offset = 0;
ht->bits.keys_offset = (flags & kCFBasicHashHasKeys) ? offset++ : 0;
ht->bits.keys2_offset = 0;
ht->bits.counts_offset = (flags & kCFBasicHashHasCounts) ? offset++ : 0;
ht->bits.orders_offset = 0;
ht->bits.hashes_offset = (flags & kCFBasicHashHasHashCache) ? offset++ : 0;
__AssignWithWriteBarrier(&ht->callbacks, cb);
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;
}
CFBasicHashRef CFBasicHashCreateCopy(CFAllocatorRef allocator, CFBasicHashRef src_ht) {
size_t size = CFBasicHashGetSize(src_ht, false) - sizeof(CFRuntimeBase);
CFBasicHashRef ht = (CFBasicHashRef)_CFRuntimeCreateInstance(allocator, CFBasicHashGetTypeID(), size, NULL);
if (NULL == ht) HALT;
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_values2 = 0;
ht->bits.strong_keys = 0;
ht->bits.strong_keys2 = 0;
}
ht->bits.finalized = 0;
ht->bits.mutations = 1;
__AssignWithWriteBarrier(&ht->callbacks, src_ht->callbacks->func(ht, kCFBasicHashCallbackOpCopyCallbacks, (uintptr_t)allocator, 0, src_ht->callbacks));
if (NULL == ht->callbacks) HALT;
CFIndex new_num_buckets = __CFBasicHashTableSizes[ht->bits.num_buckets_idx];
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 *new_values = NULL, *new_values2 = NULL, *new_keys = NULL, *new_keys2 = NULL;
uintptr_t *new_counts = NULL, *new_orders = NULL, *new_hashes = NULL;
if (0 < new_num_buckets) {
new_values = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_values);
__SetLastAllocationEventName(new_values, "CFBasicHash (value-store)");
if (0 != ht->bits.values2_offset) {
new_values2 = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_values2);
__SetLastAllocationEventName(new_values2, "CFBasicHash (value2-store)");
}
if (0 != ht->bits.keys_offset) {
new_keys = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_keys);
__SetLastAllocationEventName(new_keys, "CFBasicHash (key-store)");
}
if (0 != ht->bits.keys2_offset) {
new_keys2 = (CFBasicHashValue *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(CFBasicHashValue), ht->bits.strong_keys2);
__SetLastAllocationEventName(new_keys2, "CFBasicHash (key2-store)");
}
if (0 != ht->bits.counts_offset) {
new_counts = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
__SetLastAllocationEventName(new_counts, "CFBasicHash (count-store)");
}
if (0 != ht->bits.orders_offset) {
new_orders = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
__SetLastAllocationEventName(new_orders, "CFBasicHash (order-store)");
}
if (0 != ht->bits.hashes_offset) {
new_hashes = (uintptr_t *)__CFBasicHashAllocateMemory(ht, new_num_buckets, sizeof(uintptr_t), false);
__SetLastAllocationEventName(new_hashes, "CFBasicHash (hash-store)");
}
}
uintptr_t empty = ((uintptr_t)ht->bits.marker << __CFBasicHashMarkerShift), deleted = ~empty;
CFBasicHashValue *old_values = NULL, *old_values2 = NULL, *old_keys = NULL, *old_keys2 = NULL;
uintptr_t *old_counts = NULL, *old_orders = NULL, *old_hashes = NULL;
old_values = __CFBasicHashGetValues(src_ht);
if (0 != src_ht->bits.values2_offset) {
old_values2 = __CFBasicHashGetValues2(src_ht);
}
if (0 != src_ht->bits.keys_offset) {
old_keys = __CFBasicHashGetKeys(src_ht);
}
if (0 != src_ht->bits.keys2_offset) {
old_keys2 = __CFBasicHashGetKeys2(src_ht);
}
if (0 != src_ht->bits.counts_offset) {
old_counts = __CFBasicHashGetCounts(src_ht);
}
if (0 != src_ht->bits.orders_offset) {
old_orders = __CFBasicHashGetOrders(src_ht);
}
if (0 != src_ht->bits.hashes_offset) {
old_hashes = __CFBasicHashGetHashes(src_ht);
}
CFBasicHashValue *keys = old_keys ? old_keys : old_values;
for (CFIndex idx = 0; idx < new_num_buckets; idx++) {
uintptr_t stack_key = keys[idx].weak;
if (stack_key != empty && stack_key != deleted) {
uintptr_t stack_value = __CFBasicHashImportValue(ht, old_values[idx].weak);
if (ht->bits.strong_values) new_values[idx].strong = (id)stack_value; else new_values[idx].weak = stack_value;
if (new_values2) {
uintptr_t stack_value2 = __CFBasicHashImportValue2(ht, old_values2[idx].weak);
if (ht->bits.strong_values2) new_values2[idx].strong = (id)stack_value2; else new_values2[idx].weak = stack_value2;
}
if (new_keys) {
uintptr_t stack_key = __CFBasicHashImportKey(ht, old_keys[idx].weak);
if (ht->bits.strong_keys) new_keys[idx].strong = (id)stack_key; else new_keys[idx].weak = stack_key;
}
if (new_keys2) {
uintptr_t stack_key2 = __CFBasicHashImportKey2(ht, old_keys2[idx].weak);
if (ht->bits.strong_keys2) new_keys2[idx].strong = (id)stack_key2; else new_keys2[idx].weak = stack_key2;
}
} else {
if (ht->bits.strong_values) new_values[idx].strong = (id)stack_key; else new_values[idx].weak = stack_key;
if (new_values2) {
if (ht->bits.strong_values2) new_values2[idx].strong = (id)stack_key; else new_values2[idx].weak = stack_key;
}
if (new_keys) {
if (ht->bits.strong_keys) new_keys[idx].strong = (id)stack_key; else new_keys[idx].weak = stack_key;
}
if (new_keys2) {
if (ht->bits.strong_keys2) new_keys2[idx].strong = (id)stack_key; else new_keys2[idx].weak = stack_key;
}
}
}
if (new_counts) memmove(new_counts, old_counts, new_num_buckets * sizeof(uintptr_t));
if (new_orders) memmove(new_orders, old_orders, new_num_buckets * sizeof(uintptr_t));
if (new_hashes) memmove(new_hashes, old_hashes, new_num_buckets * sizeof(uintptr_t));
__CFBasicHashSetValues(ht, new_values);
if (new_values2) {
__CFBasicHashSetValues2(ht, new_values2);
}
if (new_keys) {
__CFBasicHashSetKeys(ht, new_keys);
}
if (new_keys2) {
__CFBasicHashSetKeys2(ht, new_keys2);
}
if (new_counts) {
__CFBasicHashSetCounts(ht, new_counts);
}
if (new_orders) {
__CFBasicHashSetOrders(ht, new_orders);
}
if (new_hashes) {
__CFBasicHashSetHashes(ht, new_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));
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;
}
void _CFbhx588461(CFBasicHashRef ht, Boolean growth) {
if (!CFBasicHashIsMutable(ht)) HALT;
if (ht->bits.finalized) HALT;
ht->bits.fast_grow = growth ? 1 : 0;
}