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// A set of integers in the range [0..N], for some given N.
6
7/*****************************************************************************/
8#ifndef _BITSET_H_
9#define _BITSET_H_
10/*****************************************************************************/
11
12// This class provides some constant declarations and some static utility methods useful
13// for bitset implementations.
14class BitSetSupport
15{
16#ifdef DEBUG
17 template <typename BitSetType, unsigned Brand, typename Env, typename BitSetTraits>
18 static void RunTests(Env env);
19#endif
20
21public:
22 static const unsigned BitsInByte = 8;
23
24 // This maps 4-bit ("nibble") values into the number of 1 bits they contain.
25 static unsigned BitCountTable[16];
26
27 // Returns the number of 1 bits in the binary representation of "u".
28 template <typename T>
29 static unsigned CountBitsInIntegral(T u)
30 {
31 unsigned res = 0;
32 // We process "u" in 4-bit nibbles, hence the "*2" below.
33 for (int i = 0; i < sizeof(T) * 2; i++)
34 {
35 res += BitCountTable[u & 0xf];
36 u >>= 4;
37 }
38 return res;
39 }
40
41#ifdef DEBUG
42 // This runs the "TestSuite" method for a few important instantiations of BitSet.
43 static void TestSuite(CompAllocator env);
44#endif
45
46 enum Operation
47 {
48#define BSOPNAME(x) x,
49#include "bitsetops.h"
50#undef BSOPNAME
51 BSOP_NUMOPS
52 };
53 static const char* OpNames[BSOP_NUMOPS];
54
55 class BitSetOpCounter
56 {
57 unsigned TotalOps;
58 unsigned OpCounts[BSOP_NUMOPS];
59 const char* m_fileName;
60 FILE* OpOutputFile;
61
62 public:
63 BitSetOpCounter(const char* fileName) : TotalOps(0), m_fileName(fileName), OpOutputFile(nullptr)
64 {
65 for (unsigned i = 0; i < BSOP_NUMOPS; i++)
66 {
67 OpCounts[i] = 0;
68 }
69 }
70
71 void RecordOp(Operation op);
72 };
73};
74
75template <>
76FORCEINLINE unsigned BitSetSupport::CountBitsInIntegral<unsigned>(unsigned c)
77{
78 // Make sure we're 32 bit.
79 assert(sizeof(unsigned) == 4);
80 c = (c & 0x55555555) + ((c >> 1) & 0x55555555);
81 c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
82 c = (c & 0x0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f);
83 c = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff);
84 c = (c & 0x0000ffff) + ((c >> 16) & 0x0000ffff);
85 return c;
86}
87
88// A "BitSet" represents a set of integers from a "universe" [0..N-1]. This implementation assumes that "N"
89// (the "Size") is provided by the "Env" template argument type discussed below, and accessed from the Env
90// via a static method of the BitSetTraits type discussed below. The intent of "BitSet" is that the set is
91// represented as a bit array. Various binary operations therefore only make sense if the operands are
92// subsets of the same universe. Further, the integers in the set that the BitSet represents may have
93// different interpretations at a higher level, so even if the range of the universe stays the same,
94// the higher-level meaning of those bits may change. For these reasons, we assume the Env can provide
95// (again, via static methods of the BitSetTraits) the current "epoch" number. The Env must keep the
96// Size the same while the epoch has a given value; a BitSet implementation may legally stamp BitSets
97// with the current epoch, and assert that BitSets from different epochs are not intermixed.
98
99// Some implementations may use a representation that (at least sometimes) is a pointer to a
100// heap-allocated data structure. (The operations of BitSetOps are static methods, rather than
101// declaring a BitSet class type with multiple subtypes, to allow maximally efficient raw
102// primitive type representations.) Therefore, we must be careful about assignment and
103// initialization. We often want to reason about BitSets as immutable values, and just copying
104// the representation would introduce sharing in the indirect case, which is usually not what's
105// desired. On the other hand, there are many cases in which the RHS value has just been
106// created functionally, and the intialization/assignment is obviously its last use. In these
107// cases, allocating a new indirect representation for the lhs (if it does not already have one)
108// would be unnecessary and wasteful. Thus, for assignment, we have a "normal" assignment
109// function, which makes a copy of the referent data structure in the indirect case, and an
110// "AssignNoCopy" version, which does not, and instead introduces sharing in the indirect case.
111// Obviously, the latter should be used with care.
112//
113// (Orthogonally, there are also further versions of assignment that differ in whether the "rhs"
114// argument may be uninitialized. The normal assignment operation requires the "rhs" argument not be
115// uninitialized; "AssignNoCopy" has the same requirement. The "AssignAllowUninitRhs" version allows
116// the "rhs" to be the uninit value, and sets the "lhs" to be uninitialized in that case.)
117
118// This class has static methods that provide the operations on BitSets.
119//
120// An instantiation requires:
121// typename BitSetType: the representation type of this kind of BitSet.
122//
123// unsigned Brand: an integer constant. This is unused by the implementation; it exists
124// *only* to ensure that we can have, if desired, multiple distinct BitSetOps
125// implementations for the same BitSetType, by instantiating these with different
126// values for Brand (thus "branding" them so that they are distinct from one another.)
127//
128// typename Env: a type that determines the (current) size of the given BitSet type, as well
129// as an allocation function, and the current epoch (integer that changes when
130// "universe" of the BitSet changes) -- all via static methods of the "BitSetTraits"
131// type.
132//
133// typename BitSetTraits:
134// An "adapter" class that provides methods that retrieves things from the Env:
135// static void* Alloc(Env, size_t byteSize): Allocates memory the BitSet implementation can use.
136// static unsigned GetSize(Env): the current size (= # of bits) of this bitset type.
137// static unsigned GetArrSize(Env, unsigned elemSize): The number of "elemSize" chunks sufficient to hold
138// "GetSize". A given BitSet implementation must call
139// this with only one constant value. Thus, and "Env"
140// may compute this result when GetSize changes.
141//
142// static unsigned GetEpoch(Env): the current epoch.
143//
144// (For many instantiations, BitSetValueArgType and BitSetValueRetType will be the same as BitSetType; in cases where
145// BitSetType is a class, type, BitSetValueArgType may need to be "const BitSetType&", for example.)
146//
147// In addition to implementing the method signatures here, an instantiation of BitSetOps must also export a
148// BitSetOps::Iter type, which supports the following operations:
149// Iter(BitSetValueArgType): a constructor
150// bool NextElem(unsigned* pElem): returns true if the iteration is not complete, and sets *pElem to the next
151// yielded member.
152//
153// Finally, it should export two further types:
154//
155// ValArgType: the type used to pass a BitSet as a by-value argument.
156// RetValType: the type that should be used to return a BitSet.
157//
158// For many instantiations, these can be identical to BitSetTypes. When the representation type is a class,
159// however, ValArgType may need to be "const BitSetType&", and RetValArg may need to be a helper class, if the
160// class hides default copy constructors and assignment operators to detect erroneous usage.
161//
162template <typename BitSetType, unsigned Brand, typename Env, typename BitSetTraits>
163class BitSetOps
164{
165#if 0
166 // Below are the set of methods that an instantiation of BitSetOps should provide. This is
167 // #if'd out because it doesn't make any difference; C++ has no mechanism for checking that
168 // the methods of an instantiation are consistent with these signatures, other than the expectations
169 // embodied in the program that uses the instantiation(s). But it's useful documentation, and
170 // we should try to keep it up to date.
171
172 public:
173
174 // The uninitialized value -- not a real bitset (if possible).
175 static BitSetValueRetType UninitVal();
176
177 // Returns "true" iff "bs" may be the uninit value.
178 static bool MayBeUninit(BitSetValueArgType bs);
179
180 // Returns the a new BitSet that is empty. Uses the Allocator of "env" to allocate memory for
181 // the representation, if necessary.
182 static BitSetValueRetType MakeEmpty(Env env);
183
184 // Returns the a new BitSet that is "full" -- represents all the integers in the current range.
185 // Uses the Allocator of "env" to allocate memory for the representation, if necessary.
186 static BitSetValueRetType MakeFull(Env env);
187
188 // Returns the set containing the single element "bitNum" (which is required to be within the
189 // BitSet's current range). Uses the Allocator of "env" to allocate memory for the representation,
190 // if necessary.
191 static BitSetValueRetType MakeSingleton(Env env, unsigned bitNum);
192
193 // Assign "rhs" to "lhs". "rhs" must not be the uninitialized value. "lhs" may be, in which case
194 // "rhs" will be copied if necessary.
195 static void Assign(Env env, BitSetType& lhs, BitSetValueArgType rhs);
196
197 // Assign "rhs" to "lhs"...*even* if "rhs" is the uninitialized value.
198 static void AssignAllowUninitRhs(Env env, BitSetType& lhs, BitSetValueArgType rhs);
199
200 // This is a "destructive" assignment -- it should only be used if the rhs is "dead" after the assignment.
201 // In particular, if the rhs has a level of indirection to a heap-allocated data structure, that pointer will
202 // be copied into the lhs.
203 static void AssignNoCopy(Env env, BitSetType& lhs, BitSetValueArgType rhs);
204
205 // Destructively set "bs" to be the empty set.
206 static void ClearD(Env env, BitSetType& bs);
207
208 // Returns a copy of "bs". If the representation of "bs" involves a level of indirection, the data
209 // structure is copied and a pointer to the copy is returned.
210 static BitSetValueRetType MakeCopy(Env env, BitSetValueArgType bs);
211
212 // Returns "true" iff ""bs" represents the empty set.
213 static bool IsEmpty(Env env, BitSetValueArgType bs);
214
215 // Returns the number of members in "bs".
216 static unsigned Count(Env env, BitSetValueArgType bs);
217
218 // Return true if the union of bs1 and bs2 is empty.
219 static bool IsEmptyUnion(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
220
221 // Returns "true" iff "i" is a member of "bs".
222 static bool IsMember(Env env, const BitSetValueArgType bs, unsigned i);
223
224 // Destructively modify "bs" to ensure that "i" is a member.
225 static void AddElemD(Env env, BitSetType& bs, unsigned i);
226 // Returns a BitSet that is a copy of "bs" with "i" added.
227 static BitSetValueRetType AddElem(Env env, BitSetValueArgType bs, unsigned i);
228
229 // Destructively modify "bs" to ensure that "i" is not a member.
230 static void RemoveElemD(Env env, BitSetType& bs, unsigned i);
231 // Returns a BitSet that is a copy of "bs" with "i" removed.
232 static BitSetValueRetType RemoveElem(Env env, BitSetValueArgType bs1, unsigned i);
233
234 // Destructively modify "bs1" to be the union of "bs1" and "bs2".
235 static void UnionD(Env env, BitSetType& bs1, BitSetValueArgType bs2);
236 // Returns a new BitSet that is the union of "bs1" and "bs2".
237 static BitSetValueRetType Union(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
238
239 // Destructively modify "bs1" to be the intersection of "bs1" and "bs2".
240 static void IntersectionD(Env env, BitSetType& bs1, BitSetValueArgType bs2);
241 // Returns a new BitSet that is the intersection of "bs1" and "bs2".
242 static BitSetValueRetType Intersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
243
244 // Returns true iff "bs1" and "bs2" have an empty intersection.
245 static bool IsEmptyIntersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
246
247 // Destructively modify "bs1" to be the set difference of "bs1" and "bs2".
248 static void DiffD(Env env, BitSetType& bs1, BitSetValueArgType bs2);
249
250 // Returns a new BitSet that is the set difference of "bs1" and "bs2".
251 static BitSetValueRetType Diff(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
252
253 // Compute the live_in set. Variable is alive if there is use or it is out set, but not in def.
254 // in = use | (out & ~def)
255 static void LivenessD(Env env, BitSetType& in, BitSetValueArgType def, BitSetValueArgType use, BitSetValueArgType out);
256
257 // Returns true iff "bs2" is a subset of "bs1."
258 static bool IsSubset(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
259
260 // Returns true iff "bs1" and "bs2" are equal.
261 static bool Equal(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2);
262
263#ifdef DEBUG
264 // Returns a string representing the contents of "bs". Allocates memory for the representation
265 // using the Allocator of "env".
266 static const char* ToString(Env env, BitSetValueArgType bs);
267#endif
268
269 // Declare this as a type -- will be a real class in real instantiations.
270 class Iter {
271 public:
272 Iter(Env env, BitSetValueArgType bs) {}
273 bool NextElem(unsigned* pElem) { return false; }
274 };
275
276 typename ValArgType;
277 typename RetValType;
278#endif // 0 -- the above is #if'd out, since it's really just an extended comment on what an instantiation
279 // should provide.
280};
281
282template <typename BitSetType,
283 unsigned Brand,
284 typename Env,
285 typename BitSetTraits,
286 typename BitSetValueArgType,
287 typename BitSetValueRetType,
288 typename BaseIter>
289class BitSetOpsWithCounter
290{
291 typedef BitSetOps<BitSetType, Brand, Env, BitSetTraits> BSO;
292
293public:
294 static BitSetValueRetType UninitVal()
295 {
296 return BSO::UninitVal();
297 }
298 static bool MayBeUninit(BitSetValueArgType bs)
299 {
300 return BSO::MayBeUninit(bs);
301 }
302 static BitSetValueRetType MakeEmpty(Env env)
303 {
304 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeEmpty);
305 return BSO::MakeEmpty(env);
306 }
307 static BitSetValueRetType MakeFull(Env env)
308 {
309 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeFull);
310 return BSO::MakeFull(env);
311 }
312 static BitSetValueRetType MakeSingleton(Env env, unsigned bitNum)
313 {
314 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeSingleton);
315 return BSO::MakeSingleton(env, bitNum);
316 }
317 static void Assign(Env env, BitSetType& lhs, BitSetValueArgType rhs)
318 {
319 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Assign);
320 BSO::Assign(env, lhs, rhs);
321 }
322 static void AssignAllowUninitRhs(Env env, BitSetType& lhs, BitSetValueArgType rhs)
323 {
324 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AssignAllowUninitRhs);
325 BSO::AssignAllowUninitRhs(env, lhs, rhs);
326 }
327 static void AssignNoCopy(Env env, BitSetType& lhs, BitSetValueArgType rhs)
328 {
329 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AssignNocopy);
330 BSO::AssignNoCopy(env, lhs, rhs);
331 }
332 static void ClearD(Env env, BitSetType& bs)
333 {
334 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_ClearD);
335 BSO::ClearD(env, bs);
336 }
337 static BitSetValueRetType MakeCopy(Env env, BitSetValueArgType bs)
338 {
339 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_MakeCopy);
340 return BSO::MakeCopy(env, bs);
341 }
342 static bool IsEmpty(Env env, BitSetValueArgType bs)
343 {
344 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsEmpty);
345 return BSO::IsEmpty(env, bs);
346 }
347 static unsigned Count(Env env, BitSetValueArgType bs)
348 {
349 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Count);
350 return BSO::Count(env, bs);
351 }
352 static bool IsMember(Env env, const BitSetValueArgType bs, unsigned i)
353 {
354 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsMember);
355 return BSO::IsMember(env, bs, i);
356 }
357 static void AddElemD(Env env, BitSetType& bs, unsigned i)
358 {
359 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AddElemD);
360 BSO::AddElemD(env, bs, i);
361 }
362 static BitSetValueRetType AddElem(Env env, BitSetValueArgType bs, unsigned i)
363 {
364 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_AddElem);
365 return BSO::AddElem(env, bs, i);
366 }
367 static void RemoveElemD(Env env, BitSetType& bs, unsigned i)
368 {
369 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_RemoveElemD);
370 BSO::RemoveElemD(env, bs, i);
371 }
372 static BitSetValueRetType RemoveElem(Env env, BitSetValueArgType bs1, unsigned i)
373 {
374 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_RemoveElem);
375 return BSO::RemoveElem(env, bs1, i);
376 }
377 static void UnionD(Env env, BitSetType& bs1, BitSetValueArgType bs2)
378 {
379 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_UnionD);
380 BSO::UnionD(env, bs1, bs2);
381 }
382 static BitSetValueRetType Union(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
383 {
384 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Union);
385 return BSO::Union(env, bs1, bs2);
386 }
387 static void IntersectionD(Env env, BitSetType& bs1, BitSetValueArgType bs2)
388 {
389 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IntersectionD);
390 BSO::IntersectionD(env, bs1, bs2);
391 }
392 static BitSetValueRetType Intersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
393 {
394 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Intersection);
395 return BSO::Intersection(env, bs1, bs2);
396 }
397 static bool IsEmptyIntersection(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
398 {
399 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsEmptyIntersection);
400 return BSO::IsEmptyIntersection(env, bs1, bs2);
401 }
402 static void DiffD(Env env, BitSetType& bs1, BitSetValueArgType bs2)
403 {
404 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_DiffD);
405 BSO::DiffD(env, bs1, bs2);
406 }
407 static BitSetValueRetType Diff(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
408 {
409 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Diff);
410 return BSO::Diff(env, bs1, bs2);
411 }
412 static bool IsSubset(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
413 {
414 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_IsSubset);
415 return BSO::IsSubset(env, bs1, bs2);
416 }
417 static bool Equal(Env env, BitSetValueArgType bs1, BitSetValueArgType bs2)
418 {
419 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_Equal);
420 return BSO::Equal(env, bs1, bs2);
421 }
422#ifdef DEBUG
423 static const char* ToString(Env env, BitSetValueArgType bs)
424 {
425 BitSetTraits::GetOpCounter(env)->RecordOp(BitSetSupport::BSOP_ToString);
426 return BSO::ToString(env, bs);
427 }
428#endif
429
430 class Iter
431 {
432 BaseIter m_iter;
433 Env m_env;
434
435 public:
436 Iter(Env env, BitSetValueArgType bs) : m_iter(env, bs), m_env(env)
437 {
438 }
439
440 bool NextElem(unsigned* pElem)
441 {
442 BitSetTraits::GetOpCounter(m_env)->RecordOp(BitSetSupport::BSOP_NextBit);
443 return m_iter.NextElem(pElem);
444 }
445 };
446};
447
448// We define symbolic names for the various bitset implementations available, to allow choices between them.
449
450#define BSUInt64 0
451#define BSShortLong 1
452#define BSUInt64Class 2
453
454/*****************************************************************************/
455#endif // _BITSET_H_
456/*****************************************************************************/
457