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 : // Declares AddressRange, AddressSpace and AddressRangeMap. AddressRange is
16 : // a primitive used by AddressSpace and AddressRangeMap. AddressSpace is useful
17 : // for maintaining a collection of objects that map to ranges of bytes in some
18 : // finite address-space, ensuring that they do not collide. An AddressRangeMap
19 : // is a specialized version of an AddressSpace where the stored objects are
20 : // themselves AddressRanges, with special semantics for simplifying the
21 : // representation.
22 :
23 : #ifndef SYZYGY_CORE_ADDRESS_SPACE_H_
24 : #define SYZYGY_CORE_ADDRESS_SPACE_H_
25 :
26 : #include <algorithm>
27 : #include <iosfwd>
28 : #include <map>
29 : #include <utility>
30 : #include <vector>
31 :
32 : #include "base/logging.h"
33 : #include "syzygy/core/address_space_internal.h"
34 : #include "syzygy/core/serialization.h"
35 :
36 : namespace core {
37 :
38 : // Forward declaration.
39 : template <typename AddressType, typename SizeType> class AddressRange;
40 :
41 : // An address space is a mapping from a set of non-overlapping address ranges
42 : // (AddressSpace::Range), each of non-zero size, to an ItemType.
43 : template <typename AddressType, typename SizeType, typename ItemType>
44 : class AddressSpace {
45 : public:
46 : // Typedef we use for convenience throughout.
47 : typedef AddressRange<AddressType, SizeType> Range;
48 : typedef std::map<Range, ItemType> RangeMap;
49 : typedef typename std::map<Range, ItemType>::iterator RangeMapIter;
50 : typedef typename std::map<Range, ItemType>::const_iterator RangeMapConstIter;
51 : typedef std::pair<RangeMapConstIter, RangeMapConstIter> RangeMapConstIterPair;
52 : typedef std::pair<RangeMapIter, RangeMapIter> RangeMapIterPair;
53 :
54 : // STL-like type definitions
55 : // @{
56 : typedef typename RangeMapIter iterator;
57 : typedef typename RangeMapConstIter const_iterator;
58 : typedef typename RangeMap::value_type value_type;
59 : // @}
60 :
61 : // Create an empty address space.
62 : AddressSpace();
63 :
64 : // Insert @p range mapping to @p item unless @p range intersects
65 : // an existing range.
66 : // @param range the range to insert.
67 : // @param item the item to associate with @p range.
68 : // @param ret_it on success, returns an iterator to the inserted item.
69 : // @returns true iff @p range inserted.
70 : bool Insert(const Range& range,
71 : const ItemType& item,
72 : typename RangeMap::iterator* ret_it = NULL);
73 :
74 : // Insert @p range mapping to @p item or return the existing item exactly
75 : // matching @p range.
76 : //
77 : // @param range the range of the item to get or insert.
78 : // @param item the item to associate with @p range if none already exists.
79 : // @param ret_it on success, returns an iterator to the found or inserted
80 : // item if not NULL.
81 : //
82 : // @returns true if the {range, item} pair is inserted or if there exists
83 : // an item exactly matching range; otherwise false, indicating that a
84 : // conflict/error has been detected.
85 : bool FindOrInsert(const Range& range,
86 : const ItemType& item,
87 : typename RangeMap::iterator* ret_it = NULL);
88 :
89 : // Inserts @p range mapping to @p item, unless @p range intersects
90 : // an existing range and does not contain it. Any existing ranges it contains
91 : // will be removed. If a range exists that contains @p range, returns true
92 : // and returns the iterator to that range.
93 : // @param range the range to insert.
94 : // @param item the item to associate with @p range.
95 : // @param ret_it on success, returns an iterator to the inserted item.
96 : // @returns true on success.
97 : //
98 : // Example insertions:
99 : //
100 : // Existing : aaaa bbbb
101 : // Inserting: xxxxxxxxxxxx
102 : // Result : cccccccccccc
103 : //
104 : // Existing : aaaaaa bbbbbb
105 : // Inserting: xxxxxxxxxx
106 : // Result : failure!
107 : bool SubsumeInsert(const Range& range,
108 : const ItemType& item,
109 : typename RangeMap::iterator* ret_it = NULL);
110 :
111 : // Inserts @p range mapping to @p item. If this range overlaps any existing
112 : // blocks, all of the overlapping blocks will be merged to form one single
113 : // block. This insertion can never fail. If @p ret_it is non-null, return the
114 : // iterator to the inserted block, or if @p range lies entirely within an
115 : // existing block, returns the iterator to that block.
116 : // @param range the range to insert.
117 : // @param item the item to associate with @p range.
118 : // @param ret_it on success, returns an iterator to the inserted item.
119 : //
120 : // Example insertions:
121 : //
122 : // Existing : aaaa bbbb
123 : // Inserting: xxxxxxxxxxxx
124 : // Result : cccccccccccc
125 : //
126 : // Existing : aaaaaa bbbbbb
127 : // Inserting: xxxxxxxxxx
128 : // Result : cccccccccccccc
129 : void MergeInsert(const Range& range,
130 : const ItemType& item,
131 : typename RangeMap::iterator* ret_it = NULL);
132 :
133 : // Remove the range that exactly matches @p range.
134 : // Returns true iff @p range is removed.
135 : bool Remove(const Range& range);
136 : // Remove the item at position @p it.
137 E : void Remove(RangeMapIter it) { ranges_.erase(it); }
138 : // Remove the items in the given range.
139 E : void Remove(RangeMapIterPair its) { ranges_.erase(its.first, its.second); }
140 E : void Remove(RangeMapIter it1, RangeMapIter it2) { ranges_.erase(it1, it2); }
141 : // Remove all items from the address space.
142 E : void Clear() { ranges_.clear(); }
143 :
144 E : const RangeMap& ranges() const { return ranges_; }
145 E : const bool empty() const { return ranges_.empty(); }
146 E : const size_t size() const { return ranges_.size(); }
147 :
148 : // Finds the first contained range that intersects @p range.
149 : RangeMapConstIter FindFirstIntersection(const Range& range) const;
150 : RangeMapIter FindFirstIntersection(const Range& range);
151 :
152 : // Caution must be taken in using the non-const version of these! It is up
153 : // to the user not to change the values of any underlying ranges so as to
154 : // invalidate the non-overlapping range property of the address space. The
155 : // non-const iterator access is only intended for deletion of entire ranges.
156 E : RangeMapConstIter begin() const { return ranges_.begin(); }
157 E : RangeMapIter begin() { return ranges_.begin(); }
158 E : RangeMapConstIter end() const { return ranges_.end(); }
159 E : RangeMapIter end() { return ranges_.end(); }
160 :
161 : // Returns a pair of iterators that iterate over all ranges
162 : // intersecting @p range.
163 : RangeMapConstIterPair FindIntersecting(const Range& range) const;
164 : RangeMapIterPair FindIntersecting(const Range& range);
165 :
166 : // Returns true if the given range intersects any range currently in the
167 : // address space.
168 : bool Intersects(const Range& range) const;
169 E : bool Intersects(AddressType address, SizeType size = 1) const {
170 E : return Intersects(Range(address, size));
171 E : }
172 :
173 : // Returns true if the given range is contained exactly in the address
174 : // space.
175 : bool ContainsExactly(const Range& range) const;
176 E : bool ContainsExactly(AddressType address, SizeType size = 1) const {
177 E : return ContainsExactly(Range(address, size));
178 E : }
179 :
180 : // Returns true if the given range is contained by exactly one range in the
181 : // address space.
182 : bool Contains(const Range& range) const;
183 E : bool Contains(AddressType address, SizeType size = 1) const {
184 E : return Contains(Range(address, size));
185 E : }
186 :
187 : // Finds the range that contains @p range.
188 : typename RangeMap::const_iterator FindContaining(const Range& range) const;
189 : typename RangeMap::iterator FindContaining(const Range& range);
190 :
191 : private:
192 : // Our ranges and their associated items.
193 : RangeMap ranges_;
194 : };
195 :
196 : // An address range has a start address and a size.
197 : // Both types must provide operator <, and it must be possible to
198 : // add a SizeType to an AddressType.
199 : template <typename AddressType, typename SizeType>
200 : class AddressRange {
201 : public:
202 : typedef AddressType Address;
203 : typedef SizeType Size;
204 :
205 E : AddressRange() : start_(0), size_(0) {
206 E : }
207 :
208 : AddressRange(const AddressType &start, const SizeType& size)
209 E : : start_(start), size_(size) {
210 E : }
211 :
212 : AddressRange(const AddressRange &other)
213 E : : start_(other.start_), size_(other.size_) {
214 E : }
215 :
216 E : void operator=(const AddressRange &other) {
217 E : start_ = other.start_;
218 E : size_ = other.size_;
219 E : }
220 :
221 : // @returns true if this range is empty.
222 E : bool IsEmpty() const { return size_ == 0; }
223 :
224 : // Determines if a given address range is contained within this range.
225 : // @param other The range to check.
226 : // @param addr Start address of the range to check.
227 : // @param size The size of the other range to check.
228 : // @returns true iff @p other is contained within this range.
229 E : bool Contains(const AddressRange& other) const {
230 E : if (other.start_ < start_ || other.end() > end())
231 E : return false;
232 :
233 E : return true;
234 E : }
235 E : bool Contains(AddressType addr, SizeType size = 1) const {
236 E : return Contains(AddressRange(addr, size));
237 E : }
238 :
239 : // Determines if a given range intersects this range.
240 : // @param other The range to test.
241 : // @param addr Start address of the range to check.
242 : // @param size The size of the other range to check.
243 : // @returns true iff @p other intersects this range.
244 E : bool Intersects(const AddressRange& other) const {
245 E : if (other.end() <= start_ || other.start_ >= end())
246 E : return false;
247 :
248 E : return true;
249 E : }
250 : bool Intersects(AddressType addr, SizeType size = 1) const {
251 : return Intersects(AddressRange(addr, size));
252 : }
253 :
254 : // @name Comparison operators. These are for the purposes of the map that we
255 : // use for tracking the address space.
256 : // @{
257 E : bool operator<(const AddressRange& other) const {
258 : // This assumes the Address and Size types provide operator <.
259 E : return internal::CompleteAddressRangeLess<AddressRange>()(*this, other);
260 E : }
261 :
262 E : bool operator==(const AddressRange& other) const {
263 : // If neither is less, they have to be equal. That is, they conflict as
264 : // far as the address-space is concerned.
265 E : return !(other < *this) && !(*this < other);
266 E : }
267 :
268 E : bool operator!=(const AddressRange& other) const {
269 E : return !operator==(other);
270 E : }
271 : // @}
272 :
273 E : AddressType start() const { return start_; }
274 E : AddressType end() const { return start_ + size_; }
275 E : SizeType size() const { return size_; }
276 :
277 E : bool Save(OutArchive* out_archive) const {
278 E : DCHECK(out_archive != NULL);
279 E : return out_archive->Save(start_) && out_archive->Save(size_);
280 E : }
281 :
282 E : bool Load(InArchive* in_archive) {
283 E : DCHECK(in_archive != NULL);
284 E : return in_archive->Load(&start_) && in_archive->Load(&size_);
285 E : }
286 :
287 : private:
288 : // Start of address range.
289 : AddressType start_;
290 : // Size of address range.
291 : SizeType size_;
292 : };
293 :
294 : // An AddressRangeMap is used for keeping track of data in one address space
295 : // that has some relationship with data in another address space. Mappings are
296 : // stored as pairs of addresses, one from the 'source' address-space and one
297 : // from the 'destination' address-space. The ranges are sorted based on the
298 : // source ranges, and the source ranges must be disjoint. The data structure
299 : // ensures that the representation used is minimal in the following sense:
300 : // a pair of address-range mappings that have the same size in both images and
301 : // are consecutive in each image will be merged. For example, consider a
302 : // mapping containing the two pairs of ranges:
303 : //
304 : // [0, 10) maps to [1000, 1010), and
305 : // [10, 30) maps to [1010, 1030).
306 : //
307 : // This is more succinctly represented as (assuming linearity of the underlying
308 : // relationship):
309 : //
310 : // [0, 30) maps to [1000, 1030).
311 : //
312 : // However, a pair of mappings like:
313 : //
314 : // [0, 10) maps to [1000, 1010), and
315 : // [10, 30) maps to [1010, 1036)
316 : //
317 : // should not be merged, as even though they are contiguous in both address
318 : // spaces, the source and destination ranges are not of the same size for the
319 : // second pair. Thus, we can't imply that the relationship holds for the pair
320 : // [0, 30) and [1000, 1036).
321 : template <typename SourceRangeType, typename DestinationRangeType>
322 : class AddressRangeMap {
323 : public:
324 : typedef SourceRangeType SourceRange;
325 : typedef DestinationRangeType DestinationRange;
326 : typedef std::pair<SourceRange, DestinationRange> RangePair;
327 : typedef std::vector<RangePair> RangePairs;
328 :
329 E : const RangePairs& range_pairs() const { return range_pairs_; }
330 E : const RangePair& range_pair(size_t i) const { return range_pairs_[i]; }
331 E : void clear() { range_pairs_.clear(); }
332 E : bool empty() const { return range_pairs_.empty(); }
333 E : size_t size() const { return range_pairs_.size(); }
334 :
335 E : bool operator==(const AddressRangeMap& other) const {
336 E : return range_pairs_ == other.range_pairs_;
337 E : }
338 :
339 E : bool operator!=(const AddressRangeMap& other) const {
340 E : return range_pairs_ != other.range_pairs_;
341 E : }
342 :
343 : // Determines if this is a simple mapping.
344 : //
345 : // A mapping is simple if there exists exactly one range, and the sizes of the
346 : // source and destination ranges are identical.
347 : //
348 : // @returns true if this mapping is simple, false otherwise.
349 E : bool IsSimple() const {
350 : return range_pairs_.size() == 1 &&
351 E : range_pairs_.front().first.size() == range_pairs_.front().second.size();
352 E : }
353 :
354 : // Given a source range finds the range pair that encompasses it, if it
355 : // exists.
356 : //
357 : // @param sec_range the source range to search for.
358 : // @returns a pointer to the range pair, or NULL if none exists.
359 : const RangePair* FindRangePair(const SourceRange& src_range) const;
360 :
361 : // Given a source range finds the range pair that encompasses it, if it
362 : // exists.
363 : //
364 : // @param start the beginning of the source range to search for.
365 : // @param size the size of the source range to search for.
366 : // @returns a pointer to the range pair, or NULL if none exists.
367 : const RangePair* FindRangePair(typename SourceRange::Address start,
368 E : typename SourceRange::Size size) const {
369 E : return FindRangePair(SourceRange(start, size));
370 E : }
371 :
372 : // Determines if the given source address range is fully mapped.
373 : //
374 : // @param src_range the source range to confirm.
375 : // @returns true if @p src_range is fully mapped, false otherwise.
376 : bool IsMapped(const SourceRange& src_range) const;
377 :
378 : // Determines if the given source address range is fully mapped.
379 : //
380 : // @param start the beginning of the source range to confirm.
381 : // @param size the size of the source range to confirm.
382 : // @returns true if the source range is fully mapped, false otherwise.
383 : bool IsMapped(typename SourceRange::Address start,
384 E : typename SourceRange::Size size) const {
385 E : return IsMapped(SourceRange(start, size));
386 E : }
387 :
388 : // Adds a new pair of ranges to the map.
389 : //
390 : // This method allows insertions at arbitrary locations, but may consequently
391 : // be slower as a reallocation may be required.
392 : //
393 : // @param src_range the source range of the mapping to be inserted.
394 : // @param dst_range the destination range of the mapping to be inserted.
395 : // @returns true on success, false otherwise.
396 : bool Insert(const SourceRange& src_range, const DestinationRange& dst_range);
397 :
398 : // Pushes a new pair of ranges to the tail end of the source address range.
399 : //
400 : // This method is amortized O(1) and is simpler than Insert if the mapping
401 : // is being created in sequential order in the source address space. This will
402 : // fail if @p src_range is not greater than all existing ranges.
403 : //
404 : // @param src_range the source range of the mapping to be inserted.
405 : // @param dst_range the destination range of the mapping to be inserted.
406 : // @returns true on success, false otherwise.
407 : bool Push(const SourceRange& src_range, const DestinationRange& dst_range);
408 :
409 : // Computes the inverse of this mapping, returning the number of address
410 : // ranges mappings that were unable to be inverted. If DestinationRange and
411 : // SourceRange are the same type this may be performed in-place.
412 : //
413 : // The inversion is deterministic. When conflicting destination ranges are
414 : // found, earlier start addresses and shorter lengths have priority.
415 : //
416 : // @param inverted a pointer to the AddressRangeMap that will be populated
417 : // with the inverted address range map.
418 : // @returns the number of conflicting address ranges that were unable to be
419 : // inverted.
420 : size_t ComputeInverse(
421 : AddressRangeMap<DestinationRange, SourceRange>* inverted) const;
422 :
423 : // Rejigs a mapping by changing the underlying address-space that is being
424 : // mapped. This inserts a range of unmapped data in the source range, pushing
425 : // all mapped ranges that are beyond the newly unmapped data. If a mapped
426 : // source range intersects the unmapped range being inserted, this mapping
427 : // is split. During a split, the first of the two split ranges will maintain
428 : // linearity when possible.
429 : //
430 : // For example, consider the following address range map (expressed as
431 : // [start, end) ranges):
432 : //
433 : // [0, 10) -> [1000, 1010), [20, 30) -> [1020, 1030)
434 : //
435 : // After inserting an unmapped range at offset 25 size 5 the mapping will be:
436 : //
437 : // [0, 10) -> [1000, 1010), [20, 25) -> [1020, 1025), [30, 35) -> [1025, 1030)
438 : //
439 : // Simple splitting can fail in a very unlikely edge case. Consider the case
440 : // where the source range has size N > 1 and the destination range has size 1.
441 : // Now consider splitting the source range. We only have one byte of
442 : // destination range, so how to split that into two? The only solution is to
443 : // duplicate the destination range, which may make the mapping no longer
444 : // invertible.
445 : //
446 : // @param unmapped the unmapped source range to insert.
447 : void InsertUnmappedRange(const SourceRange& unmapped);
448 :
449 : // Modifies a mapping by changing the underlying address-space that is being
450 : // mapped. This removes a source range, erasing any mappings over that range
451 : // and shifting all mappings beyond that range to the left, as necessary. If
452 : // any mappings intersect the range being removed they will be split in such a
453 : // way as to keep the individual mappings linear, if possible.
454 : //
455 : // For example, consider the following address range map (expressed as
456 : // [start, end) ranges):
457 : //
458 : // [0, 10) -> [1000, 1010), [20, 30) -> [1020, 1030)
459 : //
460 : // After removing the source range [5, 20), the mapping will be:
461 : //
462 : // [0, 5) -> [1000, 1005), [5, 15) -> [1020, 1030)
463 : //
464 : // @param mapped the mapped source range to remove.
465 : void RemoveMappedRange(const SourceRange& mapped);
466 :
467 : // For serialization.
468 E : bool Save(OutArchive* out_archive) const {
469 E : DCHECK(out_archive != NULL);
470 E : return out_archive->Save(range_pairs_);
471 E : }
472 E : bool Load(InArchive* in_archive) {
473 E : DCHECK(in_archive != NULL);
474 E : return in_archive->Load(&range_pairs_);
475 E : }
476 :
477 : private:
478 : // Runs a lower bound search with the provided src_range and a made up
479 : // destination range. The returned iterator either intersects src_range, is
480 : // strictly greater than it, or is 'end()'.
481 : typename RangePairs::const_iterator LowerBound(
482 : const SourceRange& src_range) const;
483 :
484 : // Stores the mapping.
485 : RangePairs range_pairs_;
486 : };
487 :
488 : template <typename AddressType, typename SizeType, typename ItemType>
489 E : AddressSpace<AddressType, SizeType, ItemType>::AddressSpace() {
490 E : }
491 :
492 : template <typename AddressType, typename SizeType, typename ItemType>
493 : bool AddressSpace<AddressType, SizeType, ItemType>::Insert(
494 : const Range& range,
495 : const ItemType& item,
496 E : typename RangeMap::iterator* ret_it) {
497 : // We can't insert empty ranges.
498 E : if (range.IsEmpty())
499 E : return false;
500 :
501 : // Is there an intersecting block?
502 E : RangeMap::iterator it = FindFirstIntersection(range);
503 E : if (it != ranges_.end())
504 E : return false;
505 :
506 : std::pair<RangeMap::iterator, bool> inserted =
507 E : ranges_.insert(std::make_pair(range, item));
508 E : DCHECK(inserted.second);
509 E : if (ret_it != NULL)
510 E : *ret_it = inserted.first;
511 :
512 E : return true;
513 E : }
514 :
515 : template <typename AddressType, typename SizeType, typename ItemType>
516 : bool AddressSpace<AddressType, SizeType, ItemType>::FindOrInsert(
517 : const Range& range,
518 : const ItemType& item,
519 E : typename RangeMap::iterator* ret_it) {
520 : // We can't insert empty ranges.
521 E : if (range.IsEmpty())
522 E : return false;
523 :
524 : // Is there already an existing block exactly matching that range? If so,
525 : // return it.
526 E : RangeMap::iterator it = FindFirstIntersection(range);
527 E : if (it != ranges_.end()) {
528 E : if (ret_it != NULL)
529 E : *ret_it = it;
530 E : return range == it->first && item == it->second;
531 : }
532 :
533 : std::pair<RangeMap::iterator, bool> inserted =
534 E : ranges_.insert(std::make_pair(range, item));
535 E : DCHECK(inserted.second);
536 E : if (ret_it != NULL)
537 E : *ret_it = inserted.first;
538 :
539 E : return true;
540 E : }
541 :
542 : template <typename AddressType, typename SizeType, typename ItemType>
543 : bool AddressSpace<AddressType, SizeType, ItemType>::SubsumeInsert(
544 : const Range& range,
545 : const ItemType& item,
546 E : typename RangeMap::iterator* ret_it) {
547 : // We can't insert empty ranges.
548 E : if (range.IsEmpty())
549 E : return false;
550 :
551 E : RangeMapIterPair its = FindIntersecting(range);
552 :
553 : // We only need to check how we intersect the first and last ranges; we
554 : // are guaranteed to subsume all others.
555 E : if (its.first != its.second) {
556 E : RangeMapIter it = its.first;
557 :
558 : // Check the first range.
559 E : DCHECK(range.Intersects(it->first));
560 : // We do not contain the first returned range?
561 E : if (!range.Contains(it->first)) {
562 : // We do not contain it, it does not contain us. We have a proper
563 : // intersection with them and the insertion fails.
564 E : if (!it->first.Contains(range))
565 E : return false;
566 :
567 : // They strictly contain us. There should be only one of them, and we
568 : // should return it.
569 E : DCHECK_EQ(1, std::distance(its.first, its.second));
570 E : if (ret_it != NULL)
571 i : *ret_it = its.first;
572 E : return true;
573 : }
574 :
575 : // We now check the second range. If we got here, the first range is a
576 : // proper subset of the range we're trying to add. We need to contain the
577 : // second range in order for the insertion to proceed. If we do not contain
578 : // it, we know it starts within our range, and finished outside of it and
579 : // therefore it is a proper intersection.
580 E : it = its.second;
581 E : --it;
582 E : DCHECK(range.Intersects(it->first));
583 E : if (!range.Contains(it->first))
584 E : return false;
585 : }
586 :
587 E : ranges_.erase(its.first, its.second);
588 :
589 : std::pair<RangeMap::iterator, bool> inserted =
590 E : ranges_.insert(std::make_pair(range, item));
591 E : DCHECK(inserted.second);
592 E : if (ret_it != NULL)
593 i : *ret_it = inserted.first;
594 :
595 E : return true;
596 E : }
597 :
598 : template <typename AddressType, typename SizeType, typename ItemType>
599 : void AddressSpace<AddressType, SizeType, ItemType>::MergeInsert(
600 : const Range& range,
601 : const ItemType& item,
602 E : typename RangeMap::iterator* ret_it) {
603 : // We can't insert empty ranges.
604 E : if (range.IsEmpty())
605 i : return;
606 :
607 E : RangeMapIterPair its = FindIntersecting(range);
608 :
609 E : AddressType start_addr = range.start();
610 E : size_t length = range.size();
611 :
612 : // Have overlap with existing blocks?
613 E : if (its.first != its.second) {
614 : // Find start address of new block. This is the min of the requested range,
615 : // or the beginning of the first intersecting block.
616 E : RangeMap::iterator it_first = its.first;
617 E : DCHECK(it_first != ranges_.end());
618 E : start_addr = std::min(range.start(), it_first->first.start());
619 :
620 : // Find end address of new block. This is the max of the requested range,
621 : // or the end of the last intersecting block.
622 E : RangeMap::iterator it_last = its.second;
623 E : --it_last;
624 E : DCHECK(it_last != ranges_.end());
625 E : AddressType end_addr = std::max(range.end(), it_last->first.end());
626 :
627 : // Erase the existing blocks.
628 E : length = end_addr - start_addr;
629 E : ranges_.erase(its.first, its.second);
630 : }
631 :
632 : // Insert the new block.
633 E : Range new_range(start_addr, length);
634 : std::pair<RangeMap::iterator, bool> inserted =
635 E : ranges_.insert(std::make_pair(new_range, item));
636 E : DCHECK(inserted.second);
637 E : if (ret_it != NULL)
638 i : *ret_it = inserted.first;
639 :
640 : return;
641 E : }
642 :
643 : template <typename AddressType, typename SizeType, typename ItemType>
644 E : bool AddressSpace<AddressType, SizeType, ItemType>::Remove(const Range& range) {
645 : // We can't remove empty ranges.
646 E : if (range.IsEmpty())
647 E : return false;
648 :
649 E : RangeMap::iterator it = ranges_.find(range);
650 E : if (it == ranges_.end())
651 E : return false;
652 :
653 E : ranges_.erase(it);
654 E : return true;
655 E : }
656 :
657 : template <typename AddressType, typename SizeType, typename ItemType>
658 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMap::const_iterator
659 : AddressSpace<AddressType, SizeType, ItemType>::FindFirstIntersection(
660 E : const Range& range) const {
661 E : return const_cast<AddressSpace*>(this)->FindFirstIntersection(range);
662 E : }
663 :
664 : template <typename AddressType, typename SizeType, typename ItemType>
665 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMap::iterator
666 : AddressSpace<AddressType, SizeType, ItemType>::FindFirstIntersection(
667 E : const Range& range) {
668 : // Empty items do not exist in the address-space.
669 E : if (range.IsEmpty())
670 E : return ranges_.end();
671 :
672 E : RangeMap::iterator it(ranges_.lower_bound(range));
673 :
674 : // There are three cases we need to handle here:
675 : // 1. An exact match.
676 E : if (it != ranges_.end() && it->first == range)
677 E : return it;
678 :
679 : // 2. Intersection with the next earlier (lower address or shorter) range.
680 : // Back up one if we can and test for intersection.
681 E : if (it != ranges_.begin()) {
682 E : RangeMap::iterator prev(it);
683 E : --prev;
684 :
685 E : if (prev->first.Intersects(range))
686 E : return prev;
687 : }
688 :
689 : // 3. Intersection to a/the found block.
690 E : if (it != ranges_.end() && it->first.Intersects(range))
691 E : return it;
692 :
693 E : return ranges_.end();
694 E : }
695 :
696 : template <typename AddressType, typename SizeType, typename ItemType>
697 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMapConstIterPair
698 : AddressSpace<AddressType, SizeType, ItemType>::FindIntersecting(
699 E : const Range& range) const {
700 E : return const_cast<AddressSpace*>(this)->FindIntersecting(range);
701 E : }
702 :
703 : template <typename AddressType, typename SizeType, typename ItemType>
704 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMapIterPair
705 : AddressSpace<AddressType, SizeType, ItemType>::FindIntersecting(
706 E : const Range& range) {
707 : // Empty ranges find nothing.
708 E : if (range.IsEmpty())
709 E : return std::make_pair(ranges_.end(), ranges_.end());
710 :
711 : // Find the start of the range first.
712 E : RangeMap::iterator begin(FindFirstIntersection(range));
713 :
714 : // Then the end.
715 : RangeMap::iterator end(ranges_.lower_bound(
716 E : Range(range.start() + range.size(), 1)));
717 :
718 : // Ensure that the relationship begin <= end holds, so that we may always
719 : // iterate over the returned range. It is possible that begin == end(),
720 : // and end != end(), which can cause problems. This is specifically the case
721 : // when there is no intersection with @p range, but that there is at least
722 : // one range beyond @p range.
723 E : if (begin == ranges_.end())
724 E : begin = end;
725 :
726 : // Since we search for the first range that starts at or after the end
727 : // of the input range, the range we find should never be intersecting.
728 E : DCHECK(end == ranges_.end() || !end->first.Intersects(range));
729 :
730 E : return std::make_pair(begin, end);
731 E : }
732 :
733 : template <typename AddressType, typename SizeType, typename ItemType>
734 : bool AddressSpace<AddressType, SizeType, ItemType>::Intersects(
735 E : const Range& range) const {
736 E : RangeMapConstIterPair its = FindIntersecting(range);
737 E : return (its.first != its.second);
738 E : }
739 :
740 : template <typename AddressType, typename SizeType, typename ItemType>
741 : bool AddressSpace<AddressType, SizeType, ItemType>::ContainsExactly(
742 E : const Range& range) const {
743 E : RangeMapConstIterPair its = FindIntersecting(range);
744 E : if (its.first == its.second)
745 E : return false;
746 E : return its.first->first == range;
747 E : }
748 :
749 : template <typename AddressType, typename SizeType, typename ItemType>
750 : bool AddressSpace<AddressType, SizeType, ItemType>::Contains(
751 E : const Range& range) const {
752 E : RangeMapConstIterPair its = FindIntersecting(range);
753 E : if (its.first == its.second)
754 E : return false;
755 E : return its.first->first.Contains(range);
756 E : }
757 :
758 : template <typename AddressType, typename SizeType, typename ItemType>
759 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMap::const_iterator
760 : AddressSpace<AddressType, SizeType, ItemType>::FindContaining(
761 E : const Range& range) const {
762 : // If there is a containing range, it must be the first intersection.
763 E : RangeMap::const_iterator it(FindFirstIntersection(range));
764 E : if (it != ranges_.end() && it->first.Contains(range))
765 E : return it;
766 :
767 E : return ranges_.end();
768 E : }
769 :
770 : template <typename AddressType, typename SizeType, typename ItemType>
771 : typename AddressSpace<AddressType, SizeType, ItemType>::RangeMap::iterator
772 : AddressSpace<AddressType, SizeType, ItemType>::FindContaining(
773 E : const Range& range) {
774 : // If there is a containing range, it must be the first intersection.
775 E : RangeMap::iterator it(FindFirstIntersection(range));
776 E : if (it != ranges_.end() && it->first.Contains(range))
777 E : return it;
778 :
779 E : return ranges_.end();
780 E : }
781 :
782 : template <typename SourceRangeType, typename DestinationRangeType>
783 : const std::pair<SourceRangeType, DestinationRangeType>*
784 : AddressRangeMap<SourceRangeType, DestinationRangeType>::FindRangePair(
785 E : const SourceRange& src_range) const {
786 : // No empty range exists in the mapping.
787 E : if (src_range.IsEmpty())
788 E : return NULL;
789 :
790 : // Find the first existing source range that is not less than src_range.
791 : // The returned iterator either intersects src_range, or is strictly greater
792 : // than it.
793 E : RangePairs::const_iterator it = LowerBound(src_range);
794 :
795 E : if (it == range_pairs_.end())
796 E : return NULL;
797 E : if (it->first.Contains(src_range))
798 E : return &(*it);
799 E : return NULL;
800 E : }
801 :
802 : template <typename SourceRangeType, typename DestinationRangeType>
803 : bool AddressRangeMap<SourceRangeType, DestinationRangeType>::IsMapped(
804 E : const SourceRange& src_range) const {
805 : // By definition no empty range is mapped.
806 E : if (src_range.IsEmpty())
807 E : return false;
808 :
809 : // Find the first existing source range that is not less than src_range.
810 : // The returned iterator either intersects src_range, or is strictly greater
811 : // than it.
812 E : RangePairs::const_iterator it = LowerBound(src_range);
813 :
814 : // Step through the successive mapped ranges and see if they cover src_range.
815 E : typename SourceRange::Address position = src_range.start();
816 E : while (true) {
817 : // No more mapped source ranges? Then src_range is not covered.
818 E : if (it == range_pairs_.end())
819 i : return false;
820 :
821 : // Is there an uncovered gap between position and the next mapped source
822 : // range? Then src_range is not covered.
823 E : if (position < it->first.start())
824 E : return false;
825 :
826 : // Step over this mapped source range and see if we're completely covered.
827 E : position = it->first.end();
828 E : if (position >= src_range.end())
829 E : return true;
830 :
831 E : ++it;
832 E : }
833 E : }
834 :
835 : template <typename SourceRangeType, typename DestinationRangeType>
836 : bool AddressRangeMap<SourceRangeType, DestinationRangeType>::Insert(
837 E : const SourceRange& src_range, const DestinationRange& dst_range) {
838 : // No empty ranges may be inserted in the mapping.
839 E : if (src_range.IsEmpty() || dst_range.IsEmpty())
840 E : return false;
841 :
842 : // Find the first existing source range that is not less than src_range.
843 : RangePairs::iterator it = std::lower_bound(
844 : range_pairs_.begin(),
845 : range_pairs_.end(),
846 : std::make_pair(src_range, dst_range),
847 E : internal::RangePairLess<SourceRange, DestinationRange>());
848 :
849 : // The search fell off the end of the vector? Push it to the back.
850 E : if (it == range_pairs_.end())
851 E : return Push(src_range, dst_range);
852 :
853 : // Does this source range overlap at all with the existing one?
854 E : if (it->first.Intersects(src_range))
855 E : return false;
856 :
857 : // At this point we know that 'it' points to a source range that is greater
858 : // than src_range. There are now 4 possibilities:
859 : // 1. It can be merged with the source range to the left, at 'it - 1'.
860 : // 2. It can be merged with the source range to the right, at 'it'.
861 : // 3. It can be merged with both the source range to the left and the right.
862 : // 4. It can't be merged at all, and needs to be inserted.
863 :
864 : // Determine in which directions we need to merge.
865 E : bool merge_left = false;
866 E : bool merge_right = false;
867 E : if (src_range.size() == dst_range.size()) {
868 : // If there is an element to the left, see if we can merge with it.
869 E : if (it != range_pairs_.begin()) {
870 E : RangePairs::iterator it_left = it - 1;
871 : if (it_left->first.size() == it_left->second.size() &&
872 : it_left->first.end() == src_range.start() &&
873 E : it_left->second.end() == dst_range.start()) {
874 E : merge_left = true;
875 : }
876 : }
877 :
878 : if (it->first.size() == it->second.size() &&
879 : src_range.end() == it->first.start() &&
880 E : dst_range.end() == it->second.start()) {
881 E : merge_right = true;
882 : }
883 : }
884 :
885 : // Don't need to change sizes because we're merging in only one direction?
886 E : if (merge_left != merge_right) {
887 E : SourceRange merged_src_range;
888 E : DestinationRange merged_dst_range;
889 E : if (merge_left) {
890 E : --it;
891 : merged_src_range = SourceRange(it->first.start(),
892 E : it->first.size() + src_range.size());
893 : merged_dst_range = DestinationRange(it->second.start(),
894 E : it->second.size() + dst_range.size());
895 E : } else {
896 : merged_src_range = SourceRange(src_range.start(),
897 E : src_range.size() + it->first.size());
898 : merged_dst_range = DestinationRange(dst_range.start(),
899 E : dst_range.size() + it->second.size());
900 : }
901 :
902 E : *it = std::make_pair(merged_src_range, merged_dst_range);
903 E : return true;
904 : }
905 :
906 : // Merging in both directions and shrinking?
907 E : if (merge_left && merge_right) {
908 E : RangePairs::iterator it_left = it - 1;
909 :
910 : SourceRange merged_src_range(
911 : it_left->first.start(),
912 E : it_left->first.size() + src_range.size() + it->first.size());
913 : DestinationRange merged_dst_range(
914 : it_left->second.start(),
915 E : it_left->second.size() + dst_range.size() + it->second.size());
916 :
917 E : *it_left = std::make_pair(merged_src_range, merged_dst_range);
918 E : range_pairs_.erase(it);
919 E : return true;
920 : }
921 :
922 : // If we get here then we're growing.
923 E : range_pairs_.insert(it, std::make_pair(src_range, dst_range));
924 E : return true;
925 E : }
926 :
927 : template <typename SourceRangeType, typename DestinationRangeType>
928 : bool AddressRangeMap<SourceRangeType, DestinationRangeType>::Push(
929 E : const SourceRange& src_range, const DestinationRange& dst_range) {
930 : // We can't insert empty ranges.
931 E : if (src_range.IsEmpty() || dst_range.IsEmpty())
932 E : return false;
933 :
934 E : if (!range_pairs_.empty()) {
935 E : SourceRange& last_src_range = range_pairs_.back().first;
936 :
937 : // If we already have RangePairs in the list, then src_range must be beyond
938 : // the last SourceRange.
939 E : if (!(last_src_range < src_range) || last_src_range.Intersects(src_range))
940 E : return false;
941 :
942 : // Can we merge this new pair of ranges with the existing last pair of
943 : // ranges?
944 E : DestinationRange& last_dst_range = range_pairs_.back().second;
945 : if (last_src_range.size() == last_dst_range.size() &&
946 : src_range.size() == dst_range.size() &&
947 : last_src_range.end() == src_range.start() &&
948 E : last_dst_range.end() == dst_range.start()) {
949 : last_src_range = SourceRange(
950 E : last_src_range.start(), last_src_range.size() + src_range.size());
951 : last_dst_range = DestinationRange(
952 E : last_dst_range.start(), last_dst_range.size() + dst_range.size());
953 E : return true;
954 : }
955 : }
956 :
957 E : range_pairs_.push_back(std::make_pair(src_range, dst_range));
958 E : return true;
959 E : }
960 :
961 : template <typename SourceRangeType, typename DestinationRangeType>
962 : size_t AddressRangeMap<SourceRangeType, DestinationRangeType>::ComputeInverse(
963 E : AddressRangeMap<DestinationRangeType, SourceRangeType>* inverted) const {
964 E : DCHECK(inverted != NULL);
965 :
966 : // Get a list of inverted range pairs.
967 : std::vector<std::pair<DestinationRangeType, SourceRangeType>>
968 E : inverted_range_pairs;
969 E : inverted_range_pairs.reserve(range_pairs_.size());
970 E : for (size_t i = 0; i < range_pairs_.size(); ++i) {
971 : inverted_range_pairs.push_back(
972 E : std::make_pair(range_pairs_[i].second, range_pairs_[i].first));
973 E : }
974 :
975 : // We sort these with a custom sort functor so that a total ordering is
976 : // defined rather than the default partial ordering defined by AddressRange.
977 : std::sort(inverted_range_pairs.begin(),
978 : inverted_range_pairs.end(),
979 : internal::CompleteAddressRangePairLess<DestinationRangeType,
980 E : SourceRangeType>());
981 :
982 : // Push these back to the inverted address range map and count the conflicts.
983 E : size_t conflicts = 0;
984 E : inverted->clear();
985 E : for (size_t i = 0; i < inverted_range_pairs.size(); ++i) {
986 : if (!inverted->Push(inverted_range_pairs[i].first,
987 E : inverted_range_pairs[i].second)) {
988 E : ++conflicts;
989 : }
990 E : }
991 :
992 E : return conflicts;
993 E : }
994 :
995 : template <typename SourceRangeType, typename DestinationRangeType>
996 : typename AddressRangeMap<SourceRangeType, DestinationRangeType>::RangePairs::
997 : const_iterator
998 : AddressRangeMap<SourceRangeType, DestinationRangeType>::LowerBound(
999 E : const SourceRange& src_range) const {
1000 : return std::lower_bound(
1001 : range_pairs_.begin(),
1002 : range_pairs_.end(),
1003 : std::make_pair(src_range,
1004 : // We have to manually create a valid DestinationRange with
1005 : // a size > 0.
1006 : DestinationRange(typename DestinationRange::Address(),
1007 : 1)),
1008 E : internal::RangePairLess<SourceRange, DestinationRange>());
1009 E : }
1010 :
1011 : template <typename SourceRangeType, typename DestinationRangeType>
1012 : void AddressRangeMap<SourceRangeType, DestinationRangeType>::
1013 E : InsertUnmappedRange(const SourceRange& unmapped) {
1014 : // Unmapping an empty range is a nop.
1015 E : if (unmapped.IsEmpty())
1016 E : return;
1017 :
1018 : typedef typename SourceRange::Size SrcSize;
1019 : typedef typename DestinationRange::Size DstSize;
1020 : typedef typename DestinationRange::Address DstAddr;
1021 :
1022 : // Walk backwards through the range pairs, fixing them as we go.
1023 E : for (size_t i = range_pairs_.size(); i > 0; --i) {
1024 E : RangePair& range_pair = range_pairs_[i - 1];
1025 E : SourceRange& src = range_pair.first;
1026 E : DestinationRange& dst = range_pair.second;
1027 :
1028 : // This range pair starts before the unmapped source range? We may have to
1029 : // split it, but we can stop looking at earlier ranges.
1030 E : if (src.start() < unmapped.start()) {
1031 : // Do we need a split?
1032 E : if (src.end() > unmapped.start()) {
1033 : SrcSize src_size_before =
1034 E : static_cast<SrcSize>(unmapped.start() - src.start());
1035 : SrcSize src_size_after =
1036 E : static_cast<SrcSize>(src.size() - src_size_before);
1037 :
1038 E : DstAddr dst_start_before = dst.start();
1039 E : DstSize dst_size_before = src_size_before;
1040 E : DstAddr dst_start_after(0);
1041 E : DstSize dst_size_after(0);
1042 :
1043 : // Special case: The destination size is 1, so indivisible. In this
1044 : // case we simply duplicate the destination range.
1045 E : if (dst.size() == 1) {
1046 E : dst_start_after = dst_start_before;
1047 E : dst_size_after = dst_size_before;
1048 E : } else {
1049 : // If the destination range is smaller than the source range, it is
1050 : // possible that dst_size_before consumes too much. In this case send
1051 : // as much as possible to the left (so it is as close to linear as
1052 : // possible), but leave some for the after the split.
1053 E : if (dst_size_before >= dst.size()) {
1054 i : dst_size_before = dst.size() - 1;
1055 i : dst_size_after = 1;
1056 : }
1057 :
1058 E : dst_start_after = dst_start_before + dst_size_before;
1059 E : dst_size_after = static_cast<DstSize>(dst.size() - dst_size_before);
1060 : }
1061 :
1062 : // Create the range for after the split.
1063 : RangePair pair_after(
1064 : SourceRange(src.start() + src_size_before + unmapped.size(),
1065 : src_size_after),
1066 E : DestinationRange(dst_start_after, dst_size_after));
1067 :
1068 : // Fix the existing pair, which is now the pair before the split.
1069 E : src = SourceRange(src.start(), src_size_before);
1070 E : dst = DestinationRange(dst_start_before, dst_size_before);
1071 :
1072 : // Insert the the new range. This invalidates range_pair, src and dst
1073 : // hence the need to do it at the very end.
1074 E : range_pairs_.insert(range_pairs_.begin() + i, pair_after);
1075 : }
1076 :
1077 E : return;
1078 : }
1079 :
1080 : // Shift this range to the right.
1081 E : src = SourceRange(src.start() + unmapped.size(), src.size());
1082 E : }
1083 E : }
1084 :
1085 : template <typename SourceRangeType, typename DestinationRangeType>
1086 : void AddressRangeMap<SourceRangeType, DestinationRangeType>::
1087 E : RemoveMappedRange(const SourceRange& mapped) {
1088 : // Removing an empty range is a nop.
1089 E : if (mapped.IsEmpty())
1090 E : return;
1091 :
1092 : typedef typename SourceRange::Size SrcSize;
1093 : typedef typename DestinationRange::Size DstSize;
1094 : typedef typename DestinationRange::Address DstAddr;
1095 :
1096 : // Special case: no source ranges to modify.
1097 E : if (range_pairs_.size() == 0)
1098 E : return;
1099 :
1100 : // Walk backwards through the range pairs, fixing them as we go.
1101 E : size_t i = range_pairs_.size();
1102 E : for (; i > 0; --i) {
1103 E : RangePair& range_pair = range_pairs_[i - 1];
1104 E : SourceRange& src = range_pair.first;
1105 E : DestinationRange& dst = range_pair.second;
1106 :
1107 : // This range pair starts before the end of the range we want to unmap?
1108 : // Then we've finished fixing ranges that simply need to be shifted.
1109 E : if (src.start() < mapped.end())
1110 E : break;
1111 :
1112 : // Shift this range to the left.
1113 E : src = SourceRange(src.start() - mapped.size(), src.size());
1114 E : }
1115 :
1116 : // At this point we've found the first range that is not beyond the
1117 : // end of mapped. Now we want to find the first range that is completely
1118 : // before mapped.
1119 E : size_t end_affected_ranges = i;
1120 E : for (; i > 0; --i) {
1121 E : RangePair& range_pair = range_pairs_[i - 1];
1122 E : SourceRange& src = range_pair.first;
1123 E : DestinationRange& dst = range_pair.second;
1124 :
1125 E : if (src.end() <= mapped.start())
1126 E : break;
1127 E : }
1128 E : size_t begin_affected_ranges = i;
1129 :
1130 : // It's possible that the affected ranges are off the end of the vector,
1131 : // in which case there is absolutely nothing to do.
1132 E : if (begin_affected_ranges >= range_pairs_.size())
1133 E : return;
1134 :
1135 : // At this point the ith through (end_affected_ranges - 1)th ranges intersect
1136 : // the range to be removed. The two endpoints may need to be split, but
1137 : // everything between them needs to be deleted. We inspect each endpoint and
1138 : // split them if need be.
1139 :
1140 : // Does the ith range need to split?
1141 E : if (range_pairs_[begin_affected_ranges].first.start() < mapped.start()) {
1142 E : RangePair& range_pair = range_pairs_[begin_affected_ranges];
1143 E : SourceRange& src = range_pair.first;
1144 E : DestinationRange& dst = range_pair.second;
1145 :
1146 E : SrcSize src_size_left = mapped.start() - src.start();
1147 E : DstSize dst_size_left = src_size_left;
1148 E : if (dst_size_left > dst.size())
1149 i : dst_size_left = dst.size();
1150 :
1151 : // Special case: this element needs to be both left split and right split.
1152 : if (begin_affected_ranges == end_affected_ranges - 1 &&
1153 E : mapped.end() < src.end()) {
1154 : // Split in such as way as to prefer linear mappings. If being linear on
1155 : // the left leaves no destination range on the right, shuffle a byte
1156 : // between the two.
1157 E : SrcSize src_size_right = src.end() - mapped.end();
1158 E : DstSize dst_size_right = src_size_right;
1159 E : if (dst_size_left + dst_size_right > dst.size()) {
1160 i : dst_size_right = dst.size() - dst_size_left;
1161 i : if (dst_size_right == 0) {
1162 i : ++dst_size_right;
1163 i : --dst_size_left;
1164 : }
1165 : }
1166 E : DCHECK_GT(dst_size_left, 0u);
1167 E : DCHECK_GT(dst_size_right, 0u);
1168 E : DCHECK_LE(dst_size_left + dst_size_right, dst.size());
1169 E : DstAddr dst_start_right = dst.end() - dst_size_right;
1170 :
1171 E : src = SourceRange(src.start(), src_size_left);
1172 E : dst = DestinationRange(dst.start(), dst_size_left);
1173 :
1174 : // We do this last as it invalidates src and dst.
1175 : range_pairs_.insert(
1176 : range_pairs_.begin() + begin_affected_ranges + 1,
1177 : std::make_pair(SourceRange(mapped.start(), src_size_right),
1178 E : DestinationRange(dst_start_right, dst_size_right)));
1179 :
1180 E : return;
1181 : }
1182 :
1183 E : src = SourceRange(src.start(), src_size_left);
1184 E : dst = DestinationRange(dst.start(), dst_size_left);
1185 E : ++begin_affected_ranges;
1186 : }
1187 :
1188 : // Does the (end_affected_ranges - 1)th range need to be split?
1189 E : if (range_pairs_[end_affected_ranges - 1].first.end() > mapped.end()) {
1190 E : RangePair& range_pair = range_pairs_[end_affected_ranges - 1];
1191 E : SourceRange& src = range_pair.first;
1192 E : DestinationRange& dst = range_pair.second;
1193 :
1194 E : SrcSize src_size = src.end() - mapped.end();
1195 E : DstSize dst_size = src_size;
1196 E : if (dst_size > dst.size())
1197 i : dst_size = dst.size();
1198 :
1199 E : src = SourceRange(src.end() - src_size - mapped.size(), src_size);
1200 E : dst = DestinationRange(dst.end() - dst_size, dst_size);
1201 E : --end_affected_ranges;
1202 : }
1203 :
1204 : // Now we have that the ranges [begin_affected_ranges, end_affected_ranges)
1205 : // need to simply be erased.
1206 E : if (begin_affected_ranges < end_affected_ranges)
1207 : range_pairs_.erase(range_pairs_.begin() + begin_affected_ranges,
1208 E : range_pairs_.begin() + end_affected_ranges);
1209 E : }
1210 :
1211 : // An ostream operator for AddressRanges.
1212 : template<typename AddressType, typename SizeType>
1213 : std::ostream& operator<<(
1214 : std::ostream& str,
1215 E : const AddressRange<AddressType, SizeType>& range) {
1216 E : str << "AddressRange(" << range.start() << ", " << range.size() << ")";
1217 E : return str;
1218 E : }
1219 :
1220 : } // namespace core
1221 :
1222 : #endif // SYZYGY_CORE_ADDRESS_SPACE_H_
|