text: // Licensed to the .NET Foundation under one or more agreements.
  // The .NET Foundation licenses this file to you under the MIT license.
  // See the LICENSE file in the project root for more information.
  
  
  /***************************************************************************/
  /*                           BitVector.h                                   */
  /***************************************************************************/
  //  Routines to support a growable bitvector
  /***************************************************************************/
  
  #ifndef BITVECTOR_H
  #define BITVECTOR_H 1
  
  #ifndef LIMITED_METHOD_CONTRACT
  #define LIMITED_METHOD_CONTRACT
  #define UNDEF_LIMITED_METHOD_CONTRACT
  #endif
  
  #ifndef WRAPPER_NO_CONTRACT
  #define WRAPPER_NO_CONTRACT
  #define UNDEF_WRAPPER_NO_CONTRACT
  #endif
  
  #ifndef SUPPORTS_DAC
  #define SUPPORTS_DAC
  #define UNDEF_SUPPORTS_DAC
  #endif
  
  #ifndef _ASSERTE
  #define _ASSERTE(x)
  #define UNDEF_ASSERTE
  #endif
  
  #define USE_BITVECTOR 1
  #if USE_BITVECTOR
  
  /* The bitvector class is meant to be a drop in replacement for an integer
     (that is you use it like an integer), however it grows as needed.
  
     Features:
         plug compatible with normal integers;
         grows as needed
         Optimized for the small case when the vector fits in machine word
         Uses one machine word if vector fits in machine word (minus a bit)
  
         Some caveates:
             You should use mutator operators  &=, |= ... instead of the 
             non-mutators whenever possible to avoid creating a temps
  
             Specifically did NOT supply automatic coersions to
             and from short types so that the programmer is aware of
             when code was being injected on his behalf.  The upshot of this
             is that you have to use the  BitVector() toUnsigned() to convert 
  */
  
  /***************************************************************************/
  
  class BitVector {
      // Set this to be unsigned char to do testing, should be UINT_PTR for real life
  
      typedef uint32_t BOOL;
      typedef uintptr_t ChunkType;  // The size of integer type that the machine can operate on directly
  //  typedef BYTE ChunkType;       // Use for testing
  
      // Maximum number of bits in our bitvector
  #define MAX_PTRARG_OFS 1024
  
      enum {
          IS_BIG     = 1,                             // The low bit is used to discrimate m_val and m_vals
          CHUNK_BITS = sizeof(ChunkType)*8,           // The number of bits that we can manipuate as a chunk
          SMALL_BITS = CHUNK_BITS - 1,                // The number of bits we can fit in the small representation
  //      SMALL_BITS = 5,                             // TESTING ONLY: The number of bits we can fit in the small representation
          VALS_COUNT = MAX_PTRARG_OFS / CHUNK_BITS,   // The number of ChunkType elements in the Vals array
      };
  
  public:
      BitVector()
      { 
          LIMITED_METHOD_CONTRACT;
          SUPPORTS_DAC;
  
          m_val = 0;
      }
  
      BOOL isBig() const
      {
          LIMITED_METHOD_CONTRACT;
          SUPPORTS_DAC;
  
          return ((m_val & IS_BIG) != 0);
      }
  
      void toBig()
      {
          LIMITED_METHOD_CONTRACT;
          SUPPORTS_DAC;
  
          if (!isBig())
          {
              doBigInit(smallBits());
          }
      }
  
      explicit BitVector(ChunkType arg)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if (arg > MaxVal)
          {
              doBigInit(arg);
          }
          else 
          {
              m_val = ChunkType(arg << 1);
          }
      }
  
      BitVector(ChunkType arg, UINT shift)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if ((arg > MaxVal) || (shift >= SMALL_BITS) || (arg > (MaxVal >> shift)))
          {
              doBigInit(arg);
              doBigLeftShiftAssign(shift);
          }
          else
          {
              m_val = ChunkType(arg << (shift+1));
          }
      }
  
  #define CONSTRUCT_ptrArgTP(arg,shift)   BitVector((arg), (shift))
  
      BitVector(const BitVector& arg)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if (arg.isBig())
          {
              doBigInit(arg);
          }
          else
          {
              m_val = arg.m_val;
          }
      }
      
      void operator <<=(unsigned shift)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if ((m_val == 0) || (shift == 0))     // Zero is a special case, don't need to do anything
              return;
  
          if (isBig() || (shift >= SMALL_BITS) || (m_val > (MaxVal >> (shift-1))))
          {
              doBigLeftShiftAssign(shift);
          }
          else 
          {
              m_val <<= shift;
          }
      }
  
      void operator >>=(unsigned shift)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if (isBig())
          {
              doBigRightShiftAssign(shift);
          }
          else
          {
              m_val >>= shift;
              m_val &= ~IS_BIG;  // clear the isBig bit if it got set
          }
      }
      
      void operator |=(const BitVector& arg)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if (((m_val | arg.m_val) & IS_BIG) != 0)
          {
              doBigOrAssign(arg);
          }
          else
          {
              m_val |= arg.m_val;
          }
      }
  
      // Note that that is set difference, not subtration
      void operator -=(const BitVector& arg)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if (((m_val | arg.m_val) & IS_BIG) != 0)
          {
              doBigDiffAssign(arg);
          }
          else
          {
              m_val &= ~arg.m_val;
          }
      }
  
      void operator &=(const BitVector& arg)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if (((m_val | arg.m_val) & IS_BIG) != 0)
          {
              doBigAndAssign(arg);
          }
          else
          {
              m_val &= arg.m_val;
          }
      }
  
      friend void setDiff(BitVector& target, const BitVector& arg)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          target -= arg;
      }
  
      friend BOOL intersect(const BitVector& arg1, const BitVector& arg2)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if (((arg1.m_val | arg2.m_val) & IS_BIG) != 0)
          {
              return arg1.doBigIntersect(arg2);
          }
          else
          {
              return ((arg1.m_val & arg2.m_val) != 0);
          }
      }
      
      BOOL operator ==(const BitVector& arg) const
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if ((m_val | arg.m_val) & IS_BIG)
          {
              return doBigEquals(arg);
          }
          else
          {
              return m_val == arg.m_val;
          }
      }
  
      BOOL operator !=(const BitVector& arg) const
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          return !(*this == arg);
      }
  
      friend ChunkType toUnsigned(const BitVector& arg)
      { 
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          if (arg.isBig())
          {
              return arg.m_vals.m_chunks[0];   // Note truncation
          }
          else 
          {
              return arg.smallBits();
          }
      }
  
      // Note that we require the invariant that zero is always stored in the
      // small form so that this works bitvector is zero iff (m_val == 0)
      friend BOOL isZero(const BitVector& arg)
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          return arg.m_val == 0;
      }
  
      /* currently only used in asserts */
      BitVector operator &(const BitVector& arg) const
      {
          WRAPPER_NO_CONTRACT;
          SUPPORTS_DAC;
  
          BitVector ret = *this;
          ret &= arg;
          return ret;
      }
  
      int  NumBits() const;
  
  private:
  
      static const ChunkType MaxVal = ((ChunkType)1 << SMALL_BITS) - 1;    // Maximum value that can be stored in m_val
  
      // This is the structure that we use when the bit vector overflows.  
      // It is a simple vector.  
      struct Vals {
          unsigned m_encodedLength;         // An encoding of the current length of the 'm_chunks' array
          ChunkType m_chunks[VALS_COUNT]; 
  
          BOOL isBig() const
          {
              LIMITED_METHOD_CONTRACT;
              SUPPORTS_DAC;
  
              return ((m_encodedLength & IS_BIG) != 0);
          }
  
          unsigned GetLength() const
          {
              LIMITED_METHOD_CONTRACT;
              SUPPORTS_DAC;
              
              if (isBig())
              {
                  unsigned length = (m_encodedLength >> 1);
                  _ASSERTE(length > 0);
                  return length;
              }
              else
              {
                  return 0;
              }
          }
  
          void SetLength(unsigned length)
          {
              LIMITED_METHOD_CONTRACT;
              SUPPORTS_DAC;
  
              _ASSERTE(length > 0);
              _ASSERTE(length <= VALS_COUNT);
  
              m_encodedLength  = (ChunkType) (length << 1);
              m_encodedLength |= (ChunkType) IS_BIG;
           }
      };
  
      //
      // This is the instance data for the bitvector
      //
      // We discrimininate on this
      union {
          ChunkType m_val;     // if m_val bit 0 is false, then bits 1-N are the bit vector
          Vals      m_vals;    // if m_val bit 1 is true, then use Vals
      };
  
  
      ChunkType smallBits() const
      {
          LIMITED_METHOD_CONTRACT;
          SUPPORTS_DAC;
  
          _ASSERTE(!isBig());
          return (m_val >> 1);
      }
  
  #ifdef STRIKE
      void doBigInit(ChunkType arg) {}
  #else
      void doBigInit(ChunkType arg);
  #endif
      void doBigInit(const BitVector& arg);
      void doBigLeftShiftAssign(unsigned arg);
      void doBigRightShiftAssign(unsigned arg);
      void doBigDiffAssign(const BitVector&);
      void doBigAndAssign(const BitVector&);
      void doBigOrAssign(const BitVector& arg);
      BOOL doBigEquals(const BitVector&) const;
      BOOL doBigIntersect(const BitVector&) const;
  };
  
  typedef BitVector ptrArgTP;
  
  #else // !USE_BITVECTOR
  
  typedef unsigned __int64 ptrArgTP;
  
      // Maximum number of bits in our bitvector
  #define MAX_PTRARG_OFS (sizeof(ptrArgTP) * 8)
  
  #define CONSTRUCT_ptrArgTP(arg,shift)   (((ptrArgTP) (arg)) << (shift))
  
  inline BOOL isZero(const ptrArgTP& arg)
  {
      LIMITED_METHOD_CONTRACT;
      SUPPORTS_DAC;
      return (arg == 0);
  }
  
  inline ptrArgTP toUnsigned(const ptrArgTP& arg)
  {
      LIMITED_METHOD_CONTRACT;
      SUPPORTS_DAC;
      return arg;
  }
  
  inline void setDiff(ptrArgTP& target, const ptrArgTP& arg)
  {
      LIMITED_METHOD_CONTRACT;
      SUPPORTS_DAC;
  
      target &= ~arg;
  }
  
  inline BOOL intersect(const ptrArgTP arg1, const ptrArgTP arg2)
  {
      LIMITED_METHOD_CONTRACT;
      SUPPORTS_DAC;
  
      return ((arg1 & arg2) != 0);
  }
  
  #endif  // !USE_BITVECTOR
  
  #ifdef UNDEF_LIMITED_METHOD_CONTRACT
  #undef LIMITED_METHOD_CONTRACT
  #undef UNDEF_LIMITED_METHOD_CONTRACT
  #endif
  
  #ifdef UNDEF_WRAPPER_NO_CONTRACT
  #undef WRAPPER_NO_CONTRACT
  #undef UNDEF_WRAPPER_NO_CONTRACT
  #endif
  
  #ifdef UNDEF_SUPPORTS_DAC
  #undef SUPPORTS_DAC
  #undef UNDEF_SUPPORTS_DAC
  #endif
  
  #ifdef UNDEF_ASSERTE
  #undef _ASSERTE
  #undef UNDEF_ASSERTE
  #endif
  
  #endif // BITVECTOR_H
  