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 1005 : 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 1005 : 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 2192 : 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 2192 : bool result = set_.insert(X).second;
175 2192 : if (result)
176 2192 : vector_.push_back(X);
177 2192 : 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
|
