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
6/***************************************************************************/
7/* BitVector.h */
8/***************************************************************************/
9// Routines to support a growable bitvector
10/***************************************************************************/
11
12#ifndef BITVECTOR_H
13#define BITVECTOR_H 1
14
15
16#ifndef LIMITED_METHOD_CONTRACT
17#define LIMITED_METHOD_CONTRACT
18#define UNDEF_LIMITED_METHOD_CONTRACT
19#endif
20
21#ifndef WRAPPER_NO_CONTRACT
22#define WRAPPER_NO_CONTRACT
23#define UNDEF_WRAPPER_NO_CONTRACT
24#endif
25
26#ifndef SUPPORTS_DAC
27#define SUPPORTS_DAC
28#define UNDEF_SUPPORTS_DAC
29#endif
30
31#ifndef _ASSERTE
32#define _ASSERTE(x)
33#define UNDEF_ASSERTE
34#endif
35
36#define USE_BITVECTOR 1
37#if USE_BITVECTOR
38
39/* The bitvector class is meant to be a drop in replacement for an integer
40 (that is you use it like an integer), however it grows as needed.
41
42 Features:
43 plug compatible with normal integers;
44 grows as needed
45 Optimized for the small case when the vector fits in machine word
46 Uses one machine word if vector fits in machine word (minus a bit)
47
48 Some caveates:
49 You should use mutator operators &=, |= ... instead of the
50 non-mutators whenever possible to avoid creating a temps
51
52 Specifically did NOT supply automatic coersions to
53 and from short types so that the programmer is aware of
54 when code was being injected on his behalf. The upshot of this
55 is that you have to use the BitVector() toUnsigned() to convert
56*/
57
58/***************************************************************************/
59
60class BitVector {
61 // Set this to be unsigned char to do testing, should be UINT_PTR for real life
62
63 typedef UINT_PTR ChunkType; // The size of integer type that the machine can operate on directly
64// typedef BYTE ChunkType; // Use for testing
65
66 // Maximum number of bits in our bitvector
67#define MAX_PTRARG_OFS 1024
68
69 enum {
70 IS_BIG = 1, // The low bit is used to discrimate m_val and m_vals
71 CHUNK_BITS = sizeof(ChunkType)*8, // The number of bits that we can manipuate as a chunk
72 SMALL_BITS = CHUNK_BITS - 1, // The number of bits we can fit in the small representation
73// SMALL_BITS = 5, // TESTING ONLY: The number of bits we can fit in the small representation
74 VALS_COUNT = MAX_PTRARG_OFS / CHUNK_BITS, // The number of ChunkType elements in the Vals array
75 };
76
77public:
78 BitVector()
79 {
80 LIMITED_METHOD_CONTRACT;
81 SUPPORTS_DAC;
82
83 m_val = 0;
84 }
85
86 BOOL isBig() const
87 {
88 LIMITED_METHOD_CONTRACT;
89 SUPPORTS_DAC;
90
91 return ((m_val & IS_BIG) != 0);
92 }
93
94 void toBig()
95 {
96 LIMITED_METHOD_CONTRACT;
97 SUPPORTS_DAC;
98
99 if (!isBig())
100 {
101 doBigInit(smallBits());
102 }
103 }
104
105 explicit BitVector(ChunkType arg)
106 {
107 WRAPPER_NO_CONTRACT;
108 SUPPORTS_DAC;
109
110 if (arg > MaxVal)
111 {
112 doBigInit(arg);
113 }
114 else
115 {
116 m_val = ChunkType(arg << 1);
117 }
118 }
119
120 BitVector(ChunkType arg, UINT shift)
121 {
122 WRAPPER_NO_CONTRACT;
123 SUPPORTS_DAC;
124
125 if ((arg > MaxVal) || (shift >= SMALL_BITS) || (arg > (MaxVal >> shift)))
126 {
127 doBigInit(arg);
128 doBigLeftShiftAssign(shift);
129 }
130 else
131 {
132 m_val = ChunkType(arg << (shift+1));
133 }
134 }
135
136#define CONSTRUCT_ptrArgTP(arg,shift) BitVector((arg), (shift))
137
138 BitVector(const BitVector& arg)
139 {
140 WRAPPER_NO_CONTRACT;
141 SUPPORTS_DAC;
142
143 if (arg.isBig())
144 {
145 doBigInit(arg);
146 }
147 else
148 {
149 m_val = arg.m_val;
150 }
151 }
152
153 void operator <<=(unsigned shift)
154 {
155 WRAPPER_NO_CONTRACT;
156 SUPPORTS_DAC;
157
158 if ((m_val == 0) || (shift == 0)) // Zero is a special case, don't need to do anything
159 return;
160
161 if (isBig() || (shift >= SMALL_BITS) || (m_val > (MaxVal >> (shift-1))))
162 {
163 doBigLeftShiftAssign(shift);
164 }
165 else
166 {
167 m_val <<= shift;
168 }
169 }
170
171 void operator >>=(unsigned shift)
172 {
173 WRAPPER_NO_CONTRACT;
174 SUPPORTS_DAC;
175
176 if (isBig())
177 {
178 doBigRightShiftAssign(shift);
179 }
180 else
181 {
182 m_val >>= shift;
183 m_val &= ~IS_BIG; // clear the isBig bit if it got set
184 }
185 }
186
187 void operator |=(const BitVector& arg)
188 {
189 WRAPPER_NO_CONTRACT;
190 SUPPORTS_DAC;
191
192 if (((m_val | arg.m_val) & IS_BIG) != 0)
193 {
194 doBigOrAssign(arg);
195 }
196 else
197 {
198 m_val |= arg.m_val;
199 }
200 }
201
202 // Note that that is set difference, not subtration
203 void operator -=(const BitVector& arg)
204 {
205 WRAPPER_NO_CONTRACT;
206 SUPPORTS_DAC;
207
208 if (((m_val | arg.m_val) & IS_BIG) != 0)
209 {
210 doBigDiffAssign(arg);
211 }
212 else
213 {
214 m_val &= ~arg.m_val;
215 }
216 }
217
218 void operator &=(const BitVector& arg)
219 {
220 WRAPPER_NO_CONTRACT;
221 SUPPORTS_DAC;
222
223 if (((m_val | arg.m_val) & IS_BIG) != 0)
224 {
225 doBigAndAssign(arg);
226 }
227 else
228 {
229 m_val &= arg.m_val;
230 }
231 }
232
233 friend void setDiff(BitVector& target, const BitVector& arg)
234 {
235 WRAPPER_NO_CONTRACT;
236 SUPPORTS_DAC;
237
238 target -= arg;
239 }
240
241 friend BOOL intersect(const BitVector& arg1, const BitVector& arg2)
242 {
243 WRAPPER_NO_CONTRACT;
244 SUPPORTS_DAC;
245
246 if (((arg1.m_val | arg2.m_val) & IS_BIG) != 0)
247 {
248 return arg1.doBigIntersect(arg2);
249 }
250 else
251 {
252 return ((arg1.m_val & arg2.m_val) != 0);
253 }
254 }
255
256 BOOL operator ==(const BitVector& arg) const
257 {
258 WRAPPER_NO_CONTRACT;
259 SUPPORTS_DAC;
260
261 if ((m_val | arg.m_val) & IS_BIG)
262 {
263 return doBigEquals(arg);
264 }
265 else
266 {
267 return m_val == arg.m_val;
268 }
269 }
270
271 BOOL operator !=(const BitVector& arg) const
272 {
273 WRAPPER_NO_CONTRACT;
274 SUPPORTS_DAC;
275
276 return !(*this == arg);
277 }
278
279 friend ChunkType toUnsigned(const BitVector& arg)
280 {
281 WRAPPER_NO_CONTRACT;
282 SUPPORTS_DAC;
283
284 if (arg.isBig())
285 {
286 return arg.m_vals.m_chunks[0]; // Note truncation
287 }
288 else
289 {
290 return arg.smallBits();
291 }
292 }
293
294 // Note that we require the invariant that zero is always stored in the
295 // small form so that this works bitvector is zero iff (m_val == 0)
296 friend BOOL isZero(const BitVector& arg)
297 {
298 WRAPPER_NO_CONTRACT;
299 SUPPORTS_DAC;
300
301 return arg.m_val == 0;
302 }
303
304 /* currently only used in asserts */
305 BitVector operator &(const BitVector& arg) const
306 {
307 WRAPPER_NO_CONTRACT;
308 SUPPORTS_DAC;
309
310 BitVector ret = *this;
311 ret &= arg;
312 return ret;
313 }
314
315 int NumBits() const;
316
317private:
318
319 static const ChunkType MaxVal = ((ChunkType)1 << SMALL_BITS) - 1; // Maximum value that can be stored in m_val
320
321 // This is the structure that we use when the bit vector overflows.
322 // It is a simple vector.
323 struct Vals {
324 unsigned m_encodedLength; // An encoding of the current length of the 'm_chunks' array
325 ChunkType m_chunks[VALS_COUNT];
326
327 BOOL isBig() const
328 {
329 LIMITED_METHOD_CONTRACT;
330 SUPPORTS_DAC;
331
332 return ((m_encodedLength & IS_BIG) != 0);
333 }
334
335 unsigned GetLength() const
336 {
337 LIMITED_METHOD_CONTRACT;
338 SUPPORTS_DAC;
339
340 if (isBig())
341 {
342 unsigned length = (m_encodedLength >> 1);
343 _ASSERTE(length > 0);
344 return length;
345 }
346 else
347 {
348 return 0;
349 }
350 }
351
352 void SetLength(unsigned length)
353 {
354 LIMITED_METHOD_CONTRACT;
355 SUPPORTS_DAC;
356
357 _ASSERTE(length > 0);
358 _ASSERTE(length <= VALS_COUNT);
359
360 m_encodedLength = (ChunkType) (length << 1);
361 m_encodedLength |= (ChunkType) IS_BIG;
362 }
363 };
364
365 //
366 // This is the instance data for the bitvector
367 //
368 // We discrimininate on this
369 union {
370 ChunkType m_val; // if m_val bit 0 is false, then bits 1-N are the bit vector
371 Vals m_vals; // if m_val bit 1 is true, then use Vals
372 };
373
374
375 ChunkType smallBits() const
376 {
377 LIMITED_METHOD_CONTRACT;
378 SUPPORTS_DAC;
379
380 _ASSERTE(!isBig());
381 return (m_val >> 1);
382 }
383
384#ifdef STRIKE
385 void doBigInit(ChunkType arg) {}
386#else
387 void doBigInit(ChunkType arg);
388#endif
389 void doBigInit(const BitVector& arg);
390 void doBigLeftShiftAssign(unsigned arg);
391 void doBigRightShiftAssign(unsigned arg);
392 void doBigDiffAssign(const BitVector&);
393 void doBigAndAssign(const BitVector&);
394 void doBigOrAssign(const BitVector& arg);
395 BOOL doBigEquals(const BitVector&) const;
396 BOOL doBigIntersect(const BitVector&) const;
397};
398
399typedef BitVector ptrArgTP;
400
401#else // !USE_BITVECTOR
402
403typedef unsigned __int64 ptrArgTP;
404
405 // Maximum number of bits in our bitvector
406#define MAX_PTRARG_OFS (sizeof(ptrArgTP) * 8)
407
408#define CONSTRUCT_ptrArgTP(arg,shift) (((ptrArgTP) (arg)) << (shift))
409
410inline BOOL isZero(const ptrArgTP& arg)
411{
412 LIMITED_METHOD_CONTRACT;
413 SUPPORTS_DAC;
414 return (arg == 0);
415}
416
417inline ptrArgTP toUnsigned(const ptrArgTP& arg)
418{
419 LIMITED_METHOD_CONTRACT;
420 SUPPORTS_DAC;
421 return arg;
422}
423
424inline void setDiff(ptrArgTP& target, const ptrArgTP& arg)
425{
426 LIMITED_METHOD_CONTRACT;
427 SUPPORTS_DAC;
428
429 target &= ~arg;
430}
431
432inline BOOL intersect(const ptrArgTP arg1, const ptrArgTP arg2)
433{
434 LIMITED_METHOD_CONTRACT;
435 SUPPORTS_DAC;
436
437 return ((arg1 & arg2) != 0);
438}
439
440#endif // !USE_BITVECTOR
441
442#ifdef UNDEF_LIMITED_METHOD_CONTRACT
443#undef LIMITED_METHOD_CONTRACT
444#undef UNDEF_LIMITED_METHOD_CONTRACT
445#endif
446
447#ifdef UNDEF_WRAPPER_NO_CONTRACT
448#undef WRAPPER_NO_CONTRACT
449#undef UNDEF_WRAPPER_NO_CONTRACT
450#endif
451
452#ifdef UNDEF_SUPPORTS_DAC
453#undef SUPPORTS_DAC
454#undef UNDEF_SUPPORTS_DAC
455#endif
456
457#ifdef UNDEF_ASSERTE
458#undef _ASSERTE
459#undef UNDEF_ASSERTE
460#endif
461
462#endif // BITVECTOR_H
463