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

#include "llvm/ADT/PriorityWorklist.h"

Inheritance diagram for llvm::PriorityWorklist< T, VectorT, MapT >:

[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. More...

bool	empty () const
	Determine if the PriorityWorklist is empty or not. More...

size_type	size () const
	Returns the number of elements in the worklist. More...

size_type	count (const key_type &key) const
	Count the number of elements of a given key in the PriorityWorklist. More...

const T &	back () const
	Return the last element of the PriorityWorklist. More...

bool	insert (const T &X)
	Insert a new element into the PriorityWorklist. More...

template<typename SequenceT >
std::enable_if<!std::is_convertible< SequenceT, T >::value >::type	insert (SequenceT &&Input)
	Insert a sequence of new elements into the PriorityWorklist. More...

void	pop_back ()
	Remove the last element of the PriorityWorklist. More...

LLVM_NODISCARD T	pop_back_val ()

bool	erase (const T &X)
	Erase an item from the worklist. More...

template<typename UnaryPredicate >
bool	erase_if (UnaryPredicate P)
	Erase items from the set vector based on a predicate function. More...

void	clear ()
	Reverse the items in the PriorityWorklist. More...

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 57 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 62 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 60 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 61 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 63 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 59 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

Return the last element of the PriorityWorklist.

Definition at line 85 of file PriorityWorklist.h.

Referenced by llvm::PriorityWorklist< llvm::LazyCallGraph::SCC *, SmallVector< llvm::LazyCallGraph::SCC *, N >, SmallDenseMap< llvm::LazyCallGraph::SCC *, ptrdiff_t > >::pop_back(), and llvm::PriorityWorklist< llvm::LazyCallGraph::SCC *, SmallVector< llvm::LazyCallGraph::SCC *, N >, SmallDenseMap< llvm::LazyCallGraph::SCC *, ptrdiff_t > >::pop_back_val().

◆ 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 213 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 80 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

Determine if the PriorityWorklist is empty or not.

Definition at line 69 of file PriorityWorklist.h.

Referenced by llvm::PriorityWorklist< llvm::LazyCallGraph::SCC *, SmallVector< llvm::LazyCallGraph::SCC *, N >, SmallDenseMap< llvm::LazyCallGraph::SCC *, ptrdiff_t > >::back(), and llvm::PriorityWorklist< llvm::LazyCallGraph::SCC *, SmallVector< llvm::LazyCallGraph::SCC *, N >, SmallDenseMap< llvm::LazyCallGraph::SCC *, ptrdiff_t > >::pop_back().

◆ 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 164 of file PriorityWorklist.h.

◆ 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());

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 195 of file PriorityWorklist.h.

◆ 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 92 of file PriorityWorklist.h.

◆ insert() [2/2]

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

template<typename SequenceT >

std::enable_if<!std::is_convertible<SequenceT, T>::value>::type llvm::PriorityWorklist< T, VectorT, MapT >::insert ( SequenceT && Input )

inline

Insert a sequence of new elements into the PriorityWorklist.

Definition at line 115 of file PriorityWorklist.h.

◆ 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

Remove the last element of the PriorityWorklist.

Definition at line 146 of file PriorityWorklist.h.

Referenced by llvm::PriorityWorklist< llvm::LazyCallGraph::SCC *, SmallVector< llvm::LazyCallGraph::SCC *, N >, SmallDenseMap< llvm::LazyCallGraph::SCC *, ptrdiff_t > >::pop_back_val().

◆ pop_back_val()

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

LLVM_NODISCARD T llvm::PriorityWorklist< T, VectorT, MapT >::pop_back_val ( )

inline

Definition at line 155 of file PriorityWorklist.h.

◆ 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 74 of file PriorityWorklist.h.

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

include/llvm/ADT/PriorityWorklist.h

Public Types

Public Member Functions

Detailed Description

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

Member Typedef Documentation

◆ const_reference

◆ key_type

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ PriorityWorklist()

Member Function Documentation

◆ back()

◆ clear()

◆ count()

◆ empty()

◆ erase()

◆ erase_if()

◆ insert() [1/2]

◆ insert() [2/2]

◆ pop_back()

◆ pop_back_val()

◆ size()

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