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"
13#include "llvm/ADT/PointerUnion.h"
14#include "llvm/ADT/SmallVector.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>
29class TinyPtrVector {
30public:
31 using VecTy = SmallVector<EltTy, 4>;
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.
37 using PtrUnion = PointerUnion<EltTy, VecTy *>;
38
39private:
40 PtrUnion Val;
41
42public:
43 TinyPtrVector() = default;
44
45 ~TinyPtrVector() {
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
55 TinyPtrVector &operator=(const TinyPtrVector &RHS) {
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
83 TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
84 RHS.Val = (EltTy)nullptr;
85 }
86
87 TinyPtrVector &operator=(TinyPtrVector &&RHS) {
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.
123 explicit TinyPtrVector(ArrayRef<EltTy> Elts)
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.
145 operator MutableArrayRef<EltTy>() {
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
184 iterator begin() {
185 if (isa<EltTy>(Val))
186 return Val.getAddrOfPtr1();
187
188 return cast<VecTy *>(Val)->begin();
189 }
190
191 iterator end() {
192 if (isa<EltTy>(Val))
193 return begin() + (Val.isNull() ? 0 : 1);
194
195 return cast<VecTy *>(Val)->end();
196 }
197
198 const_iterator begin() const {
199 return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
200 }
201
202 const_iterator end() const {
203 return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
204 }
205
206 reverse_iterator rbegin() { return reverse_iterator(end()); }
207 reverse_iterator rend() { return reverse_iterator(begin()); }
208
209 const_reverse_iterator rbegin() const {
210 return const_reverse_iterator(end());
211 }
212
213 const_reverse_iterator rend() const {
214 return const_reverse_iterator(begin());
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
280 iterator erase(iterator I) {
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
296 iterator erase(iterator S, iterator E) {
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(NewVal: 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(NewVal: V);
323 return begin();
324 }
325
326 return cast<VecTy *>(Val)->insert(I, Elt);
327 }
328
329 template<typename ItTy>
330 iterator insert(iterator I, ItTy From, ItTy To) {
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
357

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