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//===----------------------------------------------------------------------===// 10/// This file defines the SmallVector class. 12//===----------------------------------------------------------------------===// 14#ifndef LLVM_ADT_SMALLVECTOR_H 15#define LLVM_ADT_SMALLVECTOR_H 25#include <initializer_list> 39template <
class Iterator>
41typename std::iterator_traits<Iterator>::iterator_category,
42 std::input_iterator_tag>
::value>;
44/// This is all the stuff common to all SmallVectors. 46/// The template parameter specifies the type which should be used to hold the 47/// Size and Capacity of the SmallVector, so it can be adjusted. 48/// Using 32 bit size is desirable to shrink the size of the SmallVector. 49/// Using 64 bit size is desirable for cases like SmallVector<char>, where a 50/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for 51/// buffering bitcode output - which can exceed 4GB. 57 /// The maximum value of the Size_T used. 59return std::numeric_limits<Size_T>::max();
66 /// This is a helper for \a grow() that's out of line to reduce code 67 /// duplication. This function will report a fatal error if it can't grow at 68 /// least to \p MinSize. 72 /// This is an implementation of the grow() method which only works 73 /// on POD-like data types and is out of line to reduce code duplication. 74 /// This function will report a fatal error if it cannot increase capacity. 75voidgrow_pod(
void *FirstEl,
size_t MinSize,
size_t TSize);
84 /// Set the array size to \p N, which the current array must have enough 87 /// This does not construct or destroy any elements in the vector. 90Size =
static_cast<Size_T
>(
N);
93 /// Set the array data pointer to \p Begin and capacity to \p N. 95 /// This does not construct or destroy any elements in the vector. 96// This does not clean up any existing allocation. 106 std::conditional_t<
sizeof(
T) < 4 &&
sizeof(
void *) >= 8,
uint64_t,
109/// Figure out the offset of the first element. 116/// This is the part of SmallVectorTemplateBase which does not depend on whether 117/// the type T is a POD. The extra dummy template argument is used by ArrayRef 118/// to avoid unnecessarily requiring T to be complete. 119template <
typename T,
typename =
void>
125 /// Find the address of the first element. For this pointer math to be valid 126 /// with small-size of 0 for T with lots of alignment, it's important that 127 /// SmallVectorStorage is properly-aligned even for small-size of 0. 129returnconst_cast<void *
>(
reinterpret_cast<constvoid *
>(
130reinterpret_cast<constchar *
>(
this) +
133// Space after 'FirstEl' is clobbered, do not add any instance vars after it. 141 /// Return true if this is a smallvector which has not had dynamic 142 /// memory allocated for it. 145 /// Put this vector in a state of being small. 148 this->
Size = this->
Capacity = 0;
// FIXME: Setting Capacity to 0 is suspect. 151 /// Return true if V is an internal reference to the given range. 153// Use std::less to avoid UB. 154 std::less<> LessThan;
155return !LessThan(V,
First) && LessThan(V,
Last);
158 /// Return true if V is an internal reference to this vector. 163 /// Return true if First and Last form a valid (possibly empty) range in this 164 /// vector's storage. 166// Use std::less to avoid UB. 167 std::less<> LessThan;
169 !LessThan(this->
end(), Last);
172 /// Return true unless Elt will be invalidated by resizing the vector to 179// Return false if Elt will be destroyed by shrinking. 180if (NewSize <= this->
size())
181return Elt < this->
begin() + NewSize;
183// Return false if we need to grow. 187 /// Check whether Elt will be invalidated by resizing the vector to NewSize. 190"Attempting to reference an element of the vector in an operation " 191"that invalidates it");
194 /// Check whether Elt will be invalidated by increasing the size of the 200 /// Check whether any part of the range will be invalidated by clearing. 209 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>,
T *>
::value,
213 /// Check whether any part of the range will be invalidated by growing. 222 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>,
T *>
::value,
226 /// Reserve enough space to add one element, and return the updated element 227 /// pointer in case it was a reference to the storage. 231size_t NewSize = This->size() +
N;
235bool ReferencesStorage =
false;
237if (!U::TakesParamByValue) {
239 ReferencesStorage =
true;
240Index = &Elt - This->begin();
244return ReferencesStorage ? This->begin() +
Index : &Elt;
266// forward iterator creation methods. 272// reverse iterator creation methods. 285 /// Return a pointer to the vector's buffer, even if empty(). 287 /// Return a pointer to the vector's buffer, even if empty(). 318/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put 319/// method implementations that are designed to work with non-trivial T's. 321/// We approximate is_trivially_copyable with trivial move/copy construction and 322/// trivial destruction. While the standard doesn't specify that you're allowed 323/// copy these types with memcpy, there is no way for the type to observe this. 324/// This catches the important case of std::pair<POD, POD>, which is not 325/// trivially assignable. 326template <
typename T,
bool = (std::is_trivially_copy_constructible<T>::value) &&
327 (std::is_trivially_move_constructible<T>::value) &&
328 std::is_trivially_destructible<T>::value>
345 /// Move the range [I, E) into the uninitialized memory starting with "Dest", 346 /// constructing elements as needed. 347template<
typename It1,
typename It2>
349 std::uninitialized_move(
I,
E, Dest);
352 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest", 353 /// constructing elements as needed. 354template<
typename It1,
typename It2>
356 std::uninitialized_copy(
I,
E, Dest);
359 /// Grow the allocated memory (without initializing new elements), doubling 360 /// the size of the allocated memory. Guarantees space for at least one more 361 /// element, or MinSize more elements if specified. 364 /// Create a new allocation big enough for \p MinSize and pass back its size 365 /// in \p NewCapacity. This is the first section of \a grow(). 368 /// Move existing elements over to the new allocation \p NewElts, the middle 369 /// section of \a grow(). 372 /// Transfer ownership of the allocation, finishing up \a grow(). 375 /// Reserve enough space to add one element, and return the updated element 376 /// pointer in case it was a reference to the storage. 381 /// Reserve enough space to add one element, and return the updated element 382 /// pointer in case it was a reference to the storage. 384returnconst_cast<T *
>(
392// Grow manually in case Elt is an internal reference. 395 std::uninitialized_fill_n(NewElts, NumElts, Elt);
402// Grow manually in case one of Args is an internal reference. 405 ::new ((
void *)(NewElts + this->
size()))
T(std::forward<ArgTypes>(Args)...);
415 ::new ((
void *)this->
end())
T(*EltPtr);
421 ::new ((
void *)this->
end())
T(::std::move(*EltPtr));
431// Define this out-of-line to dissuade the C++ compiler from inlining it. 432template <
typename T,
bool TriviallyCopyable>
435T *NewElts = mallocForGrow(MinSize, NewCapacity);
436 moveElementsForGrow(NewElts);
437 takeAllocationForGrow(NewElts, NewCapacity);
440template <
typename T,
bool TriviallyCopyable>
442size_t MinSize,
size_t &NewCapacity) {
443returnstatic_cast<T *
>(
445 this->getFirstEl(), MinSize,
sizeof(
T), NewCapacity));
448// Define this out-of-line to dissuade the C++ compiler from inlining it. 449template <
typename T,
bool TriviallyCopyable>
452// Move the elements over. 453 this->uninitialized_move(this->begin(), this->end(), NewElts);
455// Destroy the original elements. 456 destroy_range(this->begin(), this->end());
459// Define this out-of-line to dissuade the C++ compiler from inlining it. 460template <
typename T,
bool TriviallyCopyable>
462T *NewElts,
size_t NewCapacity) {
463// If this wasn't grown from the inline copy, deallocate the old space. 467 this->set_allocation_range(NewElts, NewCapacity);
470/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put 471/// method implementations that are designed to work with trivially copyable 472/// T's. This allows using memcpy in place of copy/move construction and 473/// skipping destruction. 479 /// True if it's cheap enough to take parameters by value. Doing so avoids 480 /// overhead related to mitigations for reference invalidation. 483 /// Either const T& or T, depending on whether it's cheap enough to take 484 /// parameters by value. 485usingValueParamT = std::conditional_t<TakesParamByValue, T, const T &>;
489// No need to do a destroy loop for POD's. 492 /// Move the range [I, E) onto the uninitialized memory 493 /// starting with "Dest", constructing elements into it as needed. 494template<
typename It1,
typename It2>
500 /// Copy the range [I, E) onto the uninitialized memory 501 /// starting with "Dest", constructing elements into it as needed. 502template<
typename It1,
typename It2>
504// Arbitrary iterator types; just use the basic implementation. 505 std::uninitialized_copy(
I,
E, Dest);
508 /// Copy the range [I, E) onto the uninitialized memory 509 /// starting with "Dest", constructing elements into it as needed. 510template <
typename T1,
typename T2>
513 std::enable_if_t<std::is_same<std::remove_const_t<T1>, T2>
::value> * =
515// Use memcpy for PODs iterated by pointers (which includes SmallVector 516// iterators): std::uninitialized_copy optimizes to memmove, but we can 517// use memcpy here. Note that I and E are iterators and thus might be 518// invalid for memcpy if they are equal. 520 memcpy(
reinterpret_cast<void *
>(Dest),
I, (
E -
I) *
sizeof(
T));
523 /// Double the size of the allocated memory, guaranteeing space for at 524 /// least one more element or MinSize if specified. 527 /// Reserve enough space to add one element, and return the updated element 528 /// pointer in case it was a reference to the storage. 533 /// Reserve enough space to add one element, and return the updated element 534 /// pointer in case it was a reference to the storage. 536returnconst_cast<T *
>(
540 /// Copy \p V or return a reference, depending on \a ValueParamT. 544// Elt has been copied in case it's an internal reference, side-stepping 545// reference invalidation problems without losing the realloc optimization. 548 std::uninitialized_fill_n(this->
begin(), NumElts, Elt);
553// Use push_back with a copy in case Args has an internal reference, 554// side-stepping reference invalidation problems without losing the realloc 563 memcpy(
reinterpret_cast<void *
>(this->
end()), EltPtr,
sizeof(
T));
570/// This class consists of common code factored out of the SmallVector class to 571/// reduce code duplication based on the SmallVector 'N' template parameter. 586// Default ctor - Initialize to empty. 601// Subclass has already destructed this vector's elements. 602// If this wasn't grown from the inline copy, deallocate the old space. 616// Make set_size() private to avoid misuse in subclasses. 619template <
bool ForOverwrite>
void resizeImpl(
size_typeN) {
620if (
N == this->size())
623if (N < this->size()) {
640 /// Like resize, but \ref T is POD, the new values won't be initialized. 643 /// Like resize, but requires that \p N is less than \a size(). 645assert(this->
size() >=
N &&
"Cannot increase size with truncate");
651if (
N == this->
size())
654if (N < this->
size()) {
659// N > this->size(). Defer to append. 674T Result = ::std::move(this->
back());
681 /// Add the specified range to the end of the SmallVector. 682template <
typename ItTy,
typename = EnableIfConvertibleToInputIterator<ItTy>>
685size_type NumInputs = std::distance(in_start, in_end);
691 /// Append \p NumInputs copies of \p Elt to the end. 694 std::uninitialized_fill_n(this->
end(), NumInputs, *EltPtr);
699append(IL.begin(), IL.end());
705// Note that Elt could be an internal reference. 711// Assign over existing elements. 712 std::fill_n(this->
begin(), std::min(NumElts, this->
size()), Elt);
713if (NumElts > this->
size())
714 std::uninitialized_fill_n(this->
end(), NumElts - this->
size(), Elt);
715elseif (NumElts < this->
size())
720// FIXME: Consider assigning over existing elements, rather than clearing & 721// re-initializing them - for all assign(...) variants. 723template <
typename ItTy,
typename = EnableIfConvertibleToInputIterator<ItTy>>
738// Just cast away constness because this is a non-const member function. 744// Shift all elts down one. 745 std::move(
I+1, this->
end(), I);
752// Just cast away constness because this is a non-const member function. 759// Shift all elts down. 761// Drop the last elts. 769// Callers ensure that ArgType is derived from T. 771 std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
773"ArgType must be derived from T!");
775if (
I == this->
end()) {
// Important special case for empty vector. 776 this->
push_back(::std::forward<ArgType>(Elt));
784 std::remove_reference_t<ArgType> *EltPtr =
789// Push everything else over. 790std::move_backward(
I, this->
end()-1, this->
end());
793// If we just moved the element we're inserting, be sure to update 794// the reference (never happens if TakesParamByValue). 796 "ArgType must be '
T' when taking by
value!");
800 *
I = ::
std::forward<ArgType>(*EltPtr);
814// Convert iterator to elt# to avoid invalidating iterator when we reserve() 815size_t InsertElt =
I - this->
begin();
817if (I == this->
end()) {
// Important special case for empty vector. 819return this->
begin()+InsertElt;
824// Ensure there is enough space, and get the (maybe updated) address of 828// Uninvalidate the iterator. 829I = this->
begin()+InsertElt;
831// If there are more elements between the insertion point and the end of the 832// range than there are being inserted, we can use a simple approach to 833// insertion. Since we already reserved space, we know that this won't 834// reallocate the vector. 835if (
size_t(this->
end()-I) >= NumToInsert) {
836T *OldEnd = this->
end();
837append(std::move_iterator<iterator>(this->
end() - NumToInsert),
838 std::move_iterator<iterator>(this->
end()));
840// Copy the existing elements that get replaced. 841 std::move_backward(
I, OldEnd-NumToInsert, OldEnd);
843// If we just moved the element we're inserting, be sure to update 844// the reference (never happens if TakesParamByValue). 846 EltPtr += NumToInsert;
848 std::fill_n(
I, NumToInsert, *EltPtr);
852// Otherwise, we're inserting more elements than exist already, and we're 853// not inserting at the end. 855// Move over the elements that we're about to overwrite. 856T *OldEnd = this->
end();
858size_t NumOverwritten = OldEnd-
I;
861// If we just moved the element we're inserting, be sure to update 862// the reference (never happens if TakesParamByValue). 864 EltPtr += NumToInsert;
866// Replace the overwritten part. 867 std::fill_n(
I, NumOverwritten, *EltPtr);
869// Insert the non-overwritten middle part. 870 std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
874template <
typename ItTy,
typename = EnableIfConvertibleToInputIterator<ItTy>>
876// Convert iterator to elt# to avoid invalidating iterator when we reserve() 877size_t InsertElt =
I - this->
begin();
879if (I == this->
end()) {
// Important special case for empty vector. 881return this->
begin()+InsertElt;
886// Check that the reserve that follows doesn't invalidate the iterators. 889size_t NumToInsert = std::distance(
From, To);
891// Ensure there is enough space. 894// Uninvalidate the iterator. 895I = this->
begin()+InsertElt;
897// If there are more elements between the insertion point and the end of the 898// range than there are being inserted, we can use a simple approach to 899// insertion. Since we already reserved space, we know that this won't 900// reallocate the vector. 901if (
size_t(this->
end()-I) >= NumToInsert) {
902T *OldEnd = this->
end();
903append(std::move_iterator<iterator>(this->
end() - NumToInsert),
904 std::move_iterator<iterator>(this->
end()));
906// Copy the existing elements that get replaced. 907 std::move_backward(
I, OldEnd-NumToInsert, OldEnd);
909 std::copy(
From, To,
I);
913// Otherwise, we're inserting more elements than exist already, and we're 914// not inserting at the end. 916// Move over the elements that we're about to overwrite. 917T *OldEnd = this->
end();
919size_t NumOverwritten = OldEnd-
I;
922// Replace the overwritten part. 923for (
T *J =
I; NumOverwritten > 0; --NumOverwritten) {
928// Insert the non-overwritten middle part. 934insert(
I, IL.begin(), IL.end());
941 ::new ((
void *)this->
end())
T(std::forward<ArgTypes>(Args)...);
951if (this->
size() !=
RHS.size())
returnfalse;
955return !(*
this ==
RHS);
959return std::lexicographical_compare(this->
begin(), this->
end(),
969if (
this == &
RHS)
return;
971// We can only avoid copying elements if neither vector is small. 981// Swap the shared elements. 982size_t NumShared = this->
size();
983if (NumShared >
RHS.size()) NumShared =
RHS.size();
984for (
size_type i = 0; i != NumShared; ++i)
987// Copy over the extra elts. 989size_t EltDiff = this->
size() -
RHS.size();
991RHS.set_size(
RHS.size() + EltDiff);
994 }
elseif (
RHS.size() > this->size()) {
995size_t EltDiff =
RHS.size() - this->
size();
999RHS.set_size(NumShared);
1003template <
typename T>
1006// Avoid self-assignment. 1007if (
this == &
RHS)
return *
this;
1009// If we already have sufficient space, assign the common elements, then 1010// destroy any excess. 1011size_t RHSSize =
RHS.size();
1012size_t CurSize = this->
size();
1013if (CurSize >= RHSSize) {
1014// Assign common elements. 1017 NewEnd = std::copy(
RHS.begin(),
RHS.begin()+RHSSize, this->begin());
1019 NewEnd = this->
begin();
1021// Destroy excess elements. 1029// If we have to grow to have enough elements, destroy the current elements. 1030// This allows us to avoid copying them during the grow. 1031// FIXME: don't do this if they're efficiently moveable. 1033// Destroy current elements. 1036 this->
grow(RHSSize);
1038// Otherwise, use assignment for the already-constructed elements. 1039 std::copy(
RHS.begin(),
RHS.begin()+CurSize, this->begin());
1042// Copy construct the new elements in place. 1044 this->begin()+CurSize);
1051template <
typename T>
1053// Avoid self-assignment. 1054if (
this == &
RHS)
return *
this;
1056// If the RHS isn't small, clear this vector and then steal its buffer. 1057if (!
RHS.isSmall()) {
1062// If we already have sufficient space, assign the common elements, then 1063// destroy any excess. 1064size_t RHSSize =
RHS.size();
1065size_t CurSize = this->
size();
1066if (CurSize >= RHSSize) {
1067// Assign common elements. 1070 NewEnd = std::move(
RHS.begin(),
RHS.end(), NewEnd);
1072// Destroy excess elements and trim the bounds. 1082// If we have to grow to have enough elements, destroy the current elements. 1083// This allows us to avoid copying them during the grow. 1084// FIXME: this may not actually make any sense if we can efficiently move 1087// Destroy current elements. 1090 this->
grow(RHSSize);
1092// Otherwise, use assignment for the already-constructed elements. 1093 std::move(
RHS.begin(),
RHS.begin()+CurSize, this->begin());
1096// Move-construct the new elements in place. 1098 this->begin()+CurSize);
1107/// Storage for the SmallVector elements. This is specialized for the N=0 case 1108/// to avoid allocating unnecessary storage. 1109template <
typename T,
unsigned N>
1111alignas(
T)
char InlineElts[
N *
sizeof(
T)];
1114/// We need the storage to be properly aligned even for small-size of 0 so that 1115/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is 1119/// Forward declaration of SmallVector so that 1120/// calculateSmallVectorDefaultInlinedElements can reference 1121/// `sizeof(SmallVector<T, 0>)`. 1124/// Helper class for calculating the default number of inline elements for 1125/// `SmallVector<T>`. 1127/// This should be migrated to a constexpr function when our minimum 1128/// compiler support is enough for multi-statement constexpr functions. 1130// Parameter controlling the default number of inlined elements 1131// for `SmallVector<T>`. 1133// The default number of inlined elements ensures that 1134// 1. There is at least one inlined element. 1135// 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless 1137staticconstexprsize_t kPreferredSmallVectorSizeof = 64;
1139// static_assert that sizeof(T) is not "too big". 1141// Because our policy guarantees at least one inlined element, it is possible 1142// for an arbitrarily large inlined element to allocate an arbitrarily large 1143// amount of inline storage. We generally consider it an antipattern for a 1144// SmallVector to allocate an excessive amount of inline storage, so we want 1145// to call attention to these cases and make sure that users are making an 1146// intentional decision if they request a lot of inline storage. 1148// We want this assertion to trigger in pathological cases, but otherwise 1149// not be too easy to hit. To accomplish that, the cutoff is actually somewhat 1150// larger than kPreferredSmallVectorSizeof (otherwise, 1151// `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that 1152// pattern seems useful in practice). 1154// One wrinkle is that this assertion is in theory non-portable, since 1155// sizeof(T) is in general platform-dependent. However, we don't expect this 1156// to be much of an issue, because most LLVM development happens on 64-bit 1157// hosts, and therefore sizeof(T) is expected to *decrease* when compiled for 1158// 32-bit hosts, dodging the issue. The reverse situation, where development 1159// happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a 1160// 64-bit host, is expected to be very rare. 1163"You are trying to use a default number of inlined elements for " 1164"`SmallVector<T>` but `sizeof(T)` is really big! Please use an " 1165"explicit number of inlined elements with `SmallVector<T, N>` to make " 1166"sure you really want that much inline storage.");
1168// Discount the size of the header itself when calculating the maximum inline 1170staticconstexprsize_t PreferredInlineBytes =
1172staticconstexprsize_t NumElementsThatFit = PreferredInlineBytes /
sizeof(
T);
1174 NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1177/// This is a 'vector' (really, a variable-sized array), optimized 1178/// for the case when the array is small. It contains some number of elements 1179/// in-place, which allows it to avoid heap allocation when the actual number of 1180/// elements is below that threshold. This allows normal "small" cases to be 1181/// fast without losing generality for large inputs. 1184/// In the absence of a well-motivated choice for the number of inlined 1185/// elements \p N, it is recommended to use \c SmallVector<T> (that is, 1186/// omitting the \p N). This will choose a default number of inlined elements 1187/// reasonable for allocation on the stack (for example, trying to keep \c 1188/// sizeof(SmallVector<T>) around 64 bytes). 1190/// \warning This does not attempt to be exception safe. 1192/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h 1201// Destroy the constructed elements in the vector. 1202 this->destroy_range(this->begin(), this->end());
1215template <
typename ItTy,
typename = EnableIfConvertibleToInputIterator<ItTy>>
1220template <
typename RangeTy>
1223 this->append(R.begin(), R.end());
1230template <
typename U,
1231typename = std::enable_if_t<std::is_convertible<U, T>::value>>
1233 this->append(
A.begin(),
A.end());
1261// SmallVectorImpl<T>::operator= does not leverage N==0. Optimize the 1266 this->destroy_range(this->begin(), this->end());
1269 this->assignRemote(std::move(
RHS));
1285template <
typename T,
unsigned N>
1287returnX.capacity_in_bytes();
1290template <
typename RangeType>
1292 std::remove_const_t<std::remove_reference_t<
decltype(*std::begin(
1293 std::declval<RangeType &>()))>>;
1295/// Given a range of type R, iterate the entire range and return a 1296/// SmallVector with elements of the vector. This is useful, for example, 1297/// when you want to iterate a range and then sort the results. 1298template <
unsigned Size,
typename R>
1302template <
typename R>
1307template <
typename Out,
unsigned Size,
typename R>
1316// Explicit instantiations 1318#if SIZE_MAX > UINT32_MAX 1322}
// end namespace llvm 1326 /// Implement std::swap in terms of SmallVector swap. 1333 /// Implement std::swap in terms of SmallVector swap. 1334template<
typename T,
unsigned N>
1340}
// end namespace std 1342#endif// LLVM_ADT_SMALLVECTOR_H #define offsetof(TYPE, MEMBER)
BlockVerifier::State From
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_LIKELY(EXPR)
Given that RA is a live value
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
This is all the stuff common to all SmallVectors.
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 ...
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.
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 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, T &&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)
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.
SmallVectorTemplateBase(size_t Size)
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)
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 void uninitialized_copy(T1 *I, T1 *E, T2 *Dest, std::enable_if_t< std::is_same< std::remove_const_t< T1 >, T2 >::value > *=nullptr)
Copy the range [I, E) onto the uninitialized memory starting with "Dest", constructing elements into ...
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 ...
SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put method implementations that...
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)
static void destroy_range(T *S, T *E)
T * mallocForGrow(size_t MinSize, size_t &NewCapacity)
Create a new allocation big enough for MinSize and pass back its size in NewCapacity.
static constexpr bool TakesParamByValue
SmallVectorTemplateBase(size_t Size)
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...
T & growAndEmplaceBack(ArgTypes &&... Args)
void push_back(const T &Elt)
This is the part of SmallVectorTemplateBase which does not depend on whether the type T is a POD.
void assertSafeToAddRange(ItTy, ItTy)
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()
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...
SmallVectorTemplateCommon(size_t Size)
void assertSafeToAddRange(const T *From, const T *To)
Check whether any part of the range will be invalidated by growing.
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.
void assertSafeToReferenceAfterClear(const T *From, const T *To)
Check whether any part of the range will be invalidated by clearing.
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
const_iterator begin() const
reference operator[](size_type idx)
size_t capacity_in_bytes() const
size_type size_in_bytes() const
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.
void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize)
Check whether Elt will be invalidated by resizing the vector to NewSize.
std::reverse_iterator< iterator > reverse_iterator
void assertSafeToReferenceAfterClear(ItTy, ItTy)
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(SmallVectorImpl< T > &&RHS)
SmallVector(ArrayRef< U > A)
SmallVector(size_t Size, const T &Value)
SmallVector & operator=(const SmallVector &RHS)
SmallVector(const iterator_range< RangeTy > &R)
SmallVector & operator=(std::initializer_list< T > IL)
SmallVector(ItTy S, ItTy E)
SmallVector(SmallVector &&RHS)
SmallVector & operator=(SmallVector &&RHS)
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::conditional_t< sizeof(T)< 4 &&sizeof(void *) >=8, uint64_t, uint32_t > SmallVectorSizeType
BitVector::size_type capacity_in_bytes(const BitVector &X)
std::enable_if_t< std::is_convertible< typename std::iterator_traits< Iterator >::iterator_category, std::input_iterator_tag >::value > EnableIfConvertibleToInputIterator
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::remove_const_t< std::remove_reference_t< decltype(*std::begin(std::declval< RangeType & >()))> > ValueTypeFromRangeType
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
ArrayRef(const T &OneElt) -> ArrayRef< T >
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)
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>.
Figure out the offset of the first element.
char Base[sizeof(SmallVectorBase< SmallVectorSizeType< T > >)]
Storage for the SmallVector elements.
