CrystalSpace

Public API Reference

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
00049 
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 
00218   void SetSizeInternal (size_t newSize)
00219   {
00220     size_t newLength;
00221     if (newSize == 0)
00222       newLength = 0;
00223     else
00224       newLength = 1 + GetIndex (newSize - 1);
00225 
00226     if (newLength != mLength)
00227     {
00228       // Avoid allocation if length is 1 (common case)
00229       csBitArrayStorageType* newStore;
00230       if (newLength <= cellCount)
00231         newStore = storage.inlineStore;
00232       else
00233         newStore = (csBitArrayStorageType*)storage.Alloc (
00234           newLength * sizeof (csBitArrayStorageType));
00235 
00236       if (newLength > 0)
00237       {
00238         if (mLength > 0)
00239         {
00240           csBitArrayStorageType* oldStore = GetStore();
00241           if (newStore != oldStore)
00242           {
00243             memcpy (newStore, oldStore, 
00244               (MIN (mLength, newLength)) * sizeof (csBitArrayStorageType));
00245             if (newLength > mLength)
00246               memset(newStore + mLength, 0,
00247                      (newLength - mLength) * sizeof (csBitArrayStorageType));
00248             if (!UseInlineStore ())
00249               storage.Free (oldStore);
00250           }
00251         }
00252         else
00253           memset (newStore, 0, newLength * sizeof (csBitArrayStorageType));
00254       }
00255       mLength = newLength;
00256       if (!UseInlineStore()) storage.heapStore = newStore;
00257     }
00258 
00259     mNumBits = newSize;
00260   }
00261 
00262 public:
00266   class BitProxy
00267   {
00268   private:
00269     csBitArrayTweakable& mArray;
00270     size_t mPos;
00271   public:
00273     BitProxy (csBitArrayTweakable& array, size_t pos): mArray(array), mPos(pos)
00274     {}
00275 
00277     BitProxy &operator= (bool value)
00278     {
00279       mArray.Set (mPos, value);
00280       return *this;
00281     }
00282 
00284     BitProxy &operator= (const BitProxy &that)
00285     {
00286       mArray.Set (mPos, that.mArray.IsBitSet (that.mPos));
00287       return *this;
00288     }
00289 
00291     operator bool() const
00292     {
00293       return mArray.IsBitSet (mPos);
00294     }
00295 
00300     bool Flip()
00301     {
00302       mArray.FlipBit (mPos);
00303       return mArray.IsBitSet (mPos);
00304     }
00305   };
00306   friend class BitProxy;
00307 
00311   csBitArrayTweakable () : mLength(0), mNumBits(0)
00312   {
00313     SetSize (0);
00314   }
00315 
00319   explicit csBitArrayTweakable (size_t size) : mLength(0), mNumBits(0)
00320   {
00321     SetSize (size);
00322   }
00323 
00327   csBitArrayTweakable (const csBitArrayTweakable& that) : mLength(0), mNumBits(0)
00328   {
00329     *this = that; // Invokes this->operator=().
00330   }
00331 
00333   ~csBitArrayTweakable()
00334   {
00335     if (!UseInlineStore ())
00336       storage.Free (storage.heapStore);
00337   }
00338 
00340   size_t GetSize() const
00341   {
00342     return mNumBits;
00343   }
00344 
00349   CS_DEPRECATED_METHOD_MSG("Use GetSize() instead.")
00350   size_t Length () const
00351   {
00352     return GetSize();
00353   }
00354 
00359   CS_DEPRECATED_METHOD_MSG("Use SetSize() instead.")
00360   void SetLength (size_t newSize)
00361   {
00362     SetSize (newSize);
00363   }
00364 
00370   void SetSize (size_t newSize)
00371   {
00372     SetSizeInternal (newSize);
00373     Trim();
00374   }
00375 
00376   //
00377   // Operators
00378   //
00379 
00381   csBitArrayTweakable& operator=(const csBitArrayTweakable& that)
00382   {
00383     if (this != &that)
00384     {
00385       SetSizeInternal (that.mNumBits);
00386       memcpy (GetStore(), that.GetStore(), 
00387         mLength * sizeof (csBitArrayStorageType));
00388     }
00389     return *this;
00390   }
00391 
00393   BitProxy operator[] (size_t pos)
00394   {
00395     CS_ASSERT (pos < mNumBits);
00396     return BitProxy(*this, pos);
00397   }
00398 
00400   bool operator[] (size_t pos) const
00401   {
00402     return IsBitSet(pos);
00403   }
00404 
00406   bool operator==(const csBitArrayTweakable& that) const
00407   {
00408     if (mNumBits != that.mNumBits)
00409       return false;
00410 
00411     csBitArrayStorageType const* p0 = GetStore();
00412     csBitArrayStorageType const* p1 = that.GetStore();
00413     for (unsigned i = 0; i < mLength; i++)
00414       if (p0[i] != p1[i])
00415         return false;
00416     return true;
00417   }
00418 
00420   bool operator != (const csBitArrayTweakable& that) const
00421   {
00422     return !(*this == that);
00423   }
00424 
00426   csBitArrayTweakable& operator &= (const csBitArrayTweakable &that)
00427   {
00428     CS_ASSERT (mNumBits == that.mNumBits);
00429     csBitArrayStorageType* p0 = GetStore();
00430     csBitArrayStorageType const* p1 = that.GetStore();
00431     for (size_t i = 0; i < mLength; i++)
00432       p0[i] &= p1[i];
00433     return *this;
00434   }
00435 
00437   csBitArrayTweakable operator |= (const csBitArrayTweakable& that)
00438   {
00439     CS_ASSERT (mNumBits == that.mNumBits);
00440     csBitArrayStorageType* p0 = GetStore();
00441     csBitArrayStorageType const* p1 = that.GetStore();
00442     for (size_t i = 0; i < mLength; i++)
00443       p0[i] |= p1[i];
00444     return *this;
00445   }
00446 
00448   csBitArrayTweakable operator ^= (const csBitArrayTweakable& that)
00449   {
00450     CS_ASSERT (mNumBits == that.mNumBits);
00451     csBitArrayStorageType* p0 = GetStore();
00452     csBitArrayStorageType const* p1 = that.GetStore();
00453     for (size_t i = 0; i < mLength; i++)
00454       p0[i] ^= p1[i];
00455     return *this;
00456   }
00457 
00459   csBitArrayTweakable operator~() const
00460   {
00461     return csBitArrayTweakable(*this).FlipAllBits();
00462   }
00463 
00465   friend csBitArrayTweakable operator& (const csBitArrayTweakable& a1, 
00466     const csBitArrayTweakable& a2)
00467   {
00468     return csBitArrayTweakable (a1) &= a2;
00469   }
00470 
00472   friend csBitArrayTweakable operator | (const csBitArrayTweakable& a1, 
00473     const csBitArrayTweakable& a2)
00474   {
00475     return csBitArrayTweakable (a1) |= a2;
00476   }
00477 
00479   friend csBitArrayTweakable operator ^ (const csBitArrayTweakable& a1, 
00480     const csBitArrayTweakable& a2)
00481   {
00482     return csBitArrayTweakable (a1) ^= a2;
00483   }
00484 
00485   //
00486   // Plain English interface
00487   //
00488 
00490   void Clear()
00491   {
00492     memset (GetStore(), 0, mLength * sizeof(csBitArrayStorageType));
00493   }
00494 
00496   void SetAll()
00497   {
00498     csBitArrayStorageType* store = GetStore();
00499     for (size_t i = 0; i < mNumBits; i++)
00500       store[GetIndex(i)] = ((csBitArrayStorageType)1) << GetOffset(i);
00501   }
00502 
00504   void SetBit (size_t pos)
00505   {
00506     CS_ASSERT (pos < mNumBits);
00507     GetStore()[GetIndex(pos)] |= ((csBitArrayStorageType)1) << GetOffset(pos);
00508   }
00509 
00511   void ClearBit (size_t pos)
00512   {
00513     CS_ASSERT (pos < mNumBits);
00514     GetStore()[GetIndex(pos)] &= ~(((csBitArrayStorageType)1) << GetOffset(pos));
00515   }
00516 
00518   void FlipBit (size_t pos)
00519   {
00520     CS_ASSERT (pos < mNumBits);
00521     GetStore()[GetIndex(pos)] ^= ((csBitArrayStorageType)1) << GetOffset(pos);
00522   }
00523 
00525   void Set (size_t pos, bool val = true)
00526   {
00527     if (val)
00528       SetBit(pos);
00529     else
00530       ClearBit(pos);
00531   }
00532 
00534   bool IsBitSet (size_t pos) const
00535   {
00536     CS_ASSERT (pos < mNumBits);
00537     return (GetStore()[GetIndex(pos)] 
00538       & (((csBitArrayStorageType)1) << GetOffset(pos))) != 0;
00539   }
00540 
00547   bool IsBitSetTolerant (size_t pos) const
00548   {
00549     if (pos >= mNumBits) return false;
00550     return (GetStore()[GetIndex(pos)] 
00551       & (((csBitArrayStorageType)1) << GetOffset(pos))) != 0;
00552   }
00553   
00555   bool AreSomeBitsSet (size_t pos, size_t count) const
00556   {
00557     CS_ASSERT (pos + count <= mNumBits);
00558     csBitArrayStorageType const* p = GetStore();
00559     while (count > 0)
00560     {
00561       size_t index = GetIndex (pos);
00562       size_t offset = GetOffset (pos);
00563       size_t checkCount = MIN(count, cellSize - offset);
00564       csBitArrayStorageType mask = ((checkCount == cellSize) 
00565         ? ~(csBitArrayStorageType)0 
00566         : ((((csBitArrayStorageType)1) << checkCount) - 1)) << offset;
00567       if (p[index] & mask)
00568         return true;
00569       pos += checkCount;
00570       count -= checkCount;
00571     }
00572     return false;
00573   }
00574   
00576   bool AllBitsFalse() const
00577   {
00578     csBitArrayStorageType const* p = GetStore();
00579     for (size_t i = 0; i < mLength; i++)
00580       if (p[i] != 0)
00581         return false;
00582     return true;
00583   }
00584 
00586   csBitArrayTweakable& FlipAllBits()
00587   {
00588     csBitArrayStorageType* p = GetStore();
00589     for (size_t i = 0; i < mLength; i++)
00590       p[i] = ~p[i];
00591     Trim();
00592     return *this;
00593   }
00594   
00596   size_t NumBitsSet() const
00597   {
00598     const size_t ui32perStorage = 
00599       sizeof (csBitArrayStorageType) / sizeof (uint32);
00600 
00601     union
00602     {
00603       csBitArrayStorageType s;
00604       uint32 ui32[ui32perStorage];
00605     } v;
00606 
00607     const csBitArrayStorageType* p = GetStore();
00608     size_t num = 0;
00609     for (size_t i = 0; i < mLength; i++)
00610     {
00611       v.s = p[i];
00612       for (size_t j = 0; j < ui32perStorage; j++)
00613         num += CS::Utility::BitOps::ComputeBitsSet (v.ui32[j]);
00614     }
00615 
00616     return num;
00617   }
00618   
00623   size_t GetFirstBitSet() const
00624   {
00625     const size_t ui32perStorage = 
00626       sizeof (csBitArrayStorageType) / sizeof (uint32);
00627 
00628     union
00629     {
00630       csBitArrayStorageType s;
00631       uint32 ui32[ui32perStorage];
00632     } v;
00633 
00634     const csBitArrayStorageType* p = GetStore();
00635     size_t ofs = 0, result;
00636     for (size_t i = 0; i < mLength; i++)
00637     {
00638       v.s = p[i];
00639       for (size_t j = 0; j < ui32perStorage; j++)
00640       {
00641         if (CS::Utility::BitOps::ScanBitForward (v.ui32[j], result))
00642         {
00643           size_t r = ofs + result;
00644           if (r >= mNumBits) return csArrayItemNotFound;
00645           return r;
00646         }
00647         ofs += 32;
00648       }
00649     }
00650     return csArrayItemNotFound;
00651   }
00656   size_t GetFirstBitUnset() const
00657   {
00658     const size_t ui32perStorage = 
00659       sizeof (csBitArrayStorageType) / sizeof (uint32);
00660 
00661     union
00662     {
00663       csBitArrayStorageType s;
00664       uint32 ui32[ui32perStorage];
00665     } v;
00666 
00667     const csBitArrayStorageType* p = GetStore();
00668     size_t ofs = 0;
00669     unsigned long result;
00670     for (size_t i = 0; i < mLength; i++)
00671     {
00672       v.s = p[i];
00673       for (size_t j = 0; j < ui32perStorage; j++)
00674       {
00675         if (CS::Utility::BitOps::ScanBitForward (~v.ui32[j], result))
00676         {
00677           size_t r = ofs + result;
00678           if (r >= mNumBits) return csArrayItemNotFound;
00679           return r;
00680         }
00681         ofs += 32;
00682       }
00683     }
00684     return csArrayItemNotFound;
00685   }
00690   size_t GetLastBitSet() const
00691   {
00692     const size_t ui32perStorage = 
00693       sizeof (csBitArrayStorageType) / sizeof (uint32);
00694 
00695     union
00696     {
00697       csBitArrayStorageType s;
00698       uint32 ui32[ui32perStorage];
00699     } v;
00700 
00701     const csBitArrayStorageType* p = GetStore();
00702     size_t ofs, result;
00703     ofs = 32 * (mLength*ui32perStorage-1);
00704     for (size_t i = mLength; i-- > 0;)
00705     {
00706       v.s = p[i];
00707       for (size_t j = ui32perStorage; j-- > 0; )
00708       {
00709         if (CS::Utility::BitOps::ScanBitForward (v.ui32[j], result))
00710         {
00711           size_t r = ofs + result;
00712           if (r >= mNumBits) return csArrayItemNotFound;
00713           return r;
00714         }
00715         ofs -= 32;
00716       }
00717     }
00718     return csArrayItemNotFound;
00719   }
00724   size_t GetLastBitUnset() const
00725   {
00726     const size_t ui32perStorage = 
00727       sizeof (csBitArrayStorageType) / sizeof (uint32);
00728 
00729     union
00730     {
00731       csBitArrayStorageType s;
00732       uint32 ui32[ui32perStorage];
00733     } v;
00734 
00735     const csBitArrayStorageType* p = GetStore();
00736     size_t ofs, result;
00737     ofs = 32 * (mLength*ui32perStorage-1);
00738     for (size_t i = mLength; i-- > 0;)
00739     {
00740       v.s = p[i];
00741       for (size_t j = ui32perStorage; j-- > 0; )
00742       {
00743         if (CS::Utility::BitOps::ScanBitForward (~v.ui32[j], result))
00744         {
00745           size_t r = ofs + result;
00746           if (r >= mNumBits) return csArrayItemNotFound;
00747           return r;
00748         }
00749         ofs -= 32;
00750       }
00751     }
00752     return csArrayItemNotFound;
00753   }
00754 
00759   void Delete(size_t pos, size_t count)
00760   {
00761     if (count > 0)
00762     {
00763       size_t dst = pos;
00764       size_t src = pos + count;
00765       CS_ASSERT(src <= mNumBits);
00766       size_t ntail = mNumBits - src;
00767       while (ntail-- > 0)
00768         Set(dst++, IsBitSet(src++));
00769       SetSize(mNumBits - count);
00770     }
00771   }
00772 
00777   csBitArrayTweakable Slice(size_t pos, size_t count) const
00778   {
00779     CS_ASSERT(pos + count <= mNumBits);
00780     csBitArrayTweakable a (count);
00781     for (size_t i = pos, o = 0; i < pos + count; i++)
00782       if (IsBitSet(i))
00783         a.SetBit(o++);
00784     return a;
00785   }
00786 
00788 
00789   csBitArrayStorageType* GetArrayBits() { return GetStore(); }
00790   const csBitArrayStorageType* GetArrayBits() const { return GetStore(); }
00792 
00794 
00797   class SetBitIterator
00798   {
00799   public:
00800     SetBitIterator (const SetBitIterator& other)
00801       : bitArray (other.bitArray), pos (other.pos), offset (other.offset),
00802       cachedStore (other.cachedStore)
00803     {}
00804 
00806     size_t Next ()
00807     {
00808       while (offset < 8*sizeof(csBitArrayStorageType))
00809       {        
00810         if ((cachedStore & 0x1) != 0)
00811         {
00812           const size_t result = (pos-1)*sizeof(csBitArrayStorageType)*8 + offset;
00813 
00814           ++offset;
00815           cachedStore >>= 1;
00816           if (!cachedStore)
00817             GetNextCacheItem ();
00818 
00819           return result;
00820         }        
00821         else
00822         {
00823           ++offset;
00824           cachedStore >>= 1;
00825           if (!cachedStore)
00826             GetNextCacheItem ();
00827         }
00828       }
00829       CS_ASSERT_MSG ("Invalid iteration", false);
00830       return 0;
00831     }
00832 
00834     bool HasNext () const
00835     {
00836       return cachedStore != 0;
00837     }
00838 
00840     void Reset ()
00841     {
00842       pos = 0;
00843       GetNextCacheItem ();
00844     }
00845 
00846   protected:
00847     SetBitIterator (const ThisType& bitArray)
00848       : bitArray (bitArray), pos (0), offset (0), cachedStore (0)
00849     {
00850       Reset ();
00851     }
00852 
00853     friend class csBitArrayTweakable<InlinedBits, Allocator>;
00854 
00855     void GetNextCacheItem ()
00856     {
00857       offset = 0;
00858       while (pos < bitArray.mLength)
00859       {
00860         cachedStore = bitArray.GetStore ()[pos++];
00861         if (cachedStore)
00862           return;
00863       }
00864       cachedStore = 0;
00865     }
00866 
00867     const ThisType& bitArray;
00868     size_t pos, offset;
00869     csBitArrayStorageType cachedStore;    
00870   };
00871   friend class SetBitIterator;
00872 
00873   SetBitIterator GetSetBitIterator () const
00874   {
00875     return SetBitIterator (*this);
00876   }
00878   
00887   uint8* Serialize (size_t& numBytes) const
00888   {
00889     if (mNumBits == 0)
00890     {
00891       numBytes = 0;
00892       return 0;
00893     }
00894   
00895     struct SerializeHelper
00896     {
00897       uint8* buf;
00898       size_t bufSize, bufUsed;
00899       
00900       SerializeHelper () : buf (0), bufSize (0), bufUsed (0) {}
00901       void PushByte (uint8 b)
00902       {
00903         if (bufUsed >= bufSize)
00904         {
00905           bufSize += 4;
00906           buf = (uint8*)cs_realloc (buf, bufSize);
00907         }
00908         buf[bufUsed++] = b;
00909       }
00910       void TruncZeroes ()
00911       {
00912         while ((bufUsed > 0) && (buf[bufUsed-1] == 0))
00913           bufUsed--;
00914       }
00915     } serHelper;
00916     
00917     // Write out bits number
00918     {
00919       size_t remainder = mNumBits;
00920       
00921       while (remainder >= 128)
00922       {
00923         uint8 b = (remainder & 0x7f) | 0x80;
00924         serHelper.PushByte (b);
00925         remainder >>= 7;
00926       }
00927       serHelper.PushByte (uint8 (remainder));
00928     }
00929   
00930     const size_t ui8Count = sizeof (csBitArrayStorageType) / sizeof (uint8);
00931     uint8 ui8[ui8Count];
00932     csBitArrayStorageType const* p = GetStore();
00933     for (size_t i = 0; i < mLength; i++)
00934     {
00935       memcpy (ui8, &p[i], sizeof (ui8));
00936 #ifdef CS_LITTLE_ENDIAN
00937       for (size_t j = 0; j < ui8Count; j++)
00938 #else
00939       for (size_t j = ui8Count; j-- > 0; )
00940 #endif
00941       {
00942         serHelper.PushByte (ui8[j]);
00943       }
00944     }
00945     
00946     serHelper.TruncZeroes();
00947     numBytes = serHelper.bufUsed;
00948     return serHelper.buf;
00949   }
00954   static ThisType Unserialize (uint8* bytes, size_t numBytes)
00955   {
00956     if ((bytes == 0) || (numBytes == 0))
00957       return ThisType(); // empty bit array
00958   
00959     size_t bufPos = 0;
00960   
00961     // Read the bits number
00962     size_t numBits = 0;
00963     int shift = 0;
00964     while (bufPos < numBytes)
00965     {
00966       uint8 b = bytes[bufPos++];
00967       numBits |= (b & 0x7f) << shift;
00968       if ((b & 0x80) == 0) break;
00969       shift += 7;
00970     }
00971     
00972     ThisType newArray (numBits);
00973     
00974     // Read the actual bits
00975     csBitArrayStorageType* p = newArray.GetStore();
00976     size_t storeIndex = 0;
00977     while (bufPos < numBytes)
00978     {
00979       const size_t ui8Count = sizeof (csBitArrayStorageType) / sizeof (uint8);
00980       uint8 ui8[ui8Count];
00981       memset (ui8, 0, sizeof (ui8));
00982 #ifdef CS_LITTLE_ENDIAN
00983       for (size_t j = 0; j < ui8Count; j++)
00984 #else
00985       for (size_t j = ui8Count; j-- > 0; )
00986 #endif
00987       {
00988         ui8[j] = bytes[bufPos++];
00989         if (bufPos >= numBytes) break;
00990       }
00991       memcpy (p + (storeIndex++), ui8, sizeof (ui8));
00992     }
00993     
00994     return newArray;
00995   }
00997 };
00998 
01003 class csBitArray : public csBitArrayTweakable<>
01004 {
01005 public:
01007   csBitArray () { }
01009   explicit csBitArray (size_t size) : csBitArrayTweakable<> (size) { }
01011   csBitArray (const csBitArray& that) : csBitArrayTweakable<> (that) { }
01012 
01014   template<int A, typename B>
01015   csBitArray& operator=(const csBitArrayTweakable<A, B>& that)
01016   {
01017     if (this != &that)
01018     {
01019       SetSize (that.GetSize());
01020       memcpy (GetStore(), that.GetArrayBits(), 
01021         mLength * sizeof (csBitArrayStorageType));
01022     }
01023     return *this;
01024   }
01025 
01026 };
01027 
01028 
01033 template<>
01034 class csComparator<csBitArray, csBitArray> : 
01035   public csComparatorBitArray<csBitArray> { };
01036 
01037 
01042 template<>
01043 class csHashComputer<csBitArray> : 
01044   public csHashComputerBitArray<csBitArray> { };
01045 
01046 
01047 #endif // __CS_BITARRAY_H__

Generated for Crystal Space 2.0 by doxygen 1.7.6.1