LLVM 19.0.0git
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/// \file
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
16/// allocations 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"
28#include <cassert>
29#include <iterator>
30
31namespace 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///
39/// The key and value types are derived from the Set and Vector types
40/// respectively. This allows the vector-type operations and set-type operations
41/// to have different types. In particular, this is useful when storing pointers
42/// as "Foo *" values but looking them up as "const Foo *" keys.
43///
44/// No constraint is placed on the key and value types, although it is assumed
45/// that value_type can be converted into key_type for insertion. Users must be
46/// aware of any loss of information in this conversion. For example, setting
47/// value_type to float and key_type to int can produce very surprising results,
48/// but it is not explicitly disallowed.
49///
50/// The parameter N specifies the "small" size of the container, which is the
51/// number of elements upto which a linear scan over the Vector will be used
52/// when searching for elements instead of checking Set, due to it being better
53/// for performance. A value of 0 means that this mode of operation is not used,
54/// and is the default value.
55template <typename T, typename Vector = SmallVector<T, 0>,
56 typename Set = DenseSet<T>, unsigned N = 0>
57class SetVector {
58 // Much like in SmallPtrSet, this value should not be too high to prevent
59 // excessively long linear scans from occuring.
60 static_assert(N <= 32, "Small size should be less than or equal to 32!");
61
62public:
63 using value_type = typename Vector::value_type;
64 using key_type = typename Set::key_type;
66 using const_reference = const value_type &;
67 using set_type = Set;
69 using iterator = typename vector_type::const_iterator;
70 using const_iterator = typename vector_type::const_iterator;
71 using reverse_iterator = typename vector_type::const_reverse_iterator;
72 using const_reverse_iterator = typename vector_type::const_reverse_iterator;
73 using size_type = typename vector_type::size_type;
74
75 /// Construct an empty SetVector
76 SetVector() = default;
77
78 /// Initialize a SetVector with a range of elements
79 template<typename It>
80 SetVector(It Start, It End) {
81 insert(Start, End);
82 }
83
84 ArrayRef<value_type> getArrayRef() const { return vector_; }
85
86 /// Clear the SetVector and return the underlying vector.
88 set_.clear();
89 return std::move(vector_);
90 }
91
92 /// Determine if the SetVector is empty or not.
93 bool empty() const {
94 return vector_.empty();
95 }
96
97 /// Determine the number of elements in the SetVector.
98 size_type size() const {
99 return vector_.size();
100 }
101
102 /// Get an iterator to the beginning of the SetVector.
104 return vector_.begin();
105 }
106
107 /// Get a const_iterator to the beginning of the SetVector.
109 return vector_.begin();
110 }
111
112 /// Get an iterator to the end of the SetVector.
114 return vector_.end();
115 }
116
117 /// Get a const_iterator to the end of the SetVector.
119 return vector_.end();
120 }
121
122 /// Get an reverse_iterator to the end of the SetVector.
124 return vector_.rbegin();
125 }
126
127 /// Get a const_reverse_iterator to the end of the SetVector.
129 return vector_.rbegin();
130 }
131
132 /// Get a reverse_iterator to the beginning of the SetVector.
134 return vector_.rend();
135 }
136
137 /// Get a const_reverse_iterator to the beginning of the SetVector.
139 return vector_.rend();
140 }
141
142 /// Return the first element of the SetVector.
143 const value_type &front() const {
144 assert(!empty() && "Cannot call front() on empty SetVector!");
145 return vector_.front();
146 }
147
148 /// Return the last element of the SetVector.
149 const value_type &back() const {
150 assert(!empty() && "Cannot call back() on empty SetVector!");
151 return vector_.back();
152 }
153
154 /// Index into the SetVector.
156 assert(n < vector_.size() && "SetVector access out of range!");
157 return vector_[n];
158 }
159
160 /// Insert a new element into the SetVector.
161 /// \returns true if the element was inserted into the SetVector.
162 bool insert(const value_type &X) {
163 if constexpr (canBeSmall())
164 if (isSmall()) {
165 if (!llvm::is_contained(vector_, X)) {
166 vector_.push_back(X);
167 if (vector_.size() > N)
168 makeBig();
169 return true;
170 }
171 return false;
172 }
173
174 bool result = set_.insert(X).second;
175 if (result)
176 vector_.push_back(X);
177 return result;
178 }
179
180 /// Insert a range of elements into the SetVector.
181 template<typename It>
182 void insert(It Start, It End) {
183 for (; Start != End; ++Start)
184 insert(*Start);
185 }
186
187 /// Remove an item from the set vector.
188 bool remove(const value_type& X) {
189 if constexpr (canBeSmall())
190 if (isSmall()) {
191 typename vector_type::iterator I = find(vector_, X);
192 if (I != vector_.end()) {
193 vector_.erase(I);
194 return true;
195 }
196 return false;
197 }
198
199 if (set_.erase(X)) {
200 typename vector_type::iterator I = find(vector_, X);
201 assert(I != vector_.end() && "Corrupted SetVector instances!");
202 vector_.erase(I);
203 return true;
204 }
205 return false;
206 }
207
208 /// Erase a single element from the set vector.
209 /// \returns an iterator pointing to the next element that followed the
210 /// element erased. This is the end of the SetVector if the last element is
211 /// erased.
213 if constexpr (canBeSmall())
214 if (isSmall())
215 return vector_.erase(I);
216
217 const key_type &V = *I;
218 assert(set_.count(V) && "Corrupted SetVector instances!");
219 set_.erase(V);
220 return vector_.erase(I);
221 }
222
223 /// Remove items from the set vector based on a predicate function.
224 ///
225 /// This is intended to be equivalent to the following code, if we could
226 /// write it:
227 ///
228 /// \code
229 /// V.erase(remove_if(V, P), V.end());
230 /// \endcode
231 ///
232 /// However, SetVector doesn't expose non-const iterators, making any
233 /// algorithm like remove_if impossible to use.
234 ///
235 /// \returns true if any element is removed.
236 template <typename UnaryPredicate>
237 bool remove_if(UnaryPredicate P) {
238 typename vector_type::iterator I = [this, P] {
239 if constexpr (canBeSmall())
240 if (isSmall())
241 return llvm::remove_if(vector_, P);
242
243 return llvm::remove_if(vector_,
244 TestAndEraseFromSet<UnaryPredicate>(P, set_));
245 }();
246
247 if (I == vector_.end())
248 return false;
249 vector_.erase(I, vector_.end());
250 return true;
251 }
252
253 /// Check if the SetVector contains the given key.
254 bool contains(const key_type &key) const {
255 if constexpr (canBeSmall())
256 if (isSmall())
257 return is_contained(vector_, key);
258
259 return set_.find(key) != set_.end();
260 }
261
262 /// Count the number of elements of a given key in the SetVector.
263 /// \returns 0 if the element is not in the SetVector, 1 if it is.
264 size_type count(const key_type &key) const {
265 if constexpr (canBeSmall())
266 if (isSmall())
267 return is_contained(vector_, key);
268
269 return set_.count(key);
270 }
271
272 /// Completely clear the SetVector
273 void clear() {
274 set_.clear();
275 vector_.clear();
276 }
277
278 /// Remove the last element of the SetVector.
279 void pop_back() {
280 assert(!empty() && "Cannot remove an element from an empty SetVector!");
281 set_.erase(back());
282 vector_.pop_back();
283 }
284
285 [[nodiscard]] value_type pop_back_val() {
286 value_type Ret = back();
287 pop_back();
288 return Ret;
289 }
290
291 bool operator==(const SetVector &that) const {
292 return vector_ == that.vector_;
293 }
294
295 bool operator!=(const SetVector &that) const {
296 return vector_ != that.vector_;
297 }
298
299 /// Compute This := This u S, return whether 'This' changed.
300 /// TODO: We should be able to use set_union from SetOperations.h, but
301 /// SetVector interface is inconsistent with DenseSet.
302 template <class STy>
303 bool set_union(const STy &S) {
304 bool Changed = false;
305
306 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
307 ++SI)
308 if (insert(*SI))
309 Changed = true;
310
311 return Changed;
312 }
313
314 /// Compute This := This - B
315 /// TODO: We should be able to use set_subtract from SetOperations.h, but
316 /// SetVector interface is inconsistent with DenseSet.
317 template <class STy>
318 void set_subtract(const STy &S) {
319 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
320 ++SI)
321 remove(*SI);
322 }
323
325 set_.swap(RHS.set_);
326 vector_.swap(RHS.vector_);
327 }
328
329private:
330 /// A wrapper predicate designed for use with std::remove_if.
331 ///
332 /// This predicate wraps a predicate suitable for use with std::remove_if to
333 /// call set_.erase(x) on each element which is slated for removal.
334 template <typename UnaryPredicate>
335 class TestAndEraseFromSet {
336 UnaryPredicate P;
337 set_type &set_;
338
339 public:
340 TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
341 : P(std::move(P)), set_(set_) {}
342
343 template <typename ArgumentT>
344 bool operator()(const ArgumentT &Arg) {
345 if (P(Arg)) {
346 set_.erase(Arg);
347 return true;
348 }
349 return false;
350 }
351 };
352
353 [[nodiscard]] static constexpr bool canBeSmall() { return N != 0; }
354
355 [[nodiscard]] bool isSmall() const { return set_.empty(); }
356
357 void makeBig() {
358 if constexpr (canBeSmall())
359 for (const auto &entry : vector_)
360 set_.insert(entry);
361 }
362
363 set_type set_; ///< The set.
364 vector_type vector_; ///< The vector.
365};
366
367/// A SetVector that performs no allocations if smaller than
368/// a certain size.
369template <typename T, unsigned N>
370class SmallSetVector : public SetVector<T, SmallVector<T, N>, DenseSet<T>, N> {
371public:
372 SmallSetVector() = default;
373
374 /// Initialize a SmallSetVector with a range of elements
375 template<typename It>
376 SmallSetVector(It Start, It End) {
377 this->insert(Start, End);
378 }
379};
380
381} // end namespace llvm
382
383namespace std {
384
385/// Implement std::swap in terms of SetVector swap.
386template <typename T, typename V, typename S, unsigned N>
389 LHS.swap(RHS);
390}
391
392/// Implement std::swap in terms of SmallSetVector swap.
393template<typename T, unsigned N>
394inline void
396 LHS.swap(RHS);
397}
398
399} // end namespace std
400
401#endif // LLVM_ADT_SETVECTOR_H
This file defines the DenseSet and SmallDenseSet classes.
bool End
Definition: ELF_riscv.cpp:480
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
Value * RHS
Value * LHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A vector that has set insertion semantics.
Definition: SetVector.h:57
const_reverse_iterator rend() const
Get a const_reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:138
ArrayRef< value_type > getArrayRef() const
Definition: SetVector.h:84
typename vector_type::const_reverse_iterator reverse_iterator
Definition: SetVector.h:71
iterator erase(const_iterator I)
Erase a single element from the set vector.
Definition: SetVector.h:212
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:188
bool remove_if(UnaryPredicate P)
Remove items from the set vector based on a predicate function.
Definition: SetVector.h:237
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
const value_type & front() const
Return the first element of the SetVector.
Definition: SetVector.h:143
bool operator==(const SetVector &that) const
Definition: SetVector.h:291
value_type & reference
Definition: SetVector.h:65
typename vector_type::const_reverse_iterator const_reverse_iterator
Definition: SetVector.h:72
Vector vector_type
Definition: SetVector.h:68
const value_type & back() const
Return the last element of the SetVector.
Definition: SetVector.h:149
bool set_union(const STy &S)
Compute This := This u S, return whether 'This' changed.
Definition: SetVector.h:303
typename Vector::value_type value_type
Definition: SetVector.h:63
const_reverse_iterator rbegin() const
Get a const_reverse_iterator to the end of the SetVector.
Definition: SetVector.h:128
Vector takeVector()
Clear the SetVector and return the underlying vector.
Definition: SetVector.h:87
typename vector_type::const_iterator iterator
Definition: SetVector.h:69
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:113
SetVector()=default
Construct an empty SetVector.
reverse_iterator rbegin()
Get an reverse_iterator to the end of the SetVector.
Definition: SetVector.h:123
typename vector_type::const_iterator const_iterator
Definition: SetVector.h:70
const_iterator end() const
Get a const_iterator to the end of the SetVector.
Definition: SetVector.h:118
void clear()
Completely clear the SetVector.
Definition: SetVector.h:273
bool operator!=(const SetVector &that) const
Definition: SetVector.h:295
reverse_iterator rend()
Get a reverse_iterator to the beginning of the SetVector.
Definition: SetVector.h:133
typename vector_type::size_type size_type
Definition: SetVector.h:73
const_iterator begin() const
Get a const_iterator to the beginning 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:264
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
void insert(It Start, It End)
Insert a range of elements into the SetVector.
Definition: SetVector.h:182
const value_type & const_reference
Definition: SetVector.h:66
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:103
SetVector(It Start, It End)
Initialize a SetVector with a range of elements.
Definition: SetVector.h:80
void swap(SetVector< T, Vector, Set, N > &RHS)
Definition: SetVector.h:324
typename Set::key_type key_type
Definition: SetVector.h:64
void set_subtract(const STy &S)
Compute This := This - B TODO: We should be able to use set_subtract from SetOperations....
Definition: SetVector.h:318
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:279
value_type pop_back_val()
Definition: SetVector.h:285
const_reference operator[](size_type n) const
Index into the SetVector.
Definition: SetVector.h:155
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:254
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
SmallSetVector(It Start, It End)
Initialize a SmallSetVector with a range of elements.
Definition: SetVector.h:376
SmallSetVector()=default
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1751
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1770
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1858
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N