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   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