unittests/ADT/BitVectorTest.cpp

   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   Inv = TypeParam().flip();
 145   EXPECT_EQ(0U, Inv.count());
 146   EXPECT_EQ(0U, Inv.size());
 147   EXPECT_FALSE(Inv.any());
 148   EXPECT_TRUE(Inv.all());
 149   EXPECT_TRUE(Inv.none());
 150   EXPECT_TRUE(Inv.empty());
 151
 152   Vec.clear();
 153   EXPECT_EQ(0U, Vec.count());
 154   EXPECT_EQ(0U, Vec.size());
 155   EXPECT_FALSE(Vec.any());
 156   EXPECT_TRUE(Vec.all());
 157   EXPECT_TRUE(Vec.none());
 158   EXPECT_TRUE(Vec.empty());
 159 }
 160
 161 TYPED_TEST(BitVectorTest, CompoundAssignment) {
 162   TypeParam A;
 163   A.resize(10);
 164   A.set(4);
 165   A.set(7);
 166
 167   TypeParam B;
 168   B.resize(50);
 169   B.set(5);
 170   B.set(18);
 171
 172   A |= B;
 173   EXPECT_TRUE(A.test(4));
 174   EXPECT_TRUE(A.test(5));
 175   EXPECT_TRUE(A.test(7));
 176   EXPECT_TRUE(A.test(18));
 177   EXPECT_EQ(4U, A.count());
 178   EXPECT_EQ(50U, A.size());
 179
 180   B.resize(10);
 181   B.set();
 182   B.reset(2);
 183   B.reset(7);
 184   A &= B;
 185   EXPECT_FALSE(A.test(2));
 186   EXPECT_FALSE(A.test(7));
 187   EXPECT_EQ(2U, A.count());
 188   EXPECT_EQ(50U, A.size());
 189
 190   B.resize(100);
 191   B.set();
 192
 193   A ^= B;
 194   EXPECT_TRUE(A.test(2));
 195   EXPECT_TRUE(A.test(7));
 196   EXPECT_EQ(98U, A.count());
 197   EXPECT_EQ(100U, A.size());
 198 }
 199
 200 TYPED_TEST(BitVectorTest, ProxyIndex) {
 201   TypeParam Vec(3);
 202   EXPECT_TRUE(Vec.none());
 203   Vec[0] = Vec[1] = Vec[2] = true;
 204   EXPECT_EQ(Vec.size(), Vec.count());
 205   Vec[2] = Vec[1] = Vec[0] = false;
 206   EXPECT_TRUE(Vec.none());
 207 }
 208
 209 TYPED_TEST(BitVectorTest, PortableBitMask) {
 210   TypeParam A;
 211   const uint32_t Mask1[] = { 0x80000000, 6, 5 };
 212
 213   A.resize(10);
 214   A.setBitsInMask(Mask1, 3);
 215   EXPECT_EQ(10u, A.size());
 216   EXPECT_FALSE(A.test(0));
 217
 218   A.resize(32);
 219   A.setBitsInMask(Mask1, 3);
 220   EXPECT_FALSE(A.test(0));
 221   EXPECT_TRUE(A.test(31));
 222   EXPECT_EQ(1u, A.count());
 223
 224   A.resize(33);
 225   A.setBitsInMask(Mask1, 1);
 226   EXPECT_EQ(1u, A.count());
 227   A.setBitsInMask(Mask1, 2);
 228   EXPECT_EQ(1u, A.count());
 229
 230   A.resize(34);
 231   A.setBitsInMask(Mask1, 2);
 232   EXPECT_EQ(2u, A.count());
 233
 234   A.resize(65);
 235   A.setBitsInMask(Mask1, 3);
 236   EXPECT_EQ(4u, A.count());
 237
 238   A.setBitsNotInMask(Mask1, 1);
 239   EXPECT_EQ(32u+3u, A.count());
 240
 241   A.setBitsNotInMask(Mask1, 3);
 242   EXPECT_EQ(65u, A.count());
 243
 244   A.resize(96);
 245   EXPECT_EQ(65u, A.count());
 246
 247   A.clear();
 248   A.resize(128);
 249   A.setBitsNotInMask(Mask1, 3);
 250   EXPECT_EQ(96u-5u, A.count());
 251
 252   A.clearBitsNotInMask(Mask1, 1);
 253   EXPECT_EQ(64-4u, A.count());
 254 }
 255
 256 TYPED_TEST(BitVectorTest, BinOps) {
 257   TypeParam A;
 258   TypeParam B;
 259
 260   A.resize(65);
 261   EXPECT_FALSE(A.anyCommon(B));
 262   EXPECT_FALSE(B.anyCommon(B));
 263
 264   B.resize(64);
 265   A.set(64);
 266   EXPECT_FALSE(A.anyCommon(B));
 267   EXPECT_FALSE(B.anyCommon(A));
 268
 269   B.set(63);
 270   EXPECT_FALSE(A.anyCommon(B));
 271   EXPECT_FALSE(B.anyCommon(A));
 272
 273   A.set(63);
 274   EXPECT_TRUE(A.anyCommon(B));
 275   EXPECT_TRUE(B.anyCommon(A));
 276
 277   B.resize(70);
 278   B.set(64);
 279   B.reset(63);
 280   A.resize(64);
 281   EXPECT_FALSE(A.anyCommon(B));
 282   EXPECT_FALSE(B.anyCommon(A));
 283 }
 284
 285 TYPED_TEST(BitVectorTest, RangeOps) {
 286   TypeParam A;
 287   A.resize(256);
 288   A.reset();
 289   A.set(1, 255);
 290
 291   EXPECT_FALSE(A.test(0));
 292   EXPECT_TRUE( A.test(1));
 293   EXPECT_TRUE( A.test(23));
 294   EXPECT_TRUE( A.test(254));
 295   EXPECT_FALSE(A.test(255));
 296
 297   TypeParam B;
 298   B.resize(256);
 299   B.set();
 300   B.reset(1, 255);
 301
 302   EXPECT_TRUE( B.test(0));
 303   EXPECT_FALSE(B.test(1));
 304   EXPECT_FALSE(B.test(23));
 305   EXPECT_FALSE(B.test(254));
 306   EXPECT_TRUE( B.test(255));
 307
 308   TypeParam C;
 309   C.resize(3);
 310   C.reset();
 311   C.set(0, 1);
 312
 313   EXPECT_TRUE(C.test(0));
 314   EXPECT_FALSE( C.test(1));
 315   EXPECT_FALSE( C.test(2));
 316
 317   TypeParam D;
 318   D.resize(3);
 319   D.set();
 320   D.reset(0, 1);
 321
 322   EXPECT_FALSE(D.test(0));
 323   EXPECT_TRUE( D.test(1));
 324   EXPECT_TRUE( D.test(2));
 325
 326   TypeParam E;
 327   E.resize(128);
 328   E.reset();
 329   E.set(1, 33);
 330
 331   EXPECT_FALSE(E.test(0));
 332   EXPECT_TRUE( E.test(1));
 333   EXPECT_TRUE( E.test(32));
 334   EXPECT_FALSE(E.test(33));
 335 }
 336 }
 337 #endif