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/Support/Compiler.h"
27#include <cassert>
28#include <iterator>
29#include <vector>
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 = std::vector<T>,
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;
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>
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.
87 Vector takeVector() {
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.
103 iterator begin() {
104 return vector_.begin();
105 }
106
107 /// Get a const_iterator to the beginning of the SetVector.
108 const_iterator begin() const {
109 return vector_.begin();
110 }
111
112 /// Get an iterator to the end of the SetVector.
113 iterator end() {
114 return vector_.end();
115 }
116
117 /// Get a const_iterator to the end of the SetVector.
118 const_iterator end() const {
119 return vector_.end();
120 }
121
122 /// Get an reverse_iterator to the end of the SetVector.
123 reverse_iterator rbegin() {
124 return vector_.rbegin();
125 }
126
127 /// Get a const_reverse_iterator to the end of the SetVector.
128 const_reverse_iterator rbegin() const {
129 return vector_.rbegin();
130 }
131
132 /// Get a reverse_iterator to the beginning of the SetVector.
133 reverse_iterator rend() {
134 return vector_.rend();
135 }
136
137 /// Get a const_reverse_iterator to the beginning of the SetVector.
138 const_reverse_iterator rend() const {
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.
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.
162 bool insert(const value_type &X) {
163 if constexpr (canBeSmall())
164 if (isSmall()) {
165 if (llvm::find(vector_, X) == vector_.end()) {
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.
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>
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(X: *SI);
322 }
323
324 void swap(SetVector<T, Vector, Set, N> &RHS) {
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>
387inline 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.
393template<typename T, unsigned N>
394inline void
395swap(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

source code of include/llvm-17/llvm/ADT/SetVector.h