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