From b0b7214fc90febbbe71e1e989130194ce2b70a36 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Sat, 27 Nov 2010 21:12:36 +0000 Subject: 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 --- unittests/ADT/IntervalMapTest.cpp | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) (limited to 'unittests/ADT/IntervalMapTest.cpp') 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 -- cgit v1.2.3