Add test case with randomly ordered insertions, massive coalescing.

Implement iterator::erase() in a simple version that erases nodes when they
become empty, but doesn't try to redistribute elements among siblings for better
packing.

Handle coalescing across leaf nodes which may require erasing entries.

llvm-svn: 120226

1 files changed, 24 insertions, 0 deletions

diff --git a/llvm/unittests/ADT/IntervalMapTest.cpp b/llvm/unittests/ADT/IntervalMapTest.cpp
index 36476a4cad9..c065362135e 100644
--- a/llvm/unittests/ADT/IntervalMapTest.cpp
+++ b/llvm/unittests/ADT/IntervalMapTest.cpp
@@ -424,4 +424,28 @@ TEST(IntervalMapTest, Branched2) {
   EXPECT_TRUE(map.begin() == map.end());
 }
 
+// Random insertions, coalescing to a single interval.
+TEST(IntervalMapTest, RandomCoalescing) {
+  UU4Map::Allocator allocator;
+  UU4Map map(allocator);
+
+  // This is a poor PRNG with maximal period:
+  // x_n = 5 x_{n-1} + 1 mod 2^N
+
+  unsigned x = 100;
+  for (unsigned i = 0; i != 4096; ++i) {
+    map.insert(10*x, 10*x+9, 1);
+    EXPECT_GE(10*x, map.start());
+    EXPECT_LE(10*x+9, map.stop());
+    x = (5*x+1)%4096;
+  }
+
+  // Map should be fully coalesced after that exercise.
+  EXPECT_FALSE(map.empty());
+  EXPECT_EQ(0u, map.start());
+  EXPECT_EQ(40959u, map.stop());
+  EXPECT_EQ(1, std::distance(map.begin(), map.end()));
+
+}
+
 } // namespace