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 /// Count the number of elements of a given key in the SetVector.
209 /// \returns 0 if the element is not in the SetVector, 1 if it is.
210 size_type count(const key_type &key) const {
211 return set_.count(key);
212 }
213
214 /// Completely clear the SetVector
215 void clear() {
216 set_.clear();
217 vector_.clear();
218 }
219
220 /// Remove the last element of the SetVector.
221 void pop_back() {
222 assert(!empty() && "Cannot remove an element from an empty SetVector!");
223 set_.erase(back());
224 vector_.pop_back();
225 }
226
227 LLVM_NODISCARD T pop_back_val() {
228 T Ret = back();
229 pop_back();
230 return Ret;
231 }
232
233 bool operator==(const SetVector &that) const {
234 return vector_ == that.vector_;
235 }
236
237 bool operator!=(const SetVector &that) const {
238 return vector_ != that.vector_;
239 }
240
241 /// Compute This := This u S, return whether 'This' changed.
242 /// TODO: We should be able to use set_union from SetOperations.h, but
243 /// SetVector interface is inconsistent with DenseSet.
244 template <class STy>
245 bool set_union(const STy &S) {
246 bool Changed = false;
247
248 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
249 ++SI)
250 if (insert(*SI))
251 Changed = true;
252
253 return Changed;
254 }
255
256 /// Compute This := This - B
257 /// TODO: We should be able to use set_subtract from SetOperations.h, but
258 /// SetVector interface is inconsistent with DenseSet.
259 template <class STy>
260 void set_subtract(const STy &S) {
261 for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
262 ++SI)
263 remove(*SI);
264 }
265
266private:
267 /// A wrapper predicate designed for use with std::remove_if.
268 ///
269 /// This predicate wraps a predicate suitable for use with std::remove_if to
270 /// call set_.erase(x) on each element which is slated for removal.
271 template <typename UnaryPredicate>
272 class TestAndEraseFromSet {
273 UnaryPredicate P;
274 set_type &set_;
275
276 public:
277 TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
278 : P(std::move(P)), set_(set_) {}
279
280 template <typename ArgumentT>
281 bool operator()(const ArgumentT &Arg) {
282 if (P(Arg)) {
283 set_.erase(Arg);
284 return true;
285 }
286 return false;
287 }
288 };
289
290 set_type set_; ///< The set.
291 vector_type vector_; ///< The vector.
292};
293
294/// A SetVector that performs no allocations if smaller than
295/// a certain size.
296template <typename T, unsigned N>
297class SmallSetVector
298 : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
299public:
300 SmallSetVector() = default;
301
302 /// Initialize a SmallSetVector with a range of elements
303 template<typename It>
304 SmallSetVector(It Start, It End) {
305 this->insert(Start, End);
306 }
307};
308
309} // end namespace llvm
310
311#endif // LLVM_ADT_SETVECTOR_H
312