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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120226 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 24 insertions, 0 deletions

diff --git a/unittests/ADT/IntervalMapTest.cpp b/unittests/ADT/IntervalMapTest.cpp
index 36476a4cad..c065362135 100644
--- a/unittests/ADT/IntervalMapTest.cpp
+++ b/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