LLVM: include/llvm/ADT/SparseSet.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#ifndef LLVM_ADT_SPARSESET_H
21#define LLVM_ADT_SPARSESET_H
22
26#include
27#include
28#include
29#include
30#include
31
32namespace llvm {
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
58 return Val.getSparseSetIndex();
59 }
60};
61
62
63
64
65
66template <typename KeyT, typename ValueT, typename KeyFunctorT>
68 unsigned operator()(const ValueT &Val) const {
69 if constexpr (std::is_same_v<KeyT, ValueT>)
70 return KeyFunctorT()(Val);
71 else
73 }
74};
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115template <typename ValueT, typename KeyT = unsigned,
116 typename KeyFunctorT = identity, typename SparseT = uint8_t>
118 static_assert(std::is_unsigned_v,
119 "SparseT must be an unsigned integer type");
120
123 DenseT Dense;
124
125 struct Deleter {
126 void operator()(SparseT *S) { free(S); }
127 };
128 std::unique_ptr<SparseT[], Deleter> Sparse;
129
130 unsigned Universe = 0;
131 KeyFunctorT KeyIndexOf;
133
134public:
140
145
146
147
148
149
150
151
153
154
155 assert(empty() && "Can only resize universe on an empty map");
156
157 if (U >= Universe / 4 && U <= Universe)
158 return;
159
160
161
162 Sparse.reset(static_cast<SparseT *>(safe_calloc(U, sizeof(SparseT))));
163 Universe = U;
164 }
165
166
169
174
175
176
177
178
179 [[nodiscard]] bool empty() const { return Dense.empty(); }
180
181
182
183
184
185
186 [[nodiscard]] size_type size() const { return Dense.size(); }
187
188
189
191
192 Dense.clear();
193 }
194
195
196
197
198
199
201 assert(Idx < Universe && "Key out of range");
202 assert(Sparse != nullptr && "Invalid sparse type");
203 const unsigned Stride = std::numeric_limits::max() + 1u;
204 for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride) {
205 const unsigned FoundIdx = ValIndexOf(Dense[i]);
206 assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?");
207 if (Idx == FoundIdx)
208 return begin() + i;
209
210 if (!Stride)
211 break;
212 }
213 return end();
214 }
215
216
217
218
219
220
224
228
229
230
231
235
236
237
238
242
243
244
245
246
247
248
249
250
251
252
253 std::pair<iterator, bool> insert(const ValueT &Val) {
254 unsigned Idx = ValIndexOf(Val);
257 return {I, false};
258 Sparse[Idx] = size();
259 Dense.push_back(Val);
260 return {end() - 1, true};
261 }
262
263
264
265
267
269
270 return Dense.pop_back_val();
271 }
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
288 assert(unsigned(I - begin()) < size() && "Invalid iterator");
290 *I = Dense.back();
291 unsigned BackIdx = ValIndexOf(Dense.back());
292 assert(BackIdx < Universe && "Invalid key in set. Did object mutate?");
293 Sparse[BackIdx] = I - begin();
294 }
295
296
297 Dense.pop_back();
298 return I;
299 }
300
301
302
303
304
305
309 return false;
311 return true;
312 }
313};
314
315}
316
317#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines MallocAllocator.
This file contains library features backported from future STL versions.
This file defines the SmallVector class.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition SparseSet.h:287
ValueT & operator[](const KeyT &Key)
array subscript - If an element already exists with this key, return it.
Definition SparseSet.h:266
SparseSet & operator=(const SparseSet &)=delete
void clear()
clear - Clears the set.
Definition SparseSet.h:190
const_iterator begin() const
Definition SparseSet.h:170
ValueT value_type
Definition SparseSet.h:135
iterator findIndex(unsigned Idx)
findIndex - Find an element by its index.
Definition SparseSet.h:200
SparseSet(const SparseSet &)=delete
typename DenseT::const_iterator const_iterator
Definition SparseSet.h:168
const_iterator end() const
Definition SparseSet.h:171
bool erase(const KeyT &Key)
erase - Erases an element identified by Key, if it exists.
Definition SparseSet.h:306
typename DenseT::iterator iterator
Definition SparseSet.h:167
ValueT * pointer
Definition SparseSet.h:138
size_type size() const
size - Returns the number of elements in the set.
Definition SparseSet.h:186
const_iterator find(const KeyT &Key) const
Definition SparseSet.h:225
std::pair< iterator, bool > insert(const ValueT &Val)
insert - Attempts to insert a new element.
Definition SparseSet.h:253
ValueT & reference
Definition SparseSet.h:136
iterator begin()
Definition SparseSet.h:172
ValueT pop_back_val()
Definition SparseSet.h:268
iterator end()
Definition SparseSet.h:173
SparseSet(SparseSet &&)=default
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise.
Definition SparseSet.h:239
const ValueT * const_pointer
Definition SparseSet.h:139
const ValueT & const_reference
Definition SparseSet.h:137
iterator find(const KeyT &Key)
find - Find an element by its key.
Definition SparseSet.h:221
bool contains(const KeyT &Key) const
Check if the set contains the given Key.
Definition SparseSet.h:232
bool empty() const
empty - Returns true if the set is empty.
Definition SparseSet.h:179
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition SparseSet.h:152
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_calloc(size_t Count, size_t Sz)
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
SparseSetValFunctor - Helper class for getting a value's index.
Definition SparseSet.h:67
unsigned operator()(const ValueT &Val) const
Definition SparseSet.h:68
SparseSetValTraits - Objects in a SparseSet are identified by keys that can be uniquely converted to ...
Definition SparseSet.h:56
static unsigned getValIndex(const ValueT &Val)
Definition SparseSet.h:57