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_H_
6#define _SIMPLERHASHTABLE_H_
7
8#include "iallocator.h"
9
10// SimplerHashTable implements a mapping from a Key type to a Value type,
11// via a hash table.
12
13// Synchronization is the responsibility of the caller: if a
14// SimplerHash is used in a multithreaded context, the table should be
15// associated with a lock.
16
17// SimplerHashTable actually takes four template arguments: Key,
18// KeyFuncs, Value, and Behavior. We don't assume that Key has hash or equality
19// functions specific names; rather, we assume that KeyFuncs has
20// statics methods
21// int GetHashCode(Key)
22// and
23// bool Equals(Key, Key)
24// and use those. An
25// instantiator can thus make a small "adaptor class" to invoke
26// existing instance method hash and/or equality functions. If the
27// implementor of a candidate Key class K understands this convention,
28// these static methods can be implemented by K, so that K can be used
29// as the actual arguments for the both Key and KeyTrait classes.
30//
31// The "Behavior" argument provides the following static members:
32//
33// s_growth_factor_numerator
34// s_growth_factor_denominator Factor to grow allocation (numerator/denominator).
35// Typically inherited from default traits (3/2)
36//
37// s_density_factor_numerator
38// s_density_factor_denominator Maxium occupied density of table before growth
39// occurs (num/denom). Typically inherited (3/4).
40//
41// s_minimum_allocation Minimum table allocation count (size on first growth.) It is
42// probably preferable to call Reallocate on initialization rather
43// than override his from the default traits. (7)
44//
45// NoMemory() Called when the hash table is unable to grow due to potential
46// overflow or the lack of a sufficiently large prime.
47
48void DECLSPEC_NORETURN ThrowOutOfMemory();
49
50class DefaultSimplerHashBehavior
51{
52public:
53 static const unsigned s_growth_factor_numerator = 3;
54 static const unsigned s_growth_factor_denominator = 2;
55
56 static const unsigned s_density_factor_numerator = 3;
57 static const unsigned s_density_factor_denominator = 4;
58
59 static const unsigned s_minimum_allocation = 7;
60
61 inline static void DECLSPEC_NORETURN NoMemory()
62 {
63 ::ThrowOutOfMemory();
64 }
65};
66
67// Stores info about primes, including the magic number and shift amount needed
68// to implement a divide without using the divide instruction
69class PrimeInfo
70{
71public:
72 PrimeInfo() : prime(0), magic(0), shift(0) {}
73 PrimeInfo(unsigned p, unsigned m, unsigned s) : prime(p), magic(m), shift(s) {}
74 unsigned prime;
75 unsigned magic;
76 unsigned shift;
77};
78
79
80// Hash table class definition
81
82template <typename Key, typename KeyFuncs, typename Value, typename Behavior>
83class SimplerHashTable
84{
85public:
86 // Forward declaration.
87 class KeyIterator;
88
89 // Constructor/destructor. SHash tables always start out empty, with no
90 // allocation overhead. Call Reallocate to prime with an initial size if
91 // desired. Pass NULL as the IAllocator* if you want to use DefaultAllocator
92 // (basically, operator new/delete).
93
94 SimplerHashTable(IAllocator* alloc);
95 ~SimplerHashTable();
96
97 // operators new/delete when an IAllocator is to be used.
98 void * operator new(size_t sz, IAllocator * alloc);
99 void * operator new[](size_t sz, IAllocator * alloc);
100 void operator delete(void * p, IAllocator * alloc);
101 void operator delete[](void * p, IAllocator * alloc);
102
103 // If the table contains a mapping for "key", returns "true" and
104 // sets "*pVal" to the value to which "key" maps. Otherwise,
105 // returns false, and does not modify "*pVal".
106 bool Lookup(Key k, Value* pVal = NULL) const;
107
108 Value *LookupPointer(Key k) const;
109
110 // Causes the table to map "key" to "val". Returns "true" if
111 // "key" had already been mapped by the table, "false" otherwise.
112 bool Set(Key k, Value val);
113
114 // Ensures that "key" is not mapped to a value by the "table."
115 // Returns "true" iff it had been mapped.
116 bool Remove(Key k);
117
118 // Remove all mappings in the table.
119 void RemoveAll();
120
121 // Begin and End pointers for iteration over entire table.
122 KeyIterator Begin() const;
123 KeyIterator End() const;
124
125 // Return the number of elements currently stored in the table
126 unsigned GetCount() const;
127
128private:
129 // Forward declaration of the linked-list node class.
130 struct Node;
131
132 unsigned GetIndexForKey(Key k) const;
133
134 // If the table has a mapping for "k", return the node containing
135 // that mapping, else "NULL".
136 Node* FindNode(Key k) const;
137
138 // Resizes a hash table for growth. The new size is computed based
139 // on the current population, growth factor, and maximum density factor.
140 void Grow();
141
142 // See if it is OK to grow the hash table by one element. If not, reallocate
143 // the hash table.
144 void CheckGrowth();
145
146public:
147 // Reallocates a hash table to a specific size. The size must be big enough
148 // to hold all elements in the table appropriately.
149 //
150 // Note that the actual table size must always be a prime number; the number
151 // passed in will be upward adjusted if necessary.
152 void Reallocate(unsigned newTableSize);
153
154 // For iteration, we use a pattern similar to the STL "forward
155 // iterator" pattern. It basically consists of wrapping an
156 // "iteration variable" in an object, and providing pointer-like
157 // operators on the iterator. Example usage:
158 //
159 // for (SimplerHashTable::KeyIterator iter = foo->Begin(), end = foo->End(); !iter.Equal(end); iter++)
160 // {
161 // // use foo, iter.
162 // }
163 // iter.Get() will yield (a reference to) the
164 // current key. It will assert the equivalent of "iter != end."
165 class KeyIterator
166 {
167 private:
168 friend class SimplerHashTable;
169
170 // The method implementations have to be here for portability.
171 // Some compilers won't compile the separate implementation in shash.inl
172
173 Node** m_table;
174 Node* m_node;
175 unsigned m_tableSize;
176 unsigned m_index;
177
178 public:
179 KeyIterator(const SimplerHashTable *hash, BOOL begin)
180 : m_table(hash->m_table),
181 m_node(NULL),
182 m_tableSize(hash->m_tableSizeInfo.prime),
183 m_index(begin ? 0 : m_tableSize)
184 {
185 if (begin && hash->m_tableCount > 0)
186 {
187 assert(m_table != NULL);
188 while (m_index < m_tableSize && m_table[m_index] == NULL)
189 m_index++;
190
191 if (m_index >= m_tableSize)
192 {
193 return;
194 }
195 else
196 {
197 m_node = m_table[m_index];
198 }
199 assert(m_node != NULL);
200 }
201 }
202
203 const Key& Get() const
204 {
205 assert(m_node != NULL);
206
207 return m_node->m_key;
208 }
209
210 const Value& GetValue() const
211 {
212 assert(m_node != NULL);
213
214 return m_node->m_val;
215 }
216
217 void SetValue(const Value & value) const
218 {
219 assert(m_node != NULL);
220
221 m_node->m_val = value;
222 }
223
224 void Next()
225 {
226 if (m_node != NULL)
227 {
228 m_node = m_node->m_next;
229 if (m_node != NULL)
230 {
231 return;
232 }
233
234 // Otherwise...
235 m_index++;
236 }
237 while (m_index < m_tableSize && m_table[m_index] == NULL)
238 m_index++;
239
240 if (m_index >= m_tableSize)
241 {
242 m_node = NULL;
243 return;
244 }
245 else
246 {
247 m_node = m_table[m_index];
248 }
249 assert(m_node != NULL);
250 }
251
252 bool Equal(const KeyIterator &i) const
253 {
254 return i.m_node == m_node;
255 }
256
257 void operator++() {
258 Next();
259 }
260
261 void operator++(int) {
262 Next();
263 }
264 };
265
266 // HashTableRef only exists to support operator[]
267 // operator[] returns a HashTableRef which enables operator[] to support reading and writing
268 // in a normal array, it just returns a ref an actual element, which is not possible here.
269 class HashTableRef
270 {
271 public:
272 // this is really the getter for the array.
273 operator Value()
274 {
275
276 Value result;
277 table->Lookup(key, &result);
278 return result;
279 }
280
281 void operator =(const Value v)
282 {
283 table->Set(key, v);
284 }
285
286 friend class SimplerHashTable;
287
288 protected:
289 HashTableRef(SimplerHashTable *t, Key k)
290 {
291 table = t;
292 key = k;
293 }
294
295 SimplerHashTable *table;
296 Key key;
297 };
298
299 Value &operator[](Key k) const
300 {
301 Value* p = LookupPointer(k);
302 assert(p);
303 return *p;
304 }
305
306 private:
307 // Find the next prime number >= the given value.
308 static PrimeInfo NextPrime(unsigned number);
309
310 // Instance members
311 IAllocator* m_alloc; // IAllocator to use in this
312 // table.
313 // The node type.
314 struct Node {
315 Node* m_next; // Assume that the alignment requirement of Key and Value are no greater than Node*, so put m_next to avoid unnecessary padding.
316 Key m_key;
317 Value m_val;
318
319 Node(Key k, Value v, Node* next) : m_next(next), m_key(k), m_val(v) {}
320
321 void* operator new(size_t sz, IAllocator* alloc)
322 {
323 return alloc->Alloc(sz);
324 }
325
326 void operator delete(void* p, IAllocator* alloc)
327 {
328 alloc->Free(p);
329 }
330 };
331
332 Node** m_table; // pointer to table
333 PrimeInfo m_tableSizeInfo; // size of table (a prime) and information about it
334 unsigned m_tableCount; // number of elements in table
335 unsigned m_tableMax; // maximum occupied count
336};
337
338#include "simplerhash.inl"
339
340// A few simple KeyFuncs types...
341
342// Base class for types whose equality function is the same as their "==".
343template<typename T>
344struct KeyFuncsDefEquals
345{
346 static bool Equals(const T& x, const T& y)
347 {
348 return x == y;
349 }
350};
351
352template<typename T>
353struct PtrKeyFuncs: public KeyFuncsDefEquals<const T*>
354{
355public:
356 static unsigned GetHashCode(const T* ptr)
357 {
358 // Hmm. Maybe (unsigned) ought to be "ssize_t" -- or this ought to be ifdef'd by size.
359 return static_cast<unsigned>(reinterpret_cast<uintptr_t>(ptr));
360 }
361};
362
363template<typename T> // Must be coercable to "unsigned" with no loss of information.
364struct SmallPrimitiveKeyFuncs: public KeyFuncsDefEquals<T>
365{
366 static unsigned GetHashCode(const T& val)
367 {
368 return static_cast<unsigned>(val);
369 }
370};
371
372template<typename T> // Assumed to be of size sizeof(UINT64).
373struct LargePrimitiveKeyFuncs: public KeyFuncsDefEquals<T>
374{
375 static unsigned GetHashCode(const T val)
376 {
377 // A static cast when T is a float or a double converts the value (i.e. 0.25 converts to 0)
378 //
379 // Instead we want to use all of the bits of a float to create the hash value
380 // So we cast the address of val to a pointer to an equivalent sized unsigned int
381 // This allows us to read the actual bit representation of a float type
382 //
383 // We can't read beyond the end of val, so we use sizeof(T) to determine
384 // exactly how many bytes to read
385 //
386 if (sizeof(T) == 8)
387 {
388 // cast &val to (UINT64 *) then deref to get the bits
389 UINT64 asUINT64 = *(reinterpret_cast<const UINT64 *>(&val));
390
391 // Get the upper and lower 32-bit values from the 64-bit value
392 UINT32 upper32 = static_cast<UINT32> (asUINT64 >> 32);
393 UINT32 lower32 = static_cast<UINT32> (asUINT64 & 0xFFFFFFFF);
394
395 // Exclusive-Or the upper32 and the lower32 values
396 return static_cast<unsigned>(upper32 ^ lower32);
397
398 }
399 else if (sizeof(T) == 4)
400 {
401 // cast &val to (UINT32 *) then deref to get the bits
402 UINT32 asUINT32 = *(reinterpret_cast<const UINT32 *>(&val));
403
404 // Just return the 32-bit value
405 return static_cast<unsigned>(asUINT32);
406 }
407 else if ((sizeof(T) == 2) || (sizeof(T) == 1))
408 {
409 // For small sizes we must have an integer type
410 // so we can just use the static_cast.
411 //
412 return static_cast<unsigned>(val);
413 }
414 else
415 {
416 // Only support Hashing for types that are 8,4,2 or 1 bytes in size
417 assert(!"Unsupported size");
418 return static_cast<unsigned>(val); // compile-time error here when we have a illegal size
419 }
420 }
421};
422
423#endif // _SIMPLERHASHTABLE_H_
424