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