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