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