unittests/ADT/SmallBitVectorTest.cpp

   1 //===- llvm/unittest/ADT/SmallBitVectorTest.cpp - SmallBitVector 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 #include "llvm/ADT/SmallBitVector.h"
  11 #include "gtest/gtest.h"
  12
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 TEST(SmallBitVectorTest, TrivialOperation) {
  18   SmallBitVector Vec;
  19   EXPECT_EQ(0U, Vec.count());
  20   EXPECT_EQ(0U, Vec.size());
  21   EXPECT_FALSE(Vec.any());
  22   EXPECT_TRUE(Vec.none());
  23   EXPECT_TRUE(Vec.empty());
  24
  25   Vec.resize(5, true);
  26   EXPECT_EQ(5U, Vec.count());
  27   EXPECT_EQ(5U, Vec.size());
  28   EXPECT_TRUE(Vec.any());
  29   EXPECT_FALSE(Vec.none());
  30   EXPECT_FALSE(Vec.empty());
  31
  32   Vec.resize(11);
  33   EXPECT_EQ(5U, Vec.count());
  34   EXPECT_EQ(11U, Vec.size());
  35   EXPECT_TRUE(Vec.any());
  36   EXPECT_FALSE(Vec.none());
  37   EXPECT_FALSE(Vec.empty());
  38
  39   SmallBitVector Inv = ~Vec;
  40   EXPECT_EQ(6U, Inv.count());
  41   EXPECT_EQ(11U, Inv.size());
  42   EXPECT_TRUE(Inv.any());
  43   EXPECT_FALSE(Inv.none());
  44   EXPECT_FALSE(Inv.empty());
  45
  46   EXPECT_FALSE(Inv == Vec);
  47   EXPECT_TRUE(Inv != Vec);
  48   Vec = ~Vec;
  49   EXPECT_TRUE(Inv == Vec);
  50   EXPECT_FALSE(Inv != Vec);
  51
  52   // Add some "interesting" data to Vec.
  53   Vec.resize(23, true);
  54   Vec.resize(25, false);
  55   Vec.resize(26, true);
  56   Vec.resize(29, false);
  57   Vec.resize(33, true);
  58   Vec.resize(57, false);
  59   unsigned Count = 0;
  60   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
  61     ++Count;
  62     EXPECT_TRUE(Vec[i]);
  63     EXPECT_TRUE(Vec.test(i));
  64   }
  65   EXPECT_EQ(Count, Vec.count());
  66   EXPECT_EQ(Count, 23u);
  67   EXPECT_FALSE(Vec[0]);
  68   EXPECT_TRUE(Vec[32]);
  69   EXPECT_FALSE(Vec[56]);
  70   Vec.resize(61, false);
  71
  72   SmallBitVector Copy = Vec;
  73   SmallBitVector Alt(3, false);
  74   Alt.resize(6, true);
  75   std::swap(Alt, Vec);
  76   EXPECT_TRUE(Copy == Alt);
  77   EXPECT_TRUE(Vec.size() == 6);
  78   EXPECT_TRUE(Vec.count() == 3);
  79   EXPECT_TRUE(Vec.find_first() == 3);
  80   std::swap(Copy, Vec);
  81
  82   // Add some more "interesting" data.
  83   Vec.resize(68, true);
  84   Vec.resize(78, false);
  85   Vec.resize(89, true);
  86   Vec.resize(90, false);
  87   Vec.resize(91, true);
  88   Vec.resize(130, false);
  89   Count = 0;
  90   for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) {
  91     ++Count;
  92     EXPECT_TRUE(Vec[i]);
  93     EXPECT_TRUE(Vec.test(i));
  94   }
  95   EXPECT_EQ(Count, Vec.count());
  96   EXPECT_EQ(Count, 42u);
  97   EXPECT_FALSE(Vec[0]);
  98   EXPECT_TRUE(Vec[32]);
  99   EXPECT_FALSE(Vec[60]);
 100   EXPECT_FALSE(Vec[129]);
 101
 102   Vec.flip(60);
 103   EXPECT_TRUE(Vec[60]);
 104   EXPECT_EQ(Count + 1, Vec.count());
 105   Vec.flip(60);
 106   EXPECT_FALSE(Vec[60]);
 107   EXPECT_EQ(Count, Vec.count());
 108
 109   Vec.reset(32);
 110   EXPECT_FALSE(Vec[32]);
 111   EXPECT_EQ(Count - 1, Vec.count());
 112   Vec.set(32);
 113   EXPECT_TRUE(Vec[32]);
 114   EXPECT_EQ(Count, Vec.count());
 115
 116   Vec.flip();
 117   EXPECT_EQ(Vec.size() - Count, Vec.count());
 118
 119   Vec.reset();
 120   EXPECT_EQ(0U, Vec.count());
 121   EXPECT_EQ(130U, Vec.size());
 122   EXPECT_FALSE(Vec.any());
 123   EXPECT_TRUE(Vec.none());
 124   EXPECT_FALSE(Vec.empty());
 125
 126   Inv = ~SmallBitVector();
 127   EXPECT_EQ(0U, Inv.count());
 128   EXPECT_EQ(0U, Inv.size());
 129   EXPECT_FALSE(Inv.any());
 130   EXPECT_TRUE(Inv.none());
 131   EXPECT_TRUE(Inv.empty());
 132
 133   Vec.clear();
 134   EXPECT_EQ(0U, Vec.count());
 135   EXPECT_EQ(0U, Vec.size());
 136   EXPECT_FALSE(Vec.any());
 137   EXPECT_TRUE(Vec.none());
 138   EXPECT_TRUE(Vec.empty());
 139 }
 140
 141 TEST(SmallBitVectorTest, CompoundAssignment) {
 142   SmallBitVector A;
 143   A.resize(10);
 144   A.set(4);
 145   A.set(7);
 146
 147   SmallBitVector B;
 148   B.resize(50);
 149   B.set(5);
 150   B.set(18);
 151
 152   A |= B;
 153   EXPECT_TRUE(A.test(4));
 154   EXPECT_TRUE(A.test(5));
 155   EXPECT_TRUE(A.test(7));
 156   EXPECT_TRUE(A.test(18));
 157   EXPECT_EQ(4U, A.count());
 158   EXPECT_EQ(50U, A.size());
 159
 160   B.resize(10);
 161   B.set();
 162   B.reset(2);
 163   B.reset(7);
 164   A &= B;
 165   EXPECT_FALSE(A.test(2));
 166   EXPECT_FALSE(A.test(7));
 167   EXPECT_EQ(2U, A.count());
 168   EXPECT_EQ(50U, A.size());
 169
 170   B.resize(100);
 171   B.set();
 172
 173   A ^= B;
 174   EXPECT_TRUE(A.test(2));
 175   EXPECT_TRUE(A.test(7));
 176   EXPECT_EQ(98U, A.count());
 177   EXPECT_EQ(100U, A.size());
 178 }
 179
 180 TEST(SmallBitVectorTest, ProxyIndex) {
 181   SmallBitVector Vec(3);
 182   EXPECT_TRUE(Vec.none());
 183   Vec[0] = Vec[1] = Vec[2] = true;
 184   EXPECT_EQ(Vec.size(), Vec.count());
 185   Vec[2] = Vec[1] = Vec[0] = false;
 186   EXPECT_TRUE(Vec.none());
 187 }
 188
 189 }