LLVM 20.0.0git
TinyPtrVector.h
Go to the documentation of this file.
1//===- llvm/ADT/TinyPtrVector.h - 'Normally tiny' vectors -------*- 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#ifndef LLVM_ADT_TINYPTRVECTOR_H
10#define LLVM_ADT_TINYPTRVECTOR_H
11
12#include "llvm/ADT/ArrayRef.h"
15#include <cassert>
16#include <cstddef>
17#include <iterator>
18#include <type_traits>
19
20namespace llvm {
21
22/// TinyPtrVector - This class is specialized for cases where there are
23/// normally 0 or 1 element in a vector, but is general enough to go beyond that
24/// when required.
25///
26/// NOTE: This container doesn't allow you to store a null pointer into it.
27///
28template <typename EltTy>
30public:
32 using value_type = typename VecTy::value_type;
33 // EltTy must be the first pointer type so that is<EltTy> is true for the
34 // default-constructed PtrUnion. This allows an empty TinyPtrVector to
35 // naturally vend a begin/end iterator of type EltTy* without an additional
36 // check for the empty state.
38
39private:
40 PtrUnion Val;
41
42public:
43 TinyPtrVector() = default;
44
46 if (VecTy *V = dyn_cast_if_present<VecTy *>(Val))
47 delete V;
48 }
49
50 TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
51 if (VecTy *V = dyn_cast_if_present<VecTy *>(Val))
52 Val = new VecTy(*V);
53 }
54
56 if (this == &RHS)
57 return *this;
58 if (RHS.empty()) {
59 this->clear();
60 return *this;
61 }
62
63 // Try to squeeze into the single slot. If it won't fit, allocate a copied
64 // vector.
65 if (isa<EltTy>(Val)) {
66 if (RHS.size() == 1)
67 Val = RHS.front();
68 else
69 Val = new VecTy(*cast<VecTy *>(RHS.Val));
70 return *this;
71 }
72
73 // If we have a full vector allocated, try to re-use it.
74 if (isa<EltTy>(RHS.Val)) {
75 cast<VecTy *>(Val)->clear();
76 cast<VecTy *>(Val)->push_back(RHS.front());
77 } else {
78 *cast<VecTy *>(Val) = *cast<VecTy *>(RHS.Val);
79 }
80 return *this;
81 }
82
84 RHS.Val = (EltTy)nullptr;
85 }
86
88 if (this == &RHS)
89 return *this;
90 if (RHS.empty()) {
91 this->clear();
92 return *this;
93 }
94
95 // If this vector has been allocated on the heap, re-use it if cheap. If it
96 // would require more copying, just delete it and we'll steal the other
97 // side.
98 if (VecTy *V = dyn_cast_if_present<VecTy *>(Val)) {
99 if (isa<EltTy>(RHS.Val)) {
100 V->clear();
101 V->push_back(RHS.front());
102 RHS.Val = EltTy();
103 return *this;
104 }
105 delete V;
106 }
107
108 Val = RHS.Val;
109 RHS.Val = EltTy();
110 return *this;
111 }
112
113 TinyPtrVector(std::initializer_list<EltTy> IL)
114 : Val(IL.size() == 0
115 ? PtrUnion()
116 : IL.size() == 1 ? PtrUnion(*IL.begin())
117 : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
118
119 /// Constructor from an ArrayRef.
120 ///
121 /// This also is a constructor for individual array elements due to the single
122 /// element constructor for ArrayRef.
124 : Val(Elts.empty()
125 ? PtrUnion()
126 : Elts.size() == 1
127 ? PtrUnion(Elts[0])
128 : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
129
130 TinyPtrVector(size_t Count, EltTy Value)
131 : Val(Count == 0 ? PtrUnion()
132 : Count == 1 ? PtrUnion(Value)
133 : PtrUnion(new VecTy(Count, Value))) {}
134
135 // implicit conversion operator to ArrayRef.
136 operator ArrayRef<EltTy>() const {
137 if (Val.isNull())
138 return std::nullopt;
139 if (isa<EltTy>(Val))
140 return *Val.getAddrOfPtr1();
141 return *cast<VecTy *>(Val);
142 }
143
144 // implicit conversion operator to MutableArrayRef.
146 if (Val.isNull())
147 return std::nullopt;
148 if (isa<EltTy>(Val))
149 return *Val.getAddrOfPtr1();
150 return *cast<VecTy *>(Val);
151 }
152
153 // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
154 template <
155 typename U,
156 std::enable_if_t<std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
157 bool> = false>
158 operator ArrayRef<U>() const {
159 return operator ArrayRef<EltTy>();
160 }
161
162 bool empty() const {
163 // This vector can be empty if it contains no element, or if it
164 // contains a pointer to an empty vector.
165 if (Val.isNull()) return true;
166 if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val))
167 return Vec->empty();
168 return false;
169 }
170
171 unsigned size() const {
172 if (empty())
173 return 0;
174 if (isa<EltTy>(Val))
175 return 1;
176 return cast<VecTy *>(Val)->size();
177 }
178
179 using iterator = EltTy *;
180 using const_iterator = const EltTy *;
181 using reverse_iterator = std::reverse_iterator<iterator>;
182 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
183
185 if (isa<EltTy>(Val))
186 return Val.getAddrOfPtr1();
187
188 return cast<VecTy *>(Val)->begin();
189 }
190
192 if (isa<EltTy>(Val))
193 return begin() + (Val.isNull() ? 0 : 1);
194
195 return cast<VecTy *>(Val)->end();
196 }
197
199 return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
200 }
201
203 return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
204 }
205
208
210 return const_reverse_iterator(end());
211 }
212
215 }
216
217 EltTy operator[](unsigned i) const {
218 assert(!Val.isNull() && "can't index into an empty vector");
219 if (isa<EltTy>(Val)) {
220 assert(i == 0 && "tinyvector index out of range");
221 return cast<EltTy>(Val);
222 }
223
224 assert(i < cast<VecTy *>(Val)->size() && "tinyvector index out of range");
225 return (*cast<VecTy *>(Val))[i];
226 }
227
228 EltTy front() const {
229 assert(!empty() && "vector empty");
230 if (isa<EltTy>(Val))
231 return cast<EltTy>(Val);
232 return cast<VecTy *>(Val)->front();
233 }
234
235 EltTy back() const {
236 assert(!empty() && "vector empty");
237 if (isa<EltTy>(Val))
238 return cast<EltTy>(Val);
239 return cast<VecTy *>(Val)->back();
240 }
241
242 void push_back(EltTy NewVal) {
243 // If we have nothing, add something.
244 if (Val.isNull()) {
245 Val = NewVal;
246 assert(!Val.isNull() && "Can't add a null value");
247 return;
248 }
249
250 // If we have a single value, convert to a vector.
251 if (isa<EltTy>(Val)) {
252 EltTy V = cast<EltTy>(Val);
253 Val = new VecTy();
254 cast<VecTy *>(Val)->push_back(V);
255 }
256
257 // Add the new value, we know we have a vector.
258 cast<VecTy *>(Val)->push_back(NewVal);
259 }
260
261 void pop_back() {
262 // If we have a single value, convert to empty.
263 if (isa<EltTy>(Val))
264 Val = (EltTy)nullptr;
265 else if (VecTy *Vec = cast<VecTy *>(Val))
266 Vec->pop_back();
267 }
268
269 void clear() {
270 // If we have a single value, convert to empty.
271 if (isa<EltTy>(Val)) {
272 Val = EltTy();
273 } else if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) {
274 // If we have a vector form, just clear it.
275 Vec->clear();
276 }
277 // Otherwise, we're already empty.
278 }
279
281 assert(I >= begin() && "Iterator to erase is out of bounds.");
282 assert(I < end() && "Erasing at past-the-end iterator.");
283
284 // If we have a single value, convert to empty.
285 if (isa<EltTy>(Val)) {
286 if (I == begin())
287 Val = EltTy();
288 } else if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) {
289 // multiple items in a vector; just do the erase, there is no
290 // benefit to collapsing back to a pointer
291 return Vec->erase(I);
292 }
293 return end();
294 }
295
297 assert(S >= begin() && "Range to erase is out of bounds.");
298 assert(S <= E && "Trying to erase invalid range.");
299 assert(E <= end() && "Trying to erase past the end.");
300
301 if (isa<EltTy>(Val)) {
302 if (S == begin() && S != E)
303 Val = EltTy();
304 } else if (VecTy *Vec = dyn_cast_if_present<VecTy *>(Val)) {
305 return Vec->erase(S, E);
306 }
307 return end();
308 }
309
310 iterator insert(iterator I, const EltTy &Elt) {
311 assert(I >= this->begin() && "Insertion iterator is out of bounds.");
312 assert(I <= this->end() && "Inserting past the end of the vector.");
313 if (I == end()) {
314 push_back(Elt);
315 return std::prev(end());
316 }
317 assert(!Val.isNull() && "Null value with non-end insert iterator.");
318 if (isa<EltTy>(Val)) {
319 EltTy V = cast<EltTy>(Val);
320 assert(I == begin());
321 Val = Elt;
322 push_back(V);
323 return begin();
324 }
325
326 return cast<VecTy *>(Val)->insert(I, Elt);
327 }
328
329 template<typename ItTy>
331 assert(I >= this->begin() && "Insertion iterator is out of bounds.");
332 assert(I <= this->end() && "Inserting past the end of the vector.");
333 if (From == To)
334 return I;
335
336 // If we have a single value, convert to a vector.
337 ptrdiff_t Offset = I - begin();
338 if (Val.isNull()) {
339 if (std::next(From) == To) {
340 Val = *From;
341 return begin();
342 }
343
344 Val = new VecTy();
345 } else if (isa<EltTy>(Val)) {
346 EltTy V = cast<EltTy>(Val);
347 Val = new VecTy();
348 cast<VecTy *>(Val)->push_back(V);
349 }
350 return cast<VecTy *>(Val)->insert(begin() + Offset, From, To);
351 }
352};
353
354} // end namespace llvm
355
356#endif // LLVM_ADT_TINYPTRVECTOR_H
BlockVerifier::State From
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Given that RA is a live value
#define I(x, y, z)
Definition: MD5.cpp:58
This file defines the PointerUnion class, which is a discriminated union of pointer types.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
Value * RHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:307
bool isNull() const
Test if the pointer held in the union is null, regardless of which type it is.
Definition: PointerUnion.h:142
First const * getAddrOfPtr1() const
If the union is set to the first pointer type get an address pointing to it.
Definition: PointerUnion.h:168
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:29
reverse_iterator rbegin()
const EltTy * const_iterator
TinyPtrVector(std::initializer_list< EltTy > IL)
void push_back(EltTy NewVal)
TinyPtrVector & operator=(TinyPtrVector &&RHS)
Definition: TinyPtrVector.h:87
reverse_iterator rend()
TinyPtrVector()=default
std::reverse_iterator< const_iterator > const_reverse_iterator
const_reverse_iterator rbegin() const
TinyPtrVector(ArrayRef< EltTy > Elts)
Constructor from an ArrayRef.
std::reverse_iterator< iterator > reverse_iterator
EltTy front() const
const_iterator begin() const
iterator erase(iterator I)
TinyPtrVector & operator=(const TinyPtrVector &RHS)
Definition: TinyPtrVector.h:55
TinyPtrVector(const TinyPtrVector &RHS)
Definition: TinyPtrVector.h:50
const_reverse_iterator rend() const
const_iterator end() const
bool empty() const
unsigned size() const
iterator insert(iterator I, const EltTy &Elt)
iterator erase(iterator S, iterator E)
SmallVector< EltTy, 4 > VecTy
Definition: TinyPtrVector.h:31
EltTy back() const
typename VecTy::value_type value_type
Definition: TinyPtrVector.h:32
TinyPtrVector(TinyPtrVector &&RHS)
Definition: TinyPtrVector.h:83
iterator insert(iterator I, ItTy From, ItTy To)
EltTy operator[](unsigned i) const
TinyPtrVector(size_t Count, EltTy Value)
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:480