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#ifndef bitSetAsUint64InClass_DEFINED
6#define bitSetAsUint64InClass_DEFINED 1
7
8#include "bitset.h"
9#include "bitsetasuint64.h"
10#include "stdmacros.h"
11
12template <typename Env, typename BitSetTraits>
13class BitSetUint64ValueRetType;
14
15template <typename Env, typename BitSetTraits>
16class BitSetUint64Iter;
17
18template <typename Env, typename BitSetTraits>
19class BitSetUint64
20{
21public:
22 typedef BitSetUint64<Env, BitSetTraits> Rep;
23
24private:
25 friend class BitSetOps</*BitSetType*/ BitSetUint64<Env, BitSetTraits>,
26 /*Brand*/ BSUInt64Class,
27 /*Env*/ Env,
28 /*BitSetTraits*/ BitSetTraits>;
29
30 friend class BitSetUint64ValueRetType<Env, BitSetTraits>;
31
32 UINT64 m_bits;
33
34#ifdef DEBUG
35 unsigned m_epoch;
36#endif
37
38 typedef BitSetOps<UINT64, BSUInt64, Env, BitSetTraits> Uint64BitSetOps;
39
40 void CheckEpoch(Env env) const
41 {
42#ifdef DEBUG
43 assert(m_epoch == BitSetTraits::GetEpoch(env));
44#endif
45 }
46
47 bool operator==(const BitSetUint64& bs) const
48 {
49 return m_bits == bs.m_bits
50#ifdef DEBUG
51 && m_epoch == bs.m_epoch
52#endif
53 ;
54 }
55
56public:
57 BitSetUint64& operator=(const BitSetUint64& bs)
58 {
59 m_bits = bs.m_bits;
60#ifdef DEBUG
61 m_epoch = bs.m_epoch;
62#endif // DEBUG
63 return (*this);
64 }
65
66 BitSetUint64(const BitSetUint64& bs)
67 : m_bits(bs.m_bits)
68#ifdef DEBUG
69 , m_epoch(bs.m_epoch)
70#endif
71 {
72 }
73
74private:
75 // Return the number of bits set in the BitSet.
76 inline unsigned Count(Env env) const
77 {
78 CheckEpoch(env);
79 return Uint64BitSetOps::Count(env, m_bits);
80 }
81
82 inline void DiffD(Env env, const BitSetUint64& bs2)
83 {
84 CheckEpoch(env);
85 bs2.CheckEpoch(env);
86 Uint64BitSetOps::DiffD(env, m_bits, bs2.m_bits);
87 }
88
89 inline BitSetUint64 Diff(Env env, const BitSetUint64& bs2) const
90 {
91 CheckEpoch(env);
92 bs2.CheckEpoch(env);
93 BitSetUint64 res(*this);
94 Uint64BitSetOps::DiffD(env, res.m_bits, bs2.m_bits);
95 return res;
96 }
97
98 inline void RemoveElemD(Env env, unsigned i)
99 {
100 CheckEpoch(env);
101 Uint64BitSetOps::RemoveElemD(env, m_bits, i);
102 }
103
104 inline BitSetUint64 RemoveElem(Env env, unsigned i) const
105 {
106 CheckEpoch(env);
107 BitSetUint64 res(*this);
108 Uint64BitSetOps::RemoveElemD(env, res.m_bits, i);
109 return res;
110 }
111
112 inline void AddElemD(Env env, unsigned i)
113 {
114 CheckEpoch(env);
115 Uint64BitSetOps::AddElemD(env, m_bits, i);
116 }
117
118 inline BitSetUint64 AddElem(Env env, unsigned i) const
119 {
120 CheckEpoch(env);
121 BitSetUint64 res(*this);
122 Uint64BitSetOps::AddElemD(env, res.m_bits, i);
123 return res;
124 }
125
126 inline bool IsMember(Env env, unsigned i) const
127 {
128 CheckEpoch(env);
129 return Uint64BitSetOps::IsMember(env, m_bits, i);
130 }
131
132 inline void IntersectionD(Env env, const BitSetUint64& bs2)
133 {
134 CheckEpoch(env);
135 bs2.CheckEpoch(env);
136 m_bits = m_bits & bs2.m_bits;
137 }
138
139 inline BitSetUint64 Intersection(Env env, const BitSetUint64& bs2) const
140 {
141 CheckEpoch(env);
142 bs2.CheckEpoch(env);
143 BitSetUint64 res(*this);
144 Uint64BitSetOps::IntersectionD(env, res.m_bits, bs2.m_bits);
145 return res;
146 }
147
148 inline bool IsEmptyUnion(Env env, const BitSetUint64& bs2) const
149 {
150 CheckEpoch(env);
151 bs2.CheckEpoch(env);
152 return Uint64BitSetOps::IsEmptyUnion(env, m_bits, bs2.m_bits);
153 }
154
155 inline void UnionD(Env env, const BitSetUint64& bs2)
156 {
157 CheckEpoch(env);
158 bs2.CheckEpoch(env);
159 Uint64BitSetOps::UnionD(env, m_bits, bs2.m_bits);
160 }
161
162 inline BitSetUint64 Union(Env env, const BitSetUint64& bs2) const
163 {
164 CheckEpoch(env);
165 bs2.CheckEpoch(env);
166 BitSetUint64 res(*this);
167 Uint64BitSetOps::UnionD(env, res.m_bits, bs2.m_bits);
168 return res;
169 }
170
171 inline void ClearD(Env env)
172 {
173 assert(m_epoch == BitSetTraits::GetEpoch(env));
174 Uint64BitSetOps::ClearD(env, m_bits);
175 }
176
177 inline bool IsEmpty(Env env) const
178 {
179 CheckEpoch(env);
180 return Uint64BitSetOps::IsEmpty(env, m_bits);
181 }
182
183 inline void LivenessD(Env env, const BitSetUint64& def, const BitSetUint64& use, const BitSetUint64& out)
184 {
185 CheckEpoch(env);
186 def.CheckEpoch(env);
187 use.CheckEpoch(env);
188 out.CheckEpoch(env);
189 return Uint64BitSetOps::LivenessD(env, m_bits, def.m_bits, use.m_bits, out.m_bits);
190 }
191
192 inline bool IsSubset(Env env, const BitSetUint64& bs2) const
193 {
194 CheckEpoch(env);
195 bs2.CheckEpoch(env);
196 return Uint64BitSetOps::IsSubset(env, m_bits, bs2.m_bits);
197 }
198
199 inline bool IsEmptyIntersection(Env env, const BitSetUint64& bs2) const
200 {
201 CheckEpoch(env);
202 bs2.CheckEpoch(env);
203 return Uint64BitSetOps::IsEmptyIntersection(env, m_bits, bs2.m_bits);
204 }
205
206 inline bool Equal(Env env, const BitSetUint64& bs2) const
207 {
208 CheckEpoch(env);
209 bs2.CheckEpoch(env);
210 return Uint64BitSetOps::Equal(env, m_bits, bs2.m_bits);
211 }
212
213 const char* ToString(Env env) const
214 {
215 return Uint64BitSetOps::ToString(env, m_bits);
216 }
217
218public:
219 // Uninint
220 BitSetUint64()
221 : m_bits(0)
222#ifdef DEBUG
223 , m_epoch(UINT32_MAX) // Undefined.
224#endif
225 {
226 }
227
228 BitSetUint64(Env env, bool full = false)
229 : m_bits(0)
230#ifdef DEBUG
231 , m_epoch(BitSetTraits::GetEpoch(env))
232#endif
233 {
234 if (full)
235 {
236 m_bits = Uint64BitSetOps::MakeFull(env);
237 }
238 }
239
240 inline BitSetUint64(const BitSetUint64ValueRetType<Env, BitSetTraits>& rt);
241
242 BitSetUint64(Env env, unsigned bitNum)
243 : m_bits(Uint64BitSetOps::MakeSingleton(env, bitNum))
244#ifdef DEBUG
245 , m_epoch(BitSetTraits::GetEpoch(env))
246#endif
247 {
248 assert(bitNum < BitSetTraits::GetSize(env));
249 }
250};
251
252template <typename Env, typename BitSetTraits>
253class BitSetUint64ValueRetType
254{
255 friend class BitSetUint64<Env, BitSetTraits>;
256
257 BitSetUint64<Env, BitSetTraits> m_bs;
258
259public:
260 BitSetUint64ValueRetType(const BitSetUint64<Env, BitSetTraits>& bs) : m_bs(bs)
261 {
262 }
263};
264
265template <typename Env, typename BitSetTraits>
266BitSetUint64<Env, BitSetTraits>::BitSetUint64(const BitSetUint64ValueRetType<Env, BitSetTraits>& rt)
267 : m_bits(rt.m_bs.m_bits)
268#ifdef DEBUG
269 , m_epoch(rt.m_bs.m_epoch)
270#endif
271{
272}
273
274template <typename Env, typename BitSetTraits>
275class BitSetOps</*BitSetType*/ BitSetUint64<Env, BitSetTraits>,
276 /*Brand*/ BSUInt64Class,
277 /*Env*/ Env,
278 /*BitSetTraits*/ BitSetTraits>
279{
280 typedef BitSetUint64<Env, BitSetTraits> BST;
281 typedef const BitSetUint64<Env, BitSetTraits>& BSTValArg;
282 typedef BitSetUint64ValueRetType<Env, BitSetTraits> BSTRetVal;
283
284public:
285 static BSTRetVal UninitVal()
286 {
287 return BitSetUint64<Env, BitSetTraits>();
288 }
289
290 static bool MayBeUninit(BSTValArg bs)
291 {
292 return bs == UninitVal();
293 }
294
295 static void Assign(Env env, BST& lhs, BSTValArg rhs)
296 {
297 lhs = rhs;
298 }
299
300 static void AssignNouninit(Env env, BST& lhs, BSTValArg rhs)
301 {
302 lhs = rhs;
303 }
304
305 static void AssignAllowUninitRhs(Env env, BST& lhs, BSTValArg rhs)
306 {
307 lhs = rhs;
308 }
309
310 static void AssignNoCopy(Env env, BST& lhs, BSTValArg rhs)
311 {
312 lhs = rhs;
313 }
314
315 static void ClearD(Env env, BST& bs)
316 {
317 bs.ClearD(env);
318 }
319
320 static BSTRetVal MakeSingleton(Env env, unsigned bitNum)
321 {
322 assert(bitNum < BitSetTraits::GetSize(env));
323 return BST(env, bitNum);
324 }
325
326 static BSTRetVal MakeCopy(Env env, BSTValArg bs)
327 {
328 return bs;
329 }
330
331 static bool IsEmpty(Env env, BSTValArg bs)
332 {
333 return bs.IsEmpty(env);
334 }
335
336 static unsigned Count(Env env, BSTValArg bs)
337 {
338 return bs.Count(env);
339 }
340
341 static bool IsEmptyUnion(Env env, BSTValArg bs1, BSTValArg bs2)
342 {
343 return bs1.IsEmptyUnion(env, bs2);
344 }
345
346 static void UnionD(Env env, BST& bs1, BSTValArg bs2)
347 {
348 bs1.UnionD(env, bs2);
349 }
350
351 static BSTRetVal Union(Env env, BSTValArg bs1, BSTValArg bs2)
352 {
353 return bs1.Union(env, bs2);
354 }
355
356 static void DiffD(Env env, BST& bs1, BSTValArg bs2)
357 {
358 bs1.DiffD(env, bs2);
359 }
360
361 static BSTRetVal Diff(Env env, BSTValArg bs1, BSTValArg bs2)
362 {
363 return bs1.Diff(env, bs2);
364 }
365
366 static void RemoveElemD(Env env, BST& bs1, unsigned i)
367 {
368 assert(i < BitSetTraits::GetSize(env));
369 bs1.RemoveElemD(env, i);
370 }
371
372 static BSTRetVal RemoveElem(Env env, BSTValArg bs1, unsigned i)
373 {
374 assert(i < BitSetTraits::GetSize(env));
375 return bs1.RemoveElem(env, i);
376 }
377
378 static void AddElemD(Env env, BST& bs1, unsigned i)
379 {
380 assert(i < BitSetTraits::GetSize(env));
381 bs1.AddElemD(env, i);
382 }
383
384 static BSTRetVal AddElem(Env env, BSTValArg bs1, unsigned i)
385 {
386 assert(i < BitSetTraits::GetSize(env));
387 return bs1.AddElem(env, i);
388 }
389
390 static bool IsMember(Env env, BSTValArg bs1, unsigned i)
391 {
392 assert(i < BitSetTraits::GetSize(env));
393 return bs1.IsMember(env, i);
394 }
395
396 static void IntersectionD(Env env, BST& bs1, BSTValArg bs2)
397 {
398 bs1.IntersectionD(env, bs2);
399 }
400
401 static BSTRetVal Intersection(Env env, BSTValArg bs1, BSTValArg bs2)
402 {
403 return bs1.Intersection(env, bs2);
404 }
405
406 static bool IsEmptyIntersection(Env env, BSTValArg bs1, BSTValArg bs2)
407 {
408 return bs1.IsEmptyIntersection(env, bs2);
409 }
410
411 static void LivenessD(Env env, BST& in, BSTValArg def, BSTValArg use, BSTValArg out)
412 {
413 in.LivenessD(env, def, use, out);
414 }
415 static bool IsSubset(Env env, BSTValArg bs1, BSTValArg bs2)
416 {
417 return bs1.IsSubset(env, bs2);
418 }
419
420 static bool Equal(Env env, BSTValArg bs1, BSTValArg bs2)
421 {
422 return bs1.Equal(env, bs2);
423 }
424
425 static bool NotEqual(Env env, BSTValArg bs1, BSTValArg bs2)
426 {
427 return !bs1.Equal(env, bs2);
428 }
429
430 static BSTRetVal MakeEmpty(Env env)
431 {
432 return BST(env);
433 }
434
435 static BSTRetVal MakeFull(Env env)
436 {
437 return BST(env, /*full*/ true);
438 }
439
440#ifdef DEBUG
441 static const char* ToString(Env env, BSTValArg bs)
442 {
443 return bs.ToString(env);
444 }
445#endif
446
447 // You *can* clear a bit after it's been iterated. But you shouldn't otherwise mutate the
448 // bitset during bit iteration.
449 class Iter
450 {
451 UINT64 m_bits;
452 unsigned m_bitNum;
453
454 public:
455 Iter(Env env, const BitSetUint64<Env, BitSetTraits>& bs) : m_bits(bs.m_bits), m_bitNum(0)
456 {
457 }
458
459 bool NextElem(unsigned* pElem)
460 {
461 static const unsigned UINT64_SIZE = 64;
462
463 if ((m_bits & 0x1) != 0)
464 {
465 *pElem = m_bitNum;
466 m_bitNum++;
467 m_bits >>= 1;
468 return true;
469 }
470 else
471 {
472 // Skip groups of 4 zeros -- an optimization for sparse bitsets.
473 while (m_bitNum < UINT64_SIZE && (m_bits & 0xf) == 0)
474 {
475 m_bitNum += 4;
476 m_bits >>= 4;
477 }
478 while (m_bitNum < UINT64_SIZE && (m_bits & 0x1) == 0)
479 {
480 m_bitNum += 1;
481 m_bits >>= 1;
482 }
483 if (m_bitNum < UINT64_SIZE)
484 {
485 *pElem = m_bitNum;
486 m_bitNum++;
487 m_bits >>= 1;
488 return true;
489 }
490 else
491 {
492 return false;
493 }
494 }
495 }
496 };
497
498 typedef const BitSetUint64<Env, BitSetTraits>& ValArgType;
499 typedef BitSetUint64ValueRetType<Env, BitSetTraits> RetValType;
500};
501#endif // bitSetAsUint64InClass_DEFINED
502