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
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(KS: 7, KE: 8, V: 42);
32
33 EXPECT_FALSE(M.empty());
34 EXPECT_EQ(std::next(x: M.begin()), M.end());
35 EXPECT_EQ(M.find(K: 7), M.begin());
36 EXPECT_EQ(M.find(K: 8), M.end());
37 EXPECT_EQ(M.lookup(K: 7), 42U);
38 EXPECT_EQ(M.lookup(K: 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 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(KS: 7, KE: 8, V: 42);
49 M1.insert(KS: 8, KE: 9, V: 42);
50
51 EXPECT_FALSE(M1.empty());
52 EXPECT_EQ(std::next(x: M1.begin()), M1.end()); // Should see just one range.
53 EXPECT_EQ(M1.find(K: 7), M1.find(K: 8)); // 7 and 8 should point to same range.
54 EXPECT_EQ(M1.lookup(K: 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(KS: 7, KE: 8, V: 42);
61 M2.insert(KS: 8, KE: 9, V: 7);
62
63 EXPECT_FALSE(M2.empty());
64 EXPECT_EQ(std::next(x: std::next(x: M2.begin())), M2.end()); // Expect two ranges.
65 EXPECT_NE(M2.find(K: 7), M2.find(K: 8)); // 7 and 8 should be different ranges.
66 EXPECT_EQ(M2.lookup(K: 7), 42U); // Keys 7 and 8 should map to different values.
67 EXPECT_EQ(M2.lookup(K: 8), 7U);
68}
69
70TEST(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(KS: 8, KE: 9, V: 42);
78 M1.insert(KS: 7, KE: 8, V: 42);
79
80 EXPECT_FALSE(M1.empty());
81 EXPECT_EQ(std::next(x: M1.begin()), M1.end()); // Should see just one range.
82 EXPECT_EQ(M1.find(K: 7), M1.find(K: 8)); // 7 and 8 should point to same range.
83 EXPECT_EQ(M1.lookup(K: 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(KS: 8, KE: 9, V: 42);
90 M2.insert(KS: 7, KE: 8, V: 7);
91
92 EXPECT_FALSE(M2.empty());
93 EXPECT_EQ(std::next(x: std::next(x: M2.begin())), M2.end()); // Expect two ranges.
94 EXPECT_EQ(M2.lookup(K: 7), 7U); // Keys 7 and 8 should map to different values.
95 EXPECT_EQ(M2.lookup(K: 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 ranges
103 // when values are equal.
104 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M1;
105
106 M1.insert(KS: 7, KE: 8, V: 42);
107 M1.insert(KS: 9, KE: 10, V: 42);
108
109 // Check no coalescing yet.
110 EXPECT_NE(M1.find(K: 7), M1.find(K: 9));
111
112 // Insert a 3rd range to trigger coalescing on both sides.
113 M1.insert(KS: 8, KE: 9, V: 42);
114
115 EXPECT_FALSE(M1.empty());
116 EXPECT_EQ(std::next(x: M1.begin()), M1.end()); // Should see just one range.
117 EXPECT_EQ(M1.find(K: 7), M1.find(K: 8)); // 7, 8, and 9 should point to same range.
118 EXPECT_EQ(M1.find(K: 8), M1.find(K: 9));
119 EXPECT_EQ(M1.lookup(K: 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(KS: 7, KE: 8, V: 42);
126 M2.insert(KS: 8, KE: 9, V: 7);
127 M2.insert(KS: 9, KE: 10, V: 42);
128
129 EXPECT_FALSE(M2.empty());
130 // Expect three ranges.
131 EXPECT_EQ(std::next(x: std::next(x: std::next(x: M2.begin()))), M2.end());
132 EXPECT_NE(M2.find(K: 7), M2.find(K: 8)); // All keys should map to different ranges.
133 EXPECT_NE(M2.find(K: 8), M2.find(K: 9));
134 EXPECT_EQ(M2.lookup(K: 7), 42U); // Key 7, 8, and 9 should map to different vals.
135 EXPECT_EQ(M2.lookup(K: 8), 7U);
136 EXPECT_EQ(M2.lookup(K: 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(KS: 7, KE: 10, V: 42);
144 EXPECT_FALSE(M.empty());
145 M.erase(KS: 7, KE: 10);
146 EXPECT_TRUE(M.empty());
147}
148
149TEST(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(KS: 7, KE: 10, V: 42);
155 EXPECT_FALSE(M.empty());
156 M.erase(KS: 9, KE: 10);
157 EXPECT_EQ(std::next(x: 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 the
164 // residual range in-place.
165 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;
166
167 M.insert(KS: 7, KE: 10, V: 42);
168 EXPECT_FALSE(M.empty());
169 M.erase(KS: 7, KE: 8);
170 EXPECT_EQ(std::next(x: 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 and
177 // trailing residual subranges in-place.
178 IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;
179
180 M.insert(KS: 7, KE: 10, V: 42);
181 EXPECT_FALSE(M.empty());
182 M.erase(KS: 8, KE: 9);
183 EXPECT_EQ(std::next(x: std::next(x: 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(x: M.begin())->first.first, 9U);
187 EXPECT_EQ(std::next(x: M.begin())->first.second, 10U);
188}
189
190TEST(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(KS: 7, KE: 8, V: S());
199
200 EXPECT_FALSE(M.empty());
201 EXPECT_EQ(std::next(x: M.begin()), M.end());
202 EXPECT_EQ(M.find(K: 7), M.begin());
203 EXPECT_EQ(M.find(K: 8), M.end());
204}
205

source code of compiler-rt/lib/orc/tests/unit/interval_map_test.cpp