]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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" | |
223e47cc | 15 | #include "llvm/ADT/SmallVector.h" |
223e47cc LB |
16 | |
17 | namespace 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 | /// | |
25 | template <typename EltTy> | |
26 | class TinyPtrVector { | |
27 | public: | |
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 | ||
223e47cc | 71 | TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) { |
1a4d82fc | 72 | RHS.Val = (EltTy)nullptr; |
223e47cc LB |
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; | |
1a4d82fc | 95 | RHS.Val = (EltTy)nullptr; |
223e47cc LB |
96 | return *this; |
97 | } | |
223e47cc | 98 | |
85aaf69f SL |
99 | /// Constructor from a single element. |
100 | explicit TinyPtrVector(EltTy Elt) : Val(Elt) {} | |
101 | ||
102 | /// Constructor from an ArrayRef. | |
103 | explicit TinyPtrVector(ArrayRef<EltTy> Elts) | |
104 | : Val(new VecTy(Elts.begin(), Elts.end())) {} | |
105 | ||
223e47cc LB |
106 | // implicit conversion operator to ArrayRef. |
107 | operator ArrayRef<EltTy>() const { | |
108 | if (Val.isNull()) | |
1a4d82fc | 109 | return None; |
223e47cc LB |
110 | if (Val.template is<EltTy>()) |
111 | return *Val.getAddrOfPtr1(); | |
112 | return *Val.template get<VecTy*>(); | |
113 | } | |
114 | ||
115 | bool empty() const { | |
116 | // This vector can be empty if it contains no element, or if it | |
117 | // contains a pointer to an empty vector. | |
118 | if (Val.isNull()) return true; | |
119 | if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) | |
120 | return Vec->empty(); | |
121 | return false; | |
122 | } | |
123 | ||
124 | unsigned size() const { | |
125 | if (empty()) | |
126 | return 0; | |
127 | if (Val.template is<EltTy>()) | |
128 | return 1; | |
129 | return Val.template get<VecTy*>()->size(); | |
130 | } | |
131 | ||
132 | typedef const EltTy *const_iterator; | |
133 | typedef EltTy *iterator; | |
134 | ||
135 | iterator begin() { | |
136 | if (Val.template is<EltTy>()) | |
137 | return Val.getAddrOfPtr1(); | |
138 | ||
139 | return Val.template get<VecTy *>()->begin(); | |
140 | ||
141 | } | |
142 | iterator end() { | |
143 | if (Val.template is<EltTy>()) | |
144 | return begin() + (Val.isNull() ? 0 : 1); | |
145 | ||
146 | return Val.template get<VecTy *>()->end(); | |
147 | } | |
148 | ||
149 | const_iterator begin() const { | |
150 | return (const_iterator)const_cast<TinyPtrVector*>(this)->begin(); | |
151 | } | |
152 | ||
153 | const_iterator end() const { | |
154 | return (const_iterator)const_cast<TinyPtrVector*>(this)->end(); | |
155 | } | |
156 | ||
157 | EltTy operator[](unsigned i) const { | |
158 | assert(!Val.isNull() && "can't index into an empty vector"); | |
159 | if (EltTy V = Val.template dyn_cast<EltTy>()) { | |
160 | assert(i == 0 && "tinyvector index out of range"); | |
161 | return V; | |
162 | } | |
163 | ||
164 | assert(i < Val.template get<VecTy*>()->size() && | |
165 | "tinyvector index out of range"); | |
166 | return (*Val.template get<VecTy*>())[i]; | |
167 | } | |
168 | ||
169 | EltTy front() const { | |
170 | assert(!empty() && "vector empty"); | |
171 | if (EltTy V = Val.template dyn_cast<EltTy>()) | |
172 | return V; | |
173 | return Val.template get<VecTy*>()->front(); | |
174 | } | |
175 | ||
176 | EltTy back() const { | |
177 | assert(!empty() && "vector empty"); | |
178 | if (EltTy V = Val.template dyn_cast<EltTy>()) | |
179 | return V; | |
180 | return Val.template get<VecTy*>()->back(); | |
181 | } | |
182 | ||
183 | void push_back(EltTy NewVal) { | |
1a4d82fc | 184 | assert(NewVal && "Can't add a null value"); |
223e47cc LB |
185 | |
186 | // If we have nothing, add something. | |
187 | if (Val.isNull()) { | |
188 | Val = NewVal; | |
189 | return; | |
190 | } | |
191 | ||
192 | // If we have a single value, convert to a vector. | |
193 | if (EltTy V = Val.template dyn_cast<EltTy>()) { | |
194 | Val = new VecTy(); | |
195 | Val.template get<VecTy*>()->push_back(V); | |
196 | } | |
197 | ||
198 | // Add the new value, we know we have a vector. | |
199 | Val.template get<VecTy*>()->push_back(NewVal); | |
200 | } | |
201 | ||
202 | void pop_back() { | |
203 | // If we have a single value, convert to empty. | |
204 | if (Val.template is<EltTy>()) | |
1a4d82fc | 205 | Val = (EltTy)nullptr; |
223e47cc LB |
206 | else if (VecTy *Vec = Val.template get<VecTy*>()) |
207 | Vec->pop_back(); | |
208 | } | |
209 | ||
210 | void clear() { | |
211 | // If we have a single value, convert to empty. | |
212 | if (Val.template is<EltTy>()) { | |
1a4d82fc | 213 | Val = (EltTy)nullptr; |
223e47cc LB |
214 | } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { |
215 | // If we have a vector form, just clear it. | |
216 | Vec->clear(); | |
217 | } | |
218 | // Otherwise, we're already empty. | |
219 | } | |
220 | ||
221 | iterator erase(iterator I) { | |
222 | assert(I >= begin() && "Iterator to erase is out of bounds."); | |
223 | assert(I < end() && "Erasing at past-the-end iterator."); | |
224 | ||
225 | // If we have a single value, convert to empty. | |
226 | if (Val.template is<EltTy>()) { | |
227 | if (I == begin()) | |
1a4d82fc | 228 | Val = (EltTy)nullptr; |
223e47cc LB |
229 | } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { |
230 | // multiple items in a vector; just do the erase, there is no | |
231 | // benefit to collapsing back to a pointer | |
232 | return Vec->erase(I); | |
233 | } | |
234 | return end(); | |
235 | } | |
236 | ||
237 | iterator erase(iterator S, iterator E) { | |
238 | assert(S >= begin() && "Range to erase is out of bounds."); | |
239 | assert(S <= E && "Trying to erase invalid range."); | |
240 | assert(E <= end() && "Trying to erase past the end."); | |
241 | ||
242 | if (Val.template is<EltTy>()) { | |
243 | if (S == begin() && S != E) | |
1a4d82fc | 244 | Val = (EltTy)nullptr; |
223e47cc LB |
245 | } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) { |
246 | return Vec->erase(S, E); | |
247 | } | |
248 | return end(); | |
249 | } | |
250 | ||
251 | iterator insert(iterator I, const EltTy &Elt) { | |
252 | assert(I >= this->begin() && "Insertion iterator is out of bounds."); | |
253 | assert(I <= this->end() && "Inserting past the end of the vector."); | |
254 | if (I == end()) { | |
255 | push_back(Elt); | |
1a4d82fc | 256 | return std::prev(end()); |
223e47cc LB |
257 | } |
258 | assert(!Val.isNull() && "Null value with non-end insert iterator."); | |
259 | if (EltTy V = Val.template dyn_cast<EltTy>()) { | |
260 | assert(I == begin()); | |
261 | Val = Elt; | |
262 | push_back(V); | |
263 | return begin(); | |
264 | } | |
265 | ||
266 | return Val.template get<VecTy*>()->insert(I, Elt); | |
267 | } | |
268 | ||
269 | template<typename ItTy> | |
270 | iterator insert(iterator I, ItTy From, ItTy To) { | |
271 | assert(I >= this->begin() && "Insertion iterator is out of bounds."); | |
272 | assert(I <= this->end() && "Inserting past the end of the vector."); | |
273 | if (From == To) | |
274 | return I; | |
275 | ||
276 | // If we have a single value, convert to a vector. | |
277 | ptrdiff_t Offset = I - begin(); | |
278 | if (Val.isNull()) { | |
1a4d82fc | 279 | if (std::next(From) == To) { |
223e47cc LB |
280 | Val = *From; |
281 | return begin(); | |
282 | } | |
283 | ||
284 | Val = new VecTy(); | |
285 | } else if (EltTy V = Val.template dyn_cast<EltTy>()) { | |
286 | Val = new VecTy(); | |
287 | Val.template get<VecTy*>()->push_back(V); | |
288 | } | |
289 | return Val.template get<VecTy*>()->insert(begin() + Offset, From, To); | |
290 | } | |
291 | }; | |
292 | } // end namespace llvm | |
293 | ||
294 | #endif |