From b47bd52a30333e20c564ae72cd7466a0907bc9c5 Mon Sep 17 00:00:00 2001 From: Pavel Labath Date: Fri, 21 Dec 2018 13:04:34 +0000 Subject: [ADT] IntervalMap: add overlaps(a, b) method Summary: This function checks whether the mappings in the interval map overlap with the given range [a;b]. The motivation is to enable checking for overlap before inserting a new interval into the map. Reviewers: vsk, dblaikie Subscribers: dexonsmith, kristina, llvm-commits Differential Revision: https://reviews.llvm.org/D55760 llvm-svn: 349898 --- llvm/unittests/ADT/IntervalMapTest.cpp | 44 ++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) (limited to 'llvm/unittests/ADT') diff --git a/llvm/unittests/ADT/IntervalMapTest.cpp b/llvm/unittests/ADT/IntervalMapTest.cpp index 11f13752f31..513c063a7b6 100644 --- a/llvm/unittests/ADT/IntervalMapTest.cpp +++ b/llvm/unittests/ADT/IntervalMapTest.cpp @@ -611,6 +611,50 @@ TEST(IntervalMapTest, RandomCoalescing) { } +TEST(IntervalMapTest, Overlaps) { + UUMap::Allocator allocator; + UUMap map(allocator); + map.insert(10, 20, 0); + map.insert(30, 40, 0); + map.insert(50, 60, 0); + + EXPECT_FALSE(map.overlaps(0, 9)); + EXPECT_TRUE(map.overlaps(0, 10)); + EXPECT_TRUE(map.overlaps(0, 15)); + EXPECT_TRUE(map.overlaps(0, 25)); + EXPECT_TRUE(map.overlaps(0, 45)); + EXPECT_TRUE(map.overlaps(10, 45)); + EXPECT_TRUE(map.overlaps(30, 45)); + EXPECT_TRUE(map.overlaps(35, 36)); + EXPECT_TRUE(map.overlaps(40, 45)); + EXPECT_FALSE(map.overlaps(45, 45)); + EXPECT_TRUE(map.overlaps(60, 60)); + EXPECT_TRUE(map.overlaps(60, 66)); + EXPECT_FALSE(map.overlaps(66, 66)); +} + +TEST(IntervalMapTest, OverlapsHalfOpen) { + UUHalfOpenMap::Allocator allocator; + UUHalfOpenMap map(allocator); + map.insert(10, 20, 0); + map.insert(30, 40, 0); + map.insert(50, 60, 0); + + EXPECT_FALSE(map.overlaps(0, 9)); + EXPECT_FALSE(map.overlaps(0, 10)); + EXPECT_TRUE(map.overlaps(0, 15)); + EXPECT_TRUE(map.overlaps(0, 25)); + EXPECT_TRUE(map.overlaps(0, 45)); + EXPECT_TRUE(map.overlaps(10, 45)); + EXPECT_TRUE(map.overlaps(30, 45)); + EXPECT_TRUE(map.overlaps(35, 36)); + EXPECT_FALSE(map.overlaps(40, 45)); + EXPECT_FALSE(map.overlaps(45, 46)); + EXPECT_FALSE(map.overlaps(60, 61)); + EXPECT_FALSE(map.overlaps(60, 66)); + EXPECT_FALSE(map.overlaps(66, 67)); +} + TEST(IntervalMapOverlapsTest, SmallMaps) { typedef IntervalMapOverlaps UUOverlaps; UUMap::Allocator allocator; -- cgit v1.2.3