/
CFBasicHashFindBucket.m
198 lines (187 loc) · 7.28 KB
/
CFBasicHashFindBucket.m
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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
/*
* Copyright (c) 2014 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@
*/
/* CFBasicHashFindBucket.m
Copyright (c) 2009-2013, Apple Inc. All rights reserved.
Responsibility: Christopher Kane
*/
#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