1 : // Copyright 2012 Google Inc.
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 subet 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 E : IntegerRangePairs expected;
560 : expected.push_back(
561 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
562 : expected.push_back(
563 E : IntegerRangePair(IntegerRange(20, 10), IntegerRange(1020, 10)));
564 : expected.push_back(
565 E : IntegerRangePair(IntegerRange(40, 10), IntegerRange(1040, 10)));
566 :
567 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
568 E : }
569 :
570 E : TEST(AddressRangeMapTest, InsertAndLeftMerge) {
571 E : IntegerRangeMap map;
572 E : EXPECT_EQ(0u, map.size());
573 :
574 E : EXPECT_TRUE(map.Insert(IntegerRange(20, 10), IntegerRange(1020, 10)));
575 E : EXPECT_EQ(1u, map.size());
576 :
577 E : EXPECT_TRUE(map.Insert(IntegerRange(0, 10), IntegerRange(1000, 10)));
578 E : EXPECT_EQ(2u, map.size());
579 :
580 E : EXPECT_TRUE(map.Insert(IntegerRange(10, 5), IntegerRange(1010, 5)));
581 E : EXPECT_EQ(2u, map.size());
582 :
583 E : IntegerRangePairs expected;
584 : expected.push_back(
585 E : IntegerRangePair(IntegerRange(0, 15), IntegerRange(1000, 15)));
586 : expected.push_back(
587 E : IntegerRangePair(IntegerRange(20, 10), IntegerRange(1020, 10)));
588 :
589 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
590 E : }
591 :
592 E : TEST(AddressRangeMapTest, InsertAndRightMerge) {
593 E : IntegerRangeMap map;
594 E : EXPECT_EQ(0u, map.size());
595 :
596 E : EXPECT_TRUE(map.Insert(IntegerRange(20, 10), IntegerRange(1020, 10)));
597 E : EXPECT_EQ(1u, map.size());
598 :
599 E : EXPECT_TRUE(map.Insert(IntegerRange(0, 10), IntegerRange(1000, 10)));
600 E : EXPECT_EQ(2u, map.size());
601 :
602 E : EXPECT_TRUE(map.Insert(IntegerRange(15, 5), IntegerRange(1015, 5)));
603 E : EXPECT_EQ(2u, map.size());
604 :
605 E : IntegerRangePairs expected;
606 : expected.push_back(
607 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
608 : expected.push_back(
609 E : IntegerRangePair(IntegerRange(15, 15), IntegerRange(1015, 15)));
610 :
611 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
612 E : }
613 :
614 E : TEST(AddressRangeMapTest, InsertAndDoubleMerge) {
615 E : IntegerRangeMap map;
616 E : EXPECT_EQ(0u, map.size());
617 :
618 E : EXPECT_TRUE(map.Insert(IntegerRange(20, 10), IntegerRange(1020, 10)));
619 E : EXPECT_EQ(1u, map.size());
620 :
621 E : EXPECT_TRUE(map.Insert(IntegerRange(0, 10), IntegerRange(1000, 10)));
622 E : EXPECT_EQ(2u, map.size());
623 :
624 E : EXPECT_TRUE(map.Insert(IntegerRange(10, 10), IntegerRange(1010, 10)));
625 E : EXPECT_EQ(1u, map.size());
626 :
627 E : IntegerRangePairs expected;
628 : expected.push_back(
629 E : IntegerRangePair(IntegerRange(0, 30), IntegerRange(1000, 30)));
630 :
631 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
632 E : }
633 :
634 E : TEST(AddressRangeMapTest, Comparison) {
635 E : IntegerRangeMap map1;
636 E : IntegerRangeMap map2;
637 E : EXPECT_TRUE(map1 == map2);
638 E : EXPECT_FALSE(map1 != map2);
639 :
640 E : map1.Push(IntegerRange(0, 10), IntegerRange(1000, 10));
641 E : map2.Push(IntegerRange(0, 10), IntegerRange(1000, 10));
642 E : EXPECT_TRUE(map1 == map2);
643 E : EXPECT_FALSE(map1 != map2);
644 :
645 E : map1.Push(IntegerRange(20, 10), IntegerRange(1020, 10));
646 E : EXPECT_FALSE(map1 == map2);
647 E : EXPECT_TRUE(map1 != map2);
648 E : }
649 :
650 E : TEST(AddressRangeMapTest, Serialization) {
651 E : IntegerRangeMap map;
652 E : EXPECT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
653 E : EXPECT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
654 E : EXPECT_TRUE(map.Push(IntegerRange(40, 10), IntegerRange(1040, 10)));
655 :
656 E : EXPECT_TRUE(testing::TestSerialization(map));
657 E : }
658 :
659 E : TEST(AddressRangeMapTest, Clear) {
660 E : IntegerRangeMap map;
661 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
662 :
663 E : map.clear();
664 E : EXPECT_EQ(0u, map.size());
665 E : }
666 :
667 E : TEST(AddressRangeMapTest, ComputeInverse) {
668 E : IntegerRangeMap map;
669 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1020, 10)));
670 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1000, 10)));
671 :
672 E : IntegerRangePairs expected;
673 : expected.push_back(
674 E : IntegerRangePair(IntegerRange(1000, 10), IntegerRange(20, 10)));
675 : expected.push_back(
676 E : IntegerRangePair(IntegerRange(1020, 10), IntegerRange(0, 10)));
677 :
678 E : IntegerRangeMap imap;
679 E : EXPECT_EQ(0u, map.ComputeInverse(&imap));
680 E : EXPECT_THAT(expected, testing::ContainerEq(imap.range_pairs()));
681 :
682 E : IntegerRangeMap iimap;
683 E : EXPECT_EQ(0u, imap.ComputeInverse(&iimap));
684 E : EXPECT_EQ(map, iimap);
685 :
686 : // Test in-place inversion.
687 E : EXPECT_EQ(0u, iimap.ComputeInverse(&iimap));
688 E : EXPECT_EQ(imap, iimap);
689 E : }
690 :
691 E : TEST(AddressRangeMapTest, ComputeInverseWithConflicts) {
692 E : IntegerRangeMap map;
693 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
694 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1000, 10)));
695 :
696 E : IntegerRangePairs expected;
697 : expected.push_back(
698 E : IntegerRangePair(IntegerRange(1000, 10), IntegerRange(0, 10)));
699 :
700 E : IntegerRangeMap imap;
701 E : EXPECT_EQ(1u, map.ComputeInverse(&imap));
702 E : EXPECT_THAT(expected, testing::ContainerEq(imap.range_pairs()));
703 E : }
704 :
705 E : TEST(AddressRangeMapTest, InsertUnmappedAtStart) {
706 E : IntegerRangeMap map;
707 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
708 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
709 :
710 E : map.InsertUnmappedRange(IntegerRange(0, 10));
711 :
712 E : IntegerRangePairs expected;
713 : expected.push_back(
714 E : IntegerRangePair(IntegerRange(10, 10), IntegerRange(1000, 10)));
715 : expected.push_back(
716 E : IntegerRangePair(IntegerRange(30, 10), IntegerRange(1020, 10)));
717 :
718 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
719 E : }
720 :
721 E : TEST(AddressRangeMapTest, InsertUnmappedInMiddle) {
722 E : IntegerRangeMap map;
723 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
724 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
725 :
726 E : map.InsertUnmappedRange(IntegerRange(15, 5));
727 :
728 E : IntegerRangePairs expected;
729 : expected.push_back(
730 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
731 : expected.push_back(
732 E : IntegerRangePair(IntegerRange(25, 10), IntegerRange(1020, 10)));
733 :
734 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
735 E : }
736 :
737 E : TEST(AddressRangeMapTest, InsertUnmappedAfterEnd) {
738 E : IntegerRangeMap map;
739 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
740 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
741 :
742 E : map.InsertUnmappedRange(IntegerRange(30, 10));
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 :
759 E : IntegerRangePairs expected;
760 : expected.push_back(
761 E : IntegerRangePair(IntegerRange(0, 5), IntegerRange(1000, 5)));
762 : expected.push_back(
763 E : IntegerRangePair(IntegerRange(10, 5), IntegerRange(1005, 5)));
764 :
765 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
766 E : }
767 :
768 E : TEST(AddressRangeMapTest, InsertUnmappedSplitSingleton) {
769 E : IntegerRangeMap map;
770 E : ASSERT_TRUE(map.Push(IntegerRange(0, 2), IntegerRange(1000, 1)));
771 :
772 E : map.InsertUnmappedRange(IntegerRange(1, 1));
773 :
774 E : IntegerRangePairs expected;
775 : expected.push_back(
776 E : IntegerRangePair(IntegerRange(0, 1), IntegerRange(1000, 1)));
777 : expected.push_back(
778 E : IntegerRangePair(IntegerRange(2, 1), IntegerRange(1000, 1)));
779 :
780 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
781 E : }
782 :
783 E : TEST(AddressRangeMapTest, RemoveMappedNoData) {
784 E : IntegerRangeMap map;
785 :
786 E : map.RemoveMappedRange(IntegerRange(10, 10));
787 :
788 E : EXPECT_TRUE(map.empty());
789 E : }
790 :
791 E : TEST(AddressRangeMapTest, RemoveMappedEmpty) {
792 E : IntegerRangeMap map;
793 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
794 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
795 :
796 E : map.RemoveMappedRange(IntegerRange(10, 10));
797 :
798 E : IntegerRangePairs expected;
799 : expected.push_back(
800 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
801 : expected.push_back(
802 E : IntegerRangePair(IntegerRange(10, 10), IntegerRange(1020, 10)));
803 :
804 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
805 E : }
806 :
807 E : TEST(AddressRangeMapTest, RemoveMappedNoSplit) {
808 E : IntegerRangeMap map;
809 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
810 E : ASSERT_TRUE(map.Push(IntegerRange(15, 2), IntegerRange(1015, 2)));
811 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
812 :
813 E : map.RemoveMappedRange(IntegerRange(10, 10));
814 :
815 E : IntegerRangePairs expected;
816 : expected.push_back(
817 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
818 : expected.push_back(
819 E : IntegerRangePair(IntegerRange(10, 10), IntegerRange(1020, 10)));
820 :
821 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
822 E : }
823 :
824 E : TEST(AddressRangeMapTest, RemoveMappedSplitLeft) {
825 E : IntegerRangeMap map;
826 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
827 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
828 :
829 E : map.RemoveMappedRange(IntegerRange(5, 10));
830 :
831 E : IntegerRangePairs expected;
832 : expected.push_back(
833 E : IntegerRangePair(IntegerRange(0, 5), IntegerRange(1000, 5)));
834 : expected.push_back(
835 E : IntegerRangePair(IntegerRange(10, 10), IntegerRange(1020, 10)));
836 :
837 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
838 E : }
839 :
840 E : TEST(AddressRangeMapTest, RemoveMappedSplitRight) {
841 E : IntegerRangeMap map;
842 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
843 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
844 :
845 E : map.RemoveMappedRange(IntegerRange(15, 10));
846 :
847 E : IntegerRangePairs expected;
848 : expected.push_back(
849 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
850 : expected.push_back(
851 E : IntegerRangePair(IntegerRange(15, 5), IntegerRange(1025, 5)));
852 :
853 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
854 E : }
855 :
856 E : TEST(AddressRangeMapTest, RemoveMappedSplitBoth) {
857 E : IntegerRangeMap map;
858 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
859 E : ASSERT_TRUE(map.Push(IntegerRange(20, 10), IntegerRange(1020, 10)));
860 :
861 E : map.RemoveMappedRange(IntegerRange(5, 20));
862 :
863 E : IntegerRangePairs expected;
864 : expected.push_back(
865 E : IntegerRangePair(IntegerRange(0, 5), IntegerRange(1000, 5)));
866 : expected.push_back(
867 E : IntegerRangePair(IntegerRange(5, 5), IntegerRange(1025, 5)));
868 :
869 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
870 E : }
871 :
872 E : TEST(AddressRangeMapTest, RemoveMappedSplitBothSingleton) {
873 E : IntegerRangeMap map;
874 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
875 :
876 E : map.RemoveMappedRange(IntegerRange(5, 2));
877 :
878 E : IntegerRangePairs expected;
879 : expected.push_back(
880 E : IntegerRangePair(IntegerRange(0, 5), IntegerRange(1000, 5)));
881 : expected.push_back(
882 E : IntegerRangePair(IntegerRange(5, 3), IntegerRange(1007, 3)));
883 :
884 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
885 E : }
886 :
887 E : TEST(AddressRangeMapTest, RemoveMappedBeyondEnd) {
888 E : IntegerRangeMap map;
889 E : ASSERT_TRUE(map.Push(IntegerRange(0, 10), IntegerRange(1000, 10)));
890 :
891 E : map.RemoveMappedRange(IntegerRange(10, 10));
892 :
893 E : IntegerRangePairs expected;
894 : expected.push_back(
895 E : IntegerRangePair(IntegerRange(0, 10), IntegerRange(1000, 10)));
896 :
897 E : EXPECT_THAT(expected, testing::ContainerEq(map.range_pairs()));
898 E : }
899 :
900 : } // namespace core
|