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/SmallVector.h" 21 #include <algorithm> 22 #include <cassert> 23 #include <utility> 24 #include <vector> 25 26 namespace llvm { 27 28 /// A FILO worklist that prioritizes on re-insertion without duplication. 29 /// 30 /// This is very similar to a \c SetVector with the primary difference that 31 /// while re-insertion does not create a duplicate, it does adjust the 32 /// visitation order to respect the last insertion point. This can be useful 33 /// when the visit order needs to be prioritized based on insertion point 34 /// without actually having duplicate visits. 35 /// 36 /// Note that this doesn't prevent re-insertion of elements which have been 37 /// visited -- if you need to break cycles, a set will still be necessary. 38 /// 39 /// The type \c T must be default constructable to a null value that will be 40 /// ignored. It is an error to insert such a value, and popping elements will 41 /// never produce such a value. It is expected to be used with common nullable 42 /// types like pointers or optionals. 43 /// 44 /// Internally this uses a vector to store the worklist and a map to identify 45 /// existing elements in the worklist. Both of these may be customized, but the 46 /// map must support the basic DenseMap API for mapping from a T to an integer 47 /// index into the vector. 48 /// 49 /// A partial specialization is provided to automatically select a SmallVector 50 /// and a SmallDenseMap if custom data structures are not provided. 51 template <typename T, typename VectorT = std::vector<T>, 52 typename MapT = DenseMap<T, ptrdiff_t>> 53 class PriorityWorklist { 54 public: 55 typedef T value_type; 56 typedef T key_type; 57 typedef T& reference; 58 typedef const T& const_reference; 59 typedef typename MapT::size_type size_type; 60 61 /// Construct an empty PriorityWorklist PriorityWorklist()62 PriorityWorklist() {} 63 64 /// Determine if the PriorityWorklist is empty or not. empty()65 bool empty() const { 66 return V.empty(); 67 } 68 69 /// Returns the number of elements in the worklist. size()70 size_type size() const { 71 return M.size(); 72 } 73 74 /// Count the number of elements of a given key in the PriorityWorklist. 75 /// \returns 0 if the element is not in the PriorityWorklist, 1 if it is. count(const key_type & key)76 size_type count(const key_type &key) const { 77 return M.count(key); 78 } 79 80 /// Return the last element of the PriorityWorklist. back()81 const T &back() const { 82 assert(!empty() && "Cannot call back() on empty PriorityWorklist!"); 83 return V.back(); 84 } 85 86 /// Insert a new element into the PriorityWorklist. 87 /// \returns true if the element was inserted into the PriorityWorklist. insert(const T & X)88 bool insert(const T &X) { 89 assert(X != T() && "Cannot insert a null (default constructed) value!"); 90 auto InsertResult = M.insert({X, V.size()}); 91 if (InsertResult.second) { 92 // Fresh value, just append it to the vector. 93 V.push_back(X); 94 return true; 95 } 96 97 auto &Index = InsertResult.first->second; 98 assert(V[Index] == X && "Value not actually at index in map!"); 99 if (Index != (ptrdiff_t)(V.size() - 1)) { 100 // If the element isn't at the back, null it out and append a fresh one. 101 V[Index] = T(); 102 Index = (ptrdiff_t)V.size(); 103 V.push_back(X); 104 } 105 return false; 106 } 107 108 /// Remove the last element of the PriorityWorklist. pop_back()109 void pop_back() { 110 assert(!empty() && "Cannot remove an element when empty!"); 111 assert(back() != T() && "Cannot have a null element at the back!"); 112 M.erase(back()); 113 do { 114 V.pop_back(); 115 } while (!V.empty() && V.back() == T()); 116 } 117 pop_back_val()118 T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() { 119 T Ret = back(); 120 pop_back(); 121 return Ret; 122 } 123 124 /// Erase an item from the worklist. 125 /// 126 /// Note that this is constant time due to the nature of the worklist implementation. erase(const T & X)127 bool erase(const T& X) { 128 auto I = M.find(X); 129 if (I == M.end()) 130 return false; 131 132 assert(V[I->second] == X && "Value not actually at index in map!"); 133 if (I->second == (ptrdiff_t)(V.size() - 1)) { 134 do { 135 V.pop_back(); 136 } while (!V.empty() && V.back() == T()); 137 } else { 138 V[I->second] = T(); 139 } 140 M.erase(I); 141 return true; 142 } 143 144 /// Erase items from the set vector based on a predicate function. 145 /// 146 /// This is intended to be equivalent to the following code, if we could 147 /// write it: 148 /// 149 /// \code 150 /// V.erase(std::remove_if(V.begin(), V.end(), P), V.end()); 151 /// \endcode 152 /// 153 /// However, PriorityWorklist doesn't expose non-const iterators, making any 154 /// algorithm like remove_if impossible to use. 155 /// 156 /// \returns true if any element is removed. 157 template <typename UnaryPredicate> erase_if(UnaryPredicate P)158 bool erase_if(UnaryPredicate P) { 159 typename VectorT::iterator E = std::remove_if( 160 V.begin(), V.end(), TestAndEraseFromMap<UnaryPredicate>(P, M)); 161 if (E == V.end()) 162 return false; 163 for (auto I = V.begin(); I != E; ++I) 164 if (*I != T()) 165 M[*I] = I - V.begin(); 166 V.erase(E, V.end()); 167 return true; 168 } 169 170 /// Completely clear the PriorityWorklist clear()171 void clear() { 172 M.clear(); 173 V.clear(); 174 } 175 176 private: 177 /// A wrapper predicate designed for use with std::remove_if. 178 /// 179 /// This predicate wraps a predicate suitable for use with std::remove_if to 180 /// call M.erase(x) on each element which is slated for removal. This just 181 /// allows the predicate to be move only which we can't do with lambdas 182 /// today. 183 template <typename UnaryPredicateT> 184 class TestAndEraseFromMap { 185 UnaryPredicateT P; 186 MapT &M; 187 188 public: TestAndEraseFromMap(UnaryPredicateT P,MapT & M)189 TestAndEraseFromMap(UnaryPredicateT P, MapT &M) 190 : P(std::move(P)), M(M) {} 191 operator()192 bool operator()(const T &Arg) { 193 if (Arg == T()) 194 // Skip null values in the PriorityWorklist. 195 return false; 196 197 if (P(Arg)) { 198 M.erase(Arg); 199 return true; 200 } 201 return false; 202 } 203 }; 204 205 /// The map from value to index in the vector. 206 MapT M; 207 208 /// The vector of elements in insertion order. 209 VectorT V; 210 }; 211 212 /// A version of \c PriorityWorklist that selects small size optimized data 213 /// structures for the vector and map. 214 template <typename T, unsigned N> 215 class SmallPriorityWorklist 216 : public PriorityWorklist<T, SmallVector<T, N>, 217 SmallDenseMap<T, ptrdiff_t>> { 218 public: SmallPriorityWorklist()219 SmallPriorityWorklist() {} 220 }; 221 222 } 223 224 #endif 225