1 //===- llvm/unittest/ADT/BitVectorTest.cpp - BitVector tests --------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/ADT/BitVector.h" 10 #include "llvm/ADT/DenseSet.h" 11 #include "llvm/ADT/SmallBitVector.h" 12 #include "gtest/gtest.h" 13 14 using namespace llvm; 15 16 namespace { 17 18 // Test fixture 19 template <typename T> 20 class BitVectorTest : public ::testing::Test { }; 21 22 // Test both BitVector and SmallBitVector with the same suite of tests. 23 typedef ::testing::Types<BitVector, SmallBitVector> BitVectorTestTypes; 24 TYPED_TEST_CASE(BitVectorTest, BitVectorTestTypes); 25 26 TYPED_TEST(BitVectorTest, TrivialOperation) { 27 TypeParam Vec; 28 EXPECT_EQ(0U, Vec.count()); 29 EXPECT_EQ(0U, Vec.size()); 30 EXPECT_FALSE(Vec.any()); 31 EXPECT_TRUE(Vec.all()); 32 EXPECT_TRUE(Vec.none()); 33 EXPECT_TRUE(Vec.empty()); 34 35 Vec.resize(5, true); 36 EXPECT_EQ(5U, Vec.count()); 37 EXPECT_EQ(5U, Vec.size()); 38 EXPECT_TRUE(Vec.any()); 39 EXPECT_TRUE(Vec.all()); 40 EXPECT_FALSE(Vec.none()); 41 EXPECT_FALSE(Vec.empty()); 42 43 Vec.resize(11); 44 EXPECT_EQ(5U, Vec.count()); 45 EXPECT_EQ(11U, Vec.size()); 46 EXPECT_TRUE(Vec.any()); 47 EXPECT_FALSE(Vec.all()); 48 EXPECT_FALSE(Vec.none()); 49 EXPECT_FALSE(Vec.empty()); 50 51 TypeParam Inv = Vec; 52 Inv.flip(); 53 EXPECT_EQ(6U, Inv.count()); 54 EXPECT_EQ(11U, Inv.size()); 55 EXPECT_TRUE(Inv.any()); 56 EXPECT_FALSE(Inv.all()); 57 EXPECT_FALSE(Inv.none()); 58 EXPECT_FALSE(Inv.empty()); 59 60 EXPECT_FALSE(Inv == Vec); 61 EXPECT_TRUE(Inv != Vec); 62 Vec.flip(); 63 EXPECT_TRUE(Inv == Vec); 64 EXPECT_FALSE(Inv != Vec); 65 66 // Add some "interesting" data to Vec. 67 Vec.resize(23, true); 68 Vec.resize(25, false); 69 Vec.resize(26, true); 70 Vec.resize(29, false); 71 Vec.resize(33, true); 72 Vec.resize(57, false); 73 unsigned Count = 0; 74 for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) { 75 ++Count; 76 EXPECT_TRUE(Vec[i]); 77 EXPECT_TRUE(Vec.test(i)); 78 } 79 EXPECT_EQ(Count, Vec.count()); 80 EXPECT_EQ(Count, 23u); 81 EXPECT_FALSE(Vec[0]); 82 EXPECT_TRUE(Vec[32]); 83 EXPECT_FALSE(Vec[56]); 84 Vec.resize(61, false); 85 86 TypeParam Copy = Vec; 87 TypeParam Alt(3, false); 88 Alt.resize(6, true); 89 std::swap(Alt, Vec); 90 EXPECT_TRUE(Copy == Alt); 91 EXPECT_TRUE(Vec.size() == 6); 92 EXPECT_TRUE(Vec.count() == 3); 93 EXPECT_TRUE(Vec.find_first() == 3); 94 std::swap(Copy, Vec); 95 96 // Add some more "interesting" data. 97 Vec.resize(68, true); 98 Vec.resize(78, false); 99 Vec.resize(89, true); 100 Vec.resize(90, false); 101 Vec.resize(91, true); 102 Vec.resize(130, false); 103 Count = 0; 104 for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) { 105 ++Count; 106 EXPECT_TRUE(Vec[i]); 107 EXPECT_TRUE(Vec.test(i)); 108 } 109 EXPECT_EQ(Count, Vec.count()); 110 EXPECT_EQ(Count, 42u); 111 EXPECT_FALSE(Vec[0]); 112 EXPECT_TRUE(Vec[32]); 113 EXPECT_FALSE(Vec[60]); 114 EXPECT_FALSE(Vec[129]); 115 116 Vec.flip(60); 117 EXPECT_TRUE(Vec[60]); 118 EXPECT_EQ(Count + 1, Vec.count()); 119 Vec.flip(60); 120 EXPECT_FALSE(Vec[60]); 121 EXPECT_EQ(Count, Vec.count()); 122 123 Vec.reset(32); 124 EXPECT_FALSE(Vec[32]); 125 EXPECT_EQ(Count - 1, Vec.count()); 126 Vec.set(32); 127 EXPECT_TRUE(Vec[32]); 128 EXPECT_EQ(Count, Vec.count()); 129 130 Vec.flip(); 131 EXPECT_EQ(Vec.size() - Count, Vec.count()); 132 133 Vec.reset(); 134 EXPECT_EQ(0U, Vec.count()); 135 EXPECT_EQ(130U, Vec.size()); 136 EXPECT_FALSE(Vec.any()); 137 EXPECT_FALSE(Vec.all()); 138 EXPECT_TRUE(Vec.none()); 139 EXPECT_FALSE(Vec.empty()); 140 141 Vec.flip(); 142 EXPECT_EQ(130U, Vec.count()); 143 EXPECT_EQ(130U, Vec.size()); 144 EXPECT_TRUE(Vec.any()); 145 EXPECT_TRUE(Vec.all()); 146 EXPECT_FALSE(Vec.none()); 147 EXPECT_FALSE(Vec.empty()); 148 149 Vec.resize(64); 150 EXPECT_EQ(64U, Vec.count()); 151 EXPECT_EQ(64U, Vec.size()); 152 EXPECT_TRUE(Vec.any()); 153 EXPECT_TRUE(Vec.all()); 154 EXPECT_FALSE(Vec.none()); 155 EXPECT_FALSE(Vec.empty()); 156 157 Vec.flip(); 158 EXPECT_EQ(0U, Vec.count()); 159 EXPECT_EQ(64U, Vec.size()); 160 EXPECT_FALSE(Vec.any()); 161 EXPECT_FALSE(Vec.all()); 162 EXPECT_TRUE(Vec.none()); 163 EXPECT_FALSE(Vec.empty()); 164 165 Inv = TypeParam().flip(); 166 EXPECT_EQ(0U, Inv.count()); 167 EXPECT_EQ(0U, Inv.size()); 168 EXPECT_FALSE(Inv.any()); 169 EXPECT_TRUE(Inv.all()); 170 EXPECT_TRUE(Inv.none()); 171 EXPECT_TRUE(Inv.empty()); 172 173 Vec.clear(); 174 EXPECT_EQ(0U, Vec.count()); 175 EXPECT_EQ(0U, Vec.size()); 176 EXPECT_FALSE(Vec.any()); 177 EXPECT_TRUE(Vec.all()); 178 EXPECT_TRUE(Vec.none()); 179 EXPECT_TRUE(Vec.empty()); 180 } 181 182 TYPED_TEST(BitVectorTest, Equality) { 183 TypeParam A; 184 TypeParam B; 185 EXPECT_TRUE(A == B); 186 A.resize(10); 187 EXPECT_FALSE(A == B); 188 B.resize(10); 189 EXPECT_TRUE(A == B); 190 A.set(5); 191 EXPECT_FALSE(A == B); 192 B.set(5); 193 EXPECT_TRUE(A == B); 194 A.resize(20); 195 EXPECT_FALSE(A == B); 196 B.resize(20); 197 EXPECT_TRUE(A == B); 198 } 199 200 TYPED_TEST(BitVectorTest, SimpleFindOpsMultiWord) { 201 TypeParam A; 202 203 // Test finding next set and unset bits in a BitVector with multiple words 204 A.resize(100); 205 A.set(12); 206 A.set(13); 207 A.set(75); 208 209 EXPECT_EQ(75, A.find_last()); 210 EXPECT_EQ(12, A.find_first()); 211 EXPECT_EQ(13, A.find_next(12)); 212 EXPECT_EQ(75, A.find_next(13)); 213 EXPECT_EQ(-1, A.find_next(75)); 214 215 EXPECT_EQ(-1, A.find_prev(12)); 216 EXPECT_EQ(12, A.find_prev(13)); 217 EXPECT_EQ(13, A.find_prev(75)); 218 EXPECT_EQ(75, A.find_prev(90)); 219 220 EXPECT_EQ(0, A.find_first_unset()); 221 EXPECT_EQ(99, A.find_last_unset()); 222 EXPECT_EQ(14, A.find_next_unset(11)); 223 EXPECT_EQ(14, A.find_next_unset(12)); 224 EXPECT_EQ(14, A.find_next_unset(13)); 225 EXPECT_EQ(16, A.find_next_unset(15)); 226 EXPECT_EQ(76, A.find_next_unset(74)); 227 EXPECT_EQ(76, A.find_next_unset(75)); 228 EXPECT_EQ(-1, A.find_next_unset(99)); 229 230 A.set(0, 100); 231 EXPECT_EQ(100U, A.count()); 232 EXPECT_EQ(0, A.find_first()); 233 EXPECT_EQ(-1, A.find_first_unset()); 234 EXPECT_EQ(-1, A.find_last_unset()); 235 EXPECT_EQ(99, A.find_last()); 236 EXPECT_EQ(99, A.find_next(98)); 237 238 A.reset(0, 100); 239 EXPECT_EQ(0U, A.count()); 240 EXPECT_EQ(-1, A.find_first()); 241 EXPECT_EQ(-1, A.find_last()); 242 EXPECT_EQ(0, A.find_first_unset()); 243 EXPECT_EQ(99, A.find_last_unset()); 244 EXPECT_EQ(99, A.find_next_unset(98)); 245 } 246 247 // Test finding next set and unset bits in a BitVector/SmallBitVector within a 248 // uintptr_t - check both 32-bit (Multi) and 64-bit (Small) targets. 249 TYPED_TEST(BitVectorTest, SimpleFindOps64Bit) { 250 TypeParam A; 251 252 A.resize(57); 253 A.set(12); 254 A.set(13); 255 A.set(47); 256 257 EXPECT_EQ(47, A.find_last()); 258 EXPECT_EQ(12, A.find_first()); 259 EXPECT_EQ(13, A.find_next(12)); 260 EXPECT_EQ(47, A.find_next(13)); 261 EXPECT_EQ(-1, A.find_next(47)); 262 263 EXPECT_EQ(-1, A.find_prev(12)); 264 EXPECT_EQ(12, A.find_prev(13)); 265 EXPECT_EQ(13, A.find_prev(47)); 266 EXPECT_EQ(47, A.find_prev(56)); 267 268 EXPECT_EQ(0, A.find_first_unset()); 269 EXPECT_EQ(56, A.find_last_unset()); 270 EXPECT_EQ(14, A.find_next_unset(11)); 271 EXPECT_EQ(14, A.find_next_unset(12)); 272 EXPECT_EQ(14, A.find_next_unset(13)); 273 EXPECT_EQ(16, A.find_next_unset(15)); 274 EXPECT_EQ(48, A.find_next_unset(46)); 275 EXPECT_EQ(48, A.find_next_unset(47)); 276 EXPECT_EQ(-1, A.find_next_unset(56)); 277 } 278 279 // Check if a SmallBitVector is in small mode. This check is used in tests 280 // that run for both SmallBitVector and BitVector. This check doesn't apply 281 // to BitVector so we provide an overload that returns true to get the tests 282 // to compile. 283 static bool SmallBitVectorIsSmallMode(const SmallBitVector &bv) { 284 return bv.isSmall(); 285 } 286 static bool SmallBitVectorIsSmallMode(const BitVector &) { return true; } 287 288 // These tests are intended to exercise the single-word case of BitVector 289 // and the small-mode case of SmallBitVector. 290 TYPED_TEST(BitVectorTest, SimpleFindOpsSingleWord) { 291 // Test finding in an empty BitVector. 292 TypeParam A; 293 ASSERT_TRUE(SmallBitVectorIsSmallMode(A)); 294 EXPECT_EQ(-1, A.find_first()); 295 EXPECT_EQ(-1, A.find_last()); 296 EXPECT_EQ(-1, A.find_first_unset()); 297 EXPECT_EQ(-1, A.find_last_unset()); 298 299 A.resize(20); 300 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 TYPED_TEST(BitVectorTest, PortableBitMask) { 783 TypeParam A; 784 const uint32_t Mask1[] = { 0x80000000, 6, 5 }; 785 786 A.resize(10); 787 A.setBitsInMask(Mask1, 1); 788 EXPECT_EQ(10u, A.size()); 789 EXPECT_FALSE(A.test(0)); 790 791 A.resize(32); 792 A.setBitsInMask(Mask1, 1); 793 EXPECT_FALSE(A.test(0)); 794 EXPECT_TRUE(A.test(31)); 795 EXPECT_EQ(1u, A.count()); 796 797 A.resize(33); 798 A.setBitsInMask(Mask1, 1); 799 EXPECT_EQ(1u, A.count()); 800 A.setBitsInMask(Mask1, 2); 801 EXPECT_EQ(1u, A.count()); 802 803 A.resize(34); 804 A.setBitsInMask(Mask1, 2); 805 EXPECT_EQ(2u, A.count()); 806 807 A.resize(65); 808 A.setBitsInMask(Mask1, 3); 809 EXPECT_EQ(4u, A.count()); 810 811 A.setBitsNotInMask(Mask1, 1); 812 EXPECT_EQ(32u+3u, A.count()); 813 814 A.setBitsNotInMask(Mask1, 3); 815 EXPECT_EQ(65u, A.count()); 816 817 A.resize(96); 818 EXPECT_EQ(65u, A.count()); 819 820 A.clear(); 821 A.resize(128); 822 A.setBitsNotInMask(Mask1, 3); 823 EXPECT_EQ(96u-5u, A.count()); 824 825 A.clearBitsNotInMask(Mask1, 1); 826 EXPECT_EQ(64-4u, A.count()); 827 } 828 829 TYPED_TEST(BitVectorTest, BinOps) { 830 TypeParam A; 831 TypeParam B; 832 833 A.resize(65); 834 EXPECT_FALSE(A.anyCommon(B)); 835 EXPECT_FALSE(B.anyCommon(B)); 836 837 B.resize(64); 838 A.set(64); 839 EXPECT_FALSE(A.anyCommon(B)); 840 EXPECT_FALSE(B.anyCommon(A)); 841 842 B.set(63); 843 EXPECT_FALSE(A.anyCommon(B)); 844 EXPECT_FALSE(B.anyCommon(A)); 845 846 A.set(63); 847 EXPECT_TRUE(A.anyCommon(B)); 848 EXPECT_TRUE(B.anyCommon(A)); 849 850 B.resize(70); 851 B.set(64); 852 B.reset(63); 853 A.resize(64); 854 EXPECT_FALSE(A.anyCommon(B)); 855 EXPECT_FALSE(B.anyCommon(A)); 856 } 857 858 typedef std::vector<std::pair<int, int>> RangeList; 859 860 template <typename VecType> 861 static inline VecType createBitVector(uint32_t Size, 862 const RangeList &setRanges) { 863 VecType V; 864 V.resize(Size); 865 for (auto &R : setRanges) 866 V.set(R.first, R.second); 867 return V; 868 } 869 870 TYPED_TEST(BitVectorTest, ShiftOpsSingleWord) { 871 // Test that shift ops work when the desired shift amount is less 872 // than one word. 873 874 // 1. Case where the number of bits in the BitVector also fit into a single 875 // word. 876 TypeParam A = createBitVector<TypeParam>(12, {{2, 4}, {8, 10}}); 877 TypeParam B = A; 878 879 EXPECT_EQ(4U, A.count()); 880 EXPECT_TRUE(A.test(2)); 881 EXPECT_TRUE(A.test(3)); 882 EXPECT_TRUE(A.test(8)); 883 EXPECT_TRUE(A.test(9)); 884 885 A >>= 1; 886 EXPECT_EQ(createBitVector<TypeParam>(12, {{1, 3}, {7, 9}}), A); 887 888 A <<= 1; 889 EXPECT_EQ(B, A); 890 891 A >>= 10; 892 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); 893 894 A = B; 895 A <<= 10; 896 EXPECT_EQ(createBitVector<TypeParam>(12, {}), A); 897 898 // 2. Case where the number of bits in the BitVector do not fit into a single 899 // word. 900 901 // 31----------------------------------------------------------------------0 902 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 903 A = createBitVector<TypeParam>(40, {{0, 12}, {25, 35}}); 904 EXPECT_EQ(40U, A.size()); 905 EXPECT_EQ(22U, A.count()); 906 907 // 2a. Make sure that left shifting some 1 bits out of the vector works. 908 // 31----------------------------------------------------------------------0 909 // Before: 910 // XXXXXXXX XXXXXXXX XXXXXXXX 00000111 | 11111110 00000000 00001111 11111111 911 // After: 912 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 913 A <<= 9; 914 EXPECT_EQ(createBitVector<TypeParam>(40, {{9, 21}, {34, 40}}), A); 915 916 // 2b. Make sure that keeping the number of one bits unchanged works. 917 // 31----------------------------------------------------------------------0 918 // Before: 919 // XXXXXXXX XXXXXXXX XXXXXXXX 11111100 | 00000000 00011111 11111110 00000000 920 // After: 921 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 922 A >>= 6; 923 EXPECT_EQ(createBitVector<TypeParam>(40, {{3, 15}, {28, 34}}), A); 924 925 // 2c. Make sure that right shifting some 1 bits out of the vector works. 926 // 31----------------------------------------------------------------------0 927 // Before: 928 // XXXXXXXX XXXXXXXX XXXXXXXX 00000011 | 11110000 00000000 01111111 11111000 929 // After: 930 // XXXXXXXX XXXXXXXX XXXXXXXX 00000000 | 00000000 11111100 00000000 00011111 931 A >>= 10; 932 EXPECT_EQ(createBitVector<TypeParam>(40, {{0, 5}, {18, 24}}), A); 933 934 // 3. Big test. 935 A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); 936 A <<= 29; 937 EXPECT_EQ(createBitVector<TypeParam>( 938 300, {{1 + 29, 30 + 29}, {60 + 29, 95 + 29}, {200 + 29, 300}}), 939 A); 940 } 941 942 TYPED_TEST(BitVectorTest, ShiftOpsMultiWord) { 943 // Test that shift ops work when the desired shift amount is greater than or 944 // equal to the size of a single word. 945 auto A = createBitVector<TypeParam>(300, {{1, 30}, {60, 95}, {200, 275}}); 946 947 // Make a copy so we can re-use it later. 948 auto B = A; 949 950 // 1. Shift left by an exact multiple of the word size. This should invoke 951 // only a memmove and no per-word bit operations. 952 A <<= 64; 953 auto Expected = createBitVector<TypeParam>( 954 300, {{1 + 64, 30 + 64}, {60 + 64, 95 + 64}, {200 + 64, 300}}); 955 EXPECT_EQ(Expected, A); 956 957 // 2. Shift left by a non multiple of the word size. This should invoke both 958 // a memmove and per-word bit operations. 959 A = B; 960 A <<= 93; 961 EXPECT_EQ(createBitVector<TypeParam>( 962 300, {{1 + 93, 30 + 93}, {60 + 93, 95 + 93}, {200 + 93, 300}}), 963 A); 964 965 // 1. Shift right by an exact multiple of the word size. This should invoke 966 // only a memmove and no per-word bit operations. 967 A = B; 968 A >>= 64; 969 EXPECT_EQ( 970 createBitVector<TypeParam>(300, {{0, 95 - 64}, {200 - 64, 275 - 64}}), A); 971 972 // 2. Shift left by a non multiple of the word size. This should invoke both 973 // a memmove and per-word bit operations. 974 A = B; 975 A >>= 93; 976 EXPECT_EQ( 977 createBitVector<TypeParam>(300, {{0, 95 - 93}, {200 - 93, 275 - 93}}), A); 978 } 979 980 TYPED_TEST(BitVectorTest, RangeOps) { 981 TypeParam A; 982 A.resize(256); 983 A.reset(); 984 A.set(1, 255); 985 986 EXPECT_FALSE(A.test(0)); 987 EXPECT_TRUE( A.test(1)); 988 EXPECT_TRUE( A.test(23)); 989 EXPECT_TRUE( A.test(254)); 990 EXPECT_FALSE(A.test(255)); 991 992 TypeParam B; 993 B.resize(256); 994 B.set(); 995 B.reset(1, 255); 996 997 EXPECT_TRUE( B.test(0)); 998 EXPECT_FALSE(B.test(1)); 999 EXPECT_FALSE(B.test(23)); 1000 EXPECT_FALSE(B.test(254)); 1001 EXPECT_TRUE( B.test(255)); 1002 1003 TypeParam C; 1004 C.resize(3); 1005 C.reset(); 1006 C.set(0, 1); 1007 1008 EXPECT_TRUE(C.test(0)); 1009 EXPECT_FALSE( C.test(1)); 1010 EXPECT_FALSE( C.test(2)); 1011 1012 TypeParam D; 1013 D.resize(3); 1014 D.set(); 1015 D.reset(0, 1); 1016 1017 EXPECT_FALSE(D.test(0)); 1018 EXPECT_TRUE( D.test(1)); 1019 EXPECT_TRUE( D.test(2)); 1020 1021 TypeParam E; 1022 E.resize(128); 1023 E.reset(); 1024 E.set(1, 33); 1025 1026 EXPECT_FALSE(E.test(0)); 1027 EXPECT_TRUE( E.test(1)); 1028 EXPECT_TRUE( E.test(32)); 1029 EXPECT_FALSE(E.test(33)); 1030 1031 TypeParam BufferOverrun; 1032 unsigned size = sizeof(unsigned long) * 8; 1033 BufferOverrun.resize(size); 1034 BufferOverrun.reset(0, size); 1035 BufferOverrun.set(0, size); 1036 } 1037 1038 TYPED_TEST(BitVectorTest, CompoundTestReset) { 1039 TypeParam A(50, true); 1040 TypeParam B(50, false); 1041 1042 TypeParam C(100, true); 1043 TypeParam D(100, false); 1044 1045 EXPECT_FALSE(A.test(A)); 1046 EXPECT_TRUE(A.test(B)); 1047 EXPECT_FALSE(A.test(C)); 1048 EXPECT_TRUE(A.test(D)); 1049 EXPECT_FALSE(B.test(A)); 1050 EXPECT_FALSE(B.test(B)); 1051 EXPECT_FALSE(B.test(C)); 1052 EXPECT_FALSE(B.test(D)); 1053 EXPECT_TRUE(C.test(A)); 1054 EXPECT_TRUE(C.test(B)); 1055 EXPECT_FALSE(C.test(C)); 1056 EXPECT_TRUE(C.test(D)); 1057 1058 A.reset(B); 1059 A.reset(D); 1060 EXPECT_TRUE(A.all()); 1061 A.reset(A); 1062 EXPECT_TRUE(A.none()); 1063 A.set(); 1064 A.reset(C); 1065 EXPECT_TRUE(A.none()); 1066 A.set(); 1067 1068 C.reset(A); 1069 EXPECT_EQ(50, C.find_first()); 1070 C.reset(C); 1071 EXPECT_TRUE(C.none()); 1072 } 1073 1074 TYPED_TEST(BitVectorTest, MoveConstructor) { 1075 TypeParam A(10, true); 1076 TypeParam B(std::move(A)); 1077 // Check that the move ctor leaves the moved-from object in a valid state. 1078 // The following line used to crash. 1079 A = B; 1080 1081 TypeParam C(10, true); 1082 EXPECT_EQ(C, A); 1083 EXPECT_EQ(C, B); 1084 } 1085 1086 TYPED_TEST(BitVectorTest, MoveAssignment) { 1087 TypeParam A(10, true); 1088 TypeParam B; 1089 B = std::move(A); 1090 // Check that move assignment leaves the moved-from object in a valid state. 1091 // The following line used to crash. 1092 A = B; 1093 1094 TypeParam C(10, true); 1095 EXPECT_EQ(C, A); 1096 EXPECT_EQ(C, B); 1097 } 1098 1099 template<class TypeParam> 1100 static void testEmpty(const TypeParam &A) { 1101 EXPECT_TRUE(A.empty()); 1102 EXPECT_EQ((size_t)0, A.size()); 1103 EXPECT_EQ((size_t)0, A.count()); 1104 EXPECT_FALSE(A.any()); 1105 EXPECT_TRUE(A.all()); 1106 EXPECT_TRUE(A.none()); 1107 EXPECT_EQ(-1, A.find_first()); 1108 EXPECT_EQ(A, TypeParam()); 1109 } 1110 1111 /// Tests whether BitVector behaves well with Bits==nullptr, Capacity==0 1112 TYPED_TEST(BitVectorTest, EmptyVector) { 1113 TypeParam A; 1114 testEmpty(A); 1115 1116 TypeParam B; 1117 B.reset(); 1118 testEmpty(B); 1119 1120 TypeParam C; 1121 C.clear(); 1122 testEmpty(C); 1123 1124 TypeParam D(A); 1125 testEmpty(D); 1126 1127 TypeParam E; 1128 E = A; 1129 testEmpty(E); 1130 1131 TypeParam F; 1132 E.reset(A); 1133 testEmpty(E); 1134 } 1135 1136 TYPED_TEST(BitVectorTest, Iterators) { 1137 TypeParam Filled(10, true); 1138 EXPECT_NE(Filled.set_bits_begin(), Filled.set_bits_end()); 1139 unsigned Counter = 0; 1140 for (unsigned Bit : Filled.set_bits()) 1141 EXPECT_EQ(Bit, Counter++); 1142 1143 TypeParam Empty; 1144 EXPECT_EQ(Empty.set_bits_begin(), Empty.set_bits_end()); 1145 int BitCount = 0; 1146 for (unsigned Bit : Empty.set_bits()) { 1147 (void)Bit; 1148 BitCount++; 1149 } 1150 ASSERT_EQ(BitCount, 0); 1151 1152 TypeParam ToFill(100, false); 1153 ToFill.set(0); 1154 EXPECT_NE(ToFill.set_bits_begin(), ToFill.set_bits_end()); 1155 EXPECT_EQ(++ToFill.set_bits_begin(), ToFill.set_bits_end()); 1156 EXPECT_EQ(*ToFill.set_bits_begin(), 0U); 1157 ToFill.reset(0); 1158 EXPECT_EQ(ToFill.set_bits_begin(), ToFill.set_bits_end()); 1159 1160 const unsigned List[] = {1, 10, 25, 99}; 1161 for (unsigned Num : List) 1162 ToFill.set(Num); 1163 unsigned i = 0; 1164 for (unsigned Bit : ToFill.set_bits()) 1165 EXPECT_EQ(List[i++], Bit); 1166 } 1167 1168 TYPED_TEST(BitVectorTest, PushBack) { 1169 TypeParam Vec(10, false); 1170 EXPECT_EQ(-1, Vec.find_first()); 1171 EXPECT_EQ(10U, Vec.size()); 1172 EXPECT_EQ(0U, Vec.count()); 1173 1174 Vec.push_back(true); 1175 EXPECT_EQ(10, Vec.find_first()); 1176 EXPECT_EQ(11U, Vec.size()); 1177 EXPECT_EQ(1U, Vec.count()); 1178 1179 Vec.push_back(false); 1180 EXPECT_EQ(10, Vec.find_first()); 1181 EXPECT_EQ(12U, Vec.size()); 1182 EXPECT_EQ(1U, Vec.count()); 1183 1184 Vec.push_back(true); 1185 EXPECT_EQ(10, Vec.find_first()); 1186 EXPECT_EQ(13U, Vec.size()); 1187 EXPECT_EQ(2U, Vec.count()); 1188 1189 // Add a lot of values to cause reallocation. 1190 for (int i = 0; i != 100; ++i) { 1191 Vec.push_back(true); 1192 Vec.push_back(false); 1193 } 1194 EXPECT_EQ(10, Vec.find_first()); 1195 EXPECT_EQ(213U, Vec.size()); 1196 EXPECT_EQ(102U, Vec.count()); 1197 } 1198 1199 TYPED_TEST(BitVectorTest, DenseSet) { 1200 DenseSet<TypeParam> Set; 1201 TypeParam A(10, true); 1202 auto I = Set.insert(A); 1203 EXPECT_EQ(true, I.second); 1204 1205 TypeParam B(5, true); 1206 I = Set.insert(B); 1207 EXPECT_EQ(true, I.second); 1208 1209 TypeParam C(20, false); 1210 C.set(19); 1211 I = Set.insert(C); 1212 EXPECT_EQ(true, I.second); 1213 1214 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 1215 TypeParam D; 1216 EXPECT_DEATH(Set.insert(D), 1217 "Empty/Tombstone value shouldn't be inserted into map!"); 1218 #endif 1219 1220 EXPECT_EQ(3U, Set.size()); 1221 EXPECT_EQ(1U, Set.count(A)); 1222 EXPECT_EQ(1U, Set.count(B)); 1223 EXPECT_EQ(1U, Set.count(C)); 1224 1225 EXPECT_EQ(true, Set.erase(B)); 1226 EXPECT_EQ(2U, Set.size()); 1227 1228 EXPECT_EQ(true, Set.erase(C)); 1229 EXPECT_EQ(1U, Set.size()); 1230 1231 EXPECT_EQ(true, Set.erase(A)); 1232 EXPECT_EQ(0U, Set.size()); 1233 } 1234 1235 /// Test that capacity doesn't affect hashing. 1236 TYPED_TEST(BitVectorTest, DenseMapHashing) { 1237 using DMI = DenseMapInfo<TypeParam>; 1238 { 1239 TypeParam A; 1240 A.resize(200); 1241 A.set(100); 1242 1243 TypeParam B; 1244 B.resize(200); 1245 B.set(100); 1246 B.reserve(1000); 1247 1248 EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B)); 1249 } 1250 { 1251 TypeParam A; 1252 A.resize(20); 1253 A.set(10); 1254 1255 TypeParam B; 1256 B.resize(20); 1257 B.set(10); 1258 B.reserve(1000); 1259 1260 EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B)); 1261 } 1262 } 1263 1264 } // namespace 1265