class PriorityWorklist

Declaration

template <typename T,
          typename VectorT = std::vector<T>,
          typename MapT = DenseMap<T, ptrdiff_t>>
class PriorityWorklist { /* full declaration omitted */ };

Description

A FILO worklist that prioritizes on re-insertion without duplication. This is very similar to a \c 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 \c 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.

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:56

Templates

T

VectorT = std::vector<T>

MapT = DenseMap<T, ptrdiff_t>

Method Overview

• public PriorityWorklist<T, VectorT, MapT>()
• public const T & back() const
• public void clear()
• public llvm::PriorityWorklist::size_type count(const llvm::PriorityWorklist::key_type & key) const
• public bool empty() const
• public bool erase(const T & X)
• public template <typename UnaryPredicate>bool erase_if(UnaryPredicate P)
• public bool insert(const T & X)
• public template <typename SequenceT>typename std::enable_if<!std::is_convertible<SequenceT, T>::value>::type insert(SequenceT && Input)
• public void pop_back()
• public T pop_back_val()
• public llvm::PriorityWorklist::size_type size() const

Methods

¶PriorityWorklist<T, VectorT, MapT>()

Description

Construct an empty PriorityWorklist

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:65

¶const T& back() const

Description

Return the last element of the PriorityWorklist.

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:84

¶void clear()

Description

Completely clear the PriorityWorklist

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:212

¶llvm::PriorityWorklist::size_type count(
    const llvm::PriorityWorklist::key_type& key)
    const

Description

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

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:79

Parameters

const llvm::PriorityWorklist::key_type& key

Returns

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

¶bool empty() const

Description

Determine if the PriorityWorklist is empty or not.

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:68

¶bool erase(const T& X)

Description

Erase an item from the worklist. Note that this is constant time due to the nature of the worklist implementation.

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:163

Parameters

const T& X

¶template <typename UnaryPredicate>
bool erase_if(UnaryPredicate P)

Description

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: However, PriorityWorklist doesn't expose non-const iterators, making any algorithm like remove_if impossible to use.

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:194

Templates

UnaryPredicate

Parameters

UnaryPredicate P

Returns

true if any element is removed.

¶bool insert(const T& X)

Description

Insert a new element into the PriorityWorklist.

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:91

Parameters

const T& X

Returns

true if the element was inserted into the PriorityWorklist.

¶template <typename SequenceT>
typename std::enable_if<
    !std::is_convertible<SequenceT,
                         T>::value>::type
insert(SequenceT&& Input)

Description

Insert a sequence of new elements into the PriorityWorklist.

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:114

Templates

SequenceT

Parameters

SequenceT&& Input

¶void pop_back()

Description

Remove the last element of the PriorityWorklist.

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:145

¶T pop_back_val()

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:154

¶llvm::PriorityWorklist::size_type size() const

Description

Returns the number of elements in the worklist.

Declared at: llvm/include/llvm/ADT/PriorityWorklist.h:73