Branch data Line data Source code
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 [ # # ]: 0 : 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 [ # # ]: 0 : 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 : 0 : 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 [ # # ]: 0 : bool result = set_.insert(X).second;
175 [ # # ]: 0 : if (result)
176 : 0 : vector_.push_back(X);
177 : 0 : 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(*SI);
322 : : }
323 : :
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:
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.
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>
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>
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
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
|
