TinyPtrVector.h revision 0b1bcbf6b87f19402d8aef1ef9f6e527a07de9d4 
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/SmallVector.h"
15#include "llvm/ADT/PointerUnion.h"
16#include "llvm/Support/Compiler.h"
17
18namespace llvm {
19
20/// TinyPtrVector - This class is specialized for cases where there are
21/// normally 0 or 1 element in a vector, but is general enough to go beyond that
22/// when required.
23///
24/// NOTE: This container doesn't allow you to store a null pointer into it.
25///
26template <typename EltTy>
27class TinyPtrVector {
28public:
29  typedef llvm::SmallVector<EltTy, 4> VecTy;
30  typedef typename VecTy::value_type value_type;
31
32  llvm::PointerUnion<EltTy, VecTy*> Val;
33
34  TinyPtrVector() {}
35  ~TinyPtrVector() {
36    if (VecTy *V = Val.template dyn_cast<VecTy*>())
37      delete V;
38  }
39
40  TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
41    if (VecTy *V = Val.template dyn_cast<VecTy*>())
42      Val = new VecTy(*V);
43  }
44  TinyPtrVector &operator=(const TinyPtrVector &RHS) {
45    if (this == &RHS)
46      return *this;
47    if (RHS.empty()) {
48      this->clear();
49      return *this;
50    }
51
52    // Try to squeeze into the single slot. If it won't fit, allocate a copied
53    // vector.
54    if (Val.template is<EltTy>()) {
55      if (RHS.size() == 1)
56        Val = RHS.front();
57      else
58        Val = new VecTy(*RHS.Val.template get<VecTy*>());
59      return *this;
60    }
61
62    // If we have a full vector allocated, try to re-use it.
63    if (RHS.Val.template is<EltTy>()) {
64      Val.template get<VecTy*>()->clear();
65      Val.template get<VecTy*>()->push_back(RHS.front());
66    } else {
67      *Val.template get<VecTy*>() = *RHS.Val.template get<VecTy*>();
68    }
69    return *this;
70  }
71
72#if LLVM_USE_RVALUE_REFERENCES
73  TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
74    RHS.Val = (EltTy)0;
75  }
76  TinyPtrVector &operator=(TinyPtrVector &&RHS) {
77    if (this == &RHS)
78      return *this;
79    if (RHS.empty()) {
80      this->clear();
81      return *this;
82    }
83
84    // If this vector has been allocated on the heap, re-use it if cheap. If it
85    // would require more copying, just delete it and we'll steal the other
86    // side.
87    if (VecTy *V = Val.template dyn_cast<VecTy*>()) {
88      if (RHS.Val.template is<EltTy>()) {
89        V->clear();
90        V->push_back(RHS.front());
91        return *this;
92      }
93      delete V;
94    }
95
96    Val = RHS.Val;
97    RHS.Val = (EltTy)0;
98    return *this;
99  }
100#endif
101
102  // implicit conversion operator to ArrayRef.
103  operator ArrayRef<EltTy>() const {
104    if (Val.isNull())
105      return ArrayRef<EltTy>();
106    if (Val.template is<EltTy>())
107      return *Val.getAddrOfPtr1();
108    return *Val.template get<VecTy*>();
109  }
110
111  bool empty() const {
112    // This vector can be empty if it contains no element, or if it
113    // contains a pointer to an empty vector.
114    if (Val.isNull()) return true;
115    if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
116      return Vec->empty();
117    return false;
118  }
119
120  unsigned size() const {
121    if (empty())
122      return 0;
123    if (Val.template is<EltTy>())
124      return 1;
125    return Val.template get<VecTy*>()->size();
126  }
127
128  typedef const EltTy *const_iterator;
129  typedef EltTy *iterator;
130
131  iterator begin() {
132    if (Val.template is<EltTy>())
133      return Val.getAddrOfPtr1();
134
135    return Val.template get<VecTy *>()->begin();
136
137  }
138  iterator end() {
139    if (Val.template is<EltTy>())
140      return begin() + (Val.isNull() ? 0 : 1);
141
142    return Val.template get<VecTy *>()->end();
143  }
144
145  const_iterator begin() const {
146    return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
147  }
148
149  const_iterator end() const {
150    return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
151  }
152
153  EltTy operator[](unsigned i) const {
154    assert(!Val.isNull() && "can't index into an empty vector");
155    if (EltTy V = Val.template dyn_cast<EltTy>()) {
156      assert(i == 0 && "tinyvector index out of range");
157      return V;
158    }
159
160    assert(i < Val.template get<VecTy*>()->size() &&
161           "tinyvector index out of range");
162    return (*Val.template get<VecTy*>())[i];
163  }
164
165  EltTy front() const {
166    assert(!empty() && "vector empty");
167    if (EltTy V = Val.template dyn_cast<EltTy>())
168      return V;
169    return Val.template get<VecTy*>()->front();
170  }
171
172  EltTy back() const {
173    assert(!empty() && "vector empty");
174    if (EltTy V = Val.template dyn_cast<EltTy>())
175      return V;
176    return Val.template get<VecTy*>()->back();
177  }
178
179  void push_back(EltTy NewVal) {
180    assert(NewVal != 0 && "Can't add a null value");
181
182    // If we have nothing, add something.
183    if (Val.isNull()) {
184      Val = NewVal;
185      return;
186    }
187
188    // If we have a single value, convert to a vector.
189    if (EltTy V = Val.template dyn_cast<EltTy>()) {
190      Val = new VecTy();
191      Val.template get<VecTy*>()->push_back(V);
192    }
193
194    // Add the new value, we know we have a vector.
195    Val.template get<VecTy*>()->push_back(NewVal);
196  }
197
198  void pop_back() {
199    // If we have a single value, convert to empty.
200    if (Val.template is<EltTy>())
201      Val = (EltTy)0;
202    else if (VecTy *Vec = Val.template get<VecTy*>())
203      Vec->pop_back();
204  }
205
206  void clear() {
207    // If we have a single value, convert to empty.
208    if (Val.template is<EltTy>()) {
209      Val = (EltTy)0;
210    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
211      // If we have a vector form, just clear it.
212      Vec->clear();
213    }
214    // Otherwise, we're already empty.
215  }
216
217  iterator erase(iterator I) {
218    assert(I >= begin() && "Iterator to erase is out of bounds.");
219    assert(I < end() && "Erasing at past-the-end iterator.");
220
221    // If we have a single value, convert to empty.
222    if (Val.template is<EltTy>()) {
223      if (I == begin())
224        Val = (EltTy)0;
225    } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
226      // multiple items in a vector; just do the erase, there is no
227      // benefit to collapsing back to a pointer
228      return Vec->erase(I);
229    }
230    return end();
231  }
232};
233} // end namespace llvm
234
235#endif
236