14#ifndef LLVM_ADT_SMALLVECTOR_H
15#define LLVM_ADT_SMALLVECTOR_H
27#include <initializer_list>
41template <
class Iterator,
class Tag>
43 typename std::iterator_traits<Iterator>::iterator_category,
Tag>;
45template <
class Iterator>
47 std::enable_if_t<HasIteratorTag<Iterator, std::input_iterator_tag>::value>;
64 return std::numeric_limits<Size_T>::max();
95 Size =
static_cast<Size_T
>(
N);
111 std::conditional_t<
sizeof(
T) < 4 &&
sizeof(
void *) >= 8,
uint64_t,
124template <
typename T,
typename =
void>
134 return const_cast<void *
>(
reinterpret_cast<const void *
>(
135 reinterpret_cast<const char *
>(
this) +
161 std::less<> LessThan;
174 std::less<> LessThan;
176 !LessThan(this->
end(), Last);
187 if (NewSize <= this->
size())
188 return Elt < this->
begin() + NewSize;
197 "Attempting to reference an element of the vector in an operation "
198 "that invalidates it");
208 template <
class ItTy>
210 if constexpr (std::is_pointer_v<ItTy> &&
212 std::remove_const_t<std::remove_pointer_t<ItTy>>,
213 std::remove_const_t<T>>) {
225 if constexpr (std::is_pointer_v<ItTy> &&
226 std::is_same_v<std::remove_cv_t<std::remove_pointer_t<ItTy>>,
242 size_t NewSize = This->size() +
N;
246 bool ReferencesStorage =
false;
248 if (!U::TakesParamByValue) {
250 ReferencesStorage =
true;
251 Index = &Elt - This->begin();
255 return ReferencesStorage ? This->begin() + Index : &Elt;
343template <
typename T,
bool = (std::is_trivially_copy_constructible<T>::value) &&
344 (std::is_trivially_move_constructible<T>::value) &&
345 std::is_trivially_destructible<T>::value>
365 template<
typename It1,
typename It2>
367 std::uninitialized_move(
I,
E, Dest);
372 template<
typename It1,
typename It2>
374 std::uninitialized_copy(
I,
E, Dest);
402 return const_cast<T *
>(
413 std::uninitialized_fill_n(NewElts, NumElts, Elt);
423 ::new ((
void *)(NewElts + this->
size()))
T(std::forward<ArgTypes>(Args)...);
433 ::new ((
void *)this->
end())
T(*EltPtr);
439 ::new ((
void *)this->
end())
T(::std::move(*EltPtr));
450template <
typename T,
bool TriviallyCopyable>
458template <
typename T,
bool TriviallyCopyable>
461 size_t MinSize,
size_t &NewCapacity) {
462 return static_cast<T *
>(
464 this->
getFirstEl(), MinSize,
sizeof(
T), NewCapacity));
468template <
typename T,
bool TriviallyCopyable>
479template <
typename T,
bool TriviallyCopyable>
481 T *NewElts,
size_t NewCapacity) {
504 using ValueParamT = std::conditional_t<TakesParamByValue, T, const T &>;
514 template <
typename It1,
typename It2>
522 template <
typename It1,
typename It2>
524 if constexpr (std::is_pointer_v<It1> && std::is_pointer_v<It2> &&
526 std::remove_const_t<std::remove_pointer_t<It1>>,
527 std::remove_pointer_t<It2>>) {
533 std::memcpy(
reinterpret_cast<void *
>(Dest),
I, (
E -
I) *
sizeof(
T));
536 std::uninitialized_copy(
I,
E, Dest);
553 return const_cast<T *
>(
565 std::uninitialized_fill_n(this->
begin(), NumElts, Elt);
573 push_back(
T(std::forward<ArgTypes>(Args)...));
583 std::memcpy(
reinterpret_cast<void *
>(this->
end()), &Tmp,
sizeof(
T));
591 std::memcpy(
reinterpret_cast<void *
>(this->
end()), &Elt,
sizeof(
T));
629 assert(this->
empty() &&
"move construction requires an empty vector");
630 if (!
RHS.isSmall()) {
663 template <
bool ForOverwrite>
void resizeImpl(size_type
N) {
664 if (
N == this->
size())
673 for (
auto I = this->
end(),
E = this->
begin() + N;
I !=
E; ++
I)
689 assert(this->
size() >= N &&
"Cannot increase size with truncate");
695 if (
N == this->
size())
718 T Result = ::std::move(this->
back());
726 template <
typename ItTy,
typename = EnableIfConvertibleToInputIterator<ItTy>>
730 size_type NumInputs = std::distance(in_start, in_end);
736 for (; in_start != in_end; ++in_start)
744 std::uninitialized_fill_n(this->
end(), NumInputs, *EltPtr);
748 void append(std::initializer_list<T> IL) {
749 append(IL.begin(), IL.end());
762 std::fill_n(this->
begin(), std::min(NumElts, this->
size()), Elt);
763 if (NumElts > this->
size())
764 std::uninitialized_fill_n(this->
end(), NumElts - this->
size(), Elt);
765 else if (NumElts < this->
size())
773 template <
typename ItTy,
typename = EnableIfConvertibleToInputIterator<ItTy>>
780 void assign(std::initializer_list<T> IL) {
787 template <
typename U,
788 typename = std::enable_if_t<std::is_convertible_v<U, T>>>
801 std::move(
I+1, this->
end(), I);
827 std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
829 "ArgType must be derived from T!");
831 if (
I == this->
end()) {
832 this->
push_back(::std::forward<ArgType>(Elt));
833 return this->
end()-1;
839 size_t Index =
I - this->
begin();
840 std::remove_reference_t<ArgType> *EltPtr =
842 I = this->
begin() + Index;
846 std::move_backward(
I, this->
end()-1, this->
end());
852 "ArgType must be 'T' when taking by value!");
856 *
I = ::
std::forward<ArgType>(*EltPtr);
871 size_t InsertElt =
I - this->
begin();
873 if (I == this->
end()) {
875 return this->
begin()+InsertElt;
885 I = this->
begin()+InsertElt;
891 if (
size_t(this->
end()-I) >= NumToInsert) {
892 T *OldEnd = this->
end();
893 append(std::move_iterator<iterator>(this->
end() - NumToInsert),
894 std::move_iterator<iterator>(this->
end()));
897 std::move_backward(
I, OldEnd-NumToInsert, OldEnd);
902 EltPtr += NumToInsert;
904 std::fill_n(
I, NumToInsert, *EltPtr);
912 T *OldEnd = this->
end();
914 size_t NumOverwritten = OldEnd-
I;
920 EltPtr += NumToInsert;
923 std::fill_n(
I, NumOverwritten, *EltPtr);
926 std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
930 template <
typename ItTy,
typename = EnableIfConvertibleToInputIterator<ItTy>>
933 size_t InsertElt =
I - this->
begin();
935 if (I == this->
end()) {
937 return this->
begin()+InsertElt;
942 size_t OldSize = this->
size();
944 I = this->
begin() + InsertElt;
945 std::rotate(
I, this->
begin() + OldSize, this->
end());
954 size_t NumToInsert = std::distance(From, To);
960 I = this->
begin()+InsertElt;
966 if (
size_t(this->
end()-I) >= NumToInsert) {
967 T *OldEnd = this->
end();
968 append(std::move_iterator<iterator>(this->
end() - NumToInsert),
969 std::move_iterator<iterator>(this->
end()));
972 std::move_backward(
I, OldEnd-NumToInsert, OldEnd);
974 std::copy(From, To,
I);
982 T *OldEnd = this->
end();
984 size_t NumOverwritten = OldEnd-
I;
988 for (
T *J =
I; NumOverwritten > 0; --NumOverwritten) {
999 insert(
I, IL.begin(), IL.end());
1006 ::new ((
void *)this->
end())
T(std::forward<ArgTypes>(Args)...);
1008 return this->
back();
1016 if (this->
size() != RHS.
size())
return false;
1020 return !(*
this ==
RHS);
1024 return std::lexicographical_compare(this->
begin(), this->
end(),
1032template <
typename T>
1034 if (
this == &
RHS)
return;
1047 size_t NumShared = this->
size();
1048 if (NumShared >
RHS.size()) NumShared =
RHS.size();
1049 for (
size_type i = 0; i != NumShared; ++i)
1054 size_t EltDiff = this->
size() - RHS.
size();
1056 RHS.set_size(
RHS.size() + EltDiff);
1059 }
else if (
RHS.size() > this->size()) {
1060 size_t EltDiff =
RHS.size() - this->
size();
1064 RHS.set_size(NumShared);
1068template <
typename T>
1072 if (
this == &
RHS)
return *
this;
1076 size_t RHSSize =
RHS.size();
1077 size_t CurSize = this->
size();
1078 if (CurSize >= RHSSize) {
1082 NewEnd = std::copy(
RHS.begin(),
RHS.begin()+RHSSize, this->begin());
1084 NewEnd = this->
begin();
1101 this->
grow(RHSSize);
1102 }
else if (CurSize) {
1104 std::copy(
RHS.begin(),
RHS.begin()+CurSize, this->begin());
1109 this->begin()+CurSize);
1116template <
typename T>
1119 if (
this == &
RHS)
return *
this;
1122 if (!
RHS.isSmall()) {
1129 size_t RHSSize =
RHS.size();
1130 size_t CurSize = this->
size();
1131 if (CurSize >= RHSSize) {
1135 NewEnd = std::move(
RHS.begin(),
RHS.end(), NewEnd);
1155 this->
grow(RHSSize);
1156 }
else if (CurSize) {
1158 std::move(
RHS.begin(),
RHS.begin()+CurSize, this->begin());
1163 this->begin()+CurSize);
1174template <
typename T,
unsigned N>
1235 "You are trying to use a default number of inlined elements for "
1236 "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1237 "explicit number of inlined elements with `SmallVector<T, N>` to make "
1238 "sure you really want that much inline storage.");
1265template <
typename T,
1285 template <
typename Tag,
1286 typename = std::enable_if_t<std::is_same_v<Tag, for_overwrite_t>>>
1291 template <
typename ItTy,
typename = EnableIfConvertibleToInputIterator<ItTy>>
1296 template <
typename RangeTy>
1306 template <
typename U,
1307 typename = std::enable_if_t<std::is_convertible_v<U, T>>>
1329 bool StoleAllocation = N > 0 && !RHS.isSmall();
1330 if constexpr (std::is_trivially_move_assignable_v<T>)
1331 SmallVectorImpl<T>::operator=(::std::move(RHS));
1333 this->moveConstructFrom(::std::move(RHS));
1334 if constexpr (N > 0) {
1335 if (StoleAllocation)
1336 RHS.set_allocation_range(RHS.begin(), N);
1343 if constexpr (std::is_trivially_move_assignable_v<T>)
1344 SmallVectorImpl<T>::operator=(::std::move(RHS));
1346 this->moveConstructFrom(::std::move(RHS));
1352 bool StoleAllocation =
this != &
RHS && !
RHS.isSmall();
1355 if (StoleAllocation)
1356 RHS.set_allocation_range(
RHS.begin(),
N);
1383template <
typename T,
unsigned N>
1385 return X.capacity_in_bytes();
1388template <
typename RangeType>
1390 std::remove_const_t<detail::ValueOfRange<RangeType>>;
1395template <
unsigned Size,
typename R>
1400template <
typename R>
1406template <
typename Out,
unsigned Size,
typename R>
1417#if SIZE_MAX > UINT32_MAX
1438 template<
typename T>
1445 template<
typename T,
unsigned N>
Ops append({Chain, DAG.getConstant(SVEStores[NumParts - 2], DL, MVT::i32)})
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_UNLIKELY(EXPR)
#define LLVM_GSL_OWNER
LLVM_GSL_OWNER - Apply this to owning classes like SmallVector to enable lifetime warnings.
#define LLVM_NO_SANITIZE_CFI_UNRELATED_CAST
\macro LLVM_NO_SANITIZE_CFI_UNRELATED_CAST Disable Clang's cfi-unrelated-cast check for a function (e...
#define LLVM_ATTRIBUTE_NOINLINE
LLVM_ATTRIBUTE_NOINLINE - On compilers where we have a directive to do so, mark a method "not for inl...
#define LLVM_LIKELY(EXPR)
This file defines DenseMapInfo traits for DenseMap.
#define offsetof(TYPE, MEMBER)
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
Represent a constant reference to an array (0 or more elements consecutively in memory),...
This is all the stuff common to all SmallVectors.
LLVM_ABI void grow_pod(void *FirstEl, size_t MinSize, size_t TSize)
This is an implementation of the grow() method which only works on POD-like data types and is out of ...
LLVM_ABI void * mallocForGrow(void *FirstEl, size_t MinSize, size_t TSize, size_t &NewCapacity)
This is a helper for grow() that's out of line to reduce code duplication.
void set_allocation_range(void *Begin, size_t N)
Set the array data pointer to Begin and capacity to N.
SmallVectorSizeType< T > Capacity
SmallVectorSizeType< T > Size
SmallVectorBase(void *FirstEl, size_t TotalCapacity)
void set_size(size_t N)
Set the array size to N, which the current array must have enough capacity for.
static constexpr size_t SizeTypeMax()
The maximum value of the Size_T used.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void moveConstructFrom(SmallVectorImpl &&RHS)
void resize_for_overwrite(size_type N)
Like resize, but T is POD, the new values won't be initialized.
void append(const SmallVectorImpl &RHS)
void pop_back_n(size_type NumItems)
void assign(const SmallVectorImpl &RHS)
SmallVectorImpl(const SmallVectorImpl &)=delete
void assign(size_type NumElts, ValueParamT Elt)
reference emplace_back(ArgTypes &&... Args)
bool operator==(const SmallVectorImpl &RHS) const
void reserve(size_type N)
typename SuperClass::reference reference
iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt)
iterator erase(const_iterator CI)
iterator insert(iterator I, ItTy From, ItTy To)
typename SuperClass::const_iterator const_iterator
void assignRemote(SmallVectorImpl &&RHS)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void resize(size_type N, ValueParamT NV)
iterator insert(iterator I, MemoryLocation &&Elt)
bool operator>(const SmallVectorImpl &RHS) const
bool operator<(const SmallVectorImpl &RHS) const
iterator erase(const_iterator CS, const_iterator CE)
bool operator!=(const SmallVectorImpl &RHS) const
void truncate(size_type N)
Like resize, but requires that N is less than size().
void assign(ItTy in_start, ItTy in_end)
void assign(std::initializer_list< T > IL)
void assign(ArrayRef< U > AR)
SmallVectorImpl(unsigned N)
void swap(SmallVectorImpl &RHS)
typename SuperClass::iterator iterator
bool operator<=(const SmallVectorImpl &RHS) const
typename SuperClass::size_type size_type
void append(std::initializer_list< T > IL)
void append(size_type NumInputs, ValueParamT Elt)
Append NumInputs copies of Elt to the end.
SmallVectorImpl & operator=(const SmallVectorImpl &RHS)
void insert(iterator I, std::initializer_list< T > IL)
SmallVectorImpl & operator=(SmallVectorImpl &&RHS)
typename SuperClass::ValueParamT ValueParamT
bool operator>=(const SmallVectorImpl &RHS) const
iterator insert(iterator I, const T &Elt)
static void uninitialized_copy(It1 I, It1 E, It2 Dest)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
static void uninitialized_move(It1 I, It1 E, It2 Dest)
Move the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
std::conditional_t< TakesParamByValue, T, const T & > ValueParamT
Either const T& or T, depending on whether it's cheap enough to take parameters by value.
const T * reserveForParamAndGetAddress(const T &Elt, size_t N=1)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
void push_back(ValueParamT Elt)
SmallVectorTemplateBase(size_t SizeArg)
static void destroy_range(T *, T *)
T * reserveForParamAndGetAddress(T &Elt, size_t N=1)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
static ValueParamT forward_value_param(ValueParamT V)
Copy V or return a reference, depending on ValueParamT.
T & growAndEmplaceBack(ArgTypes &&... Args)
static constexpr bool TakesParamByValue
True if it's cheap enough to take parameters by value.
void growAndAssign(size_t NumElts, T Elt)
void grow(size_t MinSize=0)
Double the size of the allocated memory, guaranteeing space for at least one more element or MinSize ...
LLVM_ATTRIBUTE_NOINLINE void growAndPushBack(ValueParamT Elt)
void moveElementsForGrow(T *NewElts)
Move existing elements over to the new allocation NewElts, the middle section of grow().
static void uninitialized_copy(It1 I, It1 E, It2 Dest)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements as ne...
static T && forward_value_param(T &&V)
T * mallocForGrow(size_t MinSize, size_t &NewCapacity)
Create a new allocation big enough for MinSize and pass back its size in NewCapacity.
static void destroy_range(T *S, T *E)
static constexpr bool TakesParamByValue
T * reserveForParamAndGetAddress(T &Elt, size_t N=1)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
void takeAllocationForGrow(T *NewElts, size_t NewCapacity)
Transfer ownership of the allocation, finishing up grow().
void growAndAssign(size_t NumElts, const T &Elt)
static const T & forward_value_param(const T &V)
static void uninitialized_move(It1 I, It1 E, It2 Dest)
Move the range [I, E) into the uninitialized memory starting with "Dest", constructing elements as ne...
void grow(size_t MinSize=0)
Grow the allocated memory (without initializing new elements), doubling the size of the allocated mem...
const T * reserveForParamAndGetAddress(const T &Elt, size_t N=1)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
SmallVectorTemplateBase(size_t SizeArg)
T & growAndEmplaceBack(ArgTypes &&... Args)
void push_back(const T &Elt)
bool isSmall() const
Return true if this is a smallvector which has not had dynamic memory allocated for it.
const_iterator end() const
reverse_iterator rbegin()
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST const_iterator begin() const
static const T * reserveForParamAndGetAddressImpl(U *This, const T &Elt, size_t N)
Reserve enough space to add one element, and return the updated element pointer in case it was a refe...
const T & const_reference
SmallVectorTemplateCommon(size_t SizeArg)
const_reference operator[](size_type idx) const
void resetToSmall()
Put this vector in a state of being small.
bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize)
Return true unless Elt will be invalidated by resizing the vector to NewSize.
std::reverse_iterator< const_iterator > const_reverse_iterator
pointer data()
Return a pointer to the vector's buffer, even if empty().
bool isReferenceToRange(const void *V, const void *First, const void *Last) const
Return true if V is an internal reference to the given range.
void grow_pod(size_t MinSize, size_t TSize)
const_reverse_iterator rbegin() const
reference operator[](size_type idx)
size_t capacity_in_bytes() const
size_type size_in_bytes() const
ptrdiff_t difference_type
size_type max_size() const
bool isReferenceToStorage(const void *V) const
Return true if V is an internal reference to this vector.
const_reference back() const
bool isRangeInStorage(const void *First, const void *Last) const
Return true if First and Last form a valid (possibly empty) range in this vector's storage.
const_reference front() const
void assertSafeToAdd(const void *Elt, size_t N=1)
Check whether Elt will be invalidated by increasing the size of the vector by N.
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize)
Check whether Elt will be invalidated by resizing the vector to NewSize.
void assertSafeToAddRange(ItTy From, ItTy To)
Check whether any part of the range will be invalidated by growing.
std::reverse_iterator< iterator > reverse_iterator
void assertSafeToReferenceAfterClear(ItTy From, ItTy To)
Check whether any part of the range will be invalidated by clearing.
const_reverse_iterator rend() const
const_pointer data() const
Return a pointer to the vector's buffer, even if empty().
void * getFirstEl() const
Find the address of the first element.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SmallVector(std::initializer_list< T > IL)
SmallVector(size_t SizeArg, Tag)
SmallVector(SmallVectorImpl< T > &&RHS)
SmallVector(ArrayRef< U > A)
SmallVector & operator=(const SmallVector &RHS)
SmallVector(const iterator_range< RangeTy > &R)
SmallVector & operator=(std::initializer_list< T > IL)
SmallVector(ItTy S, ItTy E)
SmallVector(size_t SizeArg)
SmallVector(SmallVector &&RHS)
SmallVector & operator=(SmallVector &&RHS)
SmallVector(size_t SizeArg, const T &Value)
SmallVector(const SmallVector &RHS)
SmallVector & operator=(SmallVectorImpl< T > &&RHS)
LLVM Value Representation.
A range adaptor for a pair of iterators.
This is an optimization pass for GlobalISel generic memory operations.
std::remove_const_t< detail::ValueOfRange< RangeType > > ValueTypeFromRangeType
constexpr auto adl_begin(RangeT &&range) -> decltype(adl_detail::begin_impl(std::forward< RangeT >(range)))
Returns the begin iterator to range using std::begin and function found through Argument-Dependent Lo...
std::enable_if_t< HasIteratorTag< Iterator, std::input_iterator_tag >::value > EnableIfConvertibleToInputIterator
std::is_convertible< typename std::iterator_traits< Iterator >::iterator_category, Tag > HasIteratorTag
constexpr auto adl_end(RangeT &&range) -> decltype(adl_detail::end_impl(std::forward< RangeT >(range)))
Returns the end iterator to range using std::end and functions found through Argument-Dependent Looku...
constexpr for_overwrite_t for_overwrite
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
std::conditional_t< sizeof(T)< 4 &&sizeof(void *) >=8, uint64_t, uint32_t > SmallVectorSizeType
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
SmallVector< Out, Size > to_vector_of(R &&Range)
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Helper class for calculating the default number of inline elements for SmallVector<T>.
static constexpr size_t kPreferredSmallVectorSizeof
static constexpr size_t value
static constexpr size_t NumElementsThatFit
static constexpr size_t PreferredInlineBytes
static bool isEqual(const SmallVector< T, N > &LHS, const SmallVector< T, N > &RHS)
static unsigned getHashValue(const SmallVector< T, N > &V)
An information struct used to provide DenseMap with the various necessary components for a given valu...
Figure out the offset of the first element.
char Base[sizeof(SmallVectorBase< SmallVectorSizeType< T > >)]
Storage for the SmallVector elements.
char InlineElts[N *sizeof(T)]
A tag for constructors that leave new elements default-initialized, like resize_for_overwrite.
for_overwrite_t()=default