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