1 //===---- ADT/IntervalMapTest.cpp - IntervalMap unit tests ------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/ADT/IntervalMap.h"
11 #include "gtest/gtest.h"
12 
13 using namespace llvm;
14 
15 namespace {
16 
17 typedef IntervalMap<unsigned, unsigned> UUMap;
18 typedef IntervalMap<unsigned, unsigned, 4> UU4Map;
19 
20 // Empty map tests
21 TEST(IntervalMapTest, EmptyMap) {
22   UUMap::Allocator allocator;
23   UUMap map(allocator);
24   EXPECT_TRUE(map.empty());
25 
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));
31 
32   // Iterators.
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());
44 }
45 
46 // Single entry map tests
47 TEST(IntervalMapTest, SingleEntryMap) {
48   UUMap::Allocator allocator;
49   UUMap map(allocator);
50   map.insert(100, 150, 1);
51   EXPECT_FALSE(map.empty());
52 
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));
64 
65   // Iterators.
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());
71 
72   // Iter deref.
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());
78 
79   // Preincrement.
80   ++I;
81   EXPECT_FALSE(I.valid());
82   EXPECT_FALSE(I == map.begin());
83   EXPECT_TRUE(I == map.end());
84 
85   // PreDecrement.
86   --I;
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());
93 }
94 
95 // Flat coalescing tests.
96 TEST(IntervalMapTest, RootCoalescing) {
97   UUMap::Allocator allocator;
98   UUMap map(allocator);
99   map.insert(100, 150, 1);
100 
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());
106 
107   // Overlap left.
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());
112 
113   // Inside.
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());
118 
119   // Overlap both.
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());
124 
125   // Overlap right.
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());
130 
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());
136 
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));
144 
145   UUMap::iterator I = map.begin();
146   EXPECT_EQ(60u, I.start());
147   EXPECT_EQ(69u, I.stop());
148   EXPECT_EQ(2u, I.value());
149   ++I;
150   EXPECT_EQ(70u, I.start());
151   EXPECT_EQ(200u, I.stop());
152   EXPECT_EQ(1u, I.value());
153   ++I;
154   EXPECT_FALSE(I.valid());
155 
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));
163 }
164 
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());
176 
177   // Verify inserts.
178   UUMap::iterator I = map.begin();
179   EXPECT_EQ(100u, I.start());
180   EXPECT_EQ(110u, I.stop());
181   ++I;
182   EXPECT_EQ(120u, I.start());
183   EXPECT_EQ(130u, I.stop());
184   ++I;
185   EXPECT_EQ(140u, I.start());
186   EXPECT_EQ(150u, I.stop());
187   ++I;
188   EXPECT_EQ(160u, I.start());
189   EXPECT_EQ(170u, I.stop());
190   ++I;
191   EXPECT_FALSE(I.valid());
192 
193 
194   // Coalesce left with followers.
195   // [100;110] [120;130] [140;150] [160;170]
196   map.insert(111, 115, 1);
197   I = map.begin();
198   ASSERT_TRUE(I.valid());
199   EXPECT_EQ(100u, I.start());
200   EXPECT_EQ(115u, I.stop());
201   ++I;
202   ASSERT_TRUE(I.valid());
203   EXPECT_EQ(120u, I.start());
204   EXPECT_EQ(130u, I.stop());
205   ++I;
206   ASSERT_TRUE(I.valid());
207   EXPECT_EQ(140u, I.start());
208   EXPECT_EQ(150u, I.stop());
209   ++I;
210   ASSERT_TRUE(I.valid());
211   EXPECT_EQ(160u, I.start());
212   EXPECT_EQ(170u, I.stop());
213   ++I;
214   EXPECT_FALSE(I.valid());
215 
216   // Coalesce right with followers.
217   // [100;115] [120;130] [140;150] [160;170]
218   map.insert(135, 139, 1);
219   I = map.begin();
220   ASSERT_TRUE(I.valid());
221   EXPECT_EQ(100u, I.start());
222   EXPECT_EQ(115u, I.stop());
223   ++I;
224   ASSERT_TRUE(I.valid());
225   EXPECT_EQ(120u, I.start());
226   EXPECT_EQ(130u, I.stop());
227   ++I;
228   ASSERT_TRUE(I.valid());
229   EXPECT_EQ(135u, I.start());
230   EXPECT_EQ(150u, I.stop());
231   ++I;
232   ASSERT_TRUE(I.valid());
233   EXPECT_EQ(160u, I.start());
234   EXPECT_EQ(170u, I.stop());
235   ++I;
236   EXPECT_FALSE(I.valid());
237 
238   // Coalesce left and right with followers.
239   // [100;115] [120;130] [135;150] [160;170]
240   map.insert(131, 134, 1);
241   I = map.begin();
242   ASSERT_TRUE(I.valid());
243   EXPECT_EQ(100u, I.start());
244   EXPECT_EQ(115u, I.stop());
245   ++I;
246   ASSERT_TRUE(I.valid());
247   EXPECT_EQ(120u, I.start());
248   EXPECT_EQ(150u, I.stop());
249   ++I;
250   ASSERT_TRUE(I.valid());
251   EXPECT_EQ(160u, I.start());
252   EXPECT_EQ(170u, I.stop());
253   ++I;
254   EXPECT_FALSE(I.valid());
255 
256   // Coalesce multiple with overlap right.
257   // [100;115] [120;150] [160;170]
258   map.insert(116, 165, 1);
259   I = map.begin();
260   ASSERT_TRUE(I.valid());
261   EXPECT_EQ(100u, I.start());
262   EXPECT_EQ(170u, I.stop());
263   ++I;
264   EXPECT_FALSE(I.valid());
265 
266   // Coalesce multiple with overlap left
267   // [100;170]
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);
273   I = map.begin();
274   ASSERT_TRUE(I.valid());
275   EXPECT_EQ(100u, I.start());
276   EXPECT_EQ(210u, I.stop());
277   ++I;
278   ASSERT_TRUE(I.valid());
279   EXPECT_EQ(220u, I.start());
280   EXPECT_EQ(230u, I.stop());
281   ++I;
282   EXPECT_FALSE(I.valid());
283 
284   // Overwrite 2 from gap to gap.
285   // [100;210] [220;230]
286   map.insert(50, 250, 1);
287   I = map.begin();
288   ASSERT_TRUE(I.valid());
289   EXPECT_EQ(50u, I.start());
290   EXPECT_EQ(250u, I.stop());
291   ++I;
292   EXPECT_FALSE(I.valid());
293 
294   // Coalesce at end of full root.
295   // [50;250]
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);
301   I = map.begin();
302   ASSERT_TRUE(I.valid());
303   EXPECT_EQ(50u, I.start());
304   EXPECT_EQ(250u, I.stop());
305   ++I;
306   ASSERT_TRUE(I.valid());
307   EXPECT_EQ(260u, I.start());
308   EXPECT_EQ(270u, I.stop());
309   ++I;
310   ASSERT_TRUE(I.valid());
311   EXPECT_EQ(280u, I.start());
312   EXPECT_EQ(290u, I.stop());
313   ++I;
314   ASSERT_TRUE(I.valid());
315   EXPECT_EQ(300u, I.start());
316   EXPECT_EQ(320u, I.stop());
317   ++I;
318   EXPECT_FALSE(I.valid());
319 
320   // Test clear() on non-branched map.
321   map.clear();
322   EXPECT_TRUE(map.empty());
323   EXPECT_TRUE(map.begin() == map.end());
324 }
325 
326 // Branched, non-coalescing tests.
327 TEST(IntervalMapTest, Branched) {
328   UUMap::Allocator allocator;
329   UUMap map(allocator);
330 
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);
335 
336   // Tree limits.
337   EXPECT_FALSE(map.empty());
338   EXPECT_EQ(10u, map.start());
339   EXPECT_EQ(995u, map.stop());
340 
341   // Tree lookup.
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));
347   }
348 
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());
355     EXPECT_EQ(i, *I);
356     ++I;
357   }
358   EXPECT_FALSE(I.valid());
359   EXPECT_TRUE(I == map.end());
360 
361   // Backwards iteration.
362   for (unsigned i = 99; i; --i) {
363     --I;
364     ASSERT_TRUE(I.valid());
365     EXPECT_EQ(10*i, I.start());
366     EXPECT_EQ(10*i+5, I.stop());
367     EXPECT_EQ(i, *I);
368   }
369   EXPECT_TRUE(I == map.begin());
370 
371   // Test clear() on branched map.
372   map.clear();
373   EXPECT_TRUE(map.empty());
374   EXPECT_TRUE(map.begin() == map.end());
375 }
376 
377 // Branched, high, non-coalescing tests.
378 TEST(IntervalMapTest, Branched2) {
379   UU4Map::Allocator allocator;
380   UU4Map map(allocator);
381 
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);
385 
386   // Tree limits.
387   EXPECT_FALSE(map.empty());
388   EXPECT_EQ(10u, map.start());
389   EXPECT_EQ(9995u, map.stop());
390 
391   // Tree lookup.
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));
397   }
398 
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());
405     EXPECT_EQ(i, *I);
406     ++I;
407   }
408   EXPECT_FALSE(I.valid());
409   EXPECT_TRUE(I == map.end());
410 
411   // Backwards iteration.
412   for (unsigned i = 999; i; --i) {
413     --I;
414     ASSERT_TRUE(I.valid());
415     EXPECT_EQ(10*i, I.start());
416     EXPECT_EQ(10*i+5, I.stop());
417     EXPECT_EQ(i, *I);
418   }
419   EXPECT_TRUE(I == map.begin());
420 
421   // Test clear() on branched map.
422   map.clear();
423   EXPECT_TRUE(map.empty());
424   EXPECT_TRUE(map.begin() == map.end());
425 }
426 
427 // Random insertions, coalescing to a single interval.
428 TEST(IntervalMapTest, RandomCoalescing) {
429   UU4Map::Allocator allocator;
430   UU4Map map(allocator);
431 
432   // This is a poor PRNG with maximal period:
433   // x_n = 5 x_{n-1} + 1 mod 2^N
434 
435   unsigned x = 100;
436   for (unsigned i = 0; i != 4096; ++i) {
437     map.insert(10*x, 10*x+9, 1);
438     EXPECT_GE(10*x, map.start());
439     EXPECT_LE(10*x+9, map.stop());
440     x = (5*x+1)%4096;
441   }
442 
443   // Map should be fully coalesced after that exercise.
444   EXPECT_FALSE(map.empty());
445   EXPECT_EQ(0u, map.start());
446   EXPECT_EQ(40959u, map.stop());
447   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
448 
449 }
450 
451 } // namespace
452