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