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 | |
21 | namespace 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 | /// |
29 | template <typename EltTy> |
30 | class TinyPtrVector { |
31 | public: |
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 | |
40 | private: |
41 | PtrUnion Val; |
42 | |
43 | public: |
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 | |