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 "gtest/gtest.h"
  15
  16 using namespace llvm;
  17
  18 namespace {
  19
  20 TEST(BitVectorTest, TrivialOperation) {
  21   BitVector Vec;
  22   EXPECT_EQ(0U, Vec.count());
  23   EXPECT_EQ(0U, Vec.size());
  24   EXPECT_FALSE(Vec.any());
  25   EXPECT_TRUE(Vec.all());
  26   EXPECT_TRUE(Vec.none());
  27   EXPECT_TRUE(Vec.empty());
  28
  29   Vec.resize(5, true);
  30   EXPECT_EQ(5U, Vec.count());
  31   EXPECT_EQ(5U, Vec.size());
  32   EXPECT_TRUE(Vec.any());
  33   EXPECT_TRUE(Vec.all());
  34   EXPECT_FALSE(Vec.none());
  35   EXPECT_FALSE(Vec.empty());
  36
  37   Vec.resize(11);
  38   EXPECT_EQ(5U, Vec.count());
  39   EXPECT_EQ(11U, Vec.size());
  40   EXPECT_TRUE(Vec.any());
  41   EXPECT_FALSE(Vec.all());
  42   EXPECT_FALSE(Vec.none());
  43   EXPECT_FALSE(Vec.empty());
  44
  45   BitVector Inv = Vec;
  46   Inv.flip();
  47   EXPECT_EQ(6U, Inv.count());
  48   EXPECT_EQ(11U, Inv.size());
  49   EXPECT_TRUE(Inv.any());
  50   EXPECT_FALSE(Inv.all());
  51   EXPECT_FALSE(Inv.none());
  52   EXPECT_FALSE(Inv.empty());
  53
  54   EXPECT_FALSE(Inv == Vec);
  55   EXPECT_TRUE(Inv != Vec);
  56   Vec.flip();
  57   EXPECT_TRUE(Inv == Vec);
  58   EXPECT_FALSE(Inv != Vec);
  59
  60   // Add some "interesting" data to Vec.
  61   Vec.resize(23, true);
  62   Vec.resize(25, false);
  63   Vec.resize(26, true);
  64   Vec.resize(29, false);
  65   Vec.resize(33, true);
  66   Vec.resize(57, false);
  67   unsigned Count = 0;
  68   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
  69     ++Count;
  70     EXPECT_TRUE(Vec[i]);
  71     EXPECT_TRUE(Vec.test(i));
  72   }
  73   EXPECT_EQ(Count, Vec.count());
  74   EXPECT_EQ(Count, 23u);
  75   EXPECT_FALSE(Vec[0]);
  76   EXPECT_TRUE(Vec[32]);
  77   EXPECT_FALSE(Vec[56]);
  78   Vec.resize(61, false);
  79
  80   BitVector Copy = Vec;
  81   BitVector Alt(3, false);
  82   Alt.resize(6, true);
  83   std::swap(Alt, Vec);
  84   EXPECT_TRUE(Copy == Alt);
  85   EXPECT_TRUE(Vec.size() == 6);
  86   EXPECT_TRUE(Vec.count() == 3);
  87   EXPECT_TRUE(Vec.find_first() == 3);
  88   std::swap(Copy, Vec);
  89
  90   // Add some more "interesting" data.
  91   Vec.resize(68, true);
  92   Vec.resize(78, false);
  93   Vec.resize(89, true);
  94   Vec.resize(90, false);
  95   Vec.resize(91, true);
  96   Vec.resize(130, false);
  97   Count = 0;
  98   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
  99     ++Count;
 100     EXPECT_TRUE(Vec[i]);
 101     EXPECT_TRUE(Vec.test(i));
 102   }
 103   EXPECT_EQ(Count, Vec.count());
 104   EXPECT_EQ(Count, 42u);
 105   EXPECT_FALSE(Vec[0]);
 106   EXPECT_TRUE(Vec[32]);
 107   EXPECT_FALSE(Vec[60]);
 108   EXPECT_FALSE(Vec[129]);
 109
 110   Vec.flip(60);
 111   EXPECT_TRUE(Vec[60]);
 112   EXPECT_EQ(Count + 1, Vec.count());
 113   Vec.flip(60);
 114   EXPECT_FALSE(Vec[60]);
 115   EXPECT_EQ(Count, Vec.count());
 116
 117   Vec.reset(32);
 118   EXPECT_FALSE(Vec[32]);
 119   EXPECT_EQ(Count - 1, Vec.count());
 120   Vec.set(32);
 121   EXPECT_TRUE(Vec[32]);
 122   EXPECT_EQ(Count, Vec.count());
 123
 124   Vec.flip();
 125   EXPECT_EQ(Vec.size() - Count, Vec.count());
 126
 127   Vec.reset();
 128   EXPECT_EQ(0U, Vec.count());
 129   EXPECT_EQ(130U, Vec.size());
 130   EXPECT_FALSE(Vec.any());
 131   EXPECT_FALSE(Vec.all());
 132   EXPECT_TRUE(Vec.none());
 133   EXPECT_FALSE(Vec.empty());
 134
 135   Inv = BitVector().flip();
 136   EXPECT_EQ(0U, Inv.count());
 137   EXPECT_EQ(0U, Inv.size());
 138   EXPECT_FALSE(Inv.any());
 139   EXPECT_TRUE(Inv.all());
 140   EXPECT_TRUE(Inv.none());
 141   EXPECT_TRUE(Inv.empty());
 142
 143   Vec.clear();
 144   EXPECT_EQ(0U, Vec.count());
 145   EXPECT_EQ(0U, Vec.size());
 146   EXPECT_FALSE(Vec.any());
 147   EXPECT_TRUE(Vec.all());
 148   EXPECT_TRUE(Vec.none());
 149   EXPECT_TRUE(Vec.empty());
 150 }
 151
 152 TEST(BitVectorTest, CompoundAssignment) {
 153   BitVector A;
 154   A.resize(10);
 155   A.set(4);
 156   A.set(7);
 157
 158   BitVector B;
 159   B.resize(50);
 160   B.set(5);
 161   B.set(18);
 162
 163   A |= B;
 164   EXPECT_TRUE(A.test(4));
 165   EXPECT_TRUE(A.test(5));
 166   EXPECT_TRUE(A.test(7));
 167   EXPECT_TRUE(A.test(18));
 168   EXPECT_EQ(4U, A.count());
 169   EXPECT_EQ(50U, A.size());
 170
 171   B.resize(10);
 172   B.set();
 173   B.reset(2);
 174   B.reset(7);
 175   A &= B;
 176   EXPECT_FALSE(A.test(2));
 177   EXPECT_FALSE(A.test(7));
 178   EXPECT_EQ(2U, A.count());
 179   EXPECT_EQ(50U, A.size());
 180
 181   B.resize(100);
 182   B.set();
 183
 184   A ^= B;
 185   EXPECT_TRUE(A.test(2));
 186   EXPECT_TRUE(A.test(7));
 187   EXPECT_EQ(98U, A.count());
 188   EXPECT_EQ(100U, A.size());
 189 }
 190
 191 TEST(BitVectorTest, ProxyIndex) {
 192   BitVector Vec(3);
 193   EXPECT_TRUE(Vec.none());
 194   Vec[0] = Vec[1] = Vec[2] = true;
 195   EXPECT_EQ(Vec.size(), Vec.count());
 196   Vec[2] = Vec[1] = Vec[0] = false;
 197   EXPECT_TRUE(Vec.none());
 198 }
 199
 200 TEST(BitVectorTest, PortableBitMask) {
 201   BitVector A;
 202   const uint32_t Mask1[] = { 0x80000000, 6, 5 };
 203
 204   A.resize(10);
 205   A.setBitsInMask(Mask1, 3);
 206   EXPECT_EQ(10u, A.size());
 207   EXPECT_FALSE(A.test(0));
 208
 209   A.resize(32);
 210   A.setBitsInMask(Mask1, 3);
 211   EXPECT_FALSE(A.test(0));
 212   EXPECT_TRUE(A.test(31));
 213   EXPECT_EQ(1u, A.count());
 214
 215   A.resize(33);
 216   A.setBitsInMask(Mask1, 1);
 217   EXPECT_EQ(1u, A.count());
 218   A.setBitsInMask(Mask1, 2);
 219   EXPECT_EQ(1u, A.count());
 220
 221   A.resize(34);
 222   A.setBitsInMask(Mask1, 2);
 223   EXPECT_EQ(2u, A.count());
 224
 225   A.resize(65);
 226   A.setBitsInMask(Mask1, 3);
 227   EXPECT_EQ(4u, A.count());
 228
 229   A.setBitsNotInMask(Mask1, 1);
 230   EXPECT_EQ(32u+3u, A.count());
 231
 232   A.setBitsNotInMask(Mask1, 3);
 233   EXPECT_EQ(65u, A.count());
 234
 235   A.resize(96);
 236   EXPECT_EQ(65u, A.count());
 237
 238   A.clear();
 239   A.resize(128);
 240   A.setBitsNotInMask(Mask1, 3);
 241   EXPECT_EQ(96u-5u, A.count());
 242
 243   A.clearBitsNotInMask(Mask1, 1);
 244   EXPECT_EQ(64-4u, A.count());
 245 }
 246
 247 TEST(BitVectorTest, BinOps) {
 248   BitVector A;
 249   BitVector B;
 250
 251   A.resize(65);
 252   EXPECT_FALSE(A.anyCommon(B));
 253   EXPECT_FALSE(B.anyCommon(B));
 254
 255   B.resize(64);
 256   A.set(64);
 257   EXPECT_FALSE(A.anyCommon(B));
 258   EXPECT_FALSE(B.anyCommon(A));
 259
 260   B.set(63);
 261   EXPECT_FALSE(A.anyCommon(B));
 262   EXPECT_FALSE(B.anyCommon(A));
 263
 264   A.set(63);
 265   EXPECT_TRUE(A.anyCommon(B));
 266   EXPECT_TRUE(B.anyCommon(A));
 267
 268   B.resize(70);
 269   B.set(64);
 270   B.reset(63);
 271   A.resize(64);
 272   EXPECT_FALSE(A.anyCommon(B));
 273   EXPECT_FALSE(B.anyCommon(A));
 274 }
 275 }
 276 #endif