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// This file implements a set that has insertion order iteration
10// characteristics. This is useful for keeping a set of things that need to be
11// visited later but in a deterministic order (insertion order). The interface
12// is purposefully minimal.
13//
14// This file defines SetVector and SmallSetVector, which performs no allocations
15// if the SetVector has less than a certain number of elements.
16//
17//===----------------------------------------------------------------------===//
18
19#ifndef LLVM_ADT_SETVECTOR_H
20#define LLVM_ADT_SETVECTOR_H
21
22#include "llvm/ADT/ArrayRef.h"
23#include "llvm/ADT/DenseSet.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/Support/Compiler.h"
26#include <algorithm>
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.
38template <typename T, typename Vector = std::vector<T>,
39 typename Set = DenseSet<T>>
40class SetVector {
41public:
42 using value_type = T;
43 using key_type = T;
44 using reference = T&;
45 using const_reference = const T&;
46 using set_type = Set;
47 using vector_type = Vector;
48 using iterator = typename vector_type::const_iterator;
49 using const_iterator = typename vector_type::const_iterator;
50 using reverse_iterator = typename vector_type::const_reverse_iterator;
51 using const_reverse_iterator = typename vector_type::const_reverse_iterator;
52 using size_type = typename vector_type::size_type;
53
54 /// Construct an empty SetVector
55 SetVector() = default;
56
57 /// Initialize a SetVector with a range of elements
58 template<typename It>
59 SetVector(It Start, It End) {
60 insert(Start, End);
61 }
62
63 ArrayRef<T> getArrayRef() const { return vector_; }
64
65 /// Clear the SetVector and return the underlying vector.
66 Vector takeVector() {
67 set_.clear();
68 return std::move(vector_);
69 }
70
71 /// Determine if the SetVector is empty or not.
72 bool empty() const {
73 return vector_.empty();
74 }
75
76 /// Determine the number of elements in the SetVector.
77 size_type size() const {
78 return vector_.size();
79 }
80
81 /// Get an iterator to the beginning of the SetVector.
82 iterator begin() {
83 return vector_.begin();
84 }
85
86 /// Get a const_iterator to the beginning of the SetVector.
87 const_iterator begin() const {
88 return vector_.begin();
89 }
90
91 /// Get an iterator to the end of the SetVector.
92 iterator end() {
93 return vector_.end();
94 }
95
96 /// Get a const_iterator to the end of the SetVector.
97 const_iterator end() const {
98 return vector_.end();
99 }
100
101 /// Get an reverse_iterator to the end of the SetVector.
102 reverse_iterator rbegin() {
103 return vector_.rbegin();
104 }
105
106 /// Get a const_reverse_iterator to the end of the SetVector.
107 const_reverse_iterator rbegin() const {
108 return vector_.rbegin();
109 }
110
111 /// Get a reverse_iterator to the beginning of the SetVector.
112 reverse_iterator rend() {
113 return vector_.rend();
114 }
115
116 /// Get a const_reverse_iterator to the beginning of the SetVector.
117 const_reverse_iterator rend() const {
118 return vector_.rend();
119 }
120
121 /// Return the first element of the SetVector.
122 const T &front() const {
123 assert(!empty() && "Cannot call front() on empty SetVector!");
124 return vector_.front();
125 }
126
127 /// Return the last element of the SetVector.
128 const T &back() const {
129 assert(!empty() && "Cannot call back() on empty SetVector!");
130 return vector_.back();
131 }
132
133 /// Index into the SetVector.
134 const_reference operator[](size_type n) const {
135 assert(n < vector_.size() && "SetVector access out of range!");
136 return vector_[n];
137 }
138
139 /// Insert a new element into the SetVector.
140 /// \returns true if the element was inserted into the SetVector.
141 bool insert(const value_type &X) {
142 bool result = set_.insert(X).second;
143 if (result)
144 vector_.push_back(X);
145 return result;
146 }
147
148 /// Insert a range of elements into the SetVector.
149 template<typename It>
150 void insert(It Start, It End) {
151 for (; Start != End; ++Start)
152 if (set_.insert(*Start).second)
153 vector_.push_back(*Start);
154 }
155
156 /// Remove an item from the set vector.
157 bool remove(const value_type& X) {
158 if (set_.erase(X)) {
159 typename vector_type::iterator I = find(vector_, X);
160 assert(I != vector_.end() && "Corrupted SetVector instances!");
161 vector_.erase(I);
162 return true;
163 }
164 return false;
165 }
166
167 /// Erase a single element from the set vector.
168 /// \returns an iterator pointing to the next element that followed the
169 /// element erased. This is the end of the SetVector if the last element is
170 /// erased.
171 iterator erase(iterator I) {
172 const key_type &V = *I;
173 assert(set_.count(V) && "Corrupted SetVector instances!");
174 set_.erase(V);
175
176 // FIXME: No need to use the non-const iterator when built with
177 // std::vector.erase(const_iterator) as defined in C++11. This is for
178 // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
179 auto NI = vector_.begin();
180 std::advance(NI, std::distance<iterator>(NI, I));
181
182 return vector_.erase(NI);
183 }
184
185 /// Remove items from the set vector based on a predicate function.
186 ///
187 /// This is intended to be equivalent to the following code, if we could
188 /// write it:
189 ///
190 /// \code
191 /// V.erase(remove_if(V, P), V.end());
192 /// \endcode
193 ///
194 /// However, SetVector doesn't expose non-const iterators, making any
195 /// algorithm like remove_if impossible to use.
196 ///
197 /// \returns true if any element is removed.
198 template <typename UnaryPredicate>
199 bool remove_if(UnaryPredicate P) {
200 typename vector_type::iterator I =
201 llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
202 if (I == vector_.end())
203 return false;
204 vector_.erase(I, vector_.end());
205 return true;
206 }
207
208 /// Check if the SetVector contains the given key.
209 bool contains(const key_type &key) const {
210 return set_.find(key) != set_.end();
211 }
212
213 /// Count the number of elements of a given key in the SetVector.
214 /// \returns 0 if the element is not in the SetVector, 1 if it is.
215 size_type count(const key_type &key) const {
216 return set_.count(key);
217 }
218
219 /// Completely clear the SetVector
220 void clear() {
221 set_.clear();
222 vector_.clear();
223 }
224
225 /// Remove the last element of the SetVector.
226 void pop_back() {
227 assert(!empty() && "Cannot remove an element from an empty SetVector!");
228 set_.erase(back());
229 vector_.pop_back();
230 }
231
232 LLVM_NODISCARD T pop_back_val() {
233 T Ret = back();
234 pop_back();
235 return Ret;
236 }
237
238 bool operator==(const SetVector &that) const {
239 return vector_ == that.vector_;
240 }
241
242 bool operator!=(const SetVector &that) const {
243 return vector_ != that.vector_;
244 }
245
246 /// Compute This := This u S, return whether 'This' changed.
247 /// TODO: We should be able to use set_union from SetOperations.h, but
248 /// SetVector interface is inconsistent with DenseSet.
249 template <class STy>
250 bool set_union(const STy &S) {
251 bool Changed = false;
252
253 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
254 ++SI)
255 if (insert(*SI))
256 Changed = true;
257
258 return Changed;
259 }
260
261 /// Compute This := This - B
262 /// TODO: We should be able to use set_subtract from SetOperations.h, but
263 /// SetVector interface is inconsistent with DenseSet.
264 template <class STy>
265 void set_subtract(const STy &S) {
266 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
267 ++SI)
268 remove(*SI);
269 }
270
271 void swap(SetVector<T, Vector, Set> &RHS) {
272 set_.swap(RHS.set_);
273 vector_.swap(RHS.vector_);
274 }
275
276private:
277 /// A wrapper predicate designed for use with std::remove_if.
278 ///
279 /// This predicate wraps a predicate suitable for use with std::remove_if to
280 /// call set_.erase(x) on each element which is slated for removal.
281 template <typename UnaryPredicate>
282 class TestAndEraseFromSet {
283 UnaryPredicate P;
284 set_type &set_;
285
286 public:
287 TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
288 : P(std::move(P)), set_(set_) {}
289
290 template <typename ArgumentT>
291 bool operator()(const ArgumentT &Arg) {
292 if (P(Arg)) {
293 set_.erase(Arg);
294 return true;
295 }
296 return false;
297 }
298 };
299
300 set_type set_; ///< The set.
301 vector_type vector_; ///< The vector.
302};
303
304/// A SetVector that performs no allocations if smaller than
305/// a certain size.
306template <typename T, unsigned N>
307class SmallSetVector
308 : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
309public:
310 SmallSetVector() = default;
311
312 /// Initialize a SmallSetVector with a range of elements
313 template<typename It>
314 SmallSetVector(It Start, It End) {
315 this->insert(Start, End);
316 }
317};
318
319} // end namespace llvm
320
321namespace std {
322
323/// Implement std::swap in terms of SetVector swap.
324template<typename T, typename V, typename S>
325inline void
326swap(llvm::SetVector<T, V, S> &LHS, llvm::SetVector<T, V, S> &RHS) {
327 LHS.swap(RHS);
328}
329
330/// Implement std::swap in terms of SmallSetVector swap.
331template<typename T, unsigned N>
332inline void
333swap(llvm::SmallSetVector<T, N> &LHS, llvm::SmallSetVector<T, N> &RHS) {
334 LHS.swap(RHS);
335}
336
337} // end namespace std
338
339#endif // LLVM_ADT_SETVECTOR_H
340