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