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