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