xref: /llvm-project/llvm/unittests/ADT/BitVectorTest.cpp (revision 492674ec2ad994e49abbc556b6585bb381a027f1) 
1 //===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector tests --------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 // Some of these tests fail on PowerPC for unknown reasons.
11 #ifndef __ppc__
12 
13 #include "llvm/ADT/BitVector.h"
14 #include "llvm/ADT/SmallBitVector.h"
15 #include "gtest/gtest.h"
16 
17 using namespace llvm;
18 
19 namespace {
20 
21 // Test fixture
22 template <typename T>
23 class BitVectorTest : public ::testing::Test { };
24 
25 // Test both BitVector and SmallBitVector with the same suite of tests.
26 typedef ::testing::Types<BitVector, SmallBitVector> BitVectorTestTypes;
27 TYPED_TEST_CASE(BitVectorTest, BitVectorTestTypes);
28 
29 TYPED_TEST(BitVectorTest, TrivialOperation) {
30   TypeParam Vec;
31   EXPECT_EQ(0U, Vec.count());
32   EXPECT_EQ(0U, Vec.size());
33   EXPECT_FALSE(Vec.any());
34   EXPECT_TRUE(Vec.all());
35   EXPECT_TRUE(Vec.none());
36   EXPECT_TRUE(Vec.empty());
37 
38   Vec.resize(5, true);
39   EXPECT_EQ(5U, Vec.count());
40   EXPECT_EQ(5U, Vec.size());
41   EXPECT_TRUE(Vec.any());
42   EXPECT_TRUE(Vec.all());
43   EXPECT_FALSE(Vec.none());
44   EXPECT_FALSE(Vec.empty());
45 
46   Vec.resize(11);
47   EXPECT_EQ(5U, Vec.count());
48   EXPECT_EQ(11U, Vec.size());
49   EXPECT_TRUE(Vec.any());
50   EXPECT_FALSE(Vec.all());
51   EXPECT_FALSE(Vec.none());
52   EXPECT_FALSE(Vec.empty());
53 
54   TypeParam Inv = Vec;
55   Inv.flip();
56   EXPECT_EQ(6U, Inv.count());
57   EXPECT_EQ(11U, Inv.size());
58   EXPECT_TRUE(Inv.any());
59   EXPECT_FALSE(Inv.all());
60   EXPECT_FALSE(Inv.none());
61   EXPECT_FALSE(Inv.empty());
62 
63   EXPECT_FALSE(Inv == Vec);
64   EXPECT_TRUE(Inv != Vec);
65   Vec.flip();
66   EXPECT_TRUE(Inv == Vec);
67   EXPECT_FALSE(Inv != Vec);
68 
69   // Add some "interesting" data to Vec.
70   Vec.resize(23, true);
71   Vec.resize(25, false);
72   Vec.resize(26, true);
73   Vec.resize(29, false);
74   Vec.resize(33, true);
75   Vec.resize(57, false);
76   unsigned Count = 0;
77   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
78     ++Count;
79     EXPECT_TRUE(Vec[i]);
80     EXPECT_TRUE(Vec.test(i));
81   }
82   EXPECT_EQ(Count, Vec.count());
83   EXPECT_EQ(Count, 23u);
84   EXPECT_FALSE(Vec[0]);
85   EXPECT_TRUE(Vec[32]);
86   EXPECT_FALSE(Vec[56]);
87   Vec.resize(61, false);
88 
89   TypeParam Copy = Vec;
90   TypeParam Alt(3, false);
91   Alt.resize(6, true);
92   std::swap(Alt, Vec);
93   EXPECT_TRUE(Copy == Alt);
94   EXPECT_TRUE(Vec.size() == 6);
95   EXPECT_TRUE(Vec.count() == 3);
96   EXPECT_TRUE(Vec.find_first() == 3);
97   std::swap(Copy, Vec);
98 
99   // Add some more "interesting" data.
100   Vec.resize(68, true);
101   Vec.resize(78, false);
102   Vec.resize(89, true);
103   Vec.resize(90, false);
104   Vec.resize(91, true);
105   Vec.resize(130, false);
106   Count = 0;
107   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
108     ++Count;
109     EXPECT_TRUE(Vec[i]);
110     EXPECT_TRUE(Vec.test(i));
111   }
112   EXPECT_EQ(Count, Vec.count());
113   EXPECT_EQ(Count, 42u);
114   EXPECT_FALSE(Vec[0]);
115   EXPECT_TRUE(Vec[32]);
116   EXPECT_FALSE(Vec[60]);
117   EXPECT_FALSE(Vec[129]);
118 
119   Vec.flip(60);
120   EXPECT_TRUE(Vec[60]);
121   EXPECT_EQ(Count + 1, Vec.count());
122   Vec.flip(60);
123   EXPECT_FALSE(Vec[60]);
124   EXPECT_EQ(Count, Vec.count());
125 
126   Vec.reset(32);
127   EXPECT_FALSE(Vec[32]);
128   EXPECT_EQ(Count - 1, Vec.count());
129   Vec.set(32);
130   EXPECT_TRUE(Vec[32]);
131   EXPECT_EQ(Count, Vec.count());
132 
133   Vec.flip();
134   EXPECT_EQ(Vec.size() - Count, Vec.count());
135 
136   Vec.reset();
137   EXPECT_EQ(0U, Vec.count());
138   EXPECT_EQ(130U, Vec.size());
139   EXPECT_FALSE(Vec.any());
140   EXPECT_FALSE(Vec.all());
141   EXPECT_TRUE(Vec.none());
142   EXPECT_FALSE(Vec.empty());
143 
144   Vec.flip();
145   EXPECT_EQ(130U, Vec.count());
146   EXPECT_EQ(130U, Vec.size());
147   EXPECT_TRUE(Vec.any());
148   EXPECT_TRUE(Vec.all());
149   EXPECT_FALSE(Vec.none());
150   EXPECT_FALSE(Vec.empty());
151 
152   Vec.resize(64);
153   EXPECT_EQ(64U, Vec.count());
154   EXPECT_EQ(64U, Vec.size());
155   EXPECT_TRUE(Vec.any());
156   EXPECT_TRUE(Vec.all());
157   EXPECT_FALSE(Vec.none());
158   EXPECT_FALSE(Vec.empty());
159 
160   Vec.flip();
161   EXPECT_EQ(0U, Vec.count());
162   EXPECT_EQ(64U, Vec.size());
163   EXPECT_FALSE(Vec.any());
164   EXPECT_FALSE(Vec.all());
165   EXPECT_TRUE(Vec.none());
166   EXPECT_FALSE(Vec.empty());
167 
168   Inv = TypeParam().flip();
169   EXPECT_EQ(0U, Inv.count());
170   EXPECT_EQ(0U, Inv.size());
171   EXPECT_FALSE(Inv.any());
172   EXPECT_TRUE(Inv.all());
173   EXPECT_TRUE(Inv.none());
174   EXPECT_TRUE(Inv.empty());
175 
176   Vec.clear();
177   EXPECT_EQ(0U, Vec.count());
178   EXPECT_EQ(0U, Vec.size());
179   EXPECT_FALSE(Vec.any());
180   EXPECT_TRUE(Vec.all());
181   EXPECT_TRUE(Vec.none());
182   EXPECT_TRUE(Vec.empty());
183 }
184 
185 TYPED_TEST(BitVectorTest, FindOperations) {
186   // Test finding in an empty BitVector.
187   TypeParam A;
188   EXPECT_EQ(-1, A.find_first());
189   EXPECT_EQ(-1, A.find_last());
190   EXPECT_EQ(-1, A.find_first_unset());
191   EXPECT_EQ(-1, A.find_last_unset());
192   EXPECT_EQ(-1, A.find_next(0));
193   EXPECT_EQ(-1, A.find_next_unset(0));
194 
195   // Test finding next set and unset bits in a BitVector with multiple words
196   A.resize(100);
197   A.set(12);
198   A.set(13);
199   A.set(75);
200 
201   EXPECT_EQ(75, A.find_last());
202   EXPECT_EQ(12, A.find_first());
203   EXPECT_EQ(13, A.find_next(12));
204   EXPECT_EQ(75, A.find_next(13));
205   EXPECT_EQ(-1, A.find_next(75));
206 
207   EXPECT_EQ(0, A.find_first_unset());
208   EXPECT_EQ(99, A.find_last_unset());
209   EXPECT_EQ(14, A.find_next_unset(11));
210   EXPECT_EQ(14, A.find_next_unset(12));
211   EXPECT_EQ(14, A.find_next_unset(13));
212   EXPECT_EQ(16, A.find_next_unset(15));
213   EXPECT_EQ(76, A.find_next_unset(74));
214   EXPECT_EQ(76, A.find_next_unset(75));
215   EXPECT_EQ(-1, A.find_next_unset(99));
216 
217   A.set(0, 100);
218   EXPECT_EQ(100U, A.count());
219   EXPECT_EQ(0, A.find_first());
220   EXPECT_EQ(99, A.find_last());
221   EXPECT_EQ(-1, A.find_first_unset());
222   EXPECT_EQ(-1, A.find_last_unset());
223 
224   A.reset(0, 100);
225   EXPECT_EQ(0U, A.count());
226   EXPECT_EQ(-1, A.find_first());
227   EXPECT_EQ(-1, A.find_last());
228   EXPECT_EQ(0, A.find_first_unset());
229   EXPECT_EQ(99, A.find_last_unset());
230 }
231 
232 TYPED_TEST(BitVectorTest, CompoundAssignment) {
233   TypeParam A;
234   A.resize(10);
235   A.set(4);
236   A.set(7);
237 
238   TypeParam B;
239   B.resize(50);
240   B.set(5);
241   B.set(18);
242 
243   A |= B;
244   EXPECT_TRUE(A.test(4));
245   EXPECT_TRUE(A.test(5));
246   EXPECT_TRUE(A.test(7));
247   EXPECT_TRUE(A.test(18));
248   EXPECT_EQ(4U, A.count());
249   EXPECT_EQ(50U, A.size());
250 
251   B.resize(10);
252   B.set();
253   B.reset(2);
254   B.reset(7);
255   A &= B;
256   EXPECT_FALSE(A.test(2));
257   EXPECT_FALSE(A.test(7));
258   EXPECT_EQ(2U, A.count());
259   EXPECT_EQ(50U, A.size());
260 
261   B.resize(100);
262   B.set();
263 
264   A ^= B;
265   EXPECT_TRUE(A.test(2));
266   EXPECT_TRUE(A.test(7));
267   EXPECT_EQ(98U, A.count());
268   EXPECT_EQ(100U, A.size());
269 }
270 
271 TYPED_TEST(BitVectorTest, ProxyIndex) {
272   TypeParam Vec(3);
273   EXPECT_TRUE(Vec.none());
274   Vec[0] = Vec[1] = Vec[2] = true;
275   EXPECT_EQ(Vec.size(), Vec.count());
276   Vec[2] = Vec[1] = Vec[0] = false;
277   EXPECT_TRUE(Vec.none());
278 }
279 
280 TYPED_TEST(BitVectorTest, PortableBitMask) {
281   TypeParam A;
282   const uint32_t Mask1[] = { 0x80000000, 6, 5 };
283 
284   A.resize(10);
285   A.setBitsInMask(Mask1, 1);
286   EXPECT_EQ(10u, A.size());
287   EXPECT_FALSE(A.test(0));
288 
289   A.resize(32);
290   A.setBitsInMask(Mask1, 1);
291   EXPECT_FALSE(A.test(0));
292   EXPECT_TRUE(A.test(31));
293   EXPECT_EQ(1u, A.count());
294 
295   A.resize(33);
296   A.setBitsInMask(Mask1, 1);
297   EXPECT_EQ(1u, A.count());
298   A.setBitsInMask(Mask1, 2);
299   EXPECT_EQ(1u, A.count());
300 
301   A.resize(34);
302   A.setBitsInMask(Mask1, 2);
303   EXPECT_EQ(2u, A.count());
304 
305   A.resize(65);
306   A.setBitsInMask(Mask1, 3);
307   EXPECT_EQ(4u, A.count());
308 
309   A.setBitsNotInMask(Mask1, 1);
310   EXPECT_EQ(32u+3u, A.count());
311 
312   A.setBitsNotInMask(Mask1, 3);
313   EXPECT_EQ(65u, A.count());
314 
315   A.resize(96);
316   EXPECT_EQ(65u, A.count());
317 
318   A.clear();
319   A.resize(128);
320   A.setBitsNotInMask(Mask1, 3);
321   EXPECT_EQ(96u-5u, A.count());
322 
323   A.clearBitsNotInMask(Mask1, 1);
324   EXPECT_EQ(64-4u, A.count());
325 }
326 
327 TYPED_TEST(BitVectorTest, BinOps) {
328   TypeParam A;
329   TypeParam B;
330 
331   A.resize(65);
332   EXPECT_FALSE(A.anyCommon(B));
333   EXPECT_FALSE(B.anyCommon(B));
334 
335   B.resize(64);
336   A.set(64);
337   EXPECT_FALSE(A.anyCommon(B));
338   EXPECT_FALSE(B.anyCommon(A));
339 
340   B.set(63);
341   EXPECT_FALSE(A.anyCommon(B));
342   EXPECT_FALSE(B.anyCommon(A));
343 
344   A.set(63);
345   EXPECT_TRUE(A.anyCommon(B));
346   EXPECT_TRUE(B.anyCommon(A));
347 
348   B.resize(70);
349   B.set(64);
350   B.reset(63);
351   A.resize(64);
352   EXPECT_FALSE(A.anyCommon(B));
353   EXPECT_FALSE(B.anyCommon(A));
354 }
355 
356 typedef std::vector<std::pair<int, int>> RangeList;
357 
358 template <typename VecType>
359 static inline VecType createBitVector(uint32_t Size,
360                                       const RangeList &setRanges) {
361   VecType V;
362   V.resize(Size);
363   for (auto &R : setRanges)
364     V.set(R.first, R.second);
365   return V;
366 }
367 
368 TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) {
369   // Test that shift ops work when the desired shift amount is less
370   // than one word.
371 
372   // 1. Case where the number of bits in the BitVector also fit into a single
373   // word.
374   TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}});
375   TypeParam B = A;
376 
377   EXPECT_EQ(4U, A.count());
378   EXPECT_TRUE(A.test(2));
379   EXPECT_TRUE(A.test(3));
380   EXPECT_TRUE(A.test(8));
381   EXPECT_TRUE(A.test(9));
382 
383   A >>= 1;
384   EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A);
385 
386   A <<= 1;
387   EXPECT_EQ(B, A);
388 
389   A >>= 10;
390   EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
391 
392   A = B;
393   A <<= 10;
394   EXPECT_EQ(createBitVector<TypeParam>(12, {}), A);
395 
396   // 2. Case where the number of bits in the BitVector do not fit into a single
397   // word.
398 
399   // 31----------------------------------------------------------------------0
400   // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
401   A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}});
402   EXPECT_EQ(40U, A.size());
403   EXPECT_EQ(22U, A.count());
404 
405   // 2a. Make sure that left shifting some 1 bits out of the vector works.
406   //   31----------------------------------------------------------------------0
407   // Before:
408   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111
409   // After:
410   //   XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
411   A <<= 9;
412   EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A);
413 
414   // 2b. Make sure that keeping the number of one bits unchanged works.
415   //   31----------------------------------------------------------------------0
416   // Before:
417   //   XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000
418   // After:
419   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
420   A >>= 6;
421   EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A);
422 
423   // 2c. Make sure that right shifting some 1 bits out of the vector works.
424   //   31----------------------------------------------------------------------0
425   // Before:
426   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000
427   // After:
428   //   XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111
429   A >>= 10;
430   EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A);
431 
432   // 3. Big test.
433   A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
434   A <<= 29;
435   EXPECT_EQ(createBitVector<TypeParam>(
436                 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}),
437             A);
438 }
439 
440 TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) {
441   // Test that shift ops work when the desired shift amount is greater than or
442   // equal to the size of a single word.
443   auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}});
444 
445   // Make a copy so we can re-use it later.
446   auto B = A;
447 
448   // 1. Shift left by an exact multiple of the word size.  This should invoke
449   // only a memmove and no per-word bit operations.
450   A <<= 64;
451   auto Expected = createBitVector<TypeParam>(
452       300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}});
453   EXPECT_EQ(Expected, A);
454 
455   // 2. Shift left by a non multiple of the word size.  This should invoke both
456   // a memmove and per-word bit operations.
457   A = B;
458   A <<= 93;
459   EXPECT_EQ(createBitVector<TypeParam>(
460                 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}),
461             A);
462 
463   // 1. Shift right by an exact multiple of the word size.  This should invoke
464   // only a memmove and no per-word bit operations.
465   A = B;
466   A >>= 64;
467   EXPECT_EQ(
468       createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A);
469 
470   // 2. Shift left by a non multiple of the word size.  This should invoke both
471   // a memmove and per-word bit operations.
472   A = B;
473   A >>= 93;
474   EXPECT_EQ(
475       createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A);
476 }
477 
478 TYPED_TEST(BitVectorTest, RangeOps) {
479   TypeParam A;
480   A.resize(256);
481   A.reset();
482   A.set(1, 255);
483 
484   EXPECT_FALSE(A.test(0));
485   EXPECT_TRUE( A.test(1));
486   EXPECT_TRUE( A.test(23));
487   EXPECT_TRUE( A.test(254));
488   EXPECT_FALSE(A.test(255));
489 
490   TypeParam B;
491   B.resize(256);
492   B.set();
493   B.reset(1, 255);
494 
495   EXPECT_TRUE( B.test(0));
496   EXPECT_FALSE(B.test(1));
497   EXPECT_FALSE(B.test(23));
498   EXPECT_FALSE(B.test(254));
499   EXPECT_TRUE( B.test(255));
500 
501   TypeParam C;
502   C.resize(3);
503   C.reset();
504   C.set(0, 1);
505 
506   EXPECT_TRUE(C.test(0));
507   EXPECT_FALSE( C.test(1));
508   EXPECT_FALSE( C.test(2));
509 
510   TypeParam D;
511   D.resize(3);
512   D.set();
513   D.reset(0, 1);
514 
515   EXPECT_FALSE(D.test(0));
516   EXPECT_TRUE( D.test(1));
517   EXPECT_TRUE( D.test(2));
518 
519   TypeParam E;
520   E.resize(128);
521   E.reset();
522   E.set(1, 33);
523 
524   EXPECT_FALSE(E.test(0));
525   EXPECT_TRUE( E.test(1));
526   EXPECT_TRUE( E.test(32));
527   EXPECT_FALSE(E.test(33));
528 
529   TypeParam BufferOverrun;
530   unsigned size = sizeof(unsigned long) * 8;
531   BufferOverrun.resize(size);
532   BufferOverrun.reset(0, size);
533   BufferOverrun.set(0, size);
534 }
535 
536 TYPED_TEST(BitVectorTest, CompoundTestReset) {
537   TypeParam A(50, true);
538   TypeParam B(50, false);
539 
540   TypeParam C(100, true);
541   TypeParam D(100, false);
542 
543   EXPECT_FALSE(A.test(A));
544   EXPECT_TRUE(A.test(B));
545   EXPECT_FALSE(A.test(C));
546   EXPECT_TRUE(A.test(D));
547   EXPECT_FALSE(B.test(A));
548   EXPECT_FALSE(B.test(B));
549   EXPECT_FALSE(B.test(C));
550   EXPECT_FALSE(B.test(D));
551   EXPECT_TRUE(C.test(A));
552   EXPECT_TRUE(C.test(B));
553   EXPECT_FALSE(C.test(C));
554   EXPECT_TRUE(C.test(D));
555 
556   A.reset(B);
557   A.reset(D);
558   EXPECT_TRUE(A.all());
559   A.reset(A);
560   EXPECT_TRUE(A.none());
561   A.set();
562   A.reset(C);
563   EXPECT_TRUE(A.none());
564   A.set();
565 
566   C.reset(A);
567   EXPECT_EQ(50, C.find_first());
568   C.reset(C);
569   EXPECT_TRUE(C.none());
570 }
571 
572 TYPED_TEST(BitVectorTest, MoveConstructor) {
573   TypeParam A(10, true);
574   TypeParam B(std::move(A));
575   // Check that the move ctor leaves the moved-from object in a valid state.
576   // The following line used to crash.
577   A = B;
578 
579   TypeParam C(10, true);
580   EXPECT_EQ(C, A);
581   EXPECT_EQ(C, B);
582 }
583 
584 TYPED_TEST(BitVectorTest, MoveAssignment) {
585   TypeParam A(10, true);
586   TypeParam B;
587   B = std::move(A);
588   // Check that move assignment leaves the moved-from object in a valid state.
589   // The following line used to crash.
590   A = B;
591 
592   TypeParam C(10, true);
593   EXPECT_EQ(C, A);
594   EXPECT_EQ(C, B);
595 }
596 
597 template<class TypeParam>
598 static void testEmpty(const TypeParam &A) {
599   EXPECT_TRUE(A.empty());
600   EXPECT_EQ((size_t)0, A.size());
601   EXPECT_EQ((size_t)0, A.count());
602   EXPECT_FALSE(A.any());
603   EXPECT_TRUE(A.all());
604   EXPECT_TRUE(A.none());
605   EXPECT_EQ(-1, A.find_first());
606   EXPECT_EQ(A, TypeParam());
607 }
608 
609 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0
610 TYPED_TEST(BitVectorTest, EmptyVector) {
611   TypeParam A;
612   testEmpty(A);
613 
614   TypeParam B;
615   B.reset();
616   testEmpty(B);
617 
618   TypeParam C;
619   C.clear();
620   testEmpty(C);
621 
622   TypeParam D(A);
623   testEmpty(D);
624 
625   TypeParam E;
626   E = A;
627   testEmpty(E);
628 
629   TypeParam F;
630   E.reset(A);
631   testEmpty(E);
632 }
633 
634 }
635 #endif
636