1 //===- PriorityWorklist.h - Worklist with insertion priority ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
12 /// This file provides a priority worklist. See the class comments for details.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_ADT_PRIORITYWORKLIST_H
17 #define LLVM_ADT_PRIORITYWORKLIST_H
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Support/Compiler.h"
27 #include <type_traits>
32 /// A FILO worklist that prioritizes on re-insertion without duplication.
34 /// This is very similar to a \c SetVector with the primary difference that
35 /// while re-insertion does not create a duplicate, it does adjust the
36 /// visitation order to respect the last insertion point. This can be useful
37 /// when the visit order needs to be prioritized based on insertion point
38 /// without actually having duplicate visits.
40 /// Note that this doesn't prevent re-insertion of elements which have been
41 /// visited -- if you need to break cycles, a set will still be necessary.
43 /// The type \c T must be default constructable to a null value that will be
44 /// ignored. It is an error to insert such a value, and popping elements will
45 /// never produce such a value. It is expected to be used with common nullable
46 /// types like pointers or optionals.
48 /// Internally this uses a vector to store the worklist and a map to identify
49 /// existing elements in the worklist. Both of these may be customized, but the
50 /// map must support the basic DenseMap API for mapping from a T to an integer
51 /// index into the vector.
53 /// A partial specialization is provided to automatically select a SmallVector
54 /// and a SmallDenseMap if custom data structures are not provided.
55 template <typename T, typename VectorT = std::vector<T>,
56 typename MapT = DenseMap<T, ptrdiff_t>>
57 class PriorityWorklist {
62 using const_reference = const T&;
63 using size_type = typename MapT::size_type;
65 /// Construct an empty PriorityWorklist
66 PriorityWorklist() = default;
68 /// Determine if the PriorityWorklist is empty or not.
73 /// Returns the number of elements in the worklist.
74 size_type size() const {
78 /// Count the number of elements of a given key in the PriorityWorklist.
79 /// \returns 0 if the element is not in the PriorityWorklist, 1 if it is.
80 size_type count(const key_type &key) const {
84 /// Return the last element of the PriorityWorklist.
85 const T &back() const {
86 assert(!empty() && "Cannot call back() on empty PriorityWorklist!");
90 /// Insert a new element into the PriorityWorklist.
91 /// \returns true if the element was inserted into the PriorityWorklist.
92 bool insert(const T &X) {
93 assert(X != T() && "Cannot insert a null (default constructed) value!");
94 auto InsertResult = M.insert({X, V.size()});
95 if (InsertResult.second) {
96 // Fresh value, just append it to the vector.
101 auto &Index = InsertResult.first->second;
102 assert(V[Index] == X && "Value not actually at index in map!");
103 if (Index != (ptrdiff_t)(V.size() - 1)) {
104 // If the element isn't at the back, null it out and append a fresh one.
106 Index = (ptrdiff_t)V.size();
112 /// Insert a sequence of new elements into the PriorityWorklist.
113 template <typename SequenceT>
114 typename std::enable_if<!std::is_convertible<SequenceT, T>::value>::type
115 insert(SequenceT &&Input) {
116 if (std::begin(Input) == std::end(Input))
117 // Nothing to do for an empty input sequence.
120 // First pull the input sequence into the vector as a bulk append
122 ptrdiff_t StartIndex = V.size();
123 V.insert(V.end(), std::begin(Input), std::end(Input));
124 // Now walk backwards fixing up the index map and deleting any duplicates.
125 for (ptrdiff_t i = V.size() - 1; i >= StartIndex; --i) {
126 auto InsertResult = M.insert({V[i], i});
127 if (InsertResult.second)
130 // If the existing index is before this insert's start, nuke that one and
132 ptrdiff_t &Index = InsertResult.first->second;
133 if (Index < StartIndex) {
139 // Otherwise the existing one comes first so just clear out the value in
145 /// Remove the last element of the PriorityWorklist.
147 assert(!empty() && "Cannot remove an element when empty!");
148 assert(back() != T() && "Cannot have a null element at the back!");
152 } while (!V.empty() && V.back() == T());
155 LLVM_NODISCARD T pop_back_val() {
161 /// Erase an item from the worklist.
163 /// Note that this is constant time due to the nature of the worklist implementation.
164 bool erase(const T& X) {
169 assert(V[I->second] == X && "Value not actually at index in map!");
170 if (I->second == (ptrdiff_t)(V.size() - 1)) {
173 } while (!V.empty() && V.back() == T());
181 /// Erase items from the set vector based on a predicate function.
183 /// This is intended to be equivalent to the following code, if we could
187 /// V.erase(remove_if(V, P), V.end());
190 /// However, PriorityWorklist doesn't expose non-const iterators, making any
191 /// algorithm like remove_if impossible to use.
193 /// \returns true if any element is removed.
194 template <typename UnaryPredicate>
195 bool erase_if(UnaryPredicate P) {
196 typename VectorT::iterator E =
197 remove_if(V, TestAndEraseFromMap<UnaryPredicate>(P, M));
200 for (auto I = V.begin(); I != E; ++I)
202 M[*I] = I - V.begin();
207 /// Reverse the items in the PriorityWorklist.
209 /// This does an in-place reversal. Other kinds of reverse aren't easy to
210 /// support in the face of the worklist semantics.
212 /// Completely clear the PriorityWorklist
219 /// A wrapper predicate designed for use with std::remove_if.
221 /// This predicate wraps a predicate suitable for use with std::remove_if to
222 /// call M.erase(x) on each element which is slated for removal. This just
223 /// allows the predicate to be move only which we can't do with lambdas
225 template <typename UnaryPredicateT>
226 class TestAndEraseFromMap {
231 TestAndEraseFromMap(UnaryPredicateT P, MapT &M)
232 : P(std::move(P)), M(M) {}
234 bool operator()(const T &Arg) {
236 // Skip null values in the PriorityWorklist.
247 /// The map from value to index in the vector.
250 /// The vector of elements in insertion order.
254 /// A version of \c PriorityWorklist that selects small size optimized data
255 /// structures for the vector and map.
256 template <typename T, unsigned N>
257 class SmallPriorityWorklist
258 : public PriorityWorklist<T, SmallVector<T, N>,
259 SmallDenseMap<T, ptrdiff_t>> {
261 SmallPriorityWorklist() = default;
264 } // end namespace llvm
266 #endif // LLVM_ADT_PRIORITYWORKLIST_H