csutil/bitarray.h
Go to the documentation of this file.00001 /* 00002 Copyright (C) 2000 by Andrew Kirmse 00003 00004 This library is free software; you can redistribute it and/or 00005 modify it under the terms of the GNU Library General Public 00006 License as published by the Free Software Foundation; either 00007 version 2 of the License, or (at your option) any later version. 00008 00009 This library is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 Library General Public License for more details. 00013 00014 You should have received a copy of the GNU Library General Public 00015 License along with this library; if not, write to the Free 00016 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00017 */ 00018 00019 // A one-dimensional array of bits, similar to STL bitset. 00020 // 00021 // Copyright 2000 Andrew Kirmse. All rights reserved. 00022 // 00023 // Permission is granted to use this code for any purpose, as long as this 00024 // copyright message remains intact. 00025 00026 #ifndef __CS_BITARRAY_H__ 00027 #define __CS_BITARRAY_H__ 00028 00033 #include "csextern.h" 00034 #include "allocator.h" 00035 #include "bitops.h" 00036 #include "comparator.h" 00037 #include "hash.h" 00038 00039 #if defined(CS_COMPILER_MSVC) && (CS_PROCESSOR_SIZE == 64) 00040 /* long is 32 bit even on 64-bit MSVC, so use uint64 to utilize a storage in 00041 * 64 bit units. 00042 */ 00043 typedef uint64 csBitArrayStorageType; 00044 #else 00046 typedef unsigned long csBitArrayStorageType; 00047 #endif 00048 const size_t csBitArrayDefaultInlineBits = 00049 sizeof (csBitArrayStorageType) * 8; 00050 00051 00053 template<typename BitArray> 00054 class csComparatorBitArray 00055 { 00056 public: 00057 static int Compare (BitArray const& key1, BitArray const& key2) 00058 { 00059 csBitArrayStorageType const* p0 = key1.GetStore(); 00060 csBitArrayStorageType const* p1 = key2.GetStore(); 00061 size_t compareNum = MIN (key1.mLength, key2.mLength); 00062 size_t i = 0; 00063 for (; i < compareNum; i++) 00064 if (p0[i] != p1[i]) 00065 return (int)p0[i] - (int)p1[i]; 00066 if (key1.mLength > key2.mLength) 00067 { 00068 for (; i < key1.mLength; i++) 00069 if (p0[i] != 0) 00070 return (int)p0[i]; 00071 } 00072 else 00073 { 00074 for (; i < key2.mLength; i++) 00075 if (p1[i] != 0) 00076 return -((int)p1[i]); 00077 } 00078 return 0; 00079 } 00080 }; 00081 00082 00084 template<typename BitArray> 00085 class csHashComputerBitArray 00086 { 00087 public: 00088 static uint ComputeHash (BitArray const& key) 00089 { 00090 const size_t uintCount = sizeof (csBitArrayStorageType) / sizeof (uint); 00091 uint ui[uintCount]; 00092 uint hash = 0; 00093 csBitArrayStorageType const* p = key.GetStore(); 00094 // \todo Not very good. Find a better hash function; however, it should 00095 // return the same hash for two bit arrays that are the same except for 00096 // the amount of trailing zeros. (e.g. f(10010110) == f(100101100000...)) 00097 for (size_t i = 0; i < key.mLength; i++) 00098 { 00099 memcpy (ui, &p[i], sizeof (ui)); 00100 for (size_t j = 0; j < uintCount; j++) 00101 hash += ui[j]; 00102 } 00103 return hash; 00104 } 00105 }; 00106 00126 template<int InlinedBits = csBitArrayDefaultInlineBits, 00127 typename Allocator = CS::Memory::AllocatorMalloc> 00128 class csBitArrayTweakable 00129 { 00130 public: 00131 typedef csBitArrayTweakable<InlinedBits, Allocator> ThisType; 00132 typedef Allocator AllocatorType; 00133 00134 private: 00135 template<typename BitArray> friend class csComparatorBitArray; 00136 template<typename BitArray> friend class csHashComputerBitArray; 00137 00138 enum 00139 { 00140 cellSize = csBitArrayDefaultInlineBits, 00141 cellCount = (InlinedBits + (cellSize-1)) / cellSize 00142 }; 00143 00144 struct Storage : public Allocator 00145 { 00146 union 00147 { 00148 csBitArrayStorageType* heapStore; 00149 csBitArrayStorageType inlineStore[cellCount]; 00150 }; 00151 Storage() 00152 { 00153 memset (&inlineStore, 0, 00154 MAX(sizeof (heapStore), sizeof (inlineStore))); 00155 } 00156 }; 00157 Storage storage; 00159 size_t mLength; 00160 size_t mNumBits; 00161 00163 static size_t GetIndex (size_t bit_num) 00164 { 00165 return bit_num / cellSize; 00166 } 00167 00169 static size_t GetOffset (size_t bit_num) 00170 { 00171 return bit_num % cellSize; 00172 } 00173 00175 bool UseInlineStore () const 00176 { 00177 return mLength <= cellCount; 00178 } 00179 00184 csBitArrayStorageType const* GetStore() const 00185 { 00186 return UseInlineStore () ? storage.inlineStore : storage.heapStore; 00187 } 00188 00193 csBitArrayStorageType* GetStore() 00194 { 00195 return UseInlineStore () ? storage.inlineStore : storage.heapStore; 00196 } 00197 00199 void Trim() 00200 { 00201 size_t extra_bits = mNumBits % cellSize; 00202 if (mLength > 0 && extra_bits != 0) 00203 GetStore()[mLength - 1] &= ~((~(csBitArrayStorageType)0) << extra_bits); 00204 } 00205 00206 public: 00210 class BitProxy 00211 { 00212 private: 00213 csBitArrayTweakable& mArray; 00214 size_t mPos; 00215 public: 00217 BitProxy (csBitArrayTweakable& array, size_t pos): mArray(array), mPos(pos) 00218 {} 00219 00221 BitProxy &operator= (bool value) 00222 { 00223 mArray.Set (mPos, value); 00224 return *this; 00225 } 00226 00228 BitProxy &operator= (const BitProxy &that) 00229 { 00230 mArray.Set (mPos, that.mArray.IsBitSet (that.mPos)); 00231 return *this; 00232 } 00233 00235 operator bool() const 00236 { 00237 return mArray.IsBitSet (mPos); 00238 } 00239 00244 bool Flip() 00245 { 00246 mArray.FlipBit (mPos); 00247 return mArray.IsBitSet (mPos); 00248 } 00249 }; 00250 friend class BitProxy; 00251 00255 csBitArrayTweakable () : mLength(0), mNumBits(0) 00256 { 00257 SetSize (0); 00258 } 00259 00263 explicit csBitArrayTweakable (size_t size) : mLength(0), mNumBits(0) 00264 { 00265 SetSize (size); 00266 } 00267 00271 csBitArrayTweakable (const csBitArrayTweakable& that) : mLength(0), mNumBits(0) 00272 { 00273 *this = that; // Invokes this->operator=(). 00274 } 00275 00277 ~csBitArrayTweakable() 00278 { 00279 if (!UseInlineStore ()) 00280 storage.Free (storage.heapStore); 00281 } 00282 00284 size_t GetSize() const 00285 { 00286 return mNumBits; 00287 } 00288 00293 /*CS_DEPRECATED_METHOD_MSG("Use GetSize() instead.")*/ 00294 size_t Length () const 00295 { 00296 return GetSize(); 00297 } 00298 00303 /*CS_DEPRECATED_METHOD_MSG("Use SetSize() instead.")*/ 00304 void SetLength (size_t newSize) 00305 { 00306 SetSize (newSize); 00307 } 00308 00314 void SetSize (size_t newSize) 00315 { 00316 size_t newLength; 00317 if (newSize == 0) 00318 newLength = 0; 00319 else 00320 newLength = 1 + GetIndex (newSize - 1); 00321 00322 if (newLength != mLength) 00323 { 00324 // Avoid allocation if length is 1 (common case) 00325 csBitArrayStorageType* newStore; 00326 if (newLength <= cellCount) 00327 newStore = storage.inlineStore; 00328 else 00329 newStore = (csBitArrayStorageType*)storage.Alloc ( 00330 newLength * sizeof (csBitArrayStorageType)); 00331 00332 if (newLength > 0) 00333 { 00334 if (mLength > 0) 00335 { 00336 csBitArrayStorageType* oldStore = GetStore(); 00337 if (newStore != oldStore) 00338 { 00339 memcpy (newStore, oldStore, 00340 (MIN (mLength, newLength)) * sizeof (csBitArrayStorageType)); 00341 if (newLength > mLength) 00342 memset(newStore + mLength, 0, 00343 (newLength - mLength) * sizeof (csBitArrayStorageType)); 00344 if (!UseInlineStore ()) 00345 storage.Free (oldStore); 00346 } 00347 } 00348 else 00349 memset (newStore, 0, newLength * sizeof (csBitArrayStorageType)); 00350 } 00351 mLength = newLength; 00352 if (!UseInlineStore()) storage.heapStore = newStore; 00353 } 00354 00355 mNumBits = newSize; 00356 Trim(); 00357 } 00358 00359 // 00360 // Operators 00361 // 00362 00364 csBitArrayTweakable& operator=(const csBitArrayTweakable& that) 00365 { 00366 if (this != &that) 00367 { 00368 SetSize (that.mNumBits); 00369 memcpy (GetStore(), that.GetStore(), 00370 mLength * sizeof (csBitArrayStorageType)); 00371 } 00372 return *this; 00373 } 00374 00376 BitProxy operator[] (size_t pos) 00377 { 00378 CS_ASSERT (pos < mNumBits); 00379 return BitProxy(*this, pos); 00380 } 00381 00383 bool operator[] (size_t pos) const 00384 { 00385 return IsBitSet(pos); 00386 } 00387 00389 bool operator==(const csBitArrayTweakable& that) const 00390 { 00391 if (mNumBits != that.mNumBits) 00392 return false; 00393 00394 csBitArrayStorageType const* p0 = GetStore(); 00395 csBitArrayStorageType const* p1 = that.GetStore(); 00396 for (unsigned i = 0; i < mLength; i++) 00397 if (p0[i] != p1[i]) 00398 return false; 00399 return true; 00400 } 00401 00403 bool operator != (const csBitArrayTweakable& that) const 00404 { 00405 return !(*this == that); 00406 } 00407 00409 csBitArrayTweakable& operator &= (const csBitArrayTweakable &that) 00410 { 00411 CS_ASSERT (mNumBits == that.mNumBits); 00412 csBitArrayStorageType* p0 = GetStore(); 00413 csBitArrayStorageType const* p1 = that.GetStore(); 00414 for (size_t i = 0; i < mLength; i++) 00415 p0[i] &= p1[i]; 00416 return *this; 00417 } 00418 00420 csBitArrayTweakable operator |= (const csBitArrayTweakable& that) 00421 { 00422 CS_ASSERT (mNumBits == that.mNumBits); 00423 csBitArrayStorageType* p0 = GetStore(); 00424 csBitArrayStorageType const* p1 = that.GetStore(); 00425 for (size_t i = 0; i < mLength; i++) 00426 p0[i] |= p1[i]; 00427 return *this; 00428 } 00429 00431 csBitArrayTweakable operator ^= (const csBitArrayTweakable& that) 00432 { 00433 CS_ASSERT (mNumBits == that.mNumBits); 00434 csBitArrayStorageType* p0 = GetStore(); 00435 csBitArrayStorageType const* p1 = that.GetStore(); 00436 for (size_t i = 0; i < mLength; i++) 00437 p0[i] ^= p1[i]; 00438 return *this; 00439 } 00440 00442 csBitArrayTweakable operator~() const 00443 { 00444 return csBitArrayTweakable(*this).FlipAllBits(); 00445 } 00446 00448 friend csBitArrayTweakable operator& (const csBitArrayTweakable& a1, 00449 const csBitArrayTweakable& a2) 00450 { 00451 return csBitArrayTweakable (a1) &= a2; 00452 } 00453 00455 friend csBitArrayTweakable operator | (const csBitArrayTweakable& a1, 00456 const csBitArrayTweakable& a2) 00457 { 00458 return csBitArrayTweakable (a1) |= a2; 00459 } 00460 00462 friend csBitArrayTweakable operator ^ (const csBitArrayTweakable& a1, 00463 const csBitArrayTweakable& a2) 00464 { 00465 return csBitArrayTweakable (a1) ^= a2; 00466 } 00467 00468 // 00469 // Plain English interface 00470 // 00471 00473 void Clear() 00474 { 00475 memset (GetStore(), 0, mLength * sizeof(csBitArrayStorageType)); 00476 } 00477 00479 void SetBit (size_t pos) 00480 { 00481 CS_ASSERT (pos < mNumBits); 00482 GetStore()[GetIndex(pos)] |= ((csBitArrayStorageType)1) << GetOffset(pos); 00483 } 00484 00486 void ClearBit (size_t pos) 00487 { 00488 CS_ASSERT (pos < mNumBits); 00489 GetStore()[GetIndex(pos)] &= ~(((csBitArrayStorageType)1) << GetOffset(pos)); 00490 } 00491 00493 void FlipBit (size_t pos) 00494 { 00495 CS_ASSERT (pos < mNumBits); 00496 GetStore()[GetIndex(pos)] ^= ((csBitArrayStorageType)1) << GetOffset(pos); 00497 } 00498 00500 void Set (size_t pos, bool val = true) 00501 { 00502 if (val) 00503 SetBit(pos); 00504 else 00505 ClearBit(pos); 00506 } 00507 00509 bool IsBitSet (size_t pos) const 00510 { 00511 CS_ASSERT (pos < mNumBits); 00512 return (GetStore()[GetIndex(pos)] 00513 & (((csBitArrayStorageType)1) << GetOffset(pos))) != 0; 00514 } 00515 00517 bool AreSomeBitsSet (size_t pos, size_t count) const 00518 { 00519 CS_ASSERT (pos + count <= mNumBits); 00520 csBitArrayStorageType const* p = GetStore(); 00521 while (count > 0) 00522 { 00523 size_t index = GetIndex (pos); 00524 size_t offset = GetOffset (pos); 00525 size_t checkCount = MIN(count, cellSize - offset); 00526 csBitArrayStorageType mask = ((checkCount == cellSize) 00527 ? ~(csBitArrayStorageType)0 00528 : ((((csBitArrayStorageType)1) << checkCount) - 1)) << offset; 00529 if (p[index] & mask) 00530 return true; 00531 pos += checkCount; 00532 count -= checkCount; 00533 } 00534 return false; 00535 } 00536 00538 bool AllBitsFalse() const 00539 { 00540 csBitArrayStorageType const* p = GetStore(); 00541 for (size_t i = 0; i < mLength; i++) 00542 if (p[i] != 0) 00543 return false; 00544 return true; 00545 } 00546 00548 csBitArrayTweakable& FlipAllBits() 00549 { 00550 csBitArrayStorageType* p = GetStore(); 00551 for (size_t i = 0; i < mLength; i++) 00552 p[i] = ~p[i]; 00553 Trim(); 00554 return *this; 00555 } 00556 00558 size_t NumBitsSet() const 00559 { 00560 const size_t ui32perStorage = 00561 sizeof (csBitArrayStorageType) / sizeof (uint32); 00562 00563 union 00564 { 00565 csBitArrayStorageType s; 00566 uint32 ui32[ui32perStorage]; 00567 } v; 00568 00569 const csBitArrayStorageType* p = GetStore(); 00570 size_t num = 0; 00571 for (size_t i = 0; i < mLength; i++) 00572 { 00573 v.s = p[i]; 00574 for (size_t j = 0; j < ui32perStorage; j++) 00575 num += CS::Utility::BitOps::ComputeBitsSet (v.ui32[j]); 00576 } 00577 00578 return num; 00579 } 00580 00585 void Delete(size_t pos, size_t count) 00586 { 00587 if (count > 0) 00588 { 00589 size_t dst = pos; 00590 size_t src = pos + count; 00591 CS_ASSERT(src <= mNumBits); 00592 size_t ntail = mNumBits - src; 00593 while (ntail-- > 0) 00594 Set(dst++, IsBitSet(src++)); 00595 SetSize(mNumBits - count); 00596 } 00597 } 00598 00603 csBitArrayTweakable Slice(size_t pos, size_t count) const 00604 { 00605 CS_ASSERT(pos + count <= mNumBits); 00606 csBitArrayTweakable a (count); 00607 for (size_t i = pos, o = 0; i < pos + count; i++) 00608 if (IsBitSet(i)) 00609 a.SetBit(o++); 00610 return a; 00611 } 00612 00614 csBitArrayStorageType* GetArrayBits() 00615 { 00616 return GetStore(); 00617 } 00618 }; 00619 00624 class csBitArray : public csBitArrayTweakable<> 00625 { 00626 public: 00628 csBitArray () { } 00630 explicit csBitArray (size_t size) : csBitArrayTweakable<> (size) { } 00632 csBitArray (const csBitArray& that) : csBitArrayTweakable<> (that) { } 00633 }; 00634 00635 00640 template<> 00641 class csComparator<csBitArray, csBitArray> : 00642 public csComparatorBitArray<csBitArray> { }; 00643 00644 00649 template<> 00650 class csHashComputer<csBitArray> : 00651 public csHashComputerBitArray<csBitArray> { }; 00652 00653 00654 #endif // __CS_BITARRAY_H__
Generated for Crystal Space 1.2 by doxygen 1.4.7