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