Line data Source code
1 : //===- llvm/ADT/SetVector.h - Set with insert order iteration ---*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
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 allocations
16 : // 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 <algorithm>
28 : #include <cassert>
29 : #include <iterator>
30 : #include <vector>
31 :
32 : namespace llvm {
33 :
34 : /// A vector that has set insertion semantics.
35 : ///
36 : /// This adapter class provides a way to keep a set of things that also has the
37 : /// property of a deterministic iteration order. The order of iteration is the
38 : /// order of insertion.
39 : template <typename T, typename Vector = std::vector<T>,
40 : typename Set = DenseSet<T>>
41 142901 : class SetVector {
42 : public:
43 : using value_type = T;
44 : using key_type = T;
45 : using reference = T&;
46 : using const_reference = const T&;
47 : using set_type = Set;
48 : using vector_type = Vector;
49 : using iterator = typename vector_type::const_iterator;
50 : using const_iterator = typename vector_type::const_iterator;
51 : using reverse_iterator = typename vector_type::const_reverse_iterator;
52 : using const_reverse_iterator = typename vector_type::const_reverse_iterator;
53 : using size_type = typename vector_type::size_type;
54 :
55 : /// Construct an empty SetVector
56 1399 : SetVector() = default;
57 :
58 : /// Initialize a SetVector with a range of elements
59 : template<typename It>
60 20179 : SetVector(It Start, It End) {
61 20179 : insert(Start, End);
62 20179 : }
63 3 :
64 3 : ArrayRef<T> getArrayRef() const { return vector_; }
65 3 :
66 2 : /// Clear the SetVector and return the underlying vector.
67 2 : Vector takeVector() {
68 2 : set_.clear();
69 : return std::move(vector_);
70 : }
71 :
72 : /// Determine if the SetVector is empty or not.
73 : bool empty() const {
74 25644344 : return vector_.empty();
75 : }
76 :
77 : /// Determine the number of elements in the SetVector.
78 : size_type size() const {
79 5227372 : return vector_.size();
80 : }
81 :
82 : /// Get an iterator to the beginning of the SetVector.
83 : iterator begin() {
84 : return vector_.begin();
85 23 : }
86 :
87 : /// Get a const_iterator to the beginning of the SetVector.
88 : const_iterator begin() const {
89 121726 : return vector_.begin();
90 : }
91 :
92 : /// Get an iterator to the end of the SetVector.
93 : iterator end() {
94 : return vector_.end();
95 : }
96 :
97 : /// Get a const_iterator to the end of the SetVector.
98 : const_iterator end() const {
99 123209 : return vector_.end();
100 : }
101 :
102 : /// Get an reverse_iterator to the end of the SetVector.
103 : reverse_iterator rbegin() {
104 : return vector_.rbegin();
105 : }
106 :
107 : /// Get a const_reverse_iterator to the end of the SetVector.
108 : const_reverse_iterator rbegin() const {
109 : return vector_.rbegin();
110 : }
111 :
112 : /// Get a reverse_iterator to the beginning of the SetVector.
113 : reverse_iterator rend() {
114 92222 : return vector_.rend();
115 : }
116 :
117 : /// Get a const_reverse_iterator to the beginning of the SetVector.
118 : const_reverse_iterator rend() const {
119 : return vector_.rend();
120 : }
121 :
122 : /// Return the first element of the SetVector.
123 : const T &front() const {
124 : assert(!empty() && "Cannot call front() on empty SetVector!");
125 : return vector_.front();
126 : }
127 :
128 : /// Return the last element of the SetVector.
129 : const T &back() const {
130 : assert(!empty() && "Cannot call back() on empty SetVector!");
131 : return vector_.back();
132 : }
133 :
134 : /// Index into the SetVector.
135 : const_reference operator[](size_type n) const {
136 : assert(n < vector_.size() && "SetVector access out of range!");
137 6786 : return vector_[n];
138 : }
139 :
140 : /// Insert a new element into the SetVector.
141 : /// \returns true if the element was inserted into the SetVector.
142 38227770 : bool insert(const value_type &X) {
143 2974674 : bool result = set_.insert(X).second;
144 38227769 : if (result)
145 32931632 : vector_.push_back(X);
146 38227769 : return result;
147 : }
148 5615548 :
149 1901650 : /// Insert a range of elements into the SetVector.
150 5615548 : template<typename It>
151 5032541 : void insert(It Start, It End) {
152 6706381 : for (; Start != End; ++Start)
153 725192 : if (set_.insert(*Start).second)
154 20409099 : vector_.push_back(*Start);
155 1174477 : }
156 19482277 :
157 15947881 : /// Remove an item from the set vector.
158 29596835 : bool remove(const value_type& X) {
159 10132376 : if (set_.erase(X)) {
160 66561 : typename vector_type::iterator I = find(vector_, X);
161 3916 : assert(I != vector_.end() && "Corrupted SetVector instances!");
162 2825820 : vector_.erase(I);
163 2826515 : return true;
164 221767 : }
165 33937 : return false;
166 39913 : }
167 19733 :
168 24328 : /// Erase a single element from the set vector.
169 38163 : /// \returns an iterator pointing to the next element that followed the
170 25759 : /// element erased. This is the end of the SetVector if the last element is
171 17894 : /// erased.
172 182071 : iterator erase(iterator I) {
173 9018 : const key_type &V = *I;
174 192028 : assert(set_.count(V) && "Corrupted SetVector instances!");
175 345526 : set_.erase(V);
176 377490 :
177 40605 : // FIXME: No need to use the non-const iterator when built with
178 489559 : // std:vector.erase(const_iterator) as defined in C++11. This is for
179 165958 : // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
180 462763 : auto NI = vector_.begin();
181 459829 : std::advance(NI, std::distance<iterator>(NI, I));
182 465845 :
183 7308 : return vector_.erase(NI);
184 1845 : }
185 1845 :
186 1146 : /// Remove items from the set vector based on a predicate function.
187 0 : ///
188 : /// This is intended to be equivalent to the following code, if we could
189 : /// write it:
190 0 : ///
191 0 : /// \code
192 0 : /// V.erase(remove_if(V, P), V.end());
193 : /// \endcode
194 : ///
195 : /// However, SetVector doesn't expose non-const iterators, making any
196 : /// algorithm like remove_if impossible to use.
197 : ///
198 : /// \returns true if any element is removed.
199 : template <typename UnaryPredicate>
200 79715 : bool remove_if(UnaryPredicate P) {
201 5388 : typename vector_type::iterator I =
202 77615 : llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
203 74327 : if (I == vector_.end())
204 1146 : return false;
205 28881 : vector_.erase(I, vector_.end());
206 28889 : return true;
207 : }
208 46477 :
209 : /// Count the number of elements of a given key in the SetVector.
210 46477 : /// \returns 0 if the element is not in the SetVector, 1 if it is.
211 46477 : size_type count(const key_type &key) const {
212 4557 : return set_.count(key);
213 28867 : }
214 28927 :
215 60 : /// Completely clear the SetVector
216 2335 : void clear() {
217 0 : set_.clear();
218 2395 : vector_.clear();
219 2335 : }
220 60 :
221 5 : /// Remove the last element of the SetVector.
222 11973 : void pop_back() {
223 60 : assert(!empty() && "Cannot remove an element from an empty SetVector!");
224 9411 : set_.erase(back());
225 3248 : vector_.pop_back();
226 11217 : }
227 0 :
228 116 : LLVM_NODISCARD T pop_back_val() {
229 146612 : T Ret = back();
230 2497 : pop_back();
231 0 : return Ret;
232 0 : }
233 0 :
234 0 : bool operator==(const SetVector &that) const {
235 0 : return vector_ == that.vector_;
236 26134 : }
237 0 :
238 26134 : bool operator!=(const SetVector &that) const {
239 26134 : return vector_ != that.vector_;
240 146 : }
241 12725646 :
242 2 : /// Compute This := This u S, return whether 'This' changed.
243 146 : /// TODO: We should be able to use set_union from SetOperations.h, but
244 0 : /// SetVector interface is inconsistent with DenseSet.
245 0 : template <class STy>
246 : bool set_union(const STy &S) {
247 1684 : bool Changed = false;
248 :
249 : for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
250 : ++SI)
251 : if (insert(*SI))
252 : Changed = true;
253 0 :
254 0 : return Changed;
255 : }
256 :
257 79 : /// Compute This := This - B
258 : /// TODO: We should be able to use set_subtract from SetOperations.h, but
259 0 : /// SetVector interface is inconsistent with DenseSet.
260 : template <class STy>
261 0 : void set_subtract(const STy &S) {
262 1516 : for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
263 : ++SI)
264 : remove(*SI);
265 624134 : }
266 :
267 : private:
268 : /// A wrapper predicate designed for use with std::remove_if.
269 : ///
270 : /// This predicate wraps a predicate suitable for use with std::remove_if to
271 : /// call set_.erase(x) on each element which is slated for removal.
272 0 : template <typename UnaryPredicate>
273 23016 : class TestAndEraseFromSet {
274 0 : UnaryPredicate P;
275 : set_type &set_;
276 :
277 : public:
278 3353 : TestAndEraseFromSet(UnaryPredicate P, set_type &set_)
279 3353 : : P(std::move(P)), set_(set_) {}
280 :
281 : template <typename ArgumentT>
282 12947 : bool operator()(const ArgumentT &Arg) {
283 12947 : if (P(Arg)) {
284 25 : set_.erase(Arg);
285 25 : return true;
286 : }
287 : return false;
288 : }
289 : };
290 :
291 : set_type set_; ///< The set.
292 : vector_type vector_; ///< The vector.
293 : };
294 48812 :
295 48812 : /// A SetVector that performs no allocations if smaller than
296 : /// a certain size.
297 : template <typename T, unsigned N>
298 16729919 : class SmallSetVector
299 1139524 : : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
300 988636 : public:
301 988636 : SmallSetVector() = default;
302 :
303 : /// Initialize a SmallSetVector with a range of elements
304 : template<typename It>
305 1341503 : SmallSetVector(It Start, It End) {
306 1342314 : this->insert(Start, End);
307 1226242 : }
308 1018272 : };
309 :
310 46257115 : } // end namespace llvm
311 3060 :
312 35224 : #endif // LLVM_ADT_SETVECTOR_H
|
