decompiler
1.0.0
|
An interval map container. More...
#include <rangemap.hh>
Classes | |
class | AddrRange |
The internal sub-range object for the interval map. More... | |
class | PartIterator |
An iterator into the interval map container. More... | |
Public Types | |
typedef _recordtype::linetype | linetype |
Integer data-type defining the linear domain. | |
typedef _recordtype::subsorttype | subsorttype |
The data-type used for subsorting. | |
typedef _recordtype::inittype | inittype |
The data-type containing initialization data for records. | |
typedef PartIterator | const_iterator |
The main sub-range iterator data-type. | |
Public Member Functions | |
bool | empty (void) const |
Return true if the container is empty. | |
void | clear (void) |
Clear all records from the container. | |
std::list< _recordtype >::const_iterator | begin_list (void) const |
Beginning of records. | |
std::list< _recordtype >::const_iterator | end_list (void) const |
End of records. | |
std::list< _recordtype >::iterator | begin_list (void) |
Beginning of records. | |
std::list< _recordtype >::iterator | end_list (void) |
End of records. | |
const_iterator | begin (void) const |
Beginning of sub-ranges. | |
const_iterator | end (void) const |
Ending of sub-ranges. | |
std::pair< const_iterator, const_iterator > | find (linetype a) const |
Find sub-ranges intersecting the given boundary point. More... | |
std::pair< const_iterator, const_iterator > | find (linetype a, const subsorttype &subsort1, const subsorttype &subsort2) const |
Find sub-ranges intersecting given boundary point, and between given subsorts. More... | |
const_iterator | find_begin (linetype point) const |
Find beginning of sub-ranges that contain the given boundary point. More... | |
const_iterator | find_end (linetype point) const |
Find ending of sub-ranges that contain the given boundary point. More... | |
const_iterator | find_overlap (linetype point, linetype end) const |
Find first record overlapping given interval. More... | |
std::list< _recordtype >::iterator | insert (const inittype &data, linetype a, linetype b) |
Insert a new record into the container. More... | |
void | erase (typename std::list< _recordtype >::iterator v) |
Erase a given record from the container. More... | |
void | erase (const_iterator iter) |
Erase a record given an iterator. | |
Private Member Functions | |
void | zip (linetype i, typename std::multiset< AddrRange >::iterator iter) |
Remove the given partition boundary. More... | |
void | unzip (linetype i, typename std::multiset< AddrRange >::iterator iter) |
Insert the given partition boundary. More... | |
Private Attributes | |
std::multiset< AddrRange > | tree |
The underlying multiset of sub-ranges. | |
std::list< _recordtype > | record |
Storage for the actual record objects. | |
An interval map container.
A container for records occupying (possibly overlapping) intervals. I.e. a map from a linear ordered domain to (multiple) records. The recordtype is the main object in the container, it must support:
The recordtype must define data-types:
linetype is the data-type of elements in the linear domain. It must support:
subsorttype describes how overlapping intervals can be sub-sorted. It must support:
inittype is extra initialization data for the recordtype
The main interval map is implemented as a multiset of disjoint sub-ranges mapping to the recordtype objects. After deduping the sub-ranges form the common refinement of all the possibly overlapping recordtype ranges. A sub-range is duplicated for each distinct recordtype that overlaps that sub-range. The sub-range multiset is updated with every insertion or deletion of recordtype objects into the container, which may insert new or delete existing boundary points separating the disjoint subranges.
void ghidra::rangemap< _recordtype >::erase | ( | typename std::list< _recordtype >::iterator | v | ) |
Erase a given record from the container.
v | is the iterator to the record to be erased |
Referenced by ghidra::rangemap< ScopeMapper >::end(), and ghidra::ScopeInternal::removeSymbolMappings().
std::pair< typename rangemap< _recordtype >::const_iterator, typename rangemap< _recordtype >::const_iterator > ghidra::rangemap< _recordtype >::find | ( | linetype | point | ) | const |
Find sub-ranges intersecting the given boundary point.
point | is the given boundary point |
Referenced by ghidra::ParamListStandard::characterizeAsParam(), ghidra::rangemap< ScopeMapper >::end(), ghidra::ScopeInternal::findAddr(), ghidra::ScopeInternal::findClosestFit(), ghidra::ScopeInternal::findCodeLabel(), ghidra::ScopeInternal::findContainer(), ghidra::ParamListStandard::findEntry(), ghidra::ScopeInternal::findExternalRef(), and ghidra::ScopeInternal::findFunction().
std::pair< typename rangemap< _recordtype >::const_iterator, typename rangemap< _recordtype >::const_iterator > ghidra::rangemap< _recordtype >::find | ( | linetype | point, |
const subsorttype & | sub1, | ||
const subsorttype & | sub2 | ||
) | const |
Find sub-ranges intersecting given boundary point, and between given subsorts.
point | is the given boundary point |
sub1 | is the starting subsort |
sub2 | is the ending subsort |
rangemap< _recordtype >::const_iterator ghidra::rangemap< _recordtype >::find_begin | ( | linetype | point | ) | const |
Find beginning of sub-ranges that contain the given boundary point.
point | is the given boundary point |
Referenced by ghidra::rangemap< ScopeMapper >::end(), and ghidra::ParamListStandard::getBiggestContainedParam().
rangemap< _recordtype >::const_iterator ghidra::rangemap< _recordtype >::find_end | ( | linetype | point | ) | const |
Find ending of sub-ranges that contain the given boundary point.
point | is the given boundary point |
Referenced by ghidra::ParamListStandard::characterizeAsParam(), ghidra::rangemap< ScopeMapper >::end(), and ghidra::ParamListStandard::getBiggestContainedParam().
rangemap< _recordtype >::const_iterator ghidra::rangemap< _recordtype >::find_overlap | ( | linetype | point, |
linetype | end | ||
) | const |
Find first record overlapping given interval.
point | is the start of interval to test |
end | is the end of the interval to test |
Referenced by ghidra::rangemap< ScopeMapper >::end(), and ghidra::ScopeInternal::findOverlap().
std::list< _recordtype >::iterator ghidra::rangemap< _recordtype >::insert | ( | const inittype & | data, |
linetype | a, | ||
linetype | b | ||
) |
Insert a new record into the container.
data | is other initialization data for the new record |
a | is the start of the range occupied by the new record |
b | is the (inclusive) end of the range |
Referenced by ghidra::ScopeInternal::addMapInternal(), ghidra::ParamListStandard::addResolverRange(), and ghidra::rangemap< ScopeMapper >::end().
|
private |
Insert the given partition boundary.
All sub-ranges that contain the boundary point will be split into a sub-range that ends at the boundary point and a sub-range that begins with the boundary point (+1). This should run in O(k), where k is the number of intervals intersecting the boundary point.
i | is the given boundary point |
iter | points to the first sub-range containing the boundary point |
Referenced by ghidra::rangemap< ScopeMapper >::insert().
|
private |
Remove the given partition boundary.
All sub-ranges that end with the given boundary point are deleted, and all sub-ranges that begin with the given boundary point (+1) are extended to cover the deleted sub-range. This should run in O(k).
i | is the given boundary point |
iter | points to the first sub-range that ends with the given boundary point |
Referenced by ghidra::rangemap< ScopeMapper >::erase().