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 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 218 private: 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. 256 template <typename T, unsigned N> 257 class SmallPriorityWorklist 258 : public PriorityWorklist<T, SmallVector<T, N>, 259 SmallDenseMap<T, ptrdiff_t>> { 260 public: 261 SmallPriorityWorklist() = default; 262 }; 263 264 } // end namespace llvm 265 266 #endif // LLVM_ADT_PRIORITYWORKLIST_H 267
