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