Update prebuilt Clang to r416183b from Android.
https://android.googlesource.com/platform/prebuilts/clang/host/
linux-x86/+/06a71ddac05c22edb2d10b590e1769b3f8619bef
clang 12.0.5 (based on r416183b) from build 7284624.
Change-Id: I277a316abcf47307562d8b748b84870f31a72866
Signed-off-by: Olivier Deprez <olivier.deprez@arm.com>
diff --git a/linux-x64/clang/include/llvm/ADT/SmallVector.h b/linux-x64/clang/include/llvm/ADT/SmallVector.h
index 1758690..2e47846 100644
--- a/linux-x64/clang/include/llvm/ADT/SmallVector.h
+++ b/linux-x64/clang/include/llvm/ADT/SmallVector.h
@@ -14,12 +14,11 @@
#define LLVM_ADT_SMALLVECTOR_H
#include "llvm/ADT/iterator_range.h"
-#include "llvm/Support/AlignOf.h"
#include "llvm/Support/Compiler.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/MemAlloc.h"
#include "llvm/Support/type_traits.h"
-#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
@@ -27,6 +26,7 @@
#include <cstring>
#include <initializer_list>
#include <iterator>
+#include <limits>
#include <memory>
#include <new>
#include <type_traits>
@@ -34,11 +34,23 @@
namespace llvm {
-/// This is all the non-templated stuff common to all SmallVectors.
-class SmallVectorBase {
+/// This is all the stuff common to all SmallVectors.
+///
+/// The template parameter specifies the type which should be used to hold the
+/// Size and Capacity of the SmallVector, so it can be adjusted.
+/// Using 32 bit size is desirable to shrink the size of the SmallVector.
+/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
+/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
+/// buffering bitcode output - which can exceed 4GB.
+template <class Size_T> class SmallVectorBase {
protected:
void *BeginX;
- unsigned Size = 0, Capacity;
+ Size_T Size = 0, Capacity;
+
+ /// The maximum value of the Size_T used.
+ static constexpr size_t SizeTypeMax() {
+ return std::numeric_limits<Size_T>::max();
+ }
SmallVectorBase() = delete;
SmallVectorBase(void *FirstEl, size_t TotalCapacity)
@@ -46,7 +58,15 @@
/// This is an implementation of the grow() method which only works
/// on POD-like data types and is out of line to reduce code duplication.
- void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize);
+ /// This function will report a fatal error if it cannot increase capacity.
+ void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
+
+ /// Report that MinSize doesn't fit into this vector's size type. Throws
+ /// std::length_error or calls report_fatal_error.
+ LLVM_ATTRIBUTE_NORETURN static void report_size_overflow(size_t MinSize);
+ /// Report that this vector is already at maximum capacity. Throws
+ /// std::length_error or calls report_fatal_error.
+ LLVM_ATTRIBUTE_NORETURN static void report_at_maximum_capacity();
public:
size_t size() const { return Size; }
@@ -69,17 +89,26 @@
}
};
+template <class T>
+using SmallVectorSizeType =
+ typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
+ uint32_t>::type;
+
/// Figure out the offset of the first element.
template <class T, typename = void> struct SmallVectorAlignmentAndSize {
- AlignedCharArrayUnion<SmallVectorBase> Base;
- AlignedCharArrayUnion<T> FirstEl;
+ alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
+ SmallVectorBase<SmallVectorSizeType<T>>)];
+ alignas(T) char FirstEl[sizeof(T)];
};
/// This is the part of SmallVectorTemplateBase which does not depend on whether
/// the type T is a POD. The extra dummy template argument is used by ArrayRef
/// to avoid unnecessarily requiring T to be complete.
template <typename T, typename = void>
-class SmallVectorTemplateCommon : public SmallVectorBase {
+class SmallVectorTemplateCommon
+ : public SmallVectorBase<SmallVectorSizeType<T>> {
+ using Base = SmallVectorBase<SmallVectorSizeType<T>>;
+
/// Find the address of the first element. For this pointer math to be valid
/// with small-size of 0 for T with lots of alignment, it's important that
/// SmallVectorStorage is properly-aligned even for small-size of 0.
@@ -91,21 +120,125 @@
// Space after 'FirstEl' is clobbered, do not add any instance vars after it.
protected:
- SmallVectorTemplateCommon(size_t Size)
- : SmallVectorBase(getFirstEl(), Size) {}
+ SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
- void grow_pod(size_t MinCapacity, size_t TSize) {
- SmallVectorBase::grow_pod(getFirstEl(), MinCapacity, TSize);
+ void grow_pod(size_t MinSize, size_t TSize) {
+ Base::grow_pod(getFirstEl(), MinSize, TSize);
}
/// Return true if this is a smallvector which has not had dynamic
/// memory allocated for it.
- bool isSmall() const { return BeginX == getFirstEl(); }
+ bool isSmall() const { return this->BeginX == getFirstEl(); }
/// Put this vector in a state of being small.
void resetToSmall() {
- BeginX = getFirstEl();
- Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
+ this->BeginX = getFirstEl();
+ this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
+ }
+
+ /// Return true if V is an internal reference to the given range.
+ bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
+ // Use std::less to avoid UB.
+ std::less<> LessThan;
+ return !LessThan(V, First) && LessThan(V, Last);
+ }
+
+ /// Return true if V is an internal reference to this vector.
+ bool isReferenceToStorage(const void *V) const {
+ return isReferenceToRange(V, this->begin(), this->end());
+ }
+
+ /// Return true if First and Last form a valid (possibly empty) range in this
+ /// vector's storage.
+ bool isRangeInStorage(const void *First, const void *Last) const {
+ // Use std::less to avoid UB.
+ std::less<> LessThan;
+ return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
+ !LessThan(this->end(), Last);
+ }
+
+ /// Return true unless Elt will be invalidated by resizing the vector to
+ /// NewSize.
+ bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
+ // Past the end.
+ if (LLVM_LIKELY(!isReferenceToStorage(Elt)))
+ return true;
+
+ // Return false if Elt will be destroyed by shrinking.
+ if (NewSize <= this->size())
+ return Elt < this->begin() + NewSize;
+
+ // Return false if we need to grow.
+ return NewSize <= this->capacity();
+ }
+
+ /// Check whether Elt will be invalidated by resizing the vector to NewSize.
+ void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
+ assert(isSafeToReferenceAfterResize(Elt, NewSize) &&
+ "Attempting to reference an element of the vector in an operation "
+ "that invalidates it");
+ }
+
+ /// Check whether Elt will be invalidated by increasing the size of the
+ /// vector by N.
+ void assertSafeToAdd(const void *Elt, size_t N = 1) {
+ this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
+ }
+
+ /// Check whether any part of the range will be invalidated by clearing.
+ void assertSafeToReferenceAfterClear(const T *From, const T *To) {
+ if (From == To)
+ return;
+ this->assertSafeToReferenceAfterResize(From, 0);
+ this->assertSafeToReferenceAfterResize(To - 1, 0);
+ }
+ template <
+ class ItTy,
+ std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
+ bool> = false>
+ void assertSafeToReferenceAfterClear(ItTy, ItTy) {}
+
+ /// Check whether any part of the range will be invalidated by growing.
+ void assertSafeToAddRange(const T *From, const T *To) {
+ if (From == To)
+ return;
+ this->assertSafeToAdd(From, To - From);
+ this->assertSafeToAdd(To - 1, To - From);
+ }
+ template <
+ class ItTy,
+ std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
+ bool> = false>
+ void assertSafeToAddRange(ItTy, ItTy) {}
+
+ /// Check whether any argument will be invalidated by growing for
+ /// emplace_back.
+ template <class ArgType1, class... ArgTypes>
+ void assertSafeToEmplace(ArgType1 &Arg1, ArgTypes &... Args) {
+ this->assertSafeToAdd(&Arg1);
+ this->assertSafeToEmplace(Args...);
+ }
+ void assertSafeToEmplace() {}
+
+ /// Reserve enough space to add one element, and return the updated element
+ /// pointer in case it was a reference to the storage.
+ template <class U>
+ static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
+ size_t N) {
+ size_t NewSize = This->size() + N;
+ if (LLVM_LIKELY(NewSize <= This->capacity()))
+ return &Elt;
+
+ bool ReferencesStorage = false;
+ int64_t Index = -1;
+ if (!U::TakesParamByValue) {
+ if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))) {
+ ReferencesStorage = true;
+ Index = &Elt - This->begin();
+ }
+ }
+ This->grow(NewSize);
+ return ReferencesStorage ? This->begin() + Index : &Elt;
}
public:
@@ -123,6 +256,10 @@
using pointer = T *;
using const_pointer = const T *;
+ using Base::capacity;
+ using Base::empty;
+ using Base::size;
+
// forward iterator creation methods.
iterator begin() { return (iterator)this->BeginX; }
const_iterator begin() const { return (const_iterator)this->BeginX; }
@@ -136,7 +273,9 @@
const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
size_type size_in_bytes() const { return size() * sizeof(T); }
- size_type max_size() const { return size_type(-1) / sizeof(T); }
+ size_type max_size() const {
+ return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
+ }
size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
@@ -173,11 +312,24 @@
}
};
-/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put method
-/// implementations that are designed to work with non-POD-like T's.
-template <typename T, bool = is_trivially_copyable<T>::value>
+/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
+/// method implementations that are designed to work with non-trivial T's.
+///
+/// We approximate is_trivially_copyable with trivial move/copy construction and
+/// trivial destruction. While the standard doesn't specify that you're allowed
+/// copy these types with memcpy, there is no way for the type to observe this.
+/// This catches the important case of std::pair<POD, POD>, which is not
+/// trivially assignable.
+template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
+ (is_trivially_move_constructible<T>::value) &&
+ std::is_trivially_destructible<T>::value>
class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
+ friend class SmallVectorTemplateCommon<T>;
+
protected:
+ static constexpr bool TakesParamByValue = false;
+ using ValueParamT = const T &;
+
SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
static void destroy_range(T *S, T *E) {
@@ -207,18 +359,32 @@
/// element, or MinSize more elements if specified.
void grow(size_t MinSize = 0);
+ /// Reserve enough space to add one element, and return the updated element
+ /// pointer in case it was a reference to the storage.
+ const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
+ return this->reserveForParamAndGetAddressImpl(this, Elt, N);
+ }
+
+ /// Reserve enough space to add one element, and return the updated element
+ /// pointer in case it was a reference to the storage.
+ T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
+ return const_cast<T *>(
+ this->reserveForParamAndGetAddressImpl(this, Elt, N));
+ }
+
+ static T &&forward_value_param(T &&V) { return std::move(V); }
+ static const T &forward_value_param(const T &V) { return V; }
+
public:
void push_back(const T &Elt) {
- if (LLVM_UNLIKELY(this->size() >= this->capacity()))
- this->grow();
- ::new ((void*) this->end()) T(Elt);
+ const T *EltPtr = reserveForParamAndGetAddress(Elt);
+ ::new ((void *)this->end()) T(*EltPtr);
this->set_size(this->size() + 1);
}
void push_back(T &&Elt) {
- if (LLVM_UNLIKELY(this->size() >= this->capacity()))
- this->grow();
- ::new ((void*) this->end()) T(::std::move(Elt));
+ T *EltPtr = reserveForParamAndGetAddress(Elt);
+ ::new ((void *)this->end()) T(::std::move(*EltPtr));
this->set_size(this->size() + 1);
}
@@ -231,12 +397,21 @@
// Define this out-of-line to dissuade the C++ compiler from inlining it.
template <typename T, bool TriviallyCopyable>
void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
- if (MinSize > UINT32_MAX)
- report_bad_alloc_error("SmallVector capacity overflow during allocation");
+ // Ensure we can fit the new capacity.
+ // This is only going to be applicable when the capacity is 32 bit.
+ if (MinSize > this->SizeTypeMax())
+ this->report_size_overflow(MinSize);
+
+ // Ensure we can meet the guarantee of space for at least one more element.
+ // The above check alone will not catch the case where grow is called with a
+ // default MinSize of 0, but the current capacity cannot be increased.
+ // This is only going to be applicable when the capacity is 32 bit.
+ if (this->capacity() == this->SizeTypeMax())
+ this->report_at_maximum_capacity();
// Always grow, even from zero.
size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
- NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX));
+ NewCapacity = std::min(std::max(NewCapacity, MinSize), this->SizeTypeMax());
T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
// Move the elements over.
@@ -254,10 +429,23 @@
}
/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
-/// method implementations that are designed to work with POD-like T's.
+/// method implementations that are designed to work with trivially copyable
+/// T's. This allows using memcpy in place of copy/move construction and
+/// skipping destruction.
template <typename T>
class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
+ friend class SmallVectorTemplateCommon<T>;
+
protected:
+ /// True if it's cheap enough to take parameters by value. Doing so avoids
+ /// overhead related to mitigations for reference invalidation.
+ static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
+
+ /// Either const T& or T, depending on whether it's cheap enough to take
+ /// parameters by value.
+ using ValueParamT =
+ typename std::conditional<TakesParamByValue, T, const T &>::type;
+
SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
// No need to do a destroy loop for POD's.
@@ -284,8 +472,8 @@
template <typename T1, typename T2>
static void uninitialized_copy(
T1 *I, T1 *E, T2 *Dest,
- typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,
- T2>::value>::type * = nullptr) {
+ std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
+ T2>::value> * = nullptr) {
// Use memcpy for PODs iterated by pointers (which includes SmallVector
// iterators): std::uninitialized_copy optimizes to memmove, but we can
// use memcpy here. Note that I and E are iterators and thus might be
@@ -298,11 +486,26 @@
/// least one more element or MinSize if specified.
void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
+ /// Reserve enough space to add one element, and return the updated element
+ /// pointer in case it was a reference to the storage.
+ const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
+ return this->reserveForParamAndGetAddressImpl(this, Elt, N);
+ }
+
+ /// Reserve enough space to add one element, and return the updated element
+ /// pointer in case it was a reference to the storage.
+ T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
+ return const_cast<T *>(
+ this->reserveForParamAndGetAddressImpl(this, Elt, N));
+ }
+
+ /// Copy \p V or return a reference, depending on \a ValueParamT.
+ static ValueParamT forward_value_param(ValueParamT V) { return V; }
+
public:
- void push_back(const T &Elt) {
- if (LLVM_UNLIKELY(this->size() >= this->capacity()))
- this->grow();
- memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
+ void push_back(ValueParamT Elt) {
+ const T *EltPtr = reserveForParamAndGetAddress(Elt);
+ memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
this->set_size(this->size() + 1);
}
@@ -322,6 +525,9 @@
using size_type = typename SuperClass::size_type;
protected:
+ using SmallVectorTemplateBase<T>::TakesParamByValue;
+ using ValueParamT = typename SuperClass::ValueParamT;
+
// Default ctor - Initialize to empty.
explicit SmallVectorImpl(unsigned N)
: SmallVectorTemplateBase<T>(N) {}
@@ -341,29 +547,38 @@
this->Size = 0;
}
- void resize(size_type N) {
+private:
+ template <bool ForOverwrite> void resizeImpl(size_type N) {
if (N < this->size()) {
- this->destroy_range(this->begin()+N, this->end());
- this->set_size(N);
+ this->pop_back_n(this->size() - N);
} else if (N > this->size()) {
- if (this->capacity() < N)
- this->grow(N);
+ this->reserve(N);
for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
- new (&*I) T();
+ if (ForOverwrite)
+ new (&*I) T;
+ else
+ new (&*I) T();
this->set_size(N);
}
}
- void resize(size_type N, const T &NV) {
+public:
+ void resize(size_type N) { resizeImpl<false>(N); }
+
+ /// Like resize, but \ref T is POD, the new values won't be initialized.
+ void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
+
+ void resize(size_type N, ValueParamT NV) {
+ if (N == this->size())
+ return;
+
if (N < this->size()) {
- this->destroy_range(this->begin()+N, this->end());
- this->set_size(N);
- } else if (N > this->size()) {
- if (this->capacity() < N)
- this->grow(N);
- std::uninitialized_fill(this->end(), this->begin()+N, NV);
- this->set_size(N);
+ this->pop_back_n(this->size() - N);
+ return;
}
+
+ // N > this->size(). Defer to append.
+ this->append(N - this->size(), NV);
}
void reserve(size_type N) {
@@ -371,6 +586,12 @@
this->grow(N);
}
+ void pop_back_n(size_type NumItems) {
+ assert(this->size() >= NumItems);
+ this->destroy_range(this->end() - NumItems, this->end());
+ this->set_size(this->size() - NumItems);
+ }
+
LLVM_NODISCARD T pop_back_val() {
T Result = ::std::move(this->back());
this->pop_back();
@@ -381,24 +602,21 @@
/// Add the specified range to the end of the SmallVector.
template <typename in_iter,
- typename = typename std::enable_if<std::is_convertible<
+ typename = std::enable_if_t<std::is_convertible<
typename std::iterator_traits<in_iter>::iterator_category,
- std::input_iterator_tag>::value>::type>
+ std::input_iterator_tag>::value>>
void append(in_iter in_start, in_iter in_end) {
+ this->assertSafeToAddRange(in_start, in_end);
size_type NumInputs = std::distance(in_start, in_end);
- if (NumInputs > this->capacity() - this->size())
- this->grow(this->size()+NumInputs);
-
+ this->reserve(this->size() + NumInputs);
this->uninitialized_copy(in_start, in_end, this->end());
this->set_size(this->size() + NumInputs);
}
/// Append \p NumInputs copies of \p Elt to the end.
- void append(size_type NumInputs, const T &Elt) {
- if (NumInputs > this->capacity() - this->size())
- this->grow(this->size()+NumInputs);
-
- std::uninitialized_fill_n(this->end(), NumInputs, Elt);
+ void append(size_type NumInputs, ValueParamT Elt) {
+ const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
+ std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
this->set_size(this->size() + NumInputs);
}
@@ -410,18 +628,19 @@
// re-initializing them - for all assign(...) variants.
void assign(size_type NumElts, const T &Elt) {
+ this->assertSafeToReferenceAfterResize(&Elt, 0);
clear();
- if (this->capacity() < NumElts)
- this->grow(NumElts);
+ this->reserve(NumElts);
this->set_size(NumElts);
std::uninitialized_fill(this->begin(), this->end(), Elt);
}
template <typename in_iter,
- typename = typename std::enable_if<std::is_convertible<
+ typename = std::enable_if_t<std::is_convertible<
typename std::iterator_traits<in_iter>::iterator_category,
- std::input_iterator_tag>::value>::type>
+ std::input_iterator_tag>::value>>
void assign(in_iter in_start, in_iter in_end) {
+ this->assertSafeToReferenceAfterClear(in_start, in_end);
clear();
append(in_start, in_end);
}
@@ -435,8 +654,7 @@
// Just cast away constness because this is a non-const member function.
iterator I = const_cast<iterator>(CI);
- assert(I >= this->begin() && "Iterator to erase is out of bounds.");
- assert(I < this->end() && "Erasing at past-the-end iterator.");
+ assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.");
iterator N = I;
// Shift all elts down one.
@@ -451,9 +669,7 @@
iterator S = const_cast<iterator>(CS);
iterator E = const_cast<iterator>(CE);
- assert(S >= this->begin() && "Range to erase is out of bounds.");
- assert(S <= E && "Trying to erase invalid range.");
- assert(E <= this->end() && "Trying to erase past the end.");
+ assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.");
iterator N = S;
// Shift all elts down.
@@ -464,20 +680,26 @@
return(N);
}
- iterator insert(iterator I, T &&Elt) {
+private:
+ template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
+ // Callers ensure that ArgType is derived from T.
+ static_assert(
+ std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
+ T>::value,
+ "ArgType must be derived from T!");
+
if (I == this->end()) { // Important special case for empty vector.
- this->push_back(::std::move(Elt));
+ this->push_back(::std::forward<ArgType>(Elt));
return this->end()-1;
}
- assert(I >= this->begin() && "Insertion iterator is out of bounds.");
- assert(I <= this->end() && "Inserting past the end of the vector.");
+ assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
- if (this->size() >= this->capacity()) {
- size_t EltNo = I-this->begin();
- this->grow();
- I = this->begin()+EltNo;
- }
+ // Grow if necessary.
+ size_t Index = I - this->begin();
+ std::remove_reference_t<ArgType> *EltPtr =
+ this->reserveForParamAndGetAddress(Elt);
+ I = this->begin() + Index;
::new ((void*) this->end()) T(::std::move(this->back()));
// Push everything else over.
@@ -485,45 +707,26 @@
this->set_size(this->size() + 1);
// If we just moved the element we're inserting, be sure to update
- // the reference.
- T *EltPtr = &Elt;
- if (I <= EltPtr && EltPtr < this->end())
+ // the reference (never happens if TakesParamByValue).
+ static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
+ "ArgType must be 'T' when taking by value!");
+ if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
++EltPtr;
- *I = ::std::move(*EltPtr);
+ *I = ::std::forward<ArgType>(*EltPtr);
return I;
}
+public:
+ iterator insert(iterator I, T &&Elt) {
+ return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
+ }
+
iterator insert(iterator I, const T &Elt) {
- if (I == this->end()) { // Important special case for empty vector.
- this->push_back(Elt);
- return this->end()-1;
- }
-
- assert(I >= this->begin() && "Insertion iterator is out of bounds.");
- assert(I <= this->end() && "Inserting past the end of the vector.");
-
- if (this->size() >= this->capacity()) {
- size_t EltNo = I-this->begin();
- this->grow();
- I = this->begin()+EltNo;
- }
- ::new ((void*) this->end()) T(std::move(this->back()));
- // Push everything else over.
- std::move_backward(I, this->end()-1, this->end());
- this->set_size(this->size() + 1);
-
- // If we just moved the element we're inserting, be sure to update
- // the reference.
- const T *EltPtr = &Elt;
- if (I <= EltPtr && EltPtr < this->end())
- ++EltPtr;
-
- *I = *EltPtr;
- return I;
+ return insert_one_impl(I, this->forward_value_param(Elt));
}
- iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
+ iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
// Convert iterator to elt# to avoid invalidating iterator when we reserve()
size_t InsertElt = I - this->begin();
@@ -532,11 +735,11 @@
return this->begin()+InsertElt;
}
- assert(I >= this->begin() && "Insertion iterator is out of bounds.");
- assert(I <= this->end() && "Inserting past the end of the vector.");
+ assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
- // Ensure there is enough space.
- reserve(this->size() + NumToInsert);
+ // Ensure there is enough space, and get the (maybe updated) address of
+ // Elt.
+ const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
// Uninvalidate the iterator.
I = this->begin()+InsertElt;
@@ -553,7 +756,12 @@
// Copy the existing elements that get replaced.
std::move_backward(I, OldEnd-NumToInsert, OldEnd);
- std::fill_n(I, NumToInsert, Elt);
+ // If we just moved the element we're inserting, be sure to update
+ // the reference (never happens if TakesParamByValue).
+ if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
+ EltPtr += NumToInsert;
+
+ std::fill_n(I, NumToInsert, *EltPtr);
return I;
}
@@ -566,18 +774,23 @@
size_t NumOverwritten = OldEnd-I;
this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
+ // If we just moved the element we're inserting, be sure to update
+ // the reference (never happens if TakesParamByValue).
+ if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
+ EltPtr += NumToInsert;
+
// Replace the overwritten part.
- std::fill_n(I, NumOverwritten, Elt);
+ std::fill_n(I, NumOverwritten, *EltPtr);
// Insert the non-overwritten middle part.
- std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
+ std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
return I;
}
template <typename ItTy,
- typename = typename std::enable_if<std::is_convertible<
+ typename = std::enable_if_t<std::is_convertible<
typename std::iterator_traits<ItTy>::iterator_category,
- std::input_iterator_tag>::value>::type>
+ std::input_iterator_tag>::value>>
iterator insert(iterator I, ItTy From, ItTy To) {
// Convert iterator to elt# to avoid invalidating iterator when we reserve()
size_t InsertElt = I - this->begin();
@@ -587,8 +800,10 @@
return this->begin()+InsertElt;
}
- assert(I >= this->begin() && "Insertion iterator is out of bounds.");
- assert(I <= this->end() && "Inserting past the end of the vector.");
+ assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.");
+
+ // Check that the reserve that follows doesn't invalidate the iterators.
+ this->assertSafeToAddRange(From, To);
size_t NumToInsert = std::distance(From, To);
@@ -639,6 +854,7 @@
}
template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
+ this->assertSafeToEmplace(Args...);
if (LLVM_UNLIKELY(this->size() >= this->capacity()))
this->grow();
::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
@@ -675,10 +891,8 @@
std::swap(this->Capacity, RHS.Capacity);
return;
}
- if (RHS.size() > this->capacity())
- this->grow(RHS.size());
- if (this->size() > RHS.capacity())
- RHS.grow(this->size());
+ this->reserve(RHS.size());
+ RHS.reserve(this->size());
// Swap the shared elements.
size_t NumShared = this->size();
@@ -733,8 +947,7 @@
// FIXME: don't do this if they're efficiently moveable.
if (this->capacity() < RHSSize) {
// Destroy current elements.
- this->destroy_range(this->begin(), this->end());
- this->set_size(0);
+ this->clear();
CurSize = 0;
this->grow(RHSSize);
} else if (CurSize) {
@@ -793,8 +1006,7 @@
// elements.
if (this->capacity() < RHSSize) {
// Destroy current elements.
- this->destroy_range(this->begin(), this->end());
- this->set_size(0);
+ this->clear();
CurSize = 0;
this->grow(RHSSize);
} else if (CurSize) {
@@ -817,13 +1029,71 @@
/// to avoid allocating unnecessary storage.
template <typename T, unsigned N>
struct SmallVectorStorage {
- AlignedCharArrayUnion<T> InlineElts[N];
+ alignas(T) char InlineElts[N * sizeof(T)];
};
/// We need the storage to be properly aligned even for small-size of 0 so that
/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
/// well-defined.
-template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
+template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
+
+/// Forward declaration of SmallVector so that
+/// calculateSmallVectorDefaultInlinedElements can reference
+/// `sizeof(SmallVector<T, 0>)`.
+template <typename T, unsigned N> class LLVM_GSL_OWNER SmallVector;
+
+/// Helper class for calculating the default number of inline elements for
+/// `SmallVector<T>`.
+///
+/// This should be migrated to a constexpr function when our minimum
+/// compiler support is enough for multi-statement constexpr functions.
+template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
+ // Parameter controlling the default number of inlined elements
+ // for `SmallVector<T>`.
+ //
+ // The default number of inlined elements ensures that
+ // 1. There is at least one inlined element.
+ // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
+ // it contradicts 1.
+ static constexpr size_t kPreferredSmallVectorSizeof = 64;
+
+ // static_assert that sizeof(T) is not "too big".
+ //
+ // Because our policy guarantees at least one inlined element, it is possible
+ // for an arbitrarily large inlined element to allocate an arbitrarily large
+ // amount of inline storage. We generally consider it an antipattern for a
+ // SmallVector to allocate an excessive amount of inline storage, so we want
+ // to call attention to these cases and make sure that users are making an
+ // intentional decision if they request a lot of inline storage.
+ //
+ // We want this assertion to trigger in pathological cases, but otherwise
+ // not be too easy to hit. To accomplish that, the cutoff is actually somewhat
+ // larger than kPreferredSmallVectorSizeof (otherwise,
+ // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
+ // pattern seems useful in practice).
+ //
+ // One wrinkle is that this assertion is in theory non-portable, since
+ // sizeof(T) is in general platform-dependent. However, we don't expect this
+ // to be much of an issue, because most LLVM development happens on 64-bit
+ // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
+ // 32-bit hosts, dodging the issue. The reverse situation, where development
+ // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
+ // 64-bit host, is expected to be very rare.
+ static_assert(
+ sizeof(T) <= 256,
+ "You are trying to use a default number of inlined elements for "
+ "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
+ "explicit number of inlined elements with `SmallVector<T, N>` to make "
+ "sure you really want that much inline storage.");
+
+ // Discount the size of the header itself when calculating the maximum inline
+ // bytes.
+ static constexpr size_t PreferredInlineBytes =
+ kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
+ static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
+ static constexpr size_t value =
+ NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
+};
/// This is a 'vector' (really, a variable-sized array), optimized
/// for the case when the array is small. It contains some number of elements
@@ -831,10 +1101,20 @@
/// elements is below that threshold. This allows normal "small" cases to be
/// fast without losing generality for large inputs.
///
-/// Note that this does not attempt to be exception safe.
+/// \note
+/// In the absence of a well-motivated choice for the number of inlined
+/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
+/// omitting the \p N). This will choose a default number of inlined elements
+/// reasonable for allocation on the stack (for example, trying to keep \c
+/// sizeof(SmallVector<T>) around 64 bytes).
///
-template <typename T, unsigned N>
-class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {
+/// \warning This does not attempt to be exception safe.
+///
+/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
+template <typename T,
+ unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
+class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl<T>,
+ SmallVectorStorage<T, N> {
public:
SmallVector() : SmallVectorImpl<T>(N) {}
@@ -849,9 +1129,9 @@
}
template <typename ItTy,
- typename = typename std::enable_if<std::is_convertible<
+ typename = std::enable_if_t<std::is_convertible<
typename std::iterator_traits<ItTy>::iterator_category,
- std::input_iterator_tag>::value>::type>
+ std::input_iterator_tag>::value>>
SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
this->append(S, E);
}
@@ -871,7 +1151,7 @@
SmallVectorImpl<T>::operator=(RHS);
}
- const SmallVector &operator=(const SmallVector &RHS) {
+ SmallVector &operator=(const SmallVector &RHS) {
SmallVectorImpl<T>::operator=(RHS);
return *this;
}
@@ -886,17 +1166,17 @@
SmallVectorImpl<T>::operator=(::std::move(RHS));
}
- const SmallVector &operator=(SmallVector &&RHS) {
+ SmallVector &operator=(SmallVector &&RHS) {
SmallVectorImpl<T>::operator=(::std::move(RHS));
return *this;
}
- const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
+ SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
SmallVectorImpl<T>::operator=(::std::move(RHS));
return *this;
}
- const SmallVector &operator=(std::initializer_list<T> IL) {
+ SmallVector &operator=(std::initializer_list<T> IL) {
this->assign(IL);
return *this;
}
@@ -907,6 +1187,17 @@
return X.capacity_in_bytes();
}
+/// Given a range of type R, iterate the entire range and return a
+/// SmallVector with elements of the vector. This is useful, for example,
+/// when you want to iterate a range and then sort the results.
+template <unsigned Size, typename R>
+SmallVector<typename std::remove_const<typename std::remove_reference<
+ decltype(*std::begin(std::declval<R &>()))>::type>::type,
+ Size>
+to_vector(R &&Range) {
+ return {std::begin(Range), std::end(Range)};
+}
+
} // end namespace llvm
namespace std {