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