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