Line data Source code
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 :
30 : namespace 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.
55 : template <typename T, typename VectorT = std::vector<T>,
56 : typename MapT = DenseMap<T, ptrdiff_t>>
57 : class PriorityWorklist {
58 : public:
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 3423 : 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 2287 : bool insert(const T &X) {
93 : assert(X != T() && "Cannot insert a null (default constructed) value!");
94 2287 : auto InsertResult = M.insert({X, V.size()});
95 2287 : if (InsertResult.second) {
96 : // Fresh value, just append it to the vector.
97 2265 : V.push_back(X);
98 2265 : return true;
99 : }
100 :
101 22 : auto &Index = InsertResult.first->second;
102 : assert(V[Index] == X && "Value not actually at index in map!");
103 44 : 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 14 : V[Index] = T();
106 14 : Index = (ptrdiff_t)V.size();
107 14 : V.push_back(X);
108 : }
109 : return false;
110 : }
111 133 :
112 : /// Insert a sequence of new elements into the PriorityWorklist.
113 133 : template <typename SequenceT>
114 133 : typename std::enable_if<!std::is_convertible<SequenceT, T>::value>::type
115 220 : insert(SequenceT &&Input) {
116 348 : if (std::begin(Input) == std::end(Input))
117 128 : // Nothing to do for an empty input sequence.
118 : return;
119 :
120 5 : // First pull the input sequence into the vector as a bulk append
121 : // operation.
122 230 : ptrdiff_t StartIndex = V.size();
123 440 : V.insert(V.end(), std::begin(Input), std::end(Input));
124 5 : // Now walk backwards fixing up the index map and deleting any duplicates.
125 744 : for (ptrdiff_t i = V.size() - 1; i >= StartIndex; --i) {
126 304 : auto InsertResult = M.insert({V[i], i});
127 299 : if (InsertResult.second)
128 299 : continue;
129 :
130 1037 : // If the existing index is before this insert's start, nuke that one and
131 : // move it up.
132 1037 : ptrdiff_t &Index = InsertResult.first->second;
133 1037 : if (Index < StartIndex) {
134 0 : V[Index] = T();
135 1032 : Index = i;
136 1032 : continue;
137 : }
138 :
139 5 : // Otherwise the existing one comes first so just clear out the value in
140 : // this slot.
141 10 : V[i] = T();
142 : }
143 5 : }
144 5 :
145 5 : /// Remove the last element of the PriorityWorklist.
146 134 : 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 268 : M.erase(back());
150 : do {
151 : V.pop_back();
152 134 : } while (!V.empty() && V.back() == T());
153 904 : }
154 768 :
155 : LLVM_NODISCARD T pop_back_val() {
156 134 : T Ret = back();
157 134 : pop_back();
158 : return Ret;
159 : }
160 768 :
161 1535 : /// Erase an item from the worklist.
162 : ///
163 2451 : /// Note that this is constant time due to the nature of the worklist implementation.
164 915 : bool erase(const T& X) {
165 915 : auto I = M.find(X);
166 913 : if (I == M.end())
167 : return false;
168 :
169 : assert(V[I->second] == X && "Value not actually at index in map!");
170 8 : if (I->second == (ptrdiff_t)(V.size() - 1)) {
171 8 : do {
172 6 : V.pop_back();
173 6 : } while (!V.empty() && V.back() == T());
174 6 : } else {
175 0 : V[I->second] = T();
176 : }
177 : M.erase(I);
178 0 : return true;
179 3 : }
180 :
181 : /// Erase items from the set vector based on a predicate function.
182 1 : ///
183 : /// This is intended to be equivalent to the following code, if we could
184 3283 : /// write it:
185 : ///
186 : /// \code
187 6566 : /// V.erase(remove_if(V, P), V.end());
188 : /// \endcode
189 1 : ///
190 3288 : /// However, PriorityWorklist doesn't expose non-const iterators, making any
191 3283 : /// algorithm like remove_if impossible to use.
192 1257 : ///
193 2 : /// \returns true if any element is removed.
194 2 : template <typename UnaryPredicate>
195 2508 : bool erase_if(UnaryPredicate P) {
196 : typename VectorT::iterator E =
197 : remove_if(V, TestAndEraseFromMap<UnaryPredicate>(P, M));
198 1253 : if (E == V.end())
199 1254 : return false;
200 1098 : for (auto I = V.begin(); I != E; ++I)
201 1 : if (*I != T())
202 1 : M[*I] = I - V.begin();
203 2195 : V.erase(E, V.end());
204 : return true;
205 : }
206 1101 :
207 1097 : /// Reverse the items in the PriorityWorklist.
208 933 : ///
209 : /// This does an in-place reversal. Other kinds of reverse aren't easy to
210 210 : /// support in the face of the worklist semantics.
211 2077 :
212 1 : /// Completely clear the PriorityWorklist
213 : void clear() {
214 933 : M.clear();
215 933 : V.clear();
216 : }
217 :
218 3074 : private:
219 3075 : /// A wrapper predicate designed for use with std::remove_if.
220 : ///
221 4 : /// This predicate wraps a predicate suitable for use with std::remove_if to
222 2 : /// call M.erase(x) on each element which is slated for removal. This just
223 2 : /// allows the predicate to be move only which we can't do with lambdas
224 2 : /// today.
225 : template <typename UnaryPredicateT>
226 : class TestAndEraseFromMap {
227 : UnaryPredicateT P;
228 1 : MapT &M;
229 1 :
230 1 : public:
231 1 : TestAndEraseFromMap(UnaryPredicateT P, MapT &M)
232 1 : : 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 0 : return false;
238 :
239 : if (P(Arg)) {
240 2 : M.erase(Arg);
241 2 : return true;
242 : }
243 : return false;
244 : }
245 : };
246 :
247 1 : /// The map from value to index in the vector.
248 2 : MapT M;
249 :
250 7 : /// The vector of elements in insertion order.
251 5 : VectorT V;
252 5 : };
253 4 :
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 59 : class SmallPriorityWorklist
258 2 : : public PriorityWorklist<T, SmallVector<T, N>,
259 1 : SmallDenseMap<T, ptrdiff_t>> {
260 1 : public:
261 1 : SmallPriorityWorklist() = default;
262 : };
263 :
264 : } // end namespace llvm
265 :
266 2 : #endif // LLVM_ADT_PRIORITYWORKLIST_H
|
