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 bitSetAsUint64_DEFINED
6#define bitSetAsUint64_DEFINED 1
7
8#include "bitset.h"
9
10template <typename Env, typename BitSetTraits>
11class BitSetOps</*BitSetType*/ UINT64,
12 /*Brand*/ BSUInt64,
13 /*Env*/ Env,
14 /*BitSetTraits*/ BitSetTraits>
15{
16public:
17 typedef UINT64 Rep;
18
19private:
20 static UINT64 Singleton(unsigned bitNum)
21 {
22 assert(bitNum < sizeof(UINT64) * BitSetSupport::BitsInByte);
23 return (UINT64)1 << bitNum;
24 }
25
26public:
27 static void Assign(Env env, UINT64& lhs, UINT64 rhs)
28 {
29 lhs = rhs;
30 }
31
32 static void AssignNouninit(Env env, UINT64& lhs, UINT64 rhs)
33 {
34 lhs = rhs;
35 }
36
37 static void AssignAllowUninitRhs(Env env, UINT64& lhs, UINT64 rhs)
38 {
39 lhs = rhs;
40 }
41
42 static void AssignNoCopy(Env env, UINT64& lhs, UINT64 rhs)
43 {
44 lhs = rhs;
45 }
46
47 static void ClearD(Env env, UINT64& bs)
48 {
49 bs = 0;
50 }
51
52 static UINT64 MakeSingleton(Env env, unsigned bitNum)
53 {
54 assert(bitNum < BitSetTraits::GetSize(env));
55 return Singleton(bitNum);
56 }
57
58 static UINT64 MakeCopy(Env env, UINT64 bs)
59 {
60 return bs;
61 }
62
63 static bool IsEmpty(Env env, UINT64 bs)
64 {
65 return bs == 0;
66 }
67
68 static unsigned Count(Env env, UINT64 bs)
69 {
70 return BitSetSupport::CountBitsInIntegral(bs);
71 }
72
73 static bool IsEmptyUnion(Env env, UINT64 bs1, UINT64 bs2)
74 {
75 return (bs1 | bs2) == 0;
76 }
77
78 static void UnionD(Env env, UINT64& bs1, UINT64 bs2)
79 {
80 bs1 |= bs2;
81 }
82
83 static UINT64 Union(Env env, UINT64& bs1, UINT64 bs2)
84 {
85 return bs1 | bs2;
86 }
87
88 static void DiffD(Env env, UINT64& bs1, UINT64 bs2)
89 {
90 bs1 = bs1 & ~bs2;
91 }
92
93 static UINT64 Diff(Env env, UINT64 bs1, UINT64 bs2)
94 {
95 return bs1 & ~bs2;
96 }
97
98 static void RemoveElemD(Env env, UINT64& bs1, unsigned i)
99 {
100 assert(i < BitSetTraits::GetSize(env));
101 bs1 &= ~Singleton(i);
102 }
103
104 static UINT64 RemoveElem(Env env, UINT64 bs1, unsigned i)
105 {
106 return bs1 & ~Singleton(i);
107 }
108
109 static void AddElemD(Env env, UINT64& bs1, unsigned i)
110 {
111 assert(i < BitSetTraits::GetSize(env));
112 bs1 |= Singleton(i);
113 }
114
115 static UINT64 AddElem(Env env, UINT64 bs1, unsigned i)
116 {
117 assert(i < BitSetTraits::GetSize(env));
118 return bs1 | Singleton(i);
119 }
120
121 static bool IsMember(Env env, const UINT64 bs1, unsigned i)
122 {
123 assert(i < BitSetTraits::GetSize(env));
124 return (bs1 & Singleton(i)) != 0;
125 }
126
127 static void IntersectionD(Env env, UINT64& bs1, UINT64 bs2)
128 {
129 bs1 &= bs2;
130 }
131
132 static UINT64 Intersection(Env env, UINT64 bs1, UINT64 bs2)
133 {
134 return bs1 & bs2;
135 }
136
137 static bool IsEmptyIntersection(Env env, UINT64 bs1, UINT64 bs2)
138 {
139 return (bs1 & bs2) == 0;
140 }
141
142 static void LivenessD(Env env, UINT64& in, const UINT64 def, const UINT64 use, const UINT64 out)
143 {
144 in = use | (out & ~def);
145 }
146
147 static bool IsSubset(Env env, UINT64 bs1, UINT64 bs2)
148 {
149 return ((bs1 & bs2) == bs1);
150 }
151
152 static bool Equal(Env env, UINT64 bs1, UINT64 bs2)
153 {
154 return bs1 == bs2;
155 }
156
157 static UINT64 MakeEmpty(Env env)
158 {
159 return 0;
160 }
161
162 static UINT64 MakeFull(Env env)
163 {
164 unsigned sz = BitSetTraits::GetSize(env);
165 if (sz == sizeof(UINT64) * 8)
166 {
167 return UINT64(-1);
168 }
169 else
170 {
171 return (UINT64(1) << sz) - 1;
172 }
173 }
174
175#ifdef DEBUG
176 static const char* ToString(Env env, UINT64 bs)
177 {
178 const int CharsForUINT64 = sizeof(UINT64) * 2;
179 char* res = nullptr;
180 const int AllocSize = CharsForUINT64 + 4;
181 res = (char*)BitSetTraits::DebugAlloc(env, AllocSize);
182 UINT64 bits = bs;
183 unsigned remaining = AllocSize;
184 char* ptr = res;
185 for (unsigned bytesDone = 0; bytesDone < sizeof(UINT64); bytesDone += sizeof(unsigned))
186 {
187 unsigned bits0 = (unsigned)bits;
188 sprintf_s(ptr, remaining, "%08X", bits0);
189 ptr += 8;
190 remaining -= 8;
191 bytesDone += 4;
192 assert(sizeof(unsigned) == 4);
193 // Doing this twice by 16, rather than once by 32, avoids warnings when size_t == unsigned.
194 bits = bits >> 16;
195 bits = bits >> 16;
196 }
197 return res;
198 }
199#endif
200
201 static UINT64 UninitVal()
202 {
203 return 0;
204 }
205
206 static bool MayBeUninit(UINT64 bs)
207 {
208 return bs == UninitVal();
209 }
210
211 class Iter
212 {
213 UINT64 m_bits;
214
215 // The number of bits that have already been iterated over (set or clear).
216 unsigned m_bitNum;
217
218 public:
219 Iter(Env env, const UINT64& bits) : m_bits(bits), m_bitNum(0)
220 {
221 }
222
223 bool NextElem(unsigned* pElem)
224 {
225 // TODO-Throughtput: use BitScanForward64() intrinsic (see short/long implementation).
226 if (m_bits)
227 {
228 unsigned bitNum = m_bitNum;
229 while ((m_bits & 0x1) == 0)
230 {
231 bitNum++;
232 m_bits >>= 1;
233 }
234 *pElem = bitNum;
235 m_bitNum = bitNum + 1;
236 m_bits >>= 1;
237 return true;
238 }
239 else
240 {
241 return false;
242 }
243 }
244 };
245
246 typedef const UINT64 ValArgType;
247 typedef UINT64 RetValType;
248};
249
250#endif // bitSetAsUint64_DEFINED
251