LLVM: llvm::PriorityWorklist< T, VectorT, MapT (original) (raw)
A FILO worklist that prioritizes on re-insertion without duplication. More...
#include "[llvm/ADT/PriorityWorklist.h](PriorityWorklist%5F8h%5Fsource.html)"
| 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 T & | back () const |
| Return the last element of the PriorityWorklist. | |
| bool | insert (const T &X) |
| Insert a new element into the PriorityWorklist. | |
| template | |
| std::enable_if_t<!std::is_convertible< SequenceT, T >::value > | insert (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 | |
| bool | erase_if (UnaryPredicate P) |
| Erase items from the set vector based on a predicate function. | |
| void | clear () |
| Reverse the items in the PriorityWorklist. |
template<typename T, typename VectorT = std::vector, 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](classllvm%5F1%5F1SetVector.html "A vector that has set insertion semantics.") 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.
◆ const_reference
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ key_type
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ reference
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ size_type
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ value_type
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ back()
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ clear()
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ count()
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ empty()
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ erase()
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
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, typename MapT = DenseMap<T, ptrdiff_t>>
template
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:
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
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, typename MapT = DenseMap<T, ptrdiff_t>>
◆ insert() [2/2]
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
template
| std::enable_if_t<!std::is_convertible< SequenceT, T >::value > llvm::PriorityWorklist< T, VectorT, MapT >::insert ( SequenceT && Input) | inline |
|---|
◆ pop_back()
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ pop_back_val()
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
◆ size()
template<typename T, typename VectorT = std::vector, typename MapT = DenseMap<T, ptrdiff_t>>
The documentation for this class was generated from the following file:
- include/llvm/ADT/PriorityWorklist.h