LLVM  6.0.0svn
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. 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 Tback () 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

◆ 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

◆ 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

◆ 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: