aboutsummaryrefslogtreecommitdiffstats
path: root/unittests/ADT
diff options
context:
space:
mode:
authorJakob Stoklund Olesen <stoklund@2pi.dk>2010-11-28 22:17:11 +0000
committerJakob Stoklund Olesen <stoklund@2pi.dk>2010-11-28 22:17:11 +0000
commit5f456cda98c57b6dea8bc716978b69776d0d0e8f (patch)
tree8991c16484dbec0aafc1c0971afcef6b5561b079 /unittests/ADT
parentd652dbe72044b07a681b579a0a938c613ef15ae8 (diff)
downloadexternal_llvm-5f456cda98c57b6dea8bc716978b69776d0d0e8f.zip
external_llvm-5f456cda98c57b6dea8bc716978b69776d0d0e8f.tar.gz
external_llvm-5f456cda98c57b6dea8bc716978b69776d0d0e8f.tar.bz2
Disallow overlapping inserts, even when inserting the same value.
We always disallowed overlapping inserts with different values, and this makes the insertion code smaller and faster. If an overwriting insert is needed, it can be added as a separate method that trims any existing intervals before inserting. The immediate use cases for IntervalMap don't need this - they only use disjoint insertions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120264 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'unittests/ADT')
-rw-r--r--unittests/ADT/IntervalMapTest.cpp106
1 files changed, 9 insertions, 97 deletions
diff --git a/unittests/ADT/IntervalMapTest.cpp b/unittests/ADT/IntervalMapTest.cpp
index 6b8e761..445afca 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());