LLVM: include/llvm/ADT/SmallSet.h Source File

LLVM 22.0.0git
SmallSet.h
Go to the documentation of this file.
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/ADL.h"
18#include "llvm/ADT/STLForwardCompat.h"
19#include "llvm/ADT/SmallPtrSet.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/iterator.h"
22#include <cstddef>
23#include <functional>
24#include <initializer_list>
25#include <set>
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>
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
40 /// Iterators to the parts of the SmallSet containing the data. They are set
41 /// depending on isSmall.
42 union {
43 SetIterTy SetIter;
44 VecIterTy VecIter;
45 };
46
47 bool IsSmall;
48
49public:
50 SmallSetIterator(SetIterTy SetIter) : SetIter(SetIter), IsSmall(false) {}
51
52 SmallSetIterator(VecIterTy VecIter) : VecIter(VecIter), IsSmall(true) {}
53
54 // Spell out destructor, copy/move constructor and assignment operators for
55 // MSVC STL, where set<T>::const_iterator is not trivially copy constructible.
57 if (IsSmall)
58 VecIter.~VecIterTy();
59 else
60 SetIter.~SetIterTy();
61 }
62
63 SmallSetIterator(const SmallSetIterator &Other) : IsSmall(Other.IsSmall) {
64 if (IsSmall)
65 VecIter = Other.VecIter;
66 else
67 // Use placement new, to make sure SetIter is properly constructed, even
68 // if it is not trivially copy-able (e.g. in MSVC).
69 new (&SetIter) SetIterTy(Other.SetIter);
70 }
71
73 if (IsSmall)
74 VecIter = std::move(Other.VecIter);
75 else
76 // Use placement new, to make sure SetIter is properly constructed, even
77 // if it is not trivially copy-able (e.g. in MSVC).
78 new (&SetIter) SetIterTy(std::move(Other.SetIter));
79 }
80
82 // Call destructor for SetIter, so it gets properly destroyed if it is
83 // not trivially destructible in case we are setting VecIter.
84 if (!IsSmall)
85 SetIter.~SetIterTy();
86
87 IsSmall = Other.IsSmall;
88 if (IsSmall)
89 VecIter = Other.VecIter;
90 else
91 new (&SetIter) SetIterTy(Other.SetIter);
92 return *this;
93 }
94
96 // Call destructor for SetIter, so it gets properly destroyed if it is
97 // not trivially destructible in case we are setting VecIter.
98 if (!IsSmall)
99 SetIter.~SetIterTy();
100
101 IsSmall = Other.IsSmall;
102 if (IsSmall)
103 VecIter = std::move(Other.VecIter);
104 else
105 new (&SetIter) SetIterTy(std::move(Other.SetIter));
106 return *this;
107 }
108
109 bool operator==(const SmallSetIterator &RHS) const {
110 if (IsSmall != RHS.IsSmall)
111 return false;
112 if (IsSmall)
113 return VecIter == RHS.VecIter;
114 return SetIter == RHS.SetIter;
115 }
116
117 SmallSetIterator &operator++() { // Preincrement
118 if (IsSmall)
119 ++VecIter;
120 else
121 ++SetIter;
122 return *this;
123 }
124
125 const T &operator*() const { return IsSmall ? *VecIter : *SetIter; }
126};
127
128/// SmallSet - This maintains a set of unique values, optimizing for the case
129/// when the set is small (less than N). In this case, the set can be
130/// maintained with no mallocs. If the set gets large, we expand to using an
131/// std::set to maintain reasonable lookup times.
132template <typename T, unsigned N, typename C = std::less<T>>
133 class SmallSet {
134 /// Use a SmallVector to hold the elements here (even though it will never
135 /// reach its 'large' stage) to avoid calling the default ctors of elements
136 /// we will never use.
137 SmallVector<T, N> Vector;
138 std::set<T, C> Set;
139
140 // In small mode SmallPtrSet uses linear search for the elements, so it is
141 // not a good idea to choose this value too high. You may consider using a
142 // DenseSet<> instead if you expect many elements in the set.
143 static_assert(N <= 32, "N should be small");
144
145public:
146 using key_type = T;
147 using size_type = size_t;
148 using value_type = T;
150
151 SmallSet() = default;
152 SmallSet(const SmallSet &) = default;
153 SmallSet(SmallSet &&) = default;
154
155 template <typename IterT> SmallSet(IterT Begin, IterT End) {
156 insert(Begin, End);
157 }
158
159 template <typename Range>
162
163 SmallSet(std::initializer_list<T> L) { insert(L.begin(), L.end()); }
164
165 SmallSet &operator=(const SmallSet &) = default;
167
168 [[nodiscard]] bool empty() const { return Vector.empty() && Set.empty(); }
169
170 [[nodiscard]] size_type size() const {
171 return isSmall() ? Vector.size() : Set.size();
172 }
173
174 /// count - Return 1 if the element is in the set, 0 otherwise.
175 [[nodiscard]] size_type count(const T &V) const {
176 return contains(V) ? 1 : 0;
177 }
178
179 /// insert - Insert an element into the set if it isn't already there.
180 /// Returns a pair. The first value of it is an iterator to the inserted
181 /// element or the existing element in the set. The second value is true
182 /// if the element is inserted (it was not in the set before).
183 std::pair<const_iterator, bool> insert(const T &V) { return insertImpl(V); }
184
185 std::pair<const_iterator, bool> insert(T &&V) {
186 return insertImpl(std::move(V));
187 }
188
189 template <typename IterT>
190 void insert(IterT I, IterT E) {
191 for (; I != E; ++I)
192 insert(*I);
193 }
194
195 template <typename Range> void insert_range(Range &&R) {
196 insert(adl_begin(R), adl_end(R));
197 }
198
199 bool erase(const T &V) {
200 if (!isSmall())
201 return Set.erase(V);
202 auto I = vfind(V);
203 if (I != Vector.end()) {
204 Vector.erase(I);
205 return true;
206 }
207 return false;
208 }
209
210 void clear() {
211 Vector.clear();
212 Set.clear();
213 }
214
215 [[nodiscard]] const_iterator begin() const {
216 if (isSmall())
217 return {Vector.begin()};
218 return {Set.begin()};
219 }
220
221 [[nodiscard]] const_iterator end() const {
222 if (isSmall())
223 return {Vector.end()};
224 return {Set.end()};
225 }
226
227 /// Check if the SmallSet contains the given element.
228 [[nodiscard]] bool contains(const T &V) const {
229 if (isSmall())
230 return vfind(V) != Vector.end();
231 return Set.find(V) != Set.end();
232 }
233
234private:
235 bool isSmall() const { return Set.empty(); }
236
237 template <typename ArgType>
238 std::pair<const_iterator, bool> insertImpl(ArgType &&V) {
239 static_assert(std::is_convertible_v<ArgType, T>,
240 "ArgType must be convertible to T!");
241 if (!isSmall()) {
242 auto [I, Inserted] = Set.insert(std::forward<ArgType>(V));
243 return {const_iterator(I), Inserted};
244 }
245
246 auto I = vfind(V);
247 if (I != Vector.end()) // Don't reinsert if it already exists.
248 return {const_iterator(I), false};
249 if (Vector.size() < N) {
250 Vector.push_back(std::forward<ArgType>(V));
251 return {const_iterator(std::prev(Vector.end())), true};
252 }
253 // Otherwise, grow from vector to set.
254 Set.insert(std::make_move_iterator(Vector.begin()),
255 std::make_move_iterator(Vector.end()));
256 Vector.clear();
257 return {const_iterator(Set.insert(std::forward<ArgType>(V)).first), true};
258 }
259
260 // Handwritten linear search. The use of std::find might hurt performance as
261 // its implementation may be optimized for larger containers.
262 typename SmallVector<T, N>::const_iterator vfind(const T &V) const {
263 for (auto I = Vector.begin(), E = Vector.end(); I != E; ++I)
264 if (*I == V)
265 return I;
266 return Vector.end();
267 }
268};
269
270/// If this set is of pointer values, transparently switch over to using
271/// SmallPtrSet for performance.
272template <typename PointeeType, unsigned N>
273 class SmallSet<PointeeType *, N> : public SmallPtrSet<PointeeType *, N> {};
274
275/// Equality comparison for SmallSet.
276///
277/// Iterates over elements of LHS confirming that each element is also a member
278/// of RHS, and that RHS contains no additional values.
279/// Equivalent to N calls to RHS.count.
280/// For small-set mode amortized complexity is O(N^2)
281/// For large-set mode amortized complexity is linear, worst case is O(N^2) (if
282/// every hash collides).
283template <typename T, unsigned LN, unsigned RN, typename C>
284 [[nodiscard]] bool operator==(const SmallSet<T, LN, C> &LHS,
285 const SmallSet<T, RN, C> &RHS) {
286 if (LHS.size() != RHS.size())
287 return false;
288
289 // All elements in LHS must also be in RHS
290 return all_of(LHS, [&RHS](const T &E) { return RHS.count(E); });
291}
292
293/// Inequality comparison for SmallSet.
294///
295/// Equivalent to !(LHS == RHS). See operator== for performance notes.
296template <typename T, unsigned LN, unsigned RN, typename C>
297 [[nodiscard]] bool operator!=(const SmallSet<T, LN, C> &LHS,
298 const SmallSet<T, RN, C> &RHS) {
299 return !(LHS == RHS);
300}
301
302} // end namespace llvm
303
304#endif // LLVM_ADT_SMALLSET_H
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
I
#define I(x, y, z)
Definition MD5.cpp:58
T
#define T
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
This file contains library features backported from future STL versions.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Value * RHS
Value * LHS
SmallSetIterator - This class implements a const_iterator for SmallSet by delegating to the underlyin...
Definition SmallSet.h:35
SmallSetIterator & operator=(SmallSetIterator &&Other)
Definition SmallSet.h:95
SmallSetIterator & operator++()
Definition SmallSet.h:117
bool operator==(const SmallSetIterator &RHS) const
Definition SmallSet.h:109
SetIterTy SetIter
Definition SmallSet.h:43
SmallSetIterator(SetIterTy SetIter)
Definition SmallSet.h:50
SmallSetIterator & operator=(const SmallSetIterator &Other)
Definition SmallSet.h:81
SmallSetIterator(const SmallSetIterator &Other)
Definition SmallSet.h:63
const T & operator*() const
Definition SmallSet.h:125
VecIterTy VecIter
Definition SmallSet.h:44
SmallSetIterator(VecIterTy VecIter)
Definition SmallSet.h:52
SmallSetIterator(SmallSetIterator &&Other)
Definition SmallSet.h:72
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition SmallSet.h:133
const_iterator begin() const
Definition SmallSet.h:215
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition SmallSet.h:175
SmallSetIterator< T, N, C > const_iterator
Definition SmallSet.h:149
bool empty() const
Definition SmallSet.h:168
void insert(IterT I, IterT E)
Definition SmallSet.h:190
void insert_range(Range &&R)
Definition SmallSet.h:195
std::pair< const_iterator, bool > insert(T &&V)
Definition SmallSet.h:185
SmallSet(std::initializer_list< T > L)
Definition SmallSet.h:163
SmallSet()=default
bool erase(const T &V)
Definition SmallSet.h:199
size_t size_type
Definition SmallSet.h:147
void clear()
Definition SmallSet.h:210
SmallSet(llvm::from_range_t, Range &&R)
Definition SmallSet.h:160
SmallSet & operator=(const SmallSet &)=default
SmallSet(SmallSet &&)=default
SmallSet(const SmallSet &)=default
const_iterator end() const
Definition SmallSet.h:221
SmallSet(IterT Begin, IterT End)
Definition SmallSet.h:155
bool contains(const T &V) const
Check if the SmallSet contains the given element.
Definition SmallSet.h:228
SmallSet & operator=(SmallSet &&)=default
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition SmallSet.h:183
size_type size() const
Definition SmallSet.h:170
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition SmallVector.h:1203
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition iterator.h:80
This is an optimization pass for GlobalISel generic memory operations.
Definition AddressRanges.h:18
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1725
constexpr auto adl_begin(RangeT &&range) -> decltype(adl_detail::begin_impl(std::forward< RangeT >(range)))
Returns the begin iterator to range using std::begin and function found through Argument-Dependent Lo...
Definition ADL.h:78
bool operator!=(uint64_t V1, const APInt &V2)
Definition APInt.h:2114
constexpr auto adl_end(RangeT &&range) -> decltype(adl_detail::end_impl(std::forward< RangeT >(range)))
Returns the end iterator to range using std::end and functions found through Argument-Dependent Looku...
Definition ADL.h:86
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
@ Other
Any other memory.
Definition ModRef.h:68
N
#define N
Generated on for LLVM by doxygen 1.14.0

AltStyle によって変換されたページ (->オリジナル) /