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