diff options
Diffstat (limited to 'src/inc/bitvector.h')
-rw-r--r-- | src/inc/bitvector.h | 462 |
1 files changed, 462 insertions, 0 deletions
diff --git a/src/inc/bitvector.h b/src/inc/bitvector.h new file mode 100644 index 0000000000..a4181dbb8a --- /dev/null +++ b/src/inc/bitvector.h @@ -0,0 +1,462 @@ +// 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 UINT_PTR 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 |