1 /*========================== begin_copyright_notice ============================
2 
3 Copyright (C) 2017-2021 Intel Corporation
4 
5 SPDX-License-Identifier: MIT
6 
7 ============================= end_copyright_notice ===========================*/
8 
9 #pragma once
10 
11 #include "Object.h"
12 #include "Array.h"
13 #include "LinkedList.h"
14 
15 namespace iSTD
16 {
17 
18 /*****************************************************************************\
19 Struct: IsHashTableTypeSupported
20 \*****************************************************************************/
21 template<typename T>
22 struct IsHashTableTypeSupported                     { enum { value = false }; };
23 
24 template<>
25 struct IsHashTableTypeSupported<bool>               { enum { value = true }; };
26 
27 template<>
28 struct IsHashTableTypeSupported<char>               { enum { value = true }; };
29 
30 template<>
31 struct IsHashTableTypeSupported<unsigned char>      { enum { value = true }; };
32 
33 template<>
34 struct IsHashTableTypeSupported<int>                { enum { value = true }; };
35 
36 template<>
37 struct IsHashTableTypeSupported<unsigned int>       { enum { value = true }; };
38 
39 #ifndef __LP64__ // u/long on linux64 platform is 64-bit type and collides with U/INT64
40 template<>
41 struct IsHashTableTypeSupported<long>               { enum { value = true }; };
42 
43 template<>
44 struct IsHashTableTypeSupported<unsigned long>      { enum { value = true }; };
45 #endif
46 
47 template<>
48 struct IsHashTableTypeSupported<float>              { enum { value = true }; };
49 
50 template<>
51 struct IsHashTableTypeSupported<INT64>              { enum { value = true }; };
52 
53 template<>
54 struct IsHashTableTypeSupported<UINT64>             { enum { value = true }; };
55 
56 template<typename T>
57 struct IsHashTableTypeSupported<T*>                 { enum { value = true }; };
58 
59 /*****************************************************************************\
60 Template Parameters
61 \*****************************************************************************/
62 #define HashTableTemplateList       class KeyType, class ElementType, class CAllocatorType
63 #define CHashTableType              CHashTable<KeyType, ElementType, CAllocatorType>
64 
65 /*****************************************************************************\
66 
67 Class:
68     CHashTable
69 
70 Description:
71     Template Hash Table
72 
73 \*****************************************************************************/
74 template<HashTableTemplateList>
75 class CHashTable : public CObject<CAllocatorType>
76 {
77 public:
78 
79     // HashKey definition - converts KeyType to HashCode
80     class CHashKey : public CObject<CAllocatorType>
81     {
82     public:
83 
84         CHashKey( void );
85         CHashKey( const KeyType &keyValue );
86         CHashKey( const KeyType &keyValue, const DWORD hashCode );
87         CHashKey( const CHashKey &hashKey );
88         virtual ~CHashKey( void );
89 
90         DWORD   GetHashCode( void ) const;
91         const KeyType&  GetKeyValue( void ) const;
92 
93         bool        operator == ( const CHashKey &hashKey ) const;
94 
95     protected:
96 #ifdef _MSC_VER
97 #pragma warning( push )
98 #pragma warning( disable:4324 ) // structure was padded due to __declspec(align())
99 #endif
100         ALIGN(16)   KeyType     m_KeyValue;
101         ALIGN(16)   DWORD       m_HashCode;
102 #ifdef _MSC_VER
103 #pragma warning( pop )
104 #endif
105     };
106 
107     // Constructor \ Destructor
108     CHashTable( const DWORD size );
109     virtual ~CHashTable( void );
110 
111     // Interfaces using KeyType
112     bool    Add(
113                 const KeyType &key,
114                 const ElementType &element );
115 
116     bool    Get(
117                 const KeyType &key,
118                 ElementType &element ) const;
119 
120     bool    Remove(
121                 const KeyType &key,
122                 ElementType &element );
123 
124     bool    Remove(
125                 const ElementType &element );
126 
127     // Interfaces using HashKey
128     bool    Add(
129                 const CHashKey &hashKey,
130                 const ElementType &element );
131 
132     bool    Get(
133                 const CHashKey &hashKey,
134                 ElementType &element ) const;
135 
136     bool    Remove(
137                 const CHashKey &hashKey,
138                 ElementType &element );
139 
140     // Other interfaces
141     bool    IsEmpty( void ) const;
142     DWORD   GetCount( void ) const;
143 
144     void    DebugPrint( void ) const;
145 
146     C_ASSERT( IsHashTableTypeSupported<ElementType>::value == true );
147 
148 protected:
149 
150     // HashNode definition - hash table storage
151     class CHashNode : public CObject<CAllocatorType>
152     {
153     public:
154 
155         CHashNode( const CHashKey &hashKey, const ElementType &element );
156         virtual ~CHashNode( void );
157 
158         const CHashKey&     GetHashKey( void ) const;
159         ElementType         GetElement( void ) const;
160 
161     protected:
162 
163         CHashKey    m_HashKey;
164         ElementType m_Element;
165     };
166 
167     // Internal data structures - Array of Linked-Lists
168     typedef CLinkedList<CHashNode*, CAllocatorType>     CHashTableKeyList;
169     typedef CArray<CHashTableKeyList*, CAllocatorType>  CHashTableArray;
170 
171     CHashTableKeyList*  CreateHashKeyList( void );
172     void                DeleteHashKeyList( CHashTableKeyList* pHashKeyList );
173 
174     CHashNode*          CreateHashNode( const CHashKey &hashKey, const ElementType &element );
175     void                DeleteHashNode( CHashNode* pHashNode );
176 
177     DWORD   GetHashSize( const DWORD size ) const;
178     DWORD   GetHashIndex( const CHashKey &hashKey ) const;
179 
180     // Internal data
181     CHashTableArray     m_HashArray;
182 
183     DWORD   m_Count;
184 
185 #ifdef _DEBUG
186     DWORD   m_AddCount;
187     DWORD   m_RemoveCount;
188     DWORD   m_CollisionCount;
189 #endif
190 
191 public:
192 
193     // Iterator definition
194     class CIterator
195     {
196     public:
197 
198         CIterator( void );
199         CIterator( const CIterator &iterator );
200 
201         CIterator&  operator--( void );
202         CIterator&  operator++( void );
203 
204         bool operator==( const CIterator &iterator ) const;
205         bool operator!=( const CIterator &iterator ) const;
206 
207         CIterator&  operator=( const CIterator &iterator );
208         ElementType operator*( void );
209 
210         const KeyType&  GetKeyValue( void );
211 
212         friend class CHashTable;
213 
214     protected:
215 
216         CHashTableArray*    m_Array;
217         DWORD               m_ArrayIndex;
218 
219         typename CHashTableKeyList::CIterator m_Iterator;
220     };
221 
222     // Begin \ End iterators of HashTable
223     CIterator   Begin( void ) const;
224     CIterator   End( void ) const;
225 
226     // Interfaces using Iterator
227     bool    Add(
228                 const CHashKey &hashKey,
229                 const ElementType &element,
230                 CIterator &iterator );
231 
232     bool    Get(
233                 const CHashKey &hashKey,
234                 CIterator &iterator ) const;
235 
236     bool    Remove(
237                 CIterator iterator );
238 };
239 
240 /*****************************************************************************\
241 
242 Function:
243     CHashTable Constructor
244 
245 Description:
246     Initializes internal data
247 
248 Input:
249     const DWORD size - max size of the hash table
250 
251 Output:
252     none
253 
254 \*****************************************************************************/
255 template<HashTableTemplateList>
256 CHashTableType::CHashTable( const DWORD size )
257     : CObject<CAllocatorType>(),
258       m_HashArray( GetHashSize( size ) )
259 {
260     m_Count = 0;
261 
262 #ifdef _DEBUG
263     m_AddCount = 0;
264     m_RemoveCount = 0;
265     m_CollisionCount = 0;
266 #endif
267 }
268 
269 /*****************************************************************************\
270 
271 Function:
272     CHashTable Destructor
273 
274 Description:
275     Deletes internal data
276 
277 Input:
278     none
279 
280 Output:
281     none
282 
283 \*****************************************************************************/
284 template<HashTableTemplateList>
285 CHashTableType::~CHashTable( void )
286 {
287     const DWORD size = m_HashArray.GetSize();
288     for( DWORD i = 0; i < size; ++i )
289     {
290         CHashTableKeyList* pHashKeyList = m_HashArray.GetElement(i);
291         if( pHashKeyList )
292         {
293             DeleteHashKeyList( pHashKeyList );
294         }
295     }
296 }
297 
298 /*****************************************************************************\
299 
300 Function:
301     CHashTable::Add
302 
303 Description:
304     Adds an element to the hash table
305 
306 Input:
307     const KeyType &key - the key to which the element is referenced
308     const ElementType &element - the element to be added
309 
310 Output:
311     bool - SUCCESS or FAIL
312 
313 \*****************************************************************************/
314 template<HashTableTemplateList>
315 bool CHashTableType::Add(
316     const KeyType &key,
317     const ElementType &element )
318 {
319     CHashKey hashKey( key );
320     return Add( hashKey, element );
321 }
322 
323 /*****************************************************************************\
324 
325 Function:
326     CHashTable::Get
327 
328 Description:
329     Gets the element in the hash table referenced by the key
330 
331 Input:
332     const KeyType &key - the key of the element to get
333 
334 Output:
335     ElementType &element - the element
336     bool - SUCCESS or FAIL
337 
338 \*****************************************************************************/
339 template<HashTableTemplateList>
340 bool CHashTableType::Get(
341     const KeyType &key,
342     ElementType &element ) const
343 {
344     CHashKey hashKey( key );
345     return Get( hashKey, element );
346 }
347 
348 /*****************************************************************************\
349 
350 Function:
351     CHashTable::Remove
352 
353 Description:
354     Removes an element from the hash table
355 
356 Input:
357     const KeyType &key - the key of the element to remove
358 
359 Output:
360     ElementType &element - the element
361     bool - SUCCESS or FAIL
362 
363 \*****************************************************************************/
364 template<HashTableTemplateList>
365 bool CHashTableType::Remove(
366     const KeyType &key,
367     ElementType &element )
368 {
369     CHashKey hashKey( key );
370     return Remove( hashKey, element );
371 }
372 
373 /*****************************************************************************\
374 
375 Function:
376     CHashTable::Remove
377 
378 Description:
379     Removes an element from the hash table
380 
381 Input:
382     ElementType &element - the element to remove
383 
384 Output:
385     bool - SUCCESS or FAIL
386 
387 \*****************************************************************************/
388 template<HashTableTemplateList>
389 bool CHashTableType::Remove(
390     const ElementType &element )
391 {
392     // Walk the entire array to find the element
393     const DWORD size = m_HashArray.GetSize();
394     for( DWORD i = 0; i < size; ++i )
395     {
396         CHashTableKeyList* pHashKeyList = m_HashArray.GetElement(i);
397         if( pHashKeyList )
398         {
399             // Search the list for the node with the same element
400             typename CHashTableKeyList::CIterator iterator = pHashKeyList->Begin();
401 
402             while( iterator != pHashKeyList->End() )
403             {
404                 CHashNode* pHashNode = (*iterator);
405 
406                 if( pHashNode->GetElement() == element )
407                 {
408                     if( pHashKeyList->Remove( iterator ) )
409                     {
410                         DeleteHashNode( pHashNode );
411 
412                         if( pHashKeyList->IsEmpty() )
413                         {
414                             m_HashArray.SetElement( i, NULL );
415                             DeleteHashKeyList( pHashKeyList );
416                         }
417 
418                         ASSERT( m_Count > 0 );
419                         --m_Count;
420 
421 #ifdef _DEBUG
422                         ++m_RemoveCount;
423 #endif
424                         return true;
425                     }
426                     else
427                     {
428                         ASSERT(0);
429                         return false;
430                     }
431                 }
432 
433                 ++iterator;
434             }
435         }
436     }
437 
438     // Element was not found
439     ASSERT(0);
440     return false;
441 }
442 
443 /*****************************************************************************\
444 
445 Function:
446     CHashTable::Add
447 
448 Description:
449     Adds an element to the hash table
450 
451 Input:
452     const CHashKey &hashKey - the key to which the element is referenced
453     const ElementType &element - the element to be added
454 
455 Output:
456     bool - SUCCESS or FAIL
457 
458 \*****************************************************************************/
459 template<HashTableTemplateList>
460 bool CHashTableType::Add(
461     const CHashKey &hashKey,
462     const ElementType &element )
463 {
464     if( m_HashArray.GetSize() == 0 )
465     {
466         return false;
467     }
468     const DWORD index = GetHashIndex( hashKey );
469     ASSERT( index < m_HashArray.GetSize() );
470 
471     CHashTableKeyList* pHashKeyList = m_HashArray.GetElement( index );
472 
473     // Use the hash code to find a linked list containing all keys with the
474     // same hash code
475     if( !pHashKeyList )
476     {
477         // if the list doesn't exist then create a new one
478         pHashKeyList = CreateHashKeyList();
479 
480         if( pHashKeyList )
481         {
482             // Add the new hash key list to hash array
483             if( !m_HashArray.SetElement( index, pHashKeyList ) )
484             {
485                 ASSERT(0);
486                 SafeDelete( pHashKeyList );
487                 return false;
488             }
489         }
490         else
491         {
492             ASSERT(0);
493             return false;
494         }
495     }
496 
497     // Create the node to add to the list
498     CHashNode* pHashNode = CreateHashNode( hashKey, element );
499 
500     if( pHashNode )
501     {
502         // Add the node to the hash key list
503         if( pHashKeyList->Add( pHashNode ) )
504         {
505             ++m_Count;
506 
507 #ifdef _DEBUG
508             ++m_AddCount;
509 
510             if( pHashKeyList->GetCount() > 1 )
511             {
512                 ++m_CollisionCount;
513             }
514 #endif
515             return true;
516         }
517         else
518         {
519             DeleteHashNode( pHashNode );
520 
521             ASSERT(0);
522             return false;
523         }
524     }
525     else
526     {
527         ASSERT(0);
528         return false;
529     }
530 }
531 
532 /*****************************************************************************\
533 
534 Function:
535     CHashTable::Get
536 
537 Description:
538     Gets the element in the hash table referenced by the key
539 
540 Input:
541     const CHashKey &hashKey - the key of the element to get
542 
543 Output:
544     ElementType &element - the element
545     bool - SUCCESS or FAIL
546 
547 \*****************************************************************************/
548 template<HashTableTemplateList>
549 bool CHashTableType::Get(
550     const CHashKey &hashKey,
551     ElementType &element ) const
552 {
553     if( m_HashArray.GetSize() != 0 )
554     {
555         const DWORD index = GetHashIndex( hashKey );
556         ASSERT( index < m_HashArray.GetSize() );
557 
558         CHashTableKeyList* pHashKeyList = m_HashArray.GetElement( index );
559 
560         if( pHashKeyList )
561         {
562             // Search the list for the node with the same key
563             typename CHashTableKeyList::CIterator iterator = pHashKeyList->Begin();
564 
565             while( iterator != pHashKeyList->End() )
566             {
567                 CHashNode* pHashNode = (*iterator);
568 
569                 if( pHashNode->GetHashKey() == hashKey )
570                 {
571                     element = pHashNode->GetElement();
572                     return true;
573                 }
574 
575                 ++iterator;
576             }
577         }
578     }
579     return false;
580 }
581 
582 /*****************************************************************************\
583 
584 Function:
585     CHashTable::Remove
586 
587 Description:
588     Removes an element from the hash table
589 
590 Input:
591     const CHashKey &hashKey - the key of the element to remove
592 
593 Output:
594     ElementType &element - the element
595     bool - SUCCESS or FAIL
596 
597 \*****************************************************************************/
598 template<HashTableTemplateList>
599 bool CHashTableType::Remove(
600     const CHashKey &hashKey,
601     ElementType &element )
602 {
603     if( m_HashArray.GetSize() != 0 )
604     {
605         const DWORD index = GetHashIndex( hashKey );
606         ASSERT( index < m_HashArray.GetSize() );
607 
608         CHashTableKeyList* pHashKeyList = m_HashArray.GetElement( index );
609 
610         if( pHashKeyList )
611         {
612             // Search the list for the node with the same key
613             typename CHashTableKeyList::CIterator iterator = pHashKeyList->Begin();
614 
615             while( iterator != pHashKeyList->End() )
616             {
617                 CHashNode* pHashNode = (*iterator);
618 
619                 if( pHashNode->GetHashKey() == hashKey )
620                 {
621                     element = pHashNode->GetElement();
622 
623                     if( pHashKeyList->Remove( iterator ) )
624                     {
625                         DeleteHashNode( pHashNode );
626 
627                         if( pHashKeyList->IsEmpty() )
628                         {
629                             m_HashArray.SetElement( index, NULL );
630                             DeleteHashKeyList( pHashKeyList );
631                         }
632 
633                         ASSERT( m_Count > 0 );
634                         --m_Count;
635 
636     #ifdef _DEBUG
637                         ++m_RemoveCount;
638     #endif
639                         return true;
640                     }
641                     else
642                     {
643                         ASSERT(0);
644                         return false;
645                     }
646                 }
647 
648                 ++iterator;
649             }
650         }
651     }
652 
653     ASSERT(0);
654     return false;
655 }
656 
657 /*****************************************************************************\
658 
659 Function:
660     CHashTable::IsEmpty
661 
662 Description:
663     Determines if the hash table is empty
664 
665 Input:
666     void
667 
668 Output:
669     bool
670 
671 \*****************************************************************************/
672 template<HashTableTemplateList>
673 bool CHashTableType::IsEmpty( void ) const
674 {
675     return ( m_Count == 0 );
676 }
677 
678 /*****************************************************************************\
679 
680 Function:
681     CHashTable::GetCount
682 
683 Description:
684     Returns number of elements.
685 
686 Input:
687     void
688 
689 Output:
690     DWORD
691 
692 \*****************************************************************************/
693 template<HashTableTemplateList>
694 DWORD CHashTableType::GetCount( void ) const
695 {
696     return m_Count;
697 }
698 
699 /*****************************************************************************\
700 
701 Function:
702     CHashTable::DebugPrint
703 
704 Description:
705     Prints the hashtable to std output for debug only
706 
707 Input:
708     none
709 
710 Output:
711     none
712 
713 \*****************************************************************************/
714 template<HashTableTemplateList>
715 void CHashTableType::DebugPrint( void ) const
716 {
717 #ifdef _DEBUG
718     DPF( GFXDBG_STDLIB, "%s\n", __FUNCTION__ );
719     DPF( GFXDBG_STDLIB, "\tAddress = %p\n", this );
720 
721     DPF( GFXDBG_STDLIB, "\tCount = %u\n", m_Count );
722     DPF( GFXDBG_STDLIB, "\tAdd Count = %u\n", m_AddCount );
723     DPF( GFXDBG_STDLIB, "\tRemove Count = %u\n", m_RemoveCount );
724     DPF( GFXDBG_STDLIB, "\tCollision Count = %u\n", m_CollisionCount );
725 
726     for( DWORD i = 0; i < m_HashArray.GetSize(); i++ )
727     {
728         CHashTableKeyList* pHashKeyList = m_HashArray.GetElement(i);
729 
730         if( pHashKeyList )
731         {
732             DPF( GFXDBG_STDLIB, "\tHashArray.Element[%u].Count = %u\n",
733                 i,
734                 pHashKeyList->GetCount() );
735         }
736         else
737         {
738             DPF( GFXDBG_STDLIB, "\tHashArray.Element[%u].Count = 0\n",
739                 i );
740         }
741     }
742 #endif
743 }
744 
745 /*****************************************************************************\
746 
747 Function:
748     CHashTable::CreateHashKeyList
749 
750 Description:
751     Creates a hashtable key list
752 
753 Input:
754     none
755 
756 Output:
757     CHashTableKeyList*
758 
759 \*****************************************************************************/
760 template<HashTableTemplateList>
761 typename CHashTableType::CHashTableKeyList* CHashTableType::CreateHashKeyList( void )
762 {
763     CHashTableKeyList* pHashKeyList = new CHashTableKeyList();
764     ASSERT( pHashKeyList );
765     return pHashKeyList;
766 }
767 
768 /*****************************************************************************\
769 
770 Function:
771     CHashTable::DeleteHashKeyList
772 
773 Description:
774     Deletes a hashtable key list
775 
776 Input:
777     CHashTableKeyList* pHashKeyList
778 
779 Output:
780     none
781 
782 \*****************************************************************************/
783 template<HashTableTemplateList>
784 void CHashTableType::DeleteHashKeyList(
785     CHashTableKeyList* pHashKeyList )
786 {
787     if( pHashKeyList )
788     {
789         while( !pHashKeyList->IsEmpty() )
790         {
791             typename CHashTableKeyList::CIterator iterator = pHashKeyList->Begin();
792 
793             CHashNode* pHashNode = (*iterator);
794             DeleteHashNode( pHashNode );
795 
796             pHashKeyList->Remove( iterator );
797         }
798 
799         iSTD::SafeDelete( pHashKeyList );
800     }
801 }
802 
803 /*****************************************************************************\
804 
805 Function:
806     CHashTable::CreateHashNode
807 
808 Description:
809     Creates a hashtable list node
810 
811 Input:
812     const CHashKey &hashKey
813     const ElementType &element
814 
815 Output:
816     CHashNode*
817 
818 \*****************************************************************************/
819 template<HashTableTemplateList>
820 typename CHashTableType::CHashNode* CHashTableType::CreateHashNode(
821     const CHashKey &hashKey,
822     const ElementType &element )
823 {
824     CHashNode* pHashNode = new CHashNode( hashKey, element );
825     ASSERT( pHashNode );
826     return pHashNode;
827 }
828 
829 /*****************************************************************************\
830 
831 Function:
832     CHashTable::DeleteHashNode
833 
834 Description:
835     Deletes a hashtable list node
836 
837 Input:
838     CHashNode* pHashNode
839 
840 Output:
841     none
842 
843 \*****************************************************************************/
844 template<HashTableTemplateList>
845 void CHashTableType::DeleteHashNode( CHashNode* pHashNode )
846 {
847     if( pHashNode )
848     {
849         iSTD::SafeDelete( pHashNode );
850     }
851 }
852 
853 /*****************************************************************************\
854 
855 Function:
856     CHashTable::GetHashSize
857 
858 Description:
859     Determines the size of the hash array
860 
861 Input:
862     const DWORD size - max number of elements in the hash table
863 
864 Output:
865     DWORD
866 
867 \*****************************************************************************/
868 template<HashTableTemplateList>
869 DWORD CHashTableType::GetHashSize( const DWORD size ) const
870 {
871     // the size of the hash table array is a large prime number near but
872     // smaller than the maximum size of the cache but not near a power of two
873     if( size >= 6151 )
874     {
875         return 6151;
876     }
877     else if( size >= 3079 )
878     {
879         return 3079;
880     }
881     else if( size >= 1543 )
882     {
883         return 1543;
884     }
885     else if( size >= 769 )
886     {
887         return 769;
888     }
889     else if( size >= 389 )
890     {
891         return 389;
892     }
893     else if( size >= 193 )
894     {
895         return 193;
896     }
897     else if( size >= 97 )
898     {
899         return 97;
900     }
901     else
902     {
903         return 53;
904     }
905 }
906 
907 /*****************************************************************************\
908 
909 Function:
910     CHashTable::GetHashIndex
911 
912 Description:
913     Determines the index in the hash array for the hash key
914 
915 Input:
916     const CHashKey &hashKey
917 
918 Output:
919     DWORD
920 
921 \*****************************************************************************/
922 template<HashTableTemplateList>
923 DWORD CHashTableType::GetHashIndex( const CHashKey &hashKey ) const
924 {
925     return ( hashKey.GetHashCode() % m_HashArray.GetSize() );
926 }
927 
928 /*****************************************************************************\
929 
930 Function:
931     CHashKey constructor
932 
933 Description:
934     Initializes internal data
935 
936 Input:
937     void
938 
939 Output:
940     none
941 
942 \*****************************************************************************/
943 template<HashTableTemplateList>
944 CHashTableType::CHashKey::CHashKey( void )
945     : CObject<CAllocatorType>()
946 {
947     SafeMemSet( &m_KeyValue, 0, sizeof(KeyType) );
948     m_HashCode = 0;
949 }
950 
951 /*****************************************************************************\
952 
953 Function:
954     CHashKey constructor
955 
956 Description:
957     Initializes internal data
958 
959 Input:
960     const KeyType &keyValue
961 
962 Output:
963     none
964 
965 \*****************************************************************************/
966 template<HashTableTemplateList>
967 CHashTableType::CHashKey::CHashKey( const KeyType &keyValue )
968     : CObject<CAllocatorType>()
969 {
970 #if defined(_WIN32) && defined(_MSC_VER)
971     ASSERT( IsAligned( &m_KeyValue, sizeof(DQWORD) ) );
972     ASSERT( IsAligned( &m_HashCode, sizeof(DQWORD) ) );
973 
974     m_KeyValue = keyValue;
975     ASSERT( m_KeyValue == keyValue );
976 
977     if( sizeof(KeyType) < sizeof(DQWORD) )
978     {
979         const DWORD* pKeyValue = (const DWORD*)&m_KeyValue;
980         m_HashCode = *pKeyValue++;
981 
982         const DWORD count = (DWORD)( sizeof(KeyType) / sizeof(DWORD) );
983         for( DWORD i = 1; i < count; ++i )
984         {
985             const DWORD data = *pKeyValue++;
986             m_HashCode = ( m_HashCode << 1 ) ^ data;
987         }
988     }
989     else
990     {
991         const DWORD szAlignedKeyValue = (DWORD)(
992             ( ( ( sizeof(KeyType) - 1 ) / sizeof(DQWORD) ) + 1 )  * sizeof(DQWORD) );
993 
994         const DWORD szPad = szAlignedKeyValue - (DWORD)sizeof(KeyType);
995 
996         // Initialize structure padding due to packing alignment
997         if( szPad )
998         {
999             SafeMemSet( (BYTE*)&m_KeyValue + sizeof(KeyType), 0, szPad );
1000         }
1001 
1002         // Generate hash code
1003         const __m128i* pKeyValue = (const __m128i*)&m_KeyValue;
1004         __m128i hash = _mm_load_si128( pKeyValue++ );
1005 
1006         const DWORD count = szAlignedKeyValue / sizeof(DQWORD);
1007         for( DWORD i = 1; i < count; ++i )
1008         {
1009             const __m128i data = _mm_load_si128( pKeyValue++ );
1010             hash = _mm_xor_si128( _mm_slli_si128( hash, 1 ), data );
1011         }
1012 
1013         // Combine four 32-bit integers into single 32-bit integer
1014         hash = _mm_xor_si128(
1015             _mm_unpackhi_epi32( hash, hash ),
1016             _mm_unpacklo_epi32( hash, hash ) );
1017         hash = _mm_xor_si128(
1018             _mm_shuffle_epi32( hash, 0x2 ),
1019             hash );
1020         m_HashCode = _mm_cvtsi128_si32( hash );
1021     }
1022 #else // _MSC_VER
1023     ASSERT( IsAligned( &m_KeyValue, sizeof(DWORD) ) );
1024     ASSERT( IsAligned( &m_HashCode, sizeof(DWORD) ) );
1025 
1026     m_KeyValue = keyValue;
1027     ASSERT( m_KeyValue == keyValue );
1028 
1029     const DWORD* pKeyValue = (const DWORD*)&m_KeyValue;
1030     m_HashCode = *pKeyValue++;
1031 
1032     const DWORD count = (DWORD)( sizeof(KeyType) / sizeof(DWORD) );
1033     for( DWORD i = 1; i < count; ++i )
1034     {
1035         const DWORD data = *pKeyValue++;
1036         m_HashCode = ( m_HashCode << 1 ) ^ data;
1037     }
1038 #endif // _MSC_VER
1039 }
1040 
1041 
1042 /*****************************************************************************\
1043 
1044 Function:
1045     CHashKey constructor
1046 
1047 Description:
1048     Initializes internal data
1049 
1050 Input:
1051     const KeyType &keyValue
1052     const DWORD hashCode
1053 
1054 Output:
1055     none
1056 
1057 \*****************************************************************************/
1058 template<HashTableTemplateList>
1059 CHashTableType::CHashKey::CHashKey( const KeyType &keyValue, const DWORD hashCode )
1060     : CObject<CAllocatorType>()
1061 {
1062     m_KeyValue = keyValue;
1063     ASSERT( m_KeyValue == keyValue );
1064     m_HashCode = hashCode;
1065 }
1066 
1067 /*****************************************************************************\
1068 
1069 Function:
1070     CHashKey copy constructor
1071 
1072 Description:
1073     Initializes internal data
1074 
1075 Input:
1076     const CHashKey &hashKey
1077 
1078 Output:
1079     none
1080 
1081 \*****************************************************************************/
1082 template<HashTableTemplateList>
1083 CHashTableType::CHashKey::CHashKey( const CHashKey &hashKey )
1084 {
1085     m_KeyValue = hashKey.m_KeyValue;
1086     m_HashCode = hashKey.m_HashCode;
1087 }
1088 
1089 /*****************************************************************************\
1090 
1091 Function:
1092     CHashKey destructor
1093 
1094 Description:
1095     Deletes internal data
1096 
1097 Input:
1098     none
1099 
1100 Output:
1101     none
1102 
1103 \*****************************************************************************/
1104 template<HashTableTemplateList>
1105 CHashTableType::CHashKey::~CHashKey( void )
1106 {
1107 }
1108 
1109 /*****************************************************************************\
1110 
1111 Function:
1112     CHashKey::GetHashCode
1113 
1114 Description:
1115     Returns the 32-bit hash code
1116 
1117 Input:
1118     none
1119 
1120 Output:
1121     DWORD
1122 
1123 \*****************************************************************************/
1124 template<HashTableTemplateList>
1125 DWORD CHashTableType::CHashKey::GetHashCode( void ) const
1126 {
1127     return m_HashCode;
1128 }
1129 
1130 /*****************************************************************************\
1131 
1132 Function:
1133     CHashKey::GetKeyValue
1134 
1135 Description:
1136     Returns the key value
1137 
1138 Input:
1139     none
1140 
1141 Output:
1142     const KeyType&
1143 
1144 \*****************************************************************************/
1145 template<HashTableTemplateList>
1146 const KeyType& CHashTableType::CHashKey::GetKeyValue( void ) const
1147 {
1148     return m_KeyValue;
1149 }
1150 
1151 /*****************************************************************************\
1152 
1153 Function:
1154     CHashKey::operator ==
1155 
1156 Description:
1157     Determines if the hash keys are equal
1158 
1159 Input:
1160     const CHashKey &hashKey
1161 
1162 Output:
1163     bool - true or false
1164 
1165 \*****************************************************************************/
1166 template<HashTableTemplateList>
1167 inline bool CHashTableType::CHashKey::operator == ( const CHashKey &hashKey ) const
1168 {
1169     if( m_HashCode == hashKey.m_HashCode )
1170     {
1171         return ( m_KeyValue == hashKey.m_KeyValue );
1172     }
1173     else
1174     {
1175         return false;
1176     }
1177 }
1178 
1179 /*****************************************************************************\
1180 
1181 Function:
1182     CHashNode constructor
1183 
1184 Description:
1185     Initializes internal data
1186 
1187 Input:
1188     const CHashKey &hashKey
1189     const ElementType &element
1190 
1191 Output:
1192     none
1193 
1194 \*****************************************************************************/
1195 template<HashTableTemplateList>
1196 CHashTableType::CHashNode::CHashNode(
1197     const CHashKey &hashKey,
1198     const ElementType &element )
1199     : CObject<CAllocatorType>(),
1200       m_HashKey( hashKey )
1201 {
1202     m_Element = element;
1203 }
1204 
1205 /*****************************************************************************\
1206 
1207 Function:
1208     CHashNode destructor
1209 
1210 Description:
1211     Deletes internal data
1212 
1213 Input:
1214     none
1215 
1216 Output:
1217     none
1218 
1219 \*****************************************************************************/
1220 template<HashTableTemplateList>
1221 CHashTableType::CHashNode::~CHashNode( void )
1222 {
1223 }
1224 
1225 /*****************************************************************************\
1226 
1227 Function:
1228     CHashKey::GetHashKey
1229 
1230 Description:
1231     Returns the hash key
1232 
1233 Input:
1234     none
1235 
1236 Output:
1237     const CHashKey&
1238 
1239 \*****************************************************************************/
1240 template<HashTableTemplateList>
1241 const typename CHashTableType::CHashKey& CHashTableType::CHashNode::GetHashKey( void ) const
1242 {
1243     return m_HashKey;
1244 }
1245 
1246 /*****************************************************************************\
1247 
1248 Function:
1249     CHashKey::GetElement
1250 
1251 Description:
1252     Returns the element
1253 
1254 Input:
1255     none
1256 
1257 Output:
1258     ElementType
1259 
1260 \*****************************************************************************/
1261 template<HashTableTemplateList>
1262 ElementType CHashTableType::CHashNode::GetElement( void ) const
1263 {
1264     return m_Element;
1265 }
1266 
1267 /*****************************************************************************\
1268 
1269 Function:
1270     CHashTable::CIterator constructor
1271 
1272 Description:
1273     Default constructor
1274 
1275 Input:
1276     none
1277 
1278 Output:
1279     none
1280 
1281 \*****************************************************************************/
1282 template<HashTableTemplateList>
1283 CHashTableType::CIterator::CIterator( void )
1284     : m_Iterator()
1285 {
1286     m_Array = NULL;
1287     m_ArrayIndex = 0;
1288 }
1289 
1290 /*****************************************************************************\
1291 
1292 Function:
1293     CHashTable::CIterator copy constructor
1294 
1295 Description:
1296     Copy constructor
1297 
1298 Input:
1299     none
1300 
1301 Output:
1302     none
1303 
1304 \*****************************************************************************/
1305 template<HashTableTemplateList>
1306 CHashTableType::CIterator::CIterator( const CIterator &iterator )
1307     : m_Iterator( iterator.m_Iterator )
1308 {
1309     m_Array = iterator.m_Array;
1310     m_ArrayIndex = iterator.m_ArrayIndex;
1311 }
1312 
1313 /*****************************************************************************\
1314 
1315 Function:
1316     CHashTable::CIterator operator--
1317 
1318 Description:
1319     Iterates backwards through the hash table via predecrement
1320 
1321 Input:
1322     none
1323 
1324 Output:
1325     CHashTable::CIterator& - iterator of previous entry
1326 
1327 \*****************************************************************************/
1328 template<HashTableTemplateList>
1329 typename CHashTableType::CIterator& CHashTableType::CIterator::operator--( void )
1330 {
1331     --m_Iterator;
1332 
1333     CHashTableKeyList* pHashKeyList = m_Array->GetElement( m_ArrayIndex );
1334     ASSERT( pHashKeyList );
1335 
1336     while( ( m_Iterator == pHashKeyList->End() ) && ( m_ArrayIndex != 0 ) )
1337     {
1338         CHashTableKeyList* pPrevHashKeyList = m_Array->GetElement( --m_ArrayIndex );
1339         if( pPrevHashKeyList )
1340         {
1341             pHashKeyList = pPrevHashKeyList;
1342             m_Iterator = pHashKeyList->End();
1343             --m_Iterator;
1344         }
1345     }
1346 
1347     return *this;
1348 }
1349 
1350 /*****************************************************************************\
1351 
1352 Function:
1353     CHashTable::CIterator operator++
1354 
1355 Description:
1356     Iterates forwards through the hash table via preincrement
1357 
1358 Input:
1359     none
1360 
1361 Output:
1362     CHashTable::CIterator& - iterator of next entry
1363 
1364 \*****************************************************************************/
1365 template<HashTableTemplateList>
1366 typename CHashTableType::CIterator& CHashTableType::CIterator::operator++( void )
1367 {
1368     ++m_Iterator;
1369 
1370     CHashTableKeyList* pHashKeyList = m_Array->GetElement( m_ArrayIndex );
1371     ASSERT( pHashKeyList );
1372 
1373     const DWORD maxIndex = m_Array->GetSize() - 1;
1374     while( ( m_Iterator == pHashKeyList->End() ) && ( m_ArrayIndex != maxIndex ) )
1375     {
1376         CHashTableKeyList* pNextHashKeyList = m_Array->GetElement( ++m_ArrayIndex );
1377         if( pNextHashKeyList )
1378         {
1379             pHashKeyList = pNextHashKeyList;
1380             m_Iterator = pHashKeyList->Begin();
1381         }
1382     }
1383 
1384     return *this;
1385 }
1386 
1387 /*****************************************************************************\
1388 
1389 Function:
1390     CHashTable::CIterator::operator==
1391 
1392 Description:
1393     Determines if the iterators are equal
1394 
1395 Input:
1396     const CIterator& - pointer to the iterator to compare to.
1397 
1398 Output:
1399     bool - true if this iterator and the passed-in iterator point to the same
1400            hash table node.
1401 
1402 \*****************************************************************************/
1403 template<HashTableTemplateList>
1404 bool CHashTableType::CIterator::operator==(
1405     const CIterator& iterator ) const
1406 {
1407     return m_Iterator == iterator.m_Iterator;
1408 }
1409 
1410 /*****************************************************************************\
1411 
1412 Function:
1413     CHashTable::CIterator::operator!=
1414 
1415 Description:
1416     Determines if the iterators are not equal
1417 
1418 Input:
1419     const CIterator& - pointer to the iterator to compare to.
1420 
1421 Output:
1422     bool - true if this iterator and the passed-in iterator point to different
1423            hash table nodes.
1424 
1425 \*****************************************************************************/
1426 template<HashTableTemplateList>
1427 bool CHashTableType::CIterator::operator!=(
1428     const CIterator& iterator ) const
1429 {
1430     return m_Iterator != iterator.m_Iterator;
1431 }
1432 
1433 /*****************************************************************************\
1434 
1435 Function:
1436     CHashTable::CIterator::operator=
1437 
1438 Description:
1439     Sets the iterators equal
1440 
1441 Input:
1442     const CIterator& - reference to the iterator to copy from.
1443 
1444 Output:
1445     const CIterator & - reference to self
1446 
1447 \*****************************************************************************/
1448 template<HashTableTemplateList>
1449 typename CHashTableType::CIterator& CHashTableType::CIterator::operator=(
1450     const CIterator &iterator )
1451 {
1452     m_Array = iterator.m_Array;
1453     m_ArrayIndex = iterator.m_ArrayIndex;
1454     m_Iterator = iterator.m_Iterator;
1455     return *this;
1456 }
1457 
1458 /*****************************************************************************\
1459 
1460 Function:
1461     CHashTable::CIterator::operator*
1462 
1463 Description:
1464     Returns a reference to the element that this iterator points to
1465 
1466 Input:
1467     none
1468 
1469 Output:
1470     ElementType
1471 
1472 \*****************************************************************************/
1473 template<HashTableTemplateList>
1474 ElementType CHashTableType::CIterator::operator*( void )
1475 {
1476     return (*m_Iterator)->GetElement();
1477 }
1478 
1479 /*****************************************************************************\
1480 
1481 Function:
1482     CHashTable::CIterator::GetKey()
1483 
1484 Description:
1485     Returns key value.
1486 
1487 Input:
1488     none
1489 
1490 Output:
1491     KeyType
1492 
1493 \*****************************************************************************/
1494 template<HashTableTemplateList>
1495 const KeyType& CHashTableType::CIterator::GetKeyValue( void )
1496 {
1497     return (*m_Iterator)->GetHashKey().GetKeyValue();
1498 }
1499 
1500 /*****************************************************************************\
1501 
1502 Function:
1503     CHashTable::Begin
1504 
1505 Description:
1506     Returns an iterator to the first node in the hash table.
1507 
1508 Input:
1509     none
1510 
1511 Output:
1512     CHashTable::CIterator
1513 
1514 \*****************************************************************************/
1515 template<HashTableTemplateList>
1516 typename CHashTableType::CIterator CHashTableType::Begin( void ) const
1517 {
1518     CIterator iterator;
1519 
1520     const DWORD size = m_HashArray.GetSize();
1521     for( DWORD i = 0; i < size; ++i )
1522     {
1523         CHashTableKeyList* pHashKeyList = m_HashArray.GetElement(i);
1524         if( pHashKeyList )
1525         {
1526             iterator.m_Iterator = pHashKeyList->Begin();
1527             iterator.m_Array = const_cast<CHashTableArray*>(&m_HashArray);
1528             iterator.m_ArrayIndex = i;
1529             return iterator;
1530         }
1531     }
1532 
1533     return iterator;
1534 }
1535 
1536 /*****************************************************************************\
1537 
1538 Function:
1539     CHashTable::End
1540 
1541 Description:
1542     Returns an iterator to the last (dummy) node in the hash table
1543 
1544 Input:
1545     none
1546 
1547 Output:
1548     CHashTable::CIterator
1549 
1550 \*****************************************************************************/
1551 template<HashTableTemplateList>
1552 typename CHashTableType::CIterator CHashTableType::End( void ) const
1553 {
1554     CIterator iterator;
1555 
1556     const DWORD size = m_HashArray.GetSize();
1557     for( int i = (int)size-1; i >= 0; --i )
1558     {
1559         CHashTableKeyList* pHashKeyList = m_HashArray.GetElement((DWORD)i);
1560         if( pHashKeyList )
1561         {
1562             iterator.m_Iterator = pHashKeyList->End();
1563             iterator.m_Array = const_cast<CHashTableArray*>(&m_HashArray);
1564             iterator.m_ArrayIndex = (DWORD)i;
1565             return iterator;
1566         }
1567     }
1568 
1569     return iterator;
1570 }
1571 
1572 /*****************************************************************************\
1573 
1574 Function:
1575     CHashTable::Add
1576 
1577 Description:
1578     Adds the element to the hash table and returns its iterator
1579 
1580 Input:
1581     const CHashKey &hashKey
1582     const ElementType &element
1583 
1584 Output:
1585     CIterator &iterator
1586     bool - true if element was added
1587 
1588 \*****************************************************************************/
1589 template<HashTableTemplateList>
1590 bool CHashTableType::Add(
1591     const CHashKey &hashKey,
1592     const ElementType &element,
1593     CIterator &iterator )
1594 {
1595     if( m_HashArray.GetSize() == 0 )
1596     {
1597         return false;
1598     }
1599     const DWORD index = GetHashIndex( hashKey );
1600     ASSERT( index < m_HashArray.GetSize() );
1601 
1602     CHashTableKeyList* pHashKeyList = m_HashArray.GetElement( index );
1603 
1604     // Use the hash code to find a linked list containing all keys with the
1605     // same hash code
1606     if( !pHashKeyList )
1607     {
1608         // if the list doesn't exist then create a new one
1609         pHashKeyList = CreateHashKeyList();
1610 
1611         if( pHashKeyList )
1612         {
1613             // Add the new hash key list to hash array
1614             if( !m_HashArray.SetElement( index, pHashKeyList ) )
1615             {
1616                 ASSERT(0);
1617                 SafeDelete( pHashKeyList );
1618                 return false;
1619             }
1620         }
1621         else
1622         {
1623             ASSERT(0);
1624             return false;
1625         }
1626     }
1627 
1628     // Create the node to add to the list
1629     CHashNode* pHashNode = CreateHashNode( hashKey, element );
1630 
1631     if( pHashNode )
1632     {
1633         // Add the node to the hash key list
1634         if( pHashKeyList->Add( pHashNode ) )
1635         {
1636             ++m_Count;
1637 
1638 #ifdef _DEBUG
1639             ++m_AddCount;
1640 
1641             if( pHashKeyList->GetCount() > 1 )
1642             {
1643                 ++m_CollisionCount;
1644             }
1645 #endif
1646             iterator.m_Array = &m_HashArray;
1647             iterator.m_ArrayIndex = index;
1648             iterator.m_Iterator = pHashKeyList->Begin();
1649             return true;
1650         }
1651         else
1652         {
1653             DeleteHashNode( pHashNode );
1654 
1655             ASSERT(0);
1656             return false;
1657         }
1658     }
1659     else
1660     {
1661         ASSERT(0);
1662         return false;
1663     }
1664 }
1665 
1666 /*****************************************************************************\
1667 
1668 Function:
1669     CHashTable::Get
1670 
1671 Description:
1672     Gets the iterator of the element from the hash table
1673 
1674 Input:
1675     const CHashKey &hashKey
1676 
1677 Output:
1678     CIterator &iterator
1679     bool - true if element was removed
1680 
1681 \*****************************************************************************/
1682 template<HashTableTemplateList>
1683 bool CHashTableType::Get(
1684     const CHashKey &hashKey,
1685     CIterator &iterator ) const
1686 {
1687     if( m_HashArray.GetSize() != 0 )
1688     {
1689         const DWORD index = GetHashIndex( hashKey );
1690         ASSERT( index < m_HashArray.GetSize() );
1691 
1692         CHashTableKeyList* pHashKeyList = m_HashArray.GetElement( index );
1693 
1694         if( pHashKeyList )
1695         {
1696             // Search the list for the node with the same key
1697             typename CHashTableKeyList::CIterator list_iterator = pHashKeyList->Begin();
1698 
1699             while( list_iterator != pHashKeyList->End() )
1700             {
1701                 CHashNode* pHashNode = (*list_iterator);
1702 
1703                 if( pHashNode->GetHashKey() == hashKey )
1704                 {
1705                     iterator.m_Array = const_cast<CHashTableArray*>(&m_HashArray);
1706                     iterator.m_ArrayIndex = index;
1707                     iterator.m_Iterator = list_iterator;
1708                     return true;
1709                 }
1710 
1711                 ++list_iterator;
1712             }
1713         }
1714     }
1715     return false;
1716 }
1717 
1718 /*****************************************************************************\
1719 
1720 Function:
1721     CHashTable::Remove
1722 
1723 Description:
1724     Removes element from the hash table via iterator
1725 
1726 Input:
1727     CIterator iterator
1728 
1729 Output:
1730     bool - true if element was removed
1731 
1732 \*****************************************************************************/
1733 template<HashTableTemplateList>
1734 bool CHashTableType::Remove( CIterator iterator )
1735 {
1736     CHashTableKeyList* pHashKeyList = m_HashArray.
1737         GetElement( iterator.m_ArrayIndex );
1738 
1739     if( pHashKeyList )
1740     {
1741         CHashNode* pHashNode = *(iterator.m_Iterator);
1742 
1743         pHashKeyList->Remove( iterator.m_Iterator );
1744 
1745         DeleteHashNode( pHashNode );
1746 
1747         if( pHashKeyList->IsEmpty() )
1748         {
1749             m_HashArray.SetElement( iterator.m_ArrayIndex, NULL );
1750             DeleteHashKeyList( pHashKeyList );
1751         }
1752 
1753         ASSERT( m_Count > 0 );
1754         --m_Count;
1755 
1756 #ifdef _DEBUG
1757         ++m_RemoveCount;
1758 #endif
1759         return true;
1760     }
1761 
1762     return false;
1763 }
1764 
1765 } // iSTD
1766