1//===- PriorityWorklist.h - Worklist with insertion priority ----*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9///
10/// \file
11///
12/// This file provides a priority worklist. See the class comments for details.
13///
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_ADT_PRIORITYWORKLIST_H
17#define LLVM_ADT_PRIORITYWORKLIST_H
18
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/Support/Compiler.h"
23#include <algorithm>
24#include <cassert>
25#include <cstddef>
26#include <iterator>
27#include <type_traits>
28#include <vector>
29
30namespace llvm {
31
32/// A FILO worklist that prioritizes on re-insertion without duplication.
33///
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.
39///
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.
42///
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.
47///
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.
52///
53/// A partial specialization is provided to automatically select a SmallVector
54/// and a SmallDenseMap if custom data structures are not provided.
55template <typename T, typename VectorT = std::vector<T>,
56 typename MapT = DenseMap<T, ptrdiff_t>>
57class PriorityWorklist {
58public:
59 using value_type = T;
60 using key_type = T;
61 using reference = T&;
62 using const_reference = const T&;
63 using size_type = typename MapT::size_type;
64
65 /// Construct an empty PriorityWorklist
66 PriorityWorklist() = default;
67
68 /// Determine if the PriorityWorklist is empty or not.
69 bool empty() const {
70 return V.empty();
71 }
72
73 /// Returns the number of elements in the worklist.
74 size_type size() const {
75 return M.size();
76 }
77
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 {
81 return M.count(key);
82 }
83
84 /// Return the last element of the PriorityWorklist.
85 const T &back() const {
86 assert(!empty() && "Cannot call back() on empty PriorityWorklist!");
87 return V.back();
88 }
89
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.
97 V.push_back(X);
98 return true;
99 }
100
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.
105 V[Index] = T();
106 Index = (ptrdiff_t)V.size();
107 V.push_back(X);
108 }
109 return false;
110 }
111
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.
118 return;
119
120 // First pull the input sequence into the vector as a bulk append
121 // operation.
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)
128 continue;
129
130 // If the existing index is before this insert's start, nuke that one and
131 // move it up.
132 ptrdiff_t &Index = InsertResult.first->second;
133 if (Index < StartIndex) {
134 V[Index] = T();
135 Index = i;
136 continue;
137 }
138
139 // Otherwise the existing one comes first so just clear out the value in
140 // this slot.
141 V[i] = T();
142 }
143 }
144
145 /// Remove the last element of the PriorityWorklist.
146 void pop_back() {
147 assert(!empty() && "Cannot remove an element when empty!");
148 assert(back() != T() && "Cannot have a null element at the back!");
149 M.erase(back());
150 do {
151 V.pop_back();
152 } while (!V.empty() && V.back() == T());
153 }
154
155 LLVM_NODISCARD T pop_back_val() {
156 T Ret = back();
157 pop_back();
158 return Ret;
159 }
160
161 /// Erase an item from the worklist.
162 ///
163 /// Note that this is constant time due to the nature of the worklist implementation.
164 bool erase(const T& X) {
165 auto I = M.find(X);
166 if (I == M.end())
167 return false;
168
169 assert(V[I->second] == X && "Value not actually at index in map!");
170 if (I->second == (ptrdiff_t)(V.size() - 1)) {
171 do {
172 V.pop_back();
173 } while (!V.empty() && V.back() == T());
174 } else {
175 V[I->second] = T();
176 }
177 M.erase(I);
178 return true;
179 }
180
181 /// Erase items from the set vector based on a predicate function.
182 ///
183 /// This is intended to be equivalent to the following code, if we could
184 /// write it:
185 ///
186 /// \code
187 /// V.erase(remove_if(V, P), V.end());
188 /// \endcode
189 ///
190 /// However, PriorityWorklist doesn't expose non-const iterators, making any
191 /// algorithm like remove_if impossible to use.
192 ///
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));
198 if (E == V.end())
199 return false;
200 for (auto I = V.begin(); I != E; ++I)
201 if (*I != T())
202 M[*I] = I - V.begin();
203 V.erase(E, V.end());
204 return true;
205 }
206
207 /// Reverse the items in the PriorityWorklist.
208 ///
209 /// This does an in-place reversal. Other kinds of reverse aren't easy to
210 /// support in the face of the worklist semantics.
211
212 /// Completely clear the PriorityWorklist
213 void clear() {
214 M.clear();
215 V.clear();
216 }
217
218private:
219 /// A wrapper predicate designed for use with std::remove_if.
220 ///
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
224 /// today.
225 template <typename UnaryPredicateT>
226 class TestAndEraseFromMap {
227 UnaryPredicateT P;
228 MapT &M;
229
230 public:
231 TestAndEraseFromMap(UnaryPredicateT P, MapT &M)
232 : P(std::move(P)), M(M) {}
233
234 bool operator()(const T &Arg) {
235 if (Arg == T())
236 // Skip null values in the PriorityWorklist.
237 return false;
238
239 if (P(Arg)) {
240 M.erase(Arg);
241 return true;
242 }
243 return false;
244 }
245 };
246
247 /// The map from value to index in the vector.
248 MapT M;
249
250 /// The vector of elements in insertion order.
251 VectorT V;
252};
253
254/// A version of \c PriorityWorklist that selects small size optimized data
255/// structures for the vector and map.
256template <typename T, unsigned N>
257class SmallPriorityWorklist
258 : public PriorityWorklist<T, SmallVector<T, N>,
259 SmallDenseMap<T, ptrdiff_t>> {
260public:
261 SmallPriorityWorklist() = default;
262};
263
264} // end namespace llvm
265
266#endif // LLVM_ADT_PRIORITYWORKLIST_H
267