X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallVector.h;h=a6b65dd58b410ae70bf4f01a68c70efac0a98bea;hb=fc82fabe00b0b820e3c0d7fc9e289bace0295f11;hp=ad08db33eef9a46417813435e5d099e543bb554f;hpb=57b79795b37b367d69d58ad10f25e997b4f55ce9;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index ad08db33eef..a6b65dd58b4 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Chris Lattner and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -14,10 +14,34 @@ #ifndef LLVM_ADT_SMALLVECTOR_H #define LLVM_ADT_SMALLVECTOR_H +#include "llvm/ADT/iterator" #include -#include #include +#ifdef _MSC_VER +namespace std { +#if _MSC_VER <= 1310 + // Work around flawed VC++ implementation of std::uninitialized_copy. Define + // additional overloads so that elements with pointer types are recognized as + // scalars and not objects, causing bizarre type conversion errors. + template + inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { + _Scalar_ptr_iterator_tag _Cat; + return _Cat; + } + + template + inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { + _Scalar_ptr_iterator_tag _Cat; + return _Cat; + } +#else +// FIXME: It is not clear if the problem is fixed in VS 2005. What is clear +// is that the above hack won't work if it wasn't fixed. +#endif +} +#endif + namespace llvm { /// SmallVectorImpl - This class consists of common code factored out of the @@ -25,6 +49,7 @@ namespace llvm { /// template parameter. template class SmallVectorImpl { +protected: T *Begin, *End, *Capacity; // Allocate raw space for N elements of type T. If T has a ctor or dtor, we @@ -33,17 +58,24 @@ class SmallVectorImpl { // aligned sufficiently. Instead, we either use GCC extensions, or some // number of union instances for the space, which guarantee maximal alignment. protected: +#ifdef __GNUC__ + typedef char U; + U FirstEl __attribute__((aligned)); +#else union U { double D; long double LD; long long L; void *P; } FirstEl; +#endif // Space after 'FirstEl' is clobbered, do not add any instance vars after it. public: // Default ctor - Initialize to empty. SmallVectorImpl(unsigned N) - : Begin((T*)&FirstEl), End((T*)&FirstEl), Capacity((T*)&FirstEl+N) { + : Begin(reinterpret_cast(&FirstEl)), + End(reinterpret_cast(&FirstEl)), + Capacity(reinterpret_cast(&FirstEl)+N) { } ~SmallVectorImpl() { @@ -52,24 +84,35 @@ public: // If this wasn't grown from the inline copy, deallocate the old space. if (!isSmall()) - delete[] (char*)Begin; + delete[] reinterpret_cast(Begin); } typedef size_t size_type; typedef T* iterator; typedef const T* const_iterator; + + typedef std::reverse_iterator const_reverse_iterator; + typedef std::reverse_iterator reverse_iterator; + typedef T& reference; typedef const T& const_reference; bool empty() const { return Begin == End; } size_type size() const { return End-Begin; } - + + // forward iterator creation methods. iterator begin() { return Begin; } const_iterator begin() const { return Begin; } - iterator end() { return End; } const_iterator end() const { return End; } + // reverse iterator creation methods. + reverse_iterator rbegin() { return reverse_iterator(end()); } + const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); } + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rend() const { return const_reverse_iterator(begin());} + + reference operator[](unsigned idx) { return Begin[idx]; } @@ -117,13 +160,30 @@ public: destroy_range(Begin+N, End); End = Begin+N; } else if (N > size()) { - if (Begin+N > Capacity) + if (unsigned(Capacity-Begin) < N) grow(N); construct_range(End, Begin+N, T()); End = Begin+N; } } + void resize(unsigned N, const T &NV) { + if (N < size()) { + destroy_range(Begin+N, End); + End = Begin+N; + } else if (N > size()) { + if (unsigned(Capacity-Begin) < N) + grow(N); + construct_range(End, Begin+N, NV); + End = Begin+N; + } + } + + void reserve(unsigned N) { + if (unsigned(Capacity-Begin) < N) + grow(N); + } + void swap(SmallVectorImpl &RHS); /// append - Add the specified range to the end of the SmallVector. @@ -142,7 +202,7 @@ public: void assign(unsigned NumElts, const T &Elt) { clear(); - if (Begin+NumElts > Capacity) + if (unsigned(Capacity-Begin) < NumElts) grow(NumElts); End = Begin+NumElts; construct_range(Begin, End, Elt); @@ -184,13 +244,72 @@ public: goto Retry; } + template + iterator insert(iterator I, ItTy From, ItTy To) { + if (I == End) { // Important special case for empty vector. + append(From, To); + return end()-1; + } + + unsigned NumToInsert = std::distance(From, To); + // Convert iterator to elt# to avoid invalidating iterator when we reserve() + unsigned InsertElt = I-begin(); + + // Ensure there is enough space. + reserve(size() + NumToInsert); + + // Uninvalidate the iterator. + I = begin()+InsertElt; + + // If we already have this many elements in the collection, append the + // dest elements at the end, then copy over the appropriate elements. Since + // we already reserved space, we know that this won't reallocate the vector. + if (size() >= NumToInsert) { + T *OldEnd = End; + append(End-NumToInsert, End); + + // Copy the existing elements that get replaced. + std::copy(I, OldEnd-NumToInsert, I+NumToInsert); + + std::copy(From, To, I); + return I; + } + + // 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. + T *OldEnd = End; + End += NumToInsert; + unsigned NumOverwritten = OldEnd-I; + std::uninitialized_copy(I, OldEnd, End-NumOverwritten); + + // Replace the overwritten part. + std::copy(From, From+NumOverwritten, I); + + // Insert the non-overwritten middle part. + std::uninitialized_copy(From+NumOverwritten, To, OldEnd); + return I; + } + const SmallVectorImpl &operator=(const SmallVectorImpl &RHS); + bool operator==(const SmallVectorImpl &RHS) const { + if (size() != RHS.size()) return false; + for (T *This = Begin, *That = RHS.Begin, *End = Begin+size(); + This != End; ++This, ++That) + if (*This != *That) + return false; + return true; + } + bool operator!=(const SmallVectorImpl &RHS) const { return !(*this == RHS); } + private: /// isSmall - Return true if this is a smallvector which has not had dynamic /// memory allocated for it. bool isSmall() const { - return (void*)Begin == (void*)&FirstEl; + return reinterpret_cast(Begin) == + reinterpret_cast(&FirstEl); } /// grow - double the size of the allocated memory, guaranteeing space for at @@ -201,12 +320,11 @@ private: for (; S != E; ++S) new (S) T(Elt); } - void destroy_range(T *S, T *E) { while (S != E) { - E->~T(); --E; + E->~T(); } } }; @@ -214,8 +332,8 @@ private: // Define this out-of-line to dissuade the C++ compiler from inlining it. template void SmallVectorImpl::grow(unsigned MinSize) { - unsigned CurCapacity = Capacity-Begin; - unsigned CurSize = size(); + unsigned CurCapacity = unsigned(Capacity-Begin); + unsigned CurSize = unsigned(size()); unsigned NewCapacity = 2*CurCapacity; if (NewCapacity < MinSize) NewCapacity = MinSize; @@ -229,7 +347,7 @@ void SmallVectorImpl::grow(unsigned MinSize) { // If this wasn't grown from the inline copy, deallocate the old space. if (!isSmall()) - delete[] (char*)Begin; + delete[] reinterpret_cast(Begin); Begin = NewElts; End = NewElts+CurSize; @@ -282,11 +400,15 @@ SmallVectorImpl::operator=(const SmallVectorImpl &RHS) { // If we already have sufficient space, assign the common elements, then // destroy any excess. - unsigned RHSSize = RHS.size(); - unsigned CurSize = size(); + unsigned RHSSize = unsigned(RHS.size()); + unsigned CurSize = unsigned(size()); if (CurSize >= RHSSize) { // Assign common elements. - iterator NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin); + iterator NewEnd; + if (RHSSize) + NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin); + else + NewEnd = Begin; // Destroy excess elements. destroy_range(NewEnd, End); @@ -348,13 +470,21 @@ public: SmallVector() : SmallVectorImpl(NumTsAvailable) { } + explicit SmallVector(unsigned Size, const T &Value = T()) + : SmallVectorImpl(NumTsAvailable) { + this->reserve(Size); + while (Size--) + push_back(Value); + } + template SmallVector(ItTy S, ItTy E) : SmallVectorImpl(NumTsAvailable) { append(S, E); } SmallVector(const SmallVector &RHS) : SmallVectorImpl(NumTsAvailable) { - operator=(RHS); + if (!RHS.empty()) + operator=(RHS); } const SmallVector &operator=(const SmallVector &RHS) {