CrystalSpace

Public API Reference

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.1 by doxygen 1.5.3