1//===- llvm/ADT/SmallSet.h - 'Normally small' sets --------------*- 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 defines the SmallSet class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_SMALLSET_H
14#define LLVM_ADT_SMALLSET_H
15
16#include "llvm/ADT/None.h"
17#include "llvm/ADT/SmallPtrSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/iterator.h"
20#include "llvm/Support/Compiler.h"
21#include "llvm/Support/type_traits.h"
22#include <cstddef>
23#include <functional>
24#include <set>
25#include <type_traits>
26#include <utility>
27
28namespace llvm {
29
30/// SmallSetIterator - This class implements a const_iterator for SmallSet by
31/// delegating to the underlying SmallVector or Set iterators.
32template <typename T, unsigned N, typename C>
33class SmallSetIterator
34    : public iterator_facade_base<SmallSetIterator<T, N, C>,
35                                  std::forward_iterator_tag, T> {
36private:
37  using SetIterTy = typename std::set<T, C>::const_iterator;
38  using VecIterTy = typename SmallVector<T, N>::const_iterator;
39  using SelfTy = SmallSetIterator<T, N, C>;
40
41  /// Iterators to the parts of the SmallSet containing the data. They are set
42  /// depending on isSmall.
43  union {
44    SetIterTy SetIter;
45    VecIterTy VecIter;
46  };
47
48  bool isSmall;
49
50public:
51  SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {}
52
53  SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), isSmall(true) {}
54
55  // Spell out destructor, copy/move constructor and assignment operators for
56  // MSVC STL, where set<T>::const_iterator is not trivially copy constructible.
57  ~SmallSetIterator() {
58    if (isSmall)
59      VecIter.~VecIterTy();
60    else
61      SetIter.~SetIterTy();
62  }
63
64  SmallSetIterator(const SmallSetIterator &Other) : isSmall(Other.isSmall) {
65    if (isSmall)
66      VecIter = Other.VecIter;
67    else
68      // Use placement new, to make sure SetIter is properly constructed, even
69      // if it is not trivially copy-able (e.g. in MSVC).
70      new (&SetIter) SetIterTy(Other.SetIter);
71  }
72
73  SmallSetIterator(SmallSetIterator &&Other) : isSmall(Other.isSmall) {
74    if (isSmall)
75      VecIter = std::move(Other.VecIter);
76    else
77      // Use placement new, to make sure SetIter is properly constructed, even
78      // if it is not trivially copy-able (e.g. in MSVC).
79      new (&SetIter) SetIterTy(std::move(Other.SetIter));
80  }
81
82  SmallSetIterator& operator=(const SmallSetIterator& Other) {
83    // Call destructor for SetIter, so it gets properly destroyed if it is
84    // not trivially destructible in case we are setting VecIter.
85    if (!isSmall)
86      SetIter.~SetIterTy();
87
88    isSmall = Other.isSmall;
89    if (isSmall)
90      VecIter = Other.VecIter;
91    else
92      new (&SetIter) SetIterTy(Other.SetIter);
93    return *this;
94  }
95
96  SmallSetIterator& operator=(SmallSetIterator&& Other) {
97    // Call destructor for SetIter, so it gets properly destroyed if it is
98    // not trivially destructible in case we are setting VecIter.
99    if (!isSmall)
100      SetIter.~SetIterTy();
101
102    isSmall = Other.isSmall;
103    if (isSmall)
104      VecIter = std::move(Other.VecIter);
105    else
106      new (&SetIter) SetIterTy(std::move(Other.SetIter));
107    return *this;
108  }
109
110  bool operator==(const SmallSetIterator &RHS) const {
111    if (isSmall != RHS.isSmall)
112      return false;
113    if (isSmall)
114      return VecIter == RHS.VecIter;
115    return SetIter == RHS.SetIter;
116  }
117
118  SmallSetIterator &operator++() { // Preincrement
119    if (isSmall)
120      VecIter++;
121    else
122      SetIter++;
123    return *this;
124  }
125
126  const T &operator*() const { return isSmall ? *VecIter : *SetIter; }
127};
128
129/// SmallSet - This maintains a set of unique values, optimizing for the case
130/// when the set is small (less than N).  In this case, the set can be
131/// maintained with no mallocs.  If the set gets large, we expand to using an
132/// std::set to maintain reasonable lookup times.
133template <typename T, unsigned N, typename C = std::less<T>>
134class SmallSet {
135  /// Use a SmallVector to hold the elements here (even though it will never
136  /// reach its 'large' stage) to avoid calling the default ctors of elements
137  /// we will never use.
138  SmallVector<T, N> Vector;
139  std::set<T, C> Set;
140
141  using VIterator = typename SmallVector<T, N>::const_iterator;
142  using mutable_iterator = typename SmallVector<T, N>::iterator;
143
144  // In small mode SmallPtrSet uses linear search for the elements, so it is
145  // not a good idea to choose this value too high. You may consider using a
146  // DenseSet<> instead if you expect many elements in the set.
147  static_assert(N <= 32, "N should be small");
148
149public:
150  using size_type = size_t;
151  using const_iterator = SmallSetIterator<T, N, C>;
152
153  SmallSet() = default;
154
155  LLVM_NODISCARD bool empty() const {
156    return Vector.empty() && Set.empty();
157  }
158
159  size_type size() const {
160    return isSmall() ? Vector.size() : Set.size();
161  }
162
163  /// count - Return 1 if the element is in the set, 0 otherwise.
164  size_type count(const T &V) const {
165    if (isSmall()) {
166      // Since the collection is small, just do a linear search.
167      return vfind(V) == Vector.end() ? 0 : 1;
168    } else {
169      return Set.count(V);
170    }
171  }
172
173  /// insert - Insert an element into the set if it isn't already there.
174  /// Returns true if the element is inserted (it was not in the set before).
175  /// The first value of the returned pair is unused and provided for
176  /// partial compatibility with the standard library self-associative container
177  /// concept.
178  // FIXME: Add iterators that abstract over the small and large form, and then
179  // return those here.
180  std::pair<NoneType, bool> insert(const T &V) {
181    if (!isSmall())
182      return std::make_pair(None, Set.insert(V).second);
183
184    VIterator I = vfind(V);
185    if (I != Vector.end())    // Don't reinsert if it already exists.
186      return std::make_pair(None, false);
187    if (Vector.size() < N) {
188      Vector.push_back(V);
189      return std::make_pair(None, true);
190    }
191
192    // Otherwise, grow from vector to set.
193    while (!Vector.empty()) {
194      Set.insert(Vector.back());
195      Vector.pop_back();
196    }
197    Set.insert(V);
198    return std::make_pair(None, true);
199  }
200
201  template <typename IterT>
202  void insert(IterT I, IterT E) {
203    for (; I != E; ++I)
204      insert(*I);
205  }
206
207  bool erase(const T &V) {
208    if (!isSmall())
209      return Set.erase(V);
210    for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
211      if (*I == V) {
212        Vector.erase(I);
213        return true;
214      }
215    return false;
216  }
217
218  void clear() {
219    Vector.clear();
220    Set.clear();
221  }
222
223  const_iterator begin() const {
224    if (isSmall())
225      return {Vector.begin()};
226    return {Set.begin()};
227  }
228
229  const_iterator end() const {
230    if (isSmall())
231      return {Vector.end()};
232    return {Set.end()};
233  }
234
235private:
236  bool isSmall() const { return Set.empty(); }
237
238  VIterator vfind(const T &V) const {
239    for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
240      if (*I == V)
241        return I;
242    return Vector.end();
243  }
244};
245
246/// If this set is of pointer values, transparently switch over to using
247/// SmallPtrSet for performance.
248template <typename PointeeType, unsigned N>
249class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
250
251/// Equality comparison for SmallSet.
252///
253/// Iterates over elements of LHS confirming that each element is also a member
254/// of RHS, and that RHS contains no additional values.
255/// Equivalent to N calls to RHS.count.
256/// For small-set mode amortized complexity is O(N^2)
257/// For large-set mode amortized complexity is linear, worst case is O(N^2) (if
258/// every hash collides).
259template <typename T, unsigned LN, unsigned RN, typename C>
260bool operator==(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) {
261  if (LHS.size() != RHS.size())
262    return false;
263
264  // All elements in LHS must also be in RHS
265  return all_of(LHS, [&RHS](const T &E) { return RHS.count(E); });
266}
267
268/// Inequality comparison for SmallSet.
269///
270/// Equivalent to !(LHS == RHS). See operator== for performance notes.
271template <typename T, unsigned LN, unsigned RN, typename C>
272bool operator!=(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) {
273  return !(LHS == RHS);
274}
275
276} // end namespace llvm
277
278#endif // LLVM_ADT_SMALLSET_H
279