summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/ADT/IntervalMap.h122
-rw-r--r--unittests/ADT/IntervalMapTest.cpp106
2 files changed, 54 insertions, 174 deletions
diff --git a/include/llvm/ADT/IntervalMap.h b/include/llvm/ADT/IntervalMap.h
index 8416f71b7f..d0a3b53087 100644
--- a/include/llvm/ADT/IntervalMap.h
+++ b/include/llvm/ADT/IntervalMap.h
@@ -586,8 +586,7 @@ public:
return Traits::startLess(x, start(i)) ? NotFound : value(i);
}
- IdxPair insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y);
- unsigned extendStop(unsigned i, unsigned Size, KeyT b);
+ unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
#ifndef NDEBUG
void dump(raw_ostream &OS, unsigned Size) {
@@ -610,91 +609,58 @@ public:
/// @param y Value be mapped.
/// @return (insert position, new size), or (i, Capacity+1) on overflow.
template <typename KeyT, typename ValT, unsigned N, typename Traits>
-IdxPair LeafNode<KeyT, ValT, N, Traits>::
-insertFrom(unsigned i, unsigned Size, KeyT a, KeyT b, ValT y) {
+unsigned LeafNode<KeyT, ValT, N, Traits>::
+insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
+ unsigned i = Pos;
assert(i <= Size && Size <= N && "Invalid index");
assert(!Traits::stopLess(b, a) && "Invalid interval");
// Verify the findFrom invariant.
assert((i == 0 || Traits::stopLess(stop(i - 1), a)));
assert((i == Size || !Traits::stopLess(stop(i), a)));
+ assert((i == Size || Traits::stopLess(b, start(i))) && "Overlapping insert");
// Coalesce with previous interval.
- if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a))
- return IdxPair(i - 1, extendStop(i - 1, Size, b));
+ if (i && value(i - 1) == y && Traits::adjacent(stop(i - 1), a)) {
+ Pos = i - 1;
+ // Also coalesce with next interval?
+ if (i != Size && value(i) == y && Traits::adjacent(b, start(i))) {
+ stop(i - 1) = stop(i);
+ this->erase(i, Size);
+ return Size - 1;
+ }
+ stop(i - 1) = b;
+ return Size;
+ }
// Detect overflow.
if (i == N)
- return IdxPair(i, N + 1);
+ return N + 1;
// Add new interval at end.
if (i == Size) {
start(i) = a;
stop(i) = b;
value(i) = y;
- return IdxPair(i, Size + 1);
- }
-
- // Overlapping intervals?
- if (!Traits::stopLess(b, start(i))) {
- assert(value(i) == y && "Inconsistent values in overlapping intervals");
- if (Traits::startLess(a, start(i)))
- start(i) = a;
- return IdxPair(i, extendStop(i, Size, b));
+ return Size + 1;
}
// Try to coalesce with following interval.
if (value(i) == y && Traits::adjacent(b, start(i))) {
start(i) = a;
- return IdxPair(i, Size);
+ return Size;
}
// We must insert before i. Detect overflow.
if (Size == N)
- return IdxPair(i, N + 1);
+ return N + 1;
// Insert before i.
this->shift(i, Size);
start(i) = a;
stop(i) = b;
value(i) = y;
- return IdxPair(i, Size + 1);
-}
-
-/// extendStop - Extend stop(i) to b, coalescing with following intervals.
-/// @param i Interval to extend.
-/// @param Size Number of elements in node.
-/// @param b New interval end point.
-/// @return New node size after coalescing.
-template <typename KeyT, typename ValT, unsigned N, typename Traits>
-unsigned LeafNode<KeyT, ValT, N, Traits>::
-extendStop(unsigned i, unsigned Size, KeyT b) {
- assert(i < Size && Size <= N && "Bad indices");
-
- // Are we even extending the interval?
- if (Traits::startLess(b, stop(i)))
- return Size;
-
- // Find the first interval that may be preserved.
- unsigned j = findFrom(i + 1, Size, b);
- if (j < Size) {
- // Would key[i] overlap key[j] after the extension?
- if (Traits::stopLess(b, start(j))) {
- // Not overlapping. Perhaps adjacent and coalescable?
- if (value(i) == value(j) && Traits::adjacent(b, start(j)))
- b = stop(j++);
- } else {
- // Overlap. Include key[j] in the new interval.
- assert(value(i) == value(j) && "Overlapping values");
- b = stop(j++);
- }
- }
- stop(i) = b;
-
- // Entries [i+1;j) were coalesced.
- if (i + 1 < j && j < Size)
- this->erase(i + 1, j, Size);
- return Size - (j - (i + 1));
+ return Size + 1;
}
@@ -1138,7 +1104,7 @@ public:
// Easy insert into root leaf.
unsigned p = rootLeaf().findFrom(0, rootSize, a);
- rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y).second;
+ rootSize = rootLeaf().insertFrom(p, rootSize, a, b, y);
}
/// clear - Remove all entries.
@@ -1697,12 +1663,11 @@ iterator::insert(KeyT a, KeyT b, ValT y) {
IntervalMapImpl::Path &P = this->path;
// Try simple root leaf insert.
- IdxPair IP = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
+ unsigned Size = IM.rootLeaf().insertFrom(P.leafOffset(), IM.rootSize, a, b, y);
// Was the root node insert successful?
- if (IP.second <= RootLeaf::Capacity) {
- P.leafOffset() = IP.first;
- P.setSize(0, IM.rootSize = IP.second);
+ if (Size <= RootLeaf::Capacity) {
+ P.setSize(0, IM.rootSize = Size);
return;
}
@@ -1719,14 +1684,15 @@ template <typename KeyT, typename ValT, unsigned N, typename Traits>
void IntervalMap<KeyT, ValT, N, Traits>::
iterator::treeInsert(KeyT a, KeyT b, ValT y) {
using namespace IntervalMapImpl;
- IntervalMap &IM = *this->map;
Path &P = this->path;
+ if (!P.valid())
+ P.legalizeForInsert(this->map->height);
+
// Check if this insertion will extend the node to the left.
- if (P.valid() && P.leafOffset() == 0 &&
- Traits::startLess(a, P.leaf<Leaf>().start(0))) {
+ if (P.leafOffset() == 0 && Traits::startLess(a, P.leaf<Leaf>().start(0))) {
// Node is growing to the left, will it affect a left sibling node?
- if (NodeRef Sib = P.getLeftSibling(IM.height)) {
+ if (NodeRef Sib = P.getLeftSibling(P.height())) {
Leaf &SibLeaf = Sib.get<Leaf>();
unsigned SibOfs = Sib.size() - 1;
if (SibLeaf.value(SibOfs) == y &&
@@ -1737,11 +1703,11 @@ iterator::treeInsert(KeyT a, KeyT b, ValT y) {
// 2. Extend a to SibLeaf, erase the SibLeaf entry and continue.
// We prefer 1., but need 2 when coalescing to the right as well.
Leaf &CurLeaf = P.leaf<Leaf>();
- P.moveLeft(IM.height);
+ P.moveLeft(P.height());
if (Traits::stopLess(b, CurLeaf.start(0)) &&
(y != CurLeaf.value(0) || !Traits::adjacent(b, CurLeaf.start(0)))) {
// Easy, just extend SibLeaf and we're done.
- setNodeStop(IM.height, SibLeaf.stop(SibOfs) = b);
+ setNodeStop(P.height(), SibLeaf.stop(SibOfs) = b);
return;
} else {
// We have both left and right coalescing. Erase the old SibLeaf entry
@@ -1752,27 +1718,29 @@ iterator::treeInsert(KeyT a, KeyT b, ValT y) {
}
} else {
// No left sibling means we are at begin(). Update cached bound.
- IM.rootBranchStart() = a;
+ this->map->rootBranchStart() = a;
}
}
- P.legalizeForInsert(IM.height);
- IdxPair IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
+ // When we are inserting at the end of a leaf node, we must update stops.
+ unsigned Size = P.leafSize();
+ bool Grow = P.leafOffset() == Size;
+ Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), Size, a, b, y);
// Leaf insertion unsuccessful? Overflow and try again.
- if (IP.second > Leaf::Capacity) {
- overflow<Leaf>(IM.height);
- IP = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
- assert(IP.second <= Leaf::Capacity && "overflow() didn't make room");
+ if (Size > Leaf::Capacity) {
+ overflow<Leaf>(P.height());
+ Grow = P.leafOffset() == P.leafSize();
+ Size = P.leaf<Leaf>().insertFrom(P.leafOffset(), P.leafSize(), a, b, y);
+ assert(Size <= Leaf::Capacity && "overflow() didn't make room");
}
// Inserted, update offset and leaf size.
- P.leafOffset() = IP.first;
- P.setSize(IM.height, IP.second);
+ P.setSize(P.height(), Size);
// Insert was the last node entry, update stops.
- if (IP.first == IP.second - 1)
- setNodeStop(IM.height, P.leaf<Leaf>().stop(IP.first));
+ if (Grow)
+ setNodeStop(P.height(), b);
}
/// erase - erase the current interval and move to the next position.
diff --git a/unittests/ADT/IntervalMapTest.cpp b/unittests/ADT/IntervalMapTest.cpp
index 6b8e761ae7..445afcaf7a 100644
--- a/unittests/ADT/IntervalMapTest.cpp
+++ b/unittests/ADT/IntervalMapTest.cpp
@@ -116,50 +116,26 @@ TEST(IntervalMapTest, RootCoalescing) {
EXPECT_EQ(90u, map.start());
EXPECT_EQ(150u, map.stop());
- // Overlap left.
- map.insert(80, 100, 1);
- EXPECT_EQ(1, std::distance(map.begin(), map.end()));
- EXPECT_EQ(80u, map.start());
- EXPECT_EQ(150u, map.stop());
-
- // Inside.
- map.insert(100, 130, 1);
- EXPECT_EQ(1, std::distance(map.begin(), map.end()));
- EXPECT_EQ(80u, map.start());
- EXPECT_EQ(150u, map.stop());
-
- // Overlap both.
- map.insert(70, 160, 1);
- EXPECT_EQ(1, std::distance(map.begin(), map.end()));
- EXPECT_EQ(70u, map.start());
- EXPECT_EQ(160u, map.stop());
-
- // Overlap right.
- map.insert(80, 170, 1);
- EXPECT_EQ(1, std::distance(map.begin(), map.end()));
- EXPECT_EQ(70u, map.start());
- EXPECT_EQ(170u, map.stop());
-
// Coalesce from the right.
- map.insert(170, 200, 1);
+ map.insert(151, 200, 1);
EXPECT_EQ(1, std::distance(map.begin(), map.end()));
- EXPECT_EQ(70u, map.start());
+ EXPECT_EQ(90u, map.start());
EXPECT_EQ(200u, map.stop());
// Non-coalesce from the left.
- map.insert(60, 69, 2);
+ map.insert(60, 89, 2);
EXPECT_EQ(2, std::distance(map.begin(), map.end()));
EXPECT_EQ(60u, map.start());
EXPECT_EQ(200u, map.stop());
- EXPECT_EQ(2u, map.lookup(69));
- EXPECT_EQ(1u, map.lookup(70));
+ EXPECT_EQ(2u, map.lookup(89));
+ EXPECT_EQ(1u, map.lookup(90));
UUMap::iterator I = map.begin();
EXPECT_EQ(60u, I.start());
- EXPECT_EQ(69u, I.stop());
+ EXPECT_EQ(89u, I.stop());
EXPECT_EQ(2u, I.value());
++I;
- EXPECT_EQ(70u, I.start());
+ EXPECT_EQ(90u, I.start());
EXPECT_EQ(200u, I.stop());
EXPECT_EQ(1u, I.value());
++I;
@@ -176,13 +152,13 @@ TEST(IntervalMapTest, RootCoalescing) {
// Erase from the left.
map.begin().erase();
EXPECT_EQ(2, std::distance(map.begin(), map.end()));
- EXPECT_EQ(70u, map.start());
+ EXPECT_EQ(90u, map.start());
EXPECT_EQ(210u, map.stop());
// Erase from the right.
(--map.end()).erase();
EXPECT_EQ(1, std::distance(map.begin(), map.end()));
- EXPECT_EQ(70u, map.start());
+ EXPECT_EQ(90u, map.start());
EXPECT_EQ(200u, map.stop());
}
@@ -288,70 +264,6 @@ TEST(IntervalMapTest, RootMultiCoalescing) {
++I;
EXPECT_FALSE(I.valid());
- // Coalesce multiple with overlap right.
- // [100;115] [120;150] [160;170]
- map.insert(116, 165, 1);
- I = map.begin();
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(100u, I.start());
- EXPECT_EQ(170u, I.stop());
- ++I;
- EXPECT_FALSE(I.valid());
-
- // Coalesce multiple with overlap left
- // [100;170]
- map.insert(180, 190, 1);
- map.insert(200, 210, 1);
- map.insert(220, 230, 1);
- // [100;170] [180;190] [200;210] [220;230]
- map.insert(160, 199, 1);
- I = map.begin();
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(100u, I.start());
- EXPECT_EQ(210u, I.stop());
- ++I;
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(220u, I.start());
- EXPECT_EQ(230u, I.stop());
- ++I;
- EXPECT_FALSE(I.valid());
-
- // Overwrite 2 from gap to gap.
- // [100;210] [220;230]
- map.insert(50, 250, 1);
- I = map.begin();
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(50u, I.start());
- EXPECT_EQ(250u, I.stop());
- ++I;
- EXPECT_FALSE(I.valid());
-
- // Coalesce at end of full root.
- // [50;250]
- map.insert(260, 270, 1);
- map.insert(280, 290, 1);
- map.insert(300, 310, 1);
- // [50;250] [260;270] [280;290] [300;310]
- map.insert(311, 320, 1);
- I = map.begin();
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(50u, I.start());
- EXPECT_EQ(250u, I.stop());
- ++I;
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(260u, I.start());
- EXPECT_EQ(270u, I.stop());
- ++I;
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(280u, I.start());
- EXPECT_EQ(290u, I.stop());
- ++I;
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(300u, I.start());
- EXPECT_EQ(320u, I.stop());
- ++I;
- EXPECT_FALSE(I.valid());
-
// Test clear() on non-branched map.
map.clear();
EXPECT_TRUE(map.empty());
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-30 06:36:25 +0000