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/// \file
10/// This file defines the SmallSet class.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_SMALLSET_H
15#define LLVM_ADT_SMALLSET_H
16
17#include "llvm/ADT/SmallPtrSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/iterator.h"
21#include "llvm/Support/Compiler.h"
22#include "llvm/Support/type_traits.h"
23#include <cstddef>
24#include <functional>
25#include <set>
26#include <type_traits>
27#include <utility>
28
29namespace llvm {
30
31/// SmallSetIterator - This class implements a const_iterator for SmallSet by
32/// delegating to the underlying SmallVector or Set iterators.
33template <typename T, unsigned N, typename C>
34class SmallSetIterator
35 : public iterator_facade_base<SmallSetIterator<T, N, C>,
36 std::forward_iterator_tag, T> {
37private:
38 using SetIterTy = typename std::set<T, C>::const_iterator;
39 using VecIterTy = typename SmallVector<T, N>::const_iterator;
40 using SelfTy = SmallSetIterator<T, N, C>;
41
42 /// Iterators to the parts of the SmallSet containing the data. They are set
43 /// depending on isSmall.
44 union {
45 SetIterTy SetIter;
46 VecIterTy VecIter;
47 };
48
49 bool isSmall;
50
51public:
52 SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), isSmall(false) {}
53
54 SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), isSmall(true) {}
55
56 // Spell out destructor, copy/move constructor and assignment operators for
57 // MSVC STL, where set<T>::const_iterator is not trivially copy constructible.
58 ~SmallSetIterator() {
59 if (isSmall)
60 VecIter.~VecIterTy();
61 else
62 SetIter.~SetIterTy();
63 }
64
65 SmallSetIterator(const SmallSetIterator &Other) : isSmall(Other.isSmall) {
66 if (isSmall)
67 VecIter = Other.VecIter;
68 else
69 // Use placement new, to make sure SetIter is properly constructed, even
70 // if it is not trivially copy-able (e.g. in MSVC).
71 new (&SetIter) SetIterTy(Other.SetIter);
72 }
73
74 SmallSetIterator(SmallSetIterator &&Other) : isSmall(Other.isSmall) {
75 if (isSmall)
76 VecIter = std::move(Other.VecIter);
77 else
78 // Use placement new, to make sure SetIter is properly constructed, even
79 // if it is not trivially copy-able (e.g. in MSVC).
80 new (&SetIter) SetIterTy(std::move(Other.SetIter));
81 }
82
83 SmallSetIterator& operator=(const SmallSetIterator& Other) {
84 // Call destructor for SetIter, so it gets properly destroyed if it is
85 // not trivially destructible in case we are setting VecIter.
86 if (!isSmall)
87 SetIter.~SetIterTy();
88
89 isSmall = Other.isSmall;
90 if (isSmall)
91 VecIter = Other.VecIter;
92 else
93 new (&SetIter) SetIterTy(Other.SetIter);
94 return *this;
95 }
96
97 SmallSetIterator& operator=(SmallSetIterator&& Other) {
98 // Call destructor for SetIter, so it gets properly destroyed if it is
99 // not trivially destructible in case we are setting VecIter.
100 if (!isSmall)
101 SetIter.~SetIterTy();
102
103 isSmall = Other.isSmall;
104 if (isSmall)
105 VecIter = std::move(Other.VecIter);
106 else
107 new (&SetIter) SetIterTy(std::move(Other.SetIter));
108 return *this;
109 }
110
111 bool operator==(const SmallSetIterator &RHS) const {
112 if (isSmall != RHS.isSmall)
113 return false;
114 if (isSmall)
115 return VecIter == RHS.VecIter;
116 return SetIter == RHS.SetIter;
117 }
118
119 SmallSetIterator &operator++() { // Preincrement
120 if (isSmall)
121 VecIter++;
122 else
123 SetIter++;
124 return *this;
125 }
126
127 const T &operator*() const { return isSmall ? *VecIter : *SetIter; }
128};
129
130/// SmallSet - This maintains a set of unique values, optimizing for the case
131/// when the set is small (less than N). In this case, the set can be
132/// maintained with no mallocs. If the set gets large, we expand to using an
133/// std::set to maintain reasonable lookup times.
134template <typename T, unsigned N, typename C = std::less<T>>
135class SmallSet {
136 /// Use a SmallVector to hold the elements here (even though it will never
137 /// reach its 'large' stage) to avoid calling the default ctors of elements
138 /// we will never use.
139 SmallVector<T, N> Vector;
140 std::set<T, C> Set;
141
142 using VIterator = typename SmallVector<T, N>::const_iterator;
143 using SIterator = typename std::set<T, C>::const_iterator;
144 using mutable_iterator = typename SmallVector<T, N>::iterator;
145
146 // In small mode SmallPtrSet uses linear search for the elements, so it is
147 // not a good idea to choose this value too high. You may consider using a
148 // DenseSet<> instead if you expect many elements in the set.
149 static_assert(N <= 32, "N should be small");
150
151public:
152 using key_type = T;
153 using size_type = size_t;
154 using value_type = T;
155 using const_iterator = SmallSetIterator<T, N, C>;
156
157 SmallSet() = default;
158
159 [[nodiscard]] bool empty() const { return Vector.empty() && Set.empty(); }
160
161 size_type size() const {
162 return isSmall() ? Vector.size() : Set.size();
163 }
164
165 /// count - Return 1 if the element is in the set, 0 otherwise.
166 size_type count(const T &V) const {
167 if (isSmall()) {
168 // Since the collection is small, just do a linear search.
169 return vfind(V) == Vector.end() ? 0 : 1;
170 } else {
171 return Set.count(V);
172 }
173 }
174
175 /// insert - Insert an element into the set if it isn't already there.
176 /// Returns a pair. The first value of it is an iterator to the inserted
177 /// element or the existing element in the set. The second value is true
178 /// if the element is inserted (it was not in the set before).
179 std::pair<const_iterator, bool> insert(const T &V) {
180 if (!isSmall()) {
181 auto [I, Inserted] = Set.insert(V);
182 return std::make_pair(const_iterator(I), Inserted);
183 }
184
185 VIterator I = vfind(V);
186 if (I != Vector.end()) // Don't reinsert if it already exists.
187 return std::make_pair(const_iterator(I), false);
188 if (Vector.size() < N) {
189 Vector.push_back(V);
190 return std::make_pair(const_iterator(std::prev(Vector.end())), true);
191 }
192
193 // Otherwise, grow from vector to set.
194 while (!Vector.empty()) {
195 Set.insert(Vector.back());
196 Vector.pop_back();
197 }
198 return std::make_pair(const_iterator(Set.insert(V).first), 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
235 /// Check if the SmallSet contains the given element.
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
242private:
243 bool isSmall() const { return Set.empty(); }
244
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.
255template <typename PointeeType, unsigned N>
256class 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).
266template <typename T, unsigned LN, unsigned RN, typename C>
267bool 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.
278template <typename T, unsigned LN, unsigned RN, typename C>
279bool 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

source code of include/llvm-17/llvm/ADT/SmallSet.h