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 "utility.h" 13 #include "MemCopy.h" 14 #include "Threading.h" 15 16 namespace iSTD 17 { 18 19 /*****************************************************************************\ 20 Template Parameters 21 \*****************************************************************************/ 22 #define BitSetTemplateList class CAllocatorType 23 #define CBitSetType CBitSet<CAllocatorType> 24 25 /*****************************************************************************\ 26 Struct: 27 TPtrSize 28 Description: 29 Defines type that is size of a pointer. It also provides a set of static 30 functions for managing on bits, depending on pointer size. 31 32 \*****************************************************************************/ 33 template <int T> struct TPtrSize 34 { 35 }; 36 // Specialization for 32bit pointers: 37 template <> struct TPtrSize<4> 38 { 39 typedef unsigned int type; 40 41 static inline type Bit( const DWORD index ) 42 { 43 return BIT( index ); 44 } 45 46 static inline DWORD Bsf( const type mask ) 47 { 48 return iSTD::bsf( mask ); 49 } 50 51 static inline DWORD Bsr( const type mask ) 52 { 53 return iSTD::bsr( mask ); 54 } 55 56 static inline DWORD Count( const type mask ) 57 { 58 return iSTD::BitCount( mask ); 59 } 60 }; 61 // Specialization for 64bit pointers: 62 template <> struct TPtrSize<8> 63 { 64 typedef unsigned long long type; 65 66 static inline type Bit( const DWORD index ) 67 { 68 return QWBIT( index ); 69 } 70 71 static inline DWORD Bsf( const type mask ) 72 { 73 #if defined( _WIN64 ) || defined( __x86_64__ ) 74 return iSTD::bsf64( mask ); 75 #else 76 // Should never compile this code - added to get rid of compilation 77 // warnings on GCC. 78 ASSERT( 0 ); 79 return 0; 80 #endif 81 } 82 83 static inline DWORD Bsr( const type mask ) 84 { 85 #if defined( _WIN64 ) || defined( __x86_64__ ) 86 return iSTD::bsr64( mask ); 87 #else 88 // Should never compile this code - added to get rid of compilation 89 // warnings on GCC. 90 ASSERT( 0 ); 91 return 0; 92 #endif 93 } 94 95 static inline DWORD Count( const type mask ) 96 { 97 return iSTD::BitCount64( mask ); 98 } 99 }; 100 101 /*****************************************************************************\ 102 103 Class: 104 CBitSet 105 106 Description: 107 Implements a dynamic bit set. For sets smaller than size of pointer, bits 108 are stored in a pointer to the array, to prevent dynamic allocations. 109 110 \*****************************************************************************/ 111 template<BitSetTemplateList> 112 class CBitSet : public CObject<CAllocatorType> 113 { 114 private: 115 static const DWORD BITS_PER_BYTE = 8; 116 typedef DWORD BITSET_ARRAY_TYPE; 117 static const DWORD cBitsPerArrayElement = 118 sizeof( BITSET_ARRAY_TYPE ) * BITS_PER_BYTE; 119 120 static const DWORD cBitsInPtr = sizeof(BITSET_ARRAY_TYPE*) * 8; 121 122 typedef TPtrSize<sizeof(void*)> CPtrSize; 123 typedef CPtrSize::type bitptr_t; 124 125 public: 126 127 CBitSet( void ); 128 CBitSet( DWORD size ); 129 CBitSet( const CBitSetType& other ); 130 131 virtual ~CBitSet( void ); 132 133 void Resize( DWORD size ); 134 135 void Clear( void ); 136 void SetAll( void ); 137 void Invert( void ); 138 139 bool IsEmpty() const; 140 bool IsEmpty( DWORD start, DWORD length ) const; 141 142 bool IsSet( DWORD index ) const; 143 bool Intersects( const CBitSetType& other ) const; 144 145 DWORD GetNextMember( DWORD start ) const; 146 147 void Set( DWORD index ); 148 void Set( const CBitSetType& other ); 149 void UnSet( DWORD index ); 150 void UnSet( const CBitSetType& other ); 151 152 DWORD GetSize( void ) const; 153 DWORD BitCount( void ) const; 154 DWORD BitCount( DWORD limit ) const; 155 long Min( void ) const; 156 long Max( void ) const; 157 158 template<class T> 159 T ConvertTo() const; 160 161 bool operator==( const CBitSetType& other ) const; 162 bool operator!=( const CBitSetType& other ) const; 163 164 CBitSetType& operator= ( const CBitSetType& other ); 165 CBitSetType& operator|= ( const CBitSetType& other ); 166 CBitSetType& operator&= ( const CBitSetType& other ); 167 168 protected: 169 170 // Depending on a set size, bits can be stored in dynamically allocated 171 // memory, or in a pointer. 172 union 173 { 174 BITSET_ARRAY_TYPE* m_BitSetArray; 175 bitptr_t m_PtrBits; 176 }; 177 DWORD m_Size; 178 179 void Create( DWORD size ); 180 void Copy( const CBitSetType& other ); 181 void Delete( void ); 182 183 bool StoredInPtr( void ) const; 184 bitptr_t GetActivePtrMask( void ) const; 185 186 BITSET_ARRAY_TYPE* GetArrayPointer( void ); 187 const BITSET_ARRAY_TYPE* GetArrayPointer( void ) const; 188 189 DECL_DEBUG_MUTEX( m_InstanceNotThreadSafe ) 190 }; 191 192 /*****************************************************************************\ 193 194 Function: 195 CBitSet Constructor 196 197 Description: 198 Initializes the BitSet 199 200 Input: 201 none 202 203 Output: 204 none 205 206 \*****************************************************************************/ 207 template<BitSetTemplateList> 208 CBitSetType::CBitSet( void ) 209 : CObject<CAllocatorType>() 210 { 211 m_BitSetArray = NULL; 212 m_Size = 0; 213 214 INIT_DEBUG_MUTEX( m_InstanceNotThreadSafe ); 215 } 216 217 /*****************************************************************************\ 218 219 Function: 220 CBitSet Constructor 221 222 Description: 223 Initializes the BitSet 224 225 Input: 226 DWORD size - initial size of the BitSet 227 228 Output: 229 none 230 231 \*****************************************************************************/ 232 template<BitSetTemplateList> 233 CBitSetType::CBitSet( DWORD size ) 234 : CObject<CAllocatorType>() 235 { 236 m_BitSetArray = NULL; 237 m_Size = 0; 238 239 INIT_DEBUG_MUTEX( m_InstanceNotThreadSafe ); 240 241 Create( size ); 242 } 243 244 /*****************************************************************************\ 245 246 Function: 247 CBitSet Copy Constructor 248 249 Description: 250 Initializes the BitSet 251 252 Input: 253 const CBitSetType& other - other bitset to copy 254 255 Output: 256 none 257 258 \*****************************************************************************/ 259 template<BitSetTemplateList> 260 CBitSetType::CBitSet( const CBitSetType& other ) 261 : CObject<CAllocatorType>() 262 { 263 m_BitSetArray = NULL; 264 m_Size = 0; 265 266 INIT_DEBUG_MUTEX( m_InstanceNotThreadSafe ); 267 268 Copy( other ); 269 } 270 271 /*****************************************************************************\ 272 273 Function: 274 CBitSet Destructor 275 276 Description: 277 Frees all internal dynamic memory 278 279 Input: 280 none 281 282 Output: 283 none 284 285 \*****************************************************************************/ 286 template<BitSetTemplateList> 287 CBitSetType::~CBitSet( void ) 288 { 289 Delete(); 290 291 DELETE_DEBUG_MUTEX( m_InstanceNotThreadSafe ); 292 } 293 294 /*****************************************************************************\ 295 296 Function: 297 CBitSet::Resize 298 299 Description: 300 Resizes the bitset 301 302 Input: 303 DWORD size - new size of the BitSet 304 305 Output: 306 none 307 308 \*****************************************************************************/ 309 template<BitSetTemplateList> 310 void CBitSetType::Resize( DWORD size ) 311 { 312 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 313 314 Create( size ); 315 316 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 317 } 318 319 /*****************************************************************************\ 320 321 Function: 322 CBitSet::Clear 323 324 Description: 325 Unsets all bits in the bitset 326 327 Input: 328 none 329 330 Output: 331 none 332 333 \*****************************************************************************/ 334 template<BitSetTemplateList> 335 void CBitSetType::Clear( void ) 336 { 337 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 338 339 if( StoredInPtr() ) 340 { 341 m_PtrBits = static_cast<bitptr_t>( 0 ); 342 } 343 else 344 { 345 const DWORD cArraySizeInBytes = 346 ( m_Size + BITS_PER_BYTE - 1 ) / BITS_PER_BYTE; 347 348 SafeMemSet( m_BitSetArray, 0, cArraySizeInBytes ); 349 } 350 351 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 352 } 353 354 /*****************************************************************************\ 355 356 Function: 357 CBitSet::SetAll 358 359 Description: 360 Sets all the bits in this bitset, from bit zero to bit "size". Note that 361 any "extra" bits (bits that are part of the array but that are less than 362 "size" are not set and remain unset. 363 364 Input: 365 void 366 367 Output: 368 void 369 370 \*****************************************************************************/ 371 template<BitSetTemplateList> 372 void CBitSetType::SetAll( void ) 373 { 374 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 375 376 if( StoredInPtr() ) 377 { 378 m_PtrBits = GetActivePtrMask(); 379 } 380 else 381 { 382 ASSERT( m_BitSetArray ); 383 384 const DWORD cArraySize = 385 ( m_Size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 386 387 const BITSET_ARRAY_TYPE cExtraBits = 388 m_Size % cBitsPerArrayElement; 389 const BITSET_ARRAY_TYPE cExtraBitMask = 390 cExtraBits ? ( ( 1 << cExtraBits ) - 1 ) : ( ~0 ); 391 392 DWORD index; 393 394 for( index = 0; index < cArraySize - 1; index++ ) 395 { 396 m_BitSetArray[index] = ~((BITSET_ARRAY_TYPE)0); 397 } 398 if( index < cArraySize ) 399 { 400 m_BitSetArray[index] = ~((BITSET_ARRAY_TYPE)0) & cExtraBitMask; 401 } 402 } 403 404 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 405 } 406 407 /*****************************************************************************\ 408 409 Function: 410 CBitSet::Invert 411 412 Description: 413 Computes the inverse of this bitset. Note that any "extra" bits (bits 414 that are part of the array but that are less than "size" are not inverted 415 and remain un-set. 416 417 Input: 418 void 419 420 Output: 421 void 422 423 \*****************************************************************************/ 424 template<BitSetTemplateList> 425 void CBitSetType::Invert( void ) 426 { 427 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 428 429 if( StoredInPtr() ) 430 { 431 m_PtrBits = (~m_PtrBits) & GetActivePtrMask(); 432 } 433 else 434 { 435 ASSERT( m_BitSetArray ); 436 437 const DWORD cArraySize = 438 ( m_Size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 439 440 const BITSET_ARRAY_TYPE cExtraBits = 441 m_Size % cBitsPerArrayElement; 442 const BITSET_ARRAY_TYPE cExtraBitMask = 443 cExtraBits ? ( ( 1 << cExtraBits ) - 1 ) : ( ~0 ); 444 445 DWORD index; 446 447 for( index = 0; index < cArraySize - 1; index++ ) 448 { 449 m_BitSetArray[index] = ~m_BitSetArray[index]; 450 } 451 if( index < cArraySize ) 452 { 453 m_BitSetArray[index] = ~m_BitSetArray[index] & cExtraBitMask; 454 } 455 } 456 457 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 458 } 459 460 /*****************************************************************************\ 461 462 Function: 463 CBitSet::IsEmpty 464 465 Description: 466 Determines if any bits are on in the bit set. 467 468 Input: 469 none 470 471 Output: 472 bool 473 474 \*****************************************************************************/ 475 template<BitSetTemplateList> 476 bool CBitSetType::IsEmpty( void ) const 477 { 478 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 479 480 bool isEmpty = true; 481 482 if( StoredInPtr() ) 483 { 484 isEmpty = ( m_PtrBits == static_cast<bitptr_t>( 0 ) ); 485 } 486 else 487 { 488 DWORD index = ( m_Size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 489 490 while( isEmpty && index-- ) 491 { 492 isEmpty = (m_BitSetArray[ index ] == 0 ); 493 } 494 } 495 496 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 497 return isEmpty; 498 } 499 500 /*****************************************************************************\ 501 502 Function: 503 CBitSet::IsEmpty 504 505 Description: 506 Determines if any bits are set in the bit set in the specified range. 507 508 Input: 509 DWORD start - Start of the range to check, inclusive. 510 DWORD length - Length of the range to check. 511 512 Output: 513 bool 514 515 \*****************************************************************************/ 516 template<BitSetTemplateList> 517 bool CBitSetType::IsEmpty( DWORD start, DWORD length ) const 518 { 519 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 520 521 bool isEmpty = true; 522 523 ASSERT( start < m_Size ); 524 ASSERT( length != 0 ); 525 ASSERT( start + length <= m_Size ); 526 527 if( StoredInPtr() ) 528 { 529 const DWORD end = start + length; 530 531 // Create a bit mask for this range: 532 bitptr_t mask = ~( CPtrSize::Bit( start ) - 1 ); 533 if( end < cBitsInPtr ) 534 { 535 mask &= CPtrSize::Bit( end ) - 1; 536 } 537 538 isEmpty = ( ( mask & m_PtrBits ) == static_cast<bitptr_t>( 0 ) ); 539 } 540 else 541 { 542 const DWORD end = start + length; 543 544 const DWORD startArrayIndex = start / cBitsPerArrayElement; 545 const DWORD endArrayIndex = ( end - 1 ) / cBitsPerArrayElement; 546 547 const DWORD startBit = start % cBitsPerArrayElement; 548 const DWORD endBit = end % cBitsPerArrayElement; 549 550 const BITSET_ARRAY_TYPE startMask = ~( ( 1 << startBit ) - 1 ); 551 const BITSET_ARRAY_TYPE endMask = endBit ? ( ( 1 << endBit ) - 1 ) : ~0; 552 553 DWORD arrayIndex = startArrayIndex; 554 555 BITSET_ARRAY_TYPE data = m_BitSetArray[ arrayIndex ]; 556 557 data &= startMask; 558 559 if( startArrayIndex == endArrayIndex ) 560 { 561 data &= endMask; 562 563 isEmpty = ( data == 0 ); 564 } 565 else 566 { 567 isEmpty = ( data == 0 ); 568 569 if( isEmpty ) 570 { 571 for( arrayIndex = arrayIndex + 1; 572 arrayIndex < endArrayIndex && isEmpty; 573 arrayIndex++ ) 574 { 575 data = m_BitSetArray[ arrayIndex ]; 576 577 isEmpty = ( data == 0 ); 578 } 579 } 580 581 if( isEmpty ) 582 { 583 data = m_BitSetArray[ endArrayIndex ]; 584 data &= endMask; 585 586 isEmpty = ( data == 0 ); 587 } 588 } 589 } 590 591 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 592 return isEmpty; 593 } 594 595 /*****************************************************************************\ 596 597 Function: 598 CBitSet::IsSet 599 600 Description: 601 Returns true if the bit at the specified index is set, false otherwise. 602 603 Input: 604 DWORD index - index of the bit to check 605 606 Output: 607 bool 608 609 \*****************************************************************************/ 610 template<BitSetTemplateList> 611 bool CBitSetType::IsSet( DWORD index ) const 612 { 613 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 614 615 bool isSet = false; 616 617 if( index < m_Size ) 618 { 619 if( StoredInPtr() ) 620 { 621 isSet = ( ( m_PtrBits & CPtrSize::Bit( index ) ) != static_cast<bitptr_t>( 0 ) ); 622 } 623 else 624 { 625 DWORD arrayIndex = index / cBitsPerArrayElement; 626 DWORD bitIndex = index % cBitsPerArrayElement; 627 628 isSet = ( ( m_BitSetArray[arrayIndex] & BIT(bitIndex) ) != 0 ); 629 } 630 } 631 632 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 633 return isSet; 634 } 635 636 /*****************************************************************************\ 637 638 Function: 639 CBitSet::Intersects 640 641 Description: 642 Returns true if any bits are on in both this bit set and the passed-in 643 bit set. This is a shortcut for ( BitSet1 & BitSet2 ).IsEmpty(). 644 645 Input: 646 CBitSetType other - Other bit set 647 648 Output: 649 bool 650 651 \*****************************************************************************/ 652 template<BitSetTemplateList> 653 bool CBitSetType::Intersects( const CBitSetType& other ) const 654 { 655 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 656 657 bool intersects = false; 658 659 if( StoredInPtr() && other.StoredInPtr() ) 660 { 661 intersects = ( ( m_PtrBits & other.m_PtrBits ) != static_cast<bitptr_t>( 0 ) ); 662 } 663 else 664 { 665 // Size of bitptr_t must be multiplicity of size of BITSET_ARRAY_TYPE. 666 C_ASSERT( sizeof( bitptr_t ) % sizeof( BITSET_ARRAY_TYPE ) == 0 ); 667 668 // If stored in pointer, get pointer to this pointer and use 669 // common implementation: 670 const BITSET_ARRAY_TYPE* ptrThis = GetArrayPointer(); 671 const BITSET_ARRAY_TYPE* ptrOther = other.GetArrayPointer(); 672 673 DWORD minSize = ( m_Size < other.m_Size ) ? m_Size : other.m_Size; 674 675 DWORD index = ( minSize + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 676 677 while( !intersects && index-- ) 678 { 679 if( ( ptrThis[ index ] & ptrOther[ index ] ) != 0 ) 680 { 681 intersects = true; 682 } 683 } 684 } 685 686 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 687 return intersects; 688 } 689 690 /*****************************************************************************\ 691 692 Function: 693 CBitSet::GetNextMember 694 695 Description: 696 Gets the next member in the set, starting from the specified index. 697 If there are no additional members in the set, returns the size of 698 the set. 699 700 Example usage pattern: 701 702 for( 703 DWORD value = bitSet.GetNextMember( 0 ); 704 value < bitSet.GetSize(); 705 value = bitSet.GetNextMember( ++value ) ) 706 707 Input: 708 DWORD start - Index to start the search 709 710 Output: 711 DWORD - The next member of the set, or the size of the set if there are 712 no more members in the set. 713 714 \*****************************************************************************/ 715 template<BitSetTemplateList> 716 DWORD CBitSetType::GetNextMember( DWORD start ) const 717 { 718 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 719 720 DWORD nextMember = m_Size; 721 722 if( start < m_Size ) 723 { 724 if( StoredInPtr() ) 725 { 726 bitptr_t ptrBits = m_PtrBits; 727 728 // Mask out bits to start: 729 ptrBits &= ~( CPtrSize::Bit( start ) - 1 ); 730 731 // Find first bit: 732 if( ptrBits != static_cast<bitptr_t>( 0 ) ) 733 { 734 nextMember = CPtrSize::Bsf( ptrBits ); 735 } 736 } 737 else 738 { 739 const DWORD startArrayIndex = start / cBitsPerArrayElement; 740 const DWORD endArrayIndex = ( m_Size - 1 ) / cBitsPerArrayElement; 741 742 const DWORD startBit = start % cBitsPerArrayElement; 743 const DWORD endBit = m_Size % cBitsPerArrayElement; 744 745 const BITSET_ARRAY_TYPE startMask = ~( ( 1 << startBit ) - 1 ); 746 const BITSET_ARRAY_TYPE endMask = endBit ? ( ( 1 << endBit ) - 1 ) : ~0; 747 748 DWORD arrayIndex = startArrayIndex; 749 750 BITSET_ARRAY_TYPE data = m_BitSetArray[ arrayIndex ]; 751 752 data &= startMask; 753 754 if( arrayIndex == endArrayIndex ) 755 { 756 data &= endMask; 757 } 758 else 759 { 760 if( data == 0 ) 761 { 762 for( arrayIndex = arrayIndex + 1; 763 arrayIndex < endArrayIndex; 764 arrayIndex++ ) 765 { 766 data = m_BitSetArray[ arrayIndex ]; 767 768 if( data != 0 ) 769 { 770 break; 771 } 772 } 773 774 if( data == 0 ) 775 { 776 data = m_BitSetArray[ endArrayIndex ]; 777 data &= endMask; 778 } 779 } 780 } 781 782 if( data != 0 ) 783 { 784 // Found, find the first bit that's on in "data". 785 const DWORD lsb = bsf( data ); 786 nextMember = ( arrayIndex * cBitsPerArrayElement ) + lsb; 787 } 788 } 789 } 790 791 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 792 return nextMember; 793 } 794 795 /*****************************************************************************\ 796 797 Function: 798 CBitSet::Set 799 800 Description: 801 Sets the bit at the given index. 802 803 Input: 804 DWORD index - index of the bit to set 805 806 Output: 807 void 808 809 \*****************************************************************************/ 810 template<BitSetTemplateList> 811 void CBitSetType::Set( DWORD index ) 812 { 813 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 814 815 // If the index is larger than the size of the BitSet then grow the BitSet 816 if( index >= m_Size ) 817 { 818 Create( index + 1 ); 819 } 820 821 ASSERT( index < m_Size ); 822 823 if( StoredInPtr() ) 824 { 825 m_PtrBits |= CPtrSize::Bit( index ); 826 } 827 else 828 { 829 DWORD arrayIndex = index / cBitsPerArrayElement; 830 DWORD bitIndex = index % cBitsPerArrayElement; 831 832 m_BitSetArray[arrayIndex] |= BIT(bitIndex); 833 } 834 835 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 836 } 837 838 /*****************************************************************************\ 839 840 Function: 841 CBitSet::Set 842 843 Description: 844 Sets all of the given bits. 845 846 Input: 847 CBitSetType other - bits to set. 848 849 Output: 850 void 851 852 \*****************************************************************************/ 853 template<BitSetTemplateList> 854 void CBitSetType::Set( const CBitSetType& other ) 855 { 856 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 857 858 DWORD size = other.m_Size; 859 860 if( m_Size < other.m_Size ) 861 { 862 Create( other.m_Size ); 863 size = m_Size; 864 } 865 866 ASSERT( m_Size >= other.m_Size ); 867 868 if( StoredInPtr() ) 869 { 870 ASSERT( other.StoredInPtr() ); 871 m_PtrBits |= other.m_PtrBits; 872 } 873 else 874 { 875 const BITSET_ARRAY_TYPE* pOtherArray = other.GetArrayPointer(); 876 DWORD index = ( size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 877 while( index-- ) 878 { 879 m_BitSetArray[ index ] |= pOtherArray[ index ]; 880 } 881 } 882 883 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 884 } 885 886 /*****************************************************************************\ 887 888 Function: 889 CBitSet::UnSet 890 891 Description: 892 Un-Sets the bit at the given index. 893 894 Input: 895 DWORD index - index of the bit to un-set 896 897 Output: 898 void 899 900 \*****************************************************************************/ 901 template<BitSetTemplateList> 902 void CBitSetType::UnSet( DWORD index ) 903 { 904 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 905 906 // If the index is larger than the size of the BitSet then grow the BitSet 907 if( index >= m_Size ) 908 { 909 Create( index + 1 ); 910 if( index >= m_Size ) 911 { 912 // In case allocation failed... 913 ASSERT( index < m_Size ); 914 return; 915 } 916 } 917 918 if( StoredInPtr() ) 919 { 920 m_PtrBits &= ( ~CPtrSize::Bit( index ) ) & GetActivePtrMask(); 921 } 922 else 923 { 924 DWORD arrayIndex = index / cBitsPerArrayElement; 925 DWORD bitIndex = index % cBitsPerArrayElement; 926 927 m_BitSetArray[arrayIndex] &= ~BIT(bitIndex); 928 } 929 930 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 931 } 932 933 /*****************************************************************************\ 934 935 Function: 936 CBitSet::UnSet 937 938 Description: 939 Un-Sets all of the given bits. 940 941 Input: 942 CBitSetType other - bits to un-set. 943 944 Output: 945 void 946 947 \*****************************************************************************/ 948 template<BitSetTemplateList> 949 void CBitSetType::UnSet( const CBitSetType& other ) 950 { 951 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 952 953 DWORD size = other.m_Size; 954 955 if( m_Size < other.m_Size ) 956 { 957 Create( other.m_Size ); 958 size = m_Size; 959 } 960 961 ASSERT( m_Size >= other.m_Size ); 962 963 if( StoredInPtr() ) 964 { 965 ASSERT( other.StoredInPtr() ); 966 m_PtrBits &= ~other.m_PtrBits; 967 m_PtrBits &= GetActivePtrMask(); 968 } 969 else 970 { 971 const BITSET_ARRAY_TYPE* pOtherArray = other.GetArrayPointer(); 972 DWORD index = ( size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 973 while( index-- ) 974 { 975 m_BitSetArray[ index ] &= ~pOtherArray[ index ]; 976 } 977 } 978 979 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 980 } 981 982 /*****************************************************************************\ 983 984 Function: 985 CBitSet::GetSize 986 987 Description: 988 Returns the number of bits in the BitSet 989 990 Input: 991 void 992 993 Output: 994 DWORD length 995 996 \*****************************************************************************/ 997 template<BitSetTemplateList> 998 DWORD CBitSetType::GetSize( void ) const 999 { 1000 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1001 1002 const DWORD size = m_Size; 1003 1004 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1005 return size; 1006 } 1007 1008 /*****************************************************************************\ 1009 1010 Function: 1011 CBitSet::Min 1012 1013 Description: 1014 Returns the minimum bit set 1015 1016 Input: 1017 void 1018 1019 Output: 1020 long 1021 1022 \*****************************************************************************/ 1023 template<BitSetTemplateList> 1024 long CBitSetType::Min( void ) const 1025 { 1026 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1027 1028 long minBit = -1; 1029 1030 if( StoredInPtr() ) 1031 { 1032 if( m_PtrBits ) 1033 { 1034 minBit = CPtrSize::Bsf( m_PtrBits ); 1035 } 1036 } 1037 else 1038 { 1039 const DWORD count = ( m_Size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 1040 1041 for( DWORD i = 0; i < count; ++i ) 1042 { 1043 if( m_BitSetArray[i] != 0 ) 1044 { 1045 const DWORD lsb = bsf( m_BitSetArray[i] ); 1046 minBit = (i * cBitsPerArrayElement) + lsb; 1047 break; 1048 } 1049 } 1050 } 1051 1052 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1053 return minBit; 1054 } 1055 1056 /*****************************************************************************\ 1057 1058 Function: 1059 CBitSet::Max 1060 1061 Description: 1062 Returns the maximum bit set 1063 1064 Input: 1065 void 1066 1067 Output: 1068 long 1069 1070 \*****************************************************************************/ 1071 template<BitSetTemplateList> 1072 long CBitSetType::Max( void ) const 1073 { 1074 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1075 1076 long maxBit = -1; 1077 1078 if( StoredInPtr() ) 1079 { 1080 if( m_PtrBits ) 1081 { 1082 maxBit = CPtrSize::Bsr( m_PtrBits ); 1083 } 1084 } 1085 else 1086 { 1087 const DWORD count = ( m_Size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 1088 1089 for( long i = count-1; i >= 0; --i ) 1090 { 1091 if( m_BitSetArray[i] != 0 ) 1092 { 1093 const DWORD msb = bsr( m_BitSetArray[i] ); 1094 maxBit = (i * cBitsPerArrayElement) + msb; 1095 break; 1096 } 1097 } 1098 } 1099 1100 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1101 return maxBit; 1102 } 1103 1104 /*****************************************************************************\ 1105 1106 Function: 1107 template<class T> 1108 CBitSet::ConvertTo 1109 1110 Description: 1111 Returns a T representation of the current bit set. Only valid if the 1112 bit set consists of less than (or equal to) sizeof(T) * BITS_PER_BYTE bits. 1113 1114 It is expected that the types that bitsets get converted to will be BYTES, 1115 WORDS, or DWORDS, although other types may work as well. 1116 1117 Input: 1118 void 1119 1120 Output: 1121 T representation of the bitfield. 1122 1123 \*****************************************************************************/ 1124 template<BitSetTemplateList> template<class T> 1125 T CBitSetType::ConvertTo() const 1126 { 1127 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1128 1129 T mask = 0; 1130 1131 if( StoredInPtr() ) 1132 { 1133 bitptr_t bits = m_PtrBits; 1134 mask = (T)( bits ); 1135 } 1136 else 1137 { 1138 ASSERT( m_BitSetArray ); 1139 mask = ((T*)m_BitSetArray)[0]; 1140 } 1141 1142 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1143 return mask; 1144 } 1145 1146 /*****************************************************************************\ 1147 1148 Function: 1149 CBitSet::operator == 1150 1151 Description: 1152 Tests this bitset and another bitset for equality. 1153 1154 Input: 1155 CBitSetType& other - other BitSet 1156 1157 Output: 1158 bool 1159 1160 \*****************************************************************************/ 1161 template<BitSetTemplateList> 1162 bool CBitSetType::operator==( const CBitSetType& other ) const 1163 { 1164 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1165 1166 bool isEqual = false; 1167 1168 if( m_Size == other.m_Size ) 1169 { 1170 ASSERT( this->StoredInPtr() == other.StoredInPtr() ); 1171 1172 if( StoredInPtr() ) 1173 { 1174 isEqual = ( m_PtrBits == other.m_PtrBits ); 1175 } 1176 else 1177 { 1178 const DWORD cArraySizeInBytes = 1179 ( m_Size + BITS_PER_BYTE - 1 ) / BITS_PER_BYTE; 1180 1181 isEqual = ( 0 == 1182 SafeMemCompare( m_BitSetArray, 1183 other.m_BitSetArray, 1184 cArraySizeInBytes ) ); 1185 } 1186 } 1187 1188 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1189 return isEqual; 1190 } 1191 1192 /*****************************************************************************\ 1193 1194 Function: 1195 CBitSet::operator != 1196 1197 Description: 1198 Tests this bitset and another bitset for inequality. 1199 1200 Input: 1201 CBitSetType& other - other BitSet 1202 1203 Output: 1204 bool 1205 1206 \*****************************************************************************/ 1207 template<BitSetTemplateList> 1208 bool CBitSetType::operator!=( const CBitSetType& other ) const 1209 { 1210 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1211 1212 bool isNotEqual = true; 1213 1214 if( m_Size == other.m_Size ) 1215 { 1216 ASSERT( this->StoredInPtr() == other.StoredInPtr() ); 1217 1218 if( StoredInPtr() ) 1219 { 1220 isNotEqual = ( m_PtrBits != other.m_PtrBits ); 1221 } 1222 else 1223 { 1224 const DWORD cArraySizeInBytes = 1225 ( m_Size + BITS_PER_BYTE - 1 ) / BITS_PER_BYTE; 1226 1227 isNotEqual = ( 0 != 1228 SafeMemCompare( m_BitSetArray, 1229 other.m_BitSetArray, 1230 cArraySizeInBytes ) ); 1231 } 1232 } 1233 1234 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1235 return isNotEqual; 1236 } 1237 1238 /*****************************************************************************\ 1239 1240 Function: 1241 CBitSet::operator = 1242 1243 Description: 1244 Equal operator to copy a BitSet 1245 1246 Input: 1247 CBitSetType& other - BitSet to copy 1248 1249 Output: 1250 *this 1251 1252 \*****************************************************************************/ 1253 template<BitSetTemplateList> 1254 CBitSetType& CBitSetType::operator= ( const CBitSetType &other ) 1255 { 1256 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 1257 1258 Copy( other ); 1259 1260 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 1261 return *this; 1262 } 1263 1264 /*****************************************************************************\ 1265 1266 Function: 1267 CBitSet::operator |= 1268 1269 Description: 1270 Computes the union of this bitset with another bitset. 1271 1272 Input: 1273 CBitSetType& other - other BitSet 1274 1275 Output: 1276 *this 1277 1278 \*****************************************************************************/ 1279 template<BitSetTemplateList> 1280 CBitSetType& CBitSetType::operator|= ( const CBitSetType &other ) 1281 { 1282 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 1283 1284 DWORD size = other.m_Size; 1285 1286 if( m_Size < other.m_Size ) 1287 { 1288 Create( other.m_Size ); 1289 size = m_Size; 1290 } 1291 1292 ASSERT( m_Size >= other.m_Size ); 1293 1294 if( StoredInPtr() ) 1295 { 1296 ASSERT( other.StoredInPtr() ); 1297 m_PtrBits |= other.m_PtrBits; 1298 } 1299 else 1300 { 1301 const BITSET_ARRAY_TYPE* pOtherArray = other.GetArrayPointer(); 1302 DWORD index = ( size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 1303 while( index-- ) 1304 { 1305 m_BitSetArray[ index ] |= pOtherArray[ index ]; 1306 } 1307 } 1308 1309 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 1310 return *this; 1311 } 1312 1313 /*****************************************************************************\ 1314 1315 Function: 1316 CBitSet::operator &= 1317 1318 Description: 1319 Computes the intersection of this bitset with another bitset. 1320 1321 Input: 1322 CBitSetType& other - other BitSet 1323 1324 Output: 1325 *this 1326 1327 \*****************************************************************************/ 1328 template<BitSetTemplateList> 1329 CBitSetType& CBitSetType::operator&= ( const CBitSetType &other ) 1330 { 1331 ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 1332 1333 DWORD size = other.m_Size; 1334 1335 if( m_Size < other.m_Size ) 1336 { 1337 Create( other.m_Size ); 1338 size = m_Size; 1339 } 1340 1341 ASSERT( m_Size >= other.m_Size ); 1342 1343 if( StoredInPtr() ) 1344 { 1345 ASSERT( other.StoredInPtr() ); 1346 m_PtrBits &= other.m_PtrBits; 1347 } 1348 else 1349 { 1350 const BITSET_ARRAY_TYPE* pOtherArray = other.GetArrayPointer(); 1351 DWORD index = ( size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 1352 while( index-- ) 1353 { 1354 m_BitSetArray[ index ] &= pOtherArray[ index ]; 1355 } 1356 } 1357 1358 RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe ); 1359 return *this; 1360 } 1361 1362 /*****************************************************************************\ 1363 1364 Function: 1365 CBitSet::Create 1366 1367 Description: 1368 Creates the internal BitSet structure of the specified size 1369 1370 Input: 1371 DWORD size - number of elements 1372 1373 Output: 1374 void 1375 1376 \*****************************************************************************/ 1377 template<BitSetTemplateList> 1378 void CBitSetType::Create( DWORD size ) 1379 { 1380 if( size == m_Size ) 1381 { 1382 // Nothing to do... 1383 } 1384 if( size <= cBitsInPtr ) 1385 { 1386 // Bitset will fit in pointer. 1387 bitptr_t newPtrBits = this->ConvertTo<bitptr_t>(); 1388 1389 Delete(); 1390 1391 m_Size = size; 1392 m_PtrBits = newPtrBits & GetActivePtrMask(); 1393 } 1394 else 1395 { 1396 BITSET_ARRAY_TYPE* ptrThis = GetArrayPointer(); 1397 1398 const DWORD cNewArraySize = 1399 ( size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 1400 const DWORD cOldArraySize = 1401 ( m_Size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 1402 1403 const BITSET_ARRAY_TYPE cExtraBits = 1404 size % cBitsPerArrayElement; 1405 const BITSET_ARRAY_TYPE cExtraBitMask = 1406 cExtraBits ? ( ( 1 << cExtraBits ) - 1 ) : ( ~0 ); 1407 1408 if( cNewArraySize == cOldArraySize ) 1409 { 1410 m_Size = size; 1411 if( cNewArraySize ) 1412 { 1413 ptrThis[ cNewArraySize - 1 ] &= cExtraBitMask; 1414 } 1415 } 1416 else if( cNewArraySize ) 1417 { 1418 BITSET_ARRAY_TYPE* ptr = (BITSET_ARRAY_TYPE*) 1419 CAllocatorType::Allocate( sizeof(BITSET_ARRAY_TYPE) * cNewArraySize ); 1420 1421 if( ptr ) 1422 { 1423 if( ptrThis ) 1424 { 1425 if( cNewArraySize > cOldArraySize ) 1426 { 1427 MemCopy( ptr, 1428 ptrThis, 1429 cOldArraySize * sizeof(ptrThis[0]) ); 1430 SafeMemSet( ptr + cOldArraySize, 1431 0, 1432 ( cNewArraySize - cOldArraySize) * sizeof(ptrThis[0]) ); 1433 } 1434 else 1435 { 1436 MemCopy( ptr, 1437 ptrThis, 1438 cNewArraySize * sizeof(ptrThis[0]) ); 1439 if( cNewArraySize ) 1440 { 1441 ptr[ cNewArraySize - 1 ] &= cExtraBitMask; 1442 } 1443 } 1444 } 1445 else 1446 { 1447 SafeMemSet( ptr, 1448 0, 1449 cNewArraySize * sizeof(ptrThis[0]) ); 1450 } 1451 1452 Delete(); 1453 1454 m_BitSetArray = ptr; 1455 m_Size = size; 1456 } 1457 else 1458 { 1459 ASSERT( 0 ); 1460 } 1461 } 1462 else 1463 { 1464 Delete(); 1465 } 1466 } 1467 } 1468 1469 /*****************************************************************************\ 1470 1471 Function: 1472 CBitSet::Copy 1473 1474 Description: 1475 Copies information from one bitset to this bitset. 1476 1477 Input: 1478 const CBitSetType& other - bitset to copy. 1479 1480 Output: 1481 void 1482 1483 \*****************************************************************************/ 1484 template<BitSetTemplateList> 1485 void CBitSetType::Copy( const CBitSetType& other ) 1486 { 1487 if( this != &other ) 1488 { 1489 if( m_Size != other.m_Size ) 1490 { 1491 Create( other.m_Size ); 1492 } 1493 1494 if( m_Size == other.m_Size ) 1495 { 1496 ASSERT( this->StoredInPtr() == other.StoredInPtr() ); 1497 1498 if( StoredInPtr() ) 1499 { 1500 m_PtrBits = other.m_PtrBits; 1501 } 1502 else 1503 { 1504 const DWORD cArraySizeInBytes = 1505 ( other.m_Size + BITS_PER_BYTE - 1 ) / BITS_PER_BYTE; 1506 1507 MemCopy( m_BitSetArray, 1508 other.m_BitSetArray, 1509 cArraySizeInBytes ); 1510 } 1511 } 1512 else 1513 { 1514 // Should not happen - indicates failed memory allocation. 1515 ASSERT( 0 ); 1516 } 1517 } 1518 } 1519 1520 /*****************************************************************************\ 1521 1522 Function: 1523 CBitSet::Delete 1524 1525 Description: 1526 Deletes the internal BitSet structure 1527 1528 Input: 1529 void 1530 1531 Output: 1532 void 1533 1534 \*****************************************************************************/ 1535 template<BitSetTemplateList> 1536 void CBitSetType::Delete( void ) 1537 { 1538 ASSERT( m_BitSetArray || StoredInPtr() ); 1539 if( !StoredInPtr() && m_BitSetArray ) 1540 { 1541 CAllocatorType::Deallocate( m_BitSetArray ); 1542 } 1543 m_BitSetArray = NULL; 1544 1545 m_Size = 0; 1546 } 1547 1548 /*****************************************************************************\ 1549 1550 Function: 1551 CBitSet::BitCount 1552 1553 Description: 1554 Counts number of bits set in BitSet 1555 1556 Input: 1557 void 1558 1559 Output: 1560 DWORD number of bits set in BitSet 1561 1562 \*****************************************************************************/ 1563 template<BitSetTemplateList> 1564 DWORD CBitSetType::BitCount( void ) const 1565 { 1566 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1567 1568 DWORD bitCount = 0; 1569 1570 if( StoredInPtr() ) 1571 { 1572 bitCount = CPtrSize::Count( m_PtrBits ); 1573 } 1574 else 1575 { 1576 const DWORD cBitsPerArrayElement = 1577 ( sizeof(m_BitSetArray[0]) * 8 ); 1578 1579 DWORD index = ( m_Size + cBitsPerArrayElement - 1 ) / cBitsPerArrayElement; 1580 1581 while( index-- ) 1582 { 1583 BITSET_ARRAY_TYPE Elem = m_BitSetArray[index]; 1584 bitCount += iSTD::BitCount( Elem ); 1585 } 1586 } 1587 1588 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1589 return bitCount; 1590 } 1591 1592 /*****************************************************************************\ 1593 1594 Function: 1595 CBitSet::BitCount 1596 1597 Description: 1598 Counts number of bits set in BitSet up to (and including) limit-th index 1599 1600 Input: 1601 DWORD index 1602 1603 Output: 1604 DWORD number of bits set in BitSet up to (and including) limit-th index 1605 1606 \*****************************************************************************/ 1607 template<BitSetTemplateList> 1608 DWORD CBitSetType::BitCount( DWORD limit ) const 1609 { 1610 ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1611 1612 DWORD bitCount = 0; 1613 1614 limit = iSTD::Min( limit, m_Size-1 ); 1615 1616 for( DWORD i=0; i <= limit; i++ ) 1617 { 1618 if( IsSet( i ) ) 1619 { 1620 bitCount++; 1621 } 1622 } 1623 1624 RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe ); 1625 return bitCount; 1626 } 1627 1628 /*****************************************************************************\ 1629 1630 Function: 1631 CBitSet::StoredInPtr 1632 1633 Description: 1634 True if bits are stored in pointer. 1635 1636 Input: 1637 1638 Output: 1639 bool 1640 1641 \*****************************************************************************/ 1642 template<BitSetTemplateList> 1643 bool CBitSetType::StoredInPtr( void ) const 1644 { 1645 return m_Size <= cBitsInPtr; 1646 } 1647 1648 /*****************************************************************************\ 1649 1650 Function: 1651 CBitSet::GetActivePtrMask 1652 1653 Description: 1654 Returns pointer mask depending on set size. Can only be called if bits are 1655 stored in pointer. 1656 1657 Input: 1658 1659 Output: 1660 bitptr_t - active mask 1661 1662 \*****************************************************************************/ 1663 template<BitSetTemplateList> 1664 typename CBitSetType::bitptr_t CBitSetType::GetActivePtrMask( void ) const 1665 { 1666 ASSERT( StoredInPtr() ); 1667 1668 if( m_Size == cBitsInPtr ) 1669 { 1670 return static_cast<bitptr_t>( -1 ); 1671 } 1672 return CPtrSize::Bit( m_Size ) - 1; 1673 } 1674 1675 /*****************************************************************************\ 1676 1677 Function: 1678 CBitSet::GetArrayPointer 1679 1680 Description: 1681 Return pointer to bitset array. If bits are stored in pointer itself, 1682 return pointer to this pointer. 1683 1684 Input: 1685 1686 Output: 1687 BITSET_ARRAY_TYPE* 1688 1689 \*****************************************************************************/ 1690 template<BitSetTemplateList> 1691 typename CBitSetType::BITSET_ARRAY_TYPE* CBitSetType::GetArrayPointer( void ) 1692 { 1693 if( StoredInPtr() ) 1694 { 1695 return ( reinterpret_cast<BITSET_ARRAY_TYPE*>( &m_PtrBits ) ); 1696 } 1697 else 1698 { 1699 return m_BitSetArray; 1700 } 1701 } 1702 1703 /*****************************************************************************\ 1704 1705 Function: 1706 CBitSet::GetArrayPointer 1707 1708 Description: 1709 Return pointer to bitset array. If bits are stored in pointer itself, 1710 return pointer to this pointer. 1711 1712 Input: 1713 1714 Output: 1715 const BITSET_ARRAY_TYPE* 1716 1717 \*****************************************************************************/ 1718 template<BitSetTemplateList> 1719 const typename CBitSetType::BITSET_ARRAY_TYPE* CBitSetType::GetArrayPointer( void ) const 1720 { 1721 if( StoredInPtr() ) 1722 { 1723 return ( reinterpret_cast<const BITSET_ARRAY_TYPE*>( &m_PtrBits ) ); 1724 } 1725 else 1726 { 1727 return m_BitSetArray; 1728 } 1729 } 1730 1731 } // iSTD 1732