1 : // Copyright 2012 Google Inc. All Rights Reserved.
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 : //
15 : #include "syzygy/core/address_space.h"
16 :
17 : #include <limits>
18 : #include "gmock/gmock.h"
19 : #include "gtest/gtest.h"
20 : #include "syzygy/core/unittest_util.h"
21 :
22 : namespace core {
23 :
24 : typedef AddressRange<size_t, size_t> IntegerRange;
25 : typedef AddressRangeMap<IntegerRange, IntegerRange> IntegerRangeMap;
26 : typedef IntegerRangeMap::RangePair IntegerRangePair;
27 : typedef IntegerRangeMap::RangePairs IntegerRangePairs;
28 :
29 : namespace {
30 :
31 : // A pretty printer for std::pair.
32 : template<typename FirstType, typename SecondType>
33 : std::ostream& operator<<(std::ostream& os,
34 : const std::pair<FirstType, SecondType>& pair) {
35 : os << "pair(first=" << pair.first << ", second=" << pair.second << ")";
36 : return os;
37 : }
38 :
39 : } // namespace
40 :
41 : typedef AddressSpace<const uint8*, size_t, void*> PointerAddressSpace;
42 : typedef AddressSpace<size_t, size_t, void*> IntegerAddressSpace;
43 :
44 E : TEST(AddressSpaceTest, Create) {
45 E : PointerAddressSpace pointer_space;
46 E : IntegerAddressSpace integer_space;
47 E : }
48 :
49 E : TEST(AddressSpaceTest, Insert) {
50 E : IntegerAddressSpace address_space;
51 E : void* item = "Something to point at";
52 :
53 : // Non-overlapping insertions should work.
54 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
55 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
56 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
57 :
58 : // Overlapping insertions should be rejected.
59 E : EXPECT_FALSE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
60 E : EXPECT_FALSE(address_space.Insert(IntegerAddressSpace::Range(95, 10), item));
61 E : EXPECT_FALSE(address_space.Insert(IntegerAddressSpace::Range(100, 5), item));
62 E : EXPECT_FALSE(address_space.Insert(IntegerAddressSpace::Range(105, 5), item));
63 :
64 : // Empty insertions should be rejected.
65 E : EXPECT_FALSE(address_space.Insert(IntegerAddressSpace::Range(10, 0), item));
66 E : }
67 :
68 E : TEST(AddressSpaceTest, FindOrInsert) {
69 E : IntegerAddressSpace address_space;
70 E : void* item = "Something to point at";
71 :
72 : typedef IntegerAddressSpace::Range Range;
73 : typedef IntegerAddressSpace::RangeMapIter Iter;
74 :
75 E : Iter iter1, iter2, iter3, attempt;
76 :
77 : // Non-overlapping insertions should work.
78 E : EXPECT_TRUE(address_space.FindOrInsert(Range(100, 10), item, &iter1));
79 E : EXPECT_TRUE(address_space.FindOrInsert(Range(110, 5), item, &iter2));
80 E : EXPECT_TRUE(address_space.FindOrInsert(Range(120, 10), item, &iter3));
81 E : EXPECT_TRUE(iter1 != iter2);
82 E : EXPECT_TRUE(iter1 != iter3);
83 E : EXPECT_TRUE(iter2 != iter3);
84 :
85 : // Exactly matching range assertions insertions should be accepted.
86 E : EXPECT_TRUE(address_space.FindOrInsert(Range(100, 10), item, &attempt));
87 E : EXPECT_TRUE(attempt == iter1);
88 E : EXPECT_TRUE(address_space.FindOrInsert(Range(110, 5), item, &attempt));
89 E : EXPECT_TRUE(attempt == iter2);
90 E : EXPECT_TRUE(address_space.FindOrInsert(Range(120, 10), item, &attempt));
91 E : EXPECT_TRUE(attempt == iter3);
92 :
93 : // Non-matching overlapping insertions should be rejected.
94 E : EXPECT_FALSE(address_space.Insert(Range(95, 10), item, &attempt));
95 E : EXPECT_FALSE(address_space.Insert(Range(100, 8), item, &attempt));
96 E : EXPECT_FALSE(address_space.Insert(Range(101, 8), item, &attempt));
97 E : EXPECT_FALSE(address_space.Insert(Range(105, 5), item, &attempt));
98 E : EXPECT_FALSE(address_space.Insert(Range(105, 9), item, &attempt));
99 :
100 : // Empty insertions should be rejected.
101 E : EXPECT_FALSE(address_space.FindOrInsert(Range(10, 0), item, &attempt));
102 E : }
103 :
104 E : TEST(AddressSpaceTest, SubsumeInsert) {
105 E : IntegerAddressSpace address_space;
106 : typedef IntegerAddressSpace::Range Range;
107 E : void* item = "Something to point at";
108 :
109 : // Non-overlapping insertions should work.
110 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(100, 10), item));
111 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(110, 5), item));
112 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(120, 10), item));
113 E : EXPECT_TRUE(address_space.ranges().size() == 3);
114 :
115 : // Insertion of sub-ranges of existing ranges should work, but not
116 : // actually create anything new.
117 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(100, 5), item));
118 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(111, 2), item));
119 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(127, 2), item));
120 E : EXPECT_TRUE(address_space.ranges().size() == 3);
121 :
122 : // Reinsertions should work, but not actually create anything new.
123 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(100, 10), item));
124 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(110, 5), item));
125 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(120, 10), item));
126 E : EXPECT_TRUE(address_space.ranges().size() == 3);
127 :
128 : // Overlapping (but not containing) intersections should be rejected.
129 E : EXPECT_FALSE(address_space.SubsumeInsert(Range(95, 10), item));
130 E : EXPECT_FALSE(address_space.SubsumeInsert(Range(100, 11), item));
131 E : EXPECT_FALSE(address_space.SubsumeInsert(Range(125, 6), item));
132 E : EXPECT_TRUE(address_space.ranges().size() == 3);
133 :
134 : // Insertions of ranges that intersect multiple ranges should merge/extend
135 : // them.
136 E : address_space.MergeInsert(Range(90, 30), item);
137 E : EXPECT_TRUE(address_space.ranges().size() == 2);
138 E : address_space.MergeInsert(Range(124, 2), item);
139 E : EXPECT_TRUE(address_space.ranges().size() == 2);
140 :
141 : // Insertions of ranges that contain all intersecting existing ranges
142 : // should replace those ranges.
143 E : EXPECT_TRUE(address_space.SubsumeInsert(Range(85, 50), item));
144 E : EXPECT_TRUE(address_space.ranges().size() == 1);
145 :
146 : // Empty insertions should be rejected.
147 E : EXPECT_FALSE(address_space.SubsumeInsert(Range(10, 0), item));
148 E : }
149 :
150 E : TEST(AddressSpaceTest, Remove) {
151 E : IntegerAddressSpace address_space;
152 E : void* item = "Something to point at";
153 :
154 : // Insert some items.
155 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
156 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
157 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
158 :
159 : // Non-matching removals should fail.
160 E : ASSERT_FALSE(address_space.Remove(IntegerAddressSpace::Range(100, 9)));
161 E : ASSERT_FALSE(address_space.Remove(IntegerAddressSpace::Range(101, 9)));
162 E : ASSERT_FALSE(address_space.Remove(IntegerAddressSpace::Range(115, 5)));
163 :
164 : // Matching removals should succeed.
165 E : ASSERT_TRUE(address_space.Remove(IntegerAddressSpace::Range(100, 10)));
166 E : ASSERT_TRUE(address_space.Remove(IntegerAddressSpace::Range(110, 5)));
167 :
168 : // Items should have been removed.
169 E : ASSERT_FALSE(address_space.Remove(IntegerAddressSpace::Range(100, 10)));
170 E : ASSERT_FALSE(address_space.Remove(IntegerAddressSpace::Range(110, 5)));
171 :
172 : // Empty removals should always fail.
173 E : EXPECT_FALSE(address_space.Remove(IntegerAddressSpace::Range(10, 0)));
174 E : }
175 :
176 E : TEST(AddressSpaceTest, RemoveByIter) {
177 E : IntegerAddressSpace address_space;
178 E : void* item = "Something to point at";
179 :
180 : // Insert some items.
181 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
182 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
183 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
184 :
185 : // Removal by single iterator should succeed.
186 E : address_space.Remove(address_space.begin());
187 E : EXPECT_TRUE(address_space.ranges().size() == 2);
188 :
189 : // Removal by pair of iterators should succeed.
190 E : address_space.Remove(address_space.begin(), address_space.end());
191 E : EXPECT_TRUE(address_space.ranges().empty());
192 E : }
193 :
194 E : TEST(AddressSpaceTest, Clear) {
195 E : IntegerAddressSpace address_space;
196 E : void* item = "Something to point at";
197 :
198 : // Insert some items.
199 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
200 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
201 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
202 E : ASSERT_TRUE(!address_space.ranges().empty());
203 :
204 E : address_space.Clear();
205 E : EXPECT_TRUE(address_space.ranges().empty());
206 E : }
207 :
208 E : TEST(AddressSpaceTest, Intersects) {
209 E : IntegerAddressSpace address_space;
210 E : void* item = "Something to point at";
211 :
212 : // Insert some items.
213 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
214 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
215 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
216 :
217 : // Valid intersections should return true.
218 E : ASSERT_TRUE(address_space.Intersects(95, 10));
219 E : ASSERT_TRUE(address_space.Intersects(95, 50));
220 :
221 : // Empty intersections should fail.
222 E : ASSERT_FALSE(address_space.Intersects(95, 5));
223 E : ASSERT_FALSE(address_space.Intersects(115, 5));
224 :
225 : // Intersections with empty ranges should fail.
226 E : ASSERT_FALSE(address_space.Intersects(50, 0));
227 E : ASSERT_FALSE(address_space.Intersects(100, 0));
228 E : ASSERT_FALSE(address_space.Intersects(101, 0));
229 E : }
230 :
231 E : TEST(AddressSpaceTest, ContainsExactly) {
232 E : IntegerAddressSpace address_space;
233 E : void* item = "Something to point at";
234 :
235 : // Insert some items.
236 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
237 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
238 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
239 :
240 : // Exact containment should return true.
241 E : ASSERT_TRUE(address_space.ContainsExactly(100, 10));
242 E : ASSERT_TRUE(address_space.ContainsExactly(110, 5));
243 E : ASSERT_TRUE(address_space.ContainsExactly(120, 10));
244 :
245 : // Proper containment should fail (in both directions).
246 E : ASSERT_FALSE(address_space.ContainsExactly(101, 8));
247 E : ASSERT_FALSE(address_space.ContainsExactly(110, 4));
248 E : ASSERT_FALSE(address_space.ContainsExactly(110, 6));
249 E : ASSERT_FALSE(address_space.ContainsExactly(122, 8));
250 :
251 : // Intersections should fail.
252 E : ASSERT_FALSE(address_space.ContainsExactly(95, 10));
253 E : ASSERT_FALSE(address_space.ContainsExactly(125, 10));
254 :
255 : // Containment of with empty ranges should always fail.
256 E : ASSERT_FALSE(address_space.ContainsExactly(50, 0));
257 E : ASSERT_FALSE(address_space.ContainsExactly(100, 0));
258 E : ASSERT_FALSE(address_space.ContainsExactly(101, 0));
259 E : }
260 :
261 E : TEST(AddressSpaceTest, Contains) {
262 E : IntegerAddressSpace address_space;
263 E : void* item = "Something to point at";
264 :
265 : // Insert some items.
266 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
267 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
268 E : ASSERT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
269 :
270 : // Exact containment should return true.
271 E : ASSERT_TRUE(address_space.Contains(100, 10));
272 E : ASSERT_TRUE(address_space.Contains(110, 5));
273 E : ASSERT_TRUE(address_space.Contains(120, 10));
274 :
275 : // Proper sub-ranges of existing ranges should return true.
276 E : ASSERT_TRUE(address_space.Contains(101, 8));
277 E : ASSERT_TRUE(address_space.Contains(110, 4));
278 E : ASSERT_TRUE(address_space.Contains(122, 8));
279 :
280 : // Ranges that properly contain existing ranges should fail.
281 E : ASSERT_FALSE(address_space.Contains(110, 6));
282 :
283 : // Intersections should fail.
284 E : ASSERT_FALSE(address_space.Contains(95, 10));
285 E : ASSERT_FALSE(address_space.Contains(125, 10));
286 :
287 : // Containment of with empty ranges should always fail.
288 E : ASSERT_FALSE(address_space.Contains(50, 0));
289 E : ASSERT_FALSE(address_space.Contains(100, 0));
290 E : ASSERT_FALSE(address_space.Contains(101, 0));
291 E : }
292 :
293 E : TEST(AddressSpaceTest, FindFirstIntersection) {
294 E : IntegerAddressSpace address_space;
295 E : void* item = "Something to point at";
296 :
297 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
298 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
299 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
300 :
301 : IntegerAddressSpace::RangeMap::iterator it =
302 E : address_space.FindFirstIntersection(IntegerAddressSpace::Range(0, 99));
303 E : EXPECT_TRUE(it == address_space.ranges().end());
304 :
305 E : it = address_space.FindFirstIntersection(IntegerAddressSpace::Range(0, 100));
306 E : EXPECT_TRUE(it == address_space.ranges().end());
307 :
308 E : it = address_space.FindFirstIntersection(IntegerAddressSpace::Range(0, 130));
309 E : ASSERT_TRUE(it != address_space.ranges().end());
310 E : EXPECT_EQ(100, it->first.start());
311 :
312 E : it = address_space.FindFirstIntersection(IntegerAddressSpace::Range(110, 10));
313 E : ASSERT_TRUE(it != address_space.ranges().end());
314 E : EXPECT_EQ(110, it->first.start());
315 :
316 E : it = address_space.FindFirstIntersection(IntegerAddressSpace::Range(105, 30));
317 E : ASSERT_TRUE(it != address_space.ranges().end());
318 E : EXPECT_EQ(100, it->first.start());
319 :
320 E : it = address_space.FindFirstIntersection(IntegerAddressSpace::Range(110, 30));
321 E : ASSERT_TRUE(it != address_space.ranges().end());
322 E : EXPECT_EQ(110, it->first.start());
323 :
324 E : it = address_space.FindFirstIntersection(IntegerAddressSpace::Range(115, 5));
325 E : EXPECT_TRUE(it == address_space.ranges().end());
326 :
327 E : it = address_space.FindFirstIntersection(IntegerAddressSpace::Range(130, 30));
328 E : EXPECT_TRUE(it == address_space.ranges().end());
329 :
330 : // Empty ranges should never be found.
331 E : it = address_space.FindFirstIntersection(IntegerAddressSpace::Range(102, 0));
332 E : EXPECT_TRUE(it == address_space.ranges().end());
333 E : }
334 :
335 E : TEST(AddressSpaceTest, FindContaining) {
336 E : IntegerAddressSpace address_space;
337 E : void* item = "Something to point at";
338 :
339 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
340 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
341 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
342 :
343 : IntegerAddressSpace::RangeMap::iterator it =
344 E : address_space.FindContaining(IntegerAddressSpace::Range(110, 5));
345 E : ASSERT_TRUE(it != address_space.ranges().end());
346 E : EXPECT_EQ(110, it->first.start());
347 :
348 E : it = address_space.FindContaining(IntegerAddressSpace::Range(110, 2));
349 E : ASSERT_TRUE(it != address_space.ranges().end());
350 E : EXPECT_EQ(110, it->first.start());
351 :
352 E : it = address_space.FindContaining(IntegerAddressSpace::Range(113, 2));
353 E : ASSERT_TRUE(it != address_space.ranges().end());
354 E : EXPECT_EQ(110, it->first.start());
355 :
356 E : it = address_space.FindContaining(IntegerAddressSpace::Range(109, 5));
357 E : EXPECT_TRUE(it == address_space.ranges().end());
358 :
359 E : it = address_space.FindContaining(IntegerAddressSpace::Range(111, 5));
360 E : EXPECT_TRUE(it == address_space.ranges().end());
361 :
362 E : it = address_space.FindContaining(IntegerAddressSpace::Range(109, 7));
363 E : EXPECT_TRUE(it == address_space.ranges().end());
364 :
365 : // Empty ranges should never be found.
366 E : it = address_space.FindContaining(IntegerAddressSpace::Range(101, 0));
367 E : EXPECT_TRUE(it == address_space.ranges().end());
368 E : }
369 :
370 E : TEST(AddressSpaceTest, FindIntersecting) {
371 E : IntegerAddressSpace address_space;
372 E : void* item = "Something to point at";
373 :
374 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(100, 10), item));
375 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(110, 5), item));
376 E : EXPECT_TRUE(address_space.Insert(IntegerAddressSpace::Range(120, 10), item));
377 :
378 : IntegerAddressSpace::RangeMapIterPair it_pair =
379 E : address_space.FindIntersecting(IntegerAddressSpace::Range(0, 130));
380 E : EXPECT_TRUE(it_pair.first == address_space.ranges().begin());
381 E : EXPECT_TRUE(it_pair.second == address_space.ranges().end());
382 :
383 : it_pair =
384 E : address_space.FindIntersecting(IntegerAddressSpace::Range(115, 5));
385 E : EXPECT_TRUE(it_pair.first == it_pair.second);
386 E : EXPECT_TRUE(it_pair.second != address_space.end());
387 :
388 E : it_pair = address_space.FindIntersecting(IntegerAddressSpace::Range(100, 15));
389 E : ASSERT_TRUE(it_pair.first != address_space.ranges().end());
390 E : ASSERT_TRUE(it_pair.second != address_space.ranges().end());
391 E : EXPECT_EQ(100, it_pair.first->first.start());
392 E : EXPECT_EQ(120, it_pair.second->first.start());
393 :
394 E : it_pair = address_space.FindIntersecting(IntegerAddressSpace::Range(101, 0));
395 E : EXPECT_TRUE(it_pair.first == it_pair.second);
396 E : EXPECT_TRUE(it_pair.first == address_space.ranges().end());
397 E : }
398 :
399 E : TEST(AddressRangeMapTest, IsSimple) {
400 E : IntegerRangeMap map;
401 E : EXPECT_FALSE(map.IsSimple());
402 :
403 E : EXPECT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
404 E : EXPECT_TRUE(map.IsSimple());
405 :
406 E : EXPECT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
407 E : EXPECT_FALSE(map.IsSimple());
408 :
409 E : IntegerRangeMap map2;
410 E : EXPECT_TRUE(map2.Push(IntegerRange(0, 10), IntegerRange(1000, 15)));
411 E : EXPECT_FALSE(map2.IsSimple());
412 E : }
413 :
414 E : TEST(AddressRangeMapTest, FindRangePair) {
415 E : IntegerRangeMap map;
416 :
417 : IntegerRangeMap::RangePair pair1(
418 E : IntegerRange(0, 10), IntegerRange(1000, 10));
419 : IntegerRangeMap::RangePair pair2(
420 E : IntegerRange(10, 10), IntegerRange(1010, 15));
421 : IntegerRangeMap::RangePair pair3(
422 E : IntegerRange(40, 10), IntegerRange(1040, 10));
423 E : ASSERT_TRUE(map.Push(pair1.first, pair1.second));
424 E : ASSERT_TRUE(map.Push(pair2.first, pair2.second));
425 E : ASSERT_TRUE(map.Push(pair3.first, pair3.second));
426 E : ASSERT_EQ(3u, map.size());
427 :
428 E : const IntegerRangeMap::RangePair* pair = map.FindRangePair(5, 3);
429 E : EXPECT_TRUE(pair != NULL);
430 E : EXPECT_EQ(pair1, *pair);
431 :
432 E : pair = map.FindRangePair(IntegerRange(40, 10));
433 E : EXPECT_TRUE(pair != NULL);
434 E : EXPECT_EQ(pair3, *pair);
435 :
436 E : EXPECT_EQ(NULL, map.FindRangePair(5, 10));
437 E : EXPECT_EQ(NULL, map.FindRangePair(IntegerRange(50, 1)));
438 E : EXPECT_EQ(NULL, map.FindRangePair(2, 0));
439 E : }
440 :
441 E : TEST(AddressRangeMapTest, IsMapped) {
442 E : IntegerRangeMap map;
443 E : EXPECT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
444 E : EXPECT_TRUE(map.Push(IntegerRange(10, 10), IntegerRange(1010, 15)));
445 E : EXPECT_TRUE(map.Push(IntegerRange(40, 10), IntegerRange(1040, 10)));
446 :
447 E : EXPECT_TRUE(map.IsMapped(5, 15));
448 E : EXPECT_TRUE(map.IsMapped(IntegerRange(45, 5)));
449 :
450 E : EXPECT_FALSE(map.IsMapped(15, 10));
451 :
452 E : EXPECT_FALSE(map.IsMapped(0, 0));
453 E : }
454 :
455 E : TEST(AddressRangeMapTest, InOrderPush) {
456 E : IntegerRangeMap map;
457 E : EXPECT_EQ(0u, map.size());
458 :
459 E : EXPECT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
460 E : EXPECT_EQ(1u, map.size());
461 :
462 E : EXPECT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
463 E : EXPECT_EQ(2u, map.size());
464 :
465 E : EXPECT_FALSE(map.Push(IntegerRange(15, 10), IntegerRange(1015, 10)));
466 E : EXPECT_FALSE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
467 E : EXPECT_FALSE(map.Push(IntegerRange(23, 2), IntegerRange(1023, 2)));
468 E : EXPECT_FALSE(map.Push(IntegerRange(25, 10), IntegerRange(1025, 10)));
469 :
470 E : EXPECT_TRUE(map.Push(IntegerRange(40, 10), IntegerRange(1040, 10)));
471 E : EXPECT_EQ(3u, map.size());
472 :
473 E : EXPECT_FALSE(map.Push(IntegerRange(0, 0), IntegerRange(1000, 1)));
474 E : EXPECT_FALSE(map.Push(IntegerRange(0, 1), IntegerRange(1000, 0)));
475 E : EXPECT_EQ(3u, map.size());
476 :
477 E : IntegerRangePairs expected;
478 : expected.push_back(
479 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
480 : expected.push_back(
481 E : IntegerRangePair(IntegerRange(20, 10), IntegerRange(1020, 10)));
482 : expected.push_back(
483 E : IntegerRangePair(IntegerRange(40, 10), IntegerRange(1040, 10)));
484 :
485 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
486 E : }
487 :
488 E : TEST(AddressRangeMapTest, OutOfOrderPush) {
489 E : IntegerRangeMap map;
490 E : EXPECT_EQ(0u, map.size());
491 :
492 E : EXPECT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
493 E : EXPECT_EQ(1u, map.size());
494 :
495 E : EXPECT_FALSE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
496 E : EXPECT_EQ(1u, map.size());
497 :
498 E : IntegerRangePairs expected;
499 : expected.push_back(
500 E : IntegerRangePair(IntegerRange(20, 10), IntegerRange(1020, 10)));
501 :
502 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
503 E : }
504 :
505 E : TEST(AddressRangeMapTest, InOrderPushAndMerge) {
506 E : IntegerRangeMap map;
507 E : EXPECT_EQ(0u, map.size());
508 :
509 E : EXPECT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
510 E : EXPECT_EQ(1u, map.size());
511 :
512 E : EXPECT_TRUE(map.Push(IntegerRange(10, 10), IntegerRange(1010, 10)));
513 E : EXPECT_EQ(1u, map.size());
514 :
515 E : IntegerRangePairs expected;
516 : expected.push_back(
517 E : IntegerRangePair(IntegerRange(0, 20), IntegerRange(1000, 20)));
518 :
519 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
520 E : }
521 :
522 E : TEST(AddressRangeMapTest, Insert) {
523 E : IntegerRangeMap map;
524 E : EXPECT_EQ(0u, map.size());
525 :
526 E : EXPECT_TRUE(map.Insert(IntegerRange(20, 10), IntegerRange(1020, 10)));
527 E : EXPECT_EQ(1u, map.size());
528 :
529 E : EXPECT_TRUE(map.Insert(IntegerRange(0, 10), IntegerRange(1000, 10)));
530 E : EXPECT_EQ(2u, map.size());
531 :
532 E : EXPECT_TRUE(map.Insert(IntegerRange(40, 10), IntegerRange(1040, 10)));
533 E : EXPECT_EQ(3u, map.size());
534 :
535 : // Attempting to insert a subset of an existing range should fail.
536 E : EXPECT_FALSE(map.Insert(IntegerRange(5, 2), IntegerRange(1005, 2)));
537 E : EXPECT_EQ(3u, map.size());
538 :
539 : // Attempting to insert an existing range should fail.
540 E : EXPECT_FALSE(map.Insert(IntegerRange(0, 10), IntegerRange(1000, 10)));
541 E : EXPECT_EQ(3u, map.size());
542 :
543 : // Attempting to insert an overlapping range should fail.
544 E : EXPECT_FALSE(map.Insert(IntegerRange(5, 10), IntegerRange(1005, 10)));
545 E : EXPECT_EQ(3u, map.size());
546 :
547 : // Inserting a contiguous range at end should merge with previous.
548 E : EXPECT_TRUE(map.Insert(IntegerRange(50, 10), IntegerRange(1050, 10)));
549 E : EXPECT_EQ(3u, map.size());
550 :
551 : // Inserting empty ranges should do nothing.
552 E : EXPECT_FALSE(map.Insert(IntegerRange(0, 0), IntegerRange(1000, 1)));
553 E : EXPECT_FALSE(map.Insert(IntegerRange(0, 1), IntegerRange(1000, 0)));
554 E : EXPECT_EQ(3u, map.size());
555 :
556 E : IntegerRangePairs expected;
557 : expected.push_back(
558 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
559 : expected.push_back(
560 E : IntegerRangePair(IntegerRange(20, 10), IntegerRange(1020, 10)));
561 : expected.push_back(
562 E : IntegerRangePair(IntegerRange(40, 20), IntegerRange(1040, 20)));
563 :
564 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
565 E : }
566 :
567 E : TEST(AddressRangeMapTest, InsertAndLeftMerge) {
568 E : IntegerRangeMap map;
569 E : EXPECT_EQ(0u, map.size());
570 :
571 E : EXPECT_TRUE(map.Insert(IntegerRange(20, 10), IntegerRange(1020, 10)));
572 E : EXPECT_EQ(1u, map.size());
573 :
574 E : EXPECT_TRUE(map.Insert(IntegerRange(0, 10), IntegerRange(1000, 10)));
575 E : EXPECT_EQ(2u, map.size());
576 :
577 E : EXPECT_TRUE(map.Insert(IntegerRange(10, 5), IntegerRange(1010, 5)));
578 E : EXPECT_EQ(2u, map.size());
579 :
580 E : IntegerRangePairs expected;
581 : expected.push_back(
582 E : IntegerRangePair(IntegerRange(0, 15), IntegerRange(1000, 15)));
583 : expected.push_back(
584 E : IntegerRangePair(IntegerRange(20, 10), IntegerRange(1020, 10)));
585 :
586 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
587 E : }
588 :
589 E : TEST(AddressRangeMapTest, InsertAndRightMerge) {
590 E : IntegerRangeMap map;
591 E : EXPECT_EQ(0u, map.size());
592 :
593 E : EXPECT_TRUE(map.Insert(IntegerRange(20, 10), IntegerRange(1020, 10)));
594 E : EXPECT_EQ(1u, map.size());
595 :
596 E : EXPECT_TRUE(map.Insert(IntegerRange(0, 10), IntegerRange(1000, 10)));
597 E : EXPECT_EQ(2u, map.size());
598 :
599 E : EXPECT_TRUE(map.Insert(IntegerRange(15, 5), IntegerRange(1015, 5)));
600 E : EXPECT_EQ(2u, map.size());
601 :
602 E : IntegerRangePairs expected;
603 : expected.push_back(
604 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
605 : expected.push_back(
606 E : IntegerRangePair(IntegerRange(15, 15), IntegerRange(1015, 15)));
607 :
608 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
609 E : }
610 :
611 E : TEST(AddressRangeMapTest, InsertAndDoubleMerge) {
612 E : IntegerRangeMap map;
613 E : EXPECT_EQ(0u, map.size());
614 :
615 E : EXPECT_TRUE(map.Insert(IntegerRange(20, 10), IntegerRange(1020, 10)));
616 E : EXPECT_EQ(1u, map.size());
617 :
618 E : EXPECT_TRUE(map.Insert(IntegerRange(0, 10), IntegerRange(1000, 10)));
619 E : EXPECT_EQ(2u, map.size());
620 :
621 E : EXPECT_TRUE(map.Insert(IntegerRange(10, 10), IntegerRange(1010, 10)));
622 E : EXPECT_EQ(1u, map.size());
623 :
624 E : IntegerRangePairs expected;
625 : expected.push_back(
626 E : IntegerRangePair(IntegerRange(0, 30), IntegerRange(1000, 30)));
627 :
628 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
629 E : }
630 :
631 E : TEST(AddressRangeMapTest, Comparison) {
632 E : IntegerRangeMap map1;
633 E : IntegerRangeMap map2;
634 E : EXPECT_TRUE(map1 == map2);
635 E : EXPECT_FALSE(map1 != map2);
636 :
637 E : map1.Push(IntegerRange(0, 10), IntegerRange(1000, 10));
638 E : map2.Push(IntegerRange(0, 10), IntegerRange(1000, 10));
639 E : EXPECT_TRUE(map1 == map2);
640 E : EXPECT_FALSE(map1 != map2);
641 :
642 E : map1.Push(IntegerRange(20, 10), IntegerRange(1020, 10));
643 E : EXPECT_FALSE(map1 == map2);
644 E : EXPECT_TRUE(map1 != map2);
645 E : }
646 :
647 E : TEST(AddressRangeMapTest, Serialization) {
648 E : IntegerRangeMap map;
649 E : EXPECT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
650 E : EXPECT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
651 E : EXPECT_TRUE(map.Push(IntegerRange(40, 10), IntegerRange(1040, 10)));
652 :
653 E : EXPECT_TRUE(testing::TestSerialization(map));
654 E : }
655 :
656 E : TEST(AddressRangeMapTest, Clear) {
657 E : IntegerRangeMap map;
658 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
659 :
660 E : map.clear();
661 E : EXPECT_EQ(0u, map.size());
662 E : }
663 :
664 E : TEST(AddressRangeMapTest, ComputeInverse) {
665 E : IntegerRangeMap map;
666 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1020, 10)));
667 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1000, 10)));
668 :
669 E : IntegerRangePairs expected;
670 : expected.push_back(
671 E : IntegerRangePair(IntegerRange(1000, 10), IntegerRange(20, 10)));
672 : expected.push_back(
673 E : IntegerRangePair(IntegerRange(1020, 10), IntegerRange(0, 10)));
674 :
675 E : IntegerRangeMap imap;
676 E : EXPECT_EQ(0u, map.ComputeInverse(&imap));
677 E : EXPECT_THAT(expected, testing::ContainerEq(imap.range_pairs()));
678 :
679 E : IntegerRangeMap iimap;
680 E : EXPECT_EQ(0u, imap.ComputeInverse(&iimap));
681 E : EXPECT_EQ(map, iimap);
682 :
683 : // Test in-place inversion.
684 E : EXPECT_EQ(0u, iimap.ComputeInverse(&iimap));
685 E : EXPECT_EQ(imap, iimap);
686 E : }
687 :
688 E : TEST(AddressRangeMapTest, ComputeInverseWithConflicts) {
689 E : IntegerRangeMap map;
690 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
691 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1000, 10)));
692 :
693 E : IntegerRangePairs expected;
694 : expected.push_back(
695 E : IntegerRangePair(IntegerRange(1000, 10), IntegerRange(0, 10)));
696 :
697 E : IntegerRangeMap imap;
698 E : EXPECT_EQ(1u, map.ComputeInverse(&imap));
699 E : EXPECT_THAT(expected, testing::ContainerEq(imap.range_pairs()));
700 E : }
701 :
702 E : TEST(AddressRangeMapTest, InsertUnmappedAtStart) {
703 E : IntegerRangeMap map;
704 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
705 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
706 :
707 E : map.InsertUnmappedRange(IntegerRange(0, 10));
708 E : map.InsertUnmappedRange(IntegerRange(0, 0));
709 :
710 E : IntegerRangePairs expected;
711 : expected.push_back(
712 E : IntegerRangePair(IntegerRange(10, 10), IntegerRange(1000, 10)));
713 : expected.push_back(
714 E : IntegerRangePair(IntegerRange(30, 10), IntegerRange(1020, 10)));
715 :
716 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
717 E : }
718 :
719 E : TEST(AddressRangeMapTest, InsertUnmappedInMiddle) {
720 E : IntegerRangeMap map;
721 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
722 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
723 :
724 E : map.InsertUnmappedRange(IntegerRange(15, 5));
725 E : map.InsertUnmappedRange(IntegerRange(15, 0));
726 :
727 E : IntegerRangePairs expected;
728 : expected.push_back(
729 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
730 : expected.push_back(
731 E : IntegerRangePair(IntegerRange(25, 10), IntegerRange(1020, 10)));
732 :
733 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
734 E : }
735 :
736 E : TEST(AddressRangeMapTest, InsertUnmappedAfterEnd) {
737 E : IntegerRangeMap map;
738 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
739 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
740 :
741 E : map.InsertUnmappedRange(IntegerRange(30, 10));
742 E : map.InsertUnmappedRange(IntegerRange(30, 0));
743 :
744 E : IntegerRangePairs expected;
745 : expected.push_back(
746 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
747 : expected.push_back(
748 E : IntegerRangePair(IntegerRange(20, 10), IntegerRange(1020, 10)));
749 :
750 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
751 E : }
752 :
753 E : TEST(AddressRangeMapTest, InsertUnmappedSplit) {
754 E : IntegerRangeMap map;
755 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
756 :
757 E : map.InsertUnmappedRange(IntegerRange(5, 5));
758 E : map.InsertUnmappedRange(IntegerRange(5, 0));
759 :
760 E : IntegerRangePairs expected;
761 : expected.push_back(
762 E : IntegerRangePair(IntegerRange(0, 5), IntegerRange(1000, 5)));
763 : expected.push_back(
764 E : IntegerRangePair(IntegerRange(10, 5), IntegerRange(1005, 5)));
765 :
766 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
767 E : }
768 :
769 E : TEST(AddressRangeMapTest, InsertUnmappedSplitSingleton) {
770 E : IntegerRangeMap map;
771 E : ASSERT_TRUE(map.Push(IntegerRange(0, 2), IntegerRange(1000, 1)));
772 :
773 E : map.InsertUnmappedRange(IntegerRange(1, 1));
774 E : map.InsertUnmappedRange(IntegerRange(1, 0));
775 :
776 E : IntegerRangePairs expected;
777 : expected.push_back(
778 E : IntegerRangePair(IntegerRange(0, 1), IntegerRange(1000, 1)));
779 : expected.push_back(
780 E : IntegerRangePair(IntegerRange(2, 1), IntegerRange(1000, 1)));
781 :
782 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
783 E : }
784 :
785 E : TEST(AddressRangeMapTest, RemoveMappedNoData) {
786 E : IntegerRangeMap map;
787 :
788 E : map.RemoveMappedRange(IntegerRange(10, 10));
789 E : map.RemoveMappedRange(IntegerRange(10, 0));
790 :
791 E : EXPECT_TRUE(map.empty());
792 E : }
793 :
794 E : TEST(AddressRangeMapTest, RemoveMappedEmpty) {
795 E : IntegerRangeMap map;
796 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
797 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
798 :
799 E : map.RemoveMappedRange(IntegerRange(10, 10));
800 E : map.RemoveMappedRange(IntegerRange(10, 0));
801 :
802 E : IntegerRangePairs expected;
803 : expected.push_back(
804 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
805 : expected.push_back(
806 E : IntegerRangePair(IntegerRange(10, 10), IntegerRange(1020, 10)));
807 :
808 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
809 E : }
810 :
811 E : TEST(AddressRangeMapTest, RemoveMappedNoSplit) {
812 E : IntegerRangeMap map;
813 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
814 E : ASSERT_TRUE(map.Push(IntegerRange(15, 2), IntegerRange(1015, 2)));
815 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
816 :
817 E : map.RemoveMappedRange(IntegerRange(10, 10));
818 E : map.RemoveMappedRange(IntegerRange(10, 0));
819 :
820 E : IntegerRangePairs expected;
821 : expected.push_back(
822 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
823 : expected.push_back(
824 E : IntegerRangePair(IntegerRange(10, 10), IntegerRange(1020, 10)));
825 :
826 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
827 E : }
828 :
829 E : TEST(AddressRangeMapTest, RemoveMappedSplitLeft) {
830 E : IntegerRangeMap map;
831 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
832 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
833 :
834 E : map.RemoveMappedRange(IntegerRange(5, 10));
835 E : map.RemoveMappedRange(IntegerRange(5, 0));
836 :
837 E : IntegerRangePairs expected;
838 : expected.push_back(
839 E : IntegerRangePair(IntegerRange(0, 5), IntegerRange(1000, 5)));
840 : expected.push_back(
841 E : IntegerRangePair(IntegerRange(10, 10), IntegerRange(1020, 10)));
842 :
843 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
844 E : }
845 :
846 E : TEST(AddressRangeMapTest, RemoveMappedSplitRight) {
847 E : IntegerRangeMap map;
848 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
849 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
850 :
851 E : map.RemoveMappedRange(IntegerRange(15, 10));
852 E : map.RemoveMappedRange(IntegerRange(15, 0));
853 :
854 E : IntegerRangePairs expected;
855 : expected.push_back(
856 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
857 : expected.push_back(
858 E : IntegerRangePair(IntegerRange(15, 5), IntegerRange(1025, 5)));
859 :
860 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
861 E : }
862 :
863 E : TEST(AddressRangeMapTest, RemoveMappedSplitBoth) {
864 E : IntegerRangeMap map;
865 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
866 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
867 :
868 E : map.RemoveMappedRange(IntegerRange(5, 20));
869 E : map.RemoveMappedRange(IntegerRange(5, 0));
870 :
871 E : IntegerRangePairs expected;
872 : expected.push_back(
873 E : IntegerRangePair(IntegerRange(0, 5), IntegerRange(1000, 5)));
874 : expected.push_back(
875 E : IntegerRangePair(IntegerRange(5, 5), IntegerRange(1025, 5)));
876 :
877 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
878 E : }
879 :
880 E : TEST(AddressRangeMapTest, RemoveMappedSplitBothSingleton) {
881 E : IntegerRangeMap map;
882 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
883 :
884 E : map.RemoveMappedRange(IntegerRange(5, 2));
885 E : map.RemoveMappedRange(IntegerRange(5, 0));
886 :
887 E : IntegerRangePairs expected;
888 : expected.push_back(
889 E : IntegerRangePair(IntegerRange(0, 5), IntegerRange(1000, 5)));
890 : expected.push_back(
891 E : IntegerRangePair(IntegerRange(5, 3), IntegerRange(1007, 3)));
892 :
893 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
894 E : }
895 :
896 E : TEST(AddressRangeMapTest, RemoveMappedBeyondEnd) {
897 E : IntegerRangeMap map;
898 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
899 :
900 E : map.RemoveMappedRange(IntegerRange(10, 10));
901 E : map.RemoveMappedRange(IntegerRange(10, 0));
902 :
903 E : IntegerRangePairs expected;
904 : expected.push_back(
905 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
906 :
907 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
908 E : }
909 :
910 : } // namespace core
|