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 N defined by the "Env" (via "BitSetTraits").
6//
7// Represented as a pointer-sized item. If N bits can fit in this item, the representation is "direct"; otherwise,
8// the item is a pointer to an array of K size_t's, where K is the number of size_t's necessary to hold N bits.
9
10#ifndef bitSetAsShortLong_DEFINED
11#define bitSetAsShortLong_DEFINED 1
12
13#include "bitset.h"
14#include "compilerbitsettraits.h"
15
16typedef size_t* BitSetShortLongRep;
17
18template <typename Env, typename BitSetTraits>
19class BitSetOps</*BitSetType*/ BitSetShortLongRep,
20 /*Brand*/ BSShortLong,
21 /*Env*/ Env,
22 /*BitSetTraits*/ BitSetTraits>
23{
24public:
25 typedef BitSetShortLongRep Rep;
26
27private:
28 static const unsigned BitsInSizeT = sizeof(size_t) * BitSetSupport::BitsInByte;
29
30 inline static bool IsShort(Env env)
31 {
32 return BitSetTraits::GetArrSize(env, sizeof(size_t)) <= 1;
33 }
34
35 // The operations on the "long" (pointer-to-array-of-size_t) versions of the representation.
36 static void AssignLong(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs);
37 static BitSetShortLongRep MakeSingletonLong(Env env, unsigned bitNum);
38 static BitSetShortLongRep MakeCopyLong(Env env, BitSetShortLongRep bs);
39 static bool IsEmptyLong(Env env, BitSetShortLongRep bs);
40 static unsigned CountLong(Env env, BitSetShortLongRep bs);
41 static bool IsEmptyUnionLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2);
42 static void UnionDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2);
43 static void DiffDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2);
44 static void AddElemDLong(Env env, BitSetShortLongRep& bs, unsigned i);
45 static bool TryAddElemDLong(Env env, BitSetShortLongRep& bs, unsigned i);
46 static void RemoveElemDLong(Env env, BitSetShortLongRep& bs, unsigned i);
47 static void ClearDLong(Env env, BitSetShortLongRep& bs);
48 static BitSetShortLongRep MakeUninitArrayBits(Env env);
49 static BitSetShortLongRep MakeEmptyArrayBits(Env env);
50 static BitSetShortLongRep MakeFullArrayBits(Env env);
51 static bool IsMemberLong(Env env, BitSetShortLongRep bs, unsigned i);
52 static bool EqualLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2);
53 static bool IsSubsetLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2);
54 static bool IsEmptyIntersectionLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2);
55 static void IntersectionDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2);
56 static void DataFlowDLong(Env env,
57 BitSetShortLongRep& out,
58 const BitSetShortLongRep gen,
59 const BitSetShortLongRep in);
60 static void LivenessDLong(Env env,
61 BitSetShortLongRep& in,
62 const BitSetShortLongRep def,
63 const BitSetShortLongRep use,
64 const BitSetShortLongRep out);
65#ifdef DEBUG
66 static const char* ToStringLong(Env env, BitSetShortLongRep bs);
67#endif
68
69public:
70 inline static BitSetShortLongRep UninitVal()
71 {
72 return nullptr;
73 }
74
75 static bool MayBeUninit(BitSetShortLongRep bs)
76 {
77 return bs == UninitVal();
78 }
79
80 static void Assign(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs)
81 {
82 // We can't assert that rhs != UninitVal in the Short case, because in that
83 // case it's a legal value.
84 if (IsShort(env))
85 {
86 // Both are short.
87 lhs = rhs;
88 }
89 else if (lhs == UninitVal())
90 {
91 assert(rhs != UninitVal());
92 lhs = MakeCopy(env, rhs);
93 }
94 else
95 {
96 AssignLong(env, lhs, rhs);
97 }
98 }
99
100 static void AssignAllowUninitRhs(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs)
101 {
102 if (IsShort(env))
103 {
104 // Both are short.
105 lhs = rhs;
106 }
107 else if (rhs == UninitVal())
108 {
109 lhs = rhs;
110 }
111 else if (lhs == UninitVal())
112 {
113 lhs = MakeCopy(env, rhs);
114 }
115 else
116 {
117 AssignLong(env, lhs, rhs);
118 }
119 }
120
121 static void AssignNoCopy(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs)
122 {
123 lhs = rhs;
124 }
125
126 static void ClearD(Env env, BitSetShortLongRep& bs)
127 {
128 if (IsShort(env))
129 {
130 bs = (BitSetShortLongRep) nullptr;
131 }
132 else
133 {
134 assert(bs != UninitVal());
135 ClearDLong(env, bs);
136 }
137 }
138
139 static BitSetShortLongRep MakeSingleton(Env env, unsigned bitNum)
140 {
141 assert(bitNum < BitSetTraits::GetSize(env));
142 if (IsShort(env))
143 {
144 return BitSetShortLongRep(((size_t)1) << bitNum);
145 }
146 else
147 {
148 return MakeSingletonLong(env, bitNum);
149 }
150 }
151
152 static BitSetShortLongRep MakeCopy(Env env, BitSetShortLongRep bs)
153 {
154 if (IsShort(env))
155 {
156 return bs;
157 }
158 else
159 {
160 return MakeCopyLong(env, bs);
161 }
162 }
163
164 static bool IsEmpty(Env env, BitSetShortLongRep bs)
165 {
166 if (IsShort(env))
167 {
168 return bs == nullptr;
169 }
170 else
171 {
172 assert(bs != UninitVal());
173 return IsEmptyLong(env, bs);
174 }
175 }
176
177 static unsigned Count(Env env, BitSetShortLongRep bs)
178 {
179 if (IsShort(env))
180 {
181 return BitSetSupport::CountBitsInIntegral(size_t(bs));
182 }
183 else
184 {
185 assert(bs != UninitVal());
186 return CountLong(env, bs);
187 }
188 }
189
190 static bool IsEmptyUnion(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
191 {
192 if (IsShort(env))
193 {
194 return (((size_t)bs1) | ((size_t)bs2)) == 0;
195 }
196 else
197 {
198 return IsEmptyUnionLong(env, bs1, bs2);
199 }
200 }
201
202 static void UnionD(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
203 {
204 if (IsShort(env))
205 {
206 bs1 = (BitSetShortLongRep)(((size_t)bs1) | ((size_t)bs2));
207 }
208 else
209 {
210 UnionDLong(env, bs1, bs2);
211 }
212 }
213 static BitSetShortLongRep Union(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
214 {
215 BitSetShortLongRep res = MakeCopy(env, bs1);
216 UnionD(env, res, bs2);
217 return res;
218 }
219
220 static void DiffD(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
221 {
222 if (IsShort(env))
223 {
224 bs1 = (BitSetShortLongRep)(((size_t)bs1) & (~(size_t)bs2));
225 }
226 else
227 {
228 DiffDLong(env, bs1, bs2);
229 }
230 }
231 static BitSetShortLongRep Diff(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
232 {
233 BitSetShortLongRep res = MakeCopy(env, bs1);
234 DiffD(env, res, bs2);
235 return res;
236 }
237
238 static void RemoveElemD(Env env, BitSetShortLongRep& bs, unsigned i)
239 {
240 assert(i < BitSetTraits::GetSize(env));
241 if (IsShort(env))
242 {
243 size_t mask = ((size_t)1) << i;
244 mask = ~mask;
245 bs = (BitSetShortLongRep)(((size_t)bs) & mask);
246 }
247 else
248 {
249 assert(bs != UninitVal());
250 RemoveElemDLong(env, bs, i);
251 }
252 }
253 static BitSetShortLongRep RemoveElem(Env env, BitSetShortLongRep bs, unsigned i)
254 {
255 BitSetShortLongRep res = MakeCopy(env, bs);
256 RemoveElemD(env, res, i);
257 return res;
258 }
259
260 static void AddElemD(Env env, BitSetShortLongRep& bs, unsigned i)
261 {
262 assert(i < BitSetTraits::GetSize(env));
263 if (IsShort(env))
264 {
265 size_t mask = ((size_t)1) << i;
266 bs = (BitSetShortLongRep)(((size_t)bs) | mask);
267 }
268 else
269 {
270 AddElemDLong(env, bs, i);
271 }
272 }
273 static BitSetShortLongRep AddElem(Env env, BitSetShortLongRep bs, unsigned i)
274 {
275 BitSetShortLongRep res = MakeCopy(env, bs);
276 AddElemD(env, res, i);
277 return res;
278 }
279
280 static bool TryAddElemD(Env env, BitSetShortLongRep& bs, unsigned i)
281 {
282 assert(i < BitSetTraits::GetSize(env));
283 if (IsShort(env))
284 {
285 size_t mask = ((size_t)1) << i;
286 size_t bits = (size_t)bs;
287 bool added = (bits & mask) == 0;
288 bs = (BitSetShortLongRep)(bits | mask);
289 return added;
290 }
291 else
292 {
293 return TryAddElemDLong(env, bs, i);
294 }
295 }
296
297 static bool IsMember(Env env, const BitSetShortLongRep bs, unsigned i)
298 {
299 assert(i < BitSetTraits::GetSize(env));
300 if (IsShort(env))
301 {
302 size_t mask = ((size_t)1) << i;
303 return (((size_t)bs) & mask) != 0;
304 }
305 else
306 {
307 assert(bs != UninitVal());
308 return IsMemberLong(env, bs, i);
309 }
310 }
311
312 static void IntersectionD(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
313 {
314 if (IsShort(env))
315 {
316 (size_t&)bs1 &= (size_t)bs2;
317 }
318 else
319 {
320 IntersectionDLong(env, bs1, bs2);
321 }
322 }
323
324 static BitSetShortLongRep Intersection(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
325 {
326 BitSetShortLongRep res = MakeCopy(env, bs1);
327 IntersectionD(env, res, bs2);
328 return res;
329 }
330 static bool IsEmptyIntersection(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
331 {
332 if (IsShort(env))
333 {
334 return (((size_t)bs1) & ((size_t)bs2)) == 0;
335 }
336 else
337 {
338 return IsEmptyIntersectionLong(env, bs1, bs2);
339 }
340 }
341
342 static void DataFlowD(Env env, BitSetShortLongRep& out, const BitSetShortLongRep gen, const BitSetShortLongRep in)
343 {
344 if (IsShort(env))
345 {
346 (size_t&)out = (size_t)out & ((size_t)gen | (size_t)in);
347 }
348 else
349 {
350 DataFlowDLong(env, out, gen, in);
351 }
352 }
353
354 static void LivenessD(Env env,
355 BitSetShortLongRep& in,
356 const BitSetShortLongRep def,
357 const BitSetShortLongRep use,
358 const BitSetShortLongRep out)
359 {
360 if (IsShort(env))
361 {
362 (size_t&)in = (size_t)use | ((size_t)out & ~(size_t)def);
363 }
364 else
365 {
366 LivenessDLong(env, in, def, use, out);
367 }
368 }
369
370 static bool IsSubset(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
371 {
372 if (IsShort(env))
373 {
374 size_t u1 = (size_t)bs1;
375 size_t u2 = (size_t)bs2;
376 return (u1 & u2) == u1;
377 }
378 else
379 {
380 return IsSubsetLong(env, bs1, bs2);
381 }
382 }
383
384 static bool Equal(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
385 {
386 if (IsShort(env))
387 {
388 return (size_t)bs1 == (size_t)bs2;
389 }
390 else
391 {
392 return EqualLong(env, bs1, bs2);
393 }
394 }
395
396#ifdef DEBUG
397 // Returns a string valid until the allocator releases the memory.
398 static const char* ToString(Env env, BitSetShortLongRep bs)
399 {
400 if (IsShort(env))
401 {
402 assert(sizeof(BitSetShortLongRep) == sizeof(size_t));
403 const int CharsForSizeT = sizeof(size_t) * 2;
404 char* res = nullptr;
405 const int ShortAllocSize = CharsForSizeT + 4;
406 res = (char*)BitSetTraits::DebugAlloc(env, ShortAllocSize);
407 size_t bits = (size_t)bs;
408 unsigned remaining = ShortAllocSize;
409 char* ptr = res;
410 if (sizeof(size_t) == sizeof(int64_t))
411 {
412 sprintf_s(ptr, remaining, "%016zX", bits);
413 }
414 else
415 {
416 assert(sizeof(size_t) == sizeof(int));
417 sprintf_s(ptr, remaining, "%08zX", bits);
418 }
419 return res;
420 }
421 else
422 {
423 return ToStringLong(env, bs);
424 }
425 }
426#endif
427
428 static BitSetShortLongRep MakeEmpty(Env env)
429 {
430 if (IsShort(env))
431 {
432 return nullptr;
433 }
434 else
435 {
436 return MakeEmptyArrayBits(env);
437 }
438 }
439
440 static BitSetShortLongRep MakeFull(Env env)
441 {
442 if (IsShort(env))
443 {
444 // Can't just shift by numBits+1, since that might be 32 (and (1 << 32( == 1, for an unsigned).
445 unsigned numBits = BitSetTraits::GetSize(env);
446 if (numBits == BitsInSizeT)
447 {
448 // Can't use the implementation below to get all 1's...
449 return BitSetShortLongRep(size_t(-1));
450 }
451 else
452 {
453 return BitSetShortLongRep((size_t(1) << numBits) - 1);
454 }
455 }
456 else
457 {
458 return MakeFullArrayBits(env);
459 }
460 }
461
462 class Iter
463 {
464 // The BitSet that we're iterating over. This is updated to point at the current
465 // size_t set of bits.
466 BitSetShortLongRep m_bs;
467
468 // The end of the iteration.
469 BitSetShortLongRep m_bsEnd;
470
471 // The remaining bits to be iterated over in the current size_t set of bits.
472 // In the "short" case, these are all the remaining bits.
473 // In the "long" case, these are remaining bits in the current element;
474 // these and the bits in the remaining elements comprise the remaining bits.
475 size_t m_bits;
476
477 // The number of bits that have already been iterated over (set or clear). If you
478 // add this to the bit number of the next bit in "m_bits", you get the proper bit number of that
479 // bit in "m_bs". This is only updated when we increment m_bs.
480 unsigned m_bitNum;
481
482 public:
483 Iter(Env env, const BitSetShortLongRep& bs) : m_bs(bs), m_bitNum(0)
484 {
485 if (BitSetOps::IsShort(env))
486 {
487 m_bits = (size_t)bs;
488
489 // Set the iteration end condition, valid even though this is not a pointer in the short case.
490 m_bsEnd = bs + 1;
491 }
492 else
493 {
494 assert(bs != BitSetOps::UninitVal());
495 m_bits = bs[0];
496
497 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
498 m_bsEnd = bs + len;
499 }
500 }
501
502 bool NextElem(unsigned* pElem)
503 {
504#if BITSET_TRACK_OPCOUNTS
505 BitSetStaticsImpl::RecordOp(BitSetStaticsImpl::BSOP_NextBit);
506#endif
507 for (;;)
508 {
509 DWORD nextBit;
510 BOOL hasBit;
511#ifdef _HOST_64BIT_
512 static_assert_no_msg(sizeof(size_t) == 8);
513 hasBit = BitScanForward64(&nextBit, m_bits);
514#else
515 static_assert_no_msg(sizeof(size_t) == 4);
516 hasBit = BitScanForward(&nextBit, m_bits);
517#endif
518
519 // If there's a bit, doesn't matter if we're short or long.
520 if (hasBit)
521 {
522 *pElem = m_bitNum + nextBit;
523 m_bits &= ~(((size_t)1) << nextBit); // clear bit we just found so we don't find it again
524 return true;
525 }
526 else
527 {
528 // Go to the next size_t bit element. For short bitsets, this will hit the end condition
529 // and exit.
530 ++m_bs;
531 if (m_bs == m_bsEnd)
532 {
533 return false;
534 }
535
536 // If we get here, it's not a short type, so get the next size_t element.
537 m_bitNum += sizeof(size_t) * BitSetSupport::BitsInByte;
538 m_bits = *m_bs;
539 }
540 }
541 }
542 };
543
544 typedef const BitSetShortLongRep& ValArgType;
545 typedef BitSetShortLongRep RetValType;
546};
547
548template <typename Env, typename BitSetTraits>
549void BitSetOps</*BitSetType*/ BitSetShortLongRep,
550 /*Brand*/ BSShortLong,
551 /*Env*/ Env,
552 /*BitSetTraits*/ BitSetTraits>::AssignLong(Env env, BitSetShortLongRep& lhs, BitSetShortLongRep rhs)
553{
554 assert(!IsShort(env));
555 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
556 for (unsigned i = 0; i < len; i++)
557 {
558 lhs[i] = rhs[i];
559 }
560}
561
562template <typename Env, typename BitSetTraits>
563BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
564 /*Brand*/ BSShortLong,
565 /*Env*/ Env,
566 /*BitSetTraits*/ BitSetTraits>::MakeSingletonLong(Env env, unsigned bitNum)
567{
568 assert(!IsShort(env));
569 BitSetShortLongRep res = MakeEmptyArrayBits(env);
570 unsigned index = bitNum / BitsInSizeT;
571 res[index] = ((size_t)1) << (bitNum % BitsInSizeT);
572 return res;
573}
574
575template <typename Env, typename BitSetTraits>
576BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
577 /*Brand*/ BSShortLong,
578 /*Env*/ Env,
579 /*BitSetTraits*/ BitSetTraits>::MakeCopyLong(Env env, BitSetShortLongRep bs)
580{
581 assert(!IsShort(env));
582 BitSetShortLongRep res = MakeUninitArrayBits(env);
583 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
584 for (unsigned i = 0; i < len; i++)
585 {
586 res[i] = bs[i];
587 }
588 return res;
589}
590
591template <typename Env, typename BitSetTraits>
592bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
593 /*Brand*/ BSShortLong,
594 /*Env*/ Env,
595 /*BitSetTraits*/ BitSetTraits>::IsEmptyLong(Env env, BitSetShortLongRep bs)
596{
597 assert(!IsShort(env));
598 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
599 for (unsigned i = 0; i < len; i++)
600 {
601 if (bs[i] != 0)
602 {
603 return false;
604 }
605 }
606 return true;
607}
608
609template <typename Env, typename BitSetTraits>
610unsigned BitSetOps</*BitSetType*/ BitSetShortLongRep,
611 /*Brand*/ BSShortLong,
612 /*Env*/ Env,
613 /*BitSetTraits*/ BitSetTraits>::CountLong(Env env, BitSetShortLongRep bs)
614{
615 assert(!IsShort(env));
616 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
617 unsigned res = 0;
618 for (unsigned i = 0; i < len; i++)
619 {
620 res += BitSetSupport::CountBitsInIntegral(bs[i]);
621 }
622 return res;
623}
624
625template <typename Env, typename BitSetTraits>
626void BitSetOps</*BitSetType*/ BitSetShortLongRep,
627 /*Brand*/ BSShortLong,
628 /*Env*/ Env,
629 /*BitSetTraits*/ BitSetTraits>::UnionDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
630{
631 assert(!IsShort(env));
632 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
633 for (unsigned i = 0; i < len; i++)
634 {
635 bs1[i] |= bs2[i];
636 }
637}
638
639template <typename Env, typename BitSetTraits>
640void BitSetOps</*BitSetType*/ BitSetShortLongRep,
641 /*Brand*/ BSShortLong,
642 /*Env*/ Env,
643 /*BitSetTraits*/ BitSetTraits>::DiffDLong(Env env, BitSetShortLongRep& bs1, BitSetShortLongRep bs2)
644{
645 assert(!IsShort(env));
646 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
647 for (unsigned i = 0; i < len; i++)
648 {
649 bs1[i] &= ~bs2[i];
650 }
651}
652
653template <typename Env, typename BitSetTraits>
654void BitSetOps</*BitSetType*/ BitSetShortLongRep,
655 /*Brand*/ BSShortLong,
656 /*Env*/ Env,
657 /*BitSetTraits*/ BitSetTraits>::AddElemDLong(Env env, BitSetShortLongRep& bs, unsigned i)
658{
659 assert(!IsShort(env));
660 unsigned index = i / BitsInSizeT;
661 size_t mask = ((size_t)1) << (i % BitsInSizeT);
662 bs[index] |= mask;
663}
664
665template <typename Env, typename BitSetTraits>
666bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
667 /*Brand*/ BSShortLong,
668 /*Env*/ Env,
669 /*BitSetTraits*/ BitSetTraits>::TryAddElemDLong(Env env, BitSetShortLongRep& bs, unsigned i)
670{
671 assert(!IsShort(env));
672 unsigned index = i / BitsInSizeT;
673 size_t mask = ((size_t)1) << (i % BitsInSizeT);
674 size_t bits = bs[index];
675 bool added = (bits & mask) == 0;
676 bs[index] = bits | mask;
677 return added;
678}
679
680template <typename Env, typename BitSetTraits>
681void BitSetOps</*BitSetType*/ BitSetShortLongRep,
682 /*Brand*/ BSShortLong,
683 /*Env*/ Env,
684 /*BitSetTraits*/ BitSetTraits>::RemoveElemDLong(Env env, BitSetShortLongRep& bs, unsigned i)
685{
686 assert(!IsShort(env));
687 unsigned index = i / BitsInSizeT;
688 size_t mask = ((size_t)1) << (i % BitsInSizeT);
689 mask = ~mask;
690 bs[index] &= mask;
691}
692
693template <typename Env, typename BitSetTraits>
694void BitSetOps</*BitSetType*/ BitSetShortLongRep,
695 /*Brand*/ BSShortLong,
696 /*Env*/ Env,
697 /*BitSetTraits*/ BitSetTraits>::ClearDLong(Env env, BitSetShortLongRep& bs)
698{
699 assert(!IsShort(env));
700 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
701 for (unsigned i = 0; i < len; i++)
702 {
703 bs[i] = 0;
704 }
705}
706
707template <typename Env, typename BitSetTraits>
708BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
709 /*Brand*/ BSShortLong,
710 /*Env*/ Env,
711 /*BitSetTraits*/ BitSetTraits>::MakeUninitArrayBits(Env env)
712{
713 assert(!IsShort(env));
714 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
715 assert(len > 1); // Or else would not require an array.
716 return (BitSetShortLongRep)(BitSetTraits::Alloc(env, len * sizeof(size_t)));
717}
718
719template <typename Env, typename BitSetTraits>
720BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
721 /*Brand*/ BSShortLong,
722 /*Env*/ Env,
723 /*BitSetTraits*/ BitSetTraits>::MakeEmptyArrayBits(Env env)
724{
725 assert(!IsShort(env));
726 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
727 assert(len > 1); // Or else would not require an array.
728 BitSetShortLongRep res = (BitSetShortLongRep)(BitSetTraits::Alloc(env, len * sizeof(size_t)));
729 for (unsigned i = 0; i < len; i++)
730 {
731 res[i] = 0;
732 }
733 return res;
734}
735
736template <typename Env, typename BitSetTraits>
737BitSetShortLongRep BitSetOps</*BitSetType*/ BitSetShortLongRep,
738 /*Brand*/ BSShortLong,
739 /*Env*/ Env,
740 /*BitSetTraits*/ BitSetTraits>::MakeFullArrayBits(Env env)
741{
742 assert(!IsShort(env));
743 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
744 assert(len > 1); // Or else would not require an array.
745 BitSetShortLongRep res = (BitSetShortLongRep)(BitSetTraits::Alloc(env, len * sizeof(size_t)));
746 for (unsigned i = 0; i < len - 1; i++)
747 {
748 res[i] = size_t(-1);
749 }
750 // Start with all ones, shift in zeros in the last elem.
751 unsigned lastElemBits = (BitSetTraits::GetSize(env) - 1) % BitsInSizeT + 1;
752 res[len - 1] = (size_t(-1) >> (BitsInSizeT - lastElemBits));
753 return res;
754}
755
756template <typename Env, typename BitSetTraits>
757bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
758 /*Brand*/ BSShortLong,
759 /*Env*/ Env,
760 /*BitSetTraits*/ BitSetTraits>::IsMemberLong(Env env, BitSetShortLongRep bs, unsigned i)
761{
762 assert(!IsShort(env));
763 unsigned index = i / BitsInSizeT;
764 unsigned bitInElem = (i % BitsInSizeT);
765 size_t mask = ((size_t)1) << bitInElem;
766 return (bs[index] & mask) != 0;
767}
768
769template <typename Env, typename BitSetTraits>
770void BitSetOps</*BitSetType*/ BitSetShortLongRep,
771 /*Brand*/ BSShortLong,
772 /*Env*/ Env,
773 /*BitSetTraits*/ BitSetTraits>::IntersectionDLong(Env env,
774 BitSetShortLongRep& bs1,
775 BitSetShortLongRep bs2)
776{
777 assert(!IsShort(env));
778 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
779 for (unsigned i = 0; i < len; i++)
780 {
781 bs1[i] &= bs2[i];
782 }
783}
784
785template <typename Env, typename BitSetTraits>
786bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
787 /*Brand*/ BSShortLong,
788 /*Env*/ Env,
789 /*BitSetTraits*/ BitSetTraits>::IsEmptyIntersectionLong(Env env,
790 BitSetShortLongRep bs1,
791 BitSetShortLongRep bs2)
792{
793 assert(!IsShort(env));
794 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
795 for (unsigned i = 0; i < len; i++)
796 {
797 if ((bs1[i] & bs2[i]) != 0)
798 {
799 return false;
800 }
801 }
802 return true;
803}
804
805template <typename Env, typename BitSetTraits>
806bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
807 /*Brand*/ BSShortLong,
808 /*Env*/ Env,
809 /*BitSetTraits*/ BitSetTraits>::IsEmptyUnionLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
810{
811 assert(!IsShort(env));
812 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
813 for (unsigned i = 0; i < len; i++)
814 {
815 if ((bs1[i] | bs2[i]) != 0)
816 {
817 return false;
818 }
819 }
820 return true;
821}
822
823template <typename Env, typename BitSetTraits>
824void BitSetOps</*BitSetType*/ BitSetShortLongRep,
825 /*Brand*/ BSShortLong,
826 /*Env*/ Env,
827 /*BitSetTraits*/ BitSetTraits>::DataFlowDLong(Env env,
828 BitSetShortLongRep& out,
829 const BitSetShortLongRep gen,
830 const BitSetShortLongRep in)
831{
832 assert(!IsShort(env));
833 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
834 for (unsigned i = 0; i < len; i++)
835 {
836 out[i] = out[i] & (gen[i] | in[i]);
837 }
838}
839
840template <typename Env, typename BitSetTraits>
841void BitSetOps</*BitSetType*/ BitSetShortLongRep,
842 /*Brand*/ BSShortLong,
843 /*Env*/ Env,
844 /*BitSetTraits*/ BitSetTraits>::LivenessDLong(Env env,
845 BitSetShortLongRep& in,
846 const BitSetShortLongRep def,
847 const BitSetShortLongRep use,
848 const BitSetShortLongRep out)
849{
850 assert(!IsShort(env));
851 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
852 for (unsigned i = 0; i < len; i++)
853 {
854 in[i] = use[i] | (out[i] & ~def[i]);
855 }
856}
857
858template <typename Env, typename BitSetTraits>
859bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
860 /*Brand*/ BSShortLong,
861 /*Env*/ Env,
862 /*BitSetTraits*/ BitSetTraits>::EqualLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
863{
864 assert(!IsShort(env));
865 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
866 for (unsigned i = 0; i < len; i++)
867 {
868 if (bs1[i] != bs2[i])
869 {
870 return false;
871 }
872 }
873 return true;
874}
875
876template <typename Env, typename BitSetTraits>
877bool BitSetOps</*BitSetType*/ BitSetShortLongRep,
878 /*Brand*/ BSShortLong,
879 /*Env*/ Env,
880 /*BitSetTraits*/ BitSetTraits>::IsSubsetLong(Env env, BitSetShortLongRep bs1, BitSetShortLongRep bs2)
881{
882 assert(!IsShort(env));
883 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
884 for (unsigned i = 0; i < len; i++)
885 {
886 if ((bs1[i] & bs2[i]) != bs1[i])
887 {
888 return false;
889 }
890 }
891 return true;
892}
893
894#ifdef DEBUG
895template <typename Env, typename BitSetTraits>
896const char* BitSetOps</*BitSetType*/ BitSetShortLongRep,
897 /*Brand*/ BSShortLong,
898 /*Env*/ Env,
899 /*BitSetTraits*/ BitSetTraits>::ToStringLong(Env env, BitSetShortLongRep bs)
900{
901 assert(!IsShort(env));
902 unsigned len = BitSetTraits::GetArrSize(env, sizeof(size_t));
903 const int CharsForSizeT = sizeof(size_t) * 2;
904 unsigned allocSz = len * CharsForSizeT + 4;
905 unsigned remaining = allocSz;
906 char* res = (char*)BitSetTraits::DebugAlloc(env, allocSz);
907 char* temp = res;
908 for (unsigned i = len; 0 < i; i--)
909 {
910 size_t bits = bs[i - 1];
911 for (unsigned bytesDone = 0; bytesDone < sizeof(size_t); bytesDone += sizeof(unsigned))
912 {
913 unsigned bits0 = (unsigned)bits;
914 sprintf_s(temp, remaining, "%08X", bits0);
915 temp += 8;
916 remaining -= 8;
917 bytesDone += 4;
918 assert(sizeof(unsigned) == 4);
919 // Doing this twice by 16, rather than once by 32, avoids warnings when size_t == unsigned.
920 bits = bits >> 16;
921 bits = bits >> 16;
922 }
923 }
924 return res;
925}
926#endif
927
928#endif // bitSetAsShortLong_DEFINED
929