1 //===-- interval_map_test.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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file is a part of the ORC runtime. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "interval_map.h" 14 #include "gtest/gtest.h" 15 16 using namespace __orc_rt; 17 18 TEST(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 27 TEST(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 41 TEST(IntervalMapTest, InsertCoalesceWithPrevious) { 42 // Check that insertions coalesce with previous ranges that share the same 43 // 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 are 57 // 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 70 TEST(IntervalMapTest, InsertCoalesceWithFollowing) { 71 // Check that insertions coalesce with following ranges that share the same 72 // 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 are 86 // 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 98 TEST(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 ranges 103 // 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 are 122 // 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 139 TEST(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 149 TEST(IntervalMapTest, EraseSplittingLeft) { 150 // Check that removal of a trailing subrange succeeds, but leaves the 151 // 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 162 TEST(IntervalMapTest, EraseSplittingRight) { 163 // Check that removal of a leading subrange succeeds, but leaves the 164 // 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 175 TEST(IntervalMapTest, EraseSplittingBoth) { 176 // Check that removal of an interior subrange leaves both the leading and 177 // 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 190 TEST(IntervalMapTest, NonCoalescingMapPermitsNonComparableKeys) { 191 // Test that values that can't be equality-compared are still usable when 192 // 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