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, SimpleFindOpsMultiWord) { 186 TypeParam A; 187 188 // Test finding next set and unset bits in a BitVector with multiple words 189 A.resize(100); 190 A.set(12); 191 A.set(13); 192 A.set(75); 193 194 EXPECT_EQ(75, A.find_last()); 195 EXPECT_EQ(12, A.find_first()); 196 EXPECT_EQ(13, A.find_next(12)); 197 EXPECT_EQ(75, A.find_next(13)); 198 EXPECT_EQ(-1, A.find_next(75)); 199 200 EXPECT_EQ(-1, A.find_prev(12)); 201 EXPECT_EQ(12, A.find_prev(13)); 202 EXPECT_EQ(13, A.find_prev(75)); 203 EXPECT_EQ(75, A.find_prev(90)); 204 205 EXPECT_EQ(0, A.find_first_unset()); 206 EXPECT_EQ(99, A.find_last_unset()); 207 EXPECT_EQ(14, A.find_next_unset(11)); 208 EXPECT_EQ(14, A.find_next_unset(12)); 209 EXPECT_EQ(14, A.find_next_unset(13)); 210 EXPECT_EQ(16, A.find_next_unset(15)); 211 EXPECT_EQ(76, A.find_next_unset(74)); 212 EXPECT_EQ(76, A.find_next_unset(75)); 213 EXPECT_EQ(-1, A.find_next_unset(99)); 214 215 A.set(0, 100); 216 EXPECT_EQ(100U, A.count()); 217 EXPECT_EQ(0, A.find_first()); 218 EXPECT_EQ(-1, A.find_first_unset()); 219 EXPECT_EQ(-1, A.find_last_unset()); 220 EXPECT_EQ(99, A.find_last()); 221 EXPECT_EQ(99, A.find_next(98)); 222 223 A.reset(0, 100); 224 EXPECT_EQ(0U, A.count()); 225 EXPECT_EQ(-1, A.find_first()); 226 EXPECT_EQ(-1, A.find_last()); 227 EXPECT_EQ(0, A.find_first_unset()); 228 EXPECT_EQ(99, A.find_last_unset()); 229 EXPECT_EQ(99, A.find_next_unset(98)); 230 } 231 232 // Check if a SmallBitVector is in small mode. This check is used in tests 233 // that run for both SmallBitVector and BitVector. This check doesn't apply 234 // to BitVector so we provide an overload that returns true to get the tests 235 // to compile. 236 static bool SmallBitVectorIsSmallMode(const SmallBitVector &bv) { 237 return bv.isSmall(); 238 } 239 static bool SmallBitVectorIsSmallMode(const BitVector &) { return true; } 240 241 // These tests are intended to exercise the single-word case of BitVector 242 // and the small-mode case of SmallBitVector. 243 TYPED_TEST(BitVectorTest, SimpleFindOpsSingleWord) { 244 // Test finding in an empty BitVector. 245 TypeParam A; 246 ASSERT_TRUE(SmallBitVectorIsSmallMode(A)); 247 EXPECT_EQ(-1, A.find_first()); 248 EXPECT_EQ(-1, A.find_last()); 249 EXPECT_EQ(-1, A.find_first_unset()); 250 EXPECT_EQ(-1, A.find_last_unset()); 251 252 A.resize(20); 253 A.set(3); 254 A.set(4); 255 A.set(16); 256 ASSERT_TRUE(SmallBitVectorIsSmallMode(A)); 257 EXPECT_EQ(16, A.find_last()); 258 EXPECT_EQ(3, A.find_first()); 259 EXPECT_EQ(3, A.find_next(1)); 260 EXPECT_EQ(4, A.find_next(3)); 261 EXPECT_EQ(16, A.find_next(4)); 262 EXPECT_EQ(-1, A.find_next(16)); 263 264 EXPECT_EQ(-1, A.find_prev(3)); 265 EXPECT_EQ(3, A.find_prev(4)); 266 EXPECT_EQ(4, A.find_prev(16)); 267 EXPECT_EQ(16, A.find_prev(18)); 268 269 EXPECT_EQ(0, A.find_first_unset()); 270 EXPECT_EQ(19, A.find_last_unset()); 271 EXPECT_EQ(5, A.find_next_unset(3)); 272 EXPECT_EQ(5, A.find_next_unset(4)); 273 EXPECT_EQ(13, A.find_next_unset(12)); 274 EXPECT_EQ(17, A.find_next_unset(15)); 275 } 276 277 TEST(BitVectorTest, FindInRangeMultiWord) { 278 BitVector Vec; 279 280 Vec.resize(200); 281 Vec.set(3, 7); 282 Vec.set(24, 35); 283 Vec.set(50, 70); 284 Vec.set(150); 285 Vec.set(152); 286 Vec.set(154); 287 288 // find first 289 EXPECT_EQ(-1, Vec.find_first_in(0, 0)); 290 EXPECT_EQ(-1, Vec.find_first_in(24, 24)); 291 EXPECT_EQ(-1, Vec.find_first_in(7, 24)); 292 293 EXPECT_EQ(3, Vec.find_first_in(0, 10)); 294 EXPECT_EQ(4, Vec.find_first_in(4, 10)); 295 EXPECT_EQ(150, Vec.find_first_in(100, 200)); 296 EXPECT_EQ(152, Vec.find_first_in(151, 200)); 297 EXPECT_EQ(154, Vec.find_first_in(153, 200)); 298 299 EXPECT_EQ(-1, Vec.find_first_in(155, 200)); 300 Vec.set(199); 301 EXPECT_EQ(199, Vec.find_first_in(199, 200)); 302 Vec.reset(199); 303 304 // find last 305 EXPECT_EQ(-1, Vec.find_last_in(0, 0)); 306 EXPECT_EQ(-1, Vec.find_last_in(24, 24)); 307 EXPECT_EQ(-1, Vec.find_last_in(7, 24)); 308 309 EXPECT_EQ(6, Vec.find_last_in(0, 10)); 310 EXPECT_EQ(5, Vec.find_last_in(0, 6)); 311 EXPECT_EQ(154, Vec.find_last_in(100, 155)); 312 EXPECT_EQ(152, Vec.find_last_in(100, 154)); 313 EXPECT_EQ(150, Vec.find_last_in(100, 152)); 314 EXPECT_EQ(-1, Vec.find_last_in(100, 150)); 315 Vec.set(199); 316 EXPECT_EQ(199, Vec.find_last_in(199, 200)); 317 Vec.reset(199); 318 319 // find first unset 320 EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0)); 321 EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23)); 322 EXPECT_EQ(-1, Vec.find_first_unset_in(24, 35)); 323 324 EXPECT_EQ(0, Vec.find_first_unset_in(0, 10)); 325 EXPECT_EQ(1, Vec.find_first_unset_in(1, 10)); 326 EXPECT_EQ(7, Vec.find_first_unset_in(5, 25)); 327 EXPECT_EQ(151, Vec.find_first_unset_in(150, 200)); 328 EXPECT_EQ(151, Vec.find_first_unset_in(151, 200)); 329 EXPECT_EQ(153, Vec.find_first_unset_in(152, 200)); 330 EXPECT_EQ(153, Vec.find_first_unset_in(153, 200)); 331 EXPECT_EQ(155, Vec.find_first_unset_in(154, 200)); 332 EXPECT_EQ(155, Vec.find_first_unset_in(155, 200)); 333 EXPECT_EQ(199, Vec.find_first_unset_in(199, 200)); 334 335 // find last unset 336 EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0)); 337 EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23)); 338 EXPECT_EQ(-1, Vec.find_last_unset_in(24, 35)); 339 340 EXPECT_EQ(9, Vec.find_last_unset_in(0, 10)); 341 EXPECT_EQ(8, Vec.find_last_unset_in(0, 9)); 342 EXPECT_EQ(2, Vec.find_last_unset_in(0, 7)); 343 EXPECT_EQ(149, Vec.find_last_unset_in(100, 151)); 344 EXPECT_EQ(151, Vec.find_last_unset_in(100, 152)); 345 EXPECT_EQ(151, Vec.find_last_unset_in(100, 153)); 346 EXPECT_EQ(153, Vec.find_last_unset_in(100, 154)); 347 EXPECT_EQ(153, Vec.find_last_unset_in(100, 155)); 348 EXPECT_EQ(155, Vec.find_last_unset_in(100, 156)); 349 EXPECT_EQ(199, Vec.find_last_unset_in(199, 200)); 350 } 351 352 TEST(BitVectorTest, FindInRangeSingleWord) { 353 // When the bit vector contains only a single word, this is slightly different 354 // than when the bit vector contains multiple words, because masks are applied 355 // to the front and back of the same word. So make sure this works. 356 BitVector Vec; 357 358 Vec.resize(25); 359 Vec.set(2, 4); 360 Vec.set(6, 9); 361 Vec.set(12, 15); 362 Vec.set(19); 363 Vec.set(21); 364 Vec.set(23); 365 366 // find first 367 EXPECT_EQ(-1, Vec.find_first_in(0, 0)); 368 EXPECT_EQ(-1, Vec.find_first_in(24, 24)); 369 EXPECT_EQ(-1, Vec.find_first_in(9, 12)); 370 371 EXPECT_EQ(2, Vec.find_first_in(0, 10)); 372 EXPECT_EQ(6, Vec.find_first_in(4, 10)); 373 EXPECT_EQ(19, Vec.find_first_in(18, 25)); 374 EXPECT_EQ(21, Vec.find_first_in(20, 25)); 375 EXPECT_EQ(23, Vec.find_first_in(22, 25)); 376 EXPECT_EQ(-1, Vec.find_first_in(24, 25)); 377 378 // find last 379 EXPECT_EQ(-1, Vec.find_last_in(0, 0)); 380 EXPECT_EQ(-1, Vec.find_last_in(24, 24)); 381 EXPECT_EQ(-1, Vec.find_last_in(9, 12)); 382 383 EXPECT_EQ(8, Vec.find_last_in(0, 10)); 384 EXPECT_EQ(3, Vec.find_last_in(0, 6)); 385 EXPECT_EQ(23, Vec.find_last_in(18, 25)); 386 EXPECT_EQ(21, Vec.find_last_in(18, 23)); 387 EXPECT_EQ(19, Vec.find_last_in(18, 21)); 388 EXPECT_EQ(-1, Vec.find_last_in(18, 19)); 389 390 // find first unset 391 EXPECT_EQ(-1, Vec.find_first_unset_in(0, 0)); 392 EXPECT_EQ(-1, Vec.find_first_unset_in(23, 23)); 393 EXPECT_EQ(-1, Vec.find_first_unset_in(6, 9)); 394 395 EXPECT_EQ(0, Vec.find_first_unset_in(0, 6)); 396 EXPECT_EQ(1, Vec.find_first_unset_in(1, 6)); 397 EXPECT_EQ(9, Vec.find_first_unset_in(7, 13)); 398 EXPECT_EQ(18, Vec.find_first_unset_in(18, 25)); 399 EXPECT_EQ(20, Vec.find_first_unset_in(19, 25)); 400 EXPECT_EQ(20, Vec.find_first_unset_in(20, 25)); 401 EXPECT_EQ(22, Vec.find_first_unset_in(21, 25)); 402 EXPECT_EQ(22, Vec.find_first_unset_in(22, 25)); 403 EXPECT_EQ(24, Vec.find_first_unset_in(23, 25)); 404 EXPECT_EQ(24, Vec.find_first_unset_in(24, 25)); 405 406 // find last unset 407 EXPECT_EQ(-1, Vec.find_last_unset_in(0, 0)); 408 EXPECT_EQ(-1, Vec.find_last_unset_in(23, 23)); 409 EXPECT_EQ(-1, Vec.find_last_unset_in(6, 9)); 410 411 EXPECT_EQ(5, Vec.find_last_unset_in(0, 6)); 412 EXPECT_EQ(4, Vec.find_last_unset_in(0, 5)); 413 EXPECT_EQ(1, Vec.find_last_unset_in(0, 4)); 414 EXPECT_EQ(11, Vec.find_last_unset_in(7, 13)); 415 EXPECT_EQ(24, Vec.find_last_unset_in(18, 25)); 416 EXPECT_EQ(22, Vec.find_last_unset_in(18, 24)); 417 EXPECT_EQ(22, Vec.find_last_unset_in(18, 23)); 418 EXPECT_EQ(20, Vec.find_last_unset_in(18, 22)); 419 EXPECT_EQ(20, Vec.find_last_unset_in(18, 21)); 420 EXPECT_EQ(18, Vec.find_last_unset_in(18, 20)); 421 EXPECT_EQ(18, Vec.find_last_unset_in(18, 19)); 422 } 423 424 TYPED_TEST(BitVectorTest, CompoundAssignment) { 425 TypeParam A; 426 A.resize(10); 427 A.set(4); 428 A.set(7); 429 430 TypeParam B; 431 B.resize(50); 432 B.set(5); 433 B.set(18); 434 435 A |= B; 436 EXPECT_TRUE(A.test(4)); 437 EXPECT_TRUE(A.test(5)); 438 EXPECT_TRUE(A.test(7)); 439 EXPECT_TRUE(A.test(18)); 440 EXPECT_EQ(4U, A.count()); 441 EXPECT_EQ(50U, A.size()); 442 443 B.resize(10); 444 B.set(); 445 B.reset(2); 446 B.reset(7); 447 A &= B; 448 EXPECT_FALSE(A.test(2)); 449 EXPECT_FALSE(A.test(7)); 450 EXPECT_TRUE(A.test(4)); 451 EXPECT_TRUE(A.test(5)); 452 EXPECT_EQ(2U, A.count()); 453 EXPECT_EQ(50U, A.size()); 454 455 B.resize(100); 456 B.set(); 457 458 A ^= B; 459 EXPECT_TRUE(A.test(2)); 460 EXPECT_TRUE(A.test(7)); 461 EXPECT_EQ(98U, A.count()); 462 EXPECT_EQ(100U, A.size()); 463 } 464 465 // Test SmallBitVector operations with mixed big/small representations 466 TYPED_TEST(BitVectorTest, MixedBigSmall) { 467 { 468 TypeParam Big; 469 TypeParam Small; 470 471 Big.reserve(100); 472 Big.resize(20); 473 Small.resize(10); 474 475 Small.set(0); 476 Small.set(1); 477 Big.set(0); 478 Big.set(2); 479 Big.set(16); 480 481 Small &= Big; 482 EXPECT_TRUE(Small.test(0)); 483 EXPECT_EQ(1u, Small.count()); 484 // FIXME BitVector and SmallBitVector behave differently here. 485 // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size()) 486 // but BitVector does not. 487 // EXPECT_EQ(20u, Small.size()); 488 } 489 490 { 491 TypeParam Big; 492 TypeParam Small; 493 494 Big.reserve(100); 495 Big.resize(20); 496 Small.resize(10); 497 498 Small.set(0); 499 Small.set(1); 500 Big.set(0); 501 Big.set(2); 502 Big.set(16); 503 504 Big &= Small; 505 EXPECT_TRUE(Big.test(0)); 506 EXPECT_EQ(1u, Big.count()); 507 // FIXME BitVector and SmallBitVector behave differently here. 508 // SmallBitVector resizes the LHS to max(LHS.size(), RHS.size()) 509 // but BitVector does not. 510 // EXPECT_EQ(20u, Big.size()); 511 } 512 513 { 514 TypeParam Big; 515 TypeParam Small; 516 517 Big.reserve(100); 518 Big.resize(20); 519 Small.resize(10); 520 521 Small.set(0); 522 Small.set(1); 523 Big.set(0); 524 Big.set(2); 525 Big.set(16); 526 527 Small |= Big; 528 EXPECT_TRUE(Small.test(0)); 529 EXPECT_TRUE(Small.test(1)); 530 EXPECT_TRUE(Small.test(2)); 531 EXPECT_TRUE(Small.test(16)); 532 EXPECT_EQ(4u, Small.count()); 533 EXPECT_EQ(20u, Small.size()); 534 } 535 536 { 537 TypeParam Big; 538 TypeParam Small; 539 540 Big.reserve(100); 541 Big.resize(20); 542 Small.resize(10); 543 544 Small.set(0); 545 Small.set(1); 546 Big.set(0); 547 Big.set(2); 548 Big.set(16); 549 550 Big |= Small; 551 EXPECT_TRUE(Big.test(0)); 552 EXPECT_TRUE(Big.test(1)); 553 EXPECT_TRUE(Big.test(2)); 554 EXPECT_TRUE(Big.test(16)); 555 EXPECT_EQ(4u, Big.count()); 556 EXPECT_EQ(20u, Big.size()); 557 } 558 559 { 560 TypeParam Big; 561 TypeParam Small; 562 563 Big.reserve(100); 564 Big.resize(20); 565 Small.resize(10); 566 567 Small.set(0); 568 Small.set(1); 569 Big.set(0); 570 Big.set(2); 571 Big.set(16); 572 573 Small ^= Big; 574 EXPECT_TRUE(Small.test(1)); 575 EXPECT_TRUE(Small.test(2)); 576 EXPECT_TRUE(Small.test(16)); 577 EXPECT_EQ(3u, Small.count()); 578 EXPECT_EQ(20u, Small.size()); 579 } 580 581 { 582 TypeParam Big; 583 TypeParam Small; 584 585 Big.reserve(100); 586 Big.resize(20); 587 Small.resize(10); 588 589 Small.set(0); 590 Small.set(1); 591 Big.set(0); 592 Big.set(2); 593 Big.set(16); 594 595 Big ^= Small; 596 EXPECT_TRUE(Big.test(1)); 597 EXPECT_TRUE(Big.test(2)); 598 EXPECT_TRUE(Big.test(16)); 599 EXPECT_EQ(3u, Big.count()); 600 EXPECT_EQ(20u, Big.size()); 601 } 602 603 { 604 TypeParam Big; 605 TypeParam Small; 606 607 Big.reserve(100); 608 Big.resize(20); 609 Small.resize(10); 610 611 Small.set(0); 612 Small.set(1); 613 Big.set(0); 614 Big.set(2); 615 Big.set(16); 616 617 Small.reset(Big); 618 EXPECT_TRUE(Small.test(1)); 619 EXPECT_EQ(1u, Small.count()); 620 EXPECT_EQ(10u, Small.size()); 621 } 622 623 { 624 TypeParam Big; 625 TypeParam Small; 626 627 Big.reserve(100); 628 Big.resize(20); 629 Small.resize(10); 630 631 Small.set(0); 632 Small.set(1); 633 Big.set(0); 634 Big.set(2); 635 Big.set(16); 636 637 Big.reset(Small); 638 EXPECT_TRUE(Big.test(2)); 639 EXPECT_TRUE(Big.test(16)); 640 EXPECT_EQ(2u, Big.count()); 641 EXPECT_EQ(20u, Big.size()); 642 } 643 644 { 645 TypeParam Big; 646 TypeParam Small; 647 648 Big.reserve(100); 649 Big.resize(10); 650 Small.resize(10); 651 652 Small.set(0); 653 Small.set(1); 654 Big.set(0); 655 656 EXPECT_FALSE(Big == Small); 657 EXPECT_FALSE(Small == Big); 658 Big.set(1); 659 EXPECT_TRUE(Big == Small); 660 EXPECT_TRUE(Small == Big); 661 } 662 663 { 664 TypeParam Big; 665 TypeParam Small; 666 667 Big.reserve(100); 668 Big.resize(20); 669 Small.resize(10); 670 671 Small.set(0); 672 Big.set(1); 673 674 EXPECT_FALSE(Small.anyCommon(Big)); 675 EXPECT_FALSE(Big.anyCommon(Small)); 676 Big.set(0); 677 EXPECT_TRUE(Small.anyCommon(Big)); 678 EXPECT_TRUE(Big.anyCommon(Small)); 679 } 680 681 { 682 TypeParam Big; 683 TypeParam Small; 684 685 Big.reserve(100); 686 Big.resize(10); 687 Small.resize(10); 688 689 Small.set(0); 690 Small.set(1); 691 Big.set(0); 692 693 EXPECT_TRUE(Small.test(Big)); 694 EXPECT_FALSE(Big.test(Small)); 695 Big.set(1); 696 EXPECT_FALSE(Small.test(Big)); 697 EXPECT_FALSE(Big.test(Small)); 698 } 699 } 700 701 TYPED_TEST(BitVectorTest, ProxyIndex) { 702 TypeParam Vec(3); 703 EXPECT_TRUE(Vec.none()); 704 Vec[0] = Vec[1] = Vec[2] = true; 705 EXPECT_EQ(Vec.size(), Vec.count()); 706 Vec[2] = Vec[1] = Vec[0] = false; 707 EXPECT_TRUE(Vec.none()); 708 } 709 710 TYPED_TEST(BitVectorTest, PortableBitMask) { 711 TypeParam A; 712 const uint32_t Mask1[] = { 0x80000000, 6, 5 }; 713 714 A.resize(10); 715 A.setBitsInMask(Mask1, 1); 716 EXPECT_EQ(10u, A.size()); 717 EXPECT_FALSE(A.test(0)); 718 719 A.resize(32); 720 A.setBitsInMask(Mask1, 1); 721 EXPECT_FALSE(A.test(0)); 722 EXPECT_TRUE(A.test(31)); 723 EXPECT_EQ(1u, A.count()); 724 725 A.resize(33); 726 A.setBitsInMask(Mask1, 1); 727 EXPECT_EQ(1u, A.count()); 728 A.setBitsInMask(Mask1, 2); 729 EXPECT_EQ(1u, A.count()); 730 731 A.resize(34); 732 A.setBitsInMask(Mask1, 2); 733 EXPECT_EQ(2u, A.count()); 734 735 A.resize(65); 736 A.setBitsInMask(Mask1, 3); 737 EXPECT_EQ(4u, A.count()); 738 739 A.setBitsNotInMask(Mask1, 1); 740 EXPECT_EQ(32u+3u, A.count()); 741 742 A.setBitsNotInMask(Mask1, 3); 743 EXPECT_EQ(65u, A.count()); 744 745 A.resize(96); 746 EXPECT_EQ(65u, A.count()); 747 748 A.clear(); 749 A.resize(128); 750 A.setBitsNotInMask(Mask1, 3); 751 EXPECT_EQ(96u-5u, A.count()); 752 753 A.clearBitsNotInMask(Mask1, 1); 754 EXPECT_EQ(64-4u, A.count()); 755 } 756 757 TYPED_TEST(BitVectorTest, BinOps) { 758 TypeParam A; 759 TypeParam B; 760 761 A.resize(65); 762 EXPECT_FALSE(A.anyCommon(B)); 763 EXPECT_FALSE(B.anyCommon(B)); 764 765 B.resize(64); 766 A.set(64); 767 EXPECT_FALSE(A.anyCommon(B)); 768 EXPECT_FALSE(B.anyCommon(A)); 769 770 B.set(63); 771 EXPECT_FALSE(A.anyCommon(B)); 772 EXPECT_FALSE(B.anyCommon(A)); 773 774 A.set(63); 775 EXPECT_TRUE(A.anyCommon(B)); 776 EXPECT_TRUE(B.anyCommon(A)); 777 778 B.resize(70); 779 B.set(64); 780 B.reset(63); 781 A.resize(64); 782 EXPECT_FALSE(A.anyCommon(B)); 783 EXPECT_FALSE(B.anyCommon(A)); 784 } 785 786 typedef std::vector<std::pair<int, int>> RangeList; 787 788 template <typename VecType> 789 static inline VecType createBitVector(uint32_t Size, 790 const RangeList &setRanges) { 791 VecType V; 792 V.resize(Size); 793 for (auto &R : setRanges) 794 V.set(R.first, R.second); 795 return V; 796 } 797 798 TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) { 799 // Test that shift ops work when the desired shift amount is less 800 // than one word. 801 802 // 1. Case where the number of bits in the BitVector also fit into a single 803 // word. 804 TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}}); 805 TypeParam B = A; 806 807 EXPECT_EQ(4U, A.count()); 808 EXPECT_TRUE(A.test(2)); 809 EXPECT_TRUE(A.test(3)); 810 EXPECT_TRUE(A.test(8)); 811 EXPECT_TRUE(A.test(9)); 812 813 A >>= 1; 814 EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A); 815 816 A <<= 1; 817 EXPECT_EQ(B, A); 818 819 A >>= 10; 820 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); 821 822 A = B; 823 A <<= 10; 824 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); 825 826 // 2. Case where the number of bits in the BitVector do not fit into a single 827 // word. 828 829 // 31----------------------------------------------------------------------0 830 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 831 A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}}); 832 EXPECT_EQ(40U, A.size()); 833 EXPECT_EQ(22U, A.count()); 834 835 // 2a. Make sure that left shifting some 1 bits out of the vector works. 836 // 31----------------------------------------------------------------------0 837 // Before: 838 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 839 // After: 840 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 841 A <<= 9; 842 EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A); 843 844 // 2b. Make sure that keeping the number of one bits unchanged works. 845 // 31----------------------------------------------------------------------0 846 // Before: 847 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 848 // After: 849 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 850 A >>= 6; 851 EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A); 852 853 // 2c. Make sure that right shifting some 1 bits out of the vector works. 854 // 31----------------------------------------------------------------------0 855 // Before: 856 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 857 // After: 858 // XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111 859 A >>= 10; 860 EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A); 861 862 // 3. Big test. 863 A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); 864 A <<= 29; 865 EXPECT_EQ(createBitVector<TypeParam>( 866 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}), 867 A); 868 } 869 870 TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) { 871 // Test that shift ops work when the desired shift amount is greater than or 872 // equal to the size of a single word. 873 auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); 874 875 // Make a copy so we can re-use it later. 876 auto B = A; 877 878 // 1. Shift left by an exact multiple of the word size. This should invoke 879 // only a memmove and no per-word bit operations. 880 A <<= 64; 881 auto Expected = createBitVector<TypeParam>( 882 300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}}); 883 EXPECT_EQ(Expected, A); 884 885 // 2. Shift left by a non multiple of the word size. This should invoke both 886 // a memmove and per-word bit operations. 887 A = B; 888 A <<= 93; 889 EXPECT_EQ(createBitVector<TypeParam>( 890 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}), 891 A); 892 893 // 1. Shift right by an exact multiple of the word size. This should invoke 894 // only a memmove and no per-word bit operations. 895 A = B; 896 A >>= 64; 897 EXPECT_EQ( 898 createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A); 899 900 // 2. Shift left by a non multiple of the word size. This should invoke both 901 // a memmove and per-word bit operations. 902 A = B; 903 A >>= 93; 904 EXPECT_EQ( 905 createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A); 906 } 907 908 TYPED_TEST(BitVectorTest, RangeOps) { 909 TypeParam A; 910 A.resize(256); 911 A.reset(); 912 A.set(1, 255); 913 914 EXPECT_FALSE(A.test(0)); 915 EXPECT_TRUE( A.test(1)); 916 EXPECT_TRUE( A.test(23)); 917 EXPECT_TRUE( A.test(254)); 918 EXPECT_FALSE(A.test(255)); 919 920 TypeParam B; 921 B.resize(256); 922 B.set(); 923 B.reset(1, 255); 924 925 EXPECT_TRUE( B.test(0)); 926 EXPECT_FALSE(B.test(1)); 927 EXPECT_FALSE(B.test(23)); 928 EXPECT_FALSE(B.test(254)); 929 EXPECT_TRUE( B.test(255)); 930 931 TypeParam C; 932 C.resize(3); 933 C.reset(); 934 C.set(0, 1); 935 936 EXPECT_TRUE(C.test(0)); 937 EXPECT_FALSE( C.test(1)); 938 EXPECT_FALSE( C.test(2)); 939 940 TypeParam D; 941 D.resize(3); 942 D.set(); 943 D.reset(0, 1); 944 945 EXPECT_FALSE(D.test(0)); 946 EXPECT_TRUE( D.test(1)); 947 EXPECT_TRUE( D.test(2)); 948 949 TypeParam E; 950 E.resize(128); 951 E.reset(); 952 E.set(1, 33); 953 954 EXPECT_FALSE(E.test(0)); 955 EXPECT_TRUE( E.test(1)); 956 EXPECT_TRUE( E.test(32)); 957 EXPECT_FALSE(E.test(33)); 958 959 TypeParam BufferOverrun; 960 unsigned size = sizeof(unsigned long) * 8; 961 BufferOverrun.resize(size); 962 BufferOverrun.reset(0, size); 963 BufferOverrun.set(0, size); 964 } 965 966 TYPED_TEST(BitVectorTest, CompoundTestReset) { 967 TypeParam A(50, true); 968 TypeParam B(50, false); 969 970 TypeParam C(100, true); 971 TypeParam D(100, false); 972 973 EXPECT_FALSE(A.test(A)); 974 EXPECT_TRUE(A.test(B)); 975 EXPECT_FALSE(A.test(C)); 976 EXPECT_TRUE(A.test(D)); 977 EXPECT_FALSE(B.test(A)); 978 EXPECT_FALSE(B.test(B)); 979 EXPECT_FALSE(B.test(C)); 980 EXPECT_FALSE(B.test(D)); 981 EXPECT_TRUE(C.test(A)); 982 EXPECT_TRUE(C.test(B)); 983 EXPECT_FALSE(C.test(C)); 984 EXPECT_TRUE(C.test(D)); 985 986 A.reset(B); 987 A.reset(D); 988 EXPECT_TRUE(A.all()); 989 A.reset(A); 990 EXPECT_TRUE(A.none()); 991 A.set(); 992 A.reset(C); 993 EXPECT_TRUE(A.none()); 994 A.set(); 995 996 C.reset(A); 997 EXPECT_EQ(50, C.find_first()); 998 C.reset(C); 999 EXPECT_TRUE(C.none()); 1000 } 1001 1002 TYPED_TEST(BitVectorTest, MoveConstructor) { 1003 TypeParam A(10, true); 1004 TypeParam B(std::move(A)); 1005 // Check that the move ctor leaves the moved-from object in a valid state. 1006 // The following line used to crash. 1007 A = B; 1008 1009 TypeParam C(10, true); 1010 EXPECT_EQ(C, A); 1011 EXPECT_EQ(C, B); 1012 } 1013 1014 TYPED_TEST(BitVectorTest, MoveAssignment) { 1015 TypeParam A(10, true); 1016 TypeParam B; 1017 B = std::move(A); 1018 // Check that move assignment leaves the moved-from object in a valid state. 1019 // The following line used to crash. 1020 A = B; 1021 1022 TypeParam C(10, true); 1023 EXPECT_EQ(C, A); 1024 EXPECT_EQ(C, B); 1025 } 1026 1027 template<class TypeParam> 1028 static void testEmpty(const TypeParam &A) { 1029 EXPECT_TRUE(A.empty()); 1030 EXPECT_EQ((size_t)0, A.size()); 1031 EXPECT_EQ((size_t)0, A.count()); 1032 EXPECT_FALSE(A.any()); 1033 EXPECT_TRUE(A.all()); 1034 EXPECT_TRUE(A.none()); 1035 EXPECT_EQ(-1, A.find_first()); 1036 EXPECT_EQ(A, TypeParam()); 1037 } 1038 1039 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0 1040 TYPED_TEST(BitVectorTest, EmptyVector) { 1041 TypeParam A; 1042 testEmpty(A); 1043 1044 TypeParam B; 1045 B.reset(); 1046 testEmpty(B); 1047 1048 TypeParam C; 1049 C.clear(); 1050 testEmpty(C); 1051 1052 TypeParam D(A); 1053 testEmpty(D); 1054 1055 TypeParam E; 1056 E = A; 1057 testEmpty(E); 1058 1059 TypeParam F; 1060 E.reset(A); 1061 testEmpty(E); 1062 } 1063 1064 TYPED_TEST(BitVectorTest, Iterators) { 1065 TypeParam Filled(10, true); 1066 EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end()); 1067 unsigned Counter = 0; 1068 for (unsigned Bit : Filled.set_bits()) 1069 EXPECT_EQ(Bit, Counter++); 1070 1071 TypeParam Empty; 1072 EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end()); 1073 for (unsigned Bit : Empty.set_bits()) { 1074 (void)Bit; 1075 EXPECT_TRUE(false); 1076 } 1077 1078 TypeParam ToFill(100, false); 1079 ToFill.set(0); 1080 EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end()); 1081 EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end()); 1082 EXPECT_EQ(*ToFill.set_bits_begin(), 0U); 1083 ToFill.reset(0); 1084 EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end()); 1085 1086 const unsigned List[] = {1, 10, 25, 99}; 1087 for (unsigned Num : List) 1088 ToFill.set(Num); 1089 unsigned i = 0; 1090 for (unsigned Bit : ToFill.set_bits()) 1091 EXPECT_EQ(List[i++], Bit); 1092 } 1093 1094 TYPED_TEST(BitVectorTest, PushBack) { 1095 TypeParam Vec(10, false); 1096 EXPECT_EQ(-1, Vec.find_first()); 1097 EXPECT_EQ(10U, Vec.size()); 1098 EXPECT_EQ(0U, Vec.count()); 1099 1100 Vec.push_back(true); 1101 EXPECT_EQ(10, Vec.find_first()); 1102 EXPECT_EQ(11U, Vec.size()); 1103 EXPECT_EQ(1U, Vec.count()); 1104 1105 Vec.push_back(false); 1106 EXPECT_EQ(10, Vec.find_first()); 1107 EXPECT_EQ(12U, Vec.size()); 1108 EXPECT_EQ(1U, Vec.count()); 1109 1110 Vec.push_back(true); 1111 EXPECT_EQ(10, Vec.find_first()); 1112 EXPECT_EQ(13U, Vec.size()); 1113 EXPECT_EQ(2U, Vec.count()); 1114 1115 // Add a lot of values to cause reallocation. 1116 for (int i = 0; i != 100; ++i) { 1117 Vec.push_back(true); 1118 Vec.push_back(false); 1119 } 1120 EXPECT_EQ(10, Vec.find_first()); 1121 EXPECT_EQ(213U, Vec.size()); 1122 EXPECT_EQ(102U, Vec.count()); 1123 } 1124 } 1125 #endif 1126