aboutsummaryrefslogtreecommitdiff
path: root/include/llvm/ADT/SmallVector.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/ADT/SmallVector.h')
-rw-r--r--include/llvm/ADT/SmallVector.h160
1 files changed, 64 insertions, 96 deletions
diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h
index 505aa8d8ae61..82538e9bd108 100644
--- a/include/llvm/ADT/SmallVector.h
+++ b/include/llvm/ADT/SmallVector.h
@@ -14,6 +14,7 @@
#ifndef LLVM_ADT_SMALLVECTOR_H
#define LLVM_ADT_SMALLVECTOR_H
+#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/AlignOf.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/MathExtras.h"
@@ -183,13 +184,9 @@ protected:
/// std::move, but not all stdlibs actually provide that.
template<typename It1, typename It2>
static It2 move(It1 I, It1 E, It2 Dest) {
-#if LLVM_HAS_RVALUE_REFERENCES
for (; I != E; ++I, ++Dest)
*Dest = ::std::move(*I);
return Dest;
-#else
- return ::std::copy(I, E, Dest);
-#endif
}
/// move_backward - Use move-assignment to move the range
@@ -198,25 +195,17 @@ protected:
/// std::move_backward, but not all stdlibs actually provide that.
template<typename It1, typename It2>
static It2 move_backward(It1 I, It1 E, It2 Dest) {
-#if LLVM_HAS_RVALUE_REFERENCES
while (I != E)
*--Dest = ::std::move(*--E);
return Dest;
-#else
- return ::std::copy_backward(I, E, Dest);
-#endif
}
/// uninitialized_move - Move the range [I, E) into the uninitialized
/// memory starting with "Dest", constructing elements as needed.
template<typename It1, typename It2>
static void uninitialized_move(It1 I, It1 E, It2 Dest) {
-#if LLVM_HAS_RVALUE_REFERENCES
for (; I != E; ++I, ++Dest)
::new ((void*) &*Dest) T(::std::move(*I));
-#else
- ::std::uninitialized_copy(I, E, Dest);
-#endif
}
/// uninitialized_copy - Copy the range [I, E) onto the uninitialized
@@ -231,32 +220,22 @@ protected:
/// Guarantees space for at least one more element, or MinSize more
/// elements if specified.
void grow(size_t MinSize = 0);
-
+
public:
void push_back(const T &Elt) {
- if (this->EndX < this->CapacityX) {
- Retry:
- ::new ((void*) this->end()) T(Elt);
- this->setEnd(this->end()+1);
- return;
- }
- this->grow();
- goto Retry;
+ if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+ this->grow();
+ ::new ((void*) this->end()) T(Elt);
+ this->setEnd(this->end()+1);
}
-#if LLVM_HAS_RVALUE_REFERENCES
void push_back(T &&Elt) {
- if (this->EndX < this->CapacityX) {
- Retry:
- ::new ((void*) this->end()) T(::std::move(Elt));
- this->setEnd(this->end()+1);
- return;
- }
- this->grow();
- goto Retry;
+ if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+ this->grow();
+ ::new ((void*) this->end()) T(::std::move(Elt));
+ this->setEnd(this->end()+1);
}
-#endif
-
+
void pop_back() {
this->setEnd(this->end()-1);
this->end()->~T();
@@ -268,7 +247,7 @@ template <typename T, bool isPodLike>
void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
size_t CurCapacity = this->capacity();
size_t CurSize = this->size();
- // Always grow, even from zero.
+ // Always grow, even from zero.
size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2));
if (NewCapacity < MinSize)
NewCapacity = MinSize;
@@ -348,16 +327,12 @@ protected:
}
public:
void push_back(const T &Elt) {
- if (this->EndX < this->CapacityX) {
- Retry:
- memcpy(this->end(), &Elt, sizeof(T));
- this->setEnd(this->end()+1);
- return;
- }
- this->grow();
- goto Retry;
+ if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
+ this->grow();
+ memcpy(this->end(), &Elt, sizeof(T));
+ this->setEnd(this->end()+1);
}
-
+
void pop_back() {
this->setEnd(this->end()-1);
}
@@ -405,7 +380,8 @@ public:
} else if (N > this->size()) {
if (this->capacity() < N)
this->grow(N);
- std::uninitialized_fill(this->end(), this->begin()+N, T());
+ for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
+ new (&*I) T();
this->setEnd(this->begin()+N);
}
}
@@ -428,11 +404,7 @@ public:
}
T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
-#if LLVM_HAS_RVALUE_REFERENCES
T Result = ::std::move(this->back());
-#else
- T Result = this->back();
-#endif
this->pop_back();
return Result;
}
@@ -501,7 +473,6 @@ public:
return(N);
}
-#if LLVM_HAS_RVALUE_REFERENCES
iterator insert(iterator I, T &&Elt) {
if (I == this->end()) { // Important special case for empty vector.
this->push_back(::std::move(Elt));
@@ -511,28 +482,26 @@ public:
assert(I >= this->begin() && "Insertion iterator is out of bounds.");
assert(I <= this->end() && "Inserting past the end of the vector.");
- if (this->EndX < this->CapacityX) {
- Retry:
- ::new ((void*) this->end()) T(::std::move(this->back()));
- this->setEnd(this->end()+1);
- // Push everything else over.
- this->move_backward(I, this->end()-1, this->end());
+ if (this->EndX >= this->CapacityX) {
+ size_t EltNo = I-this->begin();
+ this->grow();
+ I = this->begin()+EltNo;
+ }
- // If we just moved the element we're inserting, be sure to update
- // the reference.
- T *EltPtr = &Elt;
- if (I <= EltPtr && EltPtr < this->EndX)
- ++EltPtr;
+ ::new ((void*) this->end()) T(::std::move(this->back()));
+ // Push everything else over.
+ this->move_backward(I, this->end()-1, this->end());
+ this->setEnd(this->end()+1);
- *I = ::std::move(*EltPtr);
- return I;
- }
- size_t EltNo = I-this->begin();
- this->grow();
- I = this->begin()+EltNo;
- goto Retry;
+ // If we just moved the element we're inserting, be sure to update
+ // the reference.
+ T *EltPtr = &Elt;
+ if (I <= EltPtr && EltPtr < this->EndX)
+ ++EltPtr;
+
+ *I = ::std::move(*EltPtr);
+ return I;
}
-#endif
iterator insert(iterator I, const T &Elt) {
if (I == this->end()) { // Important special case for empty vector.
@@ -543,26 +512,24 @@ public:
assert(I >= this->begin() && "Insertion iterator is out of bounds.");
assert(I <= this->end() && "Inserting past the end of the vector.");
- if (this->EndX < this->CapacityX) {
- Retry:
- ::new ((void*) this->end()) T(this->back());
- this->setEnd(this->end()+1);
- // Push everything else over.
- this->move_backward(I, this->end()-1, this->end());
-
- // If we just moved the element we're inserting, be sure to update
- // the reference.
- const T *EltPtr = &Elt;
- if (I <= EltPtr && EltPtr < this->EndX)
- ++EltPtr;
-
- *I = *EltPtr;
- return I;
+ if (this->EndX >= this->CapacityX) {
+ size_t EltNo = I-this->begin();
+ this->grow();
+ I = this->begin()+EltNo;
}
- size_t EltNo = I-this->begin();
- this->grow();
- I = this->begin()+EltNo;
- goto Retry;
+ ::new ((void*) this->end()) T(std::move(this->back()));
+ // Push everything else over.
+ this->move_backward(I, this->end()-1, this->end());
+ this->setEnd(this->end()+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->EndX)
+ ++EltPtr;
+
+ *I = *EltPtr;
+ return I;
}
iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
@@ -589,7 +556,8 @@ public:
// reallocate the vector.
if (size_t(this->end()-I) >= NumToInsert) {
T *OldEnd = this->end();
- append(this->end()-NumToInsert, this->end());
+ append(std::move_iterator<iterator>(this->end() - NumToInsert),
+ std::move_iterator<iterator>(this->end()));
// Copy the existing elements that get replaced.
this->move_backward(I, OldEnd-NumToInsert, OldEnd);
@@ -642,7 +610,8 @@ public:
// reallocate the vector.
if (size_t(this->end()-I) >= NumToInsert) {
T *OldEnd = this->end();
- append(this->end()-NumToInsert, this->end());
+ append(std::move_iterator<iterator>(this->end() - NumToInsert),
+ std::move_iterator<iterator>(this->end()));
// Copy the existing elements that get replaced.
this->move_backward(I, OldEnd-NumToInsert, OldEnd);
@@ -673,9 +642,7 @@ public:
SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
-#if LLVM_HAS_RVALUE_REFERENCES
SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
-#endif
bool operator==(const SmallVectorImpl &RHS) const {
if (this->size() != RHS.size()) return false;
@@ -793,7 +760,6 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::
return *this;
}
-#if LLVM_HAS_RVALUE_REFERENCES
template <typename T>
SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
// Avoid self-assignment.
@@ -842,7 +808,7 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
this->grow(RHSSize);
} else if (CurSize) {
// Otherwise, use assignment for the already-constructed elements.
- this->move(RHS.begin(), RHS.end(), this->begin());
+ this->move(RHS.begin(), RHS.begin()+CurSize, this->begin());
}
// Move-construct the new elements in place.
@@ -855,7 +821,6 @@ SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
RHS.clear();
return *this;
}
-#endif
/// Storage for the SmallVector elements which aren't contained in
/// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1'
@@ -894,6 +859,12 @@ public:
this->append(S, E);
}
+ template <typename RangeTy>
+ explicit SmallVector(const llvm::iterator_range<RangeTy> R)
+ : SmallVectorImpl<T>(N) {
+ this->append(R.begin(), R.end());
+ }
+
SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
if (!RHS.empty())
SmallVectorImpl<T>::operator=(RHS);
@@ -904,7 +875,6 @@ public:
return *this;
}
-#if LLVM_HAS_RVALUE_REFERENCES
SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
if (!RHS.empty())
SmallVectorImpl<T>::operator=(::std::move(RHS));
@@ -914,8 +884,6 @@ public:
SmallVectorImpl<T>::operator=(::std::move(RHS));
return *this;
}
-#endif
-
};
template<typename T, unsigned N>
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-07 01:11:50 +0000