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 
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(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(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