X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallVector.h;h=6e0fd94dfe67aee1e2c31791f5b9eed31a2f33e4;hb=910cf7f712a1895b993df4677c1059c595353dcc;hp=9fbbbe4f3b5d2b26005107545e09e59c9e7fb788;hpb=ba1f580f338e12c47a600050f7a77fae579acf93;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 9fbbbe4f3b5..6e0fd94dfe6 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/AlignOf.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/type_traits.h" #include @@ -32,44 +33,20 @@ class SmallVectorBase { protected: void *BeginX, *EndX, *CapacityX; - // Allocate raw space for N elements of type T. If T has a ctor or dtor, we - // don't want it to be automatically run, so we need to represent the space as - // something else. An array of char would work great, but might not be - // aligned sufficiently. Instead we use some number of union instances for - // the space, which guarantee maximal alignment. - union U { - double D; - long double LD; - long long L; - void *P; - } FirstEl; - // Space after 'FirstEl' is clobbered, do not add any instance vars after it. - protected: - SmallVectorBase(size_t Size) - : BeginX(&FirstEl), EndX(&FirstEl), CapacityX((char*)&FirstEl+Size) {} - - /// isSmall - Return true if this is a smallvector which has not had dynamic - /// memory allocated for it. - bool isSmall() const { - return BeginX == static_cast(&FirstEl); - } - - /// resetToSmall - Put this vector in a state of being small. - void resetToSmall() { - BeginX = EndX = CapacityX = &FirstEl; - } + SmallVectorBase(void *FirstEl, size_t Size) + : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {} /// 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); + void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize); public: /// size_in_bytes - This returns size()*sizeof(T). size_t size_in_bytes() const { return size_t((char*)EndX - (char*)BeginX); } - + /// capacity_in_bytes - This returns capacity()*sizeof(T). size_t capacity_in_bytes() const { return size_t((char*)CapacityX - (char*)BeginX); @@ -78,11 +55,41 @@ public: bool empty() const { return BeginX == EndX; } }; +template struct SmallVectorStorage; -template +/// SmallVectorTemplateCommon - This is the part of SmallVectorTemplateBase +/// which does not depend on whether the type T is a POD. The extra dummy +/// template argument is used by ArrayRef to avoid unnecessarily requiring T +/// to be complete. +template class SmallVectorTemplateCommon : public SmallVectorBase { +private: + template friend struct SmallVectorStorage; + + // Allocate raw space for N elements of type T. If T has a ctor or dtor, we + // don't want it to be automatically run, so we need to represent the space as + // something else. Use an array of char of sufficient alignment. + typedef llvm::AlignedCharArrayUnion U; + U FirstEl; + // Space after 'FirstEl' is clobbered, do not add any instance vars after it. + protected: - SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(Size) {} + SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {} + + void grow_pod(size_t MinSizeInBytes, size_t TSize) { + SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize); + } + + /// isSmall - Return true if this is a smallvector which has not had dynamic + /// memory allocated for it. + bool isSmall() const { + return BeginX == static_cast(&FirstEl); + } + + /// resetToSmall - Put this vector in a state of being small. + void resetToSmall() { + BeginX = EndX = CapacityX = &FirstEl; + } void setEnd(T *P) { this->EndX = P; } public: @@ -677,8 +684,8 @@ public: RHS.begin(), RHS.end()); } - /// set_size - Set the array size to \arg N, which the current array must have - /// enough capacity for. + /// Set the array size to \p N, which the current array must have enough + /// capacity for. /// /// This does not construct or destroy any elements in the vector. /// @@ -844,6 +851,17 @@ SmallVectorImpl &SmallVectorImpl::operator=(SmallVectorImpl &&RHS) { } #endif +/// Storage for the SmallVector elements which aren't contained in +/// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1' +/// element is in the base class. This is specialized for the N=1 and N=0 cases +/// to avoid allocating unnecessary storage. +template +struct SmallVectorStorage { + typename SmallVectorTemplateCommon::U InlineElts[N - 1]; +}; +template struct SmallVectorStorage {}; +template struct SmallVectorStorage {}; + /// 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 /// in-place, which allows it to avoid heap allocation when the actual number of @@ -854,41 +872,23 @@ SmallVectorImpl &SmallVectorImpl::operator=(SmallVectorImpl &&RHS) { /// template class SmallVector : public SmallVectorImpl { - /// InlineElts - These are 'N-1' elements that are stored inline in the body - /// of the vector. The extra '1' element is stored in SmallVectorImpl. - typedef typename SmallVectorImpl::U U; - enum { - // MinUs - The number of U's require to cover N T's. - MinUs = (static_cast(sizeof(T))*N + - static_cast(sizeof(U)) - 1) / - static_cast(sizeof(U)), - - // NumInlineEltsElts - The number of elements actually in this array. There - // is already one in the parent class, and we have to round up to avoid - // having a zero-element array. - NumInlineEltsElts = MinUs > 1 ? (MinUs - 1) : 1, - - // NumTsAvailable - The number of T's we actually have space for, which may - // be more than N due to rounding. - NumTsAvailable = (NumInlineEltsElts+1)*static_cast(sizeof(U))/ - static_cast(sizeof(T)) - }; - U InlineElts[NumInlineEltsElts]; + /// Storage - Inline space for elements which aren't stored in the base class. + SmallVectorStorage Storage; public: - SmallVector() : SmallVectorImpl(NumTsAvailable) { + SmallVector() : SmallVectorImpl(N) { } explicit SmallVector(unsigned Size, const T &Value = T()) - : SmallVectorImpl(NumTsAvailable) { + : SmallVectorImpl(N) { this->assign(Size, Value); } template - SmallVector(ItTy S, ItTy E) : SmallVectorImpl(NumTsAvailable) { + SmallVector(ItTy S, ItTy E) : SmallVectorImpl(N) { this->append(S, E); } - SmallVector(const SmallVector &RHS) : SmallVectorImpl(NumTsAvailable) { + SmallVector(const SmallVector &RHS) : SmallVectorImpl(N) { if (!RHS.empty()) SmallVectorImpl::operator=(RHS); } @@ -899,7 +899,7 @@ public: } #if LLVM_USE_RVALUE_REFERENCES - SmallVector(SmallVector &&RHS) : SmallVectorImpl(NumTsAvailable) { + SmallVector(SmallVector &&RHS) : SmallVectorImpl(N) { if (!RHS.empty()) SmallVectorImpl::operator=(::std::move(RHS)); } @@ -912,48 +912,6 @@ public: }; -/// Specialize SmallVector at N=0. This specialization guarantees -/// that it can be instantiated at an incomplete T if none of its -/// members are required. -template -class SmallVector : public SmallVectorImpl { -public: - SmallVector() : SmallVectorImpl(0) { - } - - explicit SmallVector(unsigned Size, const T &Value = T()) - : SmallVectorImpl(0) { - this->assign(Size, Value); - } - - template - SmallVector(ItTy S, ItTy E) : SmallVectorImpl(0) { - this->append(S, E); - } - - SmallVector(const SmallVector &RHS) : SmallVectorImpl(0) { - if (!RHS.empty()) - SmallVectorImpl::operator=(RHS); - } - - const SmallVector &operator=(const SmallVector &RHS) { - SmallVectorImpl::operator=(RHS); - return *this; - } - -#if LLVM_USE_RVALUE_REFERENCES - SmallVector(SmallVector &&RHS) : SmallVectorImpl(0) { - if (!RHS.empty()) - SmallVectorImpl::operator=(::std::move(RHS)); - } - - const SmallVector &operator=(SmallVector &&RHS) { - SmallVectorImpl::operator=(::std::move(RHS)); - return *this; - } -#endif -}; - template static inline size_t capacity_in_bytes(const SmallVector &X) { return X.capacity_in_bytes();