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