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 "comparator.h"
00036 #include "hash.h"
00037 
00038 #if defined(CS_COMPILER_MSVC) && (CS_PROCESSOR_SIZE == 64)
00039 /* long is 32 bit even on 64-bit MSVC, so use uint64 to utilize a storage in
00040  * 64 bit units.
00041  */
00042 typedef uint64 csBitArrayStorageType;
00043 #else
00045 typedef unsigned long csBitArrayStorageType;
00046 #endif
00047 const size_t csBitArrayDefaultInlineBits = 
00048   sizeof (csBitArrayStorageType) * 8;
00049   
00050   
00052 template<typename BitArray>
00053 class csComparatorBitArray
00054 {
00055 public:
00056   static int Compare (BitArray const& key1, BitArray const& key2)
00057   {
00058     csBitArrayStorageType const* p0 = key1.GetStore();
00059     csBitArrayStorageType const* p1 = key2.GetStore();
00060     size_t compareNum = MIN (key1.mLength, key2.mLength);
00061     size_t i = 0;
00062     for (; i < compareNum; i++)
00063       if (p0[i] != p1[i])
00064         return (int)p0[i] - (int)p1[i];
00065     if (key1.mLength > key2.mLength)
00066     {
00067       for (; i < key1.mLength; i++)
00068         if (p0[i] != 0)
00069           return (int)p0[i];
00070     }
00071     else
00072     {
00073       for (; i < key2.mLength; i++)
00074         if (p1[i] != 0)
00075           return -((int)p1[i]);
00076     }
00077     return 0;
00078   }
00079 };
00080 
00081   
00083 template<typename BitArray>
00084 class csHashComputerBitArray
00085 {
00086 public:
00087   static uint ComputeHash (BitArray const& key)
00088   {
00089     const size_t uintCount = sizeof (csBitArrayStorageType) / sizeof (uint);
00090     uint ui[uintCount];
00091     uint hash = 0;
00092     csBitArrayStorageType const* p = key.GetStore();
00093     // \todo Not very good. Find a better hash function; however, it should
00094     // return the same hash for two bit arrays that are the same except for
00095     // the amount of trailing zeros. (e.g. f(10010110) == f(100101100000...))
00096     for (size_t i = 0; i < key.mLength; i++)
00097     {
00098       memcpy (ui, &p[i], sizeof (ui));
00099       for (size_t j = 0; j < uintCount; j++)
00100         hash += ui[j];
00101     }
00102     return hash;
00103   }
00104 };
00105 
00125 template<int InlinedBits = csBitArrayDefaultInlineBits,
00126   typename Allocator = CS::Memory::AllocatorMalloc>
00127 class csBitArrayTweakable
00128 {
00129 public:
00130   typedef csBitArrayTweakable<InlinedBits, Allocator> ThisType;
00131   typedef Allocator AllocatorType;
00132 
00133 private:
00134   template<typename BitArray> friend class csComparatorBitArray;
00135   template<typename BitArray> friend class csHashComputerBitArray;
00136 
00137   enum
00138   {
00139     cellSize    = csBitArrayDefaultInlineBits,
00140     cellCount   = (InlinedBits + (cellSize-1)) / cellSize
00141   };
00142 
00143   struct Storage : public Allocator
00144   {
00145     union
00146     {
00147       csBitArrayStorageType* heapStore;
00148       csBitArrayStorageType inlineStore[cellCount];
00149     };
00150     Storage()
00151     {
00152       memset (&inlineStore, 0, 
00153         MAX(sizeof (heapStore), sizeof (inlineStore)));
00154     }
00155   };
00156   Storage storage;
00158   size_t mLength;          
00159   size_t mNumBits;
00160 
00162   static size_t GetIndex (size_t bit_num)
00163   {
00164     return bit_num / cellSize;
00165   }
00166 
00168   static size_t GetOffset (size_t bit_num)
00169   {
00170     return bit_num % cellSize;
00171   }
00172 
00174   bool UseInlineStore () const
00175   {
00176     return mLength <= cellCount;
00177   }
00178 
00183   csBitArrayStorageType const* GetStore() const
00184   {
00185     return UseInlineStore () ? storage.inlineStore : storage.heapStore;
00186   }
00187 
00192   csBitArrayStorageType* GetStore()
00193   {
00194     return UseInlineStore () ? storage.inlineStore : storage.heapStore;
00195   }
00196 
00198   void Trim()
00199   {
00200     size_t extra_bits = mNumBits % cellSize;
00201     if (mLength > 0 && extra_bits != 0)
00202       GetStore()[mLength - 1] &= ~((~(csBitArrayStorageType)0) << extra_bits);
00203   }
00204 
00205 public:
00209   class BitProxy
00210   {
00211   private:
00212     csBitArrayTweakable& mArray;
00213     size_t mPos;
00214   public:
00216     BitProxy (csBitArrayTweakable& array, size_t pos): mArray(array), mPos(pos)
00217     {}
00218 
00220     BitProxy &operator= (bool value)
00221     {
00222       mArray.Set (mPos, value);
00223       return *this;
00224     }
00225 
00227     BitProxy &operator= (const BitProxy &that)
00228     {
00229       mArray.Set (mPos, that.mArray.IsBitSet (that.mPos));
00230       return *this;
00231     }
00232 
00234     operator bool() const
00235     {
00236       return mArray.IsBitSet (mPos);
00237     }
00238 
00243     bool Flip()
00244     {
00245       mArray.FlipBit (mPos);
00246       return mArray.IsBitSet (mPos);
00247     }
00248   };
00249   friend class BitProxy;
00250 
00254   csBitArrayTweakable () : mLength(0), mNumBits(0)
00255   {
00256     SetSize (0);
00257   }
00258 
00262   explicit csBitArrayTweakable (size_t size) : mLength(0), mNumBits(0)
00263   {
00264     SetSize (size);
00265   }
00266 
00270   csBitArrayTweakable (const csBitArrayTweakable& that) : mLength(0), mNumBits(0)
00271   {
00272     *this = that; // Invokes this->operator=().
00273   }
00274 
00276   ~csBitArrayTweakable()
00277   {
00278     if (!UseInlineStore ())
00279       storage.Free (storage.heapStore);
00280   }
00281 
00283   size_t GetSize() const
00284   {
00285     return mNumBits;
00286   }
00287 
00292   /*CS_DEPRECATED_METHOD_MSG("Use GetSize() instead.")*/
00293   size_t Length () const
00294   {
00295     return GetSize();
00296   }
00297 
00302   /*CS_DEPRECATED_METHOD_MSG("Use SetSize() instead.")*/
00303   void SetLength (size_t newSize)
00304   {
00305     SetSize (newSize);
00306   }
00307 
00313   void SetSize (size_t newSize)
00314   {
00315     size_t newLength;
00316     if (newSize == 0)
00317       newLength = 0;
00318     else
00319       newLength = 1 + GetIndex (newSize - 1);
00320 
00321     if (newLength != mLength)
00322     {
00323       // Avoid allocation if length is 1 (common case)
00324       csBitArrayStorageType* newStore;
00325       if (newLength <= cellCount)
00326         newStore = storage.inlineStore;
00327       else
00328         newStore = (csBitArrayStorageType*)storage.Alloc (
00329           newLength * sizeof (csBitArrayStorageType));
00330 
00331       if (newLength > 0)
00332       {
00333         if (mLength > 0)
00334         {
00335           csBitArrayStorageType* oldStore = GetStore();
00336           if (newStore != oldStore)
00337           {
00338             memcpy (newStore, oldStore, 
00339               (MIN (mLength, newLength)) * sizeof (csBitArrayStorageType));
00340             if (newLength > mLength)
00341               memset(newStore + mLength, 0,
00342                      (newLength - mLength) * sizeof (csBitArrayStorageType));
00343             if (!UseInlineStore ())
00344               storage.Free (oldStore);
00345           }
00346         }
00347         else
00348           memset (newStore, 0, newLength * sizeof (csBitArrayStorageType));
00349       }
00350       mLength = newLength;
00351       if (!UseInlineStore()) storage.heapStore = newStore;
00352     }
00353 
00354     mNumBits = newSize;
00355     Trim();
00356   }
00357 
00358   //
00359   // Operators
00360   //
00361 
00363   csBitArrayTweakable& operator=(const csBitArrayTweakable& that)
00364   {
00365     if (this != &that)
00366     {
00367       SetSize (that.mNumBits);
00368       memcpy (GetStore(), that.GetStore(), 
00369         mLength * sizeof (csBitArrayStorageType));
00370     }
00371     return *this;
00372   }
00373 
00375   BitProxy operator[] (size_t pos)
00376   {
00377     CS_ASSERT (pos < mNumBits);
00378     return BitProxy(*this, pos);
00379   }
00380 
00382   bool operator[] (size_t pos) const
00383   {
00384     return IsBitSet(pos);
00385   }
00386 
00388   bool operator==(const csBitArrayTweakable& that) const
00389   {
00390     if (mNumBits != that.mNumBits)
00391       return false;
00392 
00393     csBitArrayStorageType const* p0 = GetStore();
00394     csBitArrayStorageType const* p1 = that.GetStore();
00395     for (unsigned i = 0; i < mLength; i++)
00396       if (p0[i] != p1[i])
00397         return false;
00398     return true;
00399   }
00400 
00402   bool operator != (const csBitArrayTweakable& that) const
00403   {
00404     return !(*this == that);
00405   }
00406 
00408   csBitArrayTweakable& operator &= (const csBitArrayTweakable &that)
00409   {
00410     CS_ASSERT (mNumBits == that.mNumBits);
00411     csBitArrayStorageType* p0 = GetStore();
00412     csBitArrayStorageType const* p1 = that.GetStore();
00413     for (size_t i = 0; i < mLength; i++)
00414       p0[i] &= p1[i];
00415     return *this;
00416   }
00417 
00419   csBitArrayTweakable operator |= (const csBitArrayTweakable& that)
00420   {
00421     CS_ASSERT (mNumBits == that.mNumBits);
00422     csBitArrayStorageType* p0 = GetStore();
00423     csBitArrayStorageType const* p1 = that.GetStore();
00424     for (size_t i = 0; i < mLength; i++)
00425       p0[i] |= p1[i];
00426     return *this;
00427   }
00428 
00430   csBitArrayTweakable operator ^= (const csBitArrayTweakable& that)
00431   {
00432     CS_ASSERT (mNumBits == that.mNumBits);
00433     csBitArrayStorageType* p0 = GetStore();
00434     csBitArrayStorageType const* p1 = that.GetStore();
00435     for (size_t i = 0; i < mLength; i++)
00436       p0[i] ^= p1[i];
00437     return *this;
00438   }
00439 
00441   csBitArrayTweakable operator~() const
00442   {
00443     return csBitArrayTweakable(*this).FlipAllBits();
00444   }
00445 
00447   friend csBitArrayTweakable operator& (const csBitArrayTweakable& a1, 
00448     const csBitArrayTweakable& a2)
00449   {
00450     return csBitArrayTweakable (a1) &= a2;
00451   }
00452 
00454   friend csBitArrayTweakable operator | (const csBitArrayTweakable& a1, 
00455     const csBitArrayTweakable& a2)
00456   {
00457     return csBitArrayTweakable (a1) |= a2;
00458   }
00459 
00461   friend csBitArrayTweakable operator ^ (const csBitArrayTweakable& a1, 
00462     const csBitArrayTweakable& a2)
00463   {
00464     return csBitArrayTweakable (a1) ^= a2;
00465   }
00466 
00467   //
00468   // Plain English interface
00469   //
00470 
00472   void Clear()
00473   {
00474     memset (GetStore(), 0, mLength * sizeof(csBitArrayStorageType));
00475   }
00476 
00478   void SetBit (size_t pos)
00479   {
00480     CS_ASSERT (pos < mNumBits);
00481     GetStore()[GetIndex(pos)] |= ((csBitArrayStorageType)1) << GetOffset(pos);
00482   }
00483 
00485   void ClearBit (size_t pos)
00486   {
00487     CS_ASSERT (pos < mNumBits);
00488     GetStore()[GetIndex(pos)] &= ~(((csBitArrayStorageType)1) << GetOffset(pos));
00489   }
00490 
00492   void FlipBit (size_t pos)
00493   {
00494     CS_ASSERT (pos < mNumBits);
00495     GetStore()[GetIndex(pos)] ^= ((csBitArrayStorageType)1) << GetOffset(pos);
00496   }
00497 
00499   void Set (size_t pos, bool val = true)
00500   {
00501     if (val)
00502       SetBit(pos);
00503     else
00504       ClearBit(pos);
00505   }
00506 
00508   bool IsBitSet (size_t pos) const
00509   {
00510     CS_ASSERT (pos < mNumBits);
00511     return (GetStore()[GetIndex(pos)] 
00512       & (((csBitArrayStorageType)1) << GetOffset(pos))) != 0;
00513   }
00514 
00516   bool AreSomeBitsSet (size_t pos, size_t count) const
00517   {
00518     CS_ASSERT (pos + count <= mNumBits);
00519     csBitArrayStorageType const* p = GetStore();
00520     while (count > 0)
00521     {
00522       size_t index = GetIndex (pos);
00523       size_t offset = GetOffset (pos);
00524       size_t checkCount = MIN(count, cellSize - offset);
00525       csBitArrayStorageType mask = ((checkCount == cellSize) 
00526         ? ~(csBitArrayStorageType)0 
00527         : ((((csBitArrayStorageType)1) << checkCount) - 1)) << offset;
00528       if (p[index] & mask)
00529         return true;
00530       pos += checkCount;
00531       count -= checkCount;
00532     }
00533     return false;
00534   }
00535   
00537   bool AllBitsFalse() const
00538   {
00539     csBitArrayStorageType const* p = GetStore();
00540     for (size_t i = 0; i < mLength; i++)
00541       if (p[i] != 0)
00542         return false;
00543     return true;
00544   }
00545 
00547   csBitArrayTweakable& FlipAllBits()
00548   {
00549     csBitArrayStorageType* p = GetStore();
00550     for (size_t i = 0; i < mLength; i++)
00551       p[i] = ~p[i];
00552     Trim();
00553     return *this;
00554   }
00555 
00560   void Delete(size_t pos, size_t count)
00561   {
00562     if (count > 0)
00563     {
00564       size_t dst = pos;
00565       size_t src = pos + count;
00566       CS_ASSERT(src <= mNumBits);
00567       size_t ntail = mNumBits - src;
00568       while (ntail-- > 0)
00569         Set(dst++, IsBitSet(src++));
00570       SetSize(mNumBits - count);
00571     }
00572   }
00573 
00578   csBitArrayTweakable Slice(size_t pos, size_t count) const
00579   {
00580     CS_ASSERT(pos + count <= mNumBits);
00581     csBitArrayTweakable a (count);
00582     for (size_t i = pos, o = 0; i < pos + count; i++)
00583       if (IsBitSet(i))
00584         a.SetBit(o++);
00585     return a;
00586   }
00587 
00589   csBitArrayStorageType* GetArrayBits()
00590   {
00591     return GetStore();
00592   }
00593 };
00594 
00599 class csBitArray : public csBitArrayTweakable<>
00600 {
00601 public:
00603   csBitArray () { }
00605   explicit csBitArray (size_t size) : csBitArrayTweakable<> (size) { }
00607   csBitArray (const csBitArray& that) : csBitArrayTweakable<> (that) { }
00608 };
00609 
00610 
00615 template<>
00616 class csComparator<csBitArray, csBitArray> : 
00617   public csComparatorBitArray<csBitArray> { };
00618 
00619 
00624 template<>
00625 class csHashComputer<csBitArray> : 
00626   public csHashComputerBitArray<csBitArray> { };
00627 
00628 
00629 #endif // __CS_BITARRAY_H__

Generated for Crystal Space 1.0.2 by doxygen 1.4.7