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/DenseSet.h" 24 #include "llvm/ADT/SmallSet.h" 25 #include <algorithm> 26 #include <cassert> 27 #include <vector> 28 29 namespace llvm { 30 31 /// \brief A vector that has set insertion semantics. 32 /// 33 /// This adapter class provides a way to keep a set of things that also has the 34 /// property of a deterministic iteration order. The order of iteration is the 35 /// order of insertion. 36 template <typename T, typename Vector = std::vector<T>, 37 typename Set = DenseSet<T>> 38 class SetVector { 39 public: 40 typedef T value_type; 41 typedef T key_type; 42 typedef T& reference; 43 typedef const T& const_reference; 44 typedef Set set_type; 45 typedef Vector vector_type; 46 typedef typename vector_type::const_iterator iterator; 47 typedef typename vector_type::const_iterator const_iterator; 48 typedef typename vector_type::const_reverse_iterator reverse_iterator; 49 typedef typename vector_type::const_reverse_iterator const_reverse_iterator; 50 typedef typename vector_type::size_type size_type; 51 52 /// \brief Construct an empty SetVector SetVector()53 SetVector() {} 54 55 /// \brief Initialize a SetVector with a range of elements 56 template<typename It> SetVector(It Start,It End)57 SetVector(It Start, It End) { 58 insert(Start, End); 59 } 60 getArrayRef()61 ArrayRef<T> getArrayRef() const { return vector_; } 62 63 /// \brief Determine if the SetVector is empty or not. empty()64 bool empty() const { 65 return vector_.empty(); 66 } 67 68 /// \brief Determine the number of elements in the SetVector. size()69 size_type size() const { 70 return vector_.size(); 71 } 72 73 /// \brief Get an iterator to the beginning of the SetVector. begin()74 iterator begin() { 75 return vector_.begin(); 76 } 77 78 /// \brief Get a const_iterator to the beginning of the SetVector. begin()79 const_iterator begin() const { 80 return vector_.begin(); 81 } 82 83 /// \brief Get an iterator to the end of the SetVector. end()84 iterator end() { 85 return vector_.end(); 86 } 87 88 /// \brief Get a const_iterator to the end of the SetVector. end()89 const_iterator end() const { 90 return vector_.end(); 91 } 92 93 /// \brief Get an reverse_iterator to the end of the SetVector. rbegin()94 reverse_iterator rbegin() { 95 return vector_.rbegin(); 96 } 97 98 /// \brief Get a const_reverse_iterator to the end of the SetVector. rbegin()99 const_reverse_iterator rbegin() const { 100 return vector_.rbegin(); 101 } 102 103 /// \brief Get a reverse_iterator to the beginning of the SetVector. rend()104 reverse_iterator rend() { 105 return vector_.rend(); 106 } 107 108 /// \brief Get a const_reverse_iterator to the beginning of the SetVector. rend()109 const_reverse_iterator rend() const { 110 return vector_.rend(); 111 } 112 113 /// \brief Return the last element of the SetVector. back()114 const T &back() const { 115 assert(!empty() && "Cannot call back() on empty SetVector!"); 116 return vector_.back(); 117 } 118 119 /// \brief Index into the SetVector. 120 const_reference operator[](size_type n) const { 121 assert(n < vector_.size() && "SetVector access out of range!"); 122 return vector_[n]; 123 } 124 125 /// \brief Insert a new element into the SetVector. 126 /// \returns true iff the element was inserted into the SetVector. insert(const value_type & X)127 bool insert(const value_type &X) { 128 bool result = set_.insert(X).second; 129 if (result) 130 vector_.push_back(X); 131 return result; 132 } 133 134 /// \brief Insert a range of elements into the SetVector. 135 template<typename It> insert(It Start,It End)136 void insert(It Start, It End) { 137 for (; Start != End; ++Start) 138 if (set_.insert(*Start).second) 139 vector_.push_back(*Start); 140 } 141 142 /// \brief Remove an item from the set vector. remove(const value_type & X)143 bool remove(const value_type& X) { 144 if (set_.erase(X)) { 145 typename vector_type::iterator I = 146 std::find(vector_.begin(), vector_.end(), X); 147 assert(I != vector_.end() && "Corrupted SetVector instances!"); 148 vector_.erase(I); 149 return true; 150 } 151 return false; 152 } 153 154 /// \brief Remove items from the set vector based on a predicate function. 155 /// 156 /// This is intended to be equivalent to the following code, if we could 157 /// write it: 158 /// 159 /// \code 160 /// V.erase(std::remove_if(V.begin(), V.end(), P), V.end()); 161 /// \endcode 162 /// 163 /// However, SetVector doesn't expose non-const iterators, making any 164 /// algorithm like remove_if impossible to use. 165 /// 166 /// \returns true if any element is removed. 167 template <typename UnaryPredicate> remove_if(UnaryPredicate P)168 bool remove_if(UnaryPredicate P) { 169 typename vector_type::iterator I 170 = std::remove_if(vector_.begin(), vector_.end(), 171 TestAndEraseFromSet<UnaryPredicate>(P, set_)); 172 if (I == vector_.end()) 173 return false; 174 vector_.erase(I, vector_.end()); 175 return true; 176 } 177 178 /// \brief Count the number of elements of a given key in the SetVector. 179 /// \returns 0 if the element is not in the SetVector, 1 if it is. count(const key_type & key)180 size_type count(const key_type &key) const { 181 return set_.count(key); 182 } 183 184 /// \brief Completely clear the SetVector clear()185 void clear() { 186 set_.clear(); 187 vector_.clear(); 188 } 189 190 /// \brief Remove the last element of the SetVector. pop_back()191 void pop_back() { 192 assert(!empty() && "Cannot remove an element from an empty SetVector!"); 193 set_.erase(back()); 194 vector_.pop_back(); 195 } 196 pop_back_val()197 T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() { 198 T Ret = back(); 199 pop_back(); 200 return Ret; 201 } 202 203 bool operator==(const SetVector &that) const { 204 return vector_ == that.vector_; 205 } 206 207 bool operator!=(const SetVector &that) const { 208 return vector_ != that.vector_; 209 } 210 211 private: 212 /// \brief A wrapper predicate designed for use with std::remove_if. 213 /// 214 /// This predicate wraps a predicate suitable for use with std::remove_if to 215 /// call set_.erase(x) on each element which is slated for removal. 216 template <typename UnaryPredicate> 217 class TestAndEraseFromSet { 218 UnaryPredicate P; 219 set_type &set_; 220 221 public: TestAndEraseFromSet(UnaryPredicate P,set_type & set_)222 TestAndEraseFromSet(UnaryPredicate P, set_type &set_) : P(P), set_(set_) {} 223 224 template <typename ArgumentT> operator()225 bool operator()(const ArgumentT &Arg) { 226 if (P(Arg)) { 227 set_.erase(Arg); 228 return true; 229 } 230 return false; 231 } 232 }; 233 234 set_type set_; ///< The set. 235 vector_type vector_; ///< The vector. 236 }; 237 238 /// \brief A SetVector that performs no allocations if smaller than 239 /// a certain size. 240 template <typename T, unsigned N> 241 class SmallSetVector : public SetVector<T, SmallVector<T, N>, SmallSet<T, N> > { 242 public: SmallSetVector()243 SmallSetVector() {} 244 245 /// \brief Initialize a SmallSetVector with a range of elements 246 template<typename It> SmallSetVector(It Start,It End)247 SmallSetVector(It Start, It End) { 248 this->insert(Start, End); 249 } 250 }; 251 252 } // End llvm namespace 253 254 // vim: sw=2 ai 255 #endif 256