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 
20 namespace 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 ///
28 template <typename EltTy>
29 class TinyPtrVector {
30 public:
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 
39 private:
40   PtrUnion Val;
41 
42 public:
43   TinyPtrVector() = default;
44 
~TinyPtrVector()45   ~TinyPtrVector() {
46     if (VecTy *V = Val.template dyn_cast<VecTy*>())
47       delete V;
48   }
49 
TinyPtrVector(const TinyPtrVector & RHS)50   TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
51     if (VecTy *V = Val.template dyn_cast<VecTy*>())
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 (Val.template is<EltTy>()) {
66       if (RHS.size() == 1)
67         Val = RHS.front();
68       else
69         Val = new VecTy(*RHS.Val.template get<VecTy*>());
70       return *this;
71     }
72 
73     // If we have a full vector allocated, try to re-use it.
74     if (RHS.Val.template is<EltTy>()) {
75       Val.template get<VecTy*>()->clear();
76       Val.template get<VecTy*>()->push_back(RHS.front());
77     } else {
78       *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>();
79     }
80     return *this;
81   }
82 
TinyPtrVector(TinyPtrVector && RHS)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 = Val.template dyn_cast<VecTy*>()) {
99       if (RHS.Val.template is<EltTy>()) {
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 
TinyPtrVector(std::initializer_list<EltTy> IL)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.
TinyPtrVector(ArrayRef<EltTy> Elts)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 
TinyPtrVector(size_t Count,EltTy Value)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 (Val.template is<EltTy>())
140       return *Val.getAddrOfPtr1();
141     return *Val.template get<VecTy*>();
142   }
143 
144   // implicit conversion operator to MutableArrayRef.
145   operator MutableArrayRef<EltTy>() {
146     if (Val.isNull())
147       return std::nullopt;
148     if (Val.template is<EltTy>())
149       return *Val.getAddrOfPtr1();
150     return *Val.template get<VecTy*>();
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 
empty()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 = Val.template dyn_cast<VecTy*>())
167       return Vec->empty();
168     return false;
169   }
170 
size()171   unsigned size() const {
172     if (empty())
173       return 0;
174     if (Val.template is<EltTy>())
175       return 1;
176     return Val.template get<VecTy*>()->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 
begin()184   iterator begin() {
185     if (Val.template is<EltTy>())
186       return Val.getAddrOfPtr1();
187 
188     return Val.template get<VecTy *>()->begin();
189   }
190 
end()191   iterator end() {
192     if (Val.template is<EltTy>())
193       return begin() + (Val.isNull() ? 0 : 1);
194 
195     return Val.template get<VecTy *>()->end();
196   }
197 
begin()198   const_iterator begin() const {
199     return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
200   }
201 
end()202   const_iterator end() const {
203     return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
204   }
205 
rbegin()206   reverse_iterator rbegin() { return reverse_iterator(end()); }
rend()207   reverse_iterator rend() { return reverse_iterator(begin()); }
208 
rbegin()209   const_reverse_iterator rbegin() const {
210     return const_reverse_iterator(end());
211   }
212 
rend()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 (Val.template is<EltTy>()) {
220       assert(i == 0 && "tinyvector index out of range");
221       return Val.template get<EltTy>();
222     }
223 
224     assert(i < Val.template get<VecTy*>()->size() &&
225            "tinyvector index out of range");
226     return (*Val.template get<VecTy*>())[i];
227   }
228 
front()229   EltTy front() const {
230     assert(!empty() && "vector empty");
231     if (Val.template is<EltTy>())
232       return Val.template get<EltTy>();
233     return Val.template get<VecTy*>()->front();
234   }
235 
back()236   EltTy back() const {
237     assert(!empty() && "vector empty");
238     if (Val.template is<EltTy>())
239       return Val.template get<EltTy>();
240     return Val.template get<VecTy*>()->back();
241   }
242 
push_back(EltTy NewVal)243   void push_back(EltTy NewVal) {
244     // If we have nothing, add something.
245     if (Val.isNull()) {
246       Val = NewVal;
247       assert(!Val.isNull() && "Can't add a null value");
248       return;
249     }
250 
251     // If we have a single value, convert to a vector.
252     if (Val.template is<EltTy>()) {
253       EltTy V = Val.template get<EltTy>();
254       Val = new VecTy();
255       Val.template get<VecTy*>()->push_back(V);
256     }
257 
258     // Add the new value, we know we have a vector.
259     Val.template get<VecTy*>()->push_back(NewVal);
260   }
261 
pop_back()262   void pop_back() {
263     // If we have a single value, convert to empty.
264     if (Val.template is<EltTy>())
265       Val = (EltTy)nullptr;
266     else if (VecTy *Vec = Val.template get<VecTy*>())
267       Vec->pop_back();
268   }
269 
clear()270   void clear() {
271     // If we have a single value, convert to empty.
272     if (Val.template is<EltTy>()) {
273       Val = EltTy();
274     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
275       // If we have a vector form, just clear it.
276       Vec->clear();
277     }
278     // Otherwise, we're already empty.
279   }
280 
erase(iterator I)281   iterator erase(iterator I) {
282     assert(I >= begin() && "Iterator to erase is out of bounds.");
283     assert(I < end() && "Erasing at past-the-end iterator.");
284 
285     // If we have a single value, convert to empty.
286     if (Val.template is<EltTy>()) {
287       if (I == begin())
288         Val = EltTy();
289     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
290       // multiple items in a vector; just do the erase, there is no
291       // benefit to collapsing back to a pointer
292       return Vec->erase(I);
293     }
294     return end();
295   }
296 
erase(iterator S,iterator E)297   iterator erase(iterator S, iterator E) {
298     assert(S >= begin() && "Range to erase is out of bounds.");
299     assert(S <= E && "Trying to erase invalid range.");
300     assert(E <= end() && "Trying to erase past the end.");
301 
302     if (Val.template is<EltTy>()) {
303       if (S == begin() && S != E)
304         Val = EltTy();
305     } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
306       return Vec->erase(S, E);
307     }
308     return end();
309   }
310 
insert(iterator I,const EltTy & Elt)311   iterator insert(iterator I, const EltTy &Elt) {
312     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
313     assert(I <= this->end() && "Inserting past the end of the vector.");
314     if (I == end()) {
315       push_back(Elt);
316       return std::prev(end());
317     }
318     assert(!Val.isNull() && "Null value with non-end insert iterator.");
319     if (Val.template is<EltTy>()) {
320       EltTy V = Val.template get<EltTy>();
321       assert(I == begin());
322       Val = Elt;
323       push_back(V);
324       return begin();
325     }
326 
327     return Val.template get<VecTy*>()->insert(I, Elt);
328   }
329 
330   template<typename ItTy>
insert(iterator I,ItTy From,ItTy To)331   iterator insert(iterator I, ItTy From, ItTy To) {
332     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
333     assert(I <= this->end() && "Inserting past the end of the vector.");
334     if (From == To)
335       return I;
336 
337     // If we have a single value, convert to a vector.
338     ptrdiff_t Offset = I - begin();
339     if (Val.isNull()) {
340       if (std::next(From) == To) {
341         Val = *From;
342         return begin();
343       }
344 
345       Val = new VecTy();
346     } else if (Val.template is<EltTy>()) {
347       EltTy V = Val.template get<EltTy>();
348       Val = new VecTy();
349       Val.template get<VecTy*>()->push_back(V);
350     }
351     return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
352   }
353 };
354 
355 } // end namespace llvm
356 
357 #endif // LLVM_ADT_TINYPTRVECTOR_H
358