Line data Source code
1 : //===- llvm/ADT/SmallVector.h - 'Normally small' 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 : // This file defines the SmallVector class.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #ifndef LLVM_ADT_SMALLVECTOR_H
15 : #define LLVM_ADT_SMALLVECTOR_H
16 :
17 : #include "llvm/ADT/iterator_range.h"
18 : #include "llvm/Support/AlignOf.h"
19 : #include "llvm/Support/Compiler.h"
20 : #include "llvm/Support/MathExtras.h"
21 : #include "llvm/Support/MemAlloc.h"
22 : #include "llvm/Support/type_traits.h"
23 : #include "llvm/Support/ErrorHandling.h"
24 : #include <algorithm>
25 : #include <cassert>
26 : #include <cstddef>
27 : #include <cstdlib>
28 : #include <cstring>
29 : #include <initializer_list>
30 : #include <iterator>
31 : #include <memory>
32 : #include <new>
33 : #include <type_traits>
34 : #include <utility>
35 :
36 : namespace llvm {
37 :
38 : /// This is all the non-templated stuff common to all SmallVectors.
39 : class SmallVectorBase {
40 : protected:
41 : void *BeginX;
42 : unsigned Size = 0, Capacity;
43 :
44 : SmallVectorBase() = delete;
45 : SmallVectorBase(void *FirstEl, size_t Capacity)
46 9391524883 : : BeginX(FirstEl), Capacity(Capacity) {}
47 :
48 : /// This is an implementation of the grow() method which only works
49 : /// on POD-like data types and is out of line to reduce code duplication.
50 : void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize);
51 :
52 : public:
53 13599661468 : size_t size() const { return Size; }
54 3001793850 : size_t capacity() const { return Capacity; }
55 :
56 29394197 : LLVM_NODISCARD bool empty() const { return !Size; }
57 :
58 : /// Set the array size to \p N, which the current array must have enough
59 : /// capacity for.
60 : ///
61 : /// This does not construct or destroy any elements in the vector.
62 : ///
63 : /// Clients can use this in conjunction with capacity() to write past the end
64 : /// of the buffer when they know that more elements are available, and only
65 : /// update the size later. This avoids the cost of value initializing elements
66 : /// which will only be overwritten.
67 0 : void set_size(size_t Size) {
68 : assert(Size <= capacity());
69 20863796217 : this->Size = Size;
70 0 : }
71 : };
72 :
73 : /// Figure out the offset of the first element.
74 : template <class T, typename = void> struct SmallVectorAlignmentAndSize {
75 : AlignedCharArrayUnion<SmallVectorBase> Base;
76 : AlignedCharArrayUnion<T> FirstEl;
77 : };
78 :
79 : /// This is the part of SmallVectorTemplateBase which does not depend on whether
80 : /// the type T is a POD. The extra dummy template argument is used by ArrayRef
81 : /// to avoid unnecessarily requiring T to be complete.
82 : template <typename T, typename = void>
83 : class SmallVectorTemplateCommon : public SmallVectorBase {
84 : /// Find the address of the first element. For this pointer math to be valid
85 : /// with small-size of 0 for T with lots of alignment, it's important that
86 : /// SmallVectorStorage is properly-aligned even for small-size of 0.
87 : void *getFirstEl() const {
88 : return const_cast<void *>(reinterpret_cast<const void *>(
89 : reinterpret_cast<const char *>(this) +
90 3935394730 : offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
91 : }
92 : // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
93 :
94 : protected:
95 : SmallVectorTemplateCommon(size_t Size)
96 : : SmallVectorBase(getFirstEl(), Size) {}
97 :
98 : void grow_pod(size_t MinCapacity, size_t TSize) {
99 123687022 : SmallVectorBase::grow_pod(getFirstEl(), MinCapacity, TSize);
100 : }
101 :
102 : /// Return true if this is a smallvector which has not had dynamic
103 : /// memory allocated for it.
104 699213973 : bool isSmall() const { return BeginX == getFirstEl(); }
105 :
106 : /// Put this vector in a state of being small.
107 : void resetToSmall() {
108 869233 : BeginX = getFirstEl();
109 869233 : Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
110 : }
111 :
112 : public:
113 : using size_type = size_t;
114 : using difference_type = ptrdiff_t;
115 : using value_type = T;
116 : using iterator = T *;
117 : using const_iterator = const T *;
118 :
119 : using const_reverse_iterator = std::reverse_iterator<const_iterator>;
120 : using reverse_iterator = std::reverse_iterator<iterator>;
121 :
122 : using reference = T &;
123 : using const_reference = const T &;
124 : using pointer = T *;
125 : using const_pointer = const T *;
126 :
127 : // forward iterator creation methods.
128 : LLVM_ATTRIBUTE_ALWAYS_INLINE
129 23456423425 : iterator begin() { return (iterator)this->BeginX; }
130 : LLVM_ATTRIBUTE_ALWAYS_INLINE
131 11942194327 : const_iterator begin() const { return (const_iterator)this->BeginX; }
132 : LLVM_ATTRIBUTE_ALWAYS_INLINE
133 37471022239 : iterator end() { return begin() + size(); }
134 : LLVM_ATTRIBUTE_ALWAYS_INLINE
135 4194512428 : const_iterator end() const { return begin() + size(); }
136 :
137 : // reverse iterator creation methods.
138 : reverse_iterator rbegin() { return reverse_iterator(end()); }
139 : const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
140 0 : reverse_iterator rend() { return reverse_iterator(begin()); }
141 0 : const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
142 :
143 : size_type size_in_bytes() const { return size() * sizeof(T); }
144 : size_type max_size() const { return size_type(-1) / sizeof(T); }
145 :
146 14 : size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
147 :
148 : /// Return a pointer to the vector's buffer, even if empty().
149 0 : pointer data() { return pointer(begin()); }
150 : /// Return a pointer to the vector's buffer, even if empty().
151 0 : const_pointer data() const { return const_pointer(begin()); }
152 :
153 : LLVM_ATTRIBUTE_ALWAYS_INLINE
154 : reference operator[](size_type idx) {
155 : assert(idx < size());
156 4855991006 : return begin()[idx];
157 : }
158 : LLVM_ATTRIBUTE_ALWAYS_INLINE
159 : const_reference operator[](size_type idx) const {
160 : assert(idx < size());
161 14309188750 : return begin()[idx];
162 : }
163 :
164 0 : reference front() {
165 : assert(!empty());
166 0 : return begin()[0];
167 : }
168 0 : const_reference front() const {
169 : assert(!empty());
170 0 : return begin()[0];
171 : }
172 0 :
173 : reference back() {
174 0 : assert(!empty());
175 1813549163 : return end()[-1];
176 0 : }
177 : const_reference back() const {
178 0 : assert(!empty());
179 1109614848 : return end()[-1];
180 0 : }
181 : };
182 0 :
183 1105698920 : /// SmallVectorTemplateBase<isPodLike = false> - This is where we put method
184 0 : /// implementations that are designed to work with non-POD-like T's.
185 : template <typename T, bool isPodLike>
186 0 : class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
187 102930162 : protected:
188 : SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
189 :
190 9771194 : static void destroy_range(T *S, T *E) {
191 1050868425 : while (S != E) {
192 329705835 : --E;
193 11093185 : E->~T();
194 : }
195 15601032 : }
196 6266 :
197 65541 : /// Move the range [I, E) into the uninitialized memory starting with "Dest",
198 1406446 : /// constructing elements as needed.
199 203578594 : template<typename It1, typename It2>
200 136987202 : static void uninitialized_move(It1 I, It1 E, It2 Dest) {
201 10511327 : std::uninitialized_copy(std::make_move_iterator(I),
202 608869 : std::make_move_iterator(E), Dest);
203 16064288 : }
204 1580395 :
205 922117 : /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
206 55857 : /// constructing elements as needed.
207 5563700 : template<typename It1, typename It2>
208 744396 : static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
209 2653906 : std::uninitialized_copy(I, E, Dest);
210 1516247 : }
211 332557 :
212 2381 : /// Grow the allocated memory (without initializing new elements), doubling
213 590800 : /// the size of the allocated memory. Guarantees space for at least one more
214 590692 : /// element, or MinSize more elements if specified.
215 920868 : void grow(size_t MinSize = 0);
216 138667 :
217 396413 : public:
218 187471869 : void push_back(const T &Elt) {
219 187804815 : if (LLVM_UNLIKELY(this->size() >= this->capacity()))
220 1422633 : this->grow();
221 27456462 : ::new ((void*) this->end()) T(Elt);
222 123606963 : this->set_size(this->size() + 1);
223 187214123 : }
224 96990440 :
225 112106131 : void push_back(T &&Elt) {
226 16039683 : if (LLVM_UNLIKELY(this->size() >= this->capacity()))
227 1051056 : this->grow();
228 99958750 : ::new ((void*) this->end()) T(::std::move(Elt));
229 110249982 : this->set_size(this->size() + 1);
230 47007894 : }
231 34742039 :
232 3304217 : void pop_back() {
233 160352803 : this->set_size(this->size() - 1);
234 168727198 : this->end()->~T();
235 36927279 : }
236 141850616 : };
237 181110359 :
238 178668024 : // Define this out-of-line to dissuade the C++ compiler from inlining it.
239 20741 : template <typename T, bool isPodLike>
240 3183221 : void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
241 368991422 : if (MinSize > UINT32_MAX)
242 365465903 : report_bad_alloc_error("SmallVector capacity overflow during allocation");
243 1141452 :
244 4184566 : // Always grow, even from zero.
245 37501698 : size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
246 33703686 : NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX));
247 8052319 : T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
248 3906314 :
249 5628171 : // Move the elements over.
250 2065102 : this->uninitialized_move(this->begin(), this->end(), NewElts);
251 66994 :
252 1994144 : // Destroy the original elements.
253 7517542 : destroy_range(this->begin(), this->end());
254 5090595 :
255 3370384 : // If this wasn't grown from the inline copy, deallocate the old space.
256 12239956 : if (!this->isSmall())
257 11931168 : free(this->begin());
258 504917 :
259 13382372 : this->BeginX = NewElts;
260 3288361 : this->Capacity = NewCapacity;
261 4525435 : }
262 2796521 :
263 1792460 :
264 2892155 : /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method
265 3308737 : /// implementations that are designed to work with POD-like T's.
266 1495515 : template <typename T>
267 4651463 : class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
268 4554228 : protected:
269 4351404 : SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
270 1489376 :
271 2357182 : // No need to do a destroy loop for POD's.
272 840939 : static void destroy_range(T *, T *) {}
273 695552 :
274 670006 : /// Move the range [I, E) onto the uninitialized memory
275 1693715 : /// starting with "Dest", constructing elements into it as needed.
276 2180 : template<typename It1, typename It2>
277 1040091 : static void uninitialized_move(It1 I, It1 E, It2 Dest) {
278 2536228 : // Just do a copy.
279 922440 : uninitialized_copy(I, E, Dest);
280 49786 : }
281 2325074 :
282 1695064 : /// Copy the range [I, E) onto the uninitialized memory
283 1828182 : /// starting with "Dest", constructing elements into it as needed.
284 1729238 : template<typename It1, typename It2>
285 3516598 : static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
286 4258 : // Arbitrary iterator types; just use the basic implementation.
287 2522475 : std::uninitialized_copy(I, E, Dest);
288 2191291 : }
289 1573453 :
290 306413 : /// Copy the range [I, E) onto the uninitialized memory
291 217236 : /// starting with "Dest", constructing elements into it as needed.
292 2415858 : template <typename T1, typename T2>
293 2462626 : static void uninitialized_copy(
294 129426 : T1 *I, T1 *E, T2 *Dest,
295 1125053 : typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,
296 203535 : T2>::value>::type * = nullptr) {
297 2631194 : // Use memcpy for PODs iterated by pointers (which includes SmallVector
298 2428297 : // iterators): std::uninitialized_copy optimizes to memmove, but we can
299 2429210 : // use memcpy here. Note that I and E are iterators and thus might be
300 77135 : // invalid for memcpy if they are equal.
301 1699430134 : if (I != E)
302 1712570143 : memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
303 349879 : }
304 74779 :
305 194725 : /// Double the size of the allocated memory, guaranteeing space for at
306 14679 : /// least one more element or MinSize if specified.
307 123759 : void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
308 2520989 :
309 7145210 : public:
310 18674857225 : void push_back(const T &Elt) {
311 18659730721 : if (LLVM_UNLIKELY(this->size() >= this->capacity()))
312 2468807 : this->grow();
313 18659925154 : memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
314 18657486863 : this->set_size(this->size() + 1);
315 18657467399 : }
316 210093947 :
317 242539535 : void pop_back() { this->set_size(this->size() - 1); }
318 34206880 : };
319 242443889 :
320 210156239 : /// This class consists of common code factored out of the SmallVector class to
321 242443869 : /// reduce code duplication based on the SmallVector 'N' template parameter.
322 2177636318 : template <typename T>
323 2177630617 : class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
324 2320 : using SuperClass = SmallVectorTemplateBase<T, isPodLike<T>::value>;
325 2145460401 :
326 2145566083 : public:
327 2145567094 : using iterator = typename SuperClass::iterator;
328 15231834434 : using const_iterator = typename SuperClass::const_iterator;
329 15281395325 : using size_type = typename SuperClass::size_type;
330 11131 :
331 15232060169 : protected:
332 15882286119 : // Default ctor - Initialize to empty.
333 15882296830 : explicit SmallVectorImpl(unsigned N)
334 363323316 : : SmallVectorTemplateBase<T, isPodLike<T>::value>(N) {}
335 1024828839 :
336 651920447 : public:
337 1015305918 : SmallVectorImpl(const SmallVectorImpl &) = delete;
338 392645678 :
339 396451033 : ~SmallVectorImpl() {
340 167907872 : // Subclass has already destructed this vector's elements.
341 198992358 : // If this wasn't grown from the inline copy, deallocate the old space.
342 304352748 : if (!this->isSmall())
343 1354654118 : free(this->begin());
344 1345881086 : }
345 209821518 :
346 1256289511 : void clear() {
347 1238010095 : this->destroy_range(this->begin(), this->end());
348 1389817308 : this->Size = 0;
349 398288335 : }
350 314668344 :
351 137793932 : void resize(size_type N) {
352 380397607 : if (N < this->size()) {
353 332893870 : this->destroy_range(this->begin()+N, this->end());
354 587619383 : this->set_size(N);
355 242272517 : } else if (N > this->size()) {
356 254811081 : if (this->capacity() < N)
357 317173205 : this->grow(N);
358 785810332 : for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
359 851167508 : new (&*I) T();
360 1448676157 : this->set_size(N);
361 161657004 : }
362 151677463 : }
363 95353458 :
364 123182935 : void resize(size_type N, const T &NV) {
365 352775598 : if (N < this->size()) {
366 1823734859 : this->destroy_range(this->begin()+N, this->end());
367 284005487 : this->set_size(N);
368 394884416 : } else if (N > this->size()) {
369 302678419 : if (this->capacity() < N)
370 694860135 : this->grow(N);
371 176556113 : std::uninitialized_fill(this->end(), this->begin()+N, NV);
372 197151507 : this->set_size(N);
373 46169489 : }
374 47597174 : }
375 63283913 :
376 318962425 : void reserve(size_type N) {
377 249485562 : if (this->capacity() < N)
378 561381956 : this->grow(N);
379 320992075 : }
380 280926840 :
381 135200114 : LLVM_NODISCARD T pop_back_val() {
382 136148657 : T Result = ::std::move(this->back());
383 83913360 : this->pop_back();
384 346446622 : return Result;
385 73459578 : }
386 100414818 :
387 217482765 : void swap(SmallVectorImpl &RHS);
388 191946375 :
389 122682624 : /// Add the specified range to the end of the SmallVector.
390 344300675 : template <typename in_iter,
391 394689283 : typename = typename std::enable_if<std::is_convertible<
392 440390603 : typename std::iterator_traits<in_iter>::iterator_category,
393 188766993 : std::input_iterator_tag>::value>::type>
394 1427017023 : void append(in_iter in_start, in_iter in_end) {
395 1431912753 : size_type NumInputs = std::distance(in_start, in_end);
396 463382822 : // Grow allocated space if needed.
397 1349353811 : if (NumInputs > this->capacity() - this->size())
398 301065521 : this->grow(this->size()+NumInputs);
399 269261338 :
400 392442338 : // Copy the new elements over.
401 404070193 : this->uninitialized_copy(in_start, in_end, this->end());
402 2501489031 : this->set_size(this->size() + NumInputs);
403 1346283481 : }
404 661749712 :
405 356593427 : /// Add the specified range to the end of the SmallVector.
406 281082304 : void append(size_type NumInputs, const T &Elt) {
407 203385480 : // Grow allocated space if needed.
408 231150910 : if (NumInputs > this->capacity() - this->size())
409 83985534 : this->grow(this->size()+NumInputs);
410 75944800 :
411 100309302 : // Copy the new elements over.
412 403135200 : std::uninitialized_fill_n(this->end(), NumInputs, Elt);
413 409394524 : this->set_size(this->size() + NumInputs);
414 117779638 : }
415 369463929 :
416 364780281 : void append(std::initializer_list<T> IL) {
417 337024728 : append(IL.begin(), IL.end());
418 27130696 : }
419 140730428 :
420 846812007 : // FIXME: Consider assigning over existing elements, rather than clearing &
421 380767383 : // re-initializing them - for all assign(...) variants.
422 229815953 :
423 236585712 : void assign(size_type NumElts, const T &Elt) {
424 291088009 : clear();
425 210854843 : if (this->capacity() < NumElts)
426 132829406 : this->grow(NumElts);
427 211542512 : this->set_size(NumElts);
428 216702836 : std::uninitialized_fill(this->begin(), this->end(), Elt);
429 233869104 : }
430 55121933 :
431 96115195 : template <typename in_iter,
432 205740535 : typename = typename std::enable_if<std::is_convertible<
433 165033330 : typename std::iterator_traits<in_iter>::iterator_category,
434 119136197 : std::input_iterator_tag>::value>::type>
435 200925680 : void assign(in_iter in_start, in_iter in_end) {
436 213046586 : clear();
437 177196559 : append(in_start, in_end);
438 147966981 : }
439 251278445 :
440 250583945 : void assign(std::initializer_list<T> IL) {
441 152441879 : clear();
442 428498174 : append(IL);
443 304650101 : }
444 236848239 :
445 202855454 : iterator erase(const_iterator CI) {
446 259794108 : // Just cast away constness because this is a non-const member function.
447 231109582 : iterator I = const_cast<iterator>(CI);
448 70517414 :
449 65916294 : assert(I >= this->begin() && "Iterator to erase is out of bounds.");
450 160634597 : assert(I < this->end() && "Erasing at past-the-end iterator.");
451 174539510 :
452 112495795 : iterator N = I;
453 252938864 : // Shift all elts down one.
454 261997032 : std::move(I+1, this->end(), I);
455 264985759 : // Drop the last elt.
456 251142627 : this->pop_back();
457 159138144 : return(N);
458 168432832 : }
459 176620856 :
460 131160903 : iterator erase(const_iterator CS, const_iterator CE) {
461 110395645 : // Just cast away constness because this is a non-const member function.
462 321124635 : iterator S = const_cast<iterator>(CS);
463 217110325 : iterator E = const_cast<iterator>(CE);
464 63546060 :
465 53260490 : assert(S >= this->begin() && "Range to erase is out of bounds.");
466 66009106 : assert(S <= E && "Trying to erase invalid range.");
467 64866081 : assert(E <= this->end() && "Trying to erase past the end.");
468 78606508 :
469 117527071 : iterator N = S;
470 132994680 : // Shift all elts down.
471 126754419 : iterator I = std::move(E, this->end(), S);
472 78113424 : // Drop the last elts.
473 583243052 : this->destroy_range(I, this->end());
474 575203020 : this->set_size(I - this->begin());
475 142088663 : return(N);
476 533587221 : }
477 1060913998 :
478 580467053 : iterator insert(iterator I, T &&Elt) {
479 61369322 : if (I == this->end()) { // Important special case for empty vector.
480 73435541 : this->push_back(::std::move(Elt));
481 41411978 : return this->end()-1;
482 44566170 : }
483 118551822 :
484 59279709 : assert(I >= this->begin() && "Insertion iterator is out of bounds.");
485 110164193 : assert(I <= this->end() && "Inserting past the end of the vector.");
486 111520696 :
487 185202035 : if (this->size() >= this->capacity()) {
488 213027019 : size_t EltNo = I-this->begin();
489 69311228 : this->grow();
490 177984605 : I = this->begin()+EltNo;
491 228120145 : }
492 161399724 :
493 33813660 : ::new ((void*) this->end()) T(::std::move(this->back()));
494 21455960 : // Push everything else over.
495 20284628 : std::move_backward(I, this->end()-1, this->end());
496 66548566 : this->set_size(this->size() + 1);
497 85801402 :
498 53835713 : // If we just moved the element we're inserting, be sure to update
499 76298561 : // the reference.
500 93628673 : T *EltPtr = &Elt;
501 196658587 : if (I <= EltPtr && EltPtr < this->end())
502 60688011 : ++EltPtr;
503 51556249 :
504 21754958 : *I = ::std::move(*EltPtr);
505 43661176 : return I;
506 109454262 : }
507 40702251 :
508 183556748 : iterator insert(iterator I, const T &Elt) {
509 62108495 : if (I == this->end()) { // Important special case for empty vector.
510 35688166 : this->push_back(Elt);
511 76791552 : return this->end()-1;
512 184781586 : }
513 45659934 :
514 74273626 : assert(I >= this->begin() && "Insertion iterator is out of bounds.");
515 63610882 : assert(I <= this->end() && "Inserting past the end of the vector.");
516 98914476 :
517 88112959 : if (this->size() >= this->capacity()) {
518 85912714 : size_t EltNo = I-this->begin();
519 65743390 : this->grow();
520 41536440 : I = this->begin()+EltNo;
521 335365585 : }
522 302147128 : ::new ((void*) this->end()) T(std::move(this->back()));
523 53301486 : // Push everything else over.
524 362041342 : std::move_backward(I, this->end()-1, this->end());
525 353805768 : this->set_size(this->size() + 1);
526 346479320 :
527 14320503 : // If we just moved the element we're inserting, be sure to update
528 102945263 : // the reference.
529 43936259 : const T *EltPtr = &Elt;
530 401325753 : if (I <= EltPtr && EltPtr < this->end())
531 255108300 : ++EltPtr;
532 22019496 :
533 384494110 : *I = *EltPtr;
534 354862668 : return I;
535 225411296 : }
536 300167343 :
537 148805641 : iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
538 181622968 : // Convert iterator to elt# to avoid invalidating iterator when we reserve()
539 407985277 : size_t InsertElt = I - this->begin();
540 355675505 :
541 48145699 : if (I == this->end()) { // Important special case for empty vector.
542 340083825 : append(NumToInsert, Elt);
543 372409305 : return this->begin()+InsertElt;
544 379638234 : }
545 48609091 :
546 122866959 : assert(I >= this->begin() && "Insertion iterator is out of bounds.");
547 59994586 : assert(I <= this->end() && "Inserting past the end of the vector.");
548 114234355 :
549 88844100 : // Ensure there is enough space.
550 196298022 : reserve(this->size() + NumToInsert);
551 356659837 :
552 347910376 : // Uninvalidate the iterator.
553 60126904 : I = this->begin()+InsertElt;
554 312632284 :
555 390165897 : // If there are more elements between the insertion point and the end of the
556 381141340 : // range than there are being inserted, we can use a simple approach to
557 20927141 : // insertion. Since we already reserved space, we know that this won't
558 32194785 : // reallocate the vector.
559 90462088 : if (size_t(this->end()-I) >= NumToInsert) {
560 5069001 : T *OldEnd = this->end();
561 318154449 : append(std::move_iterator<iterator>(this->end() - NumToInsert),
562 19660758 : std::move_iterator<iterator>(this->end()));
563 6162068 :
564 9278707 : // Copy the existing elements that get replaced.
565 10158953 : std::move_backward(I, OldEnd-NumToInsert, OldEnd);
566 118118343 :
567 69603460 : std::fill_n(I, NumToInsert, Elt);
568 9660420 : return I;
569 7327611 : }
570 150231652 :
571 238819548 : // Otherwise, we're inserting more elements than exist already, and we're
572 232838157 : // not inserting at the end.
573 14281308 :
574 230088380 : // Move over the elements that we're about to overwrite.
575 271461261 : T *OldEnd = this->end();
576 268143665 : this->set_size(this->size() + NumToInsert);
577 20160136 : size_t NumOverwritten = OldEnd-I;
578 66348575 : this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
579 142773758 :
580 147136145 : // Replace the overwritten part.
581 48418418 : std::fill_n(I, NumOverwritten, Elt);
582 20125477 :
583 87291309 : // Insert the non-overwritten middle part.
584 3375611 : std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
585 3693069 : return I;
586 827619 : }
587 34206360 :
588 34077597 : template <typename ItTy,
589 1043424849 : typename = typename std::enable_if<std::is_convertible<
590 201918145 : typename std::iterator_traits<ItTy>::iterator_category,
591 107986337 : std::input_iterator_tag>::value>::type>
592 102159948 : iterator insert(iterator I, ItTy From, ItTy To) {
593 131631277 : // Convert iterator to elt# to avoid invalidating iterator when we reserve()
594 218983226 : size_t InsertElt = I - this->begin();
595 128713371 :
596 94329591 : if (I == this->end()) { // Important special case for empty vector.
597 77536384 : append(From, To);
598 64042349 : return this->begin()+InsertElt;
599 102148828 : }
600 48021114 :
601 57338854 : assert(I >= this->begin() && "Insertion iterator is out of bounds.");
602 101924110 : assert(I <= this->end() && "Inserting past the end of the vector.");
603 104093027 :
604 59560534 : size_t NumToInsert = std::distance(From, To);
605 56847285 :
606 96919308 : // Ensure there is enough space.
607 36497795 : reserve(this->size() + NumToInsert);
608 11486533 :
609 6836574 : // Uninvalidate the iterator.
610 55866597 : I = this->begin()+InsertElt;
611 6195246 :
612 7769644 : // If there are more elements between the insertion point and the end of the
613 31236047 : // range than there are being inserted, we can use a simple approach to
614 2255885 : // insertion. Since we already reserved space, we know that this won't
615 40765024 : // reallocate the vector.
616 4894826 : if (size_t(this->end()-I) >= NumToInsert) {
617 3084049 : T *OldEnd = this->end();
618 9666029 : append(std::move_iterator<iterator>(this->end() - NumToInsert),
619 27449955 : std::move_iterator<iterator>(this->end()));
620 17655686 :
621 6098142 : // Copy the existing elements that get replaced.
622 110780450 : std::move_backward(I, OldEnd-NumToInsert, OldEnd);
623 127839585 :
624 137942202 : std::copy(From, To, I);
625 137227188 : return I;
626 74164188 : }
627 52386788 :
628 52781979 : // Otherwise, we're inserting more elements than exist already, and we're
629 59590988 : // not inserting at the end.
630 251017811 :
631 255095043 : // Move over the elements that we're about to overwrite.
632 265733715 : T *OldEnd = this->end();
633 140509949 : this->set_size(this->size() + NumToInsert);
634 136689226 : size_t NumOverwritten = OldEnd-I;
635 268336557 : this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
636 169362219 :
637 36749365 : // Replace the overwritten part.
638 3663174 : for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
639 8504372 : *J = *From;
640 205901376 : ++J; ++From;
641 103706628 : }
642 941922 :
643 4850033 : // Insert the non-overwritten middle part.
644 17984151 : this->uninitialized_copy(From, To, OldEnd);
645 16285663 : return I;
646 5009115 : }
647 4360200 :
648 3573671 : void insert(iterator I, std::initializer_list<T> IL) {
649 733033 : insert(I, IL.begin(), IL.end());
650 1409051 : }
651 1506707 :
652 42419221 : template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
653 25194186 : if (LLVM_UNLIKELY(this->size() >= this->capacity()))
654 49620888 : this->grow();
655 43290493 : ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
656 10868323 : this->set_size(this->size() + 1);
657 78749555 : }
658 53425403 :
659 1309406 : SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
660 2745109 :
661 31452218 : SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
662 105851577 :
663 43383984 : bool operator==(const SmallVectorImpl &RHS) const {
664 78170874 : if (this->size() != RHS.size()) return false;
665 51475455 : return std::equal(this->begin(), this->end(), RHS.begin());
666 7191900 : }
667 8136933 : bool operator!=(const SmallVectorImpl &RHS) const {
668 29598452 : return !(*this == RHS);
669 8347517 : }
670 1437343 :
671 2397589 : bool operator<(const SmallVectorImpl &RHS) const {
672 1191080 : return std::lexicographical_compare(this->begin(), this->end(),
673 26991549 : RHS.begin(), RHS.end());
674 36055058 : }
675 7177261 : };
676 35372745 :
677 5701446 : template <typename T>
678 4645410 : void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
679 1090568 : if (this == &RHS) return;
680 4021320 :
681 104409532 : // We can only avoid copying elements if neither vector is small.
682 80033202 : if (!this->isSmall() && !RHS.isSmall()) {
683 5048989 : std::swap(this->BeginX, RHS.BeginX);
684 5729178 : std::swap(this->Size, RHS.Size);
685 31552578 : std::swap(this->Capacity, RHS.Capacity);
686 31262722 : return;
687 2314767 : }
688 73029743 : if (RHS.size() > this->capacity())
689 49985549 : this->grow(RHS.size());
690 2849408 : if (this->size() > RHS.capacity())
691 976394 : RHS.grow(this->size());
692 28471083 :
693 2032133 : // Swap the shared elements.
694 4869298 : size_t NumShared = this->size();
695 128687494 : if (NumShared > RHS.size()) NumShared = RHS.size();
696 2928573 : for (size_type i = 0; i != NumShared; ++i)
697 2059828 : std::swap((*this)[i], RHS[i]);
698 1697260 :
699 952048 : // Copy over the extra elts.
700 4412353 : if (this->size() > RHS.size()) {
701 3532836 : size_t EltDiff = this->size() - RHS.size();
702 1822149 : this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
703 2268698 : RHS.set_size(RHS.size() + EltDiff);
704 2016553 : this->destroy_range(this->begin()+NumShared, this->end());
705 2159689 : this->set_size(NumShared);
706 3493369 : } else if (RHS.size() > this->size()) {
707 3120030 : size_t EltDiff = RHS.size() - this->size();
708 15286897 : this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
709 126022123 : this->set_size(this->size() + EltDiff);
710 11123007 : this->destroy_range(RHS.begin()+NumShared, RHS.end());
711 10709263 : RHS.set_size(NumShared);
712 1052968 : }
713 408310 : }
714 3410742 :
715 4848580 : template <typename T>
716 4974003 : SmallVectorImpl<T> &SmallVectorImpl<T>::
717 2504104 : operator=(const SmallVectorImpl<T> &RHS) {
718 178816721 : // Avoid self-assignment.
719 1094909 : if (this == &RHS) return *this;
720 79988 :
721 780722 : // If we already have sufficient space, assign the common elements, then
722 14660044 : // destroy any excess.
723 9406289 : size_t RHSSize = RHS.size();
724 48100092 : size_t CurSize = this->size();
725 39289779 : if (CurSize >= RHSSize) {
726 1389456 : // Assign common elements.
727 40766933 : iterator NewEnd;
728 2659796 : if (RHSSize)
729 147848 : NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
730 397160 : else
731 5500261 : NewEnd = this->begin();
732 77103639 :
733 38387776 : // Destroy excess elements.
734 206048 : this->destroy_range(NewEnd, this->end());
735 4714382 :
736 10271274 : // Trim.
737 324210 : this->set_size(RHSSize);
738 3289234 : return *this;
739 770807 : }
740 3675388 :
741 4277786 : // If we have to grow to have enough elements, destroy the current elements.
742 256264 : // This allows us to avoid copying them during the grow.
743 5244020 : // FIXME: don't do this if they're efficiently moveable.
744 36815492 : if (this->capacity() < RHSSize) {
745 35083034 : // Destroy current elements.
746 1199669 : this->destroy_range(this->begin(), this->end());
747 88143957 : this->set_size(0);
748 62781173 : CurSize = 0;
749 47882121 : this->grow(RHSSize);
750 31469357 : } else if (CurSize) {
751 50963124 : // Otherwise, use assignment for the already-constructed elements.
752 6476018 : std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
753 54819225 : }
754 53715319 :
755 32790801 : // Copy construct the new elements in place.
756 66878494 : this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
757 29258392 : this->begin()+CurSize);
758 86898188 :
759 462365568 : // Set end.
760 27601797 : this->set_size(RHSSize);
761 58334484 : return *this;
762 21027717 : }
763 7867693 :
764 7262975 : template <typename T>
765 7632176 : SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
766 5572862 : // Avoid self-assignment.
767 143051 : if (this == &RHS) return *this;
768 7755127 :
769 4305285 : // If the RHS isn't small, clear this vector and then steal its buffer.
770 8637543 : if (!RHS.isSmall()) {
771 4923820 : this->destroy_range(this->begin(), this->end());
772 4919899 : if (!this->isSmall()) free(this->begin());
773 3277672 : this->BeginX = RHS.BeginX;
774 7009382 : this->Size = RHS.Size;
775 6947282 : this->Capacity = RHS.Capacity;
776 2139433 : RHS.resetToSmall();
777 12113980 : return *this;
778 19653763 : }
779 22072627 :
780 1083076 : // If we already have sufficient space, assign the common elements, then
781 12037129 : // destroy any excess.
782 9154607 : size_t RHSSize = RHS.size();
783 1075189 : size_t CurSize = this->size();
784 2181477 : if (CurSize >= RHSSize) {
785 6429918 : // Assign common elements.
786 22497087 : iterator NewEnd = this->begin();
787 13751458 : if (RHSSize)
788 7791174 : NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
789 17124141 :
790 5566547 : // Destroy excess elements and trim the bounds.
791 15267746 : this->destroy_range(NewEnd, this->end());
792 9906296 : this->set_size(RHSSize);
793 6826401 :
794 18450070 : // Clear the RHS.
795 19453834 : RHS.clear();
796 20784544 :
797 9790285 : return *this;
798 38659502 : }
799 20906510 :
800 13399781 : // If we have to grow to have enough elements, destroy the current elements.
801 10994986 : // This allows us to avoid copying them during the grow.
802 3487419 : // FIXME: this may not actually make any sense if we can efficiently move
803 8100596 : // elements.
804 13992773 : if (this->capacity() < RHSSize) {
805 11379920 : // Destroy current elements.
806 17824594 : this->destroy_range(this->begin(), this->end());
807 9348290 : this->set_size(0);
808 7528430 : CurSize = 0;
809 13288866 : this->grow(RHSSize);
810 12029832 : } else if (CurSize) {
811 41315368 : // Otherwise, use assignment for the already-constructed elements.
812 12365152 : std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
813 4289231 : }
814 29025445 :
815 5729010 : // Move-construct the new elements in place.
816 2883259 : this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
817 4546065 : this->begin()+CurSize);
818 32982668 :
819 34015881 : // Set end.
820 34534793 : this->set_size(RHSSize);
821 6618029 :
822 2140330 : RHS.clear();
823 33339569 : return *this;
824 9782323 : }
825 12645567 :
826 12487896 : /// Storage for the SmallVector elements. This is specialized for the N=0 case
827 8464013 : /// to avoid allocating unnecessary storage.
828 3836540 : template <typename T, unsigned N>
829 951763 : struct SmallVectorStorage {
830 8515852 : AlignedCharArrayUnion<T> InlineElts[N];
831 20441357 : };
832 21207856 :
833 34110223 : /// We need the storage to be properly aligned even for small-size of 0 so that
834 4661011 : /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
835 7358574 : /// well-defined.
836 7738745 : template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
837 11642462 :
838 6943150 : /// This is a 'vector' (really, a variable-sized array), optimized
839 5182568 : /// for the case when the array is small. It contains some number of elements
840 4282224 : /// in-place, which allows it to avoid heap allocation when the actual number of
841 883348 : /// elements is below that threshold. This allows normal "small" cases to be
842 8623672 : /// fast without losing generality for large inputs.
843 18397847 : ///
844 12246237 : /// Note that this does not attempt to be exception safe.
845 6048204 : ///
846 1127652 : template <typename T, unsigned N>
847 29319385 : class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {
848 17649765 : public:
849 266201006 : SmallVector() : SmallVectorImpl<T>(N) {}
850 1046036 :
851 34967911 : ~SmallVector() {
852 3329375 : // Destroy the constructed elements in the vector.
853 4376593 : this->destroy_range(this->begin(), this->end());
854 76656980 : }
855 4721192 :
856 942528 : explicit SmallVector(size_t Size, const T &Value = T())
857 26037002 : : SmallVectorImpl<T>(N) {
858 25991378 : this->assign(Size, Value);
859 21086235 : }
860 18744687 :
861 143391811 : template <typename ItTy,
862 9773012 : typename = typename std::enable_if<std::is_convertible<
863 5861873 : typename std::iterator_traits<ItTy>::iterator_category,
864 9002204 : std::input_iterator_tag>::value>::type>
865 8863105 : SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
866 25974359 : this->append(S, E);
867 1206197039 : }
868 11156641 :
869 14989328 : template <typename RangeTy>
870 6680711 : explicit SmallVector(const iterator_range<RangeTy> &R)
871 2307895 : : SmallVectorImpl<T>(N) {
872 12651379 : this->append(R.begin(), R.end());
873 71328840 : }
874 5661008 :
875 18746419 : SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
876 31899241 : this->assign(IL);
877 14487264 : }
878 11053567 :
879 28144873 : SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
880 28904513 : if (!RHS.empty())
881 69190123 : SmallVectorImpl<T>::operator=(RHS);
882 34312011 : }
883 8563696 :
884 11722921 : const SmallVector &operator=(const SmallVector &RHS) {
885 137122563 : SmallVectorImpl<T>::operator=(RHS);
886 1889011 : return *this;
887 11685220 : }
888 9907508 :
889 883944 : SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
890 12150676 : if (!RHS.empty())
891 60091294 : SmallVectorImpl<T>::operator=(::std::move(RHS));
892 13537532 : }
893 379685110 :
894 7276500 : SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
895 53701363 : if (!RHS.empty())
896 17562899 : SmallVectorImpl<T>::operator=(::std::move(RHS));
897 138934144 : }
898 33931517 :
899 9990155 : const SmallVector &operator=(SmallVector &&RHS) {
900 184333964 : SmallVectorImpl<T>::operator=(::std::move(RHS));
901 44419958 : return *this;
902 50823059 : }
903 14573105 :
904 11307928 : const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
905 69388719 : SmallVectorImpl<T>::operator=(::std::move(RHS));
906 18739553 : return *this;
907 352259047 : }
908 358501108 :
909 56013608 : const SmallVector &operator=(std::initializer_list<T> IL) {
910 5716230 : this->assign(IL);
911 14512899 : return *this;
912 44189129 : }
913 136116521 : };
914 31367322 :
915 7362783 : template <typename T, unsigned N>
916 47076986 : inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
917 73698639 : return X.capacity_in_bytes();
918 82316938 : }
919 48014964 :
920 76158890 : } // end namespace llvm
921 314057056 :
922 66484073 : namespace std {
923 155310803 :
924 6308187 : /// Implement std::swap in terms of SmallVector swap.
925 80050540 : template<typename T>
926 21508586 : inline void
927 31045929 : swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
928 29054075 : LHS.swap(RHS);
929 56296413 : }
930 25042031 :
931 16255756 : /// Implement std::swap in terms of SmallVector swap.
932 4458864 : template<typename T, unsigned N>
933 2460906 : inline void
934 13014872 : swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
935 27235251 : LHS.swap(RHS);
936 4772698 : }
937 61054243 :
938 20776554 : } // end namespace std
939 68596200 :
940 6236376 : #endif // LLVM_ADT_SMALLVECTOR_H
|
