LLVM  10.0.0svn
SetVector.h
Go to the documentation of this file.
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;
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>
59  SetVector(It Start, It End) {
60  insert(Start, End);
61  }
62 
63  ArrayRef<T> getArrayRef() const { return vector_; }
64 
65  /// Clear the SetVector and return the underlying vector.
67  set_.clear();
68  return std::move(vector_);
69  }
70 
71  /// Determine if the SetVector is empty or not.
72  bool empty() const {
73  return vector_.empty();
74  }
75 
76  /// Determine the number of elements in the SetVector.
77  size_type size() const {
78  return vector_.size();
79  }
80 
81  /// Get an iterator to the beginning of the SetVector.
83  return vector_.begin();
84  }
85 
86  /// Get a const_iterator to the beginning of the SetVector.
88  return vector_.begin();
89  }
90 
91  /// Get an iterator to the end of the SetVector.
93  return vector_.end();
94  }
95 
96  /// Get a const_iterator to the end of the SetVector.
97  const_iterator end() const {
98  return vector_.end();
99  }
100 
101  /// Get an reverse_iterator to the end of the SetVector.
103  return vector_.rbegin();
104  }
105 
106  /// Get a const_reverse_iterator to the end of the SetVector.
108  return vector_.rbegin();
109  }
110 
111  /// Get a reverse_iterator to the beginning of the SetVector.
113  return vector_.rend();
114  }
115 
116  /// Get a const_reverse_iterator to the beginning of the SetVector.
118  return vector_.rend();
119  }
120 
121  /// Return the first element of the SetVector.
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.
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.
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.
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>
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.
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.
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>
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.
210  size_type count(const key_type &key) const {
211  return set_.count(key);
212  }
213 
214  /// Completely clear the SetVector
215  void clear() {
216  set_.clear();
217  vector_.clear();
218  }
219 
220  /// Remove the last element of the SetVector.
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 
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>
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>
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:
277  TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
278  : P(std::move(P)), set_(set_) {}
279 
280  template <typename ArgumentT>
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>
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>
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
typename vector_type::const_reverse_iterator reverse_iterator
Definition: SetVector.h:50
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:227
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:122
This class represents lattice values for constants.
Definition: AllocatorList.h:23
ArrayRef< T > getArrayRef() const
Definition: SetVector.h:63
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
bool erase(const ValueT &V)
Definition: DenseSet.h:95
iterator erase(iterator I)
Erase a single element from the set vector.
Definition: SetVector.h:171
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
SetVector()=default
Construct an empty SetVector.
const_iterator end() const
Get a const_iterator to the end of the SetVector.
Definition: SetVector.h:97
std::vector< llvm::SUnit *> vector_type
Definition: SetVector.h:47
typename vector_type::size_type size_type
Definition: SetVector.h:52
reverse_iterator rbegin()
Get an reverse_iterator to the end of the SetVector.
Definition: SetVector.h:102
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:221
const_reference operator[](size_type n) const
Index into the SetVector.
Definition: SetVector.h:134
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
typename vector_type::const_reverse_iterator const_reverse_iterator
Definition: SetVector.h:51
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
const_reverse_iterator rbegin() const
Get a const_reverse_iterator to the end of the SetVector.
Definition: SetVector.h:107
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:210
#define P(N)
bool set_union(const STy &S)
Compute This := This u S, return whether &#39;This&#39; changed.
Definition: SetVector.h:245
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1205
void insert(It Start, It End)
Insert a range of elements into the SetVector.
Definition: SetVector.h:150
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1186
typename vector_type::const_iterator const_iterator
Definition: SetVector.h:49
bool operator==(const SetVector &that) const
Definition: SetVector.h:233
SetVector(It Start, It End)
Initialize a SetVector with a range of elements.
Definition: SetVector.h:59
bool operator!=(const SetVector &that) const
Definition: SetVector.h:237
typename vector_type::const_iterator iterator
Definition: SetVector.h:48
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:66
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:260
void clear()
Completely clear the SetVector.
Definition: SetVector.h:215
reverse_iterator rend()
Get a reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:112
#define I(x, y, z)
Definition: MD5.cpp:58
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:153
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallSetVector(It Start, It End)
Initialize a SmallSetVector with a range of elements.
Definition: SetVector.h:304
A vector that has set insertion semantics.
Definition: SetVector.h:40
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
Definition: SetVector.h:199
const_reverse_iterator rend() const
Get a const_reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:117
const_iterator begin() const
Get a const_iterator to the beginning of the SetVector.
Definition: SetVector.h:87
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242