src/utilcode/bitvector.cpp

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 /***************************************************************************/
   6 /*                           BitVector.cpp                                 */
   7 /***************************************************************************/
   8 //  Routines to support a growable bitvector
   9 /***************************************************************************/
  10
  11 #include "stdafx.h"
  12 #include <memory.h>
  13
  14 #include "utilcode.h"
  15
  16 #include "bitvector.h"
  17
  18 #if USE_BITVECTOR
  19
  20 int  BitVector::NumBits() const
  21 {
  22     CONTRACTL {
  23         NOTHROW;
  24         GC_NOTRIGGER;
  25         SUPPORTS_DAC;
  26     } CONTRACTL_END;
  27
  28     int count = 0;
  29     ChunkType hiChunk;
  30
  31     if (isBig())
  32     {
  33         unsigned maxNonZero = 0;
  34         for (unsigned i=1; (i < m_vals.GetLength()); i++)
  35         {
  36             if (m_vals.m_chunks[i] != 0)
  37             {
  38                 maxNonZero = i;
  39             }
  40         }
  41         count = (maxNonZero * CHUNK_BITS) - 1;
  42         hiChunk = m_vals.m_chunks[maxNonZero];
  43     }
  44     else
  45     {
  46         hiChunk = m_val;
  47     }
  48
  49     while (hiChunk > 0)
  50     {
  51         hiChunk <<= 1;
  52         count++;
  53     }
  54
  55     _ASSERTE(count >= 0);
  56     return count;
  57 }
  58
  59 void BitVector::doBigInit(ChunkType arg)
  60 {
  61     WRAPPER_NO_CONTRACT;
  62     SUPPORTS_DAC;
  63
  64     m_vals.m_chunks[0] = arg;
  65     m_vals.SetLength(1);
  66 }
  67
  68 void BitVector::doBigInit(const BitVector& arg)
  69 {
  70     WRAPPER_NO_CONTRACT;
  71     SUPPORTS_DAC;
  72
  73     if (arg.isBig())
  74     {
  75         memcpy(m_vals.m_chunks, arg.m_vals.m_chunks, (sizeof(ChunkType) * arg.m_vals.GetLength()));
  76         m_vals.SetLength(arg.m_vals.GetLength());
  77     }
  78     else
  79     {
  80         m_val = arg.m_val;
  81     }
  82 }
  83
  84 void BitVector::doBigLeftShiftAssign(unsigned shift)
  85 {
  86     CONTRACTL {
  87         NOTHROW;
  88         GC_NOTRIGGER;
  89         SUPPORTS_DAC;
  90     } CONTRACTL_END;
  91
  92     if ((m_val == 0) || (shift == 0))     // Zero is a special case, don't need to do anything
  93         return;
  94
  95     unsigned numWords = shift / CHUNK_BITS;
  96     unsigned numBits  = shift % CHUNK_BITS;
  97
  98     //
  99     // Change to Big representation
 100     //
 101     toBig();
 102
 103     int       from    = m_vals.GetLength()-1;
 104     int       to      = from + numWords;
 105     unsigned  newlen  = to + 1;
 106
 107     ChunkType topBits = 0;
 108     if (numBits > 0)
 109     {
 110         topBits = m_vals.m_chunks[from] >> (CHUNK_BITS - numBits);
 111     }
 112
 113     if (topBits != 0 || numWords != 0)
 114     {
 115         if (topBits != 0)
 116         {
 117             m_vals.m_chunks[newlen] = topBits;
 118             newlen++;
 119         }
 120         m_vals.SetLength(newlen);
 121     }
 122
 123     while (to >= 0)
 124     {
 125         m_vals.m_chunks[to] = (from >= 0) ? (m_vals.m_chunks[from] << numBits) : 0;
 126         from--;
 127
 128         if ((from >= 0) && (numBits > 0))
 129         {
 130             m_vals.m_chunks[to] |= m_vals.m_chunks[from] >> (CHUNK_BITS - numBits);
 131         }
 132         to--;
 133     }
 134
 135     // Convert back to small format if necessary
 136     if ((newlen == 1) && (m_vals.m_chunks[0] <= MaxVal))
 137     {
 138         m_val = ChunkType(m_vals.m_chunks[0] << 1);
 139     }
 140 }
 141
 142 void BitVector::doBigRightShiftAssign(unsigned shift)
 143 {
 144     CONTRACTL {
 145         NOTHROW;
 146         GC_NOTRIGGER;
 147         SUPPORTS_DAC;
 148     } CONTRACTL_END;
 149
 150     if ((m_val == 0) || (shift == 0))     // Zero is a special case, don't need to do anything
 151         return;
 152
 153     unsigned   numWords = shift / CHUNK_BITS;
 154     unsigned   numBits  = shift % CHUNK_BITS;
 155
 156     //
 157     // Change to Big representation
 158     //
 159     toBig();
 160
 161     unsigned  from   = numWords;
 162     unsigned  to     = 0;
 163     unsigned  len    = m_vals.GetLength();
 164     unsigned  newlen = len - numWords;
 165
 166     if (from >= len)
 167     {
 168         // we always encode zero in short form
 169         m_val = 0;
 170     }
 171     else
 172     {
 173         m_vals.m_chunks[to] = (m_vals.m_chunks[from] >> numBits);
 174         from++;
 175
 176         while (from < len)
 177         {
 178             if (numBits > 0)
 179             {
 180                 m_vals.m_chunks[to] |= m_vals.m_chunks[from] << (CHUNK_BITS - numBits);
 181             }
 182             to++;
 183
 184             m_vals.m_chunks[to] = (m_vals.m_chunks[from] >> numBits);
 185             from++;
 186         }
 187
 188         if ((newlen > 1) && (m_vals.m_chunks[newlen-1] == 0))
 189         {
 190             newlen--;
 191         }
 192
 193         m_vals.SetLength(newlen);
 194
 195         // Convert back to small format if necessary
 196         if ((newlen == 1) && (m_vals.m_chunks[0] <= MaxVal))
 197         {
 198             m_val = ChunkType(m_vals.m_chunks[0] << 1);
 199         }
 200     }
 201 }
 202
 203 void BitVector::doBigAndAssign(const BitVector& arg)
 204 {
 205     CONTRACTL {
 206         NOTHROW;
 207         GC_NOTRIGGER;
 208         SUPPORTS_DAC;
 209     } CONTRACTL_END;
 210
 211     //
 212     // Change to Big representation
 213     //
 214     toBig();
 215
 216     if (arg.isBig())
 217     {
 218         bool     isZero = true;   // until proven otherwise
 219         unsigned myLen  = m_vals.GetLength();
 220         unsigned argLen = arg.m_vals.GetLength();
 221
 222         if (myLen > argLen)
 223         {
 224             // shrink our length to match argLen
 225             m_vals.SetLength(argLen);
 226             myLen = argLen;
 227         }
 228
 229         for (unsigned i = 0; (i < myLen); i++)
 230         {
 231             ChunkType curChunk = m_vals.m_chunks[i] & arg.m_vals.m_chunks[i];
 232             m_vals.m_chunks[i] = curChunk;
 233             if (curChunk != 0)
 234                 isZero = false;
 235         }
 236
 237         if (isZero)
 238         {
 239             // we always encode zero in short form
 240             m_val = 0;
 241         }
 242     }
 243     else
 244     {
 245         m_val = (m_vals.m_chunks[0] << 1) & arg.m_val;
 246     }
 247 }
 248
 249 void BitVector::doBigOrAssign(const BitVector& arg)
 250 {
 251     CONTRACTL {
 252         NOTHROW;
 253         GC_NOTRIGGER;
 254         SUPPORTS_DAC;
 255     } CONTRACTL_END;
 256
 257     //
 258     // Change to Big representation
 259     //
 260     toBig();
 261
 262     if (arg.isBig())
 263     {
 264         unsigned myLen  = m_vals.GetLength();
 265         unsigned argLen = arg.m_vals.GetLength();
 266
 267         if (myLen < argLen)
 268         {
 269             // expand our length to match argLen and zero init
 270             memset(m_vals.m_chunks + myLen, 0, sizeof(ChunkType) * (argLen - myLen));
 271             m_vals.SetLength(argLen);
 272             myLen = argLen;
 273         }
 274
 275         for(unsigned i = 0; ((i < myLen) && (i < argLen)); i++)
 276         {
 277             m_vals.m_chunks[i] |= arg.m_vals.m_chunks[i];
 278         }
 279     }
 280     else
 281     {
 282         m_vals.m_chunks[0] |= arg.smallBits();
 283     }
 284 }
 285
 286 void BitVector::doBigDiffAssign(const BitVector& arg)
 287 {
 288     CONTRACTL {
 289         NOTHROW;
 290         GC_NOTRIGGER;
 291         SUPPORTS_DAC;
 292     } CONTRACTL_END;
 293
 294     //
 295     // Change to Big representation
 296     //
 297     toBig();
 298
 299     unsigned myLen  = m_vals.GetLength();
 300     unsigned argLen = arg.m_vals.GetLength();
 301     bool     isZero = true;                    // until proven otherwise
 302
 303     for (unsigned i = 0; (i < myLen); i++)
 304     {
 305         ChunkType nextChunk = m_vals.m_chunks[i];
 306         if (i < argLen)
 307         {
 308             nextChunk &= ~arg.m_vals.m_chunks[i];
 309             m_vals.m_chunks[i] = nextChunk;
 310         }
 311         else if (i == 0)
 312         {
 313             nextChunk &= ~arg.smallBits();
 314             m_vals.m_chunks[i] = nextChunk;
 315         }
 316
 317         if (nextChunk != 0)
 318             isZero = false;
 319     }
 320
 321     if (isZero)
 322     {
 323         // we always encode zero in short form
 324         m_val = 0;
 325     }
 326 }
 327
 328 BOOL BitVector::doBigEquals(const BitVector& arg) const
 329 {
 330     CONTRACT(BOOL)
 331     {
 332         NOTHROW;
 333         GC_NOTRIGGER;
 334         SUPPORTS_DAC;
 335     }
 336     CONTRACT_END;
 337
 338     unsigned myLen  = m_vals.GetLength();
 339     unsigned argLen = arg.m_vals.GetLength();
 340     unsigned maxLen = (myLen >= argLen) ? myLen : argLen;
 341
 342     for (unsigned i=0; (i < maxLen); i++)
 343     {
 344         ChunkType myVal  = 0;
 345         ChunkType argVal = 0;
 346
 347         if (i < myLen)
 348             myVal = m_vals.m_chunks[i];
 349
 350         if (i < argLen)
 351             argVal = arg.m_vals.m_chunks[i];
 352
 353         if (i == 0)
 354         {
 355             if (myLen == 0)
 356                 myVal = smallBits();
 357             if (argLen == 0)
 358                 argVal = arg.smallBits();
 359         }
 360
 361         if (myVal != argVal)
 362             RETURN false;
 363     }
 364     RETURN true;
 365 }
 366
 367 BOOL BitVector::doBigIntersect(const BitVector& arg) const
 368 {
 369     CONTRACT(BOOL)
 370     {
 371         NOTHROW;
 372         GC_NOTRIGGER;
 373         SUPPORTS_DAC;
 374     }
 375     CONTRACT_END;
 376
 377     unsigned myLen  = m_vals.GetLength();
 378     unsigned argLen = arg.m_vals.GetLength();
 379     unsigned minLen = (myLen <= argLen) ? myLen : argLen;
 380
 381     for (unsigned i=0; (i <= minLen); i++)
 382     {
 383         ChunkType myVal  = 0;
 384         ChunkType argVal = 0;
 385
 386         if (i < myLen)
 387             myVal = m_vals.m_chunks[i];
 388
 389         if (i < argLen)
 390             argVal = arg.m_vals.m_chunks[i];
 391
 392         if (i == 0)
 393         {
 394             if (myLen == 0)
 395                 myVal = smallBits();
 396             if (argLen == 0)
 397                 argVal = arg.smallBits();
 398         }
 399
 400         if ((myVal & argVal) != 0)
 401             RETURN true;
 402     }
 403     RETURN false;
 404 }
 405
 406 #endif // USE_BITVECTOR