| 1 |
//=== CoalescingBitVectorTest.cpp - CoalescingBitVector unit 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/CoalescingBitVector.h" |
| 10 |
#include "gtest/gtest.h" |
| 11 |
|
| 12 |
using namespace llvm; |
| 13 |
|
| 14 |
namespace { |
| 15 |
|
| 16 |
using UBitVec = CoalescingBitVector<unsigned>; |
| 17 |
using U64BitVec = CoalescingBitVector<uint64_t>; |
| 18 |
|
| 19 |
bool elementsMatch(const UBitVec &BV, std::initializer_list<unsigned> List) { |
| 20 |
if (!std::equal(BV.begin(), BV.end(), List.begin(), List.end())) { |
| 21 |
UBitVec::Allocator Alloc; |
| 22 |
UBitVec Expected(Alloc); |
| 23 |
Expected.set(List); |
| 24 |
dbgs() << "elementsMatch:\n" |
| 25 |
<< " Expected: "; |
| 26 |
Expected.print(dbgs()); |
| 27 |
dbgs() << " Got: "; |
| 28 |
BV.print(dbgs()); |
| 29 |
return false; |
| 30 |
} |
| 31 |
return true; |
| 32 |
} |
| 33 |
|
| 34 |
bool rangesMatch(iterator_range<UBitVec::const_iterator> R, |
| 35 |
std::initializer_list<unsigned> List) { |
| 36 |
return std::equal(R.begin(), R.end(), List.begin(), List.end()); |
| 37 |
} |
| 38 |
|
| 39 |
TEST(CoalescingBitVectorTest, Set) { |
| 40 |
UBitVec::Allocator Alloc; |
| 41 |
UBitVec BV1(Alloc); |
| 42 |
UBitVec BV2(Alloc); |
| 43 |
|
| 44 |
BV1.set(0); |
| 45 |
EXPECT_TRUE(BV1.test(0)); |
| 46 |
EXPECT_FALSE(BV1.test(1)); |
| 47 |
|
| 48 |
BV2.set(BV1); |
| 49 |
EXPECT_TRUE(BV2.test(0)); |
| 50 |
} |
| 51 |
|
| 52 |
TEST(CoalescingBitVectorTest, Count) { |
| 53 |
UBitVec::Allocator Alloc; |
| 54 |
UBitVec BV(Alloc); |
| 55 |
EXPECT_EQ(BV.count(), 0u); |
| 56 |
BV.set(0); |
| 57 |
EXPECT_EQ(BV.count(), 1u); |
| 58 |
BV.set({11, 12, 13, 14, 15}); |
| 59 |
EXPECT_EQ(BV.count(), 6u); |
| 60 |
} |
| 61 |
|
| 62 |
TEST(CoalescingBitVectorTest, ClearAndEmpty) { |
| 63 |
UBitVec::Allocator Alloc; |
| 64 |
UBitVec BV(Alloc); |
| 65 |
EXPECT_TRUE(BV.empty()); |
| 66 |
BV.set(1); |
| 67 |
EXPECT_FALSE(BV.empty()); |
| 68 |
BV.clear(); |
| 69 |
EXPECT_TRUE(BV.empty()); |
| 70 |
} |
| 71 |
|
| 72 |
TEST(CoalescingBitVector, Copy) { |
| 73 |
UBitVec::Allocator Alloc; |
| 74 |
UBitVec BV1(Alloc); |
| 75 |
BV1.set(0); |
| 76 |
UBitVec BV2 = BV1; |
| 77 |
EXPECT_TRUE(elementsMatch(BV1, {0})); |
| 78 |
EXPECT_TRUE(elementsMatch(BV2, {0})); |
| 79 |
BV2.set(5); |
| 80 |
BV2 = BV1; |
| 81 |
EXPECT_TRUE(elementsMatch(BV1, {0})); |
| 82 |
EXPECT_TRUE(elementsMatch(BV2, {0})); |
| 83 |
} |
| 84 |
|
| 85 |
TEST(CoalescingBitVectorTest, Iterators) { |
| 86 |
UBitVec::Allocator Alloc; |
| 87 |
UBitVec BV(Alloc); |
| 88 |
|
| 89 |
BV.set({0, 1, 2}); |
| 90 |
|
| 91 |
auto It = BV.begin(); |
| 92 |
EXPECT_TRUE(It == BV.begin()); |
| 93 |
EXPECT_EQ(*It, 0u); |
| 94 |
++It; |
| 95 |
EXPECT_EQ(*It, 1u); |
| 96 |
++It; |
| 97 |
EXPECT_EQ(*It, 2u); |
| 98 |
++It; |
| 99 |
EXPECT_TRUE(It == BV.end()); |
| 100 |
EXPECT_TRUE(BV.end() == BV.end()); |
| 101 |
|
| 102 |
It = BV.begin(); |
| 103 |
EXPECT_TRUE(It == BV.begin()); |
| 104 |
auto ItCopy = It++; |
| 105 |
EXPECT_TRUE(ItCopy == BV.begin()); |
| 106 |
EXPECT_EQ(*ItCopy, 0u); |
| 107 |
EXPECT_EQ(*It, 1u); |
| 108 |
|
| 109 |
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2})); |
| 110 |
|
| 111 |
BV.set({4, 5, 6}); |
| 112 |
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6})); |
| 113 |
|
| 114 |
BV.set(3); |
| 115 |
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6})); |
| 116 |
|
| 117 |
BV.set(10); |
| 118 |
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6, 10})); |
| 119 |
|
| 120 |
// Should be able to reset unset bits. |
| 121 |
BV.reset(3); |
| 122 |
BV.reset(3); |
| 123 |
BV.reset(20000); |
| 124 |
BV.set({1000, 1001, 1002}); |
| 125 |
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6, 10, 1000, 1001, 1002})); |
| 126 |
|
| 127 |
auto It1 = BV.begin(); |
| 128 |
EXPECT_TRUE(It1 == BV.begin()); |
| 129 |
EXPECT_TRUE(++It1 == ++BV.begin()); |
| 130 |
EXPECT_TRUE(It1 != BV.begin()); |
| 131 |
EXPECT_TRUE(It1 != BV.end()); |
| 132 |
} |
| 133 |
|
| 134 |
TEST(CoalescingBitVectorTest, Reset) { |
| 135 |
UBitVec::Allocator Alloc; |
| 136 |
UBitVec BV(Alloc); |
| 137 |
|
| 138 |
BV.set(0); |
| 139 |
EXPECT_TRUE(BV.test(0)); |
| 140 |
BV.reset(0); |
| 141 |
EXPECT_FALSE(BV.test(0)); |
| 142 |
|
| 143 |
BV.clear(); |
| 144 |
BV.set({1, 2, 3}); |
| 145 |
BV.reset(1); |
| 146 |
EXPECT_TRUE(elementsMatch(BV, {2, 3})); |
| 147 |
|
| 148 |
BV.clear(); |
| 149 |
BV.set({1, 2, 3}); |
| 150 |
BV.reset(2); |
| 151 |
EXPECT_TRUE(elementsMatch(BV, {1, 3})); |
| 152 |
|
| 153 |
BV.clear(); |
| 154 |
BV.set({1, 2, 3}); |
| 155 |
BV.reset(3); |
| 156 |
EXPECT_TRUE(elementsMatch(BV, {1, 2})); |
| 157 |
} |
| 158 |
|
| 159 |
TEST(CoalescingBitVectorTest, Comparison) { |
| 160 |
UBitVec::Allocator Alloc; |
| 161 |
UBitVec BV1(Alloc); |
| 162 |
UBitVec BV2(Alloc); |
| 163 |
|
| 164 |
// Single interval. |
| 165 |
BV1.set({1, 2, 3}); |
| 166 |
BV2.set({1, 2, 3}); |
| 167 |
EXPECT_EQ(BV1, BV2); |
| 168 |
EXPECT_FALSE(BV1 != BV2); |
| 169 |
|
| 170 |
// Different number of intervals. |
| 171 |
BV1.clear(); |
| 172 |
BV2.clear(); |
| 173 |
BV1.set({1, 2, 3}); |
| 174 |
EXPECT_NE(BV1, BV2); |
| 175 |
|
| 176 |
// Multiple intervals. |
| 177 |
BV1.clear(); |
| 178 |
BV2.clear(); |
| 179 |
BV1.set({1, 2, 11, 12}); |
| 180 |
BV2.set({1, 2, 11, 12}); |
| 181 |
EXPECT_EQ(BV1, BV2); |
| 182 |
BV2.reset(1); |
| 183 |
EXPECT_NE(BV1, BV2); |
| 184 |
BV2.set(1); |
| 185 |
BV2.reset(11); |
| 186 |
EXPECT_NE(BV1, BV2); |
| 187 |
} |
| 188 |
|
| 189 |
// A simple implementation of set union, used to double-check the human |
| 190 |
// "expected" answer. |
| 191 |
void simpleUnion(UBitVec &Union, const UBitVec &LHS, |
| 192 |
const UBitVec &RHS) { |
| 193 |
for (unsigned Bit : LHS) |
| 194 |
Union.test_and_set(Bit); |
| 195 |
for (unsigned Bit : RHS) |
| 196 |
Union.test_and_set(Bit); |
| 197 |
} |
| 198 |
|
| 199 |
TEST(CoalescingBitVectorTest, Union) { |
| 200 |
UBitVec::Allocator Alloc; |
| 201 |
|
| 202 |
// Check that after doing LHS |= RHS, LHS == Expected. |
| 203 |
auto unionIs = [&](std::initializer_list<unsigned> LHS, |
| 204 |
std::initializer_list<unsigned> RHS, |
| 205 |
std::initializer_list<unsigned> Expected) { |
| 206 |
UBitVec BV1(Alloc); |
| 207 |
BV1.set(LHS); |
| 208 |
UBitVec BV2(Alloc); |
| 209 |
BV2.set(RHS); |
| 210 |
UBitVec DoubleCheckedExpected(Alloc); |
| 211 |
simpleUnion(DoubleCheckedExpected, BV1, BV2); |
| 212 |
ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected)); |
| 213 |
BV1 |= BV2; |
| 214 |
ASSERT_TRUE(elementsMatch(BV1, Expected)); |
| 215 |
}; |
| 216 |
|
| 217 |
// Check that "LHS |= RHS" and "RHS |= LHS" both produce the expected result. |
| 218 |
auto testUnionSymmetrically = [&](std::initializer_list<unsigned> LHS, |
| 219 |
std::initializer_list<unsigned> RHS, |
| 220 |
std::initializer_list<unsigned> Expected) { |
| 221 |
unionIs(LHS, RHS, Expected); |
| 222 |
unionIs(RHS, LHS, Expected); |
| 223 |
}; |
| 224 |
|
| 225 |
// Empty LHS. |
| 226 |
testUnionSymmetrically({}, {1, 2, 3}, {1, 2, 3}); |
| 227 |
|
| 228 |
// Empty RHS. |
| 229 |
testUnionSymmetrically({1, 2, 3}, {}, {1, 2, 3}); |
| 230 |
|
| 231 |
// Full overlap. |
| 232 |
testUnionSymmetrically({1}, {1}, {1}); |
| 233 |
testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12}); |
| 234 |
|
| 235 |
// Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after |
| 236 |
// it. Repeat this swapping LHS and RHS. |
| 237 |
testUnionSymmetrically({2, 3, 4}, {1, 2, 3}, {1, 2, 3, 4}); |
| 238 |
testUnionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4}); |
| 239 |
testUnionSymmetrically({2, 3, 4}, {3, 4, 5}, {2, 3, 4, 5}); |
| 240 |
testUnionSymmetrically({1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4}); |
| 241 |
testUnionSymmetrically({3, 4, 5}, {2, 3, 4}, {2, 3, 4, 5}); |
| 242 |
|
| 243 |
// Multiple overlaps, but at least one of the overlaps forces us to split an |
| 244 |
// interval (and possibly both do). For ease of understanding, fix LHS to be |
| 245 |
// {1, 2, 11, 12}, but vary RHS. |
| 246 |
testUnionSymmetrically({1, 2, 11, 12}, {1}, {1, 2, 11, 12}); |
| 247 |
testUnionSymmetrically({1, 2, 11, 12}, {2}, {1, 2, 11, 12}); |
| 248 |
testUnionSymmetrically({1, 2, 11, 12}, {11}, {1, 2, 11, 12}); |
| 249 |
testUnionSymmetrically({1, 2, 11, 12}, {12}, {1, 2, 11, 12}); |
| 250 |
testUnionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 2, 11, 12}); |
| 251 |
testUnionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 2, 11, 12}); |
| 252 |
testUnionSymmetrically({1, 2, 11, 12}, {2, 11}, {1, 2, 11, 12}); |
| 253 |
testUnionSymmetrically({1, 2, 11, 12}, {2, 12}, {1, 2, 11, 12}); |
| 254 |
testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11, 12}); |
| 255 |
testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 11, 12}); |
| 256 |
testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 2, 11, 12}); |
| 257 |
testUnionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {1, 2, 11, 12}); |
| 258 |
testUnionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {0, 1, 2, 11, 12}); |
| 259 |
testUnionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {1, 2, 3, 11, 12}); |
| 260 |
testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 2, 11, 12, 13}); |
| 261 |
testUnionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 2, 10, 11, 12}); |
| 262 |
|
| 263 |
// Partial overlap, but the existing interval covers future overlaps. |
| 264 |
testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7}, |
| 265 |
{1, 2, 3, 4, 5, 6, 7, 8}); |
| 266 |
testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 7, 8, 9}, |
| 267 |
{1, 2, 3, 4, 5, 6, 7, 8, 9}); |
| 268 |
|
| 269 |
// More partial overlaps. |
| 270 |
testUnionSymmetrically({1, 2, 3, 4, 5}, {0, 1, 2, 4, 5, 6}, |
| 271 |
{0, 1, 2, 3, 4, 5, 6}); |
| 272 |
testUnionSymmetrically({2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4}); |
| 273 |
testUnionSymmetrically({3, 4}, {1, 2, 3, 4}, {1, 2, 3, 4}); |
| 274 |
testUnionSymmetrically({1, 2}, {1, 2, 3, 4}, {1, 2, 3, 4}); |
| 275 |
testUnionSymmetrically({0, 1}, {1, 2, 3, 4}, {0, 1, 2, 3, 4}); |
| 276 |
|
| 277 |
// Merge non-overlapping. |
| 278 |
testUnionSymmetrically({0, 1}, {2, 3}, {0, 1, 2, 3}); |
| 279 |
testUnionSymmetrically({0, 3}, {1, 2}, {0, 1, 2, 3}); |
| 280 |
} |
| 281 |
|
| 282 |
// A simple implementation of set intersection, used to double-check the |
| 283 |
// human "expected" answer. |
| 284 |
void simpleIntersection(UBitVec &Intersection, const UBitVec &LHS, |
| 285 |
const UBitVec &RHS) { |
| 286 |
for (unsigned Bit : LHS) |
| 287 |
if (RHS.test(Bit)) |
| 288 |
Intersection.set(Bit); |
| 289 |
} |
| 290 |
|
| 291 |
TEST(CoalescingBitVectorTest, Intersection) { |
| 292 |
UBitVec::Allocator Alloc; |
| 293 |
|
| 294 |
// Check that after doing LHS &= RHS, LHS == Expected. |
| 295 |
auto intersectionIs = [&](std::initializer_list<unsigned> LHS, |
| 296 |
std::initializer_list<unsigned> RHS, |
| 297 |
std::initializer_list<unsigned> Expected) { |
| 298 |
UBitVec BV1(Alloc); |
| 299 |
BV1.set(LHS); |
| 300 |
UBitVec BV2(Alloc); |
| 301 |
BV2.set(RHS); |
| 302 |
UBitVec DoubleCheckedExpected(Alloc); |
| 303 |
simpleIntersection(DoubleCheckedExpected, BV1, BV2); |
| 304 |
ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected)); |
| 305 |
BV1 &= BV2; |
| 306 |
ASSERT_TRUE(elementsMatch(BV1, Expected)); |
| 307 |
}; |
| 308 |
|
| 309 |
// Check that "LHS &= RHS" and "RHS &= LHS" both produce the expected result. |
| 310 |
auto testIntersectionSymmetrically = [&](std::initializer_list<unsigned> LHS, |
| 311 |
std::initializer_list<unsigned> RHS, |
| 312 |
std::initializer_list<unsigned> Expected) { |
| 313 |
intersectionIs(LHS, RHS, Expected); |
| 314 |
intersectionIs(RHS, LHS, Expected); |
| 315 |
}; |
| 316 |
|
| 317 |
// Empty case, one-element case. |
| 318 |
testIntersectionSymmetrically({}, {}, {}); |
| 319 |
testIntersectionSymmetrically({1}, {1}, {1}); |
| 320 |
testIntersectionSymmetrically({1}, {2}, {}); |
| 321 |
|
| 322 |
// Exact overlaps cases: single overlap and multiple overlaps. |
| 323 |
testIntersectionSymmetrically({1, 2}, {1, 2}, {1, 2}); |
| 324 |
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12}); |
| 325 |
|
| 326 |
// Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after |
| 327 |
// it. |
| 328 |
testIntersectionSymmetrically({2, 3, 4}, {1, 2, 3}, {2, 3}); |
| 329 |
testIntersectionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4}); |
| 330 |
testIntersectionSymmetrically({2, 3, 4}, {3, 4, 5}, {3, 4}); |
| 331 |
|
| 332 |
// No overlap, but we have multiple intervals. |
| 333 |
testIntersectionSymmetrically({1, 2, 11, 12}, {3, 4, 13, 14}, {}); |
| 334 |
|
| 335 |
// Multiple overlaps, but at least one of the overlaps forces us to split an |
| 336 |
// interval (and possibly both do). For ease of understanding, fix LHS to be |
| 337 |
// {1, 2, 11, 12}, but vary RHS. |
| 338 |
testIntersectionSymmetrically({1, 2, 11, 12}, {1}, {1}); |
| 339 |
testIntersectionSymmetrically({1, 2, 11, 12}, {2}, {2}); |
| 340 |
testIntersectionSymmetrically({1, 2, 11, 12}, {11}, {11}); |
| 341 |
testIntersectionSymmetrically({1, 2, 11, 12}, {12}, {12}); |
| 342 |
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 11}); |
| 343 |
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 12}); |
| 344 |
testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11}, {2, 11}); |
| 345 |
testIntersectionSymmetrically({1, 2, 11, 12}, {2, 12}, {2, 12}); |
| 346 |
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11}); |
| 347 |
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 12}); |
| 348 |
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 11, 12}); |
| 349 |
testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {2, 11, 12}); |
| 350 |
testIntersectionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {11, 12}); |
| 351 |
testIntersectionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {11, 12}); |
| 352 |
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 11}); |
| 353 |
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 11}); |
| 354 |
|
| 355 |
// Partial overlap, but the existing interval covers future overlaps. |
| 356 |
testIntersectionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7}, |
| 357 |
{2, 3, 4, 6, 7}); |
| 358 |
} |
| 359 |
|
| 360 |
// A simple implementation of set intersection-with-complement, used to |
| 361 |
// double-check the human "expected" answer. |
| 362 |
void simpleIntersectionWithComplement(UBitVec &Intersection, const UBitVec &LHS, |
| 363 |
const UBitVec &RHS) { |
| 364 |
for (unsigned Bit : LHS) |
| 365 |
if (!RHS.test(Bit)) |
| 366 |
Intersection.set(Bit); |
| 367 |
} |
| 368 |
|
| 369 |
TEST(CoalescingBitVectorTest, IntersectWithComplement) { |
| 370 |
UBitVec::Allocator Alloc; |
| 371 |
|
| 372 |
// Check that after doing LHS.intersectWithComplement(RHS), LHS == Expected. |
| 373 |
auto intersectionWithComplementIs = |
| 374 |
[&](std::initializer_list<unsigned> LHS, |
| 375 |
std::initializer_list<unsigned> RHS, |
| 376 |
std::initializer_list<unsigned> Expected) { |
| 377 |
UBitVec BV1(Alloc); |
| 378 |
BV1.set(LHS); |
| 379 |
UBitVec BV2(Alloc); |
| 380 |
BV2.set(RHS); |
| 381 |
UBitVec DoubleCheckedExpected(Alloc); |
| 382 |
simpleIntersectionWithComplement(DoubleCheckedExpected, BV1, BV2); |
| 383 |
ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected)); |
| 384 |
BV1.intersectWithComplement(BV2); |
| 385 |
ASSERT_TRUE(elementsMatch(BV1, Expected)); |
| 386 |
}; |
| 387 |
|
| 388 |
// Empty case, one-element case. |
| 389 |
intersectionWithComplementIs({}, {}, {}); |
| 390 |
intersectionWithComplementIs({1}, {1}, {}); |
| 391 |
intersectionWithComplementIs({1}, {2}, {1}); |
| 392 |
|
| 393 |
// Exact overlaps cases: single overlap and multiple overlaps. |
| 394 |
intersectionWithComplementIs({1, 2}, {1, 2}, {}); |
| 395 |
intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11, 12}, {}); |
| 396 |
|
| 397 |
// Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after |
| 398 |
// it. Repeat this swapping LHS and RHS. |
| 399 |
intersectionWithComplementIs({2, 3, 4}, {1, 2, 3}, {4}); |
| 400 |
intersectionWithComplementIs({2, 3, 4}, {2, 3, 4}, {}); |
| 401 |
intersectionWithComplementIs({2, 3, 4}, {3, 4, 5}, {2}); |
| 402 |
intersectionWithComplementIs({1, 2, 3}, {2, 3, 4}, {1}); |
| 403 |
intersectionWithComplementIs({3, 4, 5}, {2, 3, 4}, {5}); |
| 404 |
|
| 405 |
// No overlap, but we have multiple intervals. |
| 406 |
intersectionWithComplementIs({1, 2, 11, 12}, {3, 4, 13, 14}, {1, 2, 11, 12}); |
| 407 |
|
| 408 |
// Multiple overlaps. For ease of understanding, fix LHS to be |
| 409 |
// {1, 2, 11, 12}, but vary RHS. |
| 410 |
intersectionWithComplementIs({1, 2, 11, 12}, {1}, {2, 11, 12}); |
| 411 |
intersectionWithComplementIs({1, 2, 11, 12}, {2}, {1, 11, 12}); |
| 412 |
intersectionWithComplementIs({1, 2, 11, 12}, {11}, {1, 2, 12}); |
| 413 |
intersectionWithComplementIs({1, 2, 11, 12}, {12}, {1, 2, 11}); |
| 414 |
intersectionWithComplementIs({1, 2, 11, 12}, {1, 11}, {2, 12}); |
| 415 |
intersectionWithComplementIs({1, 2, 11, 12}, {1, 12}, {2, 11}); |
| 416 |
intersectionWithComplementIs({1, 2, 11, 12}, {2, 11}, {1, 12}); |
| 417 |
intersectionWithComplementIs({1, 2, 11, 12}, {2, 12}, {1, 11}); |
| 418 |
intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11}, {12}); |
| 419 |
intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 12}, {11}); |
| 420 |
intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 12}, {2}); |
| 421 |
intersectionWithComplementIs({1, 2, 11, 12}, {2, 11, 12}, {1}); |
| 422 |
intersectionWithComplementIs({1, 2, 11, 12}, {0, 11, 12}, {1, 2}); |
| 423 |
intersectionWithComplementIs({1, 2, 11, 12}, {3, 11, 12}, {1, 2}); |
| 424 |
intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 13}, {2, 12}); |
| 425 |
intersectionWithComplementIs({1, 2, 11, 12}, {1, 10, 11}, {2, 12}); |
| 426 |
|
| 427 |
// Partial overlap, but the existing interval covers future overlaps. |
| 428 |
intersectionWithComplementIs({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7}, |
| 429 |
{1, 5, 8}); |
| 430 |
} |
| 431 |
|
| 432 |
TEST(CoalescingBitVectorTest, FindLowerBound) { |
| 433 |
U64BitVec::Allocator Alloc; |
| 434 |
U64BitVec BV(Alloc); |
| 435 |
uint64_t BigNum1 = uint64_t(1) << 32; |
| 436 |
uint64_t BigNum2 = (uint64_t(1) << 33) + 1; |
| 437 |
EXPECT_TRUE(BV.find(BigNum1) == BV.end()); |
| 438 |
BV.set(BigNum1); |
| 439 |
auto Find1 = BV.find(BigNum1); |
| 440 |
EXPECT_EQ(*Find1, BigNum1); |
| 441 |
BV.set(BigNum2); |
| 442 |
auto Find2 = BV.find(BigNum1); |
| 443 |
EXPECT_EQ(*Find2, BigNum1); |
| 444 |
auto Find3 = BV.find(BigNum2); |
| 445 |
EXPECT_EQ(*Find3, BigNum2); |
| 446 |
BV.reset(BigNum1); |
| 447 |
auto Find4 = BV.find(BigNum1); |
| 448 |
EXPECT_EQ(*Find4, BigNum2); |
| 449 |
|
| 450 |
BV.clear(); |
| 451 |
BV.set({1, 2, 3}); |
| 452 |
EXPECT_EQ(*BV.find(2), 2u); |
| 453 |
EXPECT_EQ(*BV.find(3), 3u); |
| 454 |
} |
| 455 |
|
| 456 |
TEST(CoalescingBitVectorTest, AdvanceToLowerBound) { |
| 457 |
U64BitVec::Allocator Alloc; |
| 458 |
U64BitVec BV(Alloc); |
| 459 |
uint64_t BigNum1 = uint64_t(1) << 32; |
| 460 |
uint64_t BigNum2 = (uint64_t(1) << 33) + 1; |
| 461 |
|
| 462 |
auto advFromBegin = [&](uint64_t To) -> U64BitVec::const_iterator { |
| 463 |
auto It = BV.begin(); |
| 464 |
It.advanceToLowerBound(To); |
| 465 |
return It; |
| 466 |
}; |
| 467 |
|
| 468 |
EXPECT_TRUE(advFromBegin(BigNum1) == BV.end()); |
| 469 |
BV.set(BigNum1); |
| 470 |
auto Find1 = advFromBegin(BigNum1); |
| 471 |
EXPECT_EQ(*Find1, BigNum1); |
| 472 |
BV.set(BigNum2); |
| 473 |
auto Find2 = advFromBegin(BigNum1); |
| 474 |
EXPECT_EQ(*Find2, BigNum1); |
| 475 |
auto Find3 = advFromBegin(BigNum2); |
| 476 |
EXPECT_EQ(*Find3, BigNum2); |
| 477 |
BV.reset(BigNum1); |
| 478 |
auto Find4 = advFromBegin(BigNum1); |
| 479 |
EXPECT_EQ(*Find4, BigNum2); |
| 480 |
|
| 481 |
BV.clear(); |
| 482 |
BV.set({1, 2, 3}); |
| 483 |
EXPECT_EQ(*advFromBegin(2), 2u); |
| 484 |
EXPECT_EQ(*advFromBegin(3), 3u); |
| 485 |
auto It = BV.begin(); |
| 486 |
It.advanceToLowerBound(0); |
| 487 |
EXPECT_EQ(*It, 1u); |
| 488 |
It.advanceToLowerBound(100); |
| 489 |
EXPECT_TRUE(It == BV.end()); |
| 490 |
It.advanceToLowerBound(100); |
| 491 |
EXPECT_TRUE(It == BV.end()); |
| 492 |
} |
| 493 |
|
| 494 |
TEST(CoalescingBitVectorTest, HalfOpenRange) { |
| 495 |
UBitVec::Allocator Alloc; |
| 496 |
|
| 497 |
{ |
| 498 |
UBitVec BV(Alloc); |
| 499 |
BV.set({1, 2, 3}); |
| 500 |
|
| 501 |
EXPECT_EQ(*BV.find(0), 1U); // find(Start) > Start |
| 502 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2, 3})); |
| 503 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 4), {1, 2, 3})); |
| 504 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 3), {1, 2})); |
| 505 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 3), {2})); |
| 506 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 4), {2, 3})); |
| 507 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(4, 5), {})); |
| 508 |
} |
| 509 |
|
| 510 |
{ |
| 511 |
UBitVec BV(Alloc); |
| 512 |
BV.set({1, 2, 11, 12}); |
| 513 |
|
| 514 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 15), {1, 2, 11, 12})); |
| 515 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 13), {1, 2, 11, 12})); |
| 516 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 12), {1, 2, 11})); |
| 517 |
|
| 518 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2})); |
| 519 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 5), {1, 2})); |
| 520 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 5), {2})); |
| 521 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 2), {1})); |
| 522 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(13, 14), {})); |
| 523 |
|
| 524 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 10), {2})); |
| 525 |
} |
| 526 |
|
| 527 |
{ |
| 528 |
UBitVec BV(Alloc); |
| 529 |
BV.set({1}); |
| 530 |
|
| 531 |
EXPECT_EQ(*BV.find(0), 1U); // find(Start) == End |
| 532 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 1), {})); |
| 533 |
} |
| 534 |
|
| 535 |
{ |
| 536 |
UBitVec BV(Alloc); |
| 537 |
BV.set({5}); |
| 538 |
|
| 539 |
EXPECT_EQ(*BV.find(3), 5U); // find(Start) > End |
| 540 |
EXPECT_TRUE(rangesMatch(BV.half_open_range(3, 4), {})); |
| 541 |
} |
| 542 |
} |
| 543 |
|
| 544 |
TEST(CoalescingBitVectorTest, Print) { |
| 545 |
std::string S; |
| 546 |
{ |
| 547 |
raw_string_ostream OS(S); |
| 548 |
UBitVec::Allocator Alloc; |
| 549 |
UBitVec BV(Alloc); |
| 550 |
BV.set({1}); |
| 551 |
BV.print(OS); |
| 552 |
|
| 553 |
BV.clear(); |
| 554 |
BV.set({1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}); |
| 555 |
BV.print(OS); |
| 556 |
} |
| 557 |
EXPECT_EQ(S, "{[1]}" |
| 558 |
"{[1][11, 20]}"); |
| 559 |
} |
| 560 |
|
| 561 |
} // namespace |