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 277