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