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