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