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 
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 template <typename T, typename Vector = std::vector<T>,
39           typename Set = DenseSet<T>>
40 class SetVector {
41 public:
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 
266 private:
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.
296 template <typename T, unsigned N>
297 class SmallSetVector
298     : public SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> {
299 public:
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