decompiler  1.0.0
Classes | Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
ghidra::rangemap< _recordtype > Class Template Reference

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_iteratorfind (linetype a) const
 Find sub-ranges intersecting the given boundary point. More...
 
std::pair< const_iterator, const_iteratorfind (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< AddrRangetree
 The underlying multiset of sub-ranges.
 
std::list< _recordtype > record
 Storage for the actual record objects.
 

Detailed Description

template<typename _recordtype>
class ghidra::rangemap< _recordtype >

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.

Member Function Documentation

◆ erase()

template<typename _recordtype>
void ghidra::rangemap< _recordtype >::erase ( typename std::list< _recordtype >::iterator  v)

Erase a given record from the container.

Parameters
vis the iterator to the record to be erased

Referenced by ghidra::rangemap< ScopeMapper >::end(), and ghidra::ScopeInternal::removeSymbolMappings().

◆ find() [1/2]

template<typename _recordtype >
std::pair< typename rangemap< _recordtype >::const_iterator, typename rangemap< _recordtype >::const_iterator > ghidra::rangemap< _recordtype >::find ( linetype  point) const

◆ find() [2/2]

template<typename _recordtype >
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.

Parameters
pointis the given boundary point
sub1is the starting subsort
sub2is the ending subsort
Returns
begin/end iterators over all intersecting and bounded sub-ranges

◆ find_begin()

template<typename _recordtype >
rangemap< _recordtype >::const_iterator ghidra::rangemap< _recordtype >::find_begin ( linetype  point) const

Find beginning of sub-ranges that contain the given boundary point.

Parameters
pointis the given boundary point
Returns
iterator to first sub-range of intersects the boundary point

Referenced by ghidra::rangemap< ScopeMapper >::end(), and ghidra::ParamListStandard::getBiggestContainedParam().

◆ find_end()

template<typename _recordtype >
rangemap< _recordtype >::const_iterator ghidra::rangemap< _recordtype >::find_end ( linetype  point) const

Find ending of sub-ranges that contain the given boundary point.

Parameters
pointis the given boundary point
Returns
iterator to first sub-range after that does not intersect the boundary point

Referenced by ghidra::ParamListStandard::characterizeAsParam(), ghidra::rangemap< ScopeMapper >::end(), and ghidra::ParamListStandard::getBiggestContainedParam().

◆ find_overlap()

template<typename _recordtype >
rangemap< _recordtype >::const_iterator ghidra::rangemap< _recordtype >::find_overlap ( linetype  point,
linetype  end 
) const

Find first record overlapping given interval.

Parameters
pointis the start of interval to test
endis the end of the interval to test
Returns
iterator to first sub-range of an intersecting record (or end)

Referenced by ghidra::rangemap< ScopeMapper >::end(), and ghidra::ScopeInternal::findOverlap().

◆ insert()

template<typename _recordtype >
std::list< _recordtype >::iterator ghidra::rangemap< _recordtype >::insert ( const inittype data,
linetype  a,
linetype  b 
)

Insert a new record into the container.

Parameters
datais other initialization data for the new record
ais the start of the range occupied by the new record
bis the (inclusive) end of the range
Returns
an iterator to the new record

Referenced by ghidra::ScopeInternal::addMapInternal(), ghidra::ParamListStandard::addResolverRange(), and ghidra::rangemap< ScopeMapper >::end().

◆ unzip()

template<typename _recordtype >
void ghidra::rangemap< _recordtype >::unzip ( linetype  i,
typename std::multiset< AddrRange >::iterator  iter 
)
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.

Parameters
iis the given boundary point
iterpoints to the first sub-range containing the boundary point

Referenced by ghidra::rangemap< ScopeMapper >::insert().

◆ zip()

template<typename _recordtype >
void ghidra::rangemap< _recordtype >::zip ( linetype  i,
typename std::multiset< AddrRange >::iterator  iter 
)
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).

Parameters
iis the given boundary point
iterpoints to the first sub-range that ends with the given boundary point

Referenced by ghidra::rangemap< ScopeMapper >::erase().


The documentation for this class was generated from the following file: