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.

Detailed Description

template<typename _recordtype>
class 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:

recordtype() a constructor taking no parameters
getFirst() beginning of range
getLast() end of range (inclusive)
getSubsort() retrieve the subsorttype object (see below)
initialize(inittype,linetype,linetype) an initializer routine

The recordtype must define data-types:

linetype
subsorttype
inittype

linetype is the data-type of elements in the linear domain. It must support:

<,<= Comparisons
==,!= Equality
+ <constant> Addition of integers
- <constant> Subtraction of integers

subsorttype describes how overlapping intervals can be sub-sorted. It must support:

<
subsorttype(false) constructor with false produces a minimal value
subsorttype(true) constructor with true produces a maximal value
copy constructor

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

template<typename _recordtype>

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

Erase a given record from the container.

Parameters

v	is the iterator to the record to be erased

References rangemap< _recordtype >::AddrRange::a, rangemap< _recordtype >::AddrRange::AddrRange(), rangemap< _recordtype >::AddrRange::b, rangemap< _recordtype >::record, rangemap< _recordtype >::tree, and rangemap< _recordtype >::zip().

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

template<typename _recordtype >

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

Find sub-ranges intersecting the given boundary point.

Parameters

point is the given boundary point

Returns: begin/end iterators over all intersecting sub-ranges

References rangemap< _recordtype >::tree.

Referenced by ParamListStandard::characterizeAsParam(), rangemap< ScopeMapper >::end(), ScopeInternal::findAddr(), ScopeInternal::findClosestFit(), ScopeInternal::findCodeLabel(), ScopeInternal::findContainer(), ParamListStandard::findEntry(), ScopeInternal::findExternalRef(), and ScopeInternal::findFunction().

template<typename _recordtype >

std::pair< typename rangemap< _recordtype >::const_iterator, typename rangemap< _recordtype >::const_iterator > rangemap< _recordtype >::find	(	linetype	point,
		const subsorttype &	sub1,
		const subsorttype &	sub2
	)		const

Find sub-ranges intersecting given boundary point, and between given subsorts.

Parameters

point	is the given boundary point
sub1	is the starting subsort
sub2	is the ending subsort

Returns: begin/end iterators over all intersecting and bounded sub-ranges

References rangemap< _recordtype >::tree.

template<typename _recordtype >

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

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

Parameters

point is the given boundary point

Returns: iterator to first sub-range of intersects the boundary point

References rangemap< _recordtype >::tree.

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

template<typename _recordtype >

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

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

Parameters

point is the given boundary point

Returns: iterator to first sub-range after that does not intersect the boundary point

References rangemap< _recordtype >::tree.

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

template<typename _recordtype >

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

Find first record overlapping given interval.

Parameters

point	is the start of interval to test
end	is the end of the interval to test

Returns: iterator to first sub-range of an intersecting record (or end)

References rangemap< _recordtype >::tree.

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

template<typename _recordtype >

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

Insert a new record into the container.

Parameters

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

Returns: an iterator to the new record

References rangemap< _recordtype >::AddrRange::a, rangemap< _recordtype >::AddrRange::AddrRange(), rangemap< _recordtype >::AddrRange::b, rangemap< _recordtype >::record, rangemap< _recordtype >::tree, and rangemap< _recordtype >::unzip().

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

template<typename _recordtype >

void 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

i	is the given boundary point
iter	points to the first sub-range containing the boundary point

References rangemap< _recordtype >::AddrRange::a, rangemap< _recordtype >::AddrRange::AddrRange(), rangemap< _recordtype >::AddrRange::b, rangemap< _recordtype >::AddrRange::first, rangemap< _recordtype >::tree, and rangemap< _recordtype >::AddrRange::value.

Referenced by rangemap< _recordtype >::insert().

template<typename _recordtype >

void 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

i	is the given boundary point
iter	points to the first sub-range that ends with the given boundary point

References rangemap< _recordtype >::tree.

Referenced by rangemap< _recordtype >::erase().

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

rangemap.hh

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename _recordtype> class rangemap< _recordtype >

Member Function Documentation

template<typename _recordtype>
class rangemap< _recordtype >