SetVector.h revision 341825
1163953Srrs//===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===// 2185694Srrs// 3218269Srrs// The LLVM Compiler Infrastructure 4218269Srrs// 5163953Srrs// This file is distributed under the University of Illinois Open Source 6163953Srrs// License. See LICENSE.TXT for details. 7163953Srrs// 8163953Srrs//===----------------------------------------------------------------------===// 9163953Srrs// 10163953Srrs// This file implements a set that has insertion order iteration 11163953Srrs// characteristics. This is useful for keeping a set of things that need to be 12163953Srrs// visited later but in a deterministic order (insertion order). The interface 13163953Srrs// is purposefully minimal. 14163953Srrs// 15163953Srrs// This file defines SetVector and SmallSetVector, which performs no allocations 16163953Srrs// if the SetVector has less than a certain number of elements. 17163953Srrs// 18163953Srrs//===----------------------------------------------------------------------===// 19163953Srrs 20163953Srrs#ifndef LLVM_ADT_SETVECTOR_H 21163953Srrs#define LLVM_ADT_SETVECTOR_H 22163953Srrs 23163953Srrs#include "llvm/ADT/ArrayRef.h" 24163953Srrs#include "llvm/ADT/DenseSet.h" 25163953Srrs#include "llvm/ADT/STLExtras.h" 26163953Srrs#include "llvm/Support/Compiler.h" 27163953Srrs#include <algorithm> 28163953Srrs#include <cassert> 29163953Srrs#include <iterator> 30163953Srrs#include <vector> 31163953Srrs 32163953Srrsnamespace llvm { 33163953Srrs 34163953Srrs/// A vector that has set insertion semantics. 35163953Srrs/// 36163953Srrs/// This adapter class provides a way to keep a set of things that also has the 37163953Srrs/// property of a deterministic iteration order. The order of iteration is the 38163953Srrs/// order of insertion. 39163953Srrstemplate <typename T, typename Vector = std::vector<T>, 40167598Srrs typename Set = DenseSet<T>> 41163953Srrsclass SetVector { 42163953Srrspublic: 43163953Srrs using value_type = T; 44163953Srrs using key_type = T; 45163953Srrs using reference = T&; 46163953Srrs using const_reference = const T&; 47163953Srrs using set_type = Set; 48163953Srrs using vector_type = Vector; 49170091Srrs using iterator = typename vector_type::const_iterator; 50172091Srrs using const_iterator = typename vector_type::const_iterator; 51188067Srrs using reverse_iterator = typename vector_type::const_reverse_iterator; 52179157Srrs using const_reverse_iterator = typename vector_type::const_reverse_iterator; 53218211Srrs using size_type = typename vector_type::size_type; 54163953Srrs 55163953Srrs /// Construct an empty SetVector 56163953Srrs SetVector() = default; 57163953Srrs 58163953Srrs /// Initialize a SetVector with a range of elements 59163953Srrs template<typename It> 60163953Srrs SetVector(It Start, It End) { 61163953Srrs insert(Start, End); 62165220Srrs } 63165220Srrs 64165220Srrs ArrayRef<T> getArrayRef() const { return vector_; } 65165220Srrs 66165220Srrs /// Clear the SetVector and return the underlying vector. 67163953Srrs Vector takeVector() { 68163953Srrs set_.clear(); 69165220Srrs return std::move(vector_); 70163953Srrs } 71163953Srrs 72163953Srrs /// Determine if the SetVector is empty or not. 73165220Srrs bool empty() const { 74165220Srrs return vector_.empty(); 75165220Srrs } 76165220Srrs 77165220Srrs /// Determine the number of elements in the SetVector. 78165220Srrs size_type size() const { 79163953Srrs return vector_.size(); 80163953Srrs } 81163953Srrs 82163953Srrs /// Get an iterator to the beginning of the SetVector. 83163953Srrs iterator begin() { 84163953Srrs return vector_.begin(); 85163953Srrs } 86163953Srrs 87179157Srrs /// Get a const_iterator to the beginning of the SetVector. 88163953Srrs const_iterator begin() const { 89163953Srrs return vector_.begin(); 90163953Srrs } 91163953Srrs 92163953Srrs /// Get an iterator to the end of the SetVector. 93169420Srrs iterator end() { 94169420Srrs return vector_.end(); 95172396Srrs } 96172396Srrs 97172396Srrs /// Get a const_iterator to the end of the SetVector. 98172396Srrs const_iterator end() const { 99172396Srrs return vector_.end(); 100172396Srrs } 101163953Srrs 102163953Srrs /// Get an reverse_iterator to the end of the SetVector. 103163953Srrs reverse_iterator rbegin() { 104163953Srrs return vector_.rbegin(); 105169420Srrs } 106169420Srrs 107169420Srrs /// Get a const_reverse_iterator to the end of the SetVector. 108163953Srrs const_reverse_iterator rbegin() const { 109163953Srrs return vector_.rbegin(); 110179141Srrs } 111179141Srrs 112179141Srrs /// Get a reverse_iterator to the beginning of the SetVector. 113179141Srrs reverse_iterator rend() { 114179141Srrs return vector_.rend(); 115179141Srrs } 116179141Srrs 117179141Srrs /// Get a const_reverse_iterator to the beginning of the SetVector. 118179141Srrs const_reverse_iterator rend() const { 119163953Srrs return vector_.rend(); 120169352Srrs } 121179157Srrs 122168299Srrs /// Return the first element of the SetVector. 123168299Srrs const T &front() const { 124172396Srrs assert(!empty() && "Cannot call front() on empty SetVector!"); 125163953Srrs return vector_.front(); 126163953Srrs } 127163953Srrs 128163953Srrs /// Return the last element of the SetVector. 129169352Srrs const T &back() const { 130179157Srrs assert(!empty() && "Cannot call back() on empty SetVector!"); 131168299Srrs return vector_.back(); 132168299Srrs } 133172396Srrs 134163953Srrs /// Index into the SetVector. 135163953Srrs const_reference operator[](size_type n) const { 136163953Srrs assert(n < vector_.size() && "SetVector access out of range!"); 137163953Srrs return vector_[n]; 138163953Srrs } 139169352Srrs 140179157Srrs /// Insert a new element into the SetVector. 141168299Srrs /// \returns true if the element was inserted into the SetVector. 142168299Srrs bool insert(const value_type &X) { 143172396Srrs bool result = set_.insert(X).second; 144163953Srrs if (result) 145163953Srrs vector_.push_back(X); 146163953Srrs return result; 147163953Srrs } 148169352Srrs 149179157Srrs /// Insert a range of elements into the SetVector. 150171440Srrs template<typename It> 151171440Srrs void insert(It Start, It End) { 152172396Srrs for (; Start != End; ++Start) 153163953Srrs if (set_.insert(*Start).second) 154163953Srrs vector_.push_back(*Start); 155163953Srrs } 156163953Srrs 157169352Srrs /// Remove an item from the set vector. 158179157Srrs bool remove(const value_type& X) { 159168299Srrs if (set_.erase(X)) { 160168299Srrs typename vector_type::iterator I = find(vector_, X); 161172396Srrs assert(I != vector_.end() && "Corrupted SetVector instances!"); 162163953Srrs vector_.erase(I); 163163953Srrs return true; 164163953Srrs } 165163953Srrs return false; 166169352Srrs } 167179157Srrs 168168299Srrs /// Erase a single element from the set vector. 169168299Srrs /// \returns an iterator pointing to the next element that followed the 170172396Srrs /// element erased. This is the end of the SetVector if the last element is 171163953Srrs /// erased. 172163953Srrs iterator erase(iterator I) { 173163953Srrs const key_type &V = *I; 174163953Srrs assert(set_.count(V) && "Corrupted SetVector instances!"); 175163953Srrs set_.erase(V); 176179157Srrs 177168299Srrs // FIXME: No need to use the non-const iterator when built with 178168299Srrs // std:vector.erase(const_iterator) as defined in C++11. This is for 179172396Srrs // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9). 180163953Srrs auto NI = vector_.begin(); 181163953Srrs std::advance(NI, std::distance<iterator>(NI, I)); 182169420Srrs 183179157Srrs return vector_.erase(NI); 184172703Srrs } 185172396Srrs 186172396Srrs /// Remove items from the set vector based on a predicate function. 187172396Srrs /// 188172396Srrs /// This is intended to be equivalent to the following code, if we could 189163953Srrs /// write it: 190163953Srrs /// 191163953Srrs /// \code 192163953Srrs /// V.erase(remove_if(V, P), V.end()); 193163953Srrs /// \endcode 194171158Srrs /// 195171158Srrs /// However, SetVector doesn't expose non-const iterators, making any 196171158Srrs /// algorithm like remove_if impossible to use. 197171158Srrs /// 198171158Srrs /// \returns true if any element is removed. 199217760Stuexen template <typename UnaryPredicate> 200217760Stuexen bool remove_if(UnaryPredicate P) { 201171158Srrs typename vector_type::iterator I = 202171158Srrs llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_)); 203171158Srrs if (I == vector_.end()) 204171158Srrs return false; 205171158Srrs vector_.erase(I, vector_.end()); 206171158Srrs return true; 207171158Srrs } 208171158Srrs 209171158Srrs /// Count the number of elements of a given key in the SetVector. 210171158Srrs /// \returns 0 if the element is not in the SetVector, 1 if it is. 211217760Stuexen size_type count(const key_type &key) const { 212217760Stuexen return set_.count(key); 213217760Stuexen } 214217760Stuexen 215217760Stuexen /// Completely clear the SetVector 216217760Stuexen void clear() { 217217760Stuexen set_.clear(); 218217760Stuexen vector_.clear(); 219171158Srrs } 220171158Srrs 221171158Srrs /// Remove the last element of the SetVector. 222171158Srrs void pop_back() { 223171158Srrs assert(!empty() && "Cannot remove an element from an empty SetVector!"); 224171158Srrs set_.erase(back()); 225171158Srrs vector_.pop_back(); 226171158Srrs } 227171158Srrs 228171158Srrs LLVM_NODISCARD T pop_back_val() { 229171158Srrs T Ret = back(); 230171158Srrs pop_back(); 231171158Srrs return Ret; 232171158Srrs } 233171158Srrs 234171158Srrs bool operator==(const SetVector &that) const { 235217760Stuexen return vector_ == that.vector_; 236217760Stuexen } 237212712Stuexen 238212712Stuexen bool operator!=(const SetVector &that) const { 239212712Stuexen return vector_ != that.vector_; 240212712Stuexen } 241171158Srrs 242171158Srrs /// Compute This := This u S, return whether 'This' changed. 243171158Srrs /// TODO: We should be able to use set_union from SetOperations.h, but 244171158Srrs /// SetVector interface is inconsistent with DenseSet. 245171158Srrs template <class STy> 246171158Srrs bool set_union(const STy &S) { 247171158Srrs bool Changed = false; 248216822Stuexen 249171158Srrs for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 250171158Srrs ++SI) 251171158Srrs if (insert(*SI)) 252171158Srrs Changed = true; 253171158Srrs 254171158Srrs return Changed; 255171158Srrs } 256163953Srrs 257163953Srrs /// Compute This := This - B 258163953Srrs /// TODO: We should be able to use set_subtract from SetOperations.h, but 259163953Srrs /// SetVector interface is inconsistent with DenseSet. 260163953Srrs template <class STy> 261163953Srrs void set_subtract(const STy &S) { 262163953Srrs for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE; 263163953Srrs ++SI) 264163953Srrs remove(*SI); 265163953Srrs } 266163953Srrs 267163953Srrsprivate: 268163953Srrs /// A wrapper predicate designed for use with std::remove_if. 269163953Srrs /// 270218129Srrs /// This predicate wraps a predicate suitable for use with std::remove_if to 271218129Srrs /// call set_.erase(x) on each element which is slated for removal. 272218129Srrs template <typename UnaryPredicate> 273212712Stuexen class TestAndEraseFromSet { 274163953Srrs UnaryPredicate P; 275163953Srrs set_type &set_; 276163953Srrs 277179783Srrs public: 278170744Srrs TestAndEraseFromSet(UnaryPredicate P, set_type &set_) 279170744Srrs : P(std::move(P)), set_(set_) {} 280163953Srrs 281163953Srrs template <typename ArgumentT> 282164181Srrs bool operator()(const ArgumentT &Arg) { 283163953Srrs if (P(Arg)) { 284163953Srrs set_.erase(Arg); 285163953Srrs return true; 286216822Stuexen } 287216822Stuexen return false; 288163953Srrs } 289196260Stuexen }; 290163953Srrs 291216822Stuexen set_type set_; ///< The set. 292216822Stuexen vector_type vector_; ///< The vector. 293216822Stuexen}; 294216822Stuexen 295216822Stuexen/// A SetVector that performs no allocations if smaller than 296216822Stuexen/// a certain size. 297216822Stuexentemplate <typename T, unsigned N> 298216822Stuexenclass SmallSetVector 299216822Stuexen : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> { 300216822Stuexenpublic: 301216822Stuexen SmallSetVector() = default; 302196260Stuexen 303196260Stuexen /// Initialize a SmallSetVector with a range of elements 304216822Stuexen template<typename It> 305216822Stuexen SmallSetVector(It Start, It End) { 306196260Stuexen this->insert(Start, End); 307196260Stuexen } 308163953Srrs}; 309163953Srrs 310163953Srrs} // end namespace llvm 311216822Stuexen 312196260Stuexen#endif // LLVM_ADT_SETVECTOR_H 313163953Srrs