// 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. // A set of integers in the range [0..N], for some given N. /*****************************************************************************/ #ifndef _BITSET_H_ #define _BITSET_H_ /*****************************************************************************/ // This class provides some constant declarations and some static utility methods useful // for bitset implementations. class BitSetSupport { #ifdef DEBUG template static void RunTests(Env env); #endif public: static const unsigned BitsInByte = 8; // This maps 4-bit ("nibble") values into the number of 1 bits they contain. static unsigned BitCountTable[16]; // Returns the number of 1 bits in the binary representation of "u". template static unsigned CountBitsInIntegral(T u) { unsigned res = 0; // We process "u" in 4-bit nibbles, hence the "*2" below. for (int i = 0; i < sizeof(T) * 2; i++) { res += BitCountTable[u & 0xf]; u >>= 4; } return res; } #ifdef DEBUG // This runs the "TestSuite" method for a few important instantiations of BitSet. static void TestSuite(IAllocator* env); #endif enum Operation { #define BSOPNAME(x) x, #include "bitsetops.h" #undef BSOPNAME BSOP_NUMOPS }; static const char* OpNames[BSOP_NUMOPS]; class BitSetOpCounter { unsigned TotalOps; unsigned OpCounts[BSOP_NUMOPS]; const char* m_fileName; FILE* OpOutputFile; public: BitSetOpCounter(const char* fileName) : TotalOps(0), m_fileName(fileName), OpOutputFile(nullptr) { for (unsigned i = 0; i < BSOP_NUMOPS; i++) { OpCounts[i] = 0; } } void RecordOp(Operation op); }; }; template <> FORCEINLINE unsigned BitSetSupport::CountBitsInIntegral(unsigned c) { // Make sure we're 32 bit. assert(sizeof(unsigned) == 4); c = (c & 0x55555555) + ((c >> 1) & 0x55555555); c = (c & 0x33333333) + ((c >> 2) & 0x33333333); c = (c & 0x0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f); c = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff); c = (c & 0x0000ffff) + ((c >> 16) & 0x0000ffff); return c; } // A "BitSet" represents a set of integers from a "universe" [0..N-1]. This implementation assumes that "N" // (the "Size") is provided by the "Env" template argument type discussed below, and accessed from the Env // via a static method of the BitSetTraits type discussed below. The intent of "BitSet" is that the set is // represented as a bit array. Various binary operations therefore only make sense if the operands are // subsets of the same universe. Further, the integers in the set that the BitSet represents may have // different interpretations at a higher level, so even if the range of the universe stays the same, // the higher-level meaning of those bits may change. For these reasons, we assume the Env can provide // (again, via static methods of the BitSetTraits) the current "epoch" number. The Env must keep the // Size the same while the epoch has a given value; a BitSet implementation may legally stamp BitSets // with the current epoch, and assert that BitSets from different epochs are not intermixed. // Some implementations may use a representation that (at least sometimes) is a pointer to a // heap-allocated data structure. (The operations of BitSetOps are static methods, rather than // declaring a BitSet class type with multiple subtypes, to allow maximally efficient raw // primitive type representations.) Therefore, we must be careful about assignment and // initialization. We often want to reason about BitSets as immutable values, and just copying // the representation would introduce sharing in the indirect case, which is usually not what's // desired. On the other hand, there are many cases in which the RHS value has just been // created functionally, and the intialization/assignment is obviously its last use. In these // cases, allocating a new indirect representation for the lhs (if it does not already have one) // would be unnecessary and wasteful. Thus, for assignment, we have a "normal" assignment // function, which makes a copy of the referent data structure in the indirect case, and an // "AssignNoCopy" version, which does not, and instead introduces sharing in the indirect case. // Obviously, the latter should be used with care. // // (Orthogonally, there are also further versions of assignment that differ in whether the "rhs" // argument may be uninitialized. The normal assignment operation requires the "rhs" argument not be // uninitialized; "AssignNoCopy" has the same requirement. The "AssignAllowUninitRhs" version allows // the "rhs" to be the uninit value, and sets the "lhs" to be uninitialized in that case.) // This class has static methods that provide the operations on BitSets. // // An instantiation requires: // typename BitSetType: the representation type of this kind of BitSet. // // unsigned Brand: an integer constant. This is unused by the implementation; it exists // *only* to ensure that we can have, if desired, multiple distinct BitSetOps // implementations for the same BitSetType, by instantiating these with different // values for Brand (thus "branding" them so that they are distinct from one another.) // // typename Env: a type that determines the (current) size of the given BitSet type, as well // as an allocation function, and the current epoch (integer that changes when // "universe" of the BitSet changes) -- all via static methods of the "BitSetTraits" // type. // // typename BitSetTraits: // An "adapter" class that provides methods that retrieves things from the Env: // static IAllocator* GetAllococator(Env): yields an "IAllocator*" that the BitSet implementation can use. // static unsigned GetSize(Env): the current size (= # of bits) of this bitset type. // static unsigned GetArrSize(Env, unsigned elemSize): The number of "elemSize" chunks sufficient to hold // "GetSize". A given BitSet implementation must call // this with only one constant value. Thus, and "Env" // may compute this result when GetSize changes. // // static unsigned GetEpoch(Env): the current epoch. // // (For many instantiations, BitSetValueArgType and BitSetValueRetType will be the same as BitSetType; in cases where // BitSetType is a class, type, BitSetValueArgType may need to be "const BitSetType&", for example.) // // In addition to implementing the method signatures here, an instantiation of BitSetOps must also export a // BitSetOps::Iter type, which supports the following operations: // Iter(BitSetValueArgType): a constructor // bool NextElem(unsigned* pElem): returns true if the iteration is not complete, and sets *pElem to the next // yielded member. // // Finally, it should export two further types: // // ValArgType: the type used to pass a BitSet as a by-value argument. // RetValType: the type that should be used to return a BitSet. // // For many instantiations, these can be identical to BitSetTypes. When the representation type is a class, // however, ValArgType may need to be "const BitSetType&", and RetValArg may need to be a helper class, if the // class hides default copy constructors and assignment operators to detect erroneous usage. // template class BitSetOps { #if 0 // Below are the set of methods that an instantiation of BitSetOps should provide. This is // #if'd out because it doesn't make any difference; C++ has no mechanism for checking that // the methods of an instantiation are consistent with these signatures, other than the expectations // embodied in the program that uses the instantiation(s). But it's useful documentation, and // we should try to keep it up to date. public: // The uninitialized value -- not a real bitset (if possible). static BitSetValueRetType UninitVal(); // Returns "true" iff "bs" may be the uninit value. static bool MayBeUninit(BitSetValueArgType bs); // Returns the a new BitSet that is empty. Uses the Allocator of "env" to allocate memory for // the representation, if necessary. static BitSetValueRetType MakeEmpty(Env env); // Returns the a new BitSet that is "full" -- represents all the integers in the current range. // Uses the Allocator of "env" to allocate memory for the representation, if necessary. static BitSetValueRetType MakeFull(Env env); // Returns the set containing the single element "bitNum" (which is required to be within the // BitSet's current range). Uses the Allocator of "env" to allocate memory for the representation, // if necessary. static BitSetValueRetType MakeSingleton(Env env, unsigned bitNum); // Assign "rhs" to "lhs". "rhs" must not be the uninitialized value. "lhs" may be, in which case // "rhs" will be copied if necessary. static void Assign(Env env, BitSetType& lhs, BitSetValueArgType rhs); // Assign "rhs" to "lhs"...*even* if "rhs" is the uninitialized value. static void AssignAllowUninitRhs(Env env, BitSetType& lhs, BitSetValueArgType rhs); // This is a "destructive" assignment -- it should only be used if the rhs is "dead" after the assignment. // In particular, if the rhs has a level of indirection to a heap-allocated data structure, that pointer will // be copied into the lhs. static void AssignNoCopy(Env env, BitSetType& lhs, BitSetValueArgType rhs); // Destructively set "bs" to be the empty set. This method is unique, in that it does *not* // require "bs" to be a bitset of the current epoch. It ensures that it is after, however. // (If the representation is indirect, this requires allocating a new, empty representation. // If this is a performance issue, we could provide a new version of ClearD that assumes/asserts // that the rep is for the current epoch -- this would be useful if a given bitset were repeatedly // cleared within an epoch.) static void ClearD(Env env, BitSetType& bs); // Returns a copy of "bs". If the representation of "bs" involves a level of indirection, the data // structure is copied and a pointer to the copy is returned. static BitSetValueRetType MakeCopy(Env env, BitSetValueArgType bs); // Returns "true" iff ""bs" represents the empty set. static bool IsEmpty(Env env, BitSetValueArgType bs); // Returns the number of members in "bs". static unsigned Count(Env env, BitSetValueArgType bs); // Returns "true" iff "i" is a member of "bs". static bool IsMember(Env env, const BitSetValueArgType bs, unsigned i); // Destructively modify "bs" to ensure that "i" is a member. static void AddElemD(Env env, BitSetType& bs, unsigned i); // Returns a BitSet that is a copy of "bs" with "i" added. static BitSetValueRetType AddElem(Env env, BitSetValueArgType bs, unsigned i); // Destructively modify "bs" to ensure that "i" is not a member. static void RemoveElemD(Env env, BitSetType& bs, unsigned i); // Returns a BitSet that is a copy of "bs" with "i" removed. static BitSetValueRetType RemoveElem(Env env, BitSetValueArgType bs1, unsigned i); // Destructively modify "bs1" to be the union of "bs1" and "bs2". static void UnionD(Env env, BitSetType& bs1, BitSetValueArgType bs2); // Returns a new BitSet that is the union of "bs1" and "bs2". static BitSetValueRetType Union(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); // Destructively modify "bs1" to be the intersection of "bs1" and "bs2". static void IntersectionD(Env env, BitSetType& bs1, BitSetValueArgType bs2); // Returns a new BitSet that is the intersection of "bs1" and "bs2". static BitSetValueRetType Intersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); // Returns true iff "bs1" and "bs2" have an empty intersection. static bool IsEmptyIntersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); // Destructively modify "bs1" to be the set difference of "bs1" and "bs2". static void DiffD(Env env, BitSetType& bs1, BitSetValueArgType bs2); // Returns a new BitSet that is the set difference of "bs1" and "bs2". static BitSetValueRetType Diff(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); // Returns true iff "bs2" is a subset of "bs1." static bool IsSubset(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); // Returns true iff "bs1" and "bs2" are equal. static bool Equal(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2); #ifdef DEBUG // Returns a string representing the contents of "bs". Allocates memory for the representation // using the Allocator of "env". static const char* ToString(Env env, BitSetValueArgType bs); #endif // Declare this as a type -- will be a real class in real instantiations. class Iter { public: Iter(Env env, BitSetValueArgType bs) {} bool NextElem(Env env, unsigned* pElem) { return false; } }; typename ValArgType; typename RetValType; #endif // 0 -- the above is #if'd out, since it's really just an extended comment on what an instantiation // should provide. }; template class BitSetOpsWithCounter { typedef BitSetOps BSO; public: static BitSetValueRetType UninitVal() { return BSO::UninitVal(); } static bool MayBeUninit(BitSetValueArgType bs) { return BSO::MayBeUninit(bs); } static BitSetValueRetType MakeEmpty(Env env) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeEmpty); return BSO::MakeEmpty(env); } static BitSetValueRetType MakeFull(Env env) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeFull); return BSO::MakeFull(env); } static BitSetValueRetType MakeSingleton(Env env, unsigned bitNum) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeSingleton); return BSO::MakeSingleton(env, bitNum); } static void Assign(Env env, BitSetType& lhs, BitSetValueArgType rhs) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Assign); BSO::Assign(env, lhs, rhs); } static void AssignAllowUninitRhs(Env env, BitSetType& lhs, BitSetValueArgType rhs) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AssignAllowUninitRhs); BSO::AssignAllowUninitRhs(env, lhs, rhs); } static void AssignNoCopy(Env env, BitSetType& lhs, BitSetValueArgType rhs) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AssignNocopy); BSO::AssignNoCopy(env, lhs, rhs); } static void ClearD(Env env, BitSetType& bs) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_ClearD); BSO::ClearD(env, bs); } static BitSetValueRetType MakeCopy(Env env, BitSetValueArgType bs) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeCopy); return BSO::MakeCopy(env, bs); } static bool IsEmpty(Env env, BitSetValueArgType bs) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsEmpty); return BSO::IsEmpty(env, bs); } static unsigned Count(Env env, BitSetValueArgType bs) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Count); return BSO::Count(env, bs); } static bool IsMember(Env env, const BitSetValueArgType bs, unsigned i) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsMember); return BSO::IsMember(env, bs, i); } static void AddElemD(Env env, BitSetType& bs, unsigned i) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AddElemD); BSO::AddElemD(env, bs, i); } static BitSetValueRetType AddElem(Env env, BitSetValueArgType bs, unsigned i) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AddElem); return BSO::AddElem(env, bs, i); } static void RemoveElemD(Env env, BitSetType& bs, unsigned i) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_RemoveElemD); BSO::RemoveElemD(env, bs, i); } static BitSetValueRetType RemoveElem(Env env, BitSetValueArgType bs1, unsigned i) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_RemoveElem); return BSO::RemoveElem(env, bs1, i); } static void UnionD(Env env, BitSetType& bs1, BitSetValueArgType bs2) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_UnionD); BSO::UnionD(env, bs1, bs2); } static BitSetValueRetType Union(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Union); return BSO::Union(env, bs1, bs2); } static void IntersectionD(Env env, BitSetType& bs1, BitSetValueArgType bs2) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IntersectionD); BSO::IntersectionD(env, bs1, bs2); } static BitSetValueRetType Intersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Intersection); return BSO::Intersection(env, bs1, bs2); } static bool IsEmptyIntersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsEmptyIntersection); return BSO::IsEmptyIntersection(env, bs1, bs2); } static void DiffD(Env env, BitSetType& bs1, BitSetValueArgType bs2) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_DiffD); BSO::DiffD(env, bs1, bs2); } static BitSetValueRetType Diff(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Diff); return BSO::Diff(env, bs1, bs2); } static bool IsSubset(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsSubset); return BSO::IsSubset(env, bs1, bs2); } static bool Equal(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Equal); return BSO::Equal(env, bs1, bs2); } #ifdef DEBUG static const char* ToString(Env env, BitSetValueArgType bs) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_ToString); return BSO::ToString(env, bs); } #endif class Iter { BaseIter m_iter; public: Iter(Env env, BitSetValueArgType bs) : m_iter(env, bs) { } bool NextElem(Env env, unsigned* pElem) { BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_NextBit); return m_iter.NextElem(env, pElem); } }; }; // We define symbolic names for the various bitset implementations available, to allow choices between them. #define BSUInt64 0 #define BSShortLong 1 #define BSUInt64Class 2 /*****************************************************************************/ #endif // _BITSET_H_ /*****************************************************************************/