1 //===---- ADT/IntervalMapTest.cpp - IntervalMap unit tests ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/ADT/IntervalMap.h"
11 #include "gtest/gtest.h"
17 typedef IntervalMap<unsigned, unsigned> UUMap;
20 TEST(IntervalMapTest, EmptyMap) {
21 UUMap::Allocator allocator;
23 EXPECT_TRUE(map.empty());
25 // Lookup on empty map.
26 EXPECT_EQ(0u, map.lookup(0));
27 EXPECT_EQ(7u, map.lookup(0, 7));
28 EXPECT_EQ(0u, map.lookup(~0u-1));
29 EXPECT_EQ(7u, map.lookup(~0u-1, 7));
32 EXPECT_TRUE(map.begin() == map.begin());
33 EXPECT_TRUE(map.begin() == map.end());
34 EXPECT_TRUE(map.end() == map.end());
35 EXPECT_FALSE(map.begin() != map.begin());
36 EXPECT_FALSE(map.begin() != map.end());
37 EXPECT_FALSE(map.end() != map.end());
38 EXPECT_FALSE(map.begin().valid());
39 EXPECT_FALSE(map.end().valid());
40 UUMap::iterator I = map.begin();
41 EXPECT_FALSE(I.valid());
42 EXPECT_TRUE(I == map.end());
45 // Single entry map tests
46 TEST(IntervalMapTest, SingleEntryMap) {
47 UUMap::Allocator allocator;
49 map.insert(100, 150, 1);
50 EXPECT_FALSE(map.empty());
52 // Lookup around interval.
53 EXPECT_EQ(0u, map.lookup(0));
54 EXPECT_EQ(0u, map.lookup(99));
55 EXPECT_EQ(1u, map.lookup(100));
56 EXPECT_EQ(1u, map.lookup(101));
57 EXPECT_EQ(1u, map.lookup(125));
58 EXPECT_EQ(1u, map.lookup(149));
59 EXPECT_EQ(1u, map.lookup(150));
60 EXPECT_EQ(0u, map.lookup(151));
61 EXPECT_EQ(0u, map.lookup(200));
62 EXPECT_EQ(0u, map.lookup(~0u-1));
65 EXPECT_TRUE(map.begin() == map.begin());
66 EXPECT_FALSE(map.begin() == map.end());
67 EXPECT_TRUE(map.end() == map.end());
68 EXPECT_TRUE(map.begin().valid());
69 EXPECT_FALSE(map.end().valid());
72 UUMap::iterator I = map.begin();
73 ASSERT_TRUE(I.valid());
74 EXPECT_EQ(100u, I.start());
75 EXPECT_EQ(150u, I.stop());
76 EXPECT_EQ(1u, I.value());
80 EXPECT_FALSE(I.valid());
81 EXPECT_FALSE(I == map.begin());
82 EXPECT_TRUE(I == map.end());
86 ASSERT_TRUE(I.valid());
87 EXPECT_EQ(100u, I.start());
88 EXPECT_EQ(150u, I.stop());
89 EXPECT_EQ(1u, I.value());
90 EXPECT_TRUE(I == map.begin());
91 EXPECT_FALSE(I == map.end());
94 // Flat coalescing tests.
95 TEST(IntervalMapTest, RootCoalescing) {
96 UUMap::Allocator allocator;
98 map.insert(100, 150, 1);
100 // Coalesce from the left.
101 map.insert(90, 99, 1);
102 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
103 EXPECT_EQ(90u, map.start());
104 EXPECT_EQ(150u, map.stop());
107 map.insert(80, 100, 1);
108 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
109 EXPECT_EQ(80u, map.start());
110 EXPECT_EQ(150u, map.stop());
113 map.insert(100, 130, 1);
114 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
115 EXPECT_EQ(80u, map.start());
116 EXPECT_EQ(150u, map.stop());
119 map.insert(70, 160, 1);
120 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
121 EXPECT_EQ(70u, map.start());
122 EXPECT_EQ(160u, map.stop());
125 map.insert(80, 170, 1);
126 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
127 EXPECT_EQ(70u, map.start());
128 EXPECT_EQ(170u, map.stop());
130 // Coalesce from the right.
131 map.insert(170, 200, 1);
132 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
133 EXPECT_EQ(70u, map.start());
134 EXPECT_EQ(200u, map.stop());
136 // Non-coalesce from the left.
137 map.insert(60, 69, 2);
138 EXPECT_EQ(2, std::distance(map.begin(), map.end()));
139 EXPECT_EQ(60u, map.start());
140 EXPECT_EQ(200u, map.stop());
141 EXPECT_EQ(2u, map.lookup(69));
142 EXPECT_EQ(1u, map.lookup(70));
144 UUMap::iterator I = map.begin();
145 EXPECT_EQ(60u, I.start());
146 EXPECT_EQ(69u, I.stop());
147 EXPECT_EQ(2u, I.value());
149 EXPECT_EQ(70u, I.start());
150 EXPECT_EQ(200u, I.stop());
151 EXPECT_EQ(1u, I.value());
153 EXPECT_FALSE(I.valid());
155 // Non-coalesce from the right.
156 map.insert(201, 210, 2);
157 EXPECT_EQ(3, std::distance(map.begin(), map.end()));
158 EXPECT_EQ(60u, map.start());
159 EXPECT_EQ(210u, map.stop());
160 EXPECT_EQ(2u, map.lookup(201));
161 EXPECT_EQ(1u, map.lookup(200));
164 // Flat multi-coalescing tests.
165 TEST(IntervalMapTest, RootMultiCoalescing) {
166 UUMap::Allocator allocator;
167 UUMap map(allocator);
168 map.insert(140, 150, 1);
169 map.insert(160, 170, 1);
170 map.insert(100, 110, 1);
171 map.insert(120, 130, 1);
172 EXPECT_EQ(4, std::distance(map.begin(), map.end()));
173 EXPECT_EQ(100u, map.start());
174 EXPECT_EQ(170u, map.stop());
177 UUMap::iterator I = map.begin();
178 EXPECT_EQ(100u, I.start());
179 EXPECT_EQ(110u, I.stop());
181 EXPECT_EQ(120u, I.start());
182 EXPECT_EQ(130u, I.stop());
184 EXPECT_EQ(140u, I.start());
185 EXPECT_EQ(150u, I.stop());
187 EXPECT_EQ(160u, I.start());
188 EXPECT_EQ(170u, I.stop());
190 EXPECT_FALSE(I.valid());
193 // Coalesce left with followers.
194 // [100;110] [120;130] [140;150] [160;170]
195 map.insert(111, 115, 1);
197 ASSERT_TRUE(I.valid());
198 EXPECT_EQ(100u, I.start());
199 EXPECT_EQ(115u, I.stop());
201 ASSERT_TRUE(I.valid());
202 EXPECT_EQ(120u, I.start());
203 EXPECT_EQ(130u, I.stop());
205 ASSERT_TRUE(I.valid());
206 EXPECT_EQ(140u, I.start());
207 EXPECT_EQ(150u, I.stop());
209 ASSERT_TRUE(I.valid());
210 EXPECT_EQ(160u, I.start());
211 EXPECT_EQ(170u, I.stop());
213 EXPECT_FALSE(I.valid());
215 // Coalesce right with followers.
216 // [100;115] [120;130] [140;150] [160;170]
217 map.insert(135, 139, 1);
219 ASSERT_TRUE(I.valid());
220 EXPECT_EQ(100u, I.start());
221 EXPECT_EQ(115u, I.stop());
223 ASSERT_TRUE(I.valid());
224 EXPECT_EQ(120u, I.start());
225 EXPECT_EQ(130u, I.stop());
227 ASSERT_TRUE(I.valid());
228 EXPECT_EQ(135u, I.start());
229 EXPECT_EQ(150u, I.stop());
231 ASSERT_TRUE(I.valid());
232 EXPECT_EQ(160u, I.start());
233 EXPECT_EQ(170u, I.stop());
235 EXPECT_FALSE(I.valid());
237 // Coalesce left and right with followers.
238 // [100;115] [120;130] [135;150] [160;170]
239 map.insert(131, 134, 1);
241 ASSERT_TRUE(I.valid());
242 EXPECT_EQ(100u, I.start());
243 EXPECT_EQ(115u, I.stop());
245 ASSERT_TRUE(I.valid());
246 EXPECT_EQ(120u, I.start());
247 EXPECT_EQ(150u, I.stop());
249 ASSERT_TRUE(I.valid());
250 EXPECT_EQ(160u, I.start());
251 EXPECT_EQ(170u, I.stop());
253 EXPECT_FALSE(I.valid());
255 // Coalesce multiple with overlap right.
256 // [100;115] [120;150] [160;170]
257 map.insert(116, 165, 1);
259 ASSERT_TRUE(I.valid());
260 EXPECT_EQ(100u, I.start());
261 EXPECT_EQ(170u, I.stop());
263 EXPECT_FALSE(I.valid());
265 // Coalesce multiple with overlap left
267 map.insert(180, 190, 1);
268 map.insert(200, 210, 1);
269 map.insert(220, 230, 1);
270 // [100;170] [180;190] [200;210] [220;230]
271 map.insert(160, 199, 1);
273 ASSERT_TRUE(I.valid());
274 EXPECT_EQ(100u, I.start());
275 EXPECT_EQ(210u, I.stop());
277 ASSERT_TRUE(I.valid());
278 EXPECT_EQ(220u, I.start());
279 EXPECT_EQ(230u, I.stop());
281 EXPECT_FALSE(I.valid());
283 // Overwrite 2 from gap to gap.
284 // [100;210] [220;230]
285 map.insert(50, 250, 1);
287 ASSERT_TRUE(I.valid());
288 EXPECT_EQ(50u, I.start());
289 EXPECT_EQ(250u, I.stop());
291 EXPECT_FALSE(I.valid());
293 // Coalesce at end of full root.
295 map.insert(260, 270, 1);
296 map.insert(280, 290, 1);
297 map.insert(300, 310, 1);
298 // [50;250] [260;270] [280;290] [300;310]
299 map.insert(311, 320, 1);
301 ASSERT_TRUE(I.valid());
302 EXPECT_EQ(50u, I.start());
303 EXPECT_EQ(250u, I.stop());
305 ASSERT_TRUE(I.valid());
306 EXPECT_EQ(260u, I.start());
307 EXPECT_EQ(270u, I.stop());
309 ASSERT_TRUE(I.valid());
310 EXPECT_EQ(280u, I.start());
311 EXPECT_EQ(290u, I.stop());
313 ASSERT_TRUE(I.valid());
314 EXPECT_EQ(300u, I.start());
315 EXPECT_EQ(320u, I.stop());
317 EXPECT_FALSE(I.valid());
320 // Branched, non-coalescing tests.
321 TEST(IntervalMapTest, Branched) {
322 UUMap::Allocator allocator;
323 UUMap map(allocator);
325 // Insert enough intervals to force a branched tree.
326 // This creates 9 leaf nodes with 11 elements each, tree height = 1.
327 for (unsigned i = 1; i < 100; ++i)
328 map.insert(10*i, 10*i+5, i);
331 EXPECT_FALSE(map.empty());
332 EXPECT_EQ(10u, map.start());
333 EXPECT_EQ(995u, map.stop());
336 for (unsigned i = 1; i < 100; ++i) {
337 EXPECT_EQ(0u, map.lookup(10*i-1));
338 EXPECT_EQ(i, map.lookup(10*i));
339 EXPECT_EQ(i, map.lookup(10*i+5));
340 EXPECT_EQ(0u, map.lookup(10*i+6));
343 // Forward iteration.
344 UUMap::iterator I = map.begin();
345 for (unsigned i = 1; i < 100; ++i) {
346 ASSERT_TRUE(I.valid());
347 EXPECT_EQ(10*i, I.start());
348 EXPECT_EQ(10*i+5, I.stop());
352 EXPECT_FALSE(I.valid());
353 EXPECT_TRUE(I == map.end());