nel/src/misc/bit_set.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU Affero General Public License as
   6 // published by the Free Software Foundation, either version 3 of the
   7 // License, or (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU Affero General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU Affero General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "stdmisc.h"
  18
  19 #include "nel/misc/bit_set.h"
  20
  21 using namespace std;
  22
  23 #ifdef DEBUG_NEW
  24         #define new DEBUG_NEW
  25 #endif
  26
  27 namespace       NLMISC
  28 {
  29
  30 // must be defined elsewhere
  31 #ifndef min
  32 #define min(a,b)            (((a) < (b)) ? (a) : (b))
  33 #endif
  34
  35
  36
  37 // ***************************************************************************
  38 CBitSet::CBitSet()
  39 {
  40         /* ***********************************************
  41          *      WARNING: This Class/Method must be thread-safe (ctor/dtor/serial): no static access for instance
  42          *      It can be loaded/called through CAsyncFileManager for instance
  43          * ***********************************************/
  44         NumBits= 0;
  45         MaskLast= 0;
  46 }
  47 CBitSet::CBitSet(uint numBits)
  48 {
  49         /* ***********************************************
  50          *      WARNING: This Class/Method must be thread-safe (ctor/dtor/serial): no static access for instance
  51          *      It can be loaded/called through CAsyncFileManager for instance
  52          * ***********************************************/
  53         NumBits= 0;
  54         MaskLast= 0;
  55         resize(numBits);
  56 }
  57 CBitSet::CBitSet(const CBitSet &bs)
  58 {
  59         /* ***********************************************
  60          *      WARNING: This Class/Method must be thread-safe (ctor/dtor/serial): no static access for instance
  61          *      It can be loaded/called through CAsyncFileManager for instance
  62          * ***********************************************/
  63         NumBits= bs.NumBits;
  64         MaskLast= bs.MaskLast;
  65         Array= bs.Array;
  66 }
  67 CBitSet::~CBitSet()
  68 {
  69         /* ***********************************************
  70          *      WARNING: This Class/Method must be thread-safe (ctor/dtor/serial): no static access for instance
  71          *      It can be loaded/called through CAsyncFileManager for instance
  72          * ***********************************************/
  73 }
  74 CBitSet &CBitSet::operator=(const CBitSet &bs)
  75 {
  76         NumBits= bs.NumBits;
  77         MaskLast= bs.MaskLast;
  78         Array= bs.Array;
  79
  80         return *this;
  81 }
  82
  83
  84 // ***************************************************************************
  85 void    CBitSet::clear()
  86 {
  87         Array.clear();
  88         NumBits= 0;
  89         MaskLast=0;
  90 }
  91 void    CBitSet::resize(uint numBits)
  92 {
  93         if(numBits==0)
  94                 clear();
  95
  96         NumBits= numBits;
  97         Array.resize( (NumBits+NL_BITLEN-1) / NL_BITLEN );
  98         uint    nLastBits= NumBits & (NL_BITLEN-1) ;
  99         // Generate the mask for the last word.
 100         if(nLastBits==0)
 101                 MaskLast= ~((uint)0);
 102         else
 103                 MaskLast= (1<< nLastBits) -1;
 104
 105         // reset to 0.
 106         clearAll();
 107 }
 108 void    CBitSet::resizeNoReset(uint numBits, bool value)
 109 {
 110         if(numBits==0)
 111                 clear();
 112
 113         uint oldNum=NumBits;
 114         NumBits= numBits;
 115         Array.resize( (NumBits+NL_BITLEN-1) / NL_BITLEN );
 116         uint    nLastBits= NumBits & (NL_BITLEN-1) ;
 117         // Generate the mask for the last word.
 118         if(nLastBits==0)
 119                 MaskLast= ~((uint)0);
 120         else
 121                 MaskLast= (1<< nLastBits) -1;
 122
 123         // Set new bit to value
 124         for (uint i=oldNum; i<(uint)NumBits; i++)
 125                 set(i, value);
 126 }
 127 void    CBitSet::setAll()
 128 {
 129         const vector<uint32>::size_type s = Array.size();
 130         fill_n(Array.begin(), s, ~((uint)0));
 131
 132         if (s)
 133                 Array[s-1]&= MaskLast;
 134 }
 135 void    CBitSet::clearAll()
 136 {
 137         fill_n(Array.begin(), Array.size(), 0);
 138 }
 139
 140
 141 // ***************************************************************************
 142 CBitSet CBitSet::operator~() const
 143 {
 144         CBitSet ret;
 145
 146         ret= *this;
 147         ret.flip();
 148         return ret;
 149 }
 150 CBitSet CBitSet::operator&(const CBitSet &bs) const
 151 {
 152         CBitSet ret;
 153
 154         ret= *this;
 155         ret&=bs;
 156         return ret;
 157 }
 158 CBitSet CBitSet::operator|(const CBitSet &bs) const
 159 {
 160         CBitSet ret;
 161
 162         ret= *this;
 163         ret|=bs;
 164         return ret;
 165 }
 166 CBitSet CBitSet::operator^(const CBitSet &bs) const
 167 {
 168         CBitSet ret;
 169
 170         ret= *this;
 171         ret^=bs;
 172         return ret;
 173 }
 174
 175
 176 // ***************************************************************************
 177 void    CBitSet::flip()
 178 {
 179         if(NumBits==0)
 180                 return;
 181
 182         for(sint i=0;i<(sint)Array.size();i++)
 183                 Array[i]= ~Array[i];
 184
 185         Array[Array.size()-1]&= MaskLast;
 186 }
 187 CBitSet &CBitSet::operator&=(const CBitSet &bs)
 188 {
 189         if(NumBits==0)
 190                 return *this;
 191
 192         vector<uint32>::size_type minSize = min(Array.size(), bs.Array.size());
 193         vector<uint32>::size_type i;
 194         for(i=0;i<minSize;i++)
 195                 Array[i]= Array[i] & bs.Array[i];
 196         for(i=minSize;i<Array.size();i++)
 197                 Array[i]=0;
 198
 199         Array[Array.size()-1]&= MaskLast;
 200
 201         return *this;
 202 }
 203 CBitSet &CBitSet::operator|=(const CBitSet &bs)
 204 {
 205         if(NumBits==0)
 206                 return *this;
 207
 208         vector<uint32>::size_type minSize = min(Array.size(), bs.Array.size());
 209         vector<uint32>::size_type i;
 210         for(i=0;i<minSize;i++)
 211                 Array[i]= Array[i] | bs.Array[i];
 212         // Do nothing for bits word from minSize to Array.size().
 213
 214         Array[Array.size()-1]&= MaskLast;
 215
 216         return *this;
 217 }
 218 CBitSet &CBitSet::operator^=(const CBitSet &bs)
 219 {
 220         if(NumBits==0)
 221                 return *this;
 222
 223         vector<uint32>::size_type minSize= min(Array.size(), bs.Array.size());
 224         vector<uint32>::size_type i;
 225         for(i=0;i<minSize;i++)
 226                 Array[i]= Array[i] ^ bs.Array[i];
 227         // Do nothing for bits word from minSize to Array.size().
 228
 229         Array[Array.size()-1]&= MaskLast;
 230
 231         return *this;
 232 }
 233
 234
 235 // ***************************************************************************
 236 bool    CBitSet::operator==(const CBitSet &bs) const
 237 {
 238         if(NumBits!=bs.NumBits)
 239                 return false;
 240
 241         for(sint i=0;i<(sint)Array.size();i++)
 242         {
 243                 if(Array[i]!=bs.Array[i])
 244                         return false;
 245         }
 246         return true;
 247 }
 248 bool    CBitSet::operator!=(const CBitSet &bs) const
 249 {
 250         return (!operator==(bs));
 251 }
 252 bool    CBitSet::compareRestrict(const CBitSet &bs) const
 253 {
 254         sint    n=min(NumBits, bs.NumBits);
 255         if(n==0) return true;
 256
 257         sint    nA= (n+NL_BITLEN-1) / NL_BITLEN;
 258         uint    mask;
 259
 260         uint    nLastBits= n & (NL_BITLEN-1) ;
 261         // Generate the mask for the last common word.
 262         if(nLastBits==0)
 263                 mask= ~((uint)0);
 264         else
 265                 mask= (1<< nLastBits) -1;
 266
 267
 268         for(sint i=0;i<nA-1;i++)
 269         {
 270                 if(Array[i]!=bs.Array[i])
 271                         return false;
 272         }
 273         if( (Array[nA-1]&mask) != (bs.Array[nA-1]&mask) )
 274                 return false;
 275
 276
 277         return true;
 278 }
 279 bool    CBitSet::allSet()
 280 {
 281         if(NumBits==0)
 282                 return false;
 283         for(sint i=0;i<(sint)Array.size()-1;i++)
 284         {
 285                 if( Array[i]!= (~((uint)0)) )
 286                         return false;
 287         }
 288         if( Array[Array.size()-1]!= MaskLast )
 289                 return false;
 290         return true;
 291 }
 292 bool    CBitSet::allCleared()
 293 {
 294         if(NumBits==0)
 295                 return false;
 296         for(sint i=0;i<(sint)Array.size();i++)
 297         {
 298                 if( Array[i]!= 0 )
 299                         return false;
 300         }
 301         return true;
 302 }
 303
 304
 305
 306 void    CBitSet::serial(IStream &f)
 307 {
 308         /* ***********************************************
 309          *      WARNING: This Class/Method must be thread-safe (ctor/dtor/serial): no static access for instance
 310          *      It can be loaded/called through CAsyncFileManager for instance
 311          * ***********************************************/
 312
 313         (void)f.serialVersion(0);
 314         uint32  sz=0;
 315         vector<uint32>  array32;
 316
 317         // Must support any size of uint.
 318         if(f.isReading())
 319         {
 320                 f.serial(sz);
 321                 resize(sz);
 322
 323                 f.serialCont(array32);
 324                 for(sint i=0;i<(sint)sz;i++)
 325                 {
 326                         uint32  a=array32[i/32];
 327                         a&= 1<<(i&31);
 328                         set(i, a!=0);
 329                 }
 330         }
 331         else
 332         {
 333                 sz= size();
 334                 f.serial(sz);
 335
 336                 array32.resize(sz/32);
 337                 fill_n(array32.begin(), array32.size(), 0);
 338                 for(sint i=0;i<(sint)sz;i++)
 339                 {
 340                         if(get(i))
 341                                 array32[i/32]|= 1<<(i&31);
 342                 }
 343                 f.serialCont(array32);
 344         }
 345 }
 346
 347
 348 /*
 349  * Return a string representing the bitfield with 1 and 0 (from left to right)
 350  */
 351 std::string     CBitSet::toString() const
 352 {
 353         string s;
 354         for ( sint i=0; i!=(sint)size(); ++i )
 355         {
 356                 s += (get(i) ? '1' : '0');
 357         }
 358         return s;
 359 }
 360
 361
 362 }
 363