LLVM  6.0.0svn
SetVector.h
Go to the documentation of this file.
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;
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.
84  return vector_.begin();
85  }
86 
87  /// \brief Get a const_iterator to the beginning of the SetVector.
89  return vector_.begin();
90  }
91 
92  /// \brief Get an iterator to the end of the SetVector.
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.
104  return vector_.rbegin();
105  }
106 
107  /// \brief Get a const_reverse_iterator to the end of the SetVector.
109  return vector_.rbegin();
110  }
111 
112  /// \brief Get a reverse_iterator to the beginning of the SetVector.
114  return vector_.rend();
115  }
116 
117  /// \brief Get a const_reverse_iterator to the beginning of the SetVector.
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.
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.
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 
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>
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
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: SmallVector.h:106
typename vector_type::const_reverse_iterator reverse_iterator
Definition: SetVector.h:51
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:329
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:228
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:123
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
ArrayRef< T > getArrayRef() const
Definition: SetVector.h:64
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:78
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:856
bool erase(const ValueT &V)
Definition: DenseSet.h:95
iterator erase(iterator I)
Erase a single element from the set vector.
Definition: SetVector.h:172
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:93
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:129
SetVector()=default
Construct an empty SetVector.
typename SuperClass::size_type size_type
Definition: SmallVector.h:330
const_iterator end() const
Get a const_iterator to the end of the SetVector.
Definition: SetVector.h:98
reverse_iterator rbegin()
Get an reverse_iterator to the end of the SetVector.
Definition: SetVector.h:103
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:222
const_reference operator[](size_type n) const
Index into the SetVector.
Definition: SetVector.h:135
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
#define T
typename vector_type::const_reverse_iterator const_reverse_iterator
Definition: SetVector.h:52
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:83
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
const_reverse_iterator rbegin() const
Get a const_reverse_iterator to the end of the SetVector.
Definition: SetVector.h:108
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:211
#define P(N)
bool set_union(const STy &S)
Compute This := This u S, return whether &#39;This&#39; changed.
Definition: SetVector.h:246
static const unsigned End
void insert(It Start, It End)
Insert a range of elements into the SetVector.
Definition: SetVector.h:151
bool operator==(const SetVector &that) const
Definition: SetVector.h:234
SetVector(It Start, It End)
Initialize a SetVector with a range of elements.
Definition: SetVector.h:60
bool operator!=(const SetVector &that) const
Definition: SetVector.h:238
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:67
auto find(R &&Range, const T &Val) -> decltype(std::begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:837
void set_subtract(const STy &S)
Compute This := This - B TODO: We should be able to use set_subtract from SetOperations.h, but SetVector interface is inconsistent with DenseSet.
Definition: SetVector.h:261
void clear()
Completely clear the SetVector.
Definition: SetVector.h:216
typename SuperClass::iterator iterator
Definition: SmallVector.h:328
amdgpu Simplify well known AMD library false Value Value * Arg
reverse_iterator rend()
Get a reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:113
#define I(x, y, z)
Definition: MD5.cpp:58
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:73
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:126
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallSetVector(It Start, It End)
Initialize a SmallSetVector with a range of elements.
Definition: SetVector.h:305
A vector that has set insertion semantics.
Definition: SetVector.h:41
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
Definition: SetVector.h:200
const_reverse_iterator rend() const
Get a const_reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:118
const_iterator begin() const
Get a const_iterator to the beginning of the SetVector.
Definition: SetVector.h:88