LLVM 20.0.0git
Classes | Public Types | Public Member Functions | List of all members
llvm::PriorityWorklist< T, VectorT, MapT > Class Template Reference

A FILO worklist that prioritizes on re-insertion without duplication. More...

#include "llvm/ADT/PriorityWorklist.h"

Inheritance diagram for llvm::PriorityWorklist< T, VectorT, MapT >:
Inheritance graph
[legend]

Public Types

using value_type = T
 
using key_type = T
 
using reference = T &
 
using const_reference = const T &
 
using size_type = typename MapT::size_type
 

Public Member Functions

 PriorityWorklist ()=default
 Construct an empty PriorityWorklist.
 
bool empty () const
 Determine if the PriorityWorklist is empty or not.
 
size_type size () const
 Returns the number of elements in the worklist.
 
size_type count (const key_type &key) const
 Count the number of elements of a given key in the PriorityWorklist.
 
const Tback () const
 Return the last element of the PriorityWorklist.
 
bool insert (const T &X)
 Insert a new element into the PriorityWorklist.
 
template<typename SequenceT >
std::enable_if_t<!std::is_convertible< SequenceT, T >::valueinsert (SequenceT &&Input)
 Insert a sequence of new elements into the PriorityWorklist.
 
void pop_back ()
 Remove the last element of the PriorityWorklist.
 
T pop_back_val ()
 
bool erase (const T &X)
 Erase an item from the worklist.
 
template<typename UnaryPredicate >
bool erase_if (UnaryPredicate P)
 Erase items from the set vector based on a predicate function.
 
void clear ()
 Reverse the items in the PriorityWorklist.
 

Detailed Description

template<typename T, typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
class llvm::PriorityWorklist< T, VectorT, MapT >

A FILO worklist that prioritizes on re-insertion without duplication.

This is very similar to a SetVector with the primary difference that while re-insertion does not create a duplicate, it does adjust the visitation order to respect the last insertion point. This can be useful when the visit order needs to be prioritized based on insertion point without actually having duplicate visits.

Note that this doesn't prevent re-insertion of elements which have been visited – if you need to break cycles, a set will still be necessary.

The type T must be default constructable to a null value that will be ignored. It is an error to insert such a value, and popping elements will never produce such a value. It is expected to be used with common nullable types like pointers or optionals.

Internally this uses a vector to store the worklist and a map to identify existing elements in the worklist. Both of these may be customized, but the map must support the basic DenseMap API for mapping from a T to an integer index into the vector.

A partial specialization is provided to automatically select a SmallVector and a SmallDenseMap if custom data structures are not provided.

Definition at line 55 of file PriorityWorklist.h.

Member Typedef Documentation

◆ const_reference

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
using llvm::PriorityWorklist< T, VectorT, MapT >::const_reference = const T&

Definition at line 60 of file PriorityWorklist.h.

◆ key_type

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
using llvm::PriorityWorklist< T, VectorT, MapT >::key_type = T

Definition at line 58 of file PriorityWorklist.h.

◆ reference

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
using llvm::PriorityWorklist< T, VectorT, MapT >::reference = T&

Definition at line 59 of file PriorityWorklist.h.

◆ size_type

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
using llvm::PriorityWorklist< T, VectorT, MapT >::size_type = typename MapT::size_type

Definition at line 61 of file PriorityWorklist.h.

◆ value_type

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
using llvm::PriorityWorklist< T, VectorT, MapT >::value_type = T

Definition at line 57 of file PriorityWorklist.h.

Constructor & Destructor Documentation

◆ PriorityWorklist()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
llvm::PriorityWorklist< T, VectorT, MapT >::PriorityWorklist ( )
default

Construct an empty PriorityWorklist.

Member Function Documentation

◆ back()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
const T & llvm::PriorityWorklist< T, VectorT, MapT >::back ( ) const
inline

◆ clear()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
void llvm::PriorityWorklist< T, VectorT, MapT >::clear ( )
inline

Reverse the items in the PriorityWorklist.

This does an in-place reversal. Other kinds of reverse aren't easy to support in the face of the worklist semantics. Completely clear the PriorityWorklist

Definition at line 211 of file PriorityWorklist.h.

◆ count()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
size_type llvm::PriorityWorklist< T, VectorT, MapT >::count ( const key_type key) const
inline

Count the number of elements of a given key in the PriorityWorklist.

Returns
0 if the element is not in the PriorityWorklist, 1 if it is.

Definition at line 78 of file PriorityWorklist.h.

◆ empty()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
bool llvm::PriorityWorklist< T, VectorT, MapT >::empty ( ) const
inline

◆ erase()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
bool llvm::PriorityWorklist< T, VectorT, MapT >::erase ( const T X)
inline

Erase an item from the worklist.

Note that this is constant time due to the nature of the worklist implementation.

Definition at line 162 of file PriorityWorklist.h.

References assert(), I, T, and X.

◆ erase_if()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
template<typename UnaryPredicate >
bool llvm::PriorityWorklist< T, VectorT, MapT >::erase_if ( UnaryPredicate  P)
inline

Erase items from the set vector based on a predicate function.

This is intended to be equivalent to the following code, if we could write it:

V.erase(remove_if(V, P), V.end());
#define P(N)
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1761

However, PriorityWorklist doesn't expose non-const iterators, making any algorithm like remove_if impossible to use.

Returns
true if any element is removed.

Definition at line 193 of file PriorityWorklist.h.

References E, I, P, llvm::remove_if(), and T.

◆ insert() [1/2]

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
bool llvm::PriorityWorklist< T, VectorT, MapT >::insert ( const T X)
inline

Insert a new element into the PriorityWorklist.

Returns
true if the element was inserted into the PriorityWorklist.

Definition at line 90 of file PriorityWorklist.h.

References assert(), T, and X.

Referenced by llvm::appendReversedLoopsToWorklist(), llvm::FunctionToLoopPassAdaptor::run(), llvm::ModuleToPostOrderCGSCCPassAdaptor::run(), and llvm::sinkRegionForLoopNest().

◆ insert() [2/2]

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
template<typename SequenceT >
std::enable_if_t<!std::is_convertible< SequenceT, T >::value > llvm::PriorityWorklist< T, VectorT, MapT >::insert ( SequenceT &&  Input)
inline

Insert a sequence of new elements into the PriorityWorklist.

Definition at line 113 of file PriorityWorklist.h.

References T.

◆ pop_back()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
void llvm::PriorityWorklist< T, VectorT, MapT >::pop_back ( )
inline

◆ pop_back_val()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
T llvm::PriorityWorklist< T, VectorT, MapT >::pop_back_val ( )
inline

◆ size()

template<typename T , typename VectorT = std::vector<T>, typename MapT = DenseMap<T, ptrdiff_t>>
size_type llvm::PriorityWorklist< T, VectorT, MapT >::size ( ) const
inline

Returns the number of elements in the worklist.

Definition at line 72 of file PriorityWorklist.h.


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