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#pragma once
6
7// JitHashTable implements a mapping from a Key type to a Value type,
8// via a hash table.
9
10// JitHashTable takes four template parameters:
11// Key, KeyFuncs, Value, Allocator and Behavior.
12// We don't assume that Key has hash or equality functions specific names;
13// rather, we assume that KeyFuncs has the following static methods
14// int GetHashCode(Key)
15// bool Equals(Key, Key)
16// and use those. An instantiator can thus make a small "adaptor class"
17// to invoke existing instance method hash and/or equality functions.
18// If the implementor of a candidate Key class K understands this convention,
19// these static methods can be implemented by K, so that K can be used
20// as the actual arguments for the both Key and KeyFuncs template parameters.
21//
22// The "Behavior" parameter must provide the following static members:
23//
24// s_growth_factor_numerator
25// s_growth_factor_denominator Factor to grow allocation (numerator/denominator).
26// Typically inherited from default traits (3/2)
27//
28// s_density_factor_numerator
29// s_density_factor_denominator Maxium occupied density of table before growth
30// occurs (num/denom). Typically inherited (3/4).
31//
32// s_minimum_allocation Minimum table allocation count (size on first growth.) It is
33// probably preferable to call Reallocate on initialization rather
34// than override this from the default traits.
35//
36// NoMemory() Called when the hash table is unable to grow due to potential
37// overflow or the lack of a sufficiently large prime.
38
39class JitHashTableBehavior
40{
41public:
42 static const unsigned s_growth_factor_numerator = 3;
43 static const unsigned s_growth_factor_denominator = 2;
44
45 static const unsigned s_density_factor_numerator = 3;
46 static const unsigned s_density_factor_denominator = 4;
47
48 static const unsigned s_minimum_allocation = 7;
49
50 inline static void DECLSPEC_NORETURN NoMemory()
51 {
52 NOMEM();
53 }
54};
55
56// Stores info about primes, including the magic number and shift amount needed
57// to implement a divide without using the divide instruction
58class JitPrimeInfo
59{
60public:
61 JitPrimeInfo() : prime(0), magic(0), shift(0)
62 {
63 }
64 JitPrimeInfo(unsigned p, unsigned m, unsigned s) : prime(p), magic(m), shift(s)
65 {
66 }
67 unsigned prime;
68 unsigned magic;
69 unsigned shift;
70
71 // Compute `numerator` / `prime` using magic division
72 unsigned magicNumberDivide(unsigned numerator) const
73 {
74 unsigned __int64 num = numerator;
75 unsigned __int64 mag = magic;
76 unsigned __int64 product = (num * mag) >> (32 + shift);
77 return (unsigned)product;
78 }
79
80 // Compute `numerator` % `prime` using magic division
81 unsigned magicNumberRem(unsigned numerator) const
82 {
83 unsigned div = magicNumberDivide(numerator);
84 unsigned result = numerator - (div * prime);
85 assert(result == numerator % prime);
86 return result;
87 }
88};
89
90// Table of primes and their magic-number-divide constant.
91// For more info see the book "Hacker's Delight" chapter 10.9 "Unsigned Division by Divisors >= 1"
92// These were selected by looking for primes, each roughly twice as big as the next, having
93// 32-bit magic numbers, (because the algorithm for using 33-bit magic numbers is slightly slower).
94
95// clang-format off
96SELECTANY const JitPrimeInfo jitPrimeInfo[]
97{
98 JitPrimeInfo(9, 0x38e38e39, 1),
99 JitPrimeInfo(23, 0xb21642c9, 4),
100 JitPrimeInfo(59, 0x22b63cbf, 3),
101 JitPrimeInfo(131, 0xfa232cf3, 7),
102 JitPrimeInfo(239, 0x891ac73b, 7),
103 JitPrimeInfo(433, 0x975a751, 4),
104 JitPrimeInfo(761, 0x561e46a5, 8),
105 JitPrimeInfo(1399, 0xbb612aa3, 10),
106 JitPrimeInfo(2473, 0x6a009f01, 10),
107 JitPrimeInfo(4327, 0xf2555049, 12),
108 JitPrimeInfo(7499, 0x45ea155f, 11),
109 JitPrimeInfo(12973, 0x1434f6d3, 10),
110 JitPrimeInfo(22433, 0x2ebe18db, 12),
111 JitPrimeInfo(46559, 0xb42bebd5, 15),
112 JitPrimeInfo(96581, 0xadb61b1b, 16),
113 JitPrimeInfo(200341, 0x29df2461, 15),
114 JitPrimeInfo(415517, 0xa181c46d, 18),
115 JitPrimeInfo(861719, 0x4de0bde5, 18),
116 JitPrimeInfo(1787021, 0x9636c46f, 20),
117 JitPrimeInfo(3705617, 0x4870adc1, 20),
118 JitPrimeInfo(7684087, 0x8bbc5b83, 22),
119 JitPrimeInfo(15933877, 0x86c65361, 23),
120 JitPrimeInfo(33040633, 0x40fec79b, 23),
121 JitPrimeInfo(68513161, 0x7d605cd1, 25),
122 JitPrimeInfo(142069021, 0xf1da390b, 27),
123 JitPrimeInfo(294594427, 0x74a2507d, 27),
124 JitPrimeInfo(733045421, 0x5dbec447, 28),
125};
126// clang-format on
127
128// Hash table class definition
129
130template <typename Key,
131 typename KeyFuncs,
132 typename Value,
133 typename Allocator = CompAllocator,
134 typename Behavior = JitHashTableBehavior>
135class JitHashTable
136{
137public:
138 class KeyIterator;
139
140 //------------------------------------------------------------------------
141 // JitHashTable: Construct an empty JitHashTable object.
142 //
143 // Arguments:
144 // alloc - the allocator to be used by the new JitHashTable object
145 //
146 // Notes:
147 // JitHashTable always starts out empty, with no allocation overhead.
148 // Call Reallocate to prime with an initial size if desired.
149 //
150 JitHashTable(Allocator alloc) : m_alloc(alloc), m_table(nullptr), m_tableSizeInfo(), m_tableCount(0), m_tableMax(0)
151 {
152#ifndef __GNUC__ // these crash GCC
153 static_assert_no_msg(Behavior::s_growth_factor_numerator > Behavior::s_growth_factor_denominator);
154 static_assert_no_msg(Behavior::s_density_factor_numerator < Behavior::s_density_factor_denominator);
155#endif
156 }
157
158 //------------------------------------------------------------------------
159 // ~JitHashTable: Destruct the JitHashTable object.
160 //
161 // Notes:
162 // Destructs all keys and values stored in the table and frees all
163 // owned memory.
164 //
165 ~JitHashTable()
166 {
167 RemoveAll();
168 }
169
170 //------------------------------------------------------------------------
171 // Lookup: Get the value associated to the specified key, if any.
172 //
173 // Arguments:
174 // k - the key
175 // pVal - pointer to a location used to store the associated value
176 //
177 // Return Value:
178 // `true` if the key exists, `false` otherwise
179 //
180 // Notes:
181 // If the key does not exist *pVal is not updated. pVal may be nullptr
182 // so this function can be used to simply check if the key exists.
183 //
184 bool Lookup(Key k, Value* pVal = nullptr) const
185 {
186 Node* pN = FindNode(k);
187
188 if (pN != nullptr)
189 {
190 if (pVal != nullptr)
191 {
192 *pVal = pN->m_val;
193 }
194 return true;
195 }
196 else
197 {
198 return false;
199 }
200 }
201
202 //------------------------------------------------------------------------
203 // Lookup: Get a pointer to the value associated to the specified key.
204 // if any.
205 //
206 // Arguments:
207 // k - the key
208 //
209 // Return Value:
210 // A pointer to the value associated with the specified key or nullptr
211 // if the key is not found
212 //
213 // Notes:
214 // This is similar to `Lookup` but avoids copying the value and allows
215 // updating the value without using `Set`.
216 //
217 Value* LookupPointer(Key k) const
218 {
219 Node* pN = FindNode(k);
220
221 if (pN != nullptr)
222 {
223 return &(pN->m_val);
224 }
225 else
226 {
227 return nullptr;
228 }
229 }
230
231 //------------------------------------------------------------------------
232 // Set: Associate the specified value with the specified key.
233 //
234 // Arguments:
235 // k - the key
236 // v - the value
237 //
238 // Return Value:
239 // `true` if the key already exists, `false` otherwise.
240 //
241 // Notes:
242 // If the key already exists then its associated value is updated to
243 // the new value.
244 //
245 bool Set(Key k, Value v)
246 {
247 CheckGrowth();
248
249 assert(m_tableSizeInfo.prime != 0);
250
251 unsigned index = GetIndexForKey(k);
252
253 Node* pN = m_table[index];
254 while ((pN != nullptr) && !KeyFuncs::Equals(k, pN->m_key))
255 {
256 pN = pN->m_next;
257 }
258 if (pN != nullptr)
259 {
260 pN->m_val = v;
261 return true;
262 }
263 else
264 {
265 Node* pNewNode = new (m_alloc) Node(m_table[index], k, v);
266 m_table[index] = pNewNode;
267 m_tableCount++;
268 return false;
269 }
270 }
271
272 //------------------------------------------------------------------------
273 // Emplace: Associates the specified key with a value constructed in-place
274 // using the supplied args if the key is not already present.
275 //
276 // Arguments:
277 // k - the key
278 // args - the args used to construct the value
279 //
280 // Return Value:
281 // A pointer to the existing or newly constructed value.
282 //
283 template <class... Args>
284 Value* Emplace(Key k, Args&&... args)
285 {
286 CheckGrowth();
287
288 assert(m_tableSizeInfo.prime != 0);
289
290 unsigned index = GetIndexForKey(k);
291
292 Node* n = m_table[index];
293 while ((n != nullptr) && !KeyFuncs::Equals(k, n->m_key))
294 {
295 n = n->m_next;
296 }
297
298 if (n == nullptr)
299 {
300 n = new (m_alloc) Node(m_table[index], k, jitstd::forward<Args>(args)...);
301
302 m_table[index] = n;
303 m_tableCount++;
304 }
305
306 return &n->m_val;
307 }
308
309 //------------------------------------------------------------------------
310 // Remove: Remove the specified key and its associated value.
311 //
312 // Arguments:
313 // k - the key
314 //
315 // Return Value:
316 // `true` if the key exists, `false` otherwise.
317 //
318 // Notes:
319 // Removing a inexistent key is not an error.
320 //
321 bool Remove(Key k)
322 {
323 unsigned index = GetIndexForKey(k);
324
325 Node* pN = m_table[index];
326 Node** ppN = &m_table[index];
327 while ((pN != nullptr) && !KeyFuncs::Equals(k, pN->m_key))
328 {
329 ppN = &pN->m_next;
330 pN = pN->m_next;
331 }
332 if (pN != nullptr)
333 {
334 *ppN = pN->m_next;
335 m_tableCount--;
336 Node::operator delete(pN, m_alloc);
337 return true;
338 }
339 else
340 {
341 return false;
342 }
343 }
344
345 //------------------------------------------------------------------------
346 // RemoveAll: Remove all keys and their associated values.
347 //
348 // Notes:
349 // This also frees all the memory owned by the table.
350 //
351 void RemoveAll()
352 {
353 for (unsigned i = 0; i < m_tableSizeInfo.prime; i++)
354 {
355 for (Node* pN = m_table[i]; pN != nullptr;)
356 {
357 Node* pNext = pN->m_next;
358 Node::operator delete(pN, m_alloc);
359 pN = pNext;
360 }
361 }
362 m_alloc.deallocate(m_table);
363
364 m_table = nullptr;
365 m_tableSizeInfo = JitPrimeInfo();
366 m_tableCount = 0;
367 m_tableMax = 0;
368
369 return;
370 }
371
372 // Get an iterator to the first key in the table.
373 KeyIterator Begin() const
374 {
375 KeyIterator i(this, TRUE);
376 return i;
377 }
378
379 // Get an iterator following the last key in the table.
380 KeyIterator End() const
381 {
382 return KeyIterator(this, FALSE);
383 }
384
385 // Get the number of keys currently stored in the table.
386 unsigned GetCount() const
387 {
388 return m_tableCount;
389 }
390
391 // Get the allocator used by this hash table.
392 Allocator GetAllocator()
393 {
394 return m_alloc;
395 }
396
397private:
398 struct Node;
399
400 //------------------------------------------------------------------------
401 // GetIndexForKey: Get the bucket index for the specified key.
402 //
403 // Arguments:
404 // k - the key
405 //
406 // Return Value:
407 // A bucket index
408 //
409 unsigned GetIndexForKey(Key k) const
410 {
411 unsigned hash = KeyFuncs::GetHashCode(k);
412
413 unsigned index = m_tableSizeInfo.magicNumberRem(hash);
414
415 return index;
416 }
417
418 //------------------------------------------------------------------------
419 // FindNode: Return a pointer to the node having the specified key, if any.
420 //
421 // Arguments:
422 // k - the key
423 //
424 // Return Value:
425 // A pointer to the node or `nullptr` if the key is not found.
426 //
427 Node* FindNode(Key k) const
428 {
429 if (m_tableSizeInfo.prime == 0)
430 {
431 return nullptr;
432 }
433
434 unsigned index = GetIndexForKey(k);
435
436 Node* pN = m_table[index];
437 if (pN == nullptr)
438 {
439 return nullptr;
440 }
441
442 // Otherwise...
443 while ((pN != nullptr) && !KeyFuncs::Equals(k, pN->m_key))
444 {
445 pN = pN->m_next;
446 }
447
448 assert((pN == nullptr) || KeyFuncs::Equals(k, pN->m_key));
449
450 // If pN != nullptr, it's the node for the key, else the key isn't mapped.
451 return pN;
452 }
453
454 //------------------------------------------------------------------------
455 // Grow: Increase the size of the bucket table.
456 //
457 // Notes:
458 // The new size is computed based on the current population, growth factor,
459 // and maximum density factor.
460 //
461 void Grow()
462 {
463 unsigned newSize =
464 (unsigned)(m_tableCount * Behavior::s_growth_factor_numerator / Behavior::s_growth_factor_denominator *
465 Behavior::s_density_factor_denominator / Behavior::s_density_factor_numerator);
466
467 if (newSize < Behavior::s_minimum_allocation)
468 {
469 newSize = Behavior::s_minimum_allocation;
470 }
471
472 // handle potential overflow
473 if (newSize < m_tableCount)
474 {
475 Behavior::NoMemory();
476 }
477
478 Reallocate(newSize);
479 }
480
481 //------------------------------------------------------------------------
482 // CheckGrowth: Check if the maximum hashtable density has been reached
483 // and increase the size of the bucket table if necessary.
484 //
485 void CheckGrowth()
486 {
487 if (m_tableCount == m_tableMax)
488 {
489 Grow();
490 }
491 }
492
493public:
494 //------------------------------------------------------------------------
495 // CheckGrowth: Replace the bucket table with a larger one and copy all nodes
496 // from the existing bucket table.
497 //
498 // Notes:
499 // The new size must be large enough to hold all existing keys in
500 // the table without exceeding the density. Note that the actual
501 // table size must always be a prime number; the specified size
502 // will be increased to the next prime if necessary.
503 //
504 void Reallocate(unsigned newTableSize)
505 {
506 assert(newTableSize >=
507 (GetCount() * Behavior::s_density_factor_denominator / Behavior::s_density_factor_numerator));
508
509 // Allocation size must be a prime number. This is necessary so that hashes uniformly
510 // distribute to all indices, and so that chaining will visit all indices in the hash table.
511 JitPrimeInfo newPrime = NextPrime(newTableSize);
512 newTableSize = newPrime.prime;
513
514 Node** newTable = m_alloc.template allocate<Node*>(newTableSize);
515
516 for (unsigned i = 0; i < newTableSize; i++)
517 {
518 newTable[i] = nullptr;
519 }
520
521 // Move all entries over to new table (re-using the Node structures.)
522
523 for (unsigned i = 0; i < m_tableSizeInfo.prime; i++)
524 {
525 Node* pN = m_table[i];
526 while (pN != nullptr)
527 {
528 Node* pNext = pN->m_next;
529
530 unsigned newIndex = newPrime.magicNumberRem(KeyFuncs::GetHashCode(pN->m_key));
531 pN->m_next = newTable[newIndex];
532 newTable[newIndex] = pN;
533
534 pN = pNext;
535 }
536 }
537
538 if (m_table != nullptr)
539 {
540 m_alloc.deallocate(m_table);
541 }
542
543 m_table = newTable;
544 m_tableSizeInfo = newPrime;
545 m_tableMax =
546 (unsigned)(newTableSize * Behavior::s_density_factor_numerator / Behavior::s_density_factor_denominator);
547 }
548
549 // For iteration, we use a pattern similar to the STL "forward
550 // iterator" pattern. It basically consists of wrapping an
551 // "iteration variable" in an object, and providing pointer-like
552 // operators on the iterator. Example usage:
553 //
554 // for (JitHashTable::KeyIterator iter = foo->Begin(), end = foo->End(); !iter.Equal(end); iter++)
555 // {
556 // // use foo, iter.
557 // }
558 // iter.Get() will yield (a reference to) the
559 // current key. It will assert the equivalent of "iter != end."
560 class KeyIterator
561 {
562 private:
563 friend class JitHashTable;
564
565 Node** m_table;
566 Node* m_node;
567 unsigned m_tableSize;
568 unsigned m_index;
569
570 public:
571 //------------------------------------------------------------------------
572 // KeyIterator: Construct an iterator for the specified JitHashTable.
573 //
574 // Arguments:
575 // hash - the hashtable
576 // begin - `true` to construct an "begin" iterator,
577 // `false` to construct an "end" iterator
578 //
579 KeyIterator(const JitHashTable* hash, BOOL begin)
580 : m_table(hash->m_table)
581 , m_node(nullptr)
582 , m_tableSize(hash->m_tableSizeInfo.prime)
583 , m_index(begin ? 0 : m_tableSize)
584 {
585 if (begin && (hash->m_tableCount > 0))
586 {
587 assert(m_table != nullptr);
588 while ((m_index < m_tableSize) && (m_table[m_index] == nullptr))
589 {
590 m_index++;
591 }
592
593 if (m_index >= m_tableSize)
594 {
595 return;
596 }
597 else
598 {
599 m_node = m_table[m_index];
600 }
601 assert(m_node != nullptr);
602 }
603 }
604
605 //------------------------------------------------------------------------
606 // Get: Get a reference to this iterator's key.
607 //
608 // Return Value:
609 // A reference to this iterator's key.
610 //
611 // Assumptions:
612 // This must not be the "end" iterator.
613 //
614 const Key& Get() const
615 {
616 assert(m_node != nullptr);
617
618 return m_node->m_key;
619 }
620
621 //------------------------------------------------------------------------
622 // GetValue: Get a reference to this iterator's value.
623 //
624 // Return Value:
625 // A reference to this iterator's value.
626 //
627 // Assumptions:
628 // This must not be the "end" iterator.
629 //
630 Value& GetValue() const
631 {
632 assert(m_node != nullptr);
633
634 return m_node->m_val;
635 }
636
637 //------------------------------------------------------------------------
638 // SetValue: Assign a new value to this iterator's key
639 //
640 // Arguments:
641 // value - the value to assign
642 //
643 // Assumptions:
644 // This must not be the "end" iterator.
645 //
646 void SetValue(const Value& value) const
647 {
648 assert(m_node != nullptr);
649
650 m_node->m_val = value;
651 }
652
653 //------------------------------------------------------------------------
654 // Next: Advance the iterator to the next node.
655 //
656 // Notes:
657 // Advancing the end iterator has no effect.
658 //
659 void Next()
660 {
661 if (m_node != nullptr)
662 {
663 m_node = m_node->m_next;
664 if (m_node != nullptr)
665 {
666 return;
667 }
668
669 // Otherwise...
670 m_index++;
671 }
672 while ((m_index < m_tableSize) && (m_table[m_index] == nullptr))
673 {
674 m_index++;
675 }
676
677 if (m_index >= m_tableSize)
678 {
679 m_node = nullptr;
680 return;
681 }
682 else
683 {
684 m_node = m_table[m_index];
685 }
686 assert(m_node != nullptr);
687 }
688
689 // Return `true` if the specified iterator has the same position as this iterator
690 bool Equal(const KeyIterator& i) const
691 {
692 return i.m_node == m_node;
693 }
694
695 // Advance the iterator to the next node
696 void operator++()
697 {
698 Next();
699 }
700
701 // Advance the iterator to the next node
702 void operator++(int)
703 {
704 Next();
705 }
706 };
707
708 //------------------------------------------------------------------------
709 // operator[]: Get a reference to the value associated with the specified key.
710 //
711 // Arguments:
712 // k - the key
713 //
714 // Return Value:
715 // A reference to the value associated with the specified key.
716 //
717 // Notes:
718 // The specified key must exist.
719 //
720 Value& operator[](Key k) const
721 {
722 Value* p = LookupPointer(k);
723 assert(p);
724 return *p;
725 }
726
727private:
728 //------------------------------------------------------------------------
729 // NextPrime: Get a prime number greater than or equal to the specified number.
730 //
731 // Arguments:
732 // number - the minimum value
733 //
734 // Return Value:
735 // A prime number.
736 //
737 static JitPrimeInfo NextPrime(unsigned number)
738 {
739 for (int i = 0; i < (int)(_countof(jitPrimeInfo)); i++)
740 {
741 if (jitPrimeInfo[i].prime >= number)
742 {
743 return jitPrimeInfo[i];
744 }
745 }
746
747 // overflow
748 Behavior::NoMemory();
749 }
750
751 // The node type.
752 struct Node
753 {
754 Node* m_next; // Assume that the alignment requirement of Key and Value are no greater than Node*,
755 // so put m_next first to avoid unnecessary padding.
756 Key m_key;
757 Value m_val;
758
759 template <class... Args>
760 Node(Node* next, Key k, Args&&... args) : m_next(next), m_key(k), m_val(jitstd::forward<Args>(args)...)
761 {
762 }
763
764 void* operator new(size_t sz, Allocator alloc)
765 {
766 return alloc.template allocate<unsigned char>(sz);
767 }
768
769 void operator delete(void* p, Allocator alloc)
770 {
771 alloc.deallocate(p);
772 }
773 };
774
775 // Instance members
776 Allocator m_alloc; // Allocator to use in this table.
777 Node** m_table; // pointer to table
778 JitPrimeInfo m_tableSizeInfo; // size of table (a prime) and information about it
779 unsigned m_tableCount; // number of elements in table
780 unsigned m_tableMax; // maximum occupied count
781};
782
783// Commonly used KeyFuncs types:
784
785// Base class for types whose equality function is the same as their "==".
786template <typename T>
787struct JitKeyFuncsDefEquals
788{
789 static bool Equals(const T& x, const T& y)
790 {
791 return x == y;
792 }
793};
794
795template <typename T>
796struct JitPtrKeyFuncs : public JitKeyFuncsDefEquals<const T*>
797{
798public:
799 static unsigned GetHashCode(const T* ptr)
800 {
801 // Using the lower 32 bits of a pointer as a hashcode should be good enough.
802 // In fact, this should result in an unique hash code unless we allocate
803 // more than 4 gigabytes or if the virtual address space is fragmented.
804 return static_cast<unsigned>(reinterpret_cast<uintptr_t>(ptr));
805 }
806};
807
808template <typename T> // Must be coercible to "unsigned" with no loss of information.
809struct JitSmallPrimitiveKeyFuncs : public JitKeyFuncsDefEquals<T>
810{
811 static unsigned GetHashCode(const T& val)
812 {
813 return static_cast<unsigned>(val);
814 }
815};
816
817template <typename T> // Assumed to be of size sizeof(UINT64).
818struct JitLargePrimitiveKeyFuncs : public JitKeyFuncsDefEquals<T>
819{
820 static unsigned GetHashCode(const T val)
821 {
822 // A static cast when T is a float or a double converts the value (i.e. 0.25 converts to 0)
823 //
824 // Instead we want to use all of the bits of a float to create the hash value
825 // So we cast the address of val to a pointer to an equivalent sized unsigned int
826 // This allows us to read the actual bit representation of a float type
827 //
828 // We can't read beyond the end of val, so we use sizeof(T) to determine
829 // exactly how many bytes to read
830 //
831 if (sizeof(T) == 8)
832 {
833 // cast &val to (UINT64 *) then deref to get the bits
834 UINT64 asUINT64 = *(reinterpret_cast<const UINT64*>(&val));
835
836 // Get the upper and lower 32-bit values from the 64-bit value
837 UINT32 upper32 = static_cast<UINT32>(asUINT64 >> 32);
838 UINT32 lower32 = static_cast<UINT32>(asUINT64 & 0xFFFFFFFF);
839
840 // Exclusive-Or the upper32 and the lower32 values
841 return static_cast<unsigned>(upper32 ^ lower32);
842 }
843 else if (sizeof(T) == 4)
844 {
845 // cast &val to (UINT32 *) then deref to get the bits
846 UINT32 asUINT32 = *(reinterpret_cast<const UINT32*>(&val));
847
848 // Just return the 32-bit value
849 return static_cast<unsigned>(asUINT32);
850 }
851 else if ((sizeof(T) == 2) || (sizeof(T) == 1))
852 {
853 // For small sizes we must have an integer type
854 // so we can just use the static_cast.
855 //
856 return static_cast<unsigned>(val);
857 }
858 else
859 {
860 // Only support Hashing for types that are 8,4,2 or 1 bytes in size
861 assert(!"Unsupported size");
862 return static_cast<unsigned>(val); // compile-time error here when we have a illegal size
863 }
864 }
865};
866