1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
/* CFBasicHashFindBucket.m
Copyright (c) 2009-2019, Apple Inc. and the Swift project authors
Portions Copyright (c) 2014-2019, Apple Inc. and the Swift project authors
Licensed under Apache License v2.0 with Runtime Library Exception
See http://swift.org/LICENSE.txt for license information
See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
Responsibility: Michael LeHew
*/
#if !defined(FIND_BUCKET_NAME) || !defined(FIND_BUCKET_HASH_STYLE) || !defined(FIND_BUCKET_FOR_REHASH) || !defined(FIND_BUCKET_FOR_INDIRECT_KEY)
#error All of FIND_BUCKET_NAME, FIND_BUCKET_HASH_STYLE, FIND_BUCKET_FOR_REHASH, and FIND_BUCKET_FOR_INDIRECT_KEY must be defined before #including this file.
#endif
// 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
#if FIND_BUCKET_FOR_REHASH
CFIndex
#else
CFBasicHashBucket
#endif
FIND_BUCKET_NAME (CFConstBasicHashRef ht, uintptr_t stack_key
#if FIND_BUCKET_FOR_REHASH
, uintptr_t key_hash
#endif
) {
uint8_t num_buckets_idx = ht->bits.num_buckets_idx;
uintptr_t num_buckets = __CFBasicHashTableSizes[num_buckets_idx];
#if FIND_BUCKET_FOR_REHASH
CFHashCode hash_code = key_hash ? key_hash : __CFBasicHashHashKey(ht, stack_key);
#else
CFHashCode hash_code = __CFBasicHashHashKey(ht, stack_key);
#endif
#if FIND_BUCKET_HASH_STYLE == 1 // __kCFBasicHashLinearHashingValue
// 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
#if defined(__arm__)
uintptr_t h1 = __CFBasicHashFold(hash_code, num_buckets_idx);
#else
uintptr_t h1 = hash_code % num_buckets;
#endif
#elif FIND_BUCKET_HASH_STYLE == 2 // __kCFBasicHashDoubleHashingValue
// 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
#if defined(__arm__)
uintptr_t h1 = __CFBasicHashFold(hash_code, num_buckets_idx);
uintptr_t h2 = __CFBasicHashFold(hash_code / num_buckets, num_buckets_idx);
#else
uintptr_t h1 = hash_code % num_buckets;
uintptr_t h2 = (hash_code / num_buckets) % num_buckets;
#endif
if (0 == h2) h2 = num_buckets - 1;
#elif FIND_BUCKET_HASH_STYLE == 3 // __kCFBasicHashExponentialHashingValue
// 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
#if defined(__arm__)
uintptr_t h1 = __CFBasicHashFold(hash_code, num_buckets_idx);
uintptr_t h2 = __CFBasicHashFold(hash_code / num_buckets, num_buckets_idx);
#else
uintptr_t h1 = hash_code % num_buckets;
uintptr_t h2 = (hash_code / num_buckets) % num_buckets;
#endif
if (0 == h2) h2 = num_buckets - 1;
uintptr_t pr = __CFBasicHashPrimitiveRoots[num_buckets_idx];
#endif
COCOA_HASHTABLE_PROBING_START(ht, num_buckets);
CFBasicHashValue *keys = (ht->bits.keys_offset) ? __CFBasicHashGetKeys(ht) : __CFBasicHashGetValues(ht);
#if !FIND_BUCKET_FOR_REHASH
uintptr_t *hashes = (__CFBasicHashHasHashCache(ht)) ? __CFBasicHashGetHashes(ht) : NULL;
#endif
CFIndex deleted_idx = kCFNotFound;
uintptr_t probe = h1;
#if FIND_BUCKET_HASH_STYLE == 3 // __kCFBasicHashExponentialHashingValue
uintptr_t acc = pr;
#endif
for (CFIndex idx = 0; idx < num_buckets; idx++) {
uintptr_t curr_key = keys[probe].neutral;
if (curr_key == 0UL) {
COCOA_HASHTABLE_PROBE_EMPTY(ht, probe);
#if FIND_BUCKET_FOR_REHASH
CFIndex result = (kCFNotFound == deleted_idx) ? probe : deleted_idx;
#else
CFBasicHashBucket result;
result.idx = (kCFNotFound == deleted_idx) ? probe : deleted_idx;
result.count = 0;
#endif
COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
return result;
#if !FIND_BUCKET_FOR_REHASH
} else if (curr_key == ~0UL) {
COCOA_HASHTABLE_PROBE_DELETED(ht, probe);
if (kCFNotFound == deleted_idx) {
deleted_idx = probe;
}
} else {
COCOA_HASHTABLE_PROBE_VALID(ht, probe);
if (__CFBasicHashSubABZero == curr_key) curr_key = 0UL;
if (__CFBasicHashSubABOne == curr_key) curr_key = ~0UL;
#if FIND_BUCKET_FOR_INDIRECT_KEY
// curr_key holds the value coming in here
curr_key = __CFBasicHashGetIndirectKey(ht, curr_key);
#endif
if (curr_key == stack_key || ((!hashes || hashes[probe] == hash_code) && __CFBasicHashTestEqualKey(ht, curr_key, stack_key))) {
COCOA_HASHTABLE_PROBING_END(ht, idx + 1);
#if FIND_BUCKET_FOR_REHASH
CFIndex result = probe;
#else
CFBasicHashBucket result;
result.idx = probe;
result.weak_value = __CFBasicHashGetValue(ht, probe);
result.weak_key = curr_key;
result.count = (ht->bits.counts_offset) ? __CFBasicHashGetSlotCount(ht, probe) : 1;
#endif
return result;
}
#endif
}
#if FIND_BUCKET_HASH_STYLE == 1 // __kCFBasicHashLinearHashingValue
probe += 1;
if (num_buckets <= probe) {
probe -= num_buckets;
}
#elif FIND_BUCKET_HASH_STYLE == 2 // __kCFBasicHashDoubleHashingValue
probe += h2;
if (num_buckets <= probe) {
probe -= num_buckets;
}
#elif FIND_BUCKET_HASH_STYLE == 3 // __kCFBasicHashExponentialHashingValue
probe = h1 + h2 * acc;
if (num_buckets <= probe) {
#if defined(__arm__)
probe = __CFBasicHashFold(probe, num_buckets_idx);
#else
probe = probe % num_buckets;
#endif
}
acc = acc * pr;
if (num_buckets <= acc) {
#if defined(__arm__)
acc = __CFBasicHashFold(acc, num_buckets_idx);
#else
acc = acc % num_buckets;
#endif
}
#endif
}
COCOA_HASHTABLE_PROBING_END(ht, num_buckets);
#if FIND_BUCKET_FOR_REHASH
CFIndex result = deleted_idx;
#else
CFBasicHashBucket result;
result.idx = deleted_idx;
result.count = 0;
#endif
return result; // all buckets full or deleted, return first deleted element which was found
}
#undef FIND_BUCKET_NAME
#undef FIND_BUCKET_HASH_STYLE
#undef FIND_BUCKET_FOR_REHASH
#undef FIND_BUCKET_FOR_INDIRECT_KEY
|
