ROSE
0.11.96.11
|
A container of ranges, somewhat like a set.
The container is able to hold non-overlapping ranges, each of which has some associated value attached to it. Arbitrary ranges can be inserted and erased from the RangeMap without regard to the ranges that are present in the map, since this class can merge and split values (through methods defined on the value) as necessary in order to maintain the non-overlapping invariant. Every attempt was made to optimize this class for storage and execution efficiency and usability. The interface is similar to the std::map interface.
In the simple case, when no data is attached to the ranges in the map, the RangeMap acts somewhat like an std::set with the following differences:
first
member is a Range (the second member is a RangeMapVoid instance with no useful data). Here's an example of using the RangeMap as a set. For every CPU instruction in a binary specimen, it adds the addresses of the instruction to the set. In some architectures, such as x86, the instructions might overlap; this approach correctly handles that.
A more complex example is using a RangeMap to store a value with each range. A simple example follows, where we want to build a RangeMap that associates any address with the function that owns that address, even when functions are discontiguous in the address space. The first step is to define the value type for the RangeMap we'll be using to store this:
Define an AST traversal add each instruction to the RangeMap:
Finally, traverse the AST and print the result. Because RangeMap merges adjacent ranges when possible, the output will contain the fewest number of ranges needed to describe the entire address space that's assigned to functions. Note that it's possible for two or more functions to "own" the same part of the address space if their instructions overlap, but since we defined our RangeMap to hold only one function pointer per address we'll see only the function that was added last for overlapping ranges.
The RangeMap class template can also be specialized to hold more complex values. The value type defines how ranges can be merged and split. RangeMap value types must implement the interface described for RangeMapVoid. Another example of a value type is RangeMapValue, that holds a simple scalar value and determines "mergeabiliy" and "splitability" based on the equality operator. Eventually, MemoryMap might also be rewritten in terms of RangeMap, and will have much more complex rules for merging, splitting, truncating, and removing.
Definition at line 852 of file rangemap.h.
#include <rangemap.h>
Classes | |
struct | RangeCompare |
The value attached to each range in this RangeMap. More... | |
Public Types | |
typedef R | Range |
typedef T | Value |
A type having the Range interface, used as keys in the underlying std::map. | |
typedef Map::iterator | iterator |
typedef Map::const_iterator | const_iterator |
typedef Map::reverse_iterator | reverse_iterator |
typedef Map::const_reverse_iterator | const_reverse_iterator |
Public Member Functions | |
RangeMap () | |
Create a new, empty map. | |
template<class Other > | |
RangeMap (const Other &other) | |
Create a new map from an existing map. | |
bool | empty () const |
Returns true if this RangeMap is empty. | |
size_t | nranges () const |
Returns the number of ranges in the range map. More... | |
Range::Value | size () const |
Returns the number of values represented by this RangeMap. More... | |
Range::Value | min () const |
Returns the minimum value in an extent map. More... | |
Range::Value | max () const |
Returns the maximum value in an extent map. More... | |
Range | minmax () const |
Returns the range of values in this map. | |
void | clear (bool notify=true) |
Clears the map. More... | |
void | erase (const Range &erase_range) |
Erases the specified range from this map. More... | |
template<class OtherMap > | |
void | erase_ranges (const OtherMap &other) |
Erase ranges from this map. More... | |
iterator | insert (Range new_range, Value new_value=Value(), bool make_hole=true) |
Insert a range/value pair into the map. More... | |
void | insert_ranges (const RangeMap &x, bool make_hole=true) |
Insert one rangemap into another. | |
void | insert_ranges (const_iterator start, const_iterator stop, bool make_hole=true) |
Insert part of one rangemap into another. More... | |
bool | overlaps (const RangeMap &x) const |
Determines if two range maps overlap. More... | |
bool | overlaps (const Range &r) const |
Determines if a range map overlaps with a specified range. More... | |
bool | distinct (const Range &r) const |
Determines if a range map does not contain any part of the specified range. More... | |
bool | distinct (const RangeMap &x) const |
Determines if two range maps are distinct. More... | |
bool | contains (Range need) const |
Determines if this range map contains all of the specified range. More... | |
bool | contains (const RangeMap &x) const |
Determins if this range map contains all of some other range map. More... | |
template<class ResultMap > | |
ResultMap | invert () const |
Create an inverse of a range map. More... | |
template<class ResultMap > | |
ResultMap | invert_within (const Range &limits) const |
Create a range map that's the inverse of some other map. More... | |
RangeMap | select_overlapping_ranges (const Range &selector) const |
Select ranges overlapping selector range. More... | |
void | check () const |
void | print (std::ostream &o) const |
Prints unformatted RangeMap on a single line. | |
iterator | begin () |
First-item iterator. More... | |
const_iterator | begin () const |
First-item iterator. More... | |
iterator | end () |
End-item iterator. More... | |
const_iterator | end () const |
End-item iterator. More... | |
reverse_iterator | rbegin () |
Returns a reverse iterator referring to the last item of the map, the rend() iterator if the RangeMap is empty. More... | |
const_reverse_iterator | rbegin () const |
Returns a reverse iterator referring to the last item of the map, the rend() iterator if the RangeMap is empty. More... | |
reverse_iterator | rend () |
Returns a reverse iterator referring to the element right before the first element in the map, which is considered its reverse end. More... | |
const_reverse_iterator | rend () const |
Returns a reverse iterator referring to the element right before the first element in the map, which is considered its reverse end. More... | |
iterator | find (const typename Range::Value &addr) |
Find the range containing specified value. More... | |
const_iterator | find (const typename Range::Value &addr) const |
Find the range containing specified value. More... | |
iterator | lower_bound (const typename Range::Value &addr) |
Finds the first range ending above the specified value. More... | |
const_iterator | lower_bound (const typename Range::Value &addr) const |
Finds the first range ending above the specified value. More... | |
iterator | find_prior (const typename Range::Value &addr) |
Finds the last range starting at or below the specified value. More... | |
const_iterator | find_prior (const typename Range::Value &addr) const |
Finds the last range starting at or below the specified value. More... | |
iterator | best_fit (const typename Range::Value &size, iterator start) |
Find range with closest size. More... | |
const_iterator | best_fit (const typename Range::Value &size, const_iterator start) const |
Find range with closest size. More... | |
iterator | first_fit (const typename Range::Value &size, iterator start) |
Find first range of larger size. More... | |
const_iterator | first_fit (const typename Range::Value &size, const_iterator start) |
Find first range of larger size. More... | |
iterator | find_overlap (const RangeMap &x) |
Find the first overlap between two RangeMap objects. More... | |
const_iterator | first_overlap (const RangeMap &x) const |
Find the first overlap between two RangeMap objects. More... | |
iterator | find_overlap (iterator start, iterator stop, const RangeMap &x) |
Find an overlap between two RangeMap objects. More... | |
const_iterator | find_overlap (const_iterator start, const_iterator stop, const RangeMap &x) const |
Find an overlap between two RangeMap objects. More... | |
Protected Types | |
typedef std::pair< Range, Range > | RangePair |
typedef std::pair< Range, Value > | MapPair |
typedef std::map< Range, Value, RangeCompare > | Map |
Protected Attributes | |
Map | ranges |
|
inline |
First-item iterator.
Returns an iterator for the first item, or the end iterator if the RangeMap is empty. The iterator is valid until any operation that changes the RangeMap, such as an insert or erase.
Definition at line 907 of file rangemap.h.
|
inline |
First-item iterator.
Returns an iterator for the first item, or the end iterator if the RangeMap is empty. The iterator is valid until any operation that changes the RangeMap, such as an insert or erase.
Definition at line 910 of file rangemap.h.
|
inline |
End-item iterator.
Returns an iterator to the one-past-last item of the RangeMap, regardless of whether the range map is empty. The iterator is valid until any operation that changes the RangeMap, such as an insert or erase.
Definition at line 919 of file rangemap.h.
Referenced by RangeMap< R, T >::select_overlapping_ranges().
|
inline |
End-item iterator.
Returns an iterator to the one-past-last item of the RangeMap, regardless of whether the range map is empty. The iterator is valid until any operation that changes the RangeMap, such as an insert or erase.
Definition at line 922 of file rangemap.h.
|
inline |
Returns a reverse iterator referring to the last item of the map, the rend() iterator if the RangeMap is empty.
The iterator is valid until any operation that changes the RangeMap, such as an insert or erase.
Definition at line 931 of file rangemap.h.
|
inline |
Returns a reverse iterator referring to the last item of the map, the rend() iterator if the RangeMap is empty.
The iterator is valid until any operation that changes the RangeMap, such as an insert or erase.
Definition at line 934 of file rangemap.h.
|
inline |
Returns a reverse iterator referring to the element right before the first element in the map, which is considered its reverse end.
Notice that rend() does not refer to the same element as begin(), but to the element right before it. The iterator is valid until any operation that changes the RangeMap, such as an insert or erase.
Definition at line 944 of file rangemap.h.
|
inline |
Returns a reverse iterator referring to the element right before the first element in the map, which is considered its reverse end.
Notice that rend() does not refer to the same element as begin(), but to the element right before it. The iterator is valid until any operation that changes the RangeMap, such as an insert or erase.
Definition at line 947 of file rangemap.h.
|
inline |
Find the range containing specified value.
Returns an iterator to the Range containing the specified value, or the end() iterator if no such range exists.
Definition at line 956 of file rangemap.h.
|
inline |
Find the range containing specified value.
Returns an iterator to the Range containing the specified value, or the end() iterator if no such range exists.
Definition at line 962 of file rangemap.h.
|
inline |
Finds the first range ending above the specified value.
This is similar to the find() method, except it does not return the end() iterator if a range exists above the specified value.
Definition at line 974 of file rangemap.h.
Referenced by RangeMap< R, T >::select_overlapping_ranges().
|
inline |
Finds the first range ending above the specified value.
This is similar to the find() method, except it does not return the end() iterator if a range exists above the specified value.
Definition at line 977 of file rangemap.h.
|
inline |
Finds the last range starting at or below the specified value.
Returns the end iterator if there is no range containing a value less than or equal to the specified value.
Definition at line 985 of file rangemap.h.
|
inline |
Finds the last range starting at or below the specified value.
Returns the end iterator if there is no range containing a value less than or equal to the specified value.
Definition at line 995 of file rangemap.h.
|
inline |
Find range with closest size.
Returns an iterator pointing to the first range at or after the specified start
iterator whose size is at least as large as the specified size. Returns the end iterator if no such range exists. Note that this is an O(N) algorithm.
Definition at line 1012 of file rangemap.h.
|
inline |
Find range with closest size.
Returns an iterator pointing to the first range at or after the specified start
iterator whose size is at least as large as the specified size. Returns the end iterator if no such range exists. Note that this is an O(N) algorithm.
Definition at line 1022 of file rangemap.h.
|
inline |
Find first range of larger size.
Returns an iterator to the first range at least as large as the specified size
and at or after start
. Returns the end iterator if no range is found. Note that this is an O(N) algorithm.
Definition at line 1038 of file rangemap.h.
|
inline |
Find first range of larger size.
Returns an iterator to the first range at least as large as the specified size
and at or after start
. Returns the end iterator if no range is found. Note that this is an O(N) algorithm.
Definition at line 1045 of file rangemap.h.
|
inline |
|
inline |
Returns the number of values represented by this RangeMap.
The number of values does not typically correlate with the amount of memory used by the RangeMap since each element of the underlying std::map represents an arbitrary number of values. Note that if the range occupies the entire possible set of values then the size might be returned as zero due to overflow, and it will be necessary to call empty() to make the determination.
Definition at line 1074 of file rangemap.h.
|
inline |
Returns the minimum value in an extent map.
The extent map must not be empty.
Definition at line 1082 of file rangemap.h.
|
inline |
Returns the maximum value in an extent map.
The extent map must not be empty.
Definition at line 1088 of file rangemap.h.
|
inline |
Clears the map.
Removes all entries from the map. If notify
is true then also call the removing() method of each value.
Definition at line 1111 of file rangemap.h.
|
inline |
Erases the specified range from this map.
The range to remove can span multiple existing ranges and/or parts of ranges, or no ranges at all. It would be nice to be able to return an iterator to the next item since we have that in hand. Unfortunately, limitations of std::map make this impractical. If you need an iterator, just make another call to lower_bound().
Definition at line 1123 of file rangemap.h.
|
inline |
Erase ranges from this map.
Every range in the other
map is erased from this map. The maps need not be the same type as long as their ranges are the same type. The values of the other
map are not used–only its ranges.
Definition at line 1183 of file rangemap.h.
|
inline |
Insert a range/value pair into the map.
If make_hole
is true then the new range is allowed to replace existing ranges (or parts thereof), otherwise if the new range conflicts with eixsting ranges the new extent is not inserted and no change is made to the map. If merge
is true then we attempt to merge the new range into adjacent ranges. Returns an iterator to the new map element, or if merged, to the element that contains the new value. Returns the end iterator if the range was not inserted.
Definition at line 1194 of file rangemap.h.
Referenced by RangeMap< R, T >::select_overlapping_ranges().
|
inline |
Insert part of one rangemap into another.
The ranges from start
(inclusive) to stop
(exclusive) are inserted into this range map. The start
and stop
iterators should not be iterators of this map, but some other.
Definition at line 1233 of file rangemap.h.
|
inline |
Determines if two range maps overlap.
Returns true iff any ranges of this map overlap with any ranges of map x
.
Definition at line 1244 of file rangemap.h.
|
inline |
Determines if a range map overlaps with a specified range.
Returns true iff any part of the range r
is present in the map. A RangeMap never overlaps with an empty range.
Definition at line 1250 of file rangemap.h.
|
inline |
Determines if a range map does not contain any part of the specified range.
Returns false if any part of the range r
is present in the map. An empty range is always distinct from the map.
Definition at line 1259 of file rangemap.h.
|
inline |
Determines if two range maps are distinct.
Returns true iff there is no range in this map that overlaps with any range of map x
.
Definition at line 1265 of file rangemap.h.
|
inline |
Determines if this range map contains all of the specified range.
If the specified range is empty then this function returns true: the map contains all empty ranges.
Definition at line 1271 of file rangemap.h.
Referenced by RangeMap< R, T >::contains().
|
inline |
Determins if this range map contains all of some other range map.
Returns true iff each range in x
is contained in some range of this map. If x
is empty this function returns true: a RangeMap contains all empty ranges.
Definition at line 1292 of file rangemap.h.
References RangeMap< R, T >::contains().
|
inline |
Find the first overlap between two RangeMap objects.
Returns an iterator for this map that points to the first range that overlaps with some range in the other map, x
. Returns the end iterator if no overlap is found.
Definition at line 1311 of file rangemap.h.
|
inline |
Find the first overlap between two RangeMap objects.
Returns an iterator for this map that points to the first range that overlaps with some range in the other map, x
. Returns the end iterator if no overlap is found.
Definition at line 1314 of file rangemap.h.
|
inline |
Find an overlap between two RangeMap objects.
Returns an iterator for this map that points to the first range that overlaps with some range in the other map, x
. The returned iterator will be between start
(inclusive) and stop
(exclusive), which must obviously be iterators for this RangeMap, not x
. Returns the end iterator if there is no overlap within the restricted ranges.
Definition at line 1325 of file rangemap.h.
|
inline |
Find an overlap between two RangeMap objects.
Returns an iterator for this map that points to the first range that overlaps with some range in the other map, x
. The returned iterator will be between start
(inclusive) and stop
(exclusive), which must obviously be iterators for this RangeMap, not x
. Returns the end iterator if there is no overlap within the restricted ranges.
Definition at line 1340 of file rangemap.h.
|
inline |
Create an inverse of a range map.
The values of the result are default constructed.
Definition at line 1364 of file rangemap.h.
|
inline |
Create a range map that's the inverse of some other map.
The returned map's ranges will be limited according to the specified limits
. The values of the result are default constructed.
Definition at line 1371 of file rangemap.h.
References Range< T >::inin().
|
inline |
Select ranges overlapping selector range.
Returns a new range map whose ranges are those ranges of this map that overlap with the specified selector
range.
Definition at line 1390 of file rangemap.h.
References RangeMap< R, T >::end(), RangeMap< R, T >::insert(), Range< T >::left_of(), RangeMap< R, T >::lower_bound(), and Range< T >::overlaps().