1 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file defines the SmallVector class.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_ADT_SMALLVECTOR_H
14 #define LLVM_ADT_SMALLVECTOR_H
16 #include "llvm/ADT/iterator_range.h"
17 #include "llvm/Support/AlignOf.h"
18 #include "llvm/Support/Compiler.h"
19 #include "llvm/Support/ErrorHandling.h"
20 #include "llvm/Support/MathExtras.h"
21 #include "llvm/Support/MemAlloc.h"
22 #include "llvm/Support/type_traits.h"
28 #include <initializer_list>
33 #include <type_traits>
38 /// This is all the stuff common to all SmallVectors.
40 /// The template parameter specifies the type which should be used to hold the
41 /// Size and Capacity of the SmallVector, so it can be adjusted.
42 /// Using 32 bit size is desirable to shrink the size of the SmallVector.
43 /// Using 64 bit size is desirable for cases like SmallVector<char>, where a
44 /// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
45 /// buffering bitcode output - which can exceed 4GB.
46 template <class Size_T> class SmallVectorBase {
49 Size_T Size = 0, Capacity;
51 /// The maximum value of the Size_T used.
52 static constexpr size_t SizeTypeMax() {
53 return std::numeric_limits<Size_T>::max();
56 SmallVectorBase() = delete;
57 SmallVectorBase(void *FirstEl, size_t TotalCapacity)
58 : BeginX(FirstEl), Capacity(TotalCapacity) {}
60 /// This is an implementation of the grow() method which only works
61 /// on POD-like data types and is out of line to reduce code duplication.
62 /// This function will report a fatal error if it cannot increase capacity.
63 void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize);
66 size_t size() const { return Size; }
67 size_t capacity() const { return Capacity; }
69 LLVM_NODISCARD bool empty() const { return !Size; }
71 /// Set the array size to \p N, which the current array must have enough
74 /// This does not construct or destroy any elements in the vector.
76 /// Clients can use this in conjunction with capacity() to write past the end
77 /// of the buffer when they know that more elements are available, and only
78 /// update the size later. This avoids the cost of value initializing elements
79 /// which will only be overwritten.
80 void set_size(size_t N) {
81 assert(N <= capacity());
87 using SmallVectorSizeType =
88 typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
91 /// Figure out the offset of the first element.
92 template <class T, typename = void> struct SmallVectorAlignmentAndSize {
93 AlignedCharArrayUnion<SmallVectorBase<SmallVectorSizeType<T>>> Base;
94 AlignedCharArrayUnion<T> FirstEl;
97 /// This is the part of SmallVectorTemplateBase which does not depend on whether
98 /// the type T is a POD. The extra dummy template argument is used by ArrayRef
99 /// to avoid unnecessarily requiring T to be complete.
100 template <typename T, typename = void>
101 class SmallVectorTemplateCommon
102 : public SmallVectorBase<SmallVectorSizeType<T>> {
103 using Base = SmallVectorBase<SmallVectorSizeType<T>>;
105 /// Find the address of the first element. For this pointer math to be valid
106 /// with small-size of 0 for T with lots of alignment, it's important that
107 /// SmallVectorStorage is properly-aligned even for small-size of 0.
108 void *getFirstEl() const {
109 return const_cast<void *>(reinterpret_cast<const void *>(
110 reinterpret_cast<const char *>(this) +
111 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
113 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
116 SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
118 void grow_pod(size_t MinCapacity, size_t TSize) {
119 Base::grow_pod(getFirstEl(), MinCapacity, TSize);
122 /// Return true if this is a smallvector which has not had dynamic
123 /// memory allocated for it.
124 bool isSmall() const { return this->BeginX == getFirstEl(); }
126 /// Put this vector in a state of being small.
127 void resetToSmall() {
128 this->BeginX = getFirstEl();
129 this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
133 using size_type = size_t;
134 using difference_type = ptrdiff_t;
135 using value_type = T;
136 using iterator = T *;
137 using const_iterator = const T *;
139 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
140 using reverse_iterator = std::reverse_iterator<iterator>;
142 using reference = T &;
143 using const_reference = const T &;
145 using const_pointer = const T *;
147 using Base::capacity;
151 // forward iterator creation methods.
152 iterator begin() { return (iterator)this->BeginX; }
153 const_iterator begin() const { return (const_iterator)this->BeginX; }
154 iterator end() { return begin() + size(); }
155 const_iterator end() const { return begin() + size(); }
157 // reverse iterator creation methods.
158 reverse_iterator rbegin() { return reverse_iterator(end()); }
159 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
160 reverse_iterator rend() { return reverse_iterator(begin()); }
161 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
163 size_type size_in_bytes() const { return size() * sizeof(T); }
164 size_type max_size() const {
165 return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
168 size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
170 /// Return a pointer to the vector's buffer, even if empty().
171 pointer data() { return pointer(begin()); }
172 /// Return a pointer to the vector's buffer, even if empty().
173 const_pointer data() const { return const_pointer(begin()); }
175 reference operator[](size_type idx) {
176 assert(idx < size());
179 const_reference operator[](size_type idx) const {
180 assert(idx < size());
188 const_reference front() const {
197 const_reference back() const {
203 /// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
204 /// method implementations that are designed to work with non-trivial T's.
206 /// We approximate is_trivially_copyable with trivial move/copy construction and
207 /// trivial destruction. While the standard doesn't specify that you're allowed
208 /// copy these types with memcpy, there is no way for the type to observe this.
209 /// This catches the important case of std::pair<POD, POD>, which is not
210 /// trivially assignable.
211 template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
212 (is_trivially_move_constructible<T>::value) &&
213 std::is_trivially_destructible<T>::value>
214 class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
216 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
218 static void destroy_range(T *S, T *E) {
225 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
226 /// constructing elements as needed.
227 template<typename It1, typename It2>
228 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
229 std::uninitialized_copy(std::make_move_iterator(I),
230 std::make_move_iterator(E), Dest);
233 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
234 /// constructing elements as needed.
235 template<typename It1, typename It2>
236 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
237 std::uninitialized_copy(I, E, Dest);
240 /// Grow the allocated memory (without initializing new elements), doubling
241 /// the size of the allocated memory. Guarantees space for at least one more
242 /// element, or MinSize more elements if specified.
243 void grow(size_t MinSize = 0);
246 void push_back(const T &Elt) {
247 if (LLVM_UNLIKELY(this->size() >= this->capacity()))
249 ::new ((void*) this->end()) T(Elt);
250 this->set_size(this->size() + 1);
253 void push_back(T &&Elt) {
254 if (LLVM_UNLIKELY(this->size() >= this->capacity()))
256 ::new ((void*) this->end()) T(::std::move(Elt));
257 this->set_size(this->size() + 1);
261 this->set_size(this->size() - 1);
266 // Define this out-of-line to dissuade the C++ compiler from inlining it.
267 template <typename T, bool TriviallyCopyable>
268 void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
269 // Ensure we can fit the new capacity.
270 // This is only going to be applicable when the capacity is 32 bit.
271 if (MinSize > this->SizeTypeMax())
272 report_bad_alloc_error("SmallVector capacity overflow during allocation");
274 // Ensure we can meet the guarantee of space for at least one more element.
275 // The above check alone will not catch the case where grow is called with a
276 // default MinCapacity of 0, but the current capacity cannot be increased.
277 // This is only going to be applicable when the capacity is 32 bit.
278 if (this->capacity() == this->SizeTypeMax())
279 report_bad_alloc_error("SmallVector capacity unable to grow");
281 // Always grow, even from zero.
282 size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
283 NewCapacity = std::min(std::max(NewCapacity, MinSize), this->SizeTypeMax());
284 T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
286 // Move the elements over.
287 this->uninitialized_move(this->begin(), this->end(), NewElts);
289 // Destroy the original elements.
290 destroy_range(this->begin(), this->end());
292 // If this wasn't grown from the inline copy, deallocate the old space.
293 if (!this->isSmall())
296 this->BeginX = NewElts;
297 this->Capacity = NewCapacity;
300 /// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
301 /// method implementations that are designed to work with trivially copyable
302 /// T's. This allows using memcpy in place of copy/move construction and
303 /// skipping destruction.
304 template <typename T>
305 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
307 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
309 // No need to do a destroy loop for POD's.
310 static void destroy_range(T *, T *) {}
312 /// Move the range [I, E) onto the uninitialized memory
313 /// starting with "Dest", constructing elements into it as needed.
314 template<typename It1, typename It2>
315 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
317 uninitialized_copy(I, E, Dest);
320 /// Copy the range [I, E) onto the uninitialized memory
321 /// starting with "Dest", constructing elements into it as needed.
322 template<typename It1, typename It2>
323 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
324 // Arbitrary iterator types; just use the basic implementation.
325 std::uninitialized_copy(I, E, Dest);
328 /// Copy the range [I, E) onto the uninitialized memory
329 /// starting with "Dest", constructing elements into it as needed.
330 template <typename T1, typename T2>
331 static void uninitialized_copy(
332 T1 *I, T1 *E, T2 *Dest,
333 std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
334 T2>::value> * = nullptr) {
335 // Use memcpy for PODs iterated by pointers (which includes SmallVector
336 // iterators): std::uninitialized_copy optimizes to memmove, but we can
337 // use memcpy here. Note that I and E are iterators and thus might be
338 // invalid for memcpy if they are equal.
340 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
343 /// Double the size of the allocated memory, guaranteeing space for at
344 /// least one more element or MinSize if specified.
345 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
348 void push_back(const T &Elt) {
349 if (LLVM_UNLIKELY(this->size() >= this->capacity()))
351 memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
352 this->set_size(this->size() + 1);
355 void pop_back() { this->set_size(this->size() - 1); }
358 /// This class consists of common code factored out of the SmallVector class to
359 /// reduce code duplication based on the SmallVector 'N' template parameter.
360 template <typename T>
361 class SmallVectorImpl : public SmallVectorTemplateBase<T> {
362 using SuperClass = SmallVectorTemplateBase<T>;
365 using iterator = typename SuperClass::iterator;
366 using const_iterator = typename SuperClass::const_iterator;
367 using reference = typename SuperClass::reference;
368 using size_type = typename SuperClass::size_type;
371 // Default ctor - Initialize to empty.
372 explicit SmallVectorImpl(unsigned N)
373 : SmallVectorTemplateBase<T>(N) {}
376 SmallVectorImpl(const SmallVectorImpl &) = delete;
379 // Subclass has already destructed this vector's elements.
380 // If this wasn't grown from the inline copy, deallocate the old space.
381 if (!this->isSmall())
386 this->destroy_range(this->begin(), this->end());
390 void resize(size_type N) {
391 if (N < this->size()) {
392 this->destroy_range(this->begin()+N, this->end());
394 } else if (N > this->size()) {
395 if (this->capacity() < N)
397 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
403 void resize(size_type N, const T &NV) {
404 if (N < this->size()) {
405 this->destroy_range(this->begin()+N, this->end());
407 } else if (N > this->size()) {
408 if (this->capacity() < N)
410 std::uninitialized_fill(this->end(), this->begin()+N, NV);
415 void reserve(size_type N) {
416 if (this->capacity() < N)
420 LLVM_NODISCARD T pop_back_val() {
421 T Result = ::std::move(this->back());
426 void swap(SmallVectorImpl &RHS);
428 /// Add the specified range to the end of the SmallVector.
429 template <typename in_iter,
430 typename = std::enable_if_t<std::is_convertible<
431 typename std::iterator_traits<in_iter>::iterator_category,
432 std::input_iterator_tag>::value>>
433 void append(in_iter in_start, in_iter in_end) {
434 size_type NumInputs = std::distance(in_start, in_end);
435 if (NumInputs > this->capacity() - this->size())
436 this->grow(this->size()+NumInputs);
438 this->uninitialized_copy(in_start, in_end, this->end());
439 this->set_size(this->size() + NumInputs);
442 /// Append \p NumInputs copies of \p Elt to the end.
443 void append(size_type NumInputs, const T &Elt) {
444 if (NumInputs > this->capacity() - this->size())
445 this->grow(this->size()+NumInputs);
447 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
448 this->set_size(this->size() + NumInputs);
451 void append(std::initializer_list<T> IL) {
452 append(IL.begin(), IL.end());
455 // FIXME: Consider assigning over existing elements, rather than clearing &
456 // re-initializing them - for all assign(...) variants.
458 void assign(size_type NumElts, const T &Elt) {
460 if (this->capacity() < NumElts)
462 this->set_size(NumElts);
463 std::uninitialized_fill(this->begin(), this->end(), Elt);
466 template <typename in_iter,
467 typename = std::enable_if_t<std::is_convertible<
468 typename std::iterator_traits<in_iter>::iterator_category,
469 std::input_iterator_tag>::value>>
470 void assign(in_iter in_start, in_iter in_end) {
472 append(in_start, in_end);
475 void assign(std::initializer_list<T> IL) {
480 iterator erase(const_iterator CI) {
481 // Just cast away constness because this is a non-const member function.
482 iterator I = const_cast<iterator>(CI);
484 assert(I >= this->begin() && "Iterator to erase is out of bounds.");
485 assert(I < this->end() && "Erasing at past-the-end iterator.");
488 // Shift all elts down one.
489 std::move(I+1, this->end(), I);
490 // Drop the last elt.
495 iterator erase(const_iterator CS, const_iterator CE) {
496 // Just cast away constness because this is a non-const member function.
497 iterator S = const_cast<iterator>(CS);
498 iterator E = const_cast<iterator>(CE);
500 assert(S >= this->begin() && "Range to erase is out of bounds.");
501 assert(S <= E && "Trying to erase invalid range.");
502 assert(E <= this->end() && "Trying to erase past the end.");
505 // Shift all elts down.
506 iterator I = std::move(E, this->end(), S);
507 // Drop the last elts.
508 this->destroy_range(I, this->end());
509 this->set_size(I - this->begin());
513 iterator insert(iterator I, T &&Elt) {
514 if (I == this->end()) { // Important special case for empty vector.
515 this->push_back(::std::move(Elt));
516 return this->end()-1;
519 assert(I >= this->begin() && "Insertion iterator is out of bounds.");
520 assert(I <= this->end() && "Inserting past the end of the vector.");
522 if (this->size() >= this->capacity()) {
523 size_t EltNo = I-this->begin();
525 I = this->begin()+EltNo;
528 ::new ((void*) this->end()) T(::std::move(this->back()));
529 // Push everything else over.
530 std::move_backward(I, this->end()-1, this->end());
531 this->set_size(this->size() + 1);
533 // If we just moved the element we're inserting, be sure to update
536 if (I <= EltPtr && EltPtr < this->end())
539 *I = ::std::move(*EltPtr);
543 iterator insert(iterator I, const T &Elt) {
544 if (I == this->end()) { // Important special case for empty vector.
545 this->push_back(Elt);
546 return this->end()-1;
549 assert(I >= this->begin() && "Insertion iterator is out of bounds.");
550 assert(I <= this->end() && "Inserting past the end of the vector.");
552 if (this->size() >= this->capacity()) {
553 size_t EltNo = I-this->begin();
555 I = this->begin()+EltNo;
557 ::new ((void*) this->end()) T(std::move(this->back()));
558 // Push everything else over.
559 std::move_backward(I, this->end()-1, this->end());
560 this->set_size(this->size() + 1);
562 // If we just moved the element we're inserting, be sure to update
564 const T *EltPtr = &Elt;
565 if (I <= EltPtr && EltPtr < this->end())
572 iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
573 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
574 size_t InsertElt = I - this->begin();
576 if (I == this->end()) { // Important special case for empty vector.
577 append(NumToInsert, Elt);
578 return this->begin()+InsertElt;
581 assert(I >= this->begin() && "Insertion iterator is out of bounds.");
582 assert(I <= this->end() && "Inserting past the end of the vector.");
584 // Ensure there is enough space.
585 reserve(this->size() + NumToInsert);
587 // Uninvalidate the iterator.
588 I = this->begin()+InsertElt;
590 // If there are more elements between the insertion point and the end of the
591 // range than there are being inserted, we can use a simple approach to
592 // insertion. Since we already reserved space, we know that this won't
593 // reallocate the vector.
594 if (size_t(this->end()-I) >= NumToInsert) {
595 T *OldEnd = this->end();
596 append(std::move_iterator<iterator>(this->end() - NumToInsert),
597 std::move_iterator<iterator>(this->end()));
599 // Copy the existing elements that get replaced.
600 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
602 std::fill_n(I, NumToInsert, Elt);
606 // Otherwise, we're inserting more elements than exist already, and we're
607 // not inserting at the end.
609 // Move over the elements that we're about to overwrite.
610 T *OldEnd = this->end();
611 this->set_size(this->size() + NumToInsert);
612 size_t NumOverwritten = OldEnd-I;
613 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
615 // Replace the overwritten part.
616 std::fill_n(I, NumOverwritten, Elt);
618 // Insert the non-overwritten middle part.
619 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
623 template <typename ItTy,
624 typename = std::enable_if_t<std::is_convertible<
625 typename std::iterator_traits<ItTy>::iterator_category,
626 std::input_iterator_tag>::value>>
627 iterator insert(iterator I, ItTy From, ItTy To) {
628 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
629 size_t InsertElt = I - this->begin();
631 if (I == this->end()) { // Important special case for empty vector.
633 return this->begin()+InsertElt;
636 assert(I >= this->begin() && "Insertion iterator is out of bounds.");
637 assert(I <= this->end() && "Inserting past the end of the vector.");
639 size_t NumToInsert = std::distance(From, To);
641 // Ensure there is enough space.
642 reserve(this->size() + NumToInsert);
644 // Uninvalidate the iterator.
645 I = this->begin()+InsertElt;
647 // If there are more elements between the insertion point and the end of the
648 // range than there are being inserted, we can use a simple approach to
649 // insertion. Since we already reserved space, we know that this won't
650 // reallocate the vector.
651 if (size_t(this->end()-I) >= NumToInsert) {
652 T *OldEnd = this->end();
653 append(std::move_iterator<iterator>(this->end() - NumToInsert),
654 std::move_iterator<iterator>(this->end()));
656 // Copy the existing elements that get replaced.
657 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
659 std::copy(From, To, I);
663 // Otherwise, we're inserting more elements than exist already, and we're
664 // not inserting at the end.
666 // Move over the elements that we're about to overwrite.
667 T *OldEnd = this->end();
668 this->set_size(this->size() + NumToInsert);
669 size_t NumOverwritten = OldEnd-I;
670 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
672 // Replace the overwritten part.
673 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
678 // Insert the non-overwritten middle part.
679 this->uninitialized_copy(From, To, OldEnd);
683 void insert(iterator I, std::initializer_list<T> IL) {
684 insert(I, IL.begin(), IL.end());
687 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
688 if (LLVM_UNLIKELY(this->size() >= this->capacity()))
690 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
691 this->set_size(this->size() + 1);
695 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
697 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
699 bool operator==(const SmallVectorImpl &RHS) const {
700 if (this->size() != RHS.size()) return false;
701 return std::equal(this->begin(), this->end(), RHS.begin());
703 bool operator!=(const SmallVectorImpl &RHS) const {
704 return !(*this == RHS);
707 bool operator<(const SmallVectorImpl &RHS) const {
708 return std::lexicographical_compare(this->begin(), this->end(),
709 RHS.begin(), RHS.end());
713 template <typename T>
714 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
715 if (this == &RHS) return;
717 // We can only avoid copying elements if neither vector is small.
718 if (!this->isSmall() && !RHS.isSmall()) {
719 std::swap(this->BeginX, RHS.BeginX);
720 std::swap(this->Size, RHS.Size);
721 std::swap(this->Capacity, RHS.Capacity);
724 if (RHS.size() > this->capacity())
725 this->grow(RHS.size());
726 if (this->size() > RHS.capacity())
727 RHS.grow(this->size());
729 // Swap the shared elements.
730 size_t NumShared = this->size();
731 if (NumShared > RHS.size()) NumShared = RHS.size();
732 for (size_type i = 0; i != NumShared; ++i)
733 std::swap((*this)[i], RHS[i]);
735 // Copy over the extra elts.
736 if (this->size() > RHS.size()) {
737 size_t EltDiff = this->size() - RHS.size();
738 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
739 RHS.set_size(RHS.size() + EltDiff);
740 this->destroy_range(this->begin()+NumShared, this->end());
741 this->set_size(NumShared);
742 } else if (RHS.size() > this->size()) {
743 size_t EltDiff = RHS.size() - this->size();
744 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
745 this->set_size(this->size() + EltDiff);
746 this->destroy_range(RHS.begin()+NumShared, RHS.end());
747 RHS.set_size(NumShared);
751 template <typename T>
752 SmallVectorImpl<T> &SmallVectorImpl<T>::
753 operator=(const SmallVectorImpl<T> &RHS) {
754 // Avoid self-assignment.
755 if (this == &RHS) return *this;
757 // If we already have sufficient space, assign the common elements, then
758 // destroy any excess.
759 size_t RHSSize = RHS.size();
760 size_t CurSize = this->size();
761 if (CurSize >= RHSSize) {
762 // Assign common elements.
765 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
767 NewEnd = this->begin();
769 // Destroy excess elements.
770 this->destroy_range(NewEnd, this->end());
773 this->set_size(RHSSize);
777 // If we have to grow to have enough elements, destroy the current elements.
778 // This allows us to avoid copying them during the grow.
779 // FIXME: don't do this if they're efficiently moveable.
780 if (this->capacity() < RHSSize) {
781 // Destroy current elements.
782 this->destroy_range(this->begin(), this->end());
786 } else if (CurSize) {
787 // Otherwise, use assignment for the already-constructed elements.
788 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
791 // Copy construct the new elements in place.
792 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
793 this->begin()+CurSize);
796 this->set_size(RHSSize);
800 template <typename T>
801 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
802 // Avoid self-assignment.
803 if (this == &RHS) return *this;
805 // If the RHS isn't small, clear this vector and then steal its buffer.
806 if (!RHS.isSmall()) {
807 this->destroy_range(this->begin(), this->end());
808 if (!this->isSmall()) free(this->begin());
809 this->BeginX = RHS.BeginX;
810 this->Size = RHS.Size;
811 this->Capacity = RHS.Capacity;
816 // If we already have sufficient space, assign the common elements, then
817 // destroy any excess.
818 size_t RHSSize = RHS.size();
819 size_t CurSize = this->size();
820 if (CurSize >= RHSSize) {
821 // Assign common elements.
822 iterator NewEnd = this->begin();
824 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
826 // Destroy excess elements and trim the bounds.
827 this->destroy_range(NewEnd, this->end());
828 this->set_size(RHSSize);
836 // If we have to grow to have enough elements, destroy the current elements.
837 // This allows us to avoid copying them during the grow.
838 // FIXME: this may not actually make any sense if we can efficiently move
840 if (this->capacity() < RHSSize) {
841 // Destroy current elements.
842 this->destroy_range(this->begin(), this->end());
846 } else if (CurSize) {
847 // Otherwise, use assignment for the already-constructed elements.
848 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
851 // Move-construct the new elements in place.
852 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
853 this->begin()+CurSize);
856 this->set_size(RHSSize);
862 /// Storage for the SmallVector elements. This is specialized for the N=0 case
863 /// to avoid allocating unnecessary storage.
864 template <typename T, unsigned N>
865 struct SmallVectorStorage {
866 AlignedCharArrayUnion<T> InlineElts[N];
869 /// We need the storage to be properly aligned even for small-size of 0 so that
870 /// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
872 template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
874 /// This is a 'vector' (really, a variable-sized array), optimized
875 /// for the case when the array is small. It contains some number of elements
876 /// in-place, which allows it to avoid heap allocation when the actual number of
877 /// elements is below that threshold. This allows normal "small" cases to be
878 /// fast without losing generality for large inputs.
880 /// Note that this does not attempt to be exception safe.
882 template <typename T, unsigned N>
883 class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl<T>,
884 SmallVectorStorage<T, N> {
886 SmallVector() : SmallVectorImpl<T>(N) {}
889 // Destroy the constructed elements in the vector.
890 this->destroy_range(this->begin(), this->end());
893 explicit SmallVector(size_t Size, const T &Value = T())
894 : SmallVectorImpl<T>(N) {
895 this->assign(Size, Value);
898 template <typename ItTy,
899 typename = std::enable_if_t<std::is_convertible<
900 typename std::iterator_traits<ItTy>::iterator_category,
901 std::input_iterator_tag>::value>>
902 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
906 template <typename RangeTy>
907 explicit SmallVector(const iterator_range<RangeTy> &R)
908 : SmallVectorImpl<T>(N) {
909 this->append(R.begin(), R.end());
912 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
916 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
918 SmallVectorImpl<T>::operator=(RHS);
921 const SmallVector &operator=(const SmallVector &RHS) {
922 SmallVectorImpl<T>::operator=(RHS);
926 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
928 SmallVectorImpl<T>::operator=(::std::move(RHS));
931 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
933 SmallVectorImpl<T>::operator=(::std::move(RHS));
936 const SmallVector &operator=(SmallVector &&RHS) {
937 SmallVectorImpl<T>::operator=(::std::move(RHS));
941 const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
942 SmallVectorImpl<T>::operator=(::std::move(RHS));
946 const SmallVector &operator=(std::initializer_list<T> IL) {
952 template <typename T, unsigned N>
953 inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
954 return X.capacity_in_bytes();
957 /// Given a range of type R, iterate the entire range and return a
958 /// SmallVector with elements of the vector. This is useful, for example,
959 /// when you want to iterate a range and then sort the results.
960 template <unsigned Size, typename R>
961 SmallVector<typename std::remove_const<typename std::remove_reference<
962 decltype(*std::begin(std::declval<R &>()))>::type>::type,
964 to_vector(R &&Range) {
965 return {std::begin(Range), std::end(Range)};
968 } // end namespace llvm
972 /// Implement std::swap in terms of SmallVector swap.
975 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
979 /// Implement std::swap in terms of SmallVector swap.
980 template<typename T, unsigned N>
982 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
986 } // end namespace std
988 #endif // LLVM_ADT_SMALLVECTOR_H