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