csutil/bitarray.h
Go to the documentation of this file.00001 /* 00002 Copyright (C) 2000 by Andrew Kirmse 00003 2008 by Marten Svanfeldt 00004 00005 This library is free software; you can redistribute it and/or 00006 modify it under the terms of the GNU Library General Public 00007 License as published by the Free Software Foundation; either 00008 version 2 of the License, or (at your option) any later version. 00009 00010 This library is distributed in the hope that it will be useful, 00011 but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 Library General Public License for more details. 00014 00015 You should have received a copy of the GNU Library General Public 00016 License along with this library; if not, write to the Free 00017 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00018 */ 00019 00020 // A one-dimensional array of bits, similar to STL bitset. 00021 // 00022 // Copyright 2000 Andrew Kirmse. All rights reserved. 00023 // 00024 // Permission is granted to use this code for any purpose, as long as this 00025 // copyright message remains intact. 00026 00027 #ifndef __CS_BITARRAY_H__ 00028 #define __CS_BITARRAY_H__ 00029 00034 #include "csextern.h" 00035 #include "csutil/allocator.h" 00036 #include "csutil/bitops.h" 00037 #include "csutil/comparator.h" 00038 #include "csutil/hash.h" 00039 00040 #include "csutil/metautils.h" 00041 #include "csutil/compileassert.h" 00042 00043 #if defined(CS_COMPILER_MSVC) && (CS_PROCESSOR_SIZE == 64) 00044 /* long is 32 bit even on 64-bit MSVC, so use uint64 to utilize a storage in 00045 * 64 bit units. 00046 */ 00047 typedef uint64 csBitArrayStorageType; 00048 #else 00050 typedef unsigned long csBitArrayStorageType; 00051 #endif 00052 const size_t csBitArrayDefaultInlineBits = 00053 sizeof (csBitArrayStorageType) * 8; 00054 00055 00057 template<typename BitArray> 00058 class csComparatorBitArray 00059 { 00060 public: 00061 static int Compare (BitArray const& key1, BitArray const& key2) 00062 { 00063 csBitArrayStorageType const* p0 = key1.GetStore(); 00064 csBitArrayStorageType const* p1 = key2.GetStore(); 00065 size_t compareNum = MIN (key1.mLength, key2.mLength); 00066 size_t i = 0; 00067 for (; i < compareNum; i++) 00068 if (p0[i] != p1[i]) 00069 return (int)p0[i] - (int)p1[i]; 00070 if (key1.mLength > key2.mLength) 00071 { 00072 for (; i < key1.mLength; i++) 00073 if (p0[i] != 0) 00074 return (int)p0[i]; 00075 } 00076 else 00077 { 00078 for (; i < key2.mLength; i++) 00079 if (p1[i] != 0) 00080 return -((int)p1[i]); 00081 } 00082 return 0; 00083 } 00084 }; 00085 00086 00088 template<typename BitArray> 00089 class csHashComputerBitArray 00090 { 00091 public: 00092 static uint ComputeHash (BitArray const& key) 00093 { 00094 const size_t uintCount = sizeof (csBitArrayStorageType) / sizeof (uint); 00095 uint ui[uintCount]; 00096 uint hash = 0; 00097 csBitArrayStorageType const* p = key.GetStore(); 00098 // \todo Not very good. Find a better hash function; however, it should 00099 // return the same hash for two bit arrays that are the same except for 00100 // the amount of trailing zeros. (e.g. f(10010110) == f(100101100000...)) 00101 for (size_t i = 0; i < key.mLength; i++) 00102 { 00103 memcpy (ui, &p[i], sizeof (ui)); 00104 for (size_t j = 0; j < uintCount; j++) 00105 hash += ui[j]; 00106 } 00107 return hash; 00108 } 00109 }; 00110 00130 template<int InlinedBits = csBitArrayDefaultInlineBits, 00131 typename Allocator = CS::Memory::AllocatorMalloc> 00132 class csBitArrayTweakable 00133 { 00134 public: 00135 typedef csBitArrayTweakable<InlinedBits, Allocator> ThisType; 00136 typedef Allocator AllocatorType; 00137 00138 protected: 00139 template<typename BitArray> friend class csComparatorBitArray; 00140 template<typename BitArray> friend class csHashComputerBitArray; 00141 00142 enum 00143 { 00144 cellSize = csBitArrayDefaultInlineBits, // This _have_ to be PO2 00145 cellCount = (InlinedBits + (cellSize-1)) / cellSize, 00146 00147 cellMask = (cellSize - 1), 00148 cellShift = CS::Meta::Log2<cellSize>::value 00149 }; 00150 CS_COMPILE_ASSERT(CS::Meta::IsLog2<cellSize>::value); 00151 00152 struct Storage : public Allocator 00153 { 00154 union 00155 { 00156 csBitArrayStorageType* heapStore; 00157 csBitArrayStorageType inlineStore[cellCount]; 00158 }; 00159 Storage() 00160 { 00161 memset (&inlineStore, 0, 00162 MAX(sizeof (heapStore), sizeof (inlineStore))); 00163 } 00164 }; 00165 Storage storage; 00167 size_t mLength; 00168 size_t mNumBits; 00169 00171 static size_t GetIndex (size_t bit_num) 00172 { 00173 return bit_num >> cellShift; 00174 } 00175 00177 static size_t GetOffset (size_t bit_num) 00178 { 00179 return bit_num & cellMask; 00180 } 00181 00183 bool UseInlineStore () const 00184 { 00185 return mLength <= cellCount; 00186 } 00187 00192 csBitArrayStorageType const* GetStore() const 00193 { 00194 return UseInlineStore () ? storage.inlineStore : storage.heapStore; 00195 } 00196 00201 csBitArrayStorageType* GetStore() 00202 { 00203 return UseInlineStore () ? storage.inlineStore : storage.heapStore; 00204 } 00205 00207 void Trim() 00208 { 00209 size_t extra_bits = mNumBits % cellSize; 00210 if (mLength > 0 && extra_bits != 0) 00211 GetStore()[mLength - 1] &= ~((~(csBitArrayStorageType)0) << extra_bits); 00212 } 00213 00214 public: 00218 class BitProxy 00219 { 00220 private: 00221 csBitArrayTweakable& mArray; 00222 size_t mPos; 00223 public: 00225 BitProxy (csBitArrayTweakable& array, size_t pos): mArray(array), mPos(pos) 00226 {} 00227 00229 BitProxy &operator= (bool value) 00230 { 00231 mArray.Set (mPos, value); 00232 return *this; 00233 } 00234 00236 BitProxy &operator= (const BitProxy &that) 00237 { 00238 mArray.Set (mPos, that.mArray.IsBitSet (that.mPos)); 00239 return *this; 00240 } 00241 00243 operator bool() const 00244 { 00245 return mArray.IsBitSet (mPos); 00246 } 00247 00252 bool Flip() 00253 { 00254 mArray.FlipBit (mPos); 00255 return mArray.IsBitSet (mPos); 00256 } 00257 }; 00258 friend class BitProxy; 00259 00263 csBitArrayTweakable () : mLength(0), mNumBits(0) 00264 { 00265 SetSize (0); 00266 } 00267 00271 explicit csBitArrayTweakable (size_t size) : mLength(0), mNumBits(0) 00272 { 00273 SetSize (size); 00274 } 00275 00279 csBitArrayTweakable (const csBitArrayTweakable& that) : mLength(0), mNumBits(0) 00280 { 00281 *this = that; // Invokes this->operator=(). 00282 } 00283 00285 ~csBitArrayTweakable() 00286 { 00287 if (!UseInlineStore ()) 00288 storage.Free (storage.heapStore); 00289 } 00290 00292 size_t GetSize() const 00293 { 00294 return mNumBits; 00295 } 00296 00301 CS_DEPRECATED_METHOD_MSG("Use GetSize() instead.") 00302 size_t Length () const 00303 { 00304 return GetSize(); 00305 } 00306 00311 CS_DEPRECATED_METHOD_MSG("Use SetSize() instead.") 00312 void SetLength (size_t newSize) 00313 { 00314 SetSize (newSize); 00315 } 00316 00322 void SetSize (size_t newSize) 00323 { 00324 size_t newLength; 00325 if (newSize == 0) 00326 newLength = 0; 00327 else 00328 newLength = 1 + GetIndex (newSize - 1); 00329 00330 if (newLength != mLength) 00331 { 00332 // Avoid allocation if length is 1 (common case) 00333 csBitArrayStorageType* newStore; 00334 if (newLength <= cellCount) 00335 newStore = storage.inlineStore; 00336 else 00337 newStore = (csBitArrayStorageType*)storage.Alloc ( 00338 newLength * sizeof (csBitArrayStorageType)); 00339 00340 if (newLength > 0) 00341 { 00342 if (mLength > 0) 00343 { 00344 csBitArrayStorageType* oldStore = GetStore(); 00345 if (newStore != oldStore) 00346 { 00347 memcpy (newStore, oldStore, 00348 (MIN (mLength, newLength)) * sizeof (csBitArrayStorageType)); 00349 if (newLength > mLength) 00350 memset(newStore + mLength, 0, 00351 (newLength - mLength) * sizeof (csBitArrayStorageType)); 00352 if (!UseInlineStore ()) 00353 storage.Free (oldStore); 00354 } 00355 } 00356 else 00357 memset (newStore, 0, newLength * sizeof (csBitArrayStorageType)); 00358 } 00359 mLength = newLength; 00360 if (!UseInlineStore()) storage.heapStore = newStore; 00361 } 00362 00363 mNumBits = newSize; 00364 Trim(); 00365 } 00366 00367 // 00368 // Operators 00369 // 00370 00372 csBitArrayTweakable& operator=(const csBitArrayTweakable& that) 00373 { 00374 if (this != &that) 00375 { 00376 SetSize (that.mNumBits); 00377 memcpy (GetStore(), that.GetStore(), 00378 mLength * sizeof (csBitArrayStorageType)); 00379 } 00380 return *this; 00381 } 00382 00384 BitProxy operator[] (size_t pos) 00385 { 00386 CS_ASSERT (pos < mNumBits); 00387 return BitProxy(*this, pos); 00388 } 00389 00391 bool operator[] (size_t pos) const 00392 { 00393 return IsBitSet(pos); 00394 } 00395 00397 bool operator==(const csBitArrayTweakable& that) const 00398 { 00399 if (mNumBits != that.mNumBits) 00400 return false; 00401 00402 csBitArrayStorageType const* p0 = GetStore(); 00403 csBitArrayStorageType const* p1 = that.GetStore(); 00404 for (unsigned i = 0; i < mLength; i++) 00405 if (p0[i] != p1[i]) 00406 return false; 00407 return true; 00408 } 00409 00411 bool operator != (const csBitArrayTweakable& that) const 00412 { 00413 return !(*this == that); 00414 } 00415 00417 csBitArrayTweakable& operator &= (const csBitArrayTweakable &that) 00418 { 00419 CS_ASSERT (mNumBits == that.mNumBits); 00420 csBitArrayStorageType* p0 = GetStore(); 00421 csBitArrayStorageType const* p1 = that.GetStore(); 00422 for (size_t i = 0; i < mLength; i++) 00423 p0[i] &= p1[i]; 00424 return *this; 00425 } 00426 00428 csBitArrayTweakable operator |= (const csBitArrayTweakable& that) 00429 { 00430 CS_ASSERT (mNumBits == that.mNumBits); 00431 csBitArrayStorageType* p0 = GetStore(); 00432 csBitArrayStorageType const* p1 = that.GetStore(); 00433 for (size_t i = 0; i < mLength; i++) 00434 p0[i] |= p1[i]; 00435 return *this; 00436 } 00437 00439 csBitArrayTweakable operator ^= (const csBitArrayTweakable& that) 00440 { 00441 CS_ASSERT (mNumBits == that.mNumBits); 00442 csBitArrayStorageType* p0 = GetStore(); 00443 csBitArrayStorageType const* p1 = that.GetStore(); 00444 for (size_t i = 0; i < mLength; i++) 00445 p0[i] ^= p1[i]; 00446 return *this; 00447 } 00448 00450 csBitArrayTweakable operator~() const 00451 { 00452 return csBitArrayTweakable(*this).FlipAllBits(); 00453 } 00454 00456 friend csBitArrayTweakable operator& (const csBitArrayTweakable& a1, 00457 const csBitArrayTweakable& a2) 00458 { 00459 return csBitArrayTweakable (a1) &= a2; 00460 } 00461 00463 friend csBitArrayTweakable operator | (const csBitArrayTweakable& a1, 00464 const csBitArrayTweakable& a2) 00465 { 00466 return csBitArrayTweakable (a1) |= a2; 00467 } 00468 00470 friend csBitArrayTweakable operator ^ (const csBitArrayTweakable& a1, 00471 const csBitArrayTweakable& a2) 00472 { 00473 return csBitArrayTweakable (a1) ^= a2; 00474 } 00475 00476 // 00477 // Plain English interface 00478 // 00479 00481 void Clear() 00482 { 00483 memset (GetStore(), 0, mLength * sizeof(csBitArrayStorageType)); 00484 } 00485 00487 void SetBit (size_t pos) 00488 { 00489 CS_ASSERT (pos < mNumBits); 00490 GetStore()[GetIndex(pos)] |= ((csBitArrayStorageType)1) << GetOffset(pos); 00491 } 00492 00494 void ClearBit (size_t pos) 00495 { 00496 CS_ASSERT (pos < mNumBits); 00497 GetStore()[GetIndex(pos)] &= ~(((csBitArrayStorageType)1) << GetOffset(pos)); 00498 } 00499 00501 void FlipBit (size_t pos) 00502 { 00503 CS_ASSERT (pos < mNumBits); 00504 GetStore()[GetIndex(pos)] ^= ((csBitArrayStorageType)1) << GetOffset(pos); 00505 } 00506 00508 void Set (size_t pos, bool val = true) 00509 { 00510 if (val) 00511 SetBit(pos); 00512 else 00513 ClearBit(pos); 00514 } 00515 00517 bool IsBitSet (size_t pos) const 00518 { 00519 CS_ASSERT (pos < mNumBits); 00520 return (GetStore()[GetIndex(pos)] 00521 & (((csBitArrayStorageType)1) << GetOffset(pos))) != 0; 00522 } 00523 00525 bool AreSomeBitsSet (size_t pos, size_t count) const 00526 { 00527 CS_ASSERT (pos + count <= mNumBits); 00528 csBitArrayStorageType const* p = GetStore(); 00529 while (count > 0) 00530 { 00531 size_t index = GetIndex (pos); 00532 size_t offset = GetOffset (pos); 00533 size_t checkCount = MIN(count, cellSize - offset); 00534 csBitArrayStorageType mask = ((checkCount == cellSize) 00535 ? ~(csBitArrayStorageType)0 00536 : ((((csBitArrayStorageType)1) << checkCount) - 1)) << offset; 00537 if (p[index] & mask) 00538 return true; 00539 pos += checkCount; 00540 count -= checkCount; 00541 } 00542 return false; 00543 } 00544 00546 bool AllBitsFalse() const 00547 { 00548 csBitArrayStorageType const* p = GetStore(); 00549 for (size_t i = 0; i < mLength; i++) 00550 if (p[i] != 0) 00551 return false; 00552 return true; 00553 } 00554 00556 csBitArrayTweakable& FlipAllBits() 00557 { 00558 csBitArrayStorageType* p = GetStore(); 00559 for (size_t i = 0; i < mLength; i++) 00560 p[i] = ~p[i]; 00561 Trim(); 00562 return *this; 00563 } 00564 00566 size_t NumBitsSet() const 00567 { 00568 const size_t ui32perStorage = 00569 sizeof (csBitArrayStorageType) / sizeof (uint32); 00570 00571 union 00572 { 00573 csBitArrayStorageType s; 00574 uint32 ui32[ui32perStorage]; 00575 } v; 00576 00577 const csBitArrayStorageType* p = GetStore(); 00578 size_t num = 0; 00579 for (size_t i = 0; i < mLength; i++) 00580 { 00581 v.s = p[i]; 00582 for (size_t j = 0; j < ui32perStorage; j++) 00583 num += CS::Utility::BitOps::ComputeBitsSet (v.ui32[j]); 00584 } 00585 00586 return num; 00587 } 00588 00593 size_t GetFirstBitSet() const 00594 { 00595 const size_t ui32perStorage = 00596 sizeof (csBitArrayStorageType) / sizeof (uint32); 00597 00598 union 00599 { 00600 csBitArrayStorageType s; 00601 uint32 ui32[ui32perStorage]; 00602 } v; 00603 00604 const csBitArrayStorageType* p = GetStore(); 00605 size_t ofs = 0, result; 00606 for (size_t i = 0; i < mLength; i++) 00607 { 00608 v.s = p[i]; 00609 for (size_t j = 0; j < ui32perStorage; j++) 00610 { 00611 if (CS::Utility::BitOps::ScanBitForward (v.ui32[j], result)) 00612 { 00613 size_t r = ofs + result; 00614 if (r >= mNumBits) return csArrayItemNotFound; 00615 return r; 00616 } 00617 ofs += 32; 00618 } 00619 } 00620 return csArrayItemNotFound; 00621 } 00626 size_t GetFirstBitUnset() const 00627 { 00628 const size_t ui32perStorage = 00629 sizeof (csBitArrayStorageType) / sizeof (uint32); 00630 00631 union 00632 { 00633 csBitArrayStorageType s; 00634 uint32 ui32[ui32perStorage]; 00635 } v; 00636 00637 const csBitArrayStorageType* p = GetStore(); 00638 size_t ofs = 0, result; 00639 for (size_t i = 0; i < mLength; i++) 00640 { 00641 v.s = p[i]; 00642 for (size_t j = 0; j < ui32perStorage; j++) 00643 { 00644 if (CS::Utility::BitOps::ScanBitForward (~v.ui32[j], result)) 00645 { 00646 size_t r = ofs + result; 00647 if (r >= mNumBits) return csArrayItemNotFound; 00648 return r; 00649 } 00650 ofs += 32; 00651 } 00652 } 00653 return csArrayItemNotFound; 00654 } 00659 size_t GetLastBitSet() const 00660 { 00661 const size_t ui32perStorage = 00662 sizeof (csBitArrayStorageType) / sizeof (uint32); 00663 00664 union 00665 { 00666 csBitArrayStorageType s; 00667 uint32 ui32[ui32perStorage]; 00668 } v; 00669 00670 const csBitArrayStorageType* p = GetStore(); 00671 size_t ofs, result; 00672 ofs = 32 * (mLength*ui32perStorage-1); 00673 for (size_t i = mLength; i-- > 0;) 00674 { 00675 v.s = p[i]; 00676 for (size_t j = ui32perStorage; j-- > 0; ) 00677 { 00678 if (CS::Utility::BitOps::ScanBitForward (v.ui32[j], result)) 00679 { 00680 size_t r = ofs + result; 00681 if (r >= mNumBits) return csArrayItemNotFound; 00682 return r; 00683 } 00684 ofs -= 32; 00685 } 00686 } 00687 return csArrayItemNotFound; 00688 } 00693 size_t GetLastBitUnset() const 00694 { 00695 const size_t ui32perStorage = 00696 sizeof (csBitArrayStorageType) / sizeof (uint32); 00697 00698 union 00699 { 00700 csBitArrayStorageType s; 00701 uint32 ui32[ui32perStorage]; 00702 } v; 00703 00704 const csBitArrayStorageType* p = GetStore(); 00705 size_t ofs, result; 00706 ofs = 32 * (mLength*ui32perStorage-1); 00707 for (size_t i = mLength; i-- > 0;) 00708 { 00709 v.s = p[i]; 00710 for (size_t j = ui32perStorage; j-- > 0; ) 00711 { 00712 if (CS::Utility::BitOps::ScanBitForward (~v.ui32[j], result)) 00713 { 00714 size_t r = ofs + result; 00715 if (r >= mNumBits) return csArrayItemNotFound; 00716 return r; 00717 } 00718 ofs -= 32; 00719 } 00720 } 00721 return csArrayItemNotFound; 00722 } 00723 00728 void Delete(size_t pos, size_t count) 00729 { 00730 if (count > 0) 00731 { 00732 size_t dst = pos; 00733 size_t src = pos + count; 00734 CS_ASSERT(src <= mNumBits); 00735 size_t ntail = mNumBits - src; 00736 while (ntail-- > 0) 00737 Set(dst++, IsBitSet(src++)); 00738 SetSize(mNumBits - count); 00739 } 00740 } 00741 00746 csBitArrayTweakable Slice(size_t pos, size_t count) const 00747 { 00748 CS_ASSERT(pos + count <= mNumBits); 00749 csBitArrayTweakable a (count); 00750 for (size_t i = pos, o = 0; i < pos + count; i++) 00751 if (IsBitSet(i)) 00752 a.SetBit(o++); 00753 return a; 00754 } 00755 00757 00758 csBitArrayStorageType* GetArrayBits() { return GetStore(); } 00759 const csBitArrayStorageType* GetArrayBits() const { return GetStore(); } 00761 00763 00766 class SetBitIterator 00767 { 00768 public: 00769 SetBitIterator (const SetBitIterator& other) 00770 : bitArray (other.bitArray), pos (other.pos), offset (other.offset), 00771 cachedStore (other.cachedStore) 00772 {} 00773 00775 size_t Next () 00776 { 00777 while (offset < 8*sizeof(csBitArrayStorageType)) 00778 { 00779 if ((cachedStore & 0x1) != 0) 00780 { 00781 const size_t result = (pos-1)*sizeof(csBitArrayStorageType)*8 + offset; 00782 00783 ++offset; 00784 cachedStore >>= 1; 00785 if (!cachedStore) 00786 GetNextCacheItem (); 00787 00788 return result; 00789 } 00790 else 00791 { 00792 ++offset; 00793 cachedStore >>= 1; 00794 if (!cachedStore) 00795 GetNextCacheItem (); 00796 } 00797 } 00798 CS_ASSERT_MSG ("Invalid iteration", false); 00799 return 0; 00800 } 00801 00803 bool HasNext () const 00804 { 00805 return cachedStore != 0; 00806 } 00807 00809 void Reset () 00810 { 00811 pos = 0; 00812 GetNextCacheItem (); 00813 } 00814 00815 protected: 00816 SetBitIterator (const ThisType& bitArray) 00817 : bitArray (bitArray), pos (0), offset (0), cachedStore (0) 00818 { 00819 Reset (); 00820 } 00821 00822 friend class csBitArrayTweakable<InlinedBits, Allocator>; 00823 00824 void GetNextCacheItem () 00825 { 00826 offset = 0; 00827 while (pos < bitArray.mLength) 00828 { 00829 cachedStore = bitArray.GetStore ()[pos++]; 00830 if (cachedStore) 00831 return; 00832 } 00833 cachedStore = 0; 00834 } 00835 00836 const ThisType& bitArray; 00837 size_t pos, offset; 00838 csBitArrayStorageType cachedStore; 00839 }; 00840 friend class SetBitIterator; 00841 00842 SetBitIterator GetSetBitIterator () const 00843 { 00844 return SetBitIterator (*this); 00845 } 00847 }; 00848 00853 class csBitArray : public csBitArrayTweakable<> 00854 { 00855 public: 00857 csBitArray () { } 00859 explicit csBitArray (size_t size) : csBitArrayTweakable<> (size) { } 00861 csBitArray (const csBitArray& that) : csBitArrayTweakable<> (that) { } 00862 00864 template<int A, typename B> 00865 csBitArray& operator=(const csBitArrayTweakable<A, B>& that) 00866 { 00867 if (this != &that) 00868 { 00869 SetSize (that.GetSize()); 00870 memcpy (GetStore(), that.GetArrayBits(), 00871 mLength * sizeof (csBitArrayStorageType)); 00872 } 00873 return *this; 00874 } 00875 00876 }; 00877 00878 00883 template<> 00884 class csComparator<csBitArray, csBitArray> : 00885 public csComparatorBitArray<csBitArray> { }; 00886 00887 00892 template<> 00893 class csHashComputer<csBitArray> : 00894 public csHashComputerBitArray<csBitArray> { }; 00895 00896 00897 #endif // __CS_BITARRAY_H__
Generated for Crystal Space 1.4.0 by doxygen 1.5.8