Line data Source code
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 :
22 : namespace 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 : ///
30 : template <typename EltTy>
31 : class TinyPtrVector {
32 : public:
33 : using VecTy = SmallVector<EltTy, 4>;
34 : using value_type = typename VecTy::value_type;
35 : using PtrUnion = PointerUnion<EltTy, VecTy *>;
36 :
37 : private:
38 : PtrUnion Val;
39 :
40 : public:
41 : TinyPtrVector() = default;
42 :
43 1704828822 : ~TinyPtrVector() {
44 33371847 : if (VecTy *V = Val.template dyn_cast<VecTy*>())
45 33371847 : delete V;
46 1704828822 : }
47 384943 :
48 356323803 : TinyPtrVector(const TinyPtrVector &RHS) : Val(RHS.Val) {
49 11061318 : if (VecTy *V = Val.template dyn_cast<VecTy*>())
50 11446001 : Val = new VecTy(*V);
51 364674358 : }
52 1660 :
53 18940 : TinyPtrVector &operator=(const TinyPtrVector &RHS) {
54 8368095 : if (this == &RHS)
55 : return *this;
56 4 : if (RHS.empty()) {
57 2 : this->clear();
58 15657 : return *this;
59 4 : }
60 2 :
61 1 : // Try to squeeze into the single slot. If it won't fit, allocate a copied
62 1 : // vector.
63 1627 : if (Val.template is<EltTy>()) {
64 2 : if (RHS.size() == 1)
65 1 : Val = RHS.front();
66 1 : else
67 2 : Val = new VecTy(*RHS.Val.template get<VecTy*>());
68 1625 : return *this;
69 32 : }
70 32 :
71 : // If we have a full vector allocated, try to re-use it.
72 0 : if (RHS.Val.template is<EltTy>()) {
73 : Val.template get<VecTy*>()->clear();
74 8 : 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 24 : }
80 0 :
81 177549 : TinyPtrVector(TinyPtrVector &&RHS) : Val(RHS.Val) {
82 : RHS.Val = (EltTy)nullptr;
83 0 : }
84 0 :
85 452946 : TinyPtrVector &operator=(TinyPtrVector &&RHS) {
86 452946 : if (this == &RHS)
87 : return *this;
88 37 : if (RHS.empty()) {
89 300162 : this->clear();
90 424226 : 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 16 : if (VecTy *V = Val.template dyn_cast<VecTy*>()) {
97 16 : if (RHS.Val.template is<EltTy>()) {
98 : V->clear();
99 0 : V->push_back(RHS.front());
100 : RHS.Val = (EltTy)nullptr;
101 4 : return *this;
102 : }
103 0 : delete V;
104 : }
105 :
106 28748 : Val = RHS.Val;
107 0 : RHS.Val = (EltTy)nullptr;
108 28736 : return *this;
109 : }
110 0 :
111 144 : TinyPtrVector(std::initializer_list<EltTy> IL)
112 : : Val(IL.size() == 0
113 : ? PtrUnion()
114 : : IL.size() == 1 ? PtrUnion(*IL.begin())
115 156 : : PtrUnion(new VecTy(IL.begin(), IL.end()))) {}
116 :
117 8 : /// Constructor from an ArrayRef.
118 : ///
119 : /// This also is a constructor for individual array elements due to the single
120 : /// element constructor for ArrayRef.
121 : explicit TinyPtrVector(ArrayRef<EltTy> Elts)
122 : : Val(Elts.empty()
123 16 : ? PtrUnion()
124 16 : : Elts.size() == 1
125 : ? PtrUnion(Elts[0])
126 : : PtrUnion(new VecTy(Elts.begin(), Elts.end()))) {}
127 :
128 4 : TinyPtrVector(size_t Count, EltTy Value)
129 : : Val(Count == 0 ? PtrUnion()
130 : : Count == 1 ? PtrUnion(Value)
131 : : PtrUnion(new VecTy(Count, Value))) {}
132 :
133 12 : // implicit conversion operator to ArrayRef.
134 0 : operator ArrayRef<EltTy>() const {
135 15353 : if (Val.isNull())
136 : return None;
137 15353 : if (Val.template is<EltTy>())
138 0 : return *Val.getAddrOfPtr1();
139 : return *Val.template get<VecTy*>();
140 : }
141 :
142 12 : // implicit conversion operator to MutableArrayRef.
143 : operator MutableArrayRef<EltTy>() {
144 139584 : if (Val.isNull())
145 : return None;
146 68219 : if (Val.template is<EltTy>())
147 : return *Val.getAddrOfPtr1();
148 : return *Val.template get<VecTy*>();
149 : }
150 :
151 2 : // Implicit conversion to ArrayRef<U> if EltTy* implicitly converts to U*.
152 99 : template<typename U,
153 : typename std::enable_if<
154 85 : std::is_convertible<ArrayRef<EltTy>, ArrayRef<U>>::value,
155 34 : bool>::type = false>
156 34 : operator ArrayRef<U>() const {
157 : return operator ArrayRef<EltTy>();
158 16 : }
159 :
160 8 : bool empty() const {
161 : // This vector can be empty if it contains no element, or if it
162 : // contains a pointer to an empty vector.
163 432012791 : if (Val.isNull()) return true;
164 : if (VecTy *Vec = Val.template dyn_cast<VecTy*>())
165 21841812 : return Vec->empty();
166 26 : return false;
167 26 : }
168 :
169 20 : unsigned size() const {
170 386 : if (empty())
171 136939 : return 0;
172 3043 : if (Val.template is<EltTy>())
173 21312 : return 1;
174 386 : return Val.template get<VecTy*>()->size();
175 : }
176 16 :
177 : using iterator = EltTy *;
178 9099 : using const_iterator = const EltTy *;
179 : using reverse_iterator = std::reverse_iterator<iterator>;
180 37933 : using const_reverse_iterator = std::reverse_iterator<const_iterator>;
181 17 :
182 9083 : iterator begin() {
183 1865932846 : if (Val.template is<EltTy>())
184 : return Val.getAddrOfPtr1();
185 4 :
186 : return Val.template get<VecTy *>()->begin();
187 : }
188 :
189 : iterator end() {
190 1839589600 : if (Val.template is<EltTy>())
191 1831265613 : return begin() + (Val.isNull() ? 0 : 1);
192 13 :
193 : return Val.template get<VecTy *>()->end();
194 10 : }
195 :
196 5 : const_iterator begin() const {
197 : return (const_iterator)const_cast<TinyPtrVector*>(this)->begin();
198 41749201 : }
199 37733827 :
200 : const_iterator end() const {
201 8 : return (const_iterator)const_cast<TinyPtrVector*>(this)->end();
202 : }
203 8 :
204 : reverse_iterator rbegin() { return reverse_iterator(end()); }
205 17 : reverse_iterator rend() { return reverse_iterator(begin()); }
206 17 :
207 : const_reverse_iterator rbegin() const {
208 8 : return const_reverse_iterator(end());
209 : }
210 4 :
211 : const_reverse_iterator rend() const {
212 : return const_reverse_iterator(begin());
213 : }
214 :
215 : EltTy operator[](unsigned i) const {
216 13 : assert(!Val.isNull() && "can't index into an empty vector");
217 19 : if (EltTy V = Val.template dyn_cast<EltTy>()) {
218 : assert(i == 0 && "tinyvector index out of range");
219 10 : return V;
220 : }
221 5 :
222 : assert(i < Val.template get<VecTy*>()->size() &&
223 8 : "tinyvector index out of range");
224 20 : return (*Val.template get<VecTy*>())[i];
225 1 : }
226 8 :
227 : EltTy front() const {
228 8 : assert(!empty() && "vector empty");
229 1490 : if (EltTy V = Val.template dyn_cast<EltTy>())
230 : return V;
231 1037 : return Val.template get<VecTy*>()->front();
232 11 : }
233 :
234 : EltTy back() const {
235 : assert(!empty() && "vector empty");
236 20 : if (EltTy V = Val.template dyn_cast<EltTy>())
237 : return V;
238 1 : return Val.template get<VecTy*>()->back();
239 : }
240 :
241 55790003 : void push_back(EltTy NewVal) {
242 : assert(NewVal && "Can't add a null value");
243 :
244 : // If we have nothing, add something.
245 55789996 : if (Val.isNull()) {
246 31804163 : Val = NewVal;
247 31804158 : return;
248 : }
249 438616 :
250 : // If we have a single value, convert to a vector.
251 23985840 : if (EltTy V = Val.template dyn_cast<EltTy>()) {
252 21736626 : Val = new VecTy();
253 22175245 : Val.template get<VecTy*>()->push_back(V);
254 432049 : }
255 432049 :
256 : // Add the new value, we know we have a vector.
257 23985840 : Val.template get<VecTy*>()->push_back(NewVal);
258 5 : }
259 6567 :
260 3324 : void pop_back() {
261 3324 : // If we have a single value, convert to empty.
262 : if (Val.template is<EltTy>())
263 : Val = (EltTy)nullptr;
264 : else if (VecTy *Vec = Val.template get<VecTy*>())
265 6567 : Vec->pop_back();
266 : }
267 422703 :
268 : void clear() {
269 : // If we have a single value, convert to empty.
270 603406809 : if (Val.template is<EltTy>()) {
271 422703 : Val = (EltTy)nullptr;
272 1491434 : } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
273 421022 : // If we have a vector form, just clear it.
274 : Vec->clear();
275 : }
276 1 : // Otherwise, we're already empty.
277 1681 : }
278 297804 :
279 47541 : iterator erase(iterator I) {
280 1439 : assert(I >= begin() && "Iterator to erase is out of bounds.");
281 : assert(I < end() && "Erasing at past-the-end iterator.");
282 :
283 1681 : // If we have a single value, convert to empty.
284 45874 : if (Val.template is<EltTy>()) {
285 47491 : if (I == begin())
286 : Val = (EltTy)nullptr;
287 1679 : } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
288 : // multiple items in a vector; just do the erase, there is no
289 3296 : // benefit to collapsing back to a pointer
290 2629 : return Vec->erase(I);
291 950 : }
292 : return end();
293 : }
294 :
295 2917 : iterator erase(iterator S, iterator E) {
296 306 : assert(S >= begin() && "Range to erase is out of bounds.");
297 340 : assert(S <= E && "Trying to erase invalid range.");
298 : assert(E <= end() && "Trying to erase past the end.");
299 :
300 499 : if (Val.template is<EltTy>()) {
301 2780 : if (S == begin() && S != E)
302 2 : Val = (EltTy)nullptr;
303 104 : } else if (VecTy *Vec = Val.template dyn_cast<VecTy*>()) {
304 68 : return Vec->erase(S, E);
305 : }
306 2 : return end();
307 : }
308 39 :
309 0 : iterator insert(iterator I, const EltTy &Elt) {
310 : assert(I >= this->begin() && "Insertion iterator is out of bounds.");
311 39 : assert(I <= this->end() && "Inserting past the end of the vector.");
312 39 : if (I == end()) {
313 : push_back(Elt);
314 : return std::prev(end());
315 74 : }
316 : assert(!Val.isNull() && "Null value with non-end insert iterator.");
317 : if (EltTy V = Val.template dyn_cast<EltTy>()) {
318 : assert(I == begin());
319 : Val = Elt;
320 : push_back(V);
321 : return begin();
322 118 : }
323 36 :
324 : return Val.template get<VecTy*>()->insert(I, Elt);
325 : }
326 :
327 : template<typename ItTy>
328 269992046 : iterator insert(iterator I, ItTy From, ItTy To) {
329 : assert(I >= this->begin() && "Insertion iterator is out of bounds.");
330 : assert(I <= this->end() && "Inserting past the end of the vector.");
331 269992046 : if (From == To)
332 : return I;
333 :
334 : // If we have a single value, convert to a vector.
335 4017784 : ptrdiff_t Offset = I - begin();
336 4030356 : if (Val.isNull()) {
337 3697995 : if (std::next(From) == To) {
338 3270149 : Val = *From;
339 13138 : return begin();
340 : }
341 :
342 427846 : Val = new VecTy();
343 320034 : } else if (EltTy V = Val.template dyn_cast<EltTy>()) {
344 145225 : Val = new VecTy();
345 144734 : Val.template get<VecTy*>()->push_back(V);
346 0 : }
347 1495556 : return Val.template get<VecTy*>()->insert(begin() + Offset, From, To);
348 286 : }
349 0 : };
350 40 :
351 205 : } // end namespace llvm
352 0 :
353 0 : #endif // LLVM_ADT_TINYPTRVECTOR_H
|
