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
17namespace 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///
25template <typename EltTy>
26class TinyPtrVector {
27public:
28  typedef llvm::SmallVector<EltTy, 4> VecTy;
29  typedef typename VecTy::value_type value_type;
30  typedef llvm::PointerUnion<EltTy, VecTy *> PtrUnion;
31
32private:
33  PtrUnion Val;
34
35public:
36  TinyPtrVector() {}
37  ~TinyPtrVector() {
38    if (VecTy *V = Val.template dyn_cast<VecTy*>())
39      delete V;
40  }
41
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
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.
106  explicit TinyPtrVector(ArrayRef<EltTy> Elts)
107      : Val(Elts.empty()
108                ? PtrUnion()
109                : Elts.size() == 1
110                      ? PtrUnion(Elts[0])
111                      : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
112
113  TinyPtrVector(size_t Count, EltTy Value)
114      : Val(Count == 0 ? PtrUnion()
115                       : Count == 1 ? PtrUnion(Value)
116                                    : PtrUnion(new VecTy(Count, Value))) {}
117
118  // implicit conversion operator to ArrayRef.
119  operator ArrayRef<EltTy>() const {
120    if (Val.isNull())
121      return None;
122    if (Val.template is<EltTy>())
123      return *Val.getAddrOfPtr1();
124    return *Val.template get<VecTy*>();
125  }
126
127  // implicit conversion operator to MutableArrayRef.
128  operator MutableArrayRef<EltTy>() {
129    if (Val.isNull())
130      return None;
131    if (Val.template is<EltTy>())
132      return *Val.getAddrOfPtr1();
133    return *Val.template get<VecTy*>();
134  }
135
136  // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
137  template<typename U,
138           typename std::enable_if<
139               std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
140               bool>::type = false>
141  operator ArrayRef<U>() const {
142    return operator ArrayRef<EltTy>();
143  }
144
145  bool empty() const {
146    // This vector can be empty if it contains no element, or if it
147    // contains a pointer to an empty vector.
148    if (Val.isNull()) return true;
149    if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
150      return Vec->empty();
151    return false;
152  }
153
154  unsigned size() const {
155    if (empty())
156      return 0;
157    if (Val.template is<EltTy>())
158      return 1;
159    return Val.template get<VecTy*>()->size();
160  }
161
162  typedef EltTy *iterator;
163  typedef const EltTy *const_iterator;
164  typedef std::reverse_iterator<iterator> reverse_iterator;
165  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
166
167  iterator begin() {
168    if (Val.template is<EltTy>())
169      return Val.getAddrOfPtr1();
170
171    return Val.template get<VecTy *>()->begin();
172  }
173  iterator end() {
174    if (Val.template is<EltTy>())
175      return begin() + (Val.isNull() ? 0 : 1);
176
177    return Val.template get<VecTy *>()->end();
178  }
179
180  const_iterator begin() const {
181    return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
182  }
183
184  const_iterator end() const {
185    return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
186  }
187
188  reverse_iterator rbegin() { return reverse_iterator(end()); }
189  reverse_iterator rend() { return reverse_iterator(begin()); }
190  const_reverse_iterator rbegin() const {
191    return const_reverse_iterator(end());
192  }
193  const_reverse_iterator rend() const {
194    return const_reverse_iterator(begin());
195  }
196
197  EltTy operator[](unsigned i) const {
198    assert(!Val.isNull() && "can't index into an empty vector");
199    if (EltTy V = Val.template dyn_cast<EltTy>()) {
200      assert(i == 0 && "tinyvector index out of range");
201      return V;
202    }
203
204    assert(i < Val.template get<VecTy*>()->size() &&
205           "tinyvector index out of range");
206    return (*Val.template get<VecTy*>())[i];
207  }
208
209  EltTy front() const {
210    assert(!empty() && "vector empty");
211    if (EltTy V = Val.template dyn_cast<EltTy>())
212      return V;
213    return Val.template get<VecTy*>()->front();
214  }
215
216  EltTy back() const {
217    assert(!empty() && "vector empty");
218    if (EltTy V = Val.template dyn_cast<EltTy>())
219      return V;
220    return Val.template get<VecTy*>()->back();
221  }
222
223  void push_back(EltTy NewVal) {
224    assert(NewVal && "Can't add a null value");
225
226    // If we have nothing, add something.
227    if (Val.isNull()) {
228      Val = NewVal;
229      return;
230    }
231
232    // If we have a single value, convert to a vector.
233    if (EltTy V = Val.template dyn_cast<EltTy>()) {
234      Val = new VecTy();
235      Val.template get<VecTy*>()->push_back(V);
236    }
237
238    // Add the new value, we know we have a vector.
239    Val.template get<VecTy*>()->push_back(NewVal);
240  }
241
242  void pop_back() {
243    // If we have a single value, convert to empty.
244    if (Val.template is<EltTy>())
245      Val = (EltTy)nullptr;
246    else if (VecTy *Vec = Val.template get<VecTy*>())
247      Vec->pop_back();
248  }
249
250  void clear() {
251    // If we have a single value, convert to empty.
252    if (Val.template is<EltTy>()) {
253      Val = (EltTy)nullptr;
254    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
255      // If we have a vector form, just clear it.
256      Vec->clear();
257    }
258    // Otherwise, we're already empty.
259  }
260
261  iterator erase(iterator I) {
262    assert(I >= begin() && "Iterator to erase is out of bounds.");
263    assert(I < end() && "Erasing at past-the-end iterator.");
264
265    // If we have a single value, convert to empty.
266    if (Val.template is<EltTy>()) {
267      if (I == begin())
268        Val = (EltTy)nullptr;
269    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
270      // multiple items in a vector; just do the erase, there is no
271      // benefit to collapsing back to a pointer
272      return Vec->erase(I);
273    }
274    return end();
275  }
276
277  iterator erase(iterator S, iterator E) {
278    assert(S >= begin() && "Range to erase is out of bounds.");
279    assert(S <= E && "Trying to erase invalid range.");
280    assert(E <= end() && "Trying to erase past the end.");
281
282    if (Val.template is<EltTy>()) {
283      if (S == begin() && S != E)
284        Val = (EltTy)nullptr;
285    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
286      return Vec->erase(S, E);
287    }
288    return end();
289  }
290
291  iterator insert(iterator I, const EltTy &Elt) {
292    assert(I >= this->begin() && "Insertion iterator is out of bounds.");
293    assert(I <= this->end() && "Inserting past the end of the vector.");
294    if (I == end()) {
295      push_back(Elt);
296      return std::prev(end());
297    }
298    assert(!Val.isNull() && "Null value with non-end insert iterator.");
299    if (EltTy V = Val.template dyn_cast<EltTy>()) {
300      assert(I == begin());
301      Val = Elt;
302      push_back(V);
303      return begin();
304    }
305
306    return Val.template get<VecTy*>()->insert(I, Elt);
307  }
308
309  template<typename ItTy>
310  iterator insert(iterator I, ItTy From, ItTy To) {
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 (From == To)
314      return I;
315
316    // If we have a single value, convert to a vector.
317    ptrdiff_t Offset = I - begin();
318    if (Val.isNull()) {
319      if (std::next(From) == To) {
320        Val = *From;
321        return begin();
322      }
323
324      Val = new VecTy();
325    } else if (EltTy V = Val.template dyn_cast<EltTy>()) {
326      Val = new VecTy();
327      Val.template get<VecTy*>()->push_back(V);
328    }
329    return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
330  }
331};
332} // end namespace llvm
333
334#endif
335