1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5#ifndef _SIMPLERHASHTABLE_INL_
6#define _SIMPLERHASHTABLE_INL_
7
8// To implement magic-number divide with a 32-bit magic number,
9// multiply by the magic number, take the top 64 bits, and shift that
10// by the amount given in the table.
11
12inline
13unsigned magicNumberDivide(unsigned numerator, const PrimeInfo &p)
14{
15 unsigned __int64 num = numerator;
16 unsigned __int64 mag = p.magic;
17 unsigned __int64 product = (num * mag) >> (32 + p.shift);
18 return (unsigned) product;
19}
20
21inline
22unsigned magicNumberRem(unsigned numerator, const PrimeInfo &p)
23{
24 unsigned div = magicNumberDivide(numerator, p);
25 unsigned result = numerator - (div * p.prime);
26 assert(result == numerator % p.prime);
27 return result;
28}
29
30template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
31SimplerHashTable<Key,KeyFuncs,Value,Behavior>::SimplerHashTable(IAllocator* alloc)
32 : m_alloc(alloc),
33 m_table(NULL),
34 m_tableSizeInfo(),
35 m_tableCount(0),
36 m_tableMax(0)
37{
38 assert(m_alloc != nullptr);
39
40#ifndef __GNUC__ // these crash GCC
41 static_assert_no_msg(Behavior::s_growth_factor_numerator > Behavior::s_growth_factor_denominator);
42 static_assert_no_msg(Behavior::s_density_factor_numerator < Behavior::s_density_factor_denominator);
43#endif
44}
45
46template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
47SimplerHashTable<Key,KeyFuncs,Value,Behavior>::~SimplerHashTable()
48{
49 RemoveAll();
50}
51
52template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
53void * SimplerHashTable<Key,KeyFuncs,Value,Behavior>::operator new(size_t sz, IAllocator * alloc)
54{
55 return alloc->Alloc(sz);
56}
57
58template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
59void * SimplerHashTable<Key,KeyFuncs,Value,Behavior>::operator new[](size_t sz, IAllocator * alloc)
60{
61 return alloc->Alloc(sz);
62}
63
64template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
65void SimplerHashTable<Key,KeyFuncs,Value,Behavior>::operator delete(void * p, IAllocator * alloc)
66{
67 alloc->Free(p);
68}
69
70template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
71void SimplerHashTable<Key,KeyFuncs,Value,Behavior>::operator delete[](void * p, IAllocator * alloc)
72{
73 alloc->Free(p);
74}
75
76template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
77unsigned SimplerHashTable<Key,KeyFuncs,Value,Behavior>::GetCount() const
78{
79 return m_tableCount;
80}
81
82template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
83bool SimplerHashTable<Key,KeyFuncs,Value,Behavior>::Lookup(Key key, Value* pVal) const
84{
85 Node* pN = FindNode(key);
86
87 if (pN != NULL)
88 {
89 if (pVal != NULL)
90 {
91 *pVal = pN->m_val;
92 }
93 return true;
94 }
95 else
96 {
97 return false;
98 }
99}
100
101template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
102Value *SimplerHashTable<Key,KeyFuncs,Value,Behavior>::LookupPointer(Key key) const
103{
104 Node* pN = FindNode(key);
105
106 if (pN != NULL)
107 return &(pN->m_val);
108 else
109 return NULL;
110}
111
112template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
113typename SimplerHashTable<Key,KeyFuncs,Value,Behavior>::Node*
114SimplerHashTable<Key,KeyFuncs,Value,Behavior>::FindNode(Key k) const
115{
116 if (m_tableSizeInfo.prime == 0)
117 return NULL;
118
119 unsigned index = GetIndexForKey(k);
120
121 Node* pN = m_table[index];
122 if (pN == NULL)
123 return NULL;
124
125 // Otherwise...
126 while (pN != NULL && !KeyFuncs::Equals(k, pN->m_key))
127 pN = pN->m_next;
128
129 assert(pN == NULL || KeyFuncs::Equals(k, pN->m_key));
130
131 // If pN != NULL, it's the node for the key, else the key isn't mapped.
132 return pN;
133}
134
135template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
136unsigned SimplerHashTable<Key,KeyFuncs,Value,Behavior>::GetIndexForKey(Key k) const
137{
138 unsigned hash = KeyFuncs::GetHashCode(k);
139
140 unsigned index = magicNumberRem(hash, m_tableSizeInfo);
141
142 return index;
143}
144
145template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
146bool SimplerHashTable<Key,KeyFuncs,Value,Behavior>::Set(Key k, Value v)
147{
148 CheckGrowth();
149
150 assert(m_tableSizeInfo.prime != 0);
151
152 unsigned index = GetIndexForKey(k);
153
154 Node* pN = m_table[index];
155 while (pN != NULL && !KeyFuncs::Equals(k, pN->m_key))
156 {
157 pN = pN->m_next;
158 }
159 if (pN != NULL)
160 {
161 pN->m_val = v;
162 return true;
163 }
164 else
165 {
166 Node* pNewNode = new (m_alloc) Node(k, v, m_table[index]);
167 m_table[index] = pNewNode;
168 m_tableCount++;
169 return false;
170 }
171}
172
173template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
174bool SimplerHashTable<Key,KeyFuncs,Value,Behavior>::Remove(Key k)
175{
176 unsigned index = GetIndexForKey(k);
177
178 Node* pN = m_table[index];
179 Node** ppN = &m_table[index];
180 while (pN != NULL && !KeyFuncs::Equals(k, pN->m_key))
181 {
182 ppN = &pN->m_next;
183 pN = pN->m_next;
184 }
185 if (pN != NULL)
186 {
187 *ppN = pN->m_next;
188 m_tableCount--;
189 Node::operator delete(pN, m_alloc);
190 return true;
191 }
192 else
193 {
194 return false;
195 }
196}
197
198template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
199void SimplerHashTable<Key,KeyFuncs,Value,Behavior>::RemoveAll()
200{
201 for (unsigned i = 0; i < m_tableSizeInfo.prime; i++)
202 {
203 for (Node* pN = m_table[i]; pN != NULL; )
204 {
205 Node* pNext = pN->m_next;
206 Node::operator delete(pN, m_alloc);
207 pN = pNext;
208 }
209 }
210 m_alloc->Free(m_table);
211
212 m_table = NULL;
213 m_tableSizeInfo = PrimeInfo();
214 m_tableCount = 0;
215 m_tableMax = 0;
216
217 return;
218}
219
220template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
221typename SimplerHashTable<Key,KeyFuncs,Value,Behavior>::KeyIterator SimplerHashTable<Key,KeyFuncs,Value,Behavior>::Begin() const
222{
223 KeyIterator i(this, TRUE);
224 return i;
225}
226
227template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
228typename SimplerHashTable<Key,KeyFuncs,Value,Behavior>::KeyIterator SimplerHashTable<Key,KeyFuncs,Value,Behavior>::End() const
229{
230 return KeyIterator(this, FALSE);
231}
232
233template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
234void SimplerHashTable<Key,KeyFuncs,Value,Behavior>::CheckGrowth()
235{
236 if (m_tableCount == m_tableMax)
237 {
238 Grow();
239 }
240}
241
242template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
243void SimplerHashTable<Key,KeyFuncs,Value,Behavior>::Grow()
244{
245 unsigned newSize = (unsigned) (m_tableCount
246 * Behavior::s_growth_factor_numerator / Behavior::s_growth_factor_denominator
247 * Behavior::s_density_factor_denominator / Behavior::s_density_factor_numerator);
248 if (newSize < Behavior::s_minimum_allocation)
249 newSize = Behavior::s_minimum_allocation;
250
251 // handle potential overflow
252 if (newSize < m_tableCount)
253 Behavior::NoMemory();
254
255 Reallocate(newSize);
256}
257
258template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
259void SimplerHashTable<Key,KeyFuncs,Value,Behavior>::Reallocate(unsigned newTableSize)
260{
261 assert(newTableSize >= (GetCount() * Behavior::s_density_factor_denominator / Behavior::s_density_factor_numerator));
262
263 // Allocation size must be a prime number. This is necessary so that hashes uniformly
264 // distribute to all indices, and so that chaining will visit all indices in the hash table.
265 PrimeInfo newPrime = NextPrime(newTableSize);
266 newTableSize = newPrime.prime;
267
268 Node** newTable = (Node**)m_alloc->ArrayAlloc(newTableSize, sizeof(Node*));
269
270 for (unsigned i = 0; i < newTableSize; i++) {
271 newTable[i] = NULL;
272 }
273
274 // Move all entries over to new table (re-using the Node structures.)
275
276 for (unsigned i = 0; i < m_tableSizeInfo.prime; i++)
277 {
278 Node* pN = m_table[i];
279 while (pN != NULL)
280 {
281 Node* pNext = pN->m_next;
282
283 unsigned newIndex = magicNumberRem(KeyFuncs::GetHashCode(pN->m_key), newPrime);
284 pN->m_next = newTable[newIndex];
285 newTable[newIndex] = pN;
286
287 pN = pNext;
288 }
289 }
290
291 // @todo:
292 // We might want to try to delay this cleanup to allow asynchronous readers
293 if (m_table != NULL)
294 m_alloc->Free(m_table);
295
296 m_table = newTable;
297 m_tableSizeInfo = newPrime;
298 m_tableMax = (unsigned) (newTableSize * Behavior::s_density_factor_numerator / Behavior::s_density_factor_denominator);
299}
300
301// Table of primes and their magic-number-divide constant.
302// For more info see the book "Hacker's Delight" chapter 10.9 "Unsigned Division by Divisors >= 1"
303// These were selected by looking for primes, each roughly twice as big as the next, having
304// 32-bit magic numbers, (because the algorithm for using 33-bit magic numbers is slightly slower).
305//
306
307SELECTANY const PrimeInfo primeInfo[] =
308{
309 PrimeInfo(9, 0x38e38e39, 1),
310 PrimeInfo(23, 0xb21642c9, 4),
311 PrimeInfo(59, 0x22b63cbf, 3),
312 PrimeInfo(131, 0xfa232cf3, 7),
313 PrimeInfo(239, 0x891ac73b, 7),
314 PrimeInfo(433, 0x975a751, 4),
315 PrimeInfo(761, 0x561e46a5, 8),
316 PrimeInfo(1399, 0xbb612aa3, 10),
317 PrimeInfo(2473, 0x6a009f01, 10),
318 PrimeInfo(4327, 0xf2555049, 12),
319 PrimeInfo(7499, 0x45ea155f, 11),
320 PrimeInfo(12973, 0x1434f6d3, 10),
321 PrimeInfo(22433, 0x2ebe18db, 12),
322 PrimeInfo(46559, 0xb42bebd5, 15),
323 PrimeInfo(96581, 0xadb61b1b, 16),
324 PrimeInfo(200341, 0x29df2461, 15),
325 PrimeInfo(415517, 0xa181c46d, 18),
326 PrimeInfo(861719, 0x4de0bde5, 18),
327 PrimeInfo(1787021, 0x9636c46f, 20),
328 PrimeInfo(3705617, 0x4870adc1, 20),
329 PrimeInfo(7684087, 0x8bbc5b83, 22),
330 PrimeInfo(15933877, 0x86c65361, 23),
331 PrimeInfo(33040633, 0x40fec79b, 23),
332 PrimeInfo(68513161, 0x7d605cd1, 25),
333 PrimeInfo(142069021, 0xf1da390b, 27),
334 PrimeInfo(294594427, 0x74a2507d, 27),
335 PrimeInfo(733045421, 0x5dbec447, 28),
336};
337
338template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
339PrimeInfo SimplerHashTable<Key,KeyFuncs,Value,Behavior>::NextPrime(unsigned number)
340{
341 for (int i = 0; i < (int) (sizeof(primeInfo) / sizeof(primeInfo[0])); i++) {
342 if (primeInfo[i].prime >= number)
343 return primeInfo[i];
344 }
345
346 // overflow
347 Behavior::NoMemory();
348}
349
350#endif // _SIMPLERHASHTABLE_INL_
351