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