LLVM 20.0.0git
Classes | Public Types | Public Member Functions | Static Public Member Functions | List of all members
llvm::IntervalTree< PointT, ValueT, DataT > Class Template Reference

#include "llvm/ADT/IntervalTree.h"

Inheritance diagram for llvm::IntervalTree< PointT, ValueT, DataT >:
Inheritance graph
[legend]

Classes

class  find_iterator
 

Public Types

enum class  Sorting { Ascending , Descending }
 
using PointType = PointT
 
using ValueType = ValueT
 
using DataType = DataT
 
using Allocator = BumpPtrAllocator
 
using IntervalReferences = SmallVector< const DataType *, 4 >
 

Public Member Functions

 IntervalTree (Allocator &NodeAllocator)
 
 ~IntervalTree ()
 
bool empty () const
 Return true when no intervals are mapped.
 
void clear ()
 Remove all entries.
 
void insert (PointType Left, PointType Right, ValueType Value)
 Add a mapping of [Left;Right] to Value.
 
IntervalReferences getContaining (PointType Point) const
 Return all the intervals in their natural tree location, that contain the given point.
 
void print (raw_ostream &OS, bool HexFormat=true)
 Print the interval tree.
 
void create ()
 Create the interval tree.
 
find_iterator find (PointType Point) const
 Iterator to start a find operation; it returns find_end() if the tree has not been built.
 
find_iterator find_end () const
 Iterator to end find operation.
 

Static Public Member Functions

static void sortIntervals (IntervalReferences &IntervalSet, Sorting Sort)
 Sort the given intervals using the following sort options: Ascending: return the intervals with the smallest at the front.
 

Detailed Description

template<typename PointT, typename ValueT, typename DataT = IntervalData<PointT, ValueT>>
class llvm::IntervalTree< PointT, ValueT, DataT >

Definition at line 248 of file IntervalTree.h.

Member Typedef Documentation

◆ Allocator

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
using llvm::IntervalTree< PointT, ValueT, DataT >::Allocator = BumpPtrAllocator

Definition at line 258 of file IntervalTree.h.

◆ DataType

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
using llvm::IntervalTree< PointT, ValueT, DataT >::DataType = DataT

Definition at line 257 of file IntervalTree.h.

◆ IntervalReferences

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
using llvm::IntervalTree< PointT, ValueT, DataT >::IntervalReferences = SmallVector<const DataType *, 4>

Definition at line 261 of file IntervalTree.h.

◆ PointType

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
using llvm::IntervalTree< PointT, ValueT, DataT >::PointType = PointT

Definition at line 255 of file IntervalTree.h.

◆ ValueType

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
using llvm::IntervalTree< PointT, ValueT, DataT >::ValueType = ValueT

Definition at line 256 of file IntervalTree.h.

Member Enumeration Documentation

◆ Sorting

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
enum class llvm::IntervalTree::Sorting
strong
Enumerator
Ascending 
Descending 

Definition at line 260 of file IntervalTree.h.

Constructor & Destructor Documentation

◆ IntervalTree()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
llvm::IntervalTree< PointT, ValueT, DataT >::IntervalTree ( Allocator NodeAllocator)
inlineexplicit

Definition at line 591 of file IntervalTree.h.

◆ ~IntervalTree()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
llvm::IntervalTree< PointT, ValueT, DataT >::~IntervalTree ( )
inline

Member Function Documentation

◆ clear()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
void llvm::IntervalTree< PointT, ValueT, DataT >::clear ( )
inline

◆ create()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
void llvm::IntervalTree< PointT, ValueT, DataT >::create ( )
inline

◆ empty()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
bool llvm::IntervalTree< PointT, ValueT, DataT >::empty ( ) const
inline

◆ find()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
find_iterator llvm::IntervalTree< PointT, ValueT, DataT >::find ( PointType  Point) const
inline

Iterator to start a find operation; it returns find_end() if the tree has not been built.

There is no support to iterate over all the elements of the tree.

Definition at line 680 of file IntervalTree.h.

References llvm::IntervalTree< PointT, ValueT, DataT >::empty(), and llvm::IntervalTree< PointT, ValueT, DataT >::find_end().

Referenced by llvm::IntervalTree< PointT, ValueT, DataT >::getContaining(), and llvm::logicalview::LVRange::getEntry().

◆ find_end()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
find_iterator llvm::IntervalTree< PointT, ValueT, DataT >::find_end ( ) const
inline

◆ getContaining()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
IntervalReferences llvm::IntervalTree< PointT, ValueT, DataT >::getContaining ( PointType  Point) const
inline

◆ insert()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
void llvm::IntervalTree< PointT, ValueT, DataT >::insert ( PointType  Left,
PointType  Right,
ValueType  Value 
)
inline

Add a mapping of [Left;Right] to Value.

Definition at line 609 of file IntervalTree.h.

References assert(), llvm::IntervalTree< PointT, ValueT, DataT >::empty(), llvm::Left, and llvm::Right.

Referenced by llvm::logicalview::LVRange::startSearch().

◆ print()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
void llvm::IntervalTree< PointT, ValueT, DataT >::print ( raw_ostream OS,
bool  HexFormat = true 
)
inline

Print the interval tree.

When HexFormat is true, the interval tree interval ranges and associated values are printed in hexadecimal format.

Definition at line 641 of file IntervalTree.h.

References OS.

Referenced by llvm::logicalview::LVRange::startSearch().

◆ sortIntervals()

template<typename PointT , typename ValueT , typename DataT = IntervalData<PointT, ValueT>>
static void llvm::IntervalTree< PointT, ValueT, DataT >::sortIntervals ( IntervalReferences IntervalSet,
Sorting  Sort 
)
inlinestatic

Sort the given intervals using the following sort options: Ascending: return the intervals with the smallest at the front.

Descending: return the intervals with the biggest at the front.

Definition at line 627 of file IntervalTree.h.

References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::SmallVectorTemplateCommon< T, typename >::end(), LHS, and RHS.


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