IntervalMapTest.cpp revision 8dc926755f287e33765a8da0c4b3922a289a9d2d 
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
13using namespace llvm;
14
15namespace {
16
17typedef IntervalMap<unsigned, unsigned> UUMap;
18
19// Empty map tests
20TEST(IntervalMapTest, EmptyMap) {
21  UUMap::Allocator allocator;
22  UUMap map(allocator);
23  EXPECT_TRUE(map.empty());
24
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));
30
31  // Iterators.
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());
43}
44
45// Single entry map tests
46TEST(IntervalMapTest, SingleEntryMap) {
47  UUMap::Allocator allocator;
48  UUMap map(allocator);
49  map.insert(100, 150, 1);
50  EXPECT_FALSE(map.empty());
51
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));
63
64  // Iterators.
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());
70
71  // Iter deref.
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());
77
78  // Preincrement.
79  ++I;
80  EXPECT_FALSE(I.valid());
81  EXPECT_FALSE(I == map.begin());
82  EXPECT_TRUE(I == map.end());
83
84  // PreDecrement.
85  --I;
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());
92}
93
94// Flat coalescing tests.
95TEST(IntervalMapTest, RootCoalescing) {
96  UUMap::Allocator allocator;
97  UUMap map(allocator);
98  map.insert(100, 150, 1);
99
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());
105
106  // Overlap left.
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());
111
112  // Inside.
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());
117
118  // Overlap both.
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());
123
124  // Overlap right.
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());
129
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());
135
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));
143
144  UUMap::iterator I = map.begin();
145  EXPECT_EQ(60u, I.start());
146  EXPECT_EQ(69u, I.stop());
147  EXPECT_EQ(2u, I.value());
148  ++I;
149  EXPECT_EQ(70u, I.start());
150  EXPECT_EQ(200u, I.stop());
151  EXPECT_EQ(1u, I.value());
152  ++I;
153  EXPECT_FALSE(I.valid());
154
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));
162}
163
164// Flat multi-coalescing tests.
165TEST(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());
175
176  // Verify inserts.
177  UUMap::iterator I = map.begin();
178  EXPECT_EQ(100u, I.start());
179  EXPECT_EQ(110u, I.stop());
180  ++I;
181  EXPECT_EQ(120u, I.start());
182  EXPECT_EQ(130u, I.stop());
183  ++I;
184  EXPECT_EQ(140u, I.start());
185  EXPECT_EQ(150u, I.stop());
186  ++I;
187  EXPECT_EQ(160u, I.start());
188  EXPECT_EQ(170u, I.stop());
189  ++I;
190  EXPECT_FALSE(I.valid());
191
192
193  // Coalesce left with followers.
194  // [100;110] [120;130] [140;150] [160;170]
195  map.insert(111, 115, 1);
196  I = map.begin();
197  ASSERT_TRUE(I.valid());
198  EXPECT_EQ(100u, I.start());
199  EXPECT_EQ(115u, I.stop());
200  ++I;
201  ASSERT_TRUE(I.valid());
202  EXPECT_EQ(120u, I.start());
203  EXPECT_EQ(130u, I.stop());
204  ++I;
205  ASSERT_TRUE(I.valid());
206  EXPECT_EQ(140u, I.start());
207  EXPECT_EQ(150u, I.stop());
208  ++I;
209  ASSERT_TRUE(I.valid());
210  EXPECT_EQ(160u, I.start());
211  EXPECT_EQ(170u, I.stop());
212  ++I;
213  EXPECT_FALSE(I.valid());
214
215  // Coalesce right with followers.
216  // [100;115] [120;130] [140;150] [160;170]
217  map.insert(135, 139, 1);
218  I = map.begin();
219  ASSERT_TRUE(I.valid());
220  EXPECT_EQ(100u, I.start());
221  EXPECT_EQ(115u, I.stop());
222  ++I;
223  ASSERT_TRUE(I.valid());
224  EXPECT_EQ(120u, I.start());
225  EXPECT_EQ(130u, I.stop());
226  ++I;
227  ASSERT_TRUE(I.valid());
228  EXPECT_EQ(135u, I.start());
229  EXPECT_EQ(150u, I.stop());
230  ++I;
231  ASSERT_TRUE(I.valid());
232  EXPECT_EQ(160u, I.start());
233  EXPECT_EQ(170u, I.stop());
234  ++I;
235  EXPECT_FALSE(I.valid());
236
237  // Coalesce left and right with followers.
238  // [100;115] [120;130] [135;150] [160;170]
239  map.insert(131, 134, 1);
240  I = map.begin();
241  ASSERT_TRUE(I.valid());
242  EXPECT_EQ(100u, I.start());
243  EXPECT_EQ(115u, I.stop());
244  ++I;
245  ASSERT_TRUE(I.valid());
246  EXPECT_EQ(120u, I.start());
247  EXPECT_EQ(150u, I.stop());
248  ++I;
249  ASSERT_TRUE(I.valid());
250  EXPECT_EQ(160u, I.start());
251  EXPECT_EQ(170u, I.stop());
252  ++I;
253  EXPECT_FALSE(I.valid());
254
255  // Coalesce multiple with overlap right.
256  // [100;115] [120;150] [160;170]
257  map.insert(116, 165, 1);
258  I = map.begin();
259  ASSERT_TRUE(I.valid());
260  EXPECT_EQ(100u, I.start());
261  EXPECT_EQ(170u, I.stop());
262  ++I;
263  EXPECT_FALSE(I.valid());
264
265  // Coalesce multiple with overlap left
266  // [100;170]
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);
272  I = map.begin();
273  ASSERT_TRUE(I.valid());
274  EXPECT_EQ(100u, I.start());
275  EXPECT_EQ(210u, I.stop());
276  ++I;
277  ASSERT_TRUE(I.valid());
278  EXPECT_EQ(220u, I.start());
279  EXPECT_EQ(230u, I.stop());
280  ++I;
281  EXPECT_FALSE(I.valid());
282
283  // Overwrite 2 from gap to gap.
284  // [100;210] [220;230]
285  map.insert(50, 250, 1);
286  I = map.begin();
287  ASSERT_TRUE(I.valid());
288  EXPECT_EQ(50u, I.start());
289  EXPECT_EQ(250u, I.stop());
290  ++I;
291  EXPECT_FALSE(I.valid());
292
293  // Coalesce at end of full root.
294  // [50;250]
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);
300  I = map.begin();
301  ASSERT_TRUE(I.valid());
302  EXPECT_EQ(50u, I.start());
303  EXPECT_EQ(250u, I.stop());
304  ++I;
305  ASSERT_TRUE(I.valid());
306  EXPECT_EQ(260u, I.start());
307  EXPECT_EQ(270u, I.stop());
308  ++I;
309  ASSERT_TRUE(I.valid());
310  EXPECT_EQ(280u, I.start());
311  EXPECT_EQ(290u, I.stop());
312  ++I;
313  ASSERT_TRUE(I.valid());
314  EXPECT_EQ(300u, I.start());
315  EXPECT_EQ(320u, I.stop());
316  ++I;
317  EXPECT_FALSE(I.valid());
318}
319
320// Branched, non-coalescing tests.
321TEST(IntervalMapTest, Branched) {
322  UUMap::Allocator allocator;
323  UUMap map(allocator);
324
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);
329
330  // Tree limits.
331  EXPECT_FALSE(map.empty());
332  EXPECT_EQ(10u, map.start());
333  EXPECT_EQ(995u, map.stop());
334
335  // Tree lookup.
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));
341  }
342
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());
349    EXPECT_EQ(i, *I);
350    ++I;
351  }
352  EXPECT_FALSE(I.valid());
353  EXPECT_TRUE(I == map.end());
354
355}
356
357} // namespace
358