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