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, 4> 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());
44 // Default constructor and cross-constness compares.
45 UUMap::const_iterator CI;
50 EXPECT_TRUE(I2 == CI);
53 // Single entry map tests
54 TEST(IntervalMapTest, SingleEntryMap) {
55 UUMap::Allocator allocator;
57 map.insert(100, 150, 1);
58 EXPECT_FALSE(map.empty());
60 // Lookup around interval.
61 EXPECT_EQ(0u, map.lookup(0));
62 EXPECT_EQ(0u, map.lookup(99));
63 EXPECT_EQ(1u, map.lookup(100));
64 EXPECT_EQ(1u, map.lookup(101));
65 EXPECT_EQ(1u, map.lookup(125));
66 EXPECT_EQ(1u, map.lookup(149));
67 EXPECT_EQ(1u, map.lookup(150));
68 EXPECT_EQ(0u, map.lookup(151));
69 EXPECT_EQ(0u, map.lookup(200));
70 EXPECT_EQ(0u, map.lookup(~0u-1));
73 EXPECT_TRUE(map.begin() == map.begin());
74 EXPECT_FALSE(map.begin() == map.end());
75 EXPECT_TRUE(map.end() == map.end());
76 EXPECT_TRUE(map.begin().valid());
77 EXPECT_FALSE(map.end().valid());
80 UUMap::iterator I = map.begin();
81 ASSERT_TRUE(I.valid());
82 EXPECT_EQ(100u, I.start());
83 EXPECT_EQ(150u, I.stop());
84 EXPECT_EQ(1u, I.value());
88 EXPECT_FALSE(I.valid());
89 EXPECT_FALSE(I == map.begin());
90 EXPECT_TRUE(I == map.end());
94 ASSERT_TRUE(I.valid());
95 EXPECT_EQ(100u, I.start());
96 EXPECT_EQ(150u, I.stop());
97 EXPECT_EQ(1u, I.value());
98 EXPECT_TRUE(I == map.begin());
99 EXPECT_FALSE(I == map.end());
103 ASSERT_TRUE(I.valid());
104 EXPECT_EQ(100u, I.start());
105 EXPECT_EQ(150u, I.stop());
106 EXPECT_EQ(2u, I.value());
110 ASSERT_TRUE(I.valid());
111 EXPECT_EQ(0u, I.start());
112 EXPECT_EQ(150u, I.stop());
113 EXPECT_EQ(2u, I.value());
116 ASSERT_TRUE(I.valid());
117 EXPECT_EQ(0u, I.start());
118 EXPECT_EQ(200u, I.stop());
119 EXPECT_EQ(2u, I.value());
121 // Shrink the bounds.
123 ASSERT_TRUE(I.valid());
124 EXPECT_EQ(150u, I.start());
125 EXPECT_EQ(200u, I.stop());
126 EXPECT_EQ(2u, I.value());
129 ASSERT_TRUE(I.valid());
130 EXPECT_EQ(150u, I.start());
131 EXPECT_EQ(160u, I.stop());
132 EXPECT_EQ(2u, I.value());
136 EXPECT_TRUE(map.empty());
137 EXPECT_EQ(0, std::distance(map.begin(), map.end()));
140 // Flat coalescing tests.
141 TEST(IntervalMapTest, RootCoalescing) {
142 UUMap::Allocator allocator;
143 UUMap map(allocator);
144 map.insert(100, 150, 1);
146 // Coalesce from the left.
147 map.insert(90, 99, 1);
148 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
149 EXPECT_EQ(90u, map.start());
150 EXPECT_EQ(150u, map.stop());
152 // Coalesce from the right.
153 map.insert(151, 200, 1);
154 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
155 EXPECT_EQ(90u, map.start());
156 EXPECT_EQ(200u, map.stop());
158 // Non-coalesce from the left.
159 map.insert(60, 89, 2);
160 EXPECT_EQ(2, std::distance(map.begin(), map.end()));
161 EXPECT_EQ(60u, map.start());
162 EXPECT_EQ(200u, map.stop());
163 EXPECT_EQ(2u, map.lookup(89));
164 EXPECT_EQ(1u, map.lookup(90));
166 UUMap::iterator I = map.begin();
167 EXPECT_EQ(60u, I.start());
168 EXPECT_EQ(89u, I.stop());
169 EXPECT_EQ(2u, I.value());
171 EXPECT_EQ(90u, I.start());
172 EXPECT_EQ(200u, I.stop());
173 EXPECT_EQ(1u, I.value());
175 EXPECT_FALSE(I.valid());
177 // Non-coalesce from the right.
178 map.insert(201, 210, 2);
179 EXPECT_EQ(3, std::distance(map.begin(), map.end()));
180 EXPECT_EQ(60u, map.start());
181 EXPECT_EQ(210u, map.stop());
182 EXPECT_EQ(2u, map.lookup(201));
183 EXPECT_EQ(1u, map.lookup(200));
185 // Erase from the left.
187 EXPECT_EQ(2, std::distance(map.begin(), map.end()));
188 EXPECT_EQ(90u, map.start());
189 EXPECT_EQ(210u, map.stop());
191 // Erase from the right.
192 (--map.end()).erase();
193 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
194 EXPECT_EQ(90u, map.start());
195 EXPECT_EQ(200u, map.stop());
197 // Add non-coalescing, then trigger coalescing with setValue.
198 map.insert(80, 89, 2);
199 map.insert(201, 210, 2);
200 EXPECT_EQ(3, std::distance(map.begin(), map.end()));
201 (++map.begin()).setValue(2);
202 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
204 ASSERT_TRUE(I.valid());
205 EXPECT_EQ(80u, I.start());
206 EXPECT_EQ(210u, I.stop());
207 EXPECT_EQ(2u, I.value());
210 // Flat multi-coalescing tests.
211 TEST(IntervalMapTest, RootMultiCoalescing) {
212 UUMap::Allocator allocator;
213 UUMap map(allocator);
214 map.insert(140, 150, 1);
215 map.insert(160, 170, 1);
216 map.insert(100, 110, 1);
217 map.insert(120, 130, 1);
218 EXPECT_EQ(4, std::distance(map.begin(), map.end()));
219 EXPECT_EQ(100u, map.start());
220 EXPECT_EQ(170u, map.stop());
223 UUMap::iterator I = map.begin();
224 EXPECT_EQ(100u, I.start());
225 EXPECT_EQ(110u, I.stop());
227 EXPECT_EQ(120u, I.start());
228 EXPECT_EQ(130u, I.stop());
230 EXPECT_EQ(140u, I.start());
231 EXPECT_EQ(150u, I.stop());
233 EXPECT_EQ(160u, I.start());
234 EXPECT_EQ(170u, I.stop());
236 EXPECT_FALSE(I.valid());
238 // Test advanceTo on flat tree.
241 ASSERT_TRUE(I.valid());
242 EXPECT_EQ(140u, I.start());
243 EXPECT_EQ(150u, I.stop());
246 ASSERT_TRUE(I.valid());
247 EXPECT_EQ(140u, I.start());
248 EXPECT_EQ(150u, I.stop());
250 // Coalesce left with followers.
251 // [100;110] [120;130] [140;150] [160;170]
252 map.insert(111, 115, 1);
254 ASSERT_TRUE(I.valid());
255 EXPECT_EQ(100u, I.start());
256 EXPECT_EQ(115u, I.stop());
258 ASSERT_TRUE(I.valid());
259 EXPECT_EQ(120u, I.start());
260 EXPECT_EQ(130u, I.stop());
262 ASSERT_TRUE(I.valid());
263 EXPECT_EQ(140u, I.start());
264 EXPECT_EQ(150u, I.stop());
266 ASSERT_TRUE(I.valid());
267 EXPECT_EQ(160u, I.start());
268 EXPECT_EQ(170u, I.stop());
270 EXPECT_FALSE(I.valid());
272 // Coalesce right with followers.
273 // [100;115] [120;130] [140;150] [160;170]
274 map.insert(135, 139, 1);
276 ASSERT_TRUE(I.valid());
277 EXPECT_EQ(100u, I.start());
278 EXPECT_EQ(115u, I.stop());
280 ASSERT_TRUE(I.valid());
281 EXPECT_EQ(120u, I.start());
282 EXPECT_EQ(130u, I.stop());
284 ASSERT_TRUE(I.valid());
285 EXPECT_EQ(135u, I.start());
286 EXPECT_EQ(150u, I.stop());
288 ASSERT_TRUE(I.valid());
289 EXPECT_EQ(160u, I.start());
290 EXPECT_EQ(170u, I.stop());
292 EXPECT_FALSE(I.valid());
294 // Coalesce left and right with followers.
295 // [100;115] [120;130] [135;150] [160;170]
296 map.insert(131, 134, 1);
298 ASSERT_TRUE(I.valid());
299 EXPECT_EQ(100u, I.start());
300 EXPECT_EQ(115u, I.stop());
302 ASSERT_TRUE(I.valid());
303 EXPECT_EQ(120u, I.start());
304 EXPECT_EQ(150u, I.stop());
306 ASSERT_TRUE(I.valid());
307 EXPECT_EQ(160u, I.start());
308 EXPECT_EQ(170u, I.stop());
310 EXPECT_FALSE(I.valid());
312 // Test clear() on non-branched map.
314 EXPECT_TRUE(map.empty());
315 EXPECT_TRUE(map.begin() == map.end());
318 // Branched, non-coalescing tests.
319 TEST(IntervalMapTest, Branched) {
320 UUMap::Allocator allocator;
321 UUMap map(allocator);
323 // Insert enough intervals to force a branched tree.
324 // This creates 9 leaf nodes with 11 elements each, tree height = 1.
325 for (unsigned i = 1; i < 100; ++i) {
326 map.insert(10*i, 10*i+5, i);
327 EXPECT_EQ(10u, map.start());
328 EXPECT_EQ(10*i+5, map.stop());
332 EXPECT_FALSE(map.empty());
333 EXPECT_EQ(10u, map.start());
334 EXPECT_EQ(995u, map.stop());
337 for (unsigned i = 1; i < 100; ++i) {
338 EXPECT_EQ(0u, map.lookup(10*i-1));
339 EXPECT_EQ(i, map.lookup(10*i));
340 EXPECT_EQ(i, map.lookup(10*i+5));
341 EXPECT_EQ(0u, map.lookup(10*i+6));
344 // Forward iteration.
345 UUMap::iterator I = map.begin();
346 for (unsigned i = 1; i < 100; ++i) {
347 ASSERT_TRUE(I.valid());
348 EXPECT_EQ(10*i, I.start());
349 EXPECT_EQ(10*i+5, I.stop());
353 EXPECT_FALSE(I.valid());
354 EXPECT_TRUE(I == map.end());
356 // Backwards iteration.
357 for (unsigned i = 99; i; --i) {
359 ASSERT_TRUE(I.valid());
360 EXPECT_EQ(10*i, I.start());
361 EXPECT_EQ(10*i+5, I.stop());
364 EXPECT_TRUE(I == map.begin());
366 // Test advanceTo in same node.
368 ASSERT_TRUE(I.valid());
369 EXPECT_EQ(20u, I.start());
370 EXPECT_EQ(25u, I.stop());
372 // Change value, no coalescing.
374 ASSERT_TRUE(I.valid());
375 EXPECT_EQ(20u, I.start());
376 EXPECT_EQ(25u, I.stop());
377 EXPECT_EQ(0u, I.value());
379 // Close the gap right, no coalescing.
381 ASSERT_TRUE(I.valid());
382 EXPECT_EQ(20u, I.start());
383 EXPECT_EQ(29u, I.stop());
384 EXPECT_EQ(0u, I.value());
386 // Change value, no coalescing.
388 ASSERT_TRUE(I.valid());
389 EXPECT_EQ(20u, I.start());
390 EXPECT_EQ(29u, I.stop());
391 EXPECT_EQ(2u, I.value());
393 // Change value, now coalescing.
395 ASSERT_TRUE(I.valid());
396 EXPECT_EQ(20u, I.start());
397 EXPECT_EQ(35u, I.stop());
398 EXPECT_EQ(3u, I.value());
400 // Close the gap, now coalescing.
402 ASSERT_TRUE(I.valid());
404 ASSERT_TRUE(I.valid());
405 EXPECT_EQ(20u, I.start());
406 EXPECT_EQ(45u, I.stop());
407 EXPECT_EQ(4u, I.value());
409 // advanceTo another node.
411 ASSERT_TRUE(I.valid());
412 EXPECT_EQ(200u, I.start());
413 EXPECT_EQ(205u, I.stop());
415 // Close the gap left, no coalescing.
417 ASSERT_TRUE(I.valid());
418 EXPECT_EQ(196u, I.start());
419 EXPECT_EQ(205u, I.stop());
420 EXPECT_EQ(20u, I.value());
422 // Change value, no coalescing.
424 ASSERT_TRUE(I.valid());
425 EXPECT_EQ(196u, I.start());
426 EXPECT_EQ(205u, I.stop());
427 EXPECT_EQ(0u, I.value());
429 // Change value, now coalescing.
431 ASSERT_TRUE(I.valid());
432 EXPECT_EQ(190u, I.start());
433 EXPECT_EQ(205u, I.stop());
434 EXPECT_EQ(19u, I.value());
436 // Close the gap, now coalescing.
438 ASSERT_TRUE(I.valid());
440 ASSERT_TRUE(I.valid());
441 EXPECT_EQ(180u, I.start());
442 EXPECT_EQ(205u, I.stop());
443 EXPECT_EQ(18u, I.value());
445 // Erase from the front.
447 for (unsigned i = 0; i != 20; ++i) {
449 EXPECT_TRUE(I == map.begin());
450 EXPECT_FALSE(map.empty());
451 EXPECT_EQ(I.start(), map.start());
452 EXPECT_EQ(995u, map.stop());
455 // Test clear() on branched map.
457 EXPECT_TRUE(map.empty());
458 EXPECT_TRUE(map.begin() == map.end());
461 // Branched, high, non-coalescing tests.
462 TEST(IntervalMapTest, Branched2) {
463 UUMap::Allocator allocator;
464 UUMap map(allocator);
466 // Insert enough intervals to force a height >= 2 tree.
467 for (unsigned i = 1; i < 1000; ++i)
468 map.insert(10*i, 10*i+5, i);
471 EXPECT_FALSE(map.empty());
472 EXPECT_EQ(10u, map.start());
473 EXPECT_EQ(9995u, map.stop());
476 for (unsigned i = 1; i < 1000; ++i) {
477 EXPECT_EQ(0u, map.lookup(10*i-1));
478 EXPECT_EQ(i, map.lookup(10*i));
479 EXPECT_EQ(i, map.lookup(10*i+5));
480 EXPECT_EQ(0u, map.lookup(10*i+6));
483 // Forward iteration.
484 UUMap::iterator I = map.begin();
485 for (unsigned i = 1; i < 1000; ++i) {
486 ASSERT_TRUE(I.valid());
487 EXPECT_EQ(10*i, I.start());
488 EXPECT_EQ(10*i+5, I.stop());
492 EXPECT_FALSE(I.valid());
493 EXPECT_TRUE(I == map.end());
495 // Backwards iteration.
496 for (unsigned i = 999; i; --i) {
498 ASSERT_TRUE(I.valid());
499 EXPECT_EQ(10*i, I.start());
500 EXPECT_EQ(10*i+5, I.stop());
503 EXPECT_TRUE(I == map.begin());
505 // Test advanceTo in same node.
507 ASSERT_TRUE(I.valid());
508 EXPECT_EQ(20u, I.start());
509 EXPECT_EQ(25u, I.stop());
511 // advanceTo sibling leaf node.
513 ASSERT_TRUE(I.valid());
514 EXPECT_EQ(200u, I.start());
515 EXPECT_EQ(205u, I.stop());
517 // advanceTo further.
519 ASSERT_TRUE(I.valid());
520 EXPECT_EQ(2000u, I.start());
521 EXPECT_EQ(2005u, I.stop());
523 // Test clear() on branched map.
525 EXPECT_TRUE(map.empty());
526 EXPECT_TRUE(map.begin() == map.end());
529 // Random insertions, coalescing to a single interval.
530 TEST(IntervalMapTest, RandomCoalescing) {
531 UUMap::Allocator allocator;
532 UUMap map(allocator);
534 // This is a poor PRNG with maximal period:
535 // x_n = 5 x_{n-1} + 1 mod 2^N
538 for (unsigned i = 0; i != 4096; ++i) {
539 map.insert(10*x, 10*x+9, 1);
540 EXPECT_GE(10*x, map.start());
541 EXPECT_LE(10*x+9, map.stop());
545 // Map should be fully coalesced after that exercise.
546 EXPECT_FALSE(map.empty());
547 EXPECT_EQ(0u, map.start());
548 EXPECT_EQ(40959u, map.stop());
549 EXPECT_EQ(1, std::distance(map.begin(), map.end()));
553 TEST(IntervalMapOverlapsTest, EmptyMaps) {
554 typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
555 UUMap::Allocator allocator;
556 UUMap mapA(allocator);
557 UUMap mapB(allocator);
560 EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
562 mapA.insert(1, 2, 3);
564 EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
566 EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());