205 lines · cpp
1//===- IntervalMapTest.cpp ------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file is a part of the ORC runtime.10//11//===----------------------------------------------------------------------===//12 13#include "orc-rt/IntervalMap.h"14#include "gtest/gtest.h"15 16using namespace orc_rt;17 18TEST(IntervalMapTest, DefaultConstructed) {19 // Check that a default-constructed IntervalMap behaves as expected.20 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;21 22 EXPECT_TRUE(M.empty());23 EXPECT_TRUE(M.begin() == M.end());24 EXPECT_TRUE(M.find(0) == M.end());25}26 27TEST(IntervalMapTest, InsertSingleElement) {28 // Check that a map with a single element inserted behaves as expected.29 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;30 31 M.insert(7, 8, 42);32 33 EXPECT_FALSE(M.empty());34 EXPECT_EQ(std::next(M.begin()), M.end());35 EXPECT_EQ(M.find(7), M.begin());36 EXPECT_EQ(M.find(8), M.end());37 EXPECT_EQ(M.lookup(7), 42U);38 EXPECT_EQ(M.lookup(8), 0U); // 8 not present, so should return unsigned().39}40 41TEST(IntervalMapTest, InsertCoalesceWithPrevious) {42 // Check that insertions coalesce with previous ranges that share the same43 // value. Also check that they _don't_ coalesce if the values are different.44 45 // Check that insertion coalesces with previous range when values are equal.46 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M1;47 48 M1.insert(7, 8, 42);49 M1.insert(8, 9, 42);50 51 EXPECT_FALSE(M1.empty());52 EXPECT_EQ(std::next(M1.begin()), M1.end()); // Should see just one range.53 EXPECT_EQ(M1.find(7), M1.find(8)); // 7 and 8 should point to same range.54 EXPECT_EQ(M1.lookup(7), 42U); // Value should be preserved.55 56 // Check that insertion does not coalesce with previous range when values are57 // not equal.58 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M2;59 60 M2.insert(7, 8, 42);61 M2.insert(8, 9, 7);62 63 EXPECT_FALSE(M2.empty());64 EXPECT_EQ(std::next(std::next(M2.begin())), M2.end()); // Expect two ranges.65 EXPECT_NE(M2.find(7), M2.find(8)); // 7 and 8 should be different ranges.66 EXPECT_EQ(M2.lookup(7), 42U); // Keys 7 and 8 should map to different values.67 EXPECT_EQ(M2.lookup(8), 7U);68}69 70TEST(IntervalMapTest, InsertCoalesceWithFollowing) {71 // Check that insertions coalesce with following ranges that share the same72 // value. Also check that they _don't_ coalesce if the values are different.73 74 // Check that insertion coalesces with following range when values are equal.75 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M1;76 77 M1.insert(8, 9, 42);78 M1.insert(7, 8, 42);79 80 EXPECT_FALSE(M1.empty());81 EXPECT_EQ(std::next(M1.begin()), M1.end()); // Should see just one range.82 EXPECT_EQ(M1.find(7), M1.find(8)); // 7 and 8 should point to same range.83 EXPECT_EQ(M1.lookup(7), 42U); // Value should be preserved.84 85 // Check that insertion does not coalesce with previous range when values are86 // not equal.87 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M2;88 89 M2.insert(8, 9, 42);90 M2.insert(7, 8, 7);91 92 EXPECT_FALSE(M2.empty());93 EXPECT_EQ(std::next(std::next(M2.begin())), M2.end()); // Expect two ranges.94 EXPECT_EQ(M2.lookup(7), 7U); // Keys 7 and 8 should map to different values.95 EXPECT_EQ(M2.lookup(8), 42U);96}97 98TEST(IntervalMapTest, InsertCoalesceBoth) {99 // Check that insertions coalesce with ranges on both sides where posssible.100 // Also check that they _don't_ coalesce if the values are different.101 102 // Check that insertion coalesces with both previous and following ranges103 // when values are equal.104 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M1;105 106 M1.insert(7, 8, 42);107 M1.insert(9, 10, 42);108 109 // Check no coalescing yet.110 EXPECT_NE(M1.find(7), M1.find(9));111 112 // Insert a 3rd range to trigger coalescing on both sides.113 M1.insert(8, 9, 42);114 115 EXPECT_FALSE(M1.empty());116 EXPECT_EQ(std::next(M1.begin()), M1.end()); // Should see just one range.117 EXPECT_EQ(M1.find(7), M1.find(8)); // 7, 8, and 9 should point to same range.118 EXPECT_EQ(M1.find(8), M1.find(9));119 EXPECT_EQ(M1.lookup(7), 42U); // Value should be preserved.120 121 // Check that insertion does not coalesce with previous range when values are122 // not equal.123 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M2;124 125 M2.insert(7, 8, 42);126 M2.insert(8, 9, 7);127 M2.insert(9, 10, 42);128 129 EXPECT_FALSE(M2.empty());130 // Expect three ranges.131 EXPECT_EQ(std::next(std::next(std::next(M2.begin()))), M2.end());132 EXPECT_NE(M2.find(7), M2.find(8)); // All keys should map to different ranges.133 EXPECT_NE(M2.find(8), M2.find(9));134 EXPECT_EQ(M2.lookup(7), 42U); // Key 7, 8, and 9 should map to different vals.135 EXPECT_EQ(M2.lookup(8), 7U);136 EXPECT_EQ(M2.lookup(9), 42U);137}138 139TEST(IntervalMapTest, EraseSingleElement) {140 // Check that we can insert and then remove a single range.141 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;142 143 M.insert(7, 10, 42);144 EXPECT_FALSE(M.empty());145 M.erase(7, 10);146 EXPECT_TRUE(M.empty());147}148 149TEST(IntervalMapTest, EraseSplittingLeft) {150 // Check that removal of a trailing subrange succeeds, but leaves the151 // residual range in-place.152 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;153 154 M.insert(7, 10, 42);155 EXPECT_FALSE(M.empty());156 M.erase(9, 10);157 EXPECT_EQ(std::next(M.begin()), M.end());158 EXPECT_EQ(M.begin()->first.first, 7U);159 EXPECT_EQ(M.begin()->first.second, 9U);160}161 162TEST(IntervalMapTest, EraseSplittingRight) {163 // Check that removal of a leading subrange succeeds, but leaves the164 // residual range in-place.165 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;166 167 M.insert(7, 10, 42);168 EXPECT_FALSE(M.empty());169 M.erase(7, 8);170 EXPECT_EQ(std::next(M.begin()), M.end());171 EXPECT_EQ(M.begin()->first.first, 8U);172 EXPECT_EQ(M.begin()->first.second, 10U);173}174 175TEST(IntervalMapTest, EraseSplittingBoth) {176 // Check that removal of an interior subrange leaves both the leading and177 // trailing residual subranges in-place.178 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;179 180 M.insert(7, 10, 42);181 EXPECT_FALSE(M.empty());182 M.erase(8, 9);183 EXPECT_EQ(std::next(std::next(M.begin())), M.end());184 EXPECT_EQ(M.begin()->first.first, 7U);185 EXPECT_EQ(M.begin()->first.second, 8U);186 EXPECT_EQ(std::next(M.begin())->first.first, 9U);187 EXPECT_EQ(std::next(M.begin())->first.second, 10U);188}189 190TEST(IntervalMapTest, NonCoalescingMapPermitsNonComparableKeys) {191 // Test that values that can't be equality-compared are still usable when192 // coalescing is disabled and behave as expected.193 194 struct S {}; // Struct with no equality comparison.195 196 IntervalMap<unsigned, S, IntervalCoalescing::Disabled> M;197 198 M.insert(7, 8, S());199 200 EXPECT_FALSE(M.empty());201 EXPECT_EQ(std::next(M.begin()), M.end());202 EXPECT_EQ(M.find(7), M.begin());203 EXPECT_EQ(M.find(8), M.end());204}205