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 
28 namespace llvm {
29 
30 /// SmallSetIterator - This class implements a const_iterator for SmallSet by
31 /// delegating to the underlying SmallVector or Set iterators.
32 template <typename T, unsigned N, typename C>
33 class SmallSetIterator
34     : public iterator_facade_base<SmallSetIterator<T, N, C>,
35                                   std::forward_iterator_tag, T> {
36 private:
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 
50 public:
SmallSetIterator(SetIterTy SetIter)51   SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {}
52 
SmallSetIterator(VecIterTy VecIter)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.
~SmallSetIterator()57   ~SmallSetIterator() {
58     if (isSmall)
59       VecIter.~VecIterTy();
60     else
61       SetIter.~SetIterTy();
62   }
63 
SmallSetIterator(const SmallSetIterator & Other)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 
SmallSetIterator(SmallSetIterator && Other)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.
133 template <typename T, unsigned N, typename C = std::less<T>>
134 class 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 
149 public:
150   using size_type = size_t;
151   using const_iterator = SmallSetIterator<T, N, C>;
152 
153   SmallSet() = default;
154 
empty()155   LLVM_NODISCARD bool empty() const {
156     return Vector.empty() && Set.empty();
157   }
158 
size()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.
count(const T & V)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.
insert(const T & V)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>
insert(IterT I,IterT E)202   void insert(IterT I, IterT E) {
203     for (; I != E; ++I)
204       insert(*I);
205   }
206 
erase(const T & V)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 
clear()218   void clear() {
219     Vector.clear();
220     Set.clear();
221   }
222 
begin()223   const_iterator begin() const {
224     if (isSmall())
225       return {Vector.begin()};
226     return {Set.begin()};
227   }
228 
end()229   const_iterator end() const {
230     if (isSmall())
231       return {Vector.end()};
232     return {Set.end()};
233   }
234 
235   /// Check if the SmallSet contains the given element.
contains(const T & V)236   bool contains(const T &V) const {
237     if (isSmall())
238       return vfind(V) != Vector.end();
239     return Set.find(V) != Set.end();
240   }
241 
242 private:
isSmall()243   bool isSmall() const { return Set.empty(); }
244 
vfind(const T & V)245   VIterator vfind(const T &V) const {
246     for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
247       if (*I == V)
248         return I;
249     return Vector.end();
250   }
251 };
252 
253 /// If this set is of pointer values, transparently switch over to using
254 /// SmallPtrSet for performance.
255 template <typename PointeeType, unsigned N>
256 class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
257 
258 /// Equality comparison for SmallSet.
259 ///
260 /// Iterates over elements of LHS confirming that each element is also a member
261 /// of RHS, and that RHS contains no additional values.
262 /// Equivalent to N calls to RHS.count.
263 /// For small-set mode amortized complexity is O(N^2)
264 /// For large-set mode amortized complexity is linear, worst case is O(N^2) (if
265 /// every hash collides).
266 template <typename T, unsigned LN, unsigned RN, typename C>
267 bool operator==(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) {
268   if (LHS.size() != RHS.size())
269     return false;
270 
271   // All elements in LHS must also be in RHS
272   return all_of(LHS, [&RHS](const T &E) { return RHS.count(E); });
273 }
274 
275 /// Inequality comparison for SmallSet.
276 ///
277 /// Equivalent to !(LHS == RHS). See operator== for performance notes.
278 template <typename T, unsigned LN, unsigned RN, typename C>
279 bool operator!=(const SmallSet<T, LN, C> &LHS, const SmallSet<T, RN, C> &RHS) {
280   return !(LHS == RHS);
281 }
282 
283 } // end namespace llvm
284 
285 #endif // LLVM_ADT_SMALLSET_H
286