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"
26 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/Support/Compiler.h"
28 #include <cassert>
29 #include <iterator>
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 ///
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.
55 template <typename T, typename Vector = SmallVector<T, 0>,
56 typename Set = DenseSet<T>, unsigned N = 0>
57 class 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
62 public:
63 using value_type = typename Vector::value_type;
64 using key_type = typename Set::key_type;
65 using reference = value_type &;
66 using const_reference = const value_type &;
67 using set_type = Set;
68 using vector_type = Vector;
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>
SetVector(It Start,It End)80 SetVector(It Start, It End) {
81 insert(Start, End);
82 }
83
getArrayRef()84 ArrayRef<value_type> getArrayRef() const { return vector_; }
85
86 /// Clear the SetVector and return the underlying vector.
takeVector()87 Vector takeVector() {
88 set_.clear();
89 return std::move(vector_);
90 }
91
92 /// Determine if the SetVector is empty or not.
empty()93 bool empty() const {
94 return vector_.empty();
95 }
96
97 /// Determine the number of elements in the SetVector.
size()98 size_type size() const {
99 return vector_.size();
100 }
101
102 /// Get an iterator to the beginning of the SetVector.
begin()103 iterator begin() {
104 return vector_.begin();
105 }
106
107 /// Get a const_iterator to the beginning of the SetVector.
begin()108 const_iterator begin() const {
109 return vector_.begin();
110 }
111
112 /// Get an iterator to the end of the SetVector.
end()113 iterator end() {
114 return vector_.end();
115 }
116
117 /// Get a const_iterator to the end of the SetVector.
end()118 const_iterator end() const {
119 return vector_.end();
120 }
121
122 /// Get an reverse_iterator to the end of the SetVector.
rbegin()123 reverse_iterator rbegin() {
124 return vector_.rbegin();
125 }
126
127 /// Get a const_reverse_iterator to the end of the SetVector.
rbegin()128 const_reverse_iterator rbegin() const {
129 return vector_.rbegin();
130 }
131
132 /// Get a reverse_iterator to the beginning of the SetVector.
rend()133 reverse_iterator rend() {
134 return vector_.rend();
135 }
136
137 /// Get a const_reverse_iterator to the beginning of the SetVector.
rend()138 const_reverse_iterator rend() const {
139 return vector_.rend();
140 }
141
142 /// Return the first element of the SetVector.
front()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.
back()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.
155 const_reference operator[](size_type n) const {
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.
insert(const value_type & X)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>
insert(It Start,It End)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.
remove(const value_type & X)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.
erase(const_iterator I)212 iterator erase(const_iterator I) {
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>
remove_if(UnaryPredicate P)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.
contains(const key_type & 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.
count(const key_type & key)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
clear()273 void clear() {
274 set_.clear();
275 vector_.clear();
276 }
277
278 /// Remove the last element of the SetVector.
pop_back()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
pop_back_val()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>
set_union(const STy & S)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>
set_subtract(const STy & S)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
swap(SetVector<T,Vector,Set,N> & RHS)324 void swap(SetVector<T, Vector, Set, N> &RHS) {
325 set_.swap(RHS.set_);
326 vector_.swap(RHS.vector_);
327 }
328
329 private:
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:
TestAndEraseFromSet(UnaryPredicate P,set_type & set_)340 TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
341 : P(std::move(P)), set_(set_) {}
342
343 template <typename ArgumentT>
operator()344 bool operator()(const ArgumentT &Arg) {
345 if (P(Arg)) {
346 set_.erase(Arg);
347 return true;
348 }
349 return false;
350 }
351 };
352
canBeSmall()353 [[nodiscard]] static constexpr bool canBeSmall() { return N != 0; }
354
isSmall()355 [[nodiscard]] bool isSmall() const { return set_.empty(); }
356
makeBig()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.
369 template <typename T, unsigned N>
370 class SmallSetVector : public SetVector<T, SmallVector<T, N>, DenseSet<T>, N> {
371 public:
372 SmallSetVector() = default;
373
374 /// Initialize a SmallSetVector with a range of elements
375 template<typename It>
SmallSetVector(It Start,It End)376 SmallSetVector(It Start, It End) {
377 this->insert(Start, End);
378 }
379 };
380
381 } // end namespace llvm
382
383 namespace std {
384
385 /// Implement std::swap in terms of SetVector swap.
386 template <typename T, typename V, typename S, unsigned N>
swap(llvm::SetVector<T,V,S,N> & LHS,llvm::SetVector<T,V,S,N> & RHS)387 inline void swap(llvm::SetVector<T, V, S, N> &LHS,
388 llvm::SetVector<T, V, S, N> &RHS) {
389 LHS.swap(RHS);
390 }
391
392 /// Implement std::swap in terms of SmallSetVector swap.
393 template<typename T, unsigned N>
394 inline void
swap(llvm::SmallSetVector<T,N> & LHS,llvm::SmallSetVector<T,N> & RHS)395 swap(llvm::SmallSetVector<T, N> &LHS, llvm::SmallSetVector<T, N> &RHS) {
396 LHS.swap(RHS);
397 }
398
399 } // end namespace std
400
401 #endif // LLVM_ADT_SETVECTOR_H
402