## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# 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 "comparator.h"
    00035 #include "hash.h"
    00036
    00037 class csBitArray;
    00038 CS_SPECIALIZE_TEMPLATE class csComparator<csBitArray, csBitArray>;
    00039 CS_SPECIALIZE_TEMPLATE class csHashComputer<csBitArray>;
    00040
    00044 class CS_CRYSTALSPACE_EXPORT csBitArray
    00045 {
    00046 public:
    00047   typedef unsigned long store_type;
    00048
    00049 private:
    00050   friend class csComparator<csBitArray, csBitArray>;
    00051   friend class csHashComputer<csBitArray>;
    00052   enum
    00053   {
    00054     bits_per_byte = 8,
    00055     cell_size     = sizeof(store_type) * bits_per_byte
    00056   };
    00057
    00058   store_type* mpStore;
    00059   store_type  mSingleWord; // Use this buffer when mLength is 1
    00060   size_t mLength;          // Length of mpStore in units of store_type
    00061   size_t mNumBits;
    00062
    00064   static size_t GetIndex (size_t bit_num)
    00065   {
    00066     return bit_num / cell_size;
    00067   }
    00068
    00070   static size_t GetOffset (size_t bit_num)
    00071   {
    00072     return bit_num % cell_size;
    00073   }
    00074
    00079   store_type const* GetStore() const
    00080   {
    00081     return mLength <= 1 ? &mSingleWord : mpStore;
    00082   }
    00083
    00088   store_type* GetStore()
    00089   {
    00090     return mLength <= 1 ? &mSingleWord : mpStore;
    00091   }
    00092
    00094   void Trim()
    00095   {
    00096     size_t extra_bits = mNumBits % cell_size;
    00097     if (mLength > 0 && extra_bits != 0)
    00098       GetStore()[mLength - 1] &= ~((~(store_type)0) << extra_bits);
    00099   }
    00100
    00101 public:
    00105   class CS_CRYSTALSPACE_EXPORT BitProxy
    00106   {
    00107   private:
    00108     csBitArray &mArray;
    00109     size_t mPos;
    00110   public:
    00112     BitProxy(csBitArray &array, size_t pos): mArray(array), mPos(pos)
    00113     {}
    00114
    00116     BitProxy &operator= (bool value)
    00117     {
    00118       mArray.Set (mPos, value);
    00119       return *this;
    00120     }
    00121
    00123     BitProxy &operator= (const BitProxy &that)
    00124     {
    00125       mArray.Set (mPos, that.mArray.IsBitSet (that.mPos));
    00126       return *this;
    00127     }
    00128
    00130     operator bool() const
    00131     {
    00132       return mArray.IsBitSet (mPos);
    00133     }
    00134
    00139     bool Flip()
    00140     {
    00141       mArray.FlipBit (mPos);
    00142       return mArray.IsBitSet (mPos);
    00143     }
    00144   };
    00145   friend class BitProxy;
    00146
    00150   csBitArray () : mpStore(0), mSingleWord(0), mLength(0), mNumBits(0)
    00151   {
    00152     SetSize (0);
    00153   }
    00154
    00158   explicit csBitArray(size_t size) :
    00159     mpStore(0), mSingleWord(0), mLength(0), mNumBits(0)
    00160   {
    00161     SetSize (size);
    00162   }
    00163
    00167   csBitArray (const csBitArray &that) :
    00168     mpStore(0), mSingleWord(0), mLength(0), mNumBits(0)
    00169   {
    00170     *this = that; // Invokes this->operator=().
    00171   }
    00172
    00174   ~csBitArray()
    00175   {
    00176     if (mpStore != 0)
    00177       delete[] mpStore;
    00178   }
    00179
    00181   size_t GetSize() const
    00182   {
    00183     return mNumBits;
    00184   }
    00185
    00190   size_t Length () const
    00191   {
    00192     return GetSize();
    00193   }
    00194
    00199   void SetLength (size_t newSize)
    00200   {
    00201     SetSize (newSize);
    00202   }
    00203
    00209   void SetSize (size_t newSize)
    00210   {
    00211     size_t newLength;
    00212     if (newSize == 0)
    00213       newLength = 0;
    00214     else
    00215       newLength = 1 + GetIndex (newSize - 1);
    00216
    00217     if (newLength != mLength)
    00218     {
    00219       // Avoid allocation if length is 1 (common case)
    00220       store_type* newStore;
    00221       if (newLength <= 1)
    00222         newStore = &mSingleWord;
    00223       else
    00224         newStore = new store_type[newLength];
    00225
    00226       if (newLength > 0)
    00227       {
    00228         if (mLength > 0)
    00229         {
    00230           store_type const* oldStore = GetStore();
    00231           if (newStore != oldStore)
    00232           {
    00233             memcpy (newStore, oldStore,
    00234               (MIN (mLength, newLength)) * sizeof (store_type));
    00235             if (newLength > mLength)
    00236               memset(newStore + mLength, 0,
    00237                      (newLength - mLength) * sizeof (store_type));
    00238           }
    00239         }
    00240         else
    00241           memset (newStore, 0, newLength * sizeof (store_type));
    00242       }
    00243
    00244       if (mpStore != 0)
    00245         delete[] mpStore;
    00246
    00247       mpStore = newLength > 1 ? newStore : 0;
    00248       mLength = newLength;
    00249     }
    00250
    00251     mNumBits = newSize;
    00252     Trim();
    00253   }
    00254
    00255   //
    00256   // Operators
    00257   //
    00258
    00260   csBitArray &operator=(const csBitArray &that)
    00261   {
    00262     if (this != &that)
    00263     {
    00264       SetSize (that.mNumBits);
    00265       memcpy (GetStore(), that.GetStore(), mLength * sizeof(store_type));
    00266     }
    00267     return *this;
    00268   }
    00269
    00271   BitProxy operator[] (size_t pos)
    00272   {
    00273     CS_ASSERT (pos < mNumBits);
    00274     return BitProxy(*this, pos);
    00275   }
    00276
    00278   bool operator[] (size_t pos) const
    00279   {
    00280     return IsBitSet(pos);
    00281   }
    00282
    00284   bool operator==(const csBitArray &that) const
    00285   {
    00286     if (mNumBits != that.mNumBits)
    00287       return false;
    00288
    00289     store_type const* p0 = GetStore();
    00290     store_type const* p1 = that.GetStore();
    00291     for (unsigned i = 0; i < mLength; i++)
    00292       if (p0[i] != p1[i])
    00293         return false;
    00294     return true;
    00295   }
    00296
    00298   bool operator != (const csBitArray &that) const
    00299   {
    00300     return !(*this == that);
    00301   }
    00302
    00304   csBitArray& operator &= (const csBitArray &that)
    00305   {
    00306     CS_ASSERT (mNumBits == that.mNumBits);
    00307     store_type* p0 = GetStore();
    00308     store_type const* p1 = that.GetStore();
    00309     for (size_t i = 0; i < mLength; i++)
    00310       p0[i] &= p1[i];
    00311     return *this;
    00312   }
    00313
    00315   csBitArray operator |= (const csBitArray &that)
    00316   {
    00317     CS_ASSERT (mNumBits == that.mNumBits);
    00318     store_type* p0 = GetStore();
    00319     store_type const* p1 = that.GetStore();
    00320     for (size_t i = 0; i < mLength; i++)
    00321       p0[i] |= p1[i];
    00322     return *this;
    00323   }
    00324
    00326   csBitArray operator ^= (const csBitArray &that)
    00327   {
    00328     CS_ASSERT (mNumBits == that.mNumBits);
    00329     store_type* p0 = GetStore();
    00330     store_type const* p1 = that.GetStore();
    00331     for (size_t i = 0; i < mLength; i++)
    00332       p0[i] ^= p1[i];
    00333     return *this;
    00334   }
    00335
    00337   csBitArray operator~() const
    00338   {
    00339     return csBitArray(*this).FlipAllBits();
    00340   }
    00341
    00343   friend csBitArray operator& (const csBitArray &a1, const csBitArray &a2)
    00344   {
    00345     return csBitArray(a1) &= a2;
    00346   }
    00347
    00349   friend csBitArray operator | (const csBitArray &a1, const csBitArray &a2)
    00350   {
    00351     return csBitArray(a1) |= a2;
    00352   }
    00353
    00355   friend csBitArray operator ^ (const csBitArray &a1, const csBitArray &a2)
    00356   {
    00357     return csBitArray(a1) ^= a2;
    00358   }
    00359
    00360   //
    00361   // Plain English interface
    00362   //
    00363
    00365   void Clear()
    00366   {
    00367     memset (GetStore(), 0, mLength * sizeof(store_type));
    00368   }
    00369
    00371   void SetBit (size_t pos)
    00372   {
    00373     CS_ASSERT (pos < mNumBits);
    00374     GetStore()[GetIndex(pos)] |= ((store_type)1) << GetOffset(pos);
    00375   }
    00376
    00378   void ClearBit (size_t pos)
    00379   {
    00380     CS_ASSERT (pos < mNumBits);
    00381     GetStore()[GetIndex(pos)] &= ~(((store_type)1) << GetOffset(pos));
    00382   }
    00383
    00385   void FlipBit (size_t pos)
    00386   {
    00387     CS_ASSERT (pos < mNumBits);
    00388     GetStore()[GetIndex(pos)] ^= ((store_type)1) << GetOffset(pos);
    00389   }
    00390
    00392   void Set (size_t pos, bool val = true)
    00393   {
    00394     if (val)
    00395       SetBit(pos);
    00396     else
    00397       ClearBit(pos);
    00398   }
    00399
    00401   bool IsBitSet (size_t pos) const
    00402   {
    00403     CS_ASSERT (pos < mNumBits);
    00404     return (GetStore()[GetIndex(pos)] & (((store_type)1) << GetOffset(pos)))
    00405       != 0;
    00406   }
    00407
    00409   bool AreSomeBitsSet (size_t pos, size_t count) const
    00410   {
    00411     CS_ASSERT (pos + count <= mNumBits);
    00412     store_type const* p = GetStore();
    00413     while (count > 0)
    00414     {
    00415       size_t index = GetIndex (pos);
    00416       size_t offset = GetOffset (pos);
    00417       size_t checkCount = MIN(count, cell_size - offset);
    00418       store_type mask = ((checkCount == cell_size) ? ~(store_type)0 :
    00419                          ((((store_type)1) << checkCount) - 1)) << offset;
    00420       if (p[index] & mask)
    00421         return true;
    00422       pos += checkCount;
    00423       count -= checkCount;
    00424     }
    00425     return false;
    00426   }
    00427
    00429   bool AllBitsFalse() const
    00430   {
    00431     store_type const* p = GetStore();
    00432     for (size_t i = 0; i < mLength; i++)
    00433       if (p[i] != 0)
    00434         return false;
    00435     return true;
    00436   }
    00437
    00439   csBitArray &FlipAllBits()
    00440   {
    00441     store_type* p = GetStore();
    00442     for (size_t i = 0; i < mLength; i++)
    00443       p[i] = ~p[i];
    00444     Trim();
    00445     return *this;
    00446   }
    00447
    00452   void Delete(size_t pos, size_t count)
    00453   {
    00454     if (count > 0)
    00455     {
    00456       size_t dst = pos;
    00457       size_t src = pos + count;
    00458       CS_ASSERT(src <= mNumBits);
    00459       size_t ntail = mNumBits - src;
    00460       while (ntail-- > 0)
    00461         Set(dst++, IsBitSet(src++));
    00462       SetSize(mNumBits - count);
    00463     }
    00464   }
    00465
    00470   csBitArray Slice(size_t pos, size_t count) const
    00471   {
    00472     CS_ASSERT(pos + count <= mNumBits);
    00473     csBitArray a(count);
    00474     for (size_t i = pos, o = 0; i < pos + count; i++)
    00475       if (IsBitSet(i))
    00476         a.SetBit(o++);
    00477     return a;
    00478   }
    00479
    00481   store_type* GetArrayBits()
    00482   {
    00483     return GetStore();
    00484   }
    00485
    00490   store_type GetSingleWord()
    00491   {
    00492     CS_ASSERT(mpStore == 0);
    00493     return mSingleWord;
    00494   }
    00495
    00500   void SetSingleWord (store_type sw)
    00501   {
    00502     CS_ASSERT(mpStore == 0);
    00503     mSingleWord = sw;
    00504   }
    00505 };
    00506
    00511 CS_SPECIALIZE_TEMPLATE
    00512 class csComparator<csBitArray, csBitArray>
    00513 {
    00514 public:
    00515   static int Compare (csBitArray const& key1, csBitArray const& key2)
    00516   {
    00517     csBitArray::store_type const* p0 = key1.GetStore();
    00518     csBitArray::store_type const* p1 = key2.GetStore();
    00519     size_t compareNum = MIN (key1.mLength, key2.mLength);
    00520     size_t i = 0;
    00521     for (; i < compareNum; i++)
    00522       if (p0[i] != p1[i])
    00523         return (int)p0[i] - (int)p1[i];
    00524     if (key1.mLength > key2.mLength)
    00525     {
    00526       for (; i < key1.mLength; i++)
    00527         if (p0[i] != 0)
    00528           return (int)p0[i];
    00529     }
    00530     else
    00531     {
    00532       for (; i < key2.mLength; i++)
    00533         if (p1[i] != 0)
    00534           return -((int)p1[i]);
    00535     }
    00536     return 0;
    00537   }
    00538 };
    00539
    00544 CS_SPECIALIZE_TEMPLATE
    00545 class csHashComputer<csBitArray>
    00546 {
    00547 public:
    00548   static uint ComputeHash (csBitArray const& key)
    00549   {
    00550     const size_t uintCount = sizeof (csBitArray::store_type) / sizeof (uint);
    00551     union
    00552     {
    00553       csBitArray::store_type store;
    00554       uint ui[uintCount];
    00555     } bitStoreToUint;
    00556     uint hash = 0;
    00557     csBitArray::store_type const* p = key.GetStore();
    00558     // @@@ Not very good. Find a better hash function; however, it should
    00559     // return the same hash for two bit arrays that are the same except for
    00560     // the amount of trailing zeros. (e.g. f(10010110) == f(100101100000...))
    00561     for (size_t i = 0; i < key.mLength; i++)
    00562     {
    00563       bitStoreToUint.store = p[i];
    00564       for (size_t j = 0; j < uintCount; j++)
    00565         hash += bitStoreToUint.ui[j];
    00566     }
    00567     return hash;
    00568   }
    00569 };
    00570
    00571
    00572 #endif // __CS_BITARRAY_H__