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;
18 typedef IntervalMap<unsigned, unsigned, 4> UU4Map;
21 TEST(IntervalMapTest, EmptyMap) {
22 UUMap::Allocator allocator;
24 EXPECT_TRUE(map.empty());
26 // Lookup on empty map.
27 EXPECT_EQ(0u, map.lookup(0));
28 EXPECT_EQ(7u, map.lookup(0, 7));
29 EXPECT_EQ(0u, map.lookup(~0u-1));
30 EXPECT_EQ(7u, map.lookup(~0u-1, 7));
33 EXPECT_TRUE(map.begin() == map.begin());
34 EXPECT_TRUE(map.begin() == map.end());
35 EXPECT_TRUE(map.end() == map.end());
36 EXPECT_FALSE(map.begin() != map.begin());
37 EXPECT_FALSE(map.begin() != map.end());
38 EXPECT_FALSE(map.end() != map.end());
39 EXPECT_FALSE(map.begin().valid());
40 EXPECT_FALSE(map.end().valid());
41 UUMap::iterator I = map.begin();
42 EXPECT_FALSE(I.valid());
43 EXPECT_TRUE(I == map.end());
46 // Single entry map tests
47 TEST(IntervalMapTest, SingleEntryMap) {
48 UUMap::Allocator allocator;
50 map.insert(100, 150, 1);
51 EXPECT_FALSE(map.empty());
53 // Lookup around interval.
54 EXPECT_EQ(0u, map.lookup(0));
55 EXPECT_EQ(0u, map.lookup(99));
56 EXPECT_EQ(1u, map.lookup(100));
57 EXPECT_EQ(1u, map.lookup(101));
58 EXPECT_EQ(1u, map.lookup(125));
59 EXPECT_EQ(1u, map.lookup(149));
60 EXPECT_EQ(1u, map.lookup(150));
61 EXPECT_EQ(0u, map.lookup(151));
62 EXPECT_EQ(0u, map.lookup(200));
63 EXPECT_EQ(0u, map.lookup(~0u-1));
66 EXPECT_TRUE(map.begin() == map.begin());
67 EXPECT_FALSE(map.begin() == map.end());
68 EXPECT_TRUE(map.end() == map.end());
69 EXPECT_TRUE(map.begin().valid());
70 EXPECT_FALSE(map.end().valid());
73 UUMap::iterator I = map.begin();
74 ASSERT_TRUE(I.valid());
75 EXPECT_EQ(100u, I.start());
76 EXPECT_EQ(150u, I.stop());
77 EXPECT_EQ(1u, I.value());
81 EXPECT_FALSE(I.valid());
82 EXPECT_FALSE(I == map.begin());
83 EXPECT_TRUE(I == map.end());
87 ASSERT_TRUE(I.valid());
88 EXPECT_EQ(100u, I.start());
89 EXPECT_EQ(150u, I.stop());
90 EXPECT_EQ(1u, I.value());
91 EXPECT_TRUE(I == map.begin());
92 EXPECT_FALSE(I == map.end());
95 // Flat coalescing tests.
96 TEST(IntervalMapTest, RootCoalescing) {
97 UUMap::Allocator allocator;
99 map.insert(100, 150, 1);
101 // Coalesce from the left.
102 map.insert(90, 99, 1);
103 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
104 EXPECT_EQ(90u, map.start());
105 EXPECT_EQ(150u, map.stop());
108 map.insert(80, 100, 1);
109 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
110 EXPECT_EQ(80u, map.start());
111 EXPECT_EQ(150u, map.stop());
114 map.insert(100, 130, 1);
115 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
116 EXPECT_EQ(80u, map.start());
117 EXPECT_EQ(150u, map.stop());
120 map.insert(70, 160, 1);
121 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
122 EXPECT_EQ(70u, map.start());
123 EXPECT_EQ(160u, map.stop());
126 map.insert(80, 170, 1);
127 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
128 EXPECT_EQ(70u, map.start());
129 EXPECT_EQ(170u, map.stop());
131 // Coalesce from the right.
132 map.insert(170, 200, 1);
133 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
134 EXPECT_EQ(70u, map.start());
135 EXPECT_EQ(200u, map.stop());
137 // Non-coalesce from the left.
138 map.insert(60, 69, 2);
139 EXPECT_EQ(2, std::distance(map.begin(), map.end()));
140 EXPECT_EQ(60u, map.start());
141 EXPECT_EQ(200u, map.stop());
142 EXPECT_EQ(2u, map.lookup(69));
143 EXPECT_EQ(1u, map.lookup(70));
145 UUMap::iterator I = map.begin();
146 EXPECT_EQ(60u, I.start());
147 EXPECT_EQ(69u, I.stop());
148 EXPECT_EQ(2u, I.value());
150 EXPECT_EQ(70u, I.start());
151 EXPECT_EQ(200u, I.stop());
152 EXPECT_EQ(1u, I.value());
154 EXPECT_FALSE(I.valid());
156 // Non-coalesce from the right.
157 map.insert(201, 210, 2);
158 EXPECT_EQ(3, std::distance(map.begin(), map.end()));
159 EXPECT_EQ(60u, map.start());
160 EXPECT_EQ(210u, map.stop());
161 EXPECT_EQ(2u, map.lookup(201));
162 EXPECT_EQ(1u, map.lookup(200));
165 // Flat multi-coalescing tests.
166 TEST(IntervalMapTest, RootMultiCoalescing) {
167 UUMap::Allocator allocator;
168 UUMap map(allocator);
169 map.insert(140, 150, 1);
170 map.insert(160, 170, 1);
171 map.insert(100, 110, 1);
172 map.insert(120, 130, 1);
173 EXPECT_EQ(4, std::distance(map.begin(), map.end()));
174 EXPECT_EQ(100u, map.start());
175 EXPECT_EQ(170u, map.stop());
178 UUMap::iterator I = map.begin();
179 EXPECT_EQ(100u, I.start());
180 EXPECT_EQ(110u, I.stop());
182 EXPECT_EQ(120u, I.start());
183 EXPECT_EQ(130u, I.stop());
185 EXPECT_EQ(140u, I.start());
186 EXPECT_EQ(150u, I.stop());
188 EXPECT_EQ(160u, I.start());
189 EXPECT_EQ(170u, I.stop());
191 EXPECT_FALSE(I.valid());
194 // Coalesce left with followers.
195 // [100;110] [120;130] [140;150] [160;170]
196 map.insert(111, 115, 1);
198 ASSERT_TRUE(I.valid());
199 EXPECT_EQ(100u, I.start());
200 EXPECT_EQ(115u, I.stop());
202 ASSERT_TRUE(I.valid());
203 EXPECT_EQ(120u, I.start());
204 EXPECT_EQ(130u, I.stop());
206 ASSERT_TRUE(I.valid());
207 EXPECT_EQ(140u, I.start());
208 EXPECT_EQ(150u, I.stop());
210 ASSERT_TRUE(I.valid());
211 EXPECT_EQ(160u, I.start());
212 EXPECT_EQ(170u, I.stop());
214 EXPECT_FALSE(I.valid());
216 // Coalesce right with followers.
217 // [100;115] [120;130] [140;150] [160;170]
218 map.insert(135, 139, 1);
220 ASSERT_TRUE(I.valid());
221 EXPECT_EQ(100u, I.start());
222 EXPECT_EQ(115u, I.stop());
224 ASSERT_TRUE(I.valid());
225 EXPECT_EQ(120u, I.start());
226 EXPECT_EQ(130u, I.stop());
228 ASSERT_TRUE(I.valid());
229 EXPECT_EQ(135u, I.start());
230 EXPECT_EQ(150u, I.stop());
232 ASSERT_TRUE(I.valid());
233 EXPECT_EQ(160u, I.start());
234 EXPECT_EQ(170u, I.stop());
236 EXPECT_FALSE(I.valid());
238 // Coalesce left and right with followers.
239 // [100;115] [120;130] [135;150] [160;170]
240 map.insert(131, 134, 1);
242 ASSERT_TRUE(I.valid());
243 EXPECT_EQ(100u, I.start());
244 EXPECT_EQ(115u, I.stop());
246 ASSERT_TRUE(I.valid());
247 EXPECT_EQ(120u, I.start());
248 EXPECT_EQ(150u, I.stop());
250 ASSERT_TRUE(I.valid());
251 EXPECT_EQ(160u, I.start());
252 EXPECT_EQ(170u, I.stop());
254 EXPECT_FALSE(I.valid());
256 // Coalesce multiple with overlap right.
257 // [100;115] [120;150] [160;170]
258 map.insert(116, 165, 1);
260 ASSERT_TRUE(I.valid());
261 EXPECT_EQ(100u, I.start());
262 EXPECT_EQ(170u, I.stop());
264 EXPECT_FALSE(I.valid());
266 // Coalesce multiple with overlap left
268 map.insert(180, 190, 1);
269 map.insert(200, 210, 1);
270 map.insert(220, 230, 1);
271 // [100;170] [180;190] [200;210] [220;230]
272 map.insert(160, 199, 1);
274 ASSERT_TRUE(I.valid());
275 EXPECT_EQ(100u, I.start());
276 EXPECT_EQ(210u, I.stop());
278 ASSERT_TRUE(I.valid());
279 EXPECT_EQ(220u, I.start());
280 EXPECT_EQ(230u, I.stop());
282 EXPECT_FALSE(I.valid());
284 // Overwrite 2 from gap to gap.
285 // [100;210] [220;230]
286 map.insert(50, 250, 1);
288 ASSERT_TRUE(I.valid());
289 EXPECT_EQ(50u, I.start());
290 EXPECT_EQ(250u, I.stop());
292 EXPECT_FALSE(I.valid());
294 // Coalesce at end of full root.
296 map.insert(260, 270, 1);
297 map.insert(280, 290, 1);
298 map.insert(300, 310, 1);
299 // [50;250] [260;270] [280;290] [300;310]
300 map.insert(311, 320, 1);
302 ASSERT_TRUE(I.valid());
303 EXPECT_EQ(50u, I.start());
304 EXPECT_EQ(250u, I.stop());
306 ASSERT_TRUE(I.valid());
307 EXPECT_EQ(260u, I.start());
308 EXPECT_EQ(270u, I.stop());
310 ASSERT_TRUE(I.valid());
311 EXPECT_EQ(280u, I.start());
312 EXPECT_EQ(290u, I.stop());
314 ASSERT_TRUE(I.valid());
315 EXPECT_EQ(300u, I.start());
316 EXPECT_EQ(320u, I.stop());
318 EXPECT_FALSE(I.valid());
320 // Test clear() on non-branched map.
322 EXPECT_TRUE(map.empty());
323 EXPECT_TRUE(map.begin() == map.end());
326 // Branched, non-coalescing tests.
327 TEST(IntervalMapTest, Branched) {
328 UUMap::Allocator allocator;
329 UUMap map(allocator);
331 // Insert enough intervals to force a branched tree.
332 // This creates 9 leaf nodes with 11 elements each, tree height = 1.
333 for (unsigned i = 1; i < 100; ++i)
334 map.insert(10*i, 10*i+5, i);
337 EXPECT_FALSE(map.empty());
338 EXPECT_EQ(10u, map.start());
339 EXPECT_EQ(995u, map.stop());
342 for (unsigned i = 1; i < 100; ++i) {
343 EXPECT_EQ(0u, map.lookup(10*i-1));
344 EXPECT_EQ(i, map.lookup(10*i));
345 EXPECT_EQ(i, map.lookup(10*i+5));
346 EXPECT_EQ(0u, map.lookup(10*i+6));
349 // Forward iteration.
350 UUMap::iterator I = map.begin();
351 for (unsigned i = 1; i < 100; ++i) {
352 ASSERT_TRUE(I.valid());
353 EXPECT_EQ(10*i, I.start());
354 EXPECT_EQ(10*i+5, I.stop());
358 EXPECT_FALSE(I.valid());
359 EXPECT_TRUE(I == map.end());
361 // Backwards iteration.
362 for (unsigned i = 99; i; --i) {
364 ASSERT_TRUE(I.valid());
365 EXPECT_EQ(10*i, I.start());
366 EXPECT_EQ(10*i+5, I.stop());
369 EXPECT_TRUE(I == map.begin());
371 // Test clear() on branched map.
373 EXPECT_TRUE(map.empty());
374 EXPECT_TRUE(map.begin() == map.end());
377 // Branched, high, non-coalescing tests.
378 TEST(IntervalMapTest, Branched2) {
379 UU4Map::Allocator allocator;
380 UU4Map map(allocator);
382 // Insert enough intervals to force a height >= 2 tree.
383 for (unsigned i = 1; i < 1000; ++i)
384 map.insert(10*i, 10*i+5, i);
387 EXPECT_FALSE(map.empty());
388 EXPECT_EQ(10u, map.start());
389 EXPECT_EQ(9995u, map.stop());
392 for (unsigned i = 1; i < 1000; ++i) {
393 EXPECT_EQ(0u, map.lookup(10*i-1));
394 EXPECT_EQ(i, map.lookup(10*i));
395 EXPECT_EQ(i, map.lookup(10*i+5));
396 EXPECT_EQ(0u, map.lookup(10*i+6));
399 // Forward iteration.
400 UU4Map::iterator I = map.begin();
401 for (unsigned i = 1; i < 1000; ++i) {
402 ASSERT_TRUE(I.valid());
403 EXPECT_EQ(10*i, I.start());
404 EXPECT_EQ(10*i+5, I.stop());
408 EXPECT_FALSE(I.valid());
409 EXPECT_TRUE(I == map.end());
411 // Backwards iteration.
412 for (unsigned i = 999; i; --i) {
414 ASSERT_TRUE(I.valid());
415 EXPECT_EQ(10*i, I.start());
416 EXPECT_EQ(10*i+5, I.stop());
419 EXPECT_TRUE(I == map.begin());
421 // Test clear() on branched map.
423 EXPECT_TRUE(map.empty());
424 EXPECT_TRUE(map.begin() == map.end());