summaryrefslogtreecommitdiffstats
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.h298
1 files changed, 265 insertions, 33 deletions
diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h
index 0d9d0d1..9fbbbe4 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/Support/Compiler.h"
#include "llvm/Support/type_traits.h"
#include <algorithm>
#include <cassert>
@@ -54,6 +55,11 @@ protected:
return BeginX == static_cast<const void*>(&FirstEl);
}
+ /// resetToSmall - Put this vector in a state of being small.
+ void resetToSmall() {
+ BeginX = EndX = CapacityX = &FirstEl;
+ }
+
/// grow_pod - 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(size_t MinSizeInBytes, size_t TSize);
@@ -160,28 +166,84 @@ protected:
}
}
- /// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory
- /// starting with "Dest", constructing elements into it as needed.
+ /// move - Use move-assignment to move the range [I, E) onto the
+ /// objects starting with "Dest". This is just <memory>'s
+ /// 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_USE_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
+ /// [I, E) onto the objects ending at "Dest", moving objects
+ /// in reverse order. This is just <algorithm>'s
+ /// 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_USE_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_USE_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
+ /// memory starting with "Dest", constructing elements as needed.
template<typename It1, typename It2>
static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
std::uninitialized_copy(I, E, Dest);
}
- /// grow - double the size of the allocated memory, guaranteeing space for at
- /// least one more element or MinSize if specified.
+ /// grow - Grow the allocated memory (without initializing new
+ /// elements), doubling the size of the allocated memory.
+ /// 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 (this->end()) T(Elt);
+ ::new ((void*) this->end()) T(Elt);
this->setEnd(this->end()+1);
return;
}
this->grow();
goto Retry;
}
+
+#if LLVM_USE_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;
+ }
+#endif
void pop_back() {
this->setEnd(this->end()-1);
@@ -199,8 +261,8 @@ void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
NewCapacity = MinSize;
T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T)));
- // Copy the elements over.
- this->uninitialized_copy(this->begin(), this->end(), NewElts);
+ // Move the elements over.
+ this->uninitialized_move(this->begin(), this->end(), NewElts);
// Destroy the original elements.
destroy_range(this->begin(), this->end());
@@ -225,6 +287,29 @@ protected:
// No need to do a destroy loop for POD's.
static void destroy_range(T *, T *) {}
+ /// move - Use move-assignment to move the range [I, E) onto the
+ /// objects starting with "Dest". For PODs, this is just memcpy.
+ template<typename It1, typename It2>
+ static It2 move(It1 I, It1 E, It2 Dest) {
+ return ::std::copy(I, E, Dest);
+ }
+
+ /// move_backward - Use move-assignment to move the range
+ /// [I, E) onto the objects ending at "Dest", moving objects
+ /// in reverse order.
+ template<typename It1, typename It2>
+ static It2 move_backward(It1 I, It1 E, It2 Dest) {
+ return ::std::copy_backward(I, E, Dest);
+ }
+
+ /// uninitialized_move - Move the range [I, E) onto the uninitialized memory
+ /// starting with "Dest", constructing elements into it as needed.
+ template<typename It1, typename It2>
+ static void uninitialized_move(It1 I, It1 E, It2 Dest) {
+ // Just do a copy.
+ uninitialized_copy(I, E, Dest);
+ }
+
/// uninitialized_copy - Copy the range [I, E) onto the uninitialized memory
/// starting with "Dest", constructing elements into it as needed.
template<typename It1, typename It2>
@@ -252,7 +337,7 @@ public:
void push_back(const T &Elt) {
if (this->EndX < this->CapacityX) {
Retry:
- *this->end() = Elt;
+ memcpy(this->end(), &Elt, sizeof(T));
this->setEnd(this->end()+1);
return;
}
@@ -330,7 +415,11 @@ public:
}
T pop_back_val() {
+#if LLVM_USE_RVALUE_REFERENCES
+ T Result = ::std::move(this->back());
+#else
T Result = this->back();
+#endif
this->pop_back();
return Result;
}
@@ -374,36 +463,79 @@ public:
}
iterator erase(iterator I) {
+ assert(I >= this->begin() && "Iterator to erase is out of bounds.");
+ assert(I < this->end() && "Erasing at past-the-end iterator.");
+
iterator N = I;
// Shift all elts down one.
- std::copy(I+1, this->end(), I);
+ this->move(I+1, this->end(), I);
// Drop the last elt.
this->pop_back();
return(N);
}
iterator erase(iterator S, iterator E) {
+ 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.");
+
iterator N = S;
// Shift all elts down.
- iterator I = std::copy(E, this->end(), S);
+ iterator I = this->move(E, this->end(), S);
// Drop the last elts.
this->destroy_range(I, this->end());
this->setEnd(I);
return(N);
}
+#if LLVM_USE_RVALUE_REFERENCES
+ iterator insert(iterator I, T &&Elt) {
+ if (I == this->end()) { // Important special case for empty vector.
+ this->push_back(::std::move(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->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 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;
+ }
+ size_t EltNo = I-this->begin();
+ this->grow();
+ I = this->begin()+EltNo;
+ goto Retry;
+ }
+#endif
+
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->EndX < this->CapacityX) {
Retry:
- new (this->end()) T(this->back());
+ ::new ((void*) this->end()) T(this->back());
this->setEnd(this->end()+1);
// Push everything else over.
- std::copy_backward(I, this->end()-1, this->end());
+ this->move_backward(I, this->end()-1, this->end());
// If we just moved the element we're inserting, be sure to update
// the reference.
@@ -421,13 +553,16 @@ public:
}
iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
+ // Convert iterator to elt# to avoid invalidating iterator when we reserve()
+ size_t InsertElt = I - this->begin();
+
if (I == this->end()) { // Important special case for empty vector.
append(NumToInsert, Elt);
- return this->end()-1;
+ return this->begin()+InsertElt;
}
- // Convert iterator to elt# to avoid invalidating iterator when we reserve()
- size_t InsertElt = I - this->begin();
+ assert(I >= this->begin() && "Insertion iterator is out of bounds.");
+ assert(I <= this->end() && "Inserting past the end of the vector.");
// Ensure there is enough space.
reserve(static_cast<unsigned>(this->size() + NumToInsert));
@@ -444,7 +579,7 @@ public:
append(this->end()-NumToInsert, this->end());
// Copy the existing elements that get replaced.
- std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
+ this->move_backward(I, OldEnd-NumToInsert, OldEnd);
std::fill_n(I, NumToInsert, Elt);
return I;
@@ -453,11 +588,11 @@ public:
// Otherwise, we're inserting more elements than exist already, and we're
// not inserting at the end.
- // Copy over the elements that we're about to overwrite.
+ // Move over the elements that we're about to overwrite.
T *OldEnd = this->end();
this->setEnd(this->end() + NumToInsert);
size_t NumOverwritten = OldEnd-I;
- this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
+ this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
// Replace the overwritten part.
std::fill_n(I, NumOverwritten, Elt);
@@ -469,14 +604,18 @@ public:
template<typename ItTy>
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();
+
if (I == this->end()) { // Important special case for empty vector.
append(From, To);
- return this->end()-1;
+ 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.");
+
size_t NumToInsert = std::distance(From, To);
- // Convert iterator to elt# to avoid invalidating iterator when we reserve()
- size_t InsertElt = I - this->begin();
// Ensure there is enough space.
reserve(static_cast<unsigned>(this->size() + NumToInsert));
@@ -493,7 +632,7 @@ public:
append(this->end()-NumToInsert, this->end());
// Copy the existing elements that get replaced.
- std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
+ this->move_backward(I, OldEnd-NumToInsert, OldEnd);
std::copy(From, To, I);
return I;
@@ -502,16 +641,16 @@ public:
// Otherwise, we're inserting more elements than exist already, and we're
// not inserting at the end.
- // Copy over the elements that we're about to overwrite.
+ // Move over the elements that we're about to overwrite.
T *OldEnd = this->end();
this->setEnd(this->end() + NumToInsert);
size_t NumOverwritten = OldEnd-I;
- this->uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
+ this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
// Replace the overwritten part.
- for (; NumOverwritten > 0; --NumOverwritten) {
- *I = *From;
- ++I; ++From;
+ for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
+ *J = *From;
+ ++J; ++From;
}
// Insert the non-overwritten middle part.
@@ -519,8 +658,11 @@ public:
return I;
}
- const SmallVectorImpl
- &operator=(const SmallVectorImpl &RHS);
+ SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
+
+#if LLVM_USE_RVALUE_REFERENCES
+ SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
+#endif
bool operator==(const SmallVectorImpl &RHS) const {
if (this->size() != RHS.size()) return false;
@@ -590,7 +732,7 @@ void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
}
template <typename T>
-const SmallVectorImpl<T> &SmallVectorImpl<T>::
+SmallVectorImpl<T> &SmallVectorImpl<T>::
operator=(const SmallVectorImpl<T> &RHS) {
// Avoid self-assignment.
if (this == &RHS) return *this;
@@ -617,6 +759,7 @@ const SmallVectorImpl<T> &SmallVectorImpl<T>::
// If we have to grow to have enough elements, destroy the current elements.
// This allows us to avoid copying them during the grow.
+ // FIXME: don't do this if they're efficiently moveable.
if (this->capacity() < RHSSize) {
// Destroy current elements.
this->destroy_range(this->begin(), this->end());
@@ -637,6 +780,69 @@ const SmallVectorImpl<T> &SmallVectorImpl<T>::
return *this;
}
+#if LLVM_USE_RVALUE_REFERENCES
+template <typename T>
+SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
+ // Avoid self-assignment.
+ if (this == &RHS) return *this;
+
+ // If the RHS isn't small, clear this vector and then steal its buffer.
+ if (!RHS.isSmall()) {
+ this->destroy_range(this->begin(), this->end());
+ if (!this->isSmall()) free(this->begin());
+ this->BeginX = RHS.BeginX;
+ this->EndX = RHS.EndX;
+ this->CapacityX = RHS.CapacityX;
+ RHS.resetToSmall();
+ return *this;
+ }
+
+ // If we already have sufficient space, assign the common elements, then
+ // destroy any excess.
+ size_t RHSSize = RHS.size();
+ size_t CurSize = this->size();
+ if (CurSize >= RHSSize) {
+ // Assign common elements.
+ iterator NewEnd = this->begin();
+ if (RHSSize)
+ NewEnd = this->move(RHS.begin(), RHS.end(), NewEnd);
+
+ // Destroy excess elements and trim the bounds.
+ this->destroy_range(NewEnd, this->end());
+ this->setEnd(NewEnd);
+
+ // Clear the RHS.
+ RHS.clear();
+
+ return *this;
+ }
+
+ // If we have to grow to have enough elements, destroy the current elements.
+ // This allows us to avoid copying them during the grow.
+ // FIXME: this may not actually make any sense if we can efficiently move
+ // elements.
+ if (this->capacity() < RHSSize) {
+ // Destroy current elements.
+ this->destroy_range(this->begin(), this->end());
+ this->setEnd(this->begin());
+ CurSize = 0;
+ this->grow(RHSSize);
+ } else if (CurSize) {
+ // Otherwise, use assignment for the already-constructed elements.
+ this->move(RHS.begin(), RHS.end(), this->begin());
+ }
+
+ // Move-construct the new elements in place.
+ this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
+ this->begin()+CurSize);
+
+ // Set end.
+ this->setEnd(this->begin()+RHSSize);
+
+ RHS.clear();
+ return *this;
+}
+#endif
/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
/// for the case when the array is small. It contains some number of elements
@@ -692,6 +898,18 @@ public:
return *this;
}
+#if LLVM_USE_RVALUE_REFERENCES
+ SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(NumTsAvailable) {
+ if (!RHS.empty())
+ SmallVectorImpl<T>::operator=(::std::move(RHS));
+ }
+
+ const SmallVector &operator=(SmallVector &&RHS) {
+ SmallVectorImpl<T>::operator=(::std::move(RHS));
+ return *this;
+ }
+#endif
+
};
/// Specialize SmallVector at N=0. This specialization guarantees
@@ -700,7 +918,8 @@ public:
template <typename T>
class SmallVector<T,0> : public SmallVectorImpl<T> {
public:
- SmallVector() : SmallVectorImpl<T>(0) {}
+ SmallVector() : SmallVectorImpl<T>(0) {
+ }
explicit SmallVector(unsigned Size, const T &Value = T())
: SmallVectorImpl<T>(0) {
@@ -713,13 +932,26 @@ public:
}
SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(0) {
+ if (!RHS.empty())
+ SmallVectorImpl<T>::operator=(RHS);
+ }
+
+ const SmallVector &operator=(const SmallVector &RHS) {
SmallVectorImpl<T>::operator=(RHS);
+ return *this;
}
- SmallVector &operator=(const SmallVectorImpl<T> &RHS) {
- return SmallVectorImpl<T>::operator=(RHS);
+#if LLVM_USE_RVALUE_REFERENCES
+ SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(0) {
+ if (!RHS.empty())
+ SmallVectorImpl<T>::operator=(::std::move(RHS));
}
+ const SmallVector &operator=(SmallVector &&RHS) {
+ SmallVectorImpl<T>::operator=(::std::move(RHS));
+ return *this;
+ }
+#endif
};
template<typename T, unsigned N>
OpenPOWER on IntegriCloud