| 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 |
EXPECT_EQ(false, Vec.back()); |
| 1175 |
|
| 1176 |
Vec.push_back(true); |
| 1177 |
EXPECT_EQ(10, Vec.find_first()); |
| 1178 |
EXPECT_EQ(11U, Vec.size()); |
| 1179 |
EXPECT_EQ(1U, Vec.count()); |
| 1180 |
EXPECT_EQ(true, Vec.back()); |
| 1181 |
|
| 1182 |
Vec.push_back(false); |
| 1183 |
EXPECT_EQ(10, Vec.find_first()); |
| 1184 |
EXPECT_EQ(12U, Vec.size()); |
| 1185 |
EXPECT_EQ(1U, Vec.count()); |
| 1186 |
EXPECT_EQ(false, Vec.back()); |
| 1187 |
|
| 1188 |
Vec.push_back(true); |
| 1189 |
EXPECT_EQ(10, Vec.find_first()); |
| 1190 |
EXPECT_EQ(13U, Vec.size()); |
| 1191 |
EXPECT_EQ(2U, Vec.count()); |
| 1192 |
EXPECT_EQ(true, Vec.back()); |
| 1193 |
|
| 1194 |
// Add a lot of values to cause reallocation. |
| 1195 |
for (int i = 0; i != 100; ++i) { |
| 1196 |
Vec.push_back(true); |
| 1197 |
Vec.push_back(false); |
| 1198 |
} |
| 1199 |
EXPECT_EQ(10, Vec.find_first()); |
| 1200 |
EXPECT_EQ(213U, Vec.size()); |
| 1201 |
EXPECT_EQ(102U, Vec.count()); |
| 1202 |
} |
| 1203 |
|
| 1204 |
TYPED_TEST(BitVectorTest, PopBack) { |
| 1205 |
TypeParam Vec(10, true); |
| 1206 |
EXPECT_EQ(10U, Vec.size()); |
| 1207 |
EXPECT_EQ(10U, Vec.count()); |
| 1208 |
EXPECT_EQ(true, Vec.back()); |
| 1209 |
|
| 1210 |
Vec.pop_back(); |
| 1211 |
EXPECT_EQ(9U, Vec.size()); |
| 1212 |
EXPECT_EQ(9U, Vec.count()); |
| 1213 |
EXPECT_EQ(true, Vec.back()); |
| 1214 |
|
| 1215 |
Vec.push_back(false); |
| 1216 |
EXPECT_EQ(10U, Vec.size()); |
| 1217 |
EXPECT_EQ(9U, Vec.count()); |
| 1218 |
EXPECT_EQ(false, Vec.back()); |
| 1219 |
|
| 1220 |
Vec.pop_back(); |
| 1221 |
EXPECT_EQ(9U, Vec.size()); |
| 1222 |
EXPECT_EQ(9U, Vec.count()); |
| 1223 |
EXPECT_EQ(true, Vec.back()); |
| 1224 |
} |
| 1225 |
|
| 1226 |
TYPED_TEST(BitVectorTest, DenseSet) { |
| 1227 |
DenseSet<TypeParam> Set; |
| 1228 |
TypeParam A(10, true); |
| 1229 |
auto I = Set.insert(A); |
| 1230 |
EXPECT_EQ(true, I.second); |
| 1231 |
|
| 1232 |
TypeParam B(5, true); |
| 1233 |
I = Set.insert(B); |
| 1234 |
EXPECT_EQ(true, I.second); |
| 1235 |
|
| 1236 |
TypeParam C(20, false); |
| 1237 |
C.set(19); |
| 1238 |
I = Set.insert(C); |
| 1239 |
EXPECT_EQ(true, I.second); |
| 1240 |
|
| 1241 |
#if LLVM_ENABLE_ABI_BREAKING_CHECKS |
| 1242 |
TypeParam D; |
| 1243 |
EXPECT_DEATH(Set.insert(D), |
| 1244 |
"Empty/Tombstone value shouldn't be inserted into map!"); |
| 1245 |
#endif |
| 1246 |
|
| 1247 |
EXPECT_EQ(3U, Set.size()); |
| 1248 |
EXPECT_EQ(1U, Set.count(A)); |
| 1249 |
EXPECT_EQ(1U, Set.count(B)); |
| 1250 |
EXPECT_EQ(1U, Set.count(C)); |
| 1251 |
|
| 1252 |
EXPECT_EQ(true, Set.erase(B)); |
| 1253 |
EXPECT_EQ(2U, Set.size()); |
| 1254 |
|
| 1255 |
EXPECT_EQ(true, Set.erase(C)); |
| 1256 |
EXPECT_EQ(1U, Set.size()); |
| 1257 |
|
| 1258 |
EXPECT_EQ(true, Set.erase(A)); |
| 1259 |
EXPECT_EQ(0U, Set.size()); |
| 1260 |
} |
| 1261 |
|
| 1262 |
/// Test that capacity doesn't affect hashing. |
| 1263 |
TYPED_TEST(BitVectorTest, DenseMapHashing) { |
| 1264 |
using DMI = DenseMapInfo<TypeParam>; |
| 1265 |
{ |
| 1266 |
TypeParam A; |
| 1267 |
A.resize(200); |
| 1268 |
A.set(100); |
| 1269 |
|
| 1270 |
TypeParam B; |
| 1271 |
B.resize(200); |
| 1272 |
B.set(100); |
| 1273 |
B.reserve(1000); |
| 1274 |
|
| 1275 |
EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B)); |
| 1276 |
} |
| 1277 |
{ |
| 1278 |
TypeParam A; |
| 1279 |
A.resize(20); |
| 1280 |
A.set(10); |
| 1281 |
|
| 1282 |
TypeParam B; |
| 1283 |
B.resize(20); |
| 1284 |
B.set(10); |
| 1285 |
B.reserve(1000); |
| 1286 |
|
| 1287 |
EXPECT_EQ(DMI::getHashValue(A), DMI::getHashValue(B)); |
| 1288 |
} |
| 1289 |
} |
| 1290 |
|
| 1291 |
TEST(BitVectoryTest, Apply) { |
| 1292 |
for (int i = 0; i < 2; ++i) { |
| 1293 |
int j = i * 100 + 3; |
| 1294 |
|
| 1295 |
const BitVector x = |
| 1296 |
createBitVector<BitVector>(j + 5, {{i, i + 1}, {j - 1, j}}); |
| 1297 |
const BitVector y = createBitVector<BitVector>(j + 5, {{i, j}}); |
| 1298 |
const BitVector z = |
| 1299 |
createBitVector<BitVector>(j + 5, {{i + 1, i + 2}, {j, j + 1}}); |
| 1300 |
|
| 1301 |
auto op0 = [](auto x) { return ~x; }; |
| 1302 |
BitVector expected0 = x; |
| 1303 |
expected0.flip(); |
| 1304 |
BitVector out0(j - 2); |
| 1305 |
BitVector::apply(op0, out0, x); |
| 1306 |
EXPECT_EQ(out0, expected0); |
| 1307 |
|
| 1308 |
auto op1 = [](auto x, auto y) { return x & ~y; }; |
| 1309 |
BitVector expected1 = x; |
| 1310 |
expected1.reset(y); |
| 1311 |
BitVector out1; |
| 1312 |
BitVector::apply(op1, out1, x, y); |
| 1313 |
EXPECT_EQ(out1, expected1); |
| 1314 |
|
| 1315 |
auto op2 = [](auto x, auto y, auto z) { return (x ^ ~y) | z; }; |
| 1316 |
BitVector expected2 = y; |
| 1317 |
expected2.flip(); |
| 1318 |
expected2 ^= x; |
| 1319 |
expected2 |= z; |
| 1320 |
BitVector out2(j + 5); |
| 1321 |
BitVector::apply(op2, out2, x, y, z); |
| 1322 |
EXPECT_EQ(out2, expected2); |
| 1323 |
} |
| 1324 |
} |
| 1325 |
|
| 1326 |
|
| 1327 |
} // namespace |