LLVM 17.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
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/iterator.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>
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;
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.
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
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
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
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 size_type = size_t;
154
155 SmallSet() = default;
156
157 [[nodiscard]] bool empty() const { return Vector.empty() && Set.empty(); }
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 a pair. The first value of it is an iterator to the inserted
175 /// element or the existing element in the set. The second value is true
176 /// if the element is inserted (it was not in the set before).
177 std::pair<const_iterator, bool> insert(const T &V) {
178 if (!isSmall()) {
179 auto [I, Inserted] = Set.insert(V);
180 return std::make_pair(const_iterator(I), Inserted);
181 }
182
183 VIterator I = vfind(V);
184 if (I != Vector.end()) // Don't reinsert if it already exists.
185 return std::make_pair(const_iterator(I), false);
186 if (Vector.size() < N) {
187 Vector.push_back(V);
188 return std::make_pair(const_iterator(std::prev(Vector.end())), true);
189 }
190
191 // Otherwise, grow from vector to set.
192 while (!Vector.empty()) {
193 Set.insert(Vector.back());
194 Vector.pop_back();
195 }
196 return std::make_pair(const_iterator(Set.insert(V).first), true);
197 }
198
199 template <typename IterT>
200 void insert(IterT I, IterT E) {
201 for (; I != E; ++I)
202 insert(*I);
203 }
204
205 bool erase(const T &V) {
206 if (!isSmall())
207 return Set.erase(V);
208 for (mutable_iterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
209 if (*I == V) {
210 Vector.erase(I);
211 return true;
212 }
213 return false;
214 }
215
216 void clear() {
217 Vector.clear();
218 Set.clear();
219 }
220
222 if (isSmall())
223 return {Vector.begin()};
224 return {Set.begin()};
225 }
226
228 if (isSmall())
229 return {Vector.end()};
230 return {Set.end()};
231 }
232
233 /// Check if the SmallSet contains the given element.
234 bool contains(const T &V) const {
235 if (isSmall())
236 return vfind(V) != Vector.end();
237 return Set.find(V) != Set.end();
238 }
239
240private:
241 bool isSmall() const { return Set.empty(); }
242
243 VIterator vfind(const T &V) const {
244 for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
245 if (*I == V)
246 return I;
247 return Vector.end();
248 }
249};
250
251/// If this set is of pointer values, transparently switch over to using
252/// SmallPtrSet for performance.
253template <typename PointeeType, unsigned N>
254class SmallSet<PointeeType*, N> : public SmallPtrSet<PointeeType*, N> {};
255
256/// Equality comparison for SmallSet.
257///
258/// Iterates over elements of LHS confirming that each element is also a member
259/// of RHS, and that RHS contains no additional values.
260/// Equivalent to N calls to RHS.count.
261/// For small-set mode amortized complexity is O(N^2)
262/// For large-set mode amortized complexity is linear, worst case is O(N^2) (if
263/// every hash collides).
264template <typename T, unsigned LN, unsigned RN, typename C>
266 if (LHS.size() != RHS.size())
267 return false;
268
269 // All elements in LHS must also be in RHS
270 return all_of(LHS, [&RHS](const T &E) { return RHS.count(E); });
271}
272
273/// Inequality comparison for SmallSet.
274///
275/// Equivalent to !(LHS == RHS). See operator== for performance notes.
276template <typename T, unsigned LN, unsigned RN, typename C>
278 return !(LHS == RHS);
279}
280
281} // end namespace llvm
282
283#endif // LLVM_ADT_SMALLSET_H
basic Basic Alias true
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define I(x, y, z)
Definition: MD5.cpp:58
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Value * RHS
Value * LHS
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
SmallSetIterator - This class implements a const_iterator for SmallSet by delegating to the underlyin...
Definition: SmallSet.h:36
SmallSetIterator & operator=(SmallSetIterator &&Other)
Definition: SmallSet.h:97
SmallSetIterator & operator++()
Definition: SmallSet.h:119
bool operator==(const SmallSetIterator &RHS) const
Definition: SmallSet.h:111
SmallSetIterator(SetIterTy SetIter)
Definition: SmallSet.h:52
SmallSetIterator & operator=(const SmallSetIterator &Other)
Definition: SmallSet.h:83
SmallSetIterator(const SmallSetIterator &Other)
Definition: SmallSet.h:65
const T & operator*() const
Definition: SmallSet.h:127
SmallSetIterator(VecIterTy VecIter)
Definition: SmallSet.h:54
SmallSetIterator(SmallSetIterator &&Other)
Definition: SmallSet.h:74
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
const_iterator begin() const
Definition: SmallSet.h:221
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
SmallSetIterator< T, N, C > const_iterator
Definition: SmallSet.h:153
bool empty() const
Definition: SmallSet.h:157
void insert(IterT I, IterT E)
Definition: SmallSet.h:200
SmallSet()=default
bool erase(const T &V)
Definition: SmallSet.h:205
size_t size_type
Definition: SmallSet.h:152
void clear()
Definition: SmallSet.h:216
const_iterator end() const
Definition: SmallSet.h:227
bool contains(const T &V) const
Check if the SmallSet contains the given element.
Definition: SmallSet.h:234
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:177
size_type size() const
Definition: SmallSet.h:159
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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:1819
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:2047
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
#define N