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