Add B+-tree test case that creates a height 3 tree with a smaller root node.
Change temporary debugging code to write a dot file directly.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120171 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/unittests/ADT/IntervalMapTest.cpp b/unittests/ADT/IntervalMapTest.cpp
index d4b2f52b..36476a4 100644
--- a/unittests/ADT/IntervalMapTest.cpp
+++ b/unittests/ADT/IntervalMapTest.cpp
@@ -15,6 +15,7 @@
namespace {
typedef IntervalMap<unsigned, unsigned> UUMap;
+typedef IntervalMap<unsigned, unsigned, 4> UU4Map;
// Empty map tests
TEST(IntervalMapTest, EmptyMap) {
@@ -373,4 +374,54 @@
EXPECT_TRUE(map.begin() == map.end());
}
+// Branched, high, non-coalescing tests.
+TEST(IntervalMapTest, Branched2) {
+ UU4Map::Allocator allocator;
+ UU4Map map(allocator);
+
+ // Insert enough intervals to force a height >= 2 tree.
+ for (unsigned i = 1; i < 1000; ++i)
+ map.insert(10*i, 10*i+5, i);
+
+ // Tree limits.
+ EXPECT_FALSE(map.empty());
+ EXPECT_EQ(10u, map.start());
+ EXPECT_EQ(9995u, map.stop());
+
+ // Tree lookup.
+ for (unsigned i = 1; i < 1000; ++i) {
+ EXPECT_EQ(0u, map.lookup(10*i-1));
+ EXPECT_EQ(i, map.lookup(10*i));
+ EXPECT_EQ(i, map.lookup(10*i+5));
+ EXPECT_EQ(0u, map.lookup(10*i+6));
+ }
+
+ // Forward iteration.
+ UU4Map::iterator I = map.begin();
+ for (unsigned i = 1; i < 1000; ++i) {
+ ASSERT_TRUE(I.valid());
+ EXPECT_EQ(10*i, I.start());
+ EXPECT_EQ(10*i+5, I.stop());
+ EXPECT_EQ(i, *I);
+ ++I;
+ }
+ EXPECT_FALSE(I.valid());
+ EXPECT_TRUE(I == map.end());
+
+ // Backwards iteration.
+ for (unsigned i = 999; i; --i) {
+ --I;
+ ASSERT_TRUE(I.valid());
+ EXPECT_EQ(10*i, I.start());
+ EXPECT_EQ(10*i+5, I.stop());
+ EXPECT_EQ(i, *I);
+ }
+ EXPECT_TRUE(I == map.begin());
+
+ // Test clear() on branched map.
+ map.clear();
+ EXPECT_TRUE(map.empty());
+ EXPECT_TRUE(map.begin() == map.end());
+}
+
} // namespace