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