00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef __CS_BITARRAY_H__
00027 #define __CS_BITARRAY_H__
00028
00029 #include <memory.h>
00030
00032 class csBitArray
00033 {
00034 private:
00035 typedef unsigned long store_type;
00036 enum
00037 {
00038 bits_per_byte = 8,
00039 cell_size = sizeof(store_type) * bits_per_byte
00040 };
00041
00042 store_type *mpStore;
00043 store_type mSingleWord;
00044 unsigned mLength;
00045 unsigned mNumBits;
00046
00048 static unsigned GetIndex(unsigned bit_num)
00049 {
00050 return bit_num / cell_size;
00051 }
00052
00053 static unsigned GetOffset(unsigned bit_num)
00054 {
00055 return bit_num % cell_size;
00056 }
00057
00058 void Init(unsigned size)
00059 {
00060 mNumBits = size;
00061
00062 if (size == 0)
00063 mLength = 0;
00064 else
00065 mLength = 1 + GetIndex(size - 1);
00066
00067
00068 if (mLength <= 1)
00069 mpStore = &mSingleWord;
00070 else
00071 mpStore = new store_type[mLength];
00072 }
00073
00075 inline void Trim()
00076 {
00077 unsigned extra_bits = mNumBits % cell_size;
00078 if (mLength > 0 && extra_bits != 0)
00079 mpStore[mLength - 1] &= ~((~(store_type) 0) << extra_bits);
00080 }
00081
00082 public:
00086 class BitProxy
00087 {
00088 private:
00089 csBitArray &mArray;
00090 unsigned mPos;
00091 public:
00092 BitProxy(csBitArray &array, unsigned pos): mArray(array), mPos(pos)
00093 {}
00094
00095 BitProxy &operator= (bool value)
00096 {
00097 mArray.Set(mPos, value);
00098 return *this;
00099 }
00100
00101 BitProxy &operator= (const BitProxy &that)
00102 {
00103 mArray.Set(mPos, that.mArray.IsBitSet(that.mPos));
00104 return *this;
00105 }
00106
00107 operator bool() const
00108 {
00109 return mArray.IsBitSet(mPos);
00110 }
00111
00112 bool Flip()
00113 {
00114 mArray.FlipBit(mPos);
00115 return mArray.IsBitSet(mPos);
00116 }
00117 };
00118
00119
00120 friend class BitProxy;
00121
00122
00123
00124
00125
00127 explicit csBitArray(unsigned size)
00128 {
00129 Init(size);
00130
00131 Trim();
00132 }
00133
00135 csBitArray(const csBitArray &that)
00136 {
00137 mpStore = 0;
00138 *this = that;
00139 }
00140
00142 virtual ~csBitArray()
00143 {
00144 if (mLength > 1)
00145 delete mpStore;
00146 }
00147
00148
00149
00150
00151
00153 csBitArray &operator=(const csBitArray &that)
00154 {
00155 if (this != &that)
00156 {
00157 if (mLength > 1)
00158 delete mpStore;
00159
00160 Init(that.mNumBits);
00161
00162 memcpy (mpStore, that.mpStore, mLength * sizeof(store_type));
00163 }
00164 return *this;
00165 }
00166
00168 BitProxy operator[](unsigned pos)
00169 {
00170 CS_ASSERT (pos < mNumBits);
00171 return BitProxy(*this, pos);
00172 }
00173
00175 const BitProxy operator[](unsigned pos) const
00176 {
00177 CS_ASSERT (pos < mNumBits);
00178 return BitProxy(CONST_CAST(csBitArray&,*this), pos);
00179 }
00180
00182 bool operator==(const csBitArray &that) const
00183 {
00184 if (mNumBits != that.mNumBits)
00185 return false;
00186
00187 for (unsigned i = 0; i < mLength; i++)
00188 if (mpStore[i] != that.mpStore[i])
00189 return false;
00190 return true;
00191 }
00192
00194 bool operator!=(const csBitArray &that) const
00195 {
00196 return !(*this == that);
00197 }
00198
00200 csBitArray &operator&=(const csBitArray &that)
00201 {
00202 CS_ASSERT (mNumBits == that.mNumBits);
00203 for (unsigned i = 0; i < mLength; i++)
00204 mpStore[i] &= that.mpStore[i];
00205 return *this;
00206 }
00207
00209 csBitArray operator|=(const csBitArray &that)
00210 {
00211 CS_ASSERT (mNumBits == that.mNumBits);
00212 for (unsigned i = 0; i < mLength; i++)
00213 mpStore[i] |= that.mpStore[i];
00214 return *this;
00215 }
00216
00218 csBitArray operator^=(const csBitArray &that)
00219 {
00220 CS_ASSERT (mNumBits == that.mNumBits);
00221 for (unsigned i = 0; i < mLength; i++)
00222 mpStore[i] ^= that.mpStore[i];
00223 return *this;
00224 }
00225
00227 csBitArray operator~() const
00228 {
00229 return csBitArray(*this).FlipAllBits();
00230 }
00231
00233 friend csBitArray operator&(const csBitArray &a1, const csBitArray &a2)
00234 {
00235 return csBitArray(a1) &= a2;
00236 }
00237
00239 friend csBitArray operator|(const csBitArray &a1, const csBitArray &a2)
00240 {
00241 return csBitArray(a1) |= a2;
00242 }
00243
00245 friend csBitArray operator^(const csBitArray &a1, const csBitArray &a2)
00246 {
00247 return csBitArray(a1) ^= a2;
00248 }
00249
00250
00251
00252
00253
00255 void Clear()
00256 {
00257 memset (mpStore, 0, mLength * sizeof(store_type));
00258 }
00259
00261 void SetBit(unsigned pos)
00262 {
00263 CS_ASSERT (pos < mNumBits);
00264 mpStore[GetIndex(pos)] |= 1 << GetOffset(pos);
00265 }
00266
00268 void ClearBit(unsigned pos)
00269 {
00270 CS_ASSERT (pos < mNumBits);
00271 mpStore[GetIndex(pos)] &= ~(1 << GetOffset(pos));
00272 }
00273
00275 void FlipBit(unsigned pos)
00276 {
00277 CS_ASSERT (pos < mNumBits);
00278 mpStore[GetIndex(pos)] ^= 1 << GetOffset(pos);
00279 }
00280
00282 void Set(unsigned pos, bool val)
00283 {
00284 val ? SetBit(pos) : ClearBit(pos);
00285 }
00286
00288 bool IsBitSet(unsigned pos) const
00289 {
00290 CS_ASSERT (pos < mNumBits);
00291 return (mpStore[GetIndex(pos)] & (1 << GetOffset(pos))) != 0;
00292 }
00293
00295 bool AllBitsFalse() const
00296 {
00297 for (unsigned i=0; i < mLength; i++)
00298 if (mpStore[i] != 0)
00299 return false;
00300 return true;
00301 }
00302
00304 csBitArray &FlipAllBits()
00305 {
00306 for (unsigned i=0; i < mLength; i++)
00307 mpStore[i] = ~mpStore[i];
00308
00309 Trim();
00310 return *this;
00311 }
00312
00314 store_type* GetArrayBits()
00315 {
00316 return mpStore;
00317 }
00318
00323 unsigned GetSingleWord()
00324 {
00325 return mSingleWord;
00326 }
00327
00332 void SetSingleWord(unsigned w)
00333 {
00334 mSingleWord=w;
00335 }
00336 };
00337
00338 #endif // __CS_BITARRAY_H__