xref: /llvm-project/llvm/unittests/ADT/BitVectorTest.cpp (revision 27f1895f53d435ad0cafe6396f5eb680f95e95c7)
1 //===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector tests --------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/ADT/BitVector.h"
10 #include "llvm/ADT/DenseSet.h"
11 #include "llvm/ADT/SmallBitVector.h"
12 #include "gtest/gtest.h"
13 
14 using namespace llvm;
15 
16 namespace {
17 
18 // Test fixture
19 template <typename T>
20 class BitVectorTest : public ::testing::Test { };
21 
22 // Test both BitVector and SmallBitVector with the same suite of tests.
23 typedef ::testing::Types<BitVector, SmallBitVector> BitVectorTestTypes;
24 TYPED_TEST_CASE(BitVectorTest, BitVectorTestTypes);
25 
26 TYPED_TEST(BitVectorTest, TrivialOperation) {
27   TypeParam Vec;
28   EXPECT_EQ(0U, Vec.count());
29   EXPECT_EQ(0U, Vec.size());
30   EXPECT_FALSE(Vec.any());
31   EXPECT_TRUE(Vec.all());
32   EXPECT_TRUE(Vec.none());
33   EXPECT_TRUE(Vec.empty());
34 
35   Vec.resize(5, true);
36   EXPECT_EQ(5U, Vec.count());
37   EXPECT_EQ(5U, Vec.size());
38   EXPECT_TRUE(Vec.any());
39   EXPECT_TRUE(Vec.all());
40   EXPECT_FALSE(Vec.none());
41   EXPECT_FALSE(Vec.empty());
42 
43   Vec.resize(11);
44   EXPECT_EQ(5U, Vec.count());
45   EXPECT_EQ(11U, Vec.size());
46   EXPECT_TRUE(Vec.any());
47   EXPECT_FALSE(Vec.all());
48   EXPECT_FALSE(Vec.none());
49   EXPECT_FALSE(Vec.empty());
50 
51   TypeParam Inv = Vec;
52   Inv.flip();
53   EXPECT_EQ(6U, Inv.count());
54   EXPECT_EQ(11U, Inv.size());
55   EXPECT_TRUE(Inv.any());
56   EXPECT_FALSE(Inv.all());
57   EXPECT_FALSE(Inv.none());
58   EXPECT_FALSE(Inv.empty());
59 
60   EXPECT_FALSE(Inv == Vec);
61   EXPECT_TRUE(Inv != Vec);
62   Vec.flip();
63   EXPECT_TRUE(Inv == Vec);
64   EXPECT_FALSE(Inv != Vec);
65 
66   // Add some "interesting" data to Vec.
67   Vec.resize(23, true);
68   Vec.resize(25, false);
69   Vec.resize(26, true);
70   Vec.resize(29, false);
71   Vec.resize(33, true);
72   Vec.resize(57, false);
73   unsigned Count = 0;
74   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
75     ++Count;
76     EXPECT_TRUE(Vec[i]);
77     EXPECT_TRUE(Vec.test(i));
78   }
79   EXPECT_EQ(Count, Vec.count());
80   EXPECT_EQ(Count, 23u);
81   EXPECT_FALSE(Vec[0]);
82   EXPECT_TRUE(Vec[32]);
83   EXPECT_FALSE(Vec[56]);
84   Vec.resize(61, false);
85 
86   TypeParam Copy = Vec;
87   TypeParam Alt(3, false);
88   Alt.resize(6, true);
89   std::swap(Alt, Vec);
90   EXPECT_TRUE(Copy == Alt);
91   EXPECT_TRUE(Vec.size() == 6);
92   EXPECT_TRUE(Vec.count() == 3);
93   EXPECT_TRUE(Vec.find_first() == 3);
94   std::swap(Copy, Vec);
95 
96   // Add some more "interesting" data.
97   Vec.resize(68, true);
98   Vec.resize(78, false);
99   Vec.resize(89, true);
100   Vec.resize(90, false);
101   Vec.resize(91, true);
102   Vec.resize(130, false);
103   Count = 0;
104   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
105     ++Count;
106     EXPECT_TRUE(Vec[i]);
107     EXPECT_TRUE(Vec.test(i));
108   }
109   EXPECT_EQ(Count, Vec.count());
110   EXPECT_EQ(Count, 42u);
111   EXPECT_FALSE(Vec[0]);
112   EXPECT_TRUE(Vec[32]);
113   EXPECT_FALSE(Vec[60]);
114   EXPECT_FALSE(Vec[129]);
115 
116   Vec.flip(60);
117   EXPECT_TRUE(Vec[60]);
118   EXPECT_EQ(Count + 1, Vec.count());
119   Vec.flip(60);
120   EXPECT_FALSE(Vec[60]);
121   EXPECT_EQ(Count, Vec.count());
122 
123   Vec.reset(32);
124   EXPECT_FALSE(Vec[32]);
125   EXPECT_EQ(Count - 1, Vec.count());
126   Vec.set(32);
127   EXPECT_TRUE(Vec[32]);
128   EXPECT_EQ(Count, Vec.count());
129 
130   Vec.flip();
131   EXPECT_EQ(Vec.size() - Count, Vec.count());
132 
133   Vec.reset();
134   EXPECT_EQ(0U, Vec.count());
135   EXPECT_EQ(130U, Vec.size());
136   EXPECT_FALSE(Vec.any());
137   EXPECT_FALSE(Vec.all());
138   EXPECT_TRUE(Vec.none());
139   EXPECT_FALSE(Vec.empty());
140 
141   Vec.flip();
142   EXPECT_EQ(130U, Vec.count());
143   EXPECT_EQ(130U, Vec.size());
144   EXPECT_TRUE(Vec.any());
145   EXPECT_TRUE(Vec.all());
146   EXPECT_FALSE(Vec.none());
147   EXPECT_FALSE(Vec.empty());
148 
149   Vec.resize(64);
150   EXPECT_EQ(64U, Vec.count());
151   EXPECT_EQ(64U, Vec.size());
152   EXPECT_TRUE(Vec.any());
153   EXPECT_TRUE(Vec.all());
154   EXPECT_FALSE(Vec.none());
155   EXPECT_FALSE(Vec.empty());
156 
157   Vec.flip();
158   EXPECT_EQ(0U, Vec.count());
159   EXPECT_EQ(64U, Vec.size());
160   EXPECT_FALSE(Vec.any());
161   EXPECT_FALSE(Vec.all());
162   EXPECT_TRUE(Vec.none());
163   EXPECT_FALSE(Vec.empty());
164 
165   Inv = TypeParam().flip();
166   EXPECT_EQ(0U, Inv.count());
167   EXPECT_EQ(0U, Inv.size());
168   EXPECT_FALSE(Inv.any());
169   EXPECT_TRUE(Inv.all());
170   EXPECT_TRUE(Inv.none());
171   EXPECT_TRUE(Inv.empty());
172 
173   Vec.clear();
174   EXPECT_EQ(0U, Vec.count());
175   EXPECT_EQ(0U, Vec.size());
176   EXPECT_FALSE(Vec.any());
177   EXPECT_TRUE(Vec.all());
178   EXPECT_TRUE(Vec.none());
179   EXPECT_TRUE(Vec.empty());
180 }
181 
182 TYPED_TEST(BitVectorTest, Equality) {
183   TypeParam A;
184   TypeParam B;
185   EXPECT_TRUE(A == B);
186   A.resize(10);
187   EXPECT_FALSE(A == B);
188   B.resize(10);
189   EXPECT_TRUE(A == B);
190   A.set(5);
191   EXPECT_FALSE(A == B);
192   B.set(5);
193   EXPECT_TRUE(A == B);
194   A.resize(20);
195   EXPECT_FALSE(A == B);
196   B.resize(20);
197   EXPECT_TRUE(A == B);
198 }
199 
200 TYPED_TEST(BitVectorTest, SimpleFindOpsMultiWord) {
201   TypeParam A;
202 
203   // Test finding next set and unset bits in a BitVector with multiple words
204   A.resize(100);
205   A.set(12);
206   A.set(13);
207   A.set(75);
208 
209   EXPECT_EQ(75, A.find_last());
210   EXPECT_EQ(12, A.find_first());
211   EXPECT_EQ(13, A.find_next(12));
212   EXPECT_EQ(75, A.find_next(13));
213   EXPECT_EQ(-1, A.find_next(75));
214 
215   EXPECT_EQ(-1, A.find_prev(12));
216   EXPECT_EQ(12, A.find_prev(13));
217   EXPECT_EQ(13, A.find_prev(75));
218   EXPECT_EQ(75, A.find_prev(90));
219 
220   EXPECT_EQ(0, A.find_first_unset());
221   EXPECT_EQ(99, A.find_last_unset());
222   EXPECT_EQ(14, A.find_next_unset(11));
223   EXPECT_EQ(14, A.find_next_unset(12));
224   EXPECT_EQ(14, A.find_next_unset(13));
225   EXPECT_EQ(16, A.find_next_unset(15));
226   EXPECT_EQ(76, A.find_next_unset(74));
227   EXPECT_EQ(76, A.find_next_unset(75));
228   EXPECT_EQ(-1, A.find_next_unset(99));
229 
230   A.set(0, 100);
231   EXPECT_EQ(100U, A.count());
232   EXPECT_EQ(0, A.find_first());
233   EXPECT_EQ(-1, A.find_first_unset());
234   EXPECT_EQ(-1, A.find_last_unset());
235   EXPECT_EQ(99, A.find_last());
236   EXPECT_EQ(99, A.find_next(98));
237 
238   A.reset(0, 100);
239   EXPECT_EQ(0U, A.count());
240   EXPECT_EQ(-1, A.find_first());
241   EXPECT_EQ(-1, A.find_last());
242   EXPECT_EQ(0, A.find_first_unset());
243   EXPECT_EQ(99, A.find_last_unset());
244   EXPECT_EQ(99, A.find_next_unset(98));
245 }
246 
247 // Test finding next set and unset bits in a BitVector/SmallBitVector within a
248 // uintptr_t - check both 32-bit (Multi) and 64-bit (Small) targets.
249 TYPED_TEST(BitVectorTest, SimpleFindOps64Bit) {
250   TypeParam A;
251 
252   A.resize(57);
253   A.set(12);
254   A.set(13);
255   A.set(47);
256 
257   EXPECT_EQ(47, A.find_last());
258   EXPECT_EQ(12, A.find_first());
259   EXPECT_EQ(13, A.find_next(12));
260   EXPECT_EQ(47, A.find_next(13));
261   EXPECT_EQ(-1, A.find_next(47));
262 
263   EXPECT_EQ(-1, A.find_prev(12));
264   EXPECT_EQ(12, A.find_prev(13));
265   EXPECT_EQ(13, A.find_prev(47));
266   EXPECT_EQ(47, A.find_prev(56));
267 
268   EXPECT_EQ(0, A.find_first_unset());
269   EXPECT_EQ(56, A.find_last_unset());
270   EXPECT_EQ(14, A.find_next_unset(11));
271   EXPECT_EQ(14, A.find_next_unset(12));
272   EXPECT_EQ(14, A.find_next_unset(13));
273   EXPECT_EQ(16, A.find_next_unset(15));
274   EXPECT_EQ(48, A.find_next_unset(46));
275   EXPECT_EQ(48, A.find_next_unset(47));
276   EXPECT_EQ(-1, A.find_next_unset(56));
277 }
278 
279 // Check if a SmallBitVector is in small mode. This check is used in tests
280 // that run for both SmallBitVector and BitVector. This check doesn't apply
281 // to BitVector so we provide an overload that returns true to get the tests
282 // to compile.
283 static bool SmallBitVectorIsSmallMode(const SmallBitVector &bv) {
284   return bv.isSmall();
285 }
286 static bool SmallBitVectorIsSmallMode(const BitVector &) { return true; }
287 
288 // These tests are intended to exercise the single-word case of BitVector
289 // and the small-mode case of SmallBitVector.
290 TYPED_TEST(BitVectorTest, SimpleFindOpsSingleWord) {
291   // Test finding in an empty BitVector.
292   TypeParam A;
293   ASSERT_TRUE(SmallBitVectorIsSmallMode(A));
294   EXPECT_EQ(-1, A.find_first());
295   EXPECT_EQ(-1, A.find_last());
296   EXPECT_EQ(-1, A.find_first_unset());
297   EXPECT_EQ(-1, A.find_last_unset());
298 
299   A.resize(20);
300   A.set(3);
301   A.set(4);
302   A.set(16);
303   ASSERT_TRUE(SmallBitVectorIsSmallMode(A));
304   EXPECT_EQ(16, A.find_last());
305   EXPECT_EQ(3, A.find_first());
306   EXPECT_EQ(3, A.find_next(1));
307   EXPECT_EQ(4, A.find_next(3));
308   EXPECT_EQ(16, A.find_next(4));
309   EXPECT_EQ(-1, A.find_next(16));
310 
311   EXPECT_EQ(-1, A.find_prev(3));
312   EXPECT_EQ(3, A.find_prev(4));
313   EXPECT_EQ(4, A.find_prev(16));
314   EXPECT_EQ(16, A.find_prev(18));
315 
316   EXPECT_EQ(0, A.find_first_unset());
317   EXPECT_EQ(19, A.find_last_unset());
318   EXPECT_EQ(5, A.find_next_unset(3));
319   EXPECT_EQ(5, A.find_next_unset(4));
320   EXPECT_EQ(13, A.find_next_unset(12));
321   EXPECT_EQ(17, A.find_next_unset(15));
322 }
323 
324 TEST(BitVectorTest, FindInRangeMultiWord) {
325   BitVector Vec;
326 
327   Vec.resize(200);
328   Vec.set(3, 7);
329   Vec.set(24, 35);
330   Vec.set(50, 70);
331   Vec.set(150);
332   Vec.set(152);
333   Vec.set(154);
334 
335   // find first
336   EXPECT_EQ(-1, Vec.find_first_in(0, 0));
337   EXPECT_EQ(-1, Vec.find_first_in(24, 24));
338   EXPECT_EQ(-1, Vec.find_first_in(7, 24));
339 
340   EXPECT_EQ(3, Vec.find_first_in(0, 10));
341   EXPECT_EQ(4, Vec.find_first_in(4, 10));
342   EXPECT_EQ(150, Vec.find_first_in(100, 200));
343   EXPECT_EQ(152, Vec.find_first_in(151, 200));
344   EXPECT_EQ(154, Vec.find_first_in(153, 200));
345 
346   EXPECT_EQ(-1, Vec.find_first_in(155, 200));
347   Vec.set(199);
348   EXPECT_EQ(199, Vec.find_first_in(199, 200));
349   Vec.reset(199);
350 
351   // find last
352   EXPECT_EQ(-1, Vec.find_last_in(0, 0));
353   EXPECT_EQ(-1, Vec.find_last_in(24, 24));
354   EXPECT_EQ(-1, Vec.find_last_in(7, 24));
355 
356   EXPECT_EQ(6, Vec.find_last_in(0, 10));
357   EXPECT_EQ(5, Vec.find_last_in(0, 6));
358   EXPECT_EQ(154, Vec.find_last_in(100, 155));
359   EXPECT_EQ(152, Vec.find_last_in(100, 154));
360   EXPECT_EQ(150, Vec.find_last_in(100, 152));
361   EXPECT_EQ(-1, Vec.find_last_in(100, 150));
362   Vec.set(199);
363   EXPECT_EQ(199, Vec.find_last_in(199, 200));
364   Vec.reset(199);
365 
366   // find first unset
367   EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));
368   EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));
369   EXPECT_EQ(-1, Vec.find_first_unset_in(24, 35));
370 
371   EXPECT_EQ(0, Vec.find_first_unset_in(0, 10));
372   EXPECT_EQ(1, Vec.find_first_unset_in(1, 10));
373   EXPECT_EQ(7, Vec.find_first_unset_in(5, 25));
374   EXPECT_EQ(151, Vec.find_first_unset_in(150, 200));
375   EXPECT_EQ(151, Vec.find_first_unset_in(151, 200));
376   EXPECT_EQ(153, Vec.find_first_unset_in(152, 200));
377   EXPECT_EQ(153, Vec.find_first_unset_in(153, 200));
378   EXPECT_EQ(155, Vec.find_first_unset_in(154, 200));
379   EXPECT_EQ(155, Vec.find_first_unset_in(155, 200));
380   EXPECT_EQ(199, Vec.find_first_unset_in(199, 200));
381 
382   // find last unset
383   EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));
384   EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));
385   EXPECT_EQ(-1, Vec.find_last_unset_in(24, 35));
386 
387   EXPECT_EQ(9, Vec.find_last_unset_in(0, 10));
388   EXPECT_EQ(8, Vec.find_last_unset_in(0, 9));
389   EXPECT_EQ(2, Vec.find_last_unset_in(0, 7));
390   EXPECT_EQ(149, Vec.find_last_unset_in(100, 151));
391   EXPECT_EQ(151, Vec.find_last_unset_in(100, 152));
392   EXPECT_EQ(151, Vec.find_last_unset_in(100, 153));
393   EXPECT_EQ(153, Vec.find_last_unset_in(100, 154));
394   EXPECT_EQ(153, Vec.find_last_unset_in(100, 155));
395   EXPECT_EQ(155, Vec.find_last_unset_in(100, 156));
396   EXPECT_EQ(199, Vec.find_last_unset_in(199, 200));
397 }
398 
399 TEST(BitVectorTest, FindInRangeSingleWord) {
400   // When the bit vector contains only a single word, this is slightly different
401   // than when the bit vector contains multiple words, because masks are applied
402   // to the front and back of the same word.  So make sure this works.
403   BitVector Vec;
404 
405   Vec.resize(25);
406   Vec.set(2, 4);
407   Vec.set(6, 9);
408   Vec.set(12, 15);
409   Vec.set(19);
410   Vec.set(21);
411   Vec.set(23);
412 
413   // find first
414   EXPECT_EQ(-1, Vec.find_first_in(0, 0));
415   EXPECT_EQ(-1, Vec.find_first_in(24, 24));
416   EXPECT_EQ(-1, Vec.find_first_in(9, 12));
417 
418   EXPECT_EQ(2, Vec.find_first_in(0, 10));
419   EXPECT_EQ(6, Vec.find_first_in(4, 10));
420   EXPECT_EQ(19, Vec.find_first_in(18, 25));
421   EXPECT_EQ(21, Vec.find_first_in(20, 25));
422   EXPECT_EQ(23, Vec.find_first_in(22, 25));
423   EXPECT_EQ(-1, Vec.find_first_in(24, 25));
424 
425   // find last
426   EXPECT_EQ(-1, Vec.find_last_in(0, 0));
427   EXPECT_EQ(-1, Vec.find_last_in(24, 24));
428   EXPECT_EQ(-1, Vec.find_last_in(9, 12));
429 
430   EXPECT_EQ(8, Vec.find_last_in(0, 10));
431   EXPECT_EQ(3, Vec.find_last_in(0, 6));
432   EXPECT_EQ(23, Vec.find_last_in(18, 25));
433   EXPECT_EQ(21, Vec.find_last_in(18, 23));
434   EXPECT_EQ(19, Vec.find_last_in(18, 21));
435   EXPECT_EQ(-1, Vec.find_last_in(18, 19));
436 
437   // find first unset
438   EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0));
439   EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23));
440   EXPECT_EQ(-1, Vec.find_first_unset_in(6, 9));
441 
442   EXPECT_EQ(0, Vec.find_first_unset_in(0, 6));
443   EXPECT_EQ(1, Vec.find_first_unset_in(1, 6));
444   EXPECT_EQ(9, Vec.find_first_unset_in(7, 13));
445   EXPECT_EQ(18, Vec.find_first_unset_in(18, 25));
446   EXPECT_EQ(20, Vec.find_first_unset_in(19, 25));
447   EXPECT_EQ(20, Vec.find_first_unset_in(20, 25));
448   EXPECT_EQ(22, Vec.find_first_unset_in(21, 25));
449   EXPECT_EQ(22, Vec.find_first_unset_in(22, 25));
450   EXPECT_EQ(24, Vec.find_first_unset_in(23, 25));
451   EXPECT_EQ(24, Vec.find_first_unset_in(24, 25));
452 
453   // find last unset
454   EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0));
455   EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23));
456   EXPECT_EQ(-1, Vec.find_last_unset_in(6, 9));
457 
458   EXPECT_EQ(5, Vec.find_last_unset_in(0, 6));
459   EXPECT_EQ(4, Vec.find_last_unset_in(0, 5));
460   EXPECT_EQ(1, Vec.find_last_unset_in(0, 4));
461   EXPECT_EQ(11, Vec.find_last_unset_in(7, 13));
462   EXPECT_EQ(24, Vec.find_last_unset_in(18, 25));
463   EXPECT_EQ(22, Vec.find_last_unset_in(18, 24));
464   EXPECT_EQ(22, Vec.find_last_unset_in(18, 23));
465   EXPECT_EQ(20, Vec.find_last_unset_in(18, 22));
466   EXPECT_EQ(20, Vec.find_last_unset_in(18, 21));
467   EXPECT_EQ(18, Vec.find_last_unset_in(18, 20));
468   EXPECT_EQ(18, Vec.find_last_unset_in(18, 19));
469 }
470 
471 TYPED_TEST(BitVectorTest, CompoundAssignment) {
472   TypeParam A;
473   A.resize(10);
474   A.set(4);
475   A.set(7);
476 
477   TypeParam B;
478   B.resize(50);
479   B.set(5);
480   B.set(18);
481 
482   A |= B;
483   EXPECT_TRUE(A.test(4));
484   EXPECT_TRUE(A.test(5));
485   EXPECT_TRUE(A.test(7));
486   EXPECT_TRUE(A.test(18));
487   EXPECT_EQ(4U, A.count());
488   EXPECT_EQ(50U, A.size());
489 
490   B.resize(10);
491   B.set();
492   B.reset(2);
493   B.reset(7);
494   A &= B;
495   EXPECT_FALSE(A.test(2));
496   EXPECT_FALSE(A.test(7));
497   EXPECT_TRUE(A.test(4));
498   EXPECT_TRUE(A.test(5));
499   EXPECT_EQ(2U, A.count());
500   EXPECT_EQ(50U, A.size());
501 
502   B.resize(100);
503   B.set();
504 
505   A ^= B;
506   EXPECT_TRUE(A.test(2));
507   EXPECT_TRUE(A.test(7));
508   EXPECT_EQ(98U, A.count());
509   EXPECT_EQ(100U, A.size());
510 }
511 
512 // Test SmallBitVector operations with mixed big/small representations
513 TYPED_TEST(BitVectorTest, MixedBigSmall) {
514   {
515     TypeParam Big;
516     TypeParam Small;
517 
518     Big.reserve(100);
519     Big.resize(20);
520     Small.resize(10);
521 
522     Small.set(0);
523     Small.set(1);
524     Big.set(0);
525     Big.set(2);
526     Big.set(16);
527 
528     Small &= Big;
529     EXPECT_TRUE(Small.test(0));
530     EXPECT_EQ(1u, Small.count());
531     // FIXME BitVector and SmallBitVector behave differently here.
532     // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())
533     // but BitVector does not.
534     // EXPECT_EQ(20u, Small.size());
535   }
536 
537   {
538     TypeParam Big;
539     TypeParam Small;
540 
541     Big.reserve(100);
542     Big.resize(20);
543     Small.resize(10);
544 
545     Small.set(0);
546     Small.set(1);
547     Big.set(0);
548     Big.set(2);
549     Big.set(16);
550 
551     Big &= Small;
552     EXPECT_TRUE(Big.test(0));
553     EXPECT_EQ(1u, Big.count());
554     // FIXME BitVector and SmallBitVector behave differently here.
555     // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size())
556     // but BitVector does not.
557     // EXPECT_EQ(20u, Big.size());
558   }
559 
560   {
561     TypeParam Big;
562     TypeParam Small;
563 
564     Big.reserve(100);
565     Big.resize(20);
566     Small.resize(10);
567 
568     Small.set(0);
569     Small.set(1);
570     Big.set(0);
571     Big.set(2);
572     Big.set(16);
573 
574     Small |= Big;
575     EXPECT_TRUE(Small.test(0));
576     EXPECT_TRUE(Small.test(1));
577     EXPECT_TRUE(Small.test(2));
578     EXPECT_TRUE(Small.test(16));
579     EXPECT_EQ(4u, Small.count());
580     EXPECT_EQ(20u, Small.size());
581   }
582 
583   {
584     TypeParam Big;
585     TypeParam Small;
586 
587     Big.reserve(100);
588     Big.resize(20);
589     Small.resize(10);
590 
591     Small.set(0);
592     Small.set(1);
593     Big.set(0);
594     Big.set(2);
595     Big.set(16);
596 
597     Big |= Small;
598     EXPECT_TRUE(Big.test(0));
599     EXPECT_TRUE(Big.test(1));
600     EXPECT_TRUE(Big.test(2));
601     EXPECT_TRUE(Big.test(16));
602     EXPECT_EQ(4u, Big.count());
603     EXPECT_EQ(20u, Big.size());
604   }
605 
606   {
607     TypeParam Big;
608     TypeParam Small;
609 
610     Big.reserve(100);
611     Big.resize(20);
612     Small.resize(10);
613 
614     Small.set(0);
615     Small.set(1);
616     Big.set(0);
617     Big.set(2);
618     Big.set(16);
619 
620     Small ^= Big;
621     EXPECT_TRUE(Small.test(1));
622     EXPECT_TRUE(Small.test(2));
623     EXPECT_TRUE(Small.test(16));
624     EXPECT_EQ(3u, Small.count());
625     EXPECT_EQ(20u, Small.size());
626   }
627 
628   {
629     TypeParam Big;
630     TypeParam Small;
631 
632     Big.reserve(100);
633     Big.resize(20);
634     Small.resize(10);
635 
636     Small.set(0);
637     Small.set(1);
638     Big.set(0);
639     Big.set(2);
640     Big.set(16);
641 
642     Big ^= Small;
643     EXPECT_TRUE(Big.test(1));
644     EXPECT_TRUE(Big.test(2));
645     EXPECT_TRUE(Big.test(16));
646     EXPECT_EQ(3u, Big.count());
647     EXPECT_EQ(20u, Big.size());
648   }
649 
650   {
651     TypeParam Big;
652     TypeParam Small;
653 
654     Big.reserve(100);
655     Big.resize(20);
656     Small.resize(10);
657 
658     Small.set(0);
659     Small.set(1);
660     Big.set(0);
661     Big.set(2);
662     Big.set(16);
663 
664     Small.reset(Big);
665     EXPECT_TRUE(Small.test(1));
666     EXPECT_EQ(1u, Small.count());
667     EXPECT_EQ(10u, Small.size());
668   }
669 
670   {
671     TypeParam Big;
672     TypeParam Small;
673 
674     Big.reserve(100);
675     Big.resize(20);
676     Small.resize(10);
677 
678     Small.set(0);
679     Small.set(1);
680     Big.set(0);
681     Big.set(2);
682     Big.set(16);
683 
684     Big.reset(Small);
685     EXPECT_TRUE(Big.test(2));
686     EXPECT_TRUE(Big.test(16));
687     EXPECT_EQ(2u, Big.count());
688     EXPECT_EQ(20u, Big.size());
689   }
690 
691   {
692     TypeParam Big;
693     TypeParam Small;
694 
695     Big.reserve(100);
696     Big.resize(10);
697     Small.resize(10);
698 
699     Small.set(0);
700     Small.set(1);
701     Big.set(0);
702 
703     EXPECT_FALSE(Big == Small);
704     EXPECT_FALSE(Small == Big);
705     Big.set(1);
706     EXPECT_TRUE(Big == Small);
707     EXPECT_TRUE(Small == Big);
708   }
709 
710   {
711     TypeParam Big;
712     TypeParam Small;
713 
714     Big.reserve(100);
715     Big.resize(20);
716     Small.resize(10);
717 
718     Small.set(0);
719     Big.set(1);
720 
721     EXPECT_FALSE(Small.anyCommon(Big));
722     EXPECT_FALSE(Big.anyCommon(Small));
723     Big.set(0);
724     EXPECT_TRUE(Small.anyCommon(Big));
725     EXPECT_TRUE(Big.anyCommon(Small));
726   }
727 
728   {
729     TypeParam Big;
730     TypeParam Small;
731 
732     Big.reserve(100);
733     Big.resize(10);
734     Small.resize(10);
735 
736     Small.set(0);
737     Small.set(1);
738     Big.set(0);
739 
740     EXPECT_TRUE(Small.test(Big));
741     EXPECT_FALSE(Big.test(Small));
742     Big.set(1);
743     EXPECT_FALSE(Small.test(Big));
744     EXPECT_FALSE(Big.test(Small));
745   }
746 }
747 
748 TYPED_TEST(BitVectorTest, ProxyIndex) {
749   TypeParam Vec(3);
750   EXPECT_TRUE(Vec.none());
751   Vec[0] = Vec[1] = Vec[2] = true;
752   EXPECT_EQ(Vec.size(), Vec.count());
753   Vec[2] = Vec[1] = Vec[0] = false;
754   EXPECT_TRUE(Vec.none());
755 }
756 
757 TYPED_TEST(BitVectorTest, PortableBitMask) {
758   TypeParam A;
759   const uint32_t Mask1[] = { 0x80000000, 6, 5 };
760 
761   A.resize(10);
762   A.setBitsInMask(Mask1, 1);
763   EXPECT_EQ(10u, A.size());
764   EXPECT_FALSE(A.test(0));
765 
766   A.resize(32);
767   A.setBitsInMask(Mask1, 1);
768   EXPECT_FALSE(A.test(0));
769   EXPECT_TRUE(A.test(31));
770   EXPECT_EQ(1u, A.count());
771 
772   A.resize(33);
773   A.setBitsInMask(Mask1, 1);
774   EXPECT_EQ(1u, A.count());
775   A.setBitsInMask(Mask1, 2);
776   EXPECT_EQ(1u, A.count());
777 
778   A.resize(34);
779   A.setBitsInMask(Mask1, 2);
780   EXPECT_EQ(2u, A.count());
781 
782   A.resize(65);
783   A.setBitsInMask(Mask1, 3);
784   EXPECT_EQ(4u, A.count());
785 
786   A.setBitsNotInMask(Mask1, 1);
787   EXPECT_EQ(32u+3u, A.count());
788 
789   A.setBitsNotInMask(Mask1, 3);
790   EXPECT_EQ(65u, A.count());
791 
792   A.resize(96);
793   EXPECT_EQ(65u, A.count());
794 
795   A.clear();
796   A.resize(128);
797   A.setBitsNotInMask(Mask1, 3);
798   EXPECT_EQ(96u-5u, A.count());
799 
800   A.clearBitsNotInMask(Mask1, 1);
801   EXPECT_EQ(64-4u, A.count());
802 }
803 
804 TYPED_TEST(BitVectorTest, BinOps) {
805   TypeParam A;
806   TypeParam B;
807 
808   A.resize(65);
809   EXPECT_FALSE(A.anyCommon(B));
810   EXPECT_FALSE(B.anyCommon(B));
811 
812   B.resize(64);
813   A.set(64);
814   EXPECT_FALSE(A.anyCommon(B));
815   EXPECT_FALSE(B.anyCommon(A));
816 
817   B.set(63);
818   EXPECT_FALSE(A.anyCommon(B));
819   EXPECT_FALSE(B.anyCommon(A));
820 
821   A.set(63);
822   EXPECT_TRUE(A.anyCommon(B));
823   EXPECT_TRUE(B.anyCommon(A));
824 
825   B.resize(70);
826   B.set(64);
827   B.reset(63);
828   A.resize(64);
829   EXPECT_FALSE(A.anyCommon(B));
830   EXPECT_FALSE(B.anyCommon(A));
831 }
832 
833 typedef std::vector<std::pair<int, int>> RangeList;
834 
835 template <typename VecType>
836 static inline VecType createBitVector(uint32_t Size,
837                                       const RangeList &setRanges) {
838   VecType V;
839   V.resize(Size);
840   for (auto &R : setRanges)
841     V.set(R.first, R.second);
842   return V;
843 }
844 
845 TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) {
846   // Test that shift ops work when the desired shift amount is less
847   // than one word.
848 
849   // 1. Case where the number of bits in the BitVector also fit into a single
850   // word.
851   TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}});
852   TypeParam B = A;
853 
854   EXPECT_EQ(4U, A.count());
855   EXPECT_TRUE(A.test(2));
856   EXPECT_TRUE(A.test(3));
857   EXPECT_TRUE(A.test(8));
858   EXPECT_TRUE(A.test(9));
859 
860   A >>= 1;
861   EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A);
862 
863   A <<= 1;
864   EXPECT_EQ(B, A);
865 
866   A >>= 10;
867   EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
868 
869   A = B;
870   A <<= 10;
871   EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
872 
873   // 2. Case where the number of bits in the BitVector do not fit into a single
874   // word.
875 
876   // 31----------------------------------------------------------------------0
877   // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
878   A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}});
879   EXPECT_EQ(40U, A.size());
880   EXPECT_EQ(22U, A.count());
881 
882   // 2a. Make sure that left shifting some 1 bits out of the vector works.
883   //   31----------------------------------------------------------------------0
884   // Before:
885   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
886   // After:
887   //   XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
888   A <<= 9;
889   EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A);
890 
891   // 2b. Make sure that keeping the number of one bits unchanged works.
892   //   31----------------------------------------------------------------------0
893   // Before:
894   //   XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
895   // After:
896   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
897   A >>= 6;
898   EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A);
899 
900   // 2c. Make sure that right shifting some 1 bits out of the vector works.
901   //   31----------------------------------------------------------------------0
902   // Before:
903   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
904   // After:
905   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111
906   A >>= 10;
907   EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A);
908 
909   // 3. Big test.
910   A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
911   A <<= 29;
912   EXPECT_EQ(createBitVector<TypeParam>(
913                 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}),
914             A);
915 }
916 
917 TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) {
918   // Test that shift ops work when the desired shift amount is greater than or
919   // equal to the size of a single word.
920   auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
921 
922   // Make a copy so we can re-use it later.
923   auto B = A;
924 
925   // 1. Shift left by an exact multiple of the word size.  This should invoke
926   // only a memmove and no per-word bit operations.
927   A <<= 64;
928   auto Expected = createBitVector<TypeParam>(
929       300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}});
930   EXPECT_EQ(Expected, A);
931 
932   // 2. Shift left by a non multiple of the word size.  This should invoke both
933   // a memmove and per-word bit operations.
934   A = B;
935   A <<= 93;
936   EXPECT_EQ(createBitVector<TypeParam>(
937                 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}),
938             A);
939 
940   // 1. Shift right by an exact multiple of the word size.  This should invoke
941   // only a memmove and no per-word bit operations.
942   A = B;
943   A >>= 64;
944   EXPECT_EQ(
945       createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A);
946 
947   // 2. Shift left by a non multiple of the word size.  This should invoke both
948   // a memmove and per-word bit operations.
949   A = B;
950   A >>= 93;
951   EXPECT_EQ(
952       createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A);
953 }
954 
955 TYPED_TEST(BitVectorTest, RangeOps) {
956   TypeParam A;
957   A.resize(256);
958   A.reset();
959   A.set(1, 255);
960 
961   EXPECT_FALSE(A.test(0));
962   EXPECT_TRUE( A.test(1));
963   EXPECT_TRUE( A.test(23));
964   EXPECT_TRUE( A.test(254));
965   EXPECT_FALSE(A.test(255));
966 
967   TypeParam B;
968   B.resize(256);
969   B.set();
970   B.reset(1, 255);
971 
972   EXPECT_TRUE( B.test(0));
973   EXPECT_FALSE(B.test(1));
974   EXPECT_FALSE(B.test(23));
975   EXPECT_FALSE(B.test(254));
976   EXPECT_TRUE( B.test(255));
977 
978   TypeParam C;
979   C.resize(3);
980   C.reset();
981   C.set(0, 1);
982 
983   EXPECT_TRUE(C.test(0));
984   EXPECT_FALSE( C.test(1));
985   EXPECT_FALSE( C.test(2));
986 
987   TypeParam D;
988   D.resize(3);
989   D.set();
990   D.reset(0, 1);
991 
992   EXPECT_FALSE(D.test(0));
993   EXPECT_TRUE( D.test(1));
994   EXPECT_TRUE( D.test(2));
995 
996   TypeParam E;
997   E.resize(128);
998   E.reset();
999   E.set(1, 33);
1000 
1001   EXPECT_FALSE(E.test(0));
1002   EXPECT_TRUE( E.test(1));
1003   EXPECT_TRUE( E.test(32));
1004   EXPECT_FALSE(E.test(33));
1005 
1006   TypeParam BufferOverrun;
1007   unsigned size = sizeof(unsigned long) * 8;
1008   BufferOverrun.resize(size);
1009   BufferOverrun.reset(0, size);
1010   BufferOverrun.set(0, size);
1011 }
1012 
1013 TYPED_TEST(BitVectorTest, CompoundTestReset) {
1014   TypeParam A(50, true);
1015   TypeParam B(50, false);
1016 
1017   TypeParam C(100, true);
1018   TypeParam D(100, false);
1019 
1020   EXPECT_FALSE(A.test(A));
1021   EXPECT_TRUE(A.test(B));
1022   EXPECT_FALSE(A.test(C));
1023   EXPECT_TRUE(A.test(D));
1024   EXPECT_FALSE(B.test(A));
1025   EXPECT_FALSE(B.test(B));
1026   EXPECT_FALSE(B.test(C));
1027   EXPECT_FALSE(B.test(D));
1028   EXPECT_TRUE(C.test(A));
1029   EXPECT_TRUE(C.test(B));
1030   EXPECT_FALSE(C.test(C));
1031   EXPECT_TRUE(C.test(D));
1032 
1033   A.reset(B);
1034   A.reset(D);
1035   EXPECT_TRUE(A.all());
1036   A.reset(A);
1037   EXPECT_TRUE(A.none());
1038   A.set();
1039   A.reset(C);
1040   EXPECT_TRUE(A.none());
1041   A.set();
1042 
1043   C.reset(A);
1044   EXPECT_EQ(50, C.find_first());
1045   C.reset(C);
1046   EXPECT_TRUE(C.none());
1047 }
1048 
1049 TYPED_TEST(BitVectorTest, MoveConstructor) {
1050   TypeParam A(10, true);
1051   TypeParam B(std::move(A));
1052   // Check that the move ctor leaves the moved-from object in a valid state.
1053   // The following line used to crash.
1054   A = B;
1055 
1056   TypeParam C(10, true);
1057   EXPECT_EQ(C, A);
1058   EXPECT_EQ(C, B);
1059 }
1060 
1061 TYPED_TEST(BitVectorTest, MoveAssignment) {
1062   TypeParam A(10, true);
1063   TypeParam B;
1064   B = std::move(A);
1065   // Check that move assignment leaves the moved-from object in a valid state.
1066   // The following line used to crash.
1067   A = B;
1068 
1069   TypeParam C(10, true);
1070   EXPECT_EQ(C, A);
1071   EXPECT_EQ(C, B);
1072 }
1073 
1074 template<class TypeParam>
1075 static void testEmpty(const TypeParam &A) {
1076   EXPECT_TRUE(A.empty());
1077   EXPECT_EQ((size_t)0, A.size());
1078   EXPECT_EQ((size_t)0, A.count());
1079   EXPECT_FALSE(A.any());
1080   EXPECT_TRUE(A.all());
1081   EXPECT_TRUE(A.none());
1082   EXPECT_EQ(-1, A.find_first());
1083   EXPECT_EQ(A, TypeParam());
1084 }
1085 
1086 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0
1087 TYPED_TEST(BitVectorTest, EmptyVector) {
1088   TypeParam A;
1089   testEmpty(A);
1090 
1091   TypeParam B;
1092   B.reset();
1093   testEmpty(B);
1094 
1095   TypeParam C;
1096   C.clear();
1097   testEmpty(C);
1098 
1099   TypeParam D(A);
1100   testEmpty(D);
1101 
1102   TypeParam E;
1103   E = A;
1104   testEmpty(E);
1105 
1106   TypeParam F;
1107   E.reset(A);
1108   testEmpty(E);
1109 }
1110 
1111 TYPED_TEST(BitVectorTest, Iterators) {
1112   TypeParam Filled(10, true);
1113   EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end());
1114   unsigned Counter = 0;
1115   for (unsigned Bit : Filled.set_bits())
1116     EXPECT_EQ(Bit, Counter++);
1117 
1118   TypeParam Empty;
1119   EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end());
1120   for (unsigned Bit : Empty.set_bits()) {
1121     (void)Bit;
1122     EXPECT_TRUE(false);
1123   }
1124 
1125   TypeParam ToFill(100, false);
1126   ToFill.set(0);
1127   EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end());
1128   EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end());
1129   EXPECT_EQ(*ToFill.set_bits_begin(), 0U);
1130   ToFill.reset(0);
1131   EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end());
1132 
1133   const unsigned List[] = {1, 10, 25, 99};
1134   for (unsigned Num : List)
1135     ToFill.set(Num);
1136   unsigned i = 0;
1137   for (unsigned Bit : ToFill.set_bits())
1138     EXPECT_EQ(List[i++], Bit);
1139 }
1140 
1141 TYPED_TEST(BitVectorTest, PushBack) {
1142   TypeParam Vec(10, false);
1143   EXPECT_EQ(-1, Vec.find_first());
1144   EXPECT_EQ(10U, Vec.size());
1145   EXPECT_EQ(0U, Vec.count());
1146 
1147   Vec.push_back(true);
1148   EXPECT_EQ(10, Vec.find_first());
1149   EXPECT_EQ(11U, Vec.size());
1150   EXPECT_EQ(1U, Vec.count());
1151 
1152   Vec.push_back(false);
1153   EXPECT_EQ(10, Vec.find_first());
1154   EXPECT_EQ(12U, Vec.size());
1155   EXPECT_EQ(1U, Vec.count());
1156 
1157   Vec.push_back(true);
1158   EXPECT_EQ(10, Vec.find_first());
1159   EXPECT_EQ(13U, Vec.size());
1160   EXPECT_EQ(2U, Vec.count());
1161 
1162   // Add a lot of values to cause reallocation.
1163   for (int i = 0; i != 100; ++i) {
1164     Vec.push_back(true);
1165     Vec.push_back(false);
1166   }
1167   EXPECT_EQ(10, Vec.find_first());
1168   EXPECT_EQ(213U, Vec.size());
1169   EXPECT_EQ(102U, Vec.count());
1170 }
1171 
1172 TYPED_TEST(BitVectorTest, DenseSet) {
1173   DenseSet<TypeParam> Set;
1174   TypeParam A(10, true);
1175   auto I = Set.insert(A);
1176   EXPECT_EQ(true, I.second);
1177 
1178   TypeParam B(5, true);
1179   I = Set.insert(B);
1180   EXPECT_EQ(true, I.second);
1181 
1182   TypeParam C(20, false);
1183   C.set(19);
1184   I = Set.insert(C);
1185   EXPECT_EQ(true, I.second);
1186 
1187 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
1188   TypeParam D;
1189   EXPECT_DEATH(Set.insert(D),
1190                "Empty/Tombstone value shouldn't be inserted into map!");
1191 #endif
1192 
1193   EXPECT_EQ(3U, Set.size());
1194   EXPECT_EQ(1U, Set.count(A));
1195   EXPECT_EQ(1U, Set.count(B));
1196   EXPECT_EQ(1U, Set.count(C));
1197 
1198   EXPECT_EQ(true, Set.erase(B));
1199   EXPECT_EQ(2U, Set.size());
1200 
1201   EXPECT_EQ(true, Set.erase(C));
1202   EXPECT_EQ(1U, Set.size());
1203 
1204   EXPECT_EQ(true, Set.erase(A));
1205   EXPECT_EQ(0U, Set.size());
1206 }
1207 } // namespace
1208