diff options
| -rw-r--r-- | include/llvm/ADT/SmallVector.h | 226 | ||||
| -rw-r--r-- | include/llvm/Support/Compiler.h | 19 |
2 files changed, 231 insertions, 14 deletions
diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 8b75ff56a3..973e0284ab 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> @@ -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; } @@ -392,6 +481,36 @@ public: 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; + } + + 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); @@ -400,10 +519,10 @@ public: 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. @@ -444,7 +563,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; @@ -493,7 +612,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; @@ -519,8 +638,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 +712,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 +739,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 +760,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 +878,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 diff --git a/include/llvm/Support/Compiler.h b/include/llvm/Support/Compiler.h index d0b186ea7c..0ae02e85c5 100644 --- a/include/llvm/Support/Compiler.h +++ b/include/llvm/Support/Compiler.h @@ -19,6 +19,25 @@ # define __has_feature(x) 0 #endif +/// LLVM_HAS_RVALUE_REFERENCES - Does the compiler provide r-value references? +/// This implies that <utility> provides the one-argument std::move; it +/// does not imply the existence of any other C++ library features. +#if (__has_feature(cxx_rvalue_references) \ + || defined(__GXX_EXPERIMENTAL_CXX0X__) \ + || _MSC_VER >= 1600) +#define LLVM_USE_RVALUE_REFERENCES 1 +#else +#define LLVM_USE_RVALUE_REFERENCES 0 +#endif + +/// llvm_move - Expands to ::std::move if the compiler supports +/// r-value references; otherwise, expands to the argument. +#if LLVM_USE_RVALUE_REFERENCES +#define llvm_move(value) (::std::move(arg)) +#else +#define llvm_move(value) (value) +#endif + /// LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked /// into a shared library, then the class should be private to the library and /// not accessible from outside it. Can also be used to mark variables and |