1 //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- 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 // This file implements a set that has insertion order iteration 11 // characteristics. This is useful for keeping a set of things that need to be 12 // visited later but in a deterministic order (insertion order). The interface 13 // is purposefully minimal. 14 // 15 // This file defines SetVector and SmallSetVector, which performs no allocations 16 // if the SetVector has less than a certain number of elements. 17 // 18 //===----------------------------------------------------------------------===// 19 20 #ifndef LLVM_ADT_SETVECTOR_H 21 #define LLVM_ADT_SETVECTOR_H 22 23 #include "llvm/ADT/ArrayRef.h" 24 #include "llvm/ADT/DenseSet.h" 25 #include "llvm/ADT/STLExtras.h" 26 #include "llvm/Support/Compiler.h" 27 #include <algorithm> 28 #include <cassert> 29 #include <iterator> 30 #include <vector> 31 32 namespace llvm { 33 34 /// \brief A vector that has set insertion semantics. 35 /// 36 /// This adapter class provides a way to keep a set of things that also has the 37 /// property of a deterministic iteration order. The order of iteration is the 38 /// order of insertion. 39 template <typename T, typename Vector = std::vector<T>, 40 typename Set = DenseSet<T>> 41 class SetVector { 42 public: 43 using value_type = T; 44 using key_type = T; 45 using reference = T&; 46 using const_reference = const T&; 47 using set_type = Set; 48 using vector_type = Vector; 49 using iterator = typename vector_type::const_iterator; 50 using const_iterator = typename vector_type::const_iterator; 51 using reverse_iterator = typename vector_type::const_reverse_iterator; 52 using const_reverse_iterator = typename vector_type::const_reverse_iterator; 53 using size_type = typename vector_type::size_type; 54 55 /// \brief Construct an empty SetVector 56 SetVector() = default; 57 58 /// \brief Initialize a SetVector with a range of elements 59 template<typename It> 60 SetVector(It Start, It End) { 61 insert(Start, End); 62 } 63 64 ArrayRef<T> getArrayRef() const { return vector_; } 65 66 /// Clear the SetVector and return the underlying vector. 67 Vector takeVector() { 68 set_.clear(); 69 return std::move(vector_); 70 } 71 72 /// \brief Determine if the SetVector is empty or not. 73 bool empty() const { 74 return vector_.empty(); 75 } 76 77 /// \brief Determine the number of elements in the SetVector. 78 size_type size() const { 79 return vector_.size(); 80 } 81 82 /// \brief Get an iterator to the beginning of the SetVector. 83 iterator begin() { 84 return vector_.begin(); 85 } 86 87 /// \brief Get a const_iterator to the beginning of the SetVector. 88 const_iterator begin() const { 89 return vector_.begin(); 90 } 91 92 /// \brief Get an iterator to the end of the SetVector. 93 iterator end() { 94 return vector_.end(); 95 } 96 97 /// \brief Get a const_iterator to the end of the SetVector. 98 const_iterator end() const { 99 return vector_.end(); 100 } 101 102 /// \brief Get an reverse_iterator to the end of the SetVector. 103 reverse_iterator rbegin() { 104 return vector_.rbegin(); 105 } 106 107 /// \brief Get a const_reverse_iterator to the end of the SetVector. 108 const_reverse_iterator rbegin() const { 109 return vector_.rbegin(); 110 } 111 112 /// \brief Get a reverse_iterator to the beginning of the SetVector. 113 reverse_iterator rend() { 114 return vector_.rend(); 115 } 116 117 /// \brief Get a const_reverse_iterator to the beginning of the SetVector. 118 const_reverse_iterator rend() const { 119 return vector_.rend(); 120 } 121 122 /// \brief Return the first element of the SetVector. 123 const T &front() const { 124 assert(!empty() && "Cannot call front() on empty SetVector!"); 125 return vector_.front(); 126 } 127 128 /// \brief Return the last element of the SetVector. 129 const T &back() const { 130 assert(!empty() && "Cannot call back() on empty SetVector!"); 131 return vector_.back(); 132 } 133 134 /// \brief Index into the SetVector. 135 const_reference operator[](size_type n) const { 136 assert(n < vector_.size() && "SetVector access out of range!"); 137 return vector_[n]; 138 } 139 140 /// \brief Insert a new element into the SetVector. 141 /// \returns true if the element was inserted into the SetVector. 142 bool insert(const value_type &X) { 143 bool result = set_.insert(X).second; 144 if (result) 145 vector_.push_back(X); 146 return result; 147 } 148 149 /// \brief Insert a range of elements into the SetVector. 150 template<typename It> 151 void insert(It Start, It End) { 152 for (; Start != End; ++Start) 153 if (set_.insert(*Start).second) 154 vector_.push_back(*Start); 155 } 156 157 /// \brief Remove an item from the set vector. 158 bool remove(const value_type& X) { 159 if (set_.erase(X)) { 160 typename vector_type::iterator I = find(vector_, X); 161 assert(I != vector_.end() && "Corrupted SetVector instances!"); 162 vector_.erase(I); 163 return true; 164 } 165 return false; 166 } 167 168 /// Erase a single element from the set vector. 169 /// \returns an iterator pointing to the next element that followed the 170 /// element erased. This is the end of the SetVector if the last element is 171 /// erased. 172 iterator erase(iterator I) { 173 const key_type &V = *I; 174 assert(set_.count(V) && "Corrupted SetVector instances!"); 175 set_.erase(V); 176 177 // FIXME: No need to use the non-const iterator when built with 178 // std:vector.erase(const_iterator) as defined in C++11. This is for 179 // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9). 180 auto NI = vector_.begin(); 181 std::advance(NI, std::distance<iterator>(NI, I)); 182 183 return vector_.erase(NI); 184 } 185 186 /// \brief Remove items from the set vector based on a predicate function. 187 /// 188 /// This is intended to be equivalent to the following code, if we could 189 /// write it: 190 /// 191 /// \code 192 /// V.erase(remove_if(V, P), V.end()); 193 /// \endcode 194 /// 195 /// However, SetVector doesn't expose non-const iterators, making any 196 /// algorithm like remove_if impossible to use. 197 /// 198 /// \returns true if any element is removed. 199 template <typename UnaryPredicate> 200 bool remove_if(UnaryPredicate P) { 201 typename vector_type::iterator I = 202 llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_)); 203 if (I == vector_.end()) 204 return false; 205 vector_.erase(I, vector_.end()); 206 return true; 207 } 208 209 /// \brief Count the number of elements of a given key in the SetVector. 210 /// \returns 0 if the element is not in the SetVector, 1 if it is. 211 size_type count(const key_type &key) const { 212 return set_.count(key); 213 } 214 215 /// \brief Completely clear the SetVector 216 void clear() { 217 set_.clear(); 218 vector_.clear(); 219 } 220 221 /// \brief Remove the last element of the SetVector. 222 void pop_back() { 223 assert(!empty() && "Cannot remove an element from an empty SetVector!"); 224 set_.erase(back()); 225 vector_.pop_back(); 226 } 227 228 LLVM_NODISCARD T pop_back_val() { 229 T Ret = back(); 230 pop_back(); 231 return Ret; 232 } 233 234 bool operator==(const SetVector &that) const { 235 return vector_ == that.vector_; 236 } 237 238 bool operator!=(const SetVector &that) const { 239 return vector_ != that.vector_; 240 } 241 242 /// \brief Compute This := This u S, return whether 'This' changed. 243 /// TODO: We should be able to use set_union from SetOperations.h, but 244 /// SetVector interface is inconsistent with DenseSet. 245 template <class STy> 246 bool set_union(const STy &S) { 247 bool Changed = false; 248 249 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 250 ++SI) 251 if (insert(*SI)) 252 Changed = true; 253 254 return Changed; 255 } 256 257 /// \brief Compute This := This - B 258 /// TODO: We should be able to use set_subtract from SetOperations.h, but 259 /// SetVector interface is inconsistent with DenseSet. 260 template <class STy> 261 void set_subtract(const STy &S) { 262 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 263 ++SI) 264 remove(*SI); 265 } 266 267 private: 268 /// \brief A wrapper predicate designed for use with std::remove_if. 269 /// 270 /// This predicate wraps a predicate suitable for use with std::remove_if to 271 /// call set_.erase(x) on each element which is slated for removal. 272 template <typename UnaryPredicate> 273 class TestAndEraseFromSet { 274 UnaryPredicate P; 275 set_type &set_; 276 277 public: 278 TestAndEraseFromSet(UnaryPredicate P, set_type &set_) 279 : P(std::move(P)), set_(set_) {} 280 281 template <typename ArgumentT> 282 bool operator()(const ArgumentT &Arg) { 283 if (P(Arg)) { 284 set_.erase(Arg); 285 return true; 286 } 287 return false; 288 } 289 }; 290 291 set_type set_; ///< The set. 292 vector_type vector_; ///< The vector. 293 }; 294 295 /// \brief A SetVector that performs no allocations if smaller than 296 /// a certain size. 297 template <typename T, unsigned N> 298 class SmallSetVector 299 : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> { 300 public: 301 SmallSetVector() = default; 302 303 /// \brief Initialize a SmallSetVector with a range of elements 304 template<typename It> 305 SmallSetVector(It Start, It End) { 306 this->insert(Start, End); 307 } 308 }; 309 310 } // end namespace llvm 311 312 #endif // LLVM_ADT_SETVECTOR_H 313
