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