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, SimpleFindOps) { 186 // Test finding in an empty BitVector. 187 TypeParam A; 188 EXPECT_EQ(-1, A.find_first()); 189 EXPECT_EQ(-1, A.find_last()); 190 EXPECT_EQ(-1, A.find_first_unset()); 191 EXPECT_EQ(-1, A.find_last_unset()); 192 193 // Test finding next set and unset bits in a BitVector with multiple words 194 A.resize(100); 195 A.set(12); 196 A.set(13); 197 A.set(75); 198 199 EXPECT_EQ(75, A.find_last()); 200 EXPECT_EQ(12, A.find_first()); 201 EXPECT_EQ(13, A.find_next(12)); 202 EXPECT_EQ(75, A.find_next(13)); 203 EXPECT_EQ(-1, A.find_next(75)); 204 205 EXPECT_EQ(-1, A.find_prev(12)); 206 EXPECT_EQ(12, A.find_prev(13)); 207 EXPECT_EQ(13, A.find_prev(75)); 208 EXPECT_EQ(75, A.find_prev(90)); 209 210 EXPECT_EQ(0, A.find_first_unset()); 211 EXPECT_EQ(99, A.find_last_unset()); 212 EXPECT_EQ(14, A.find_next_unset(11)); 213 EXPECT_EQ(14, A.find_next_unset(12)); 214 EXPECT_EQ(14, A.find_next_unset(13)); 215 EXPECT_EQ(16, A.find_next_unset(15)); 216 EXPECT_EQ(76, A.find_next_unset(74)); 217 EXPECT_EQ(76, A.find_next_unset(75)); 218 EXPECT_EQ(-1, A.find_next_unset(99)); 219 220 A.set(0, 100); 221 EXPECT_EQ(100U, A.count()); 222 EXPECT_EQ(0, A.find_first()); 223 EXPECT_EQ(-1, A.find_first_unset()); 224 EXPECT_EQ(-1, A.find_last_unset()); 225 EXPECT_EQ(99, A.find_last()); 226 EXPECT_EQ(99, A.find_next(98)); 227 228 A.reset(0, 100); 229 EXPECT_EQ(0U, A.count()); 230 EXPECT_EQ(-1, A.find_first()); 231 EXPECT_EQ(-1, A.find_last()); 232 EXPECT_EQ(0, A.find_first_unset()); 233 EXPECT_EQ(99, A.find_last_unset()); 234 EXPECT_EQ(99, A.find_next_unset(98)); 235 236 // Also test with a vector that is small enough to fit in 1 word. 237 A.resize(20); 238 A.set(3); 239 A.set(4); 240 A.set(16); 241 EXPECT_EQ(16, A.find_last()); 242 EXPECT_EQ(3, A.find_first()); 243 EXPECT_EQ(3, A.find_next(1)); 244 EXPECT_EQ(4, A.find_next(3)); 245 EXPECT_EQ(16, A.find_next(4)); 246 EXPECT_EQ(-1, A.find_next(16)); 247 248 EXPECT_EQ(-1, A.find_prev(3)); 249 EXPECT_EQ(3, A.find_prev(4)); 250 EXPECT_EQ(4, A.find_prev(16)); 251 EXPECT_EQ(16, A.find_prev(18)); 252 253 EXPECT_EQ(0, A.find_first_unset()); 254 EXPECT_EQ(19, A.find_last_unset()); 255 EXPECT_EQ(5, A.find_next_unset(3)); 256 EXPECT_EQ(5, A.find_next_unset(4)); 257 EXPECT_EQ(13, A.find_next_unset(12)); 258 EXPECT_EQ(17, A.find_next_unset(15)); 259 } 260 261 TEST(BitVectorTest, FindInRangeMultiWord) { 262 BitVector Vec; 263 264 Vec.resize(200); 265 Vec.set(3, 7); 266 Vec.set(24, 35); 267 Vec.set(50, 70); 268 Vec.set(150); 269 Vec.set(152); 270 Vec.set(154); 271 272 // find first 273 EXPECT_EQ(-1, Vec.find_first_in(0, 0)); 274 EXPECT_EQ(-1, Vec.find_first_in(24, 24)); 275 EXPECT_EQ(-1, Vec.find_first_in(7, 24)); 276 277 EXPECT_EQ(3, Vec.find_first_in(0, 10)); 278 EXPECT_EQ(4, Vec.find_first_in(4, 10)); 279 EXPECT_EQ(150, Vec.find_first_in(100, 200)); 280 EXPECT_EQ(152, Vec.find_first_in(151, 200)); 281 EXPECT_EQ(154, Vec.find_first_in(153, 200)); 282 283 EXPECT_EQ(-1, Vec.find_first_in(155, 200)); 284 Vec.set(199); 285 EXPECT_EQ(199, Vec.find_first_in(199, 200)); 286 Vec.reset(199); 287 288 // find last 289 EXPECT_EQ(-1, Vec.find_last_in(0, 0)); 290 EXPECT_EQ(-1, Vec.find_last_in(24, 24)); 291 EXPECT_EQ(-1, Vec.find_last_in(7, 24)); 292 293 EXPECT_EQ(6, Vec.find_last_in(0, 10)); 294 EXPECT_EQ(5, Vec.find_last_in(0, 6)); 295 EXPECT_EQ(154, Vec.find_last_in(100, 155)); 296 EXPECT_EQ(152, Vec.find_last_in(100, 154)); 297 EXPECT_EQ(150, Vec.find_last_in(100, 152)); 298 EXPECT_EQ(-1, Vec.find_last_in(100, 150)); 299 Vec.set(199); 300 EXPECT_EQ(199, Vec.find_last_in(199, 200)); 301 Vec.reset(199); 302 303 // find first unset 304 EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0)); 305 EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23)); 306 EXPECT_EQ(-1, Vec.find_first_unset_in(24, 35)); 307 308 EXPECT_EQ(0, Vec.find_first_unset_in(0, 10)); 309 EXPECT_EQ(1, Vec.find_first_unset_in(1, 10)); 310 EXPECT_EQ(7, Vec.find_first_unset_in(5, 25)); 311 EXPECT_EQ(151, Vec.find_first_unset_in(150, 200)); 312 EXPECT_EQ(151, Vec.find_first_unset_in(151, 200)); 313 EXPECT_EQ(153, Vec.find_first_unset_in(152, 200)); 314 EXPECT_EQ(153, Vec.find_first_unset_in(153, 200)); 315 EXPECT_EQ(155, Vec.find_first_unset_in(154, 200)); 316 EXPECT_EQ(155, Vec.find_first_unset_in(155, 200)); 317 EXPECT_EQ(199, Vec.find_first_unset_in(199, 200)); 318 319 // find last unset 320 EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0)); 321 EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23)); 322 EXPECT_EQ(-1, Vec.find_last_unset_in(24, 35)); 323 324 EXPECT_EQ(9, Vec.find_last_unset_in(0, 10)); 325 EXPECT_EQ(8, Vec.find_last_unset_in(0, 9)); 326 EXPECT_EQ(2, Vec.find_last_unset_in(0, 7)); 327 EXPECT_EQ(149, Vec.find_last_unset_in(100, 151)); 328 EXPECT_EQ(151, Vec.find_last_unset_in(100, 152)); 329 EXPECT_EQ(151, Vec.find_last_unset_in(100, 153)); 330 EXPECT_EQ(153, Vec.find_last_unset_in(100, 154)); 331 EXPECT_EQ(153, Vec.find_last_unset_in(100, 155)); 332 EXPECT_EQ(155, Vec.find_last_unset_in(100, 156)); 333 EXPECT_EQ(199, Vec.find_last_unset_in(199, 200)); 334 } 335 336 TEST(BitVectorTest, FindInRangeSingleWord) { 337 // When the bit vector contains only a single word, this is slightly different 338 // than when the bit vector contains multiple words, because masks are applied 339 // to the front and back of the same word. So make sure this works. 340 BitVector Vec; 341 342 Vec.resize(25); 343 Vec.set(2, 4); 344 Vec.set(6, 9); 345 Vec.set(12, 15); 346 Vec.set(19); 347 Vec.set(21); 348 Vec.set(23); 349 350 // find first 351 EXPECT_EQ(-1, Vec.find_first_in(0, 0)); 352 EXPECT_EQ(-1, Vec.find_first_in(24, 24)); 353 EXPECT_EQ(-1, Vec.find_first_in(9, 12)); 354 355 EXPECT_EQ(2, Vec.find_first_in(0, 10)); 356 EXPECT_EQ(6, Vec.find_first_in(4, 10)); 357 EXPECT_EQ(19, Vec.find_first_in(18, 25)); 358 EXPECT_EQ(21, Vec.find_first_in(20, 25)); 359 EXPECT_EQ(23, Vec.find_first_in(22, 25)); 360 EXPECT_EQ(-1, Vec.find_first_in(24, 25)); 361 362 // find last 363 EXPECT_EQ(-1, Vec.find_last_in(0, 0)); 364 EXPECT_EQ(-1, Vec.find_last_in(24, 24)); 365 EXPECT_EQ(-1, Vec.find_last_in(9, 12)); 366 367 EXPECT_EQ(8, Vec.find_last_in(0, 10)); 368 EXPECT_EQ(3, Vec.find_last_in(0, 6)); 369 EXPECT_EQ(23, Vec.find_last_in(18, 25)); 370 EXPECT_EQ(21, Vec.find_last_in(18, 23)); 371 EXPECT_EQ(19, Vec.find_last_in(18, 21)); 372 EXPECT_EQ(-1, Vec.find_last_in(18, 19)); 373 374 // find first unset 375 EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0)); 376 EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23)); 377 EXPECT_EQ(-1, Vec.find_first_unset_in(6, 9)); 378 379 EXPECT_EQ(0, Vec.find_first_unset_in(0, 6)); 380 EXPECT_EQ(1, Vec.find_first_unset_in(1, 6)); 381 EXPECT_EQ(9, Vec.find_first_unset_in(7, 13)); 382 EXPECT_EQ(18, Vec.find_first_unset_in(18, 25)); 383 EXPECT_EQ(20, Vec.find_first_unset_in(19, 25)); 384 EXPECT_EQ(20, Vec.find_first_unset_in(20, 25)); 385 EXPECT_EQ(22, Vec.find_first_unset_in(21, 25)); 386 EXPECT_EQ(22, Vec.find_first_unset_in(22, 25)); 387 EXPECT_EQ(24, Vec.find_first_unset_in(23, 25)); 388 EXPECT_EQ(24, Vec.find_first_unset_in(24, 25)); 389 390 // find last unset 391 EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0)); 392 EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23)); 393 EXPECT_EQ(-1, Vec.find_last_unset_in(6, 9)); 394 395 EXPECT_EQ(5, Vec.find_last_unset_in(0, 6)); 396 EXPECT_EQ(4, Vec.find_last_unset_in(0, 5)); 397 EXPECT_EQ(1, Vec.find_last_unset_in(0, 4)); 398 EXPECT_EQ(11, Vec.find_last_unset_in(7, 13)); 399 EXPECT_EQ(24, Vec.find_last_unset_in(18, 25)); 400 EXPECT_EQ(22, Vec.find_last_unset_in(18, 24)); 401 EXPECT_EQ(22, Vec.find_last_unset_in(18, 23)); 402 EXPECT_EQ(20, Vec.find_last_unset_in(18, 22)); 403 EXPECT_EQ(20, Vec.find_last_unset_in(18, 21)); 404 EXPECT_EQ(18, Vec.find_last_unset_in(18, 20)); 405 EXPECT_EQ(18, Vec.find_last_unset_in(18, 19)); 406 } 407 408 TYPED_TEST(BitVectorTest, CompoundAssignment) { 409 TypeParam A; 410 A.resize(10); 411 A.set(4); 412 A.set(7); 413 414 TypeParam B; 415 B.resize(50); 416 B.set(5); 417 B.set(18); 418 419 A |= B; 420 EXPECT_TRUE(A.test(4)); 421 EXPECT_TRUE(A.test(5)); 422 EXPECT_TRUE(A.test(7)); 423 EXPECT_TRUE(A.test(18)); 424 EXPECT_EQ(4U, A.count()); 425 EXPECT_EQ(50U, A.size()); 426 427 B.resize(10); 428 B.set(); 429 B.reset(2); 430 B.reset(7); 431 A &= B; 432 EXPECT_FALSE(A.test(2)); 433 EXPECT_FALSE(A.test(7)); 434 EXPECT_EQ(2U, A.count()); 435 EXPECT_EQ(50U, A.size()); 436 437 B.resize(100); 438 B.set(); 439 440 A ^= B; 441 EXPECT_TRUE(A.test(2)); 442 EXPECT_TRUE(A.test(7)); 443 EXPECT_EQ(98U, A.count()); 444 EXPECT_EQ(100U, A.size()); 445 } 446 447 TYPED_TEST(BitVectorTest, ProxyIndex) { 448 TypeParam Vec(3); 449 EXPECT_TRUE(Vec.none()); 450 Vec[0] = Vec[1] = Vec[2] = true; 451 EXPECT_EQ(Vec.size(), Vec.count()); 452 Vec[2] = Vec[1] = Vec[0] = false; 453 EXPECT_TRUE(Vec.none()); 454 } 455 456 TYPED_TEST(BitVectorTest, PortableBitMask) { 457 TypeParam A; 458 const uint32_t Mask1[] = { 0x80000000, 6, 5 }; 459 460 A.resize(10); 461 A.setBitsInMask(Mask1, 1); 462 EXPECT_EQ(10u, A.size()); 463 EXPECT_FALSE(A.test(0)); 464 465 A.resize(32); 466 A.setBitsInMask(Mask1, 1); 467 EXPECT_FALSE(A.test(0)); 468 EXPECT_TRUE(A.test(31)); 469 EXPECT_EQ(1u, A.count()); 470 471 A.resize(33); 472 A.setBitsInMask(Mask1, 1); 473 EXPECT_EQ(1u, A.count()); 474 A.setBitsInMask(Mask1, 2); 475 EXPECT_EQ(1u, A.count()); 476 477 A.resize(34); 478 A.setBitsInMask(Mask1, 2); 479 EXPECT_EQ(2u, A.count()); 480 481 A.resize(65); 482 A.setBitsInMask(Mask1, 3); 483 EXPECT_EQ(4u, A.count()); 484 485 A.setBitsNotInMask(Mask1, 1); 486 EXPECT_EQ(32u+3u, A.count()); 487 488 A.setBitsNotInMask(Mask1, 3); 489 EXPECT_EQ(65u, A.count()); 490 491 A.resize(96); 492 EXPECT_EQ(65u, A.count()); 493 494 A.clear(); 495 A.resize(128); 496 A.setBitsNotInMask(Mask1, 3); 497 EXPECT_EQ(96u-5u, A.count()); 498 499 A.clearBitsNotInMask(Mask1, 1); 500 EXPECT_EQ(64-4u, A.count()); 501 } 502 503 TYPED_TEST(BitVectorTest, BinOps) { 504 TypeParam A; 505 TypeParam B; 506 507 A.resize(65); 508 EXPECT_FALSE(A.anyCommon(B)); 509 EXPECT_FALSE(B.anyCommon(B)); 510 511 B.resize(64); 512 A.set(64); 513 EXPECT_FALSE(A.anyCommon(B)); 514 EXPECT_FALSE(B.anyCommon(A)); 515 516 B.set(63); 517 EXPECT_FALSE(A.anyCommon(B)); 518 EXPECT_FALSE(B.anyCommon(A)); 519 520 A.set(63); 521 EXPECT_TRUE(A.anyCommon(B)); 522 EXPECT_TRUE(B.anyCommon(A)); 523 524 B.resize(70); 525 B.set(64); 526 B.reset(63); 527 A.resize(64); 528 EXPECT_FALSE(A.anyCommon(B)); 529 EXPECT_FALSE(B.anyCommon(A)); 530 } 531 532 typedef std::vector<std::pair<int, int>> RangeList; 533 534 template <typename VecType> 535 static inline VecType createBitVector(uint32_t Size, 536 const RangeList &setRanges) { 537 VecType V; 538 V.resize(Size); 539 for (auto &R : setRanges) 540 V.set(R.first, R.second); 541 return V; 542 } 543 544 TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) { 545 // Test that shift ops work when the desired shift amount is less 546 // than one word. 547 548 // 1. Case where the number of bits in the BitVector also fit into a single 549 // word. 550 TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}}); 551 TypeParam B = A; 552 553 EXPECT_EQ(4U, A.count()); 554 EXPECT_TRUE(A.test(2)); 555 EXPECT_TRUE(A.test(3)); 556 EXPECT_TRUE(A.test(8)); 557 EXPECT_TRUE(A.test(9)); 558 559 A >>= 1; 560 EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A); 561 562 A <<= 1; 563 EXPECT_EQ(B, A); 564 565 A >>= 10; 566 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); 567 568 A = B; 569 A <<= 10; 570 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); 571 572 // 2. Case where the number of bits in the BitVector do not fit into a single 573 // word. 574 575 // 31----------------------------------------------------------------------0 576 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 577 A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}}); 578 EXPECT_EQ(40U, A.size()); 579 EXPECT_EQ(22U, A.count()); 580 581 // 2a. Make sure that left shifting some 1 bits out of the vector works. 582 // 31----------------------------------------------------------------------0 583 // Before: 584 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 585 // After: 586 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 587 A <<= 9; 588 EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A); 589 590 // 2b. Make sure that keeping the number of one bits unchanged works. 591 // 31----------------------------------------------------------------------0 592 // Before: 593 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 594 // After: 595 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 596 A >>= 6; 597 EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A); 598 599 // 2c. Make sure that right shifting some 1 bits out of the vector works. 600 // 31----------------------------------------------------------------------0 601 // Before: 602 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 603 // After: 604 // XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111 605 A >>= 10; 606 EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A); 607 608 // 3. Big test. 609 A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); 610 A <<= 29; 611 EXPECT_EQ(createBitVector<TypeParam>( 612 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}), 613 A); 614 } 615 616 TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) { 617 // Test that shift ops work when the desired shift amount is greater than or 618 // equal to the size of a single word. 619 auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); 620 621 // Make a copy so we can re-use it later. 622 auto B = A; 623 624 // 1. Shift left by an exact multiple of the word size. This should invoke 625 // only a memmove and no per-word bit operations. 626 A <<= 64; 627 auto Expected = createBitVector<TypeParam>( 628 300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}}); 629 EXPECT_EQ(Expected, A); 630 631 // 2. Shift left by a non multiple of the word size. This should invoke both 632 // a memmove and per-word bit operations. 633 A = B; 634 A <<= 93; 635 EXPECT_EQ(createBitVector<TypeParam>( 636 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}), 637 A); 638 639 // 1. Shift right by an exact multiple of the word size. This should invoke 640 // only a memmove and no per-word bit operations. 641 A = B; 642 A >>= 64; 643 EXPECT_EQ( 644 createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A); 645 646 // 2. Shift left by a non multiple of the word size. This should invoke both 647 // a memmove and per-word bit operations. 648 A = B; 649 A >>= 93; 650 EXPECT_EQ( 651 createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A); 652 } 653 654 TYPED_TEST(BitVectorTest, RangeOps) { 655 TypeParam A; 656 A.resize(256); 657 A.reset(); 658 A.set(1, 255); 659 660 EXPECT_FALSE(A.test(0)); 661 EXPECT_TRUE( A.test(1)); 662 EXPECT_TRUE( A.test(23)); 663 EXPECT_TRUE( A.test(254)); 664 EXPECT_FALSE(A.test(255)); 665 666 TypeParam B; 667 B.resize(256); 668 B.set(); 669 B.reset(1, 255); 670 671 EXPECT_TRUE( B.test(0)); 672 EXPECT_FALSE(B.test(1)); 673 EXPECT_FALSE(B.test(23)); 674 EXPECT_FALSE(B.test(254)); 675 EXPECT_TRUE( B.test(255)); 676 677 TypeParam C; 678 C.resize(3); 679 C.reset(); 680 C.set(0, 1); 681 682 EXPECT_TRUE(C.test(0)); 683 EXPECT_FALSE( C.test(1)); 684 EXPECT_FALSE( C.test(2)); 685 686 TypeParam D; 687 D.resize(3); 688 D.set(); 689 D.reset(0, 1); 690 691 EXPECT_FALSE(D.test(0)); 692 EXPECT_TRUE( D.test(1)); 693 EXPECT_TRUE( D.test(2)); 694 695 TypeParam E; 696 E.resize(128); 697 E.reset(); 698 E.set(1, 33); 699 700 EXPECT_FALSE(E.test(0)); 701 EXPECT_TRUE( E.test(1)); 702 EXPECT_TRUE( E.test(32)); 703 EXPECT_FALSE(E.test(33)); 704 705 TypeParam BufferOverrun; 706 unsigned size = sizeof(unsigned long) * 8; 707 BufferOverrun.resize(size); 708 BufferOverrun.reset(0, size); 709 BufferOverrun.set(0, size); 710 } 711 712 TYPED_TEST(BitVectorTest, CompoundTestReset) { 713 TypeParam A(50, true); 714 TypeParam B(50, false); 715 716 TypeParam C(100, true); 717 TypeParam D(100, false); 718 719 EXPECT_FALSE(A.test(A)); 720 EXPECT_TRUE(A.test(B)); 721 EXPECT_FALSE(A.test(C)); 722 EXPECT_TRUE(A.test(D)); 723 EXPECT_FALSE(B.test(A)); 724 EXPECT_FALSE(B.test(B)); 725 EXPECT_FALSE(B.test(C)); 726 EXPECT_FALSE(B.test(D)); 727 EXPECT_TRUE(C.test(A)); 728 EXPECT_TRUE(C.test(B)); 729 EXPECT_FALSE(C.test(C)); 730 EXPECT_TRUE(C.test(D)); 731 732 A.reset(B); 733 A.reset(D); 734 EXPECT_TRUE(A.all()); 735 A.reset(A); 736 EXPECT_TRUE(A.none()); 737 A.set(); 738 A.reset(C); 739 EXPECT_TRUE(A.none()); 740 A.set(); 741 742 C.reset(A); 743 EXPECT_EQ(50, C.find_first()); 744 C.reset(C); 745 EXPECT_TRUE(C.none()); 746 } 747 748 TYPED_TEST(BitVectorTest, MoveConstructor) { 749 TypeParam A(10, true); 750 TypeParam B(std::move(A)); 751 // Check that the move ctor leaves the moved-from object in a valid state. 752 // The following line used to crash. 753 A = B; 754 755 TypeParam C(10, true); 756 EXPECT_EQ(C, A); 757 EXPECT_EQ(C, B); 758 } 759 760 TYPED_TEST(BitVectorTest, MoveAssignment) { 761 TypeParam A(10, true); 762 TypeParam B; 763 B = std::move(A); 764 // Check that move assignment leaves the moved-from object in a valid state. 765 // The following line used to crash. 766 A = B; 767 768 TypeParam C(10, true); 769 EXPECT_EQ(C, A); 770 EXPECT_EQ(C, B); 771 } 772 773 template<class TypeParam> 774 static void testEmpty(const TypeParam &A) { 775 EXPECT_TRUE(A.empty()); 776 EXPECT_EQ((size_t)0, A.size()); 777 EXPECT_EQ((size_t)0, A.count()); 778 EXPECT_FALSE(A.any()); 779 EXPECT_TRUE(A.all()); 780 EXPECT_TRUE(A.none()); 781 EXPECT_EQ(-1, A.find_first()); 782 EXPECT_EQ(A, TypeParam()); 783 } 784 785 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0 786 TYPED_TEST(BitVectorTest, EmptyVector) { 787 TypeParam A; 788 testEmpty(A); 789 790 TypeParam B; 791 B.reset(); 792 testEmpty(B); 793 794 TypeParam C; 795 C.clear(); 796 testEmpty(C); 797 798 TypeParam D(A); 799 testEmpty(D); 800 801 TypeParam E; 802 E = A; 803 testEmpty(E); 804 805 TypeParam F; 806 E.reset(A); 807 testEmpty(E); 808 } 809 810 TYPED_TEST(BitVectorTest, Iterators) { 811 TypeParam Filled(10, true); 812 EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end()); 813 unsigned Counter = 0; 814 for (unsigned Bit : Filled.set_bits()) 815 EXPECT_EQ(Bit, Counter++); 816 817 TypeParam Empty; 818 EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end()); 819 for (unsigned Bit : Empty.set_bits()) { 820 (void)Bit; 821 EXPECT_TRUE(false); 822 } 823 824 TypeParam ToFill(100, false); 825 ToFill.set(0); 826 EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end()); 827 EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end()); 828 EXPECT_EQ(*ToFill.set_bits_begin(), 0U); 829 ToFill.reset(0); 830 EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end()); 831 832 const unsigned List[] = {1, 10, 25, 99}; 833 for (unsigned Num : List) 834 ToFill.set(Num); 835 unsigned i = 0; 836 for (unsigned Bit : ToFill.set_bits()) 837 EXPECT_EQ(List[i++], Bit); 838 } 839 840 TYPED_TEST(BitVectorTest, PushBack) { 841 TypeParam Vec(10, false); 842 EXPECT_EQ(-1, Vec.find_first()); 843 EXPECT_EQ(10U, Vec.size()); 844 EXPECT_EQ(0U, Vec.count()); 845 846 Vec.push_back(true); 847 EXPECT_EQ(10, Vec.find_first()); 848 EXPECT_EQ(11U, Vec.size()); 849 EXPECT_EQ(1U, Vec.count()); 850 851 Vec.push_back(false); 852 EXPECT_EQ(10, Vec.find_first()); 853 EXPECT_EQ(12U, Vec.size()); 854 EXPECT_EQ(1U, Vec.count()); 855 856 Vec.push_back(true); 857 EXPECT_EQ(10, Vec.find_first()); 858 EXPECT_EQ(13U, Vec.size()); 859 EXPECT_EQ(2U, Vec.count()); 860 861 // Add a lot of values to cause reallocation. 862 for (int i = 0; i != 100; ++i) { 863 Vec.push_back(true); 864 Vec.push_back(false); 865 } 866 EXPECT_EQ(10, Vec.find_first()); 867 EXPECT_EQ(213U, Vec.size()); 868 EXPECT_EQ(102U, Vec.count()); 869 } 870 } 871 #endif 872