Home | History | Annotate | Download | only in ADT
      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, CompoundAssignment) {
    186   TypeParam A;
    187   A.resize(10);
    188   A.set(4);
    189   A.set(7);
    190 
    191   TypeParam B;
    192   B.resize(50);
    193   B.set(5);
    194   B.set(18);
    195 
    196   A |= B;
    197   EXPECT_TRUE(A.test(4));
    198   EXPECT_TRUE(A.test(5));
    199   EXPECT_TRUE(A.test(7));
    200   EXPECT_TRUE(A.test(18));
    201   EXPECT_EQ(4U, A.count());
    202   EXPECT_EQ(50U, A.size());
    203 
    204   B.resize(10);
    205   B.set();
    206   B.reset(2);
    207   B.reset(7);
    208   A &= B;
    209   EXPECT_FALSE(A.test(2));
    210   EXPECT_FALSE(A.test(7));
    211   EXPECT_EQ(2U, A.count());
    212   EXPECT_EQ(50U, A.size());
    213 
    214   B.resize(100);
    215   B.set();
    216 
    217   A ^= B;
    218   EXPECT_TRUE(A.test(2));
    219   EXPECT_TRUE(A.test(7));
    220   EXPECT_EQ(98U, A.count());
    221   EXPECT_EQ(100U, A.size());
    222 }
    223 
    224 TYPED_TEST(BitVectorTest, ProxyIndex) {
    225   TypeParam Vec(3);
    226   EXPECT_TRUE(Vec.none());
    227   Vec[0] = Vec[1] = Vec[2] = true;
    228   EXPECT_EQ(Vec.size(), Vec.count());
    229   Vec[2] = Vec[1] = Vec[0] = false;
    230   EXPECT_TRUE(Vec.none());
    231 }
    232 
    233 TYPED_TEST(BitVectorTest, PortableBitMask) {
    234   TypeParam A;
    235   const uint32_t Mask1[] = { 0x80000000, 6, 5 };
    236 
    237   A.resize(10);
    238   A.setBitsInMask(Mask1, 3);
    239   EXPECT_EQ(10u, A.size());
    240   EXPECT_FALSE(A.test(0));
    241 
    242   A.resize(32);
    243   A.setBitsInMask(Mask1, 3);
    244   EXPECT_FALSE(A.test(0));
    245   EXPECT_TRUE(A.test(31));
    246   EXPECT_EQ(1u, A.count());
    247 
    248   A.resize(33);
    249   A.setBitsInMask(Mask1, 1);
    250   EXPECT_EQ(1u, A.count());
    251   A.setBitsInMask(Mask1, 2);
    252   EXPECT_EQ(1u, A.count());
    253 
    254   A.resize(34);
    255   A.setBitsInMask(Mask1, 2);
    256   EXPECT_EQ(2u, A.count());
    257 
    258   A.resize(65);
    259   A.setBitsInMask(Mask1, 3);
    260   EXPECT_EQ(4u, A.count());
    261 
    262   A.setBitsNotInMask(Mask1, 1);
    263   EXPECT_EQ(32u+3u, A.count());
    264 
    265   A.setBitsNotInMask(Mask1, 3);
    266   EXPECT_EQ(65u, A.count());
    267 
    268   A.resize(96);
    269   EXPECT_EQ(65u, A.count());
    270 
    271   A.clear();
    272   A.resize(128);
    273   A.setBitsNotInMask(Mask1, 3);
    274   EXPECT_EQ(96u-5u, A.count());
    275 
    276   A.clearBitsNotInMask(Mask1, 1);
    277   EXPECT_EQ(64-4u, A.count());
    278 }
    279 
    280 TYPED_TEST(BitVectorTest, BinOps) {
    281   TypeParam A;
    282   TypeParam B;
    283 
    284   A.resize(65);
    285   EXPECT_FALSE(A.anyCommon(B));
    286   EXPECT_FALSE(B.anyCommon(B));
    287 
    288   B.resize(64);
    289   A.set(64);
    290   EXPECT_FALSE(A.anyCommon(B));
    291   EXPECT_FALSE(B.anyCommon(A));
    292 
    293   B.set(63);
    294   EXPECT_FALSE(A.anyCommon(B));
    295   EXPECT_FALSE(B.anyCommon(A));
    296 
    297   A.set(63);
    298   EXPECT_TRUE(A.anyCommon(B));
    299   EXPECT_TRUE(B.anyCommon(A));
    300 
    301   B.resize(70);
    302   B.set(64);
    303   B.reset(63);
    304   A.resize(64);
    305   EXPECT_FALSE(A.anyCommon(B));
    306   EXPECT_FALSE(B.anyCommon(A));
    307 }
    308 
    309 TYPED_TEST(BitVectorTest, RangeOps) {
    310   TypeParam A;
    311   A.resize(256);
    312   A.reset();
    313   A.set(1, 255);
    314 
    315   EXPECT_FALSE(A.test(0));
    316   EXPECT_TRUE( A.test(1));
    317   EXPECT_TRUE( A.test(23));
    318   EXPECT_TRUE( A.test(254));
    319   EXPECT_FALSE(A.test(255));
    320 
    321   TypeParam B;
    322   B.resize(256);
    323   B.set();
    324   B.reset(1, 255);
    325 
    326   EXPECT_TRUE( B.test(0));
    327   EXPECT_FALSE(B.test(1));
    328   EXPECT_FALSE(B.test(23));
    329   EXPECT_FALSE(B.test(254));
    330   EXPECT_TRUE( B.test(255));
    331 
    332   TypeParam C;
    333   C.resize(3);
    334   C.reset();
    335   C.set(0, 1);
    336 
    337   EXPECT_TRUE(C.test(0));
    338   EXPECT_FALSE( C.test(1));
    339   EXPECT_FALSE( C.test(2));
    340 
    341   TypeParam D;
    342   D.resize(3);
    343   D.set();
    344   D.reset(0, 1);
    345 
    346   EXPECT_FALSE(D.test(0));
    347   EXPECT_TRUE( D.test(1));
    348   EXPECT_TRUE( D.test(2));
    349 
    350   TypeParam E;
    351   E.resize(128);
    352   E.reset();
    353   E.set(1, 33);
    354 
    355   EXPECT_FALSE(E.test(0));
    356   EXPECT_TRUE( E.test(1));
    357   EXPECT_TRUE( E.test(32));
    358   EXPECT_FALSE(E.test(33));
    359 
    360   TypeParam BufferOverrun;
    361   unsigned size = sizeof(unsigned long) * 8;
    362   BufferOverrun.resize(size);
    363   BufferOverrun.reset(0, size);
    364   BufferOverrun.set(0, size);
    365 }
    366 
    367 TYPED_TEST(BitVectorTest, CompoundTestReset) {
    368   TypeParam A(50, true);
    369   TypeParam B(50, false);
    370 
    371   TypeParam C(100, true);
    372   TypeParam D(100, false);
    373 
    374   EXPECT_FALSE(A.test(A));
    375   EXPECT_TRUE(A.test(B));
    376   EXPECT_FALSE(A.test(C));
    377   EXPECT_TRUE(A.test(D));
    378   EXPECT_FALSE(B.test(A));
    379   EXPECT_FALSE(B.test(B));
    380   EXPECT_FALSE(B.test(C));
    381   EXPECT_FALSE(B.test(D));
    382   EXPECT_TRUE(C.test(A));
    383   EXPECT_TRUE(C.test(B));
    384   EXPECT_FALSE(C.test(C));
    385   EXPECT_TRUE(C.test(D));
    386 
    387   A.reset(B);
    388   A.reset(D);
    389   EXPECT_TRUE(A.all());
    390   A.reset(A);
    391   EXPECT_TRUE(A.none());
    392   A.set();
    393   A.reset(C);
    394   EXPECT_TRUE(A.none());
    395   A.set();
    396 
    397   C.reset(A);
    398   EXPECT_EQ(50, C.find_first());
    399   C.reset(C);
    400   EXPECT_TRUE(C.none());
    401 }
    402 }
    403 #endif
    404