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(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 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
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(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
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(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
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 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
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(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 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
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(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