LLVM API Documentation

SmallVector.h

Go to the documentation of this file.
00001 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the SmallVector class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ADT_SMALLVECTOR_H
00015 #define LLVM_ADT_SMALLVECTOR_H
00016 
00017 #include "llvm/ADT/iterator.h"
00018 #include "llvm/Support/type_traits.h"
00019 #include <algorithm>
00020 #include <cassert>
00021 #include <cstring>
00022 #include <memory>
00023 
00024 #ifdef _MSC_VER
00025 namespace std {
00026 #if _MSC_VER <= 1310
00027   // Work around flawed VC++ implementation of std::uninitialized_copy.  Define
00028   // additional overloads so that elements with pointer types are recognized as
00029   // scalars and not objects, causing bizarre type conversion errors.
00030   template<class T1, class T2>
00031   inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) {
00032     _Scalar_ptr_iterator_tag _Cat;
00033     return _Cat;
00034   }
00035 
00036   template<class T1, class T2>
00037   inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) {
00038     _Scalar_ptr_iterator_tag _Cat;
00039     return _Cat;
00040   }
00041 #else
00042 // FIXME: It is not clear if the problem is fixed in VS 2005.  What is clear
00043 // is that the above hack won't work if it wasn't fixed.
00044 #endif
00045 }
00046 #endif
00047 
00048 namespace llvm {
00049 
00050 /// SmallVectorImpl - This class consists of common code factored out of the
00051 /// SmallVector class to reduce code duplication based on the SmallVector 'N'
00052 /// template parameter.
00053 template <typename T>
00054 class SmallVectorImpl {
00055 protected:
00056   T *Begin, *End, *Capacity;
00057 
00058   // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
00059   // don't want it to be automatically run, so we need to represent the space as
00060   // something else.  An array of char would work great, but might not be
00061   // aligned sufficiently.  Instead, we either use GCC extensions, or some
00062   // number of union instances for the space, which guarantee maximal alignment.
00063 protected:
00064 #ifdef __GNUC__
00065   typedef char U;
00066   U FirstEl __attribute__((aligned));
00067 #else
00068   union U {
00069     double D;
00070     long double LD;
00071     long long L;
00072     void *P;
00073   } FirstEl;
00074 #endif
00075   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
00076 public:
00077   // Default ctor - Initialize to empty.
00078   explicit SmallVectorImpl(unsigned N)
00079     : Begin(reinterpret_cast<T*>(&FirstEl)),
00080       End(reinterpret_cast<T*>(&FirstEl)),
00081       Capacity(reinterpret_cast<T*>(&FirstEl)+N) {
00082   }
00083 
00084   ~SmallVectorImpl() {
00085     // Destroy the constructed elements in the vector.
00086     destroy_range(Begin, End);
00087 
00088     // If this wasn't grown from the inline copy, deallocate the old space.
00089     if (!isSmall())
00090       operator delete(Begin);
00091   }
00092 
00093   typedef size_t size_type;
00094   typedef ptrdiff_t difference_type;
00095   typedef T value_type;
00096   typedef T* iterator;
00097   typedef const T* const_iterator;
00098 
00099   typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
00100   typedef std::reverse_iterator<iterator>  reverse_iterator;
00101 
00102   typedef T& reference;
00103   typedef const T& const_reference;
00104   typedef T* pointer;
00105   typedef const T* const_pointer;
00106 
00107   bool empty() const { return Begin == End; }
00108   size_type size() const { return End-Begin; }
00109   size_type max_size() const { return size_type(-1) / sizeof(T); }
00110 
00111   // forward iterator creation methods.
00112   iterator begin() { return Begin; }
00113   const_iterator begin() const { return Begin; }
00114   iterator end() { return End; }
00115   const_iterator end() const { return End; }
00116 
00117   // reverse iterator creation methods.
00118   reverse_iterator rbegin()            { return reverse_iterator(end()); }
00119   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
00120   reverse_iterator rend()              { return reverse_iterator(begin()); }
00121   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
00122 
00123 
00124   reference operator[](unsigned idx) {
00125     assert(Begin + idx < End);
00126     return Begin[idx];
00127   }
00128   const_reference operator[](unsigned idx) const {
00129     assert(Begin + idx < End);
00130     return Begin[idx];
00131   }
00132 
00133   reference front() {
00134     return begin()[0];
00135   }
00136   const_reference front() const {
00137     return begin()[0];
00138   }
00139 
00140   reference back() {
00141     return end()[-1];
00142   }
00143   const_reference back() const {
00144     return end()[-1];
00145   }
00146 
00147   void push_back(const_reference Elt) {
00148     if (End < Capacity) {
00149   Retry:
00150       new (End) T(Elt);
00151       ++End;
00152       return;
00153     }
00154     grow();
00155     goto Retry;
00156   }
00157 
00158   void pop_back() {
00159     --End;
00160     End->~T();
00161   }
00162 
00163   T pop_back_val() {
00164     T Result = back();
00165     pop_back();
00166     return Result;
00167   }
00168 
00169   void clear() {
00170     destroy_range(Begin, End);
00171     End = Begin;
00172   }
00173 
00174   void resize(unsigned N) {
00175     if (N < size()) {
00176       destroy_range(Begin+N, End);
00177       End = Begin+N;
00178     } else if (N > size()) {
00179       if (unsigned(Capacity-Begin) < N)
00180         grow(N);
00181       construct_range(End, Begin+N, T());
00182       End = Begin+N;
00183     }
00184   }
00185 
00186   void resize(unsigned N, const T &NV) {
00187     if (N < size()) {
00188       destroy_range(Begin+N, End);
00189       End = Begin+N;
00190     } else if (N > size()) {
00191       if (unsigned(Capacity-Begin) < N)
00192         grow(N);
00193       construct_range(End, Begin+N, NV);
00194       End = Begin+N;
00195     }
00196   }
00197 
00198   void reserve(unsigned N) {
00199     if (unsigned(Capacity-Begin) < N)
00200       grow(N);
00201   }
00202 
00203   void swap(SmallVectorImpl &RHS);
00204 
00205   /// append - Add the specified range to the end of the SmallVector.
00206   ///
00207   template<typename in_iter>
00208   void append(in_iter in_start, in_iter in_end) {
00209     size_type NumInputs = std::distance(in_start, in_end);
00210     // Grow allocated space if needed.
00211     if (NumInputs > size_type(Capacity-End))
00212       grow(size()+NumInputs);
00213 
00214     // Copy the new elements over.
00215     std::uninitialized_copy(in_start, in_end, End);
00216     End += NumInputs;
00217   }
00218 
00219   /// append - Add the specified range to the end of the SmallVector.
00220   ///
00221   void append(size_type NumInputs, const T &Elt) {
00222     // Grow allocated space if needed.
00223     if (NumInputs > size_type(Capacity-End))
00224       grow(size()+NumInputs);
00225 
00226     // Copy the new elements over.
00227     std::uninitialized_fill_n(End, NumInputs, Elt);
00228     End += NumInputs;
00229   }
00230 
00231   void assign(unsigned NumElts, const T &Elt) {
00232     clear();
00233     if (unsigned(Capacity-Begin) < NumElts)
00234       grow(NumElts);
00235     End = Begin+NumElts;
00236     construct_range(Begin, End, Elt);
00237   }
00238 
00239   iterator erase(iterator I) {
00240     iterator N = I;
00241     // Shift all elts down one.
00242     std::copy(I+1, End, I);
00243     // Drop the last elt.
00244     pop_back();
00245     return(N);
00246   }
00247 
00248   iterator erase(iterator S, iterator E) {
00249     iterator N = S;
00250     // Shift all elts down.
00251     iterator I = std::copy(E, End, S);
00252     // Drop the last elts.
00253     destroy_range(I, End);
00254     End = I;
00255     return(N);
00256   }
00257 
00258   iterator insert(iterator I, const T &Elt) {
00259     if (I == End) {  // Important special case for empty vector.
00260       push_back(Elt);
00261       return end()-1;
00262     }
00263 
00264     if (End < Capacity) {
00265   Retry:
00266       new (End) T(back());
00267       ++End;
00268       // Push everything else over.
00269       std::copy_backward(I, End-1, End);
00270       *I = Elt;
00271       return I;
00272     }
00273     size_t EltNo = I-Begin;
00274     grow();
00275     I = Begin+EltNo;
00276     goto Retry;
00277   }
00278 
00279   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
00280     if (I == End) {  // Important special case for empty vector.
00281       append(NumToInsert, Elt);
00282       return end()-1;
00283     }
00284 
00285     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
00286     size_t InsertElt = I-begin();
00287 
00288     // Ensure there is enough space.
00289     reserve(static_cast<unsigned>(size() + NumToInsert));
00290 
00291     // Uninvalidate the iterator.
00292     I = begin()+InsertElt;
00293 
00294     // If there are more elements between the insertion point and the end of the
00295     // range than there are being inserted, we can use a simple approach to
00296     // insertion.  Since we already reserved space, we know that this won't
00297     // reallocate the vector.
00298     if (size_t(end()-I) >= NumToInsert) {
00299       T *OldEnd = End;
00300       append(End-NumToInsert, End);
00301 
00302       // Copy the existing elements that get replaced.
00303       std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
00304 
00305       std::fill_n(I, NumToInsert, Elt);
00306       return I;
00307     }
00308 
00309     // Otherwise, we're inserting more elements than exist already, and we're
00310     // not inserting at the end.
00311 
00312     // Copy over the elements that we're about to overwrite.
00313     T *OldEnd = End;
00314     End += NumToInsert;
00315     size_t NumOverwritten = OldEnd-I;
00316     std::uninitialized_copy(I, OldEnd, End-NumOverwritten);
00317 
00318     // Replace the overwritten part.
00319     std::fill_n(I, NumOverwritten, Elt);
00320 
00321     // Insert the non-overwritten middle part.
00322     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
00323     return I;
00324   }
00325 
00326   template<typename ItTy>
00327   iterator insert(iterator I, ItTy From, ItTy To) {
00328     if (I == End) {  // Important special case for empty vector.
00329       append(From, To);
00330       return end()-1;
00331     }
00332 
00333     size_t NumToInsert = std::distance(From, To);
00334     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
00335     size_t InsertElt = I-begin();
00336 
00337     // Ensure there is enough space.
00338     reserve(static_cast<unsigned>(size() + NumToInsert));
00339 
00340     // Uninvalidate the iterator.
00341     I = begin()+InsertElt;
00342 
00343     // If there are more elements between the insertion point and the end of the
00344     // range than there are being inserted, we can use a simple approach to
00345     // insertion.  Since we already reserved space, we know that this won't
00346     // reallocate the vector.
00347     if (size_t(end()-I) >= NumToInsert) {
00348       T *OldEnd = End;
00349       append(End-NumToInsert, End);
00350 
00351       // Copy the existing elements that get replaced.
00352       std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
00353 
00354       std::copy(From, To, I);
00355       return I;
00356     }
00357 
00358     // Otherwise, we're inserting more elements than exist already, and we're
00359     // not inserting at the end.
00360 
00361     // Copy over the elements that we're about to overwrite.
00362     T *OldEnd = End;
00363     End += NumToInsert;
00364     size_t NumOverwritten = OldEnd-I;
00365     std::uninitialized_copy(I, OldEnd, End-NumOverwritten);
00366 
00367     // Replace the overwritten part.
00368     std::copy(From, From+NumOverwritten, I);
00369 
00370     // Insert the non-overwritten middle part.
00371     std::uninitialized_copy(From+NumOverwritten, To, OldEnd);
00372     return I;
00373   }
00374 
00375   /// data - Return a pointer to the vector's buffer, even if empty().
00376   pointer data() {
00377     return pointer(Begin);
00378   }
00379 
00380   /// data - Return a pointer to the vector's buffer, even if empty().
00381   const_pointer data() const {
00382     return const_pointer(Begin);
00383   }
00384 
00385   const SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
00386 
00387   bool operator==(const SmallVectorImpl &RHS) const {
00388     if (size() != RHS.size()) return false;
00389     for (T *This = Begin, *That = RHS.Begin, *E = Begin+size();
00390          This != E; ++This, ++That)
00391       if (*This != *That)
00392         return false;
00393     return true;
00394   }
00395   bool operator!=(const SmallVectorImpl &RHS) const { return !(*this == RHS); }
00396 
00397   bool operator<(const SmallVectorImpl &RHS) const {
00398     return std::lexicographical_compare(begin(), end(),
00399                                         RHS.begin(), RHS.end());
00400   }
00401 
00402   /// capacity - Return the total number of elements in the currently allocated
00403   /// buffer.
00404   size_t capacity() const { return Capacity - Begin; }
00405 
00406   /// set_size - Set the array size to \arg N, which the current array must have
00407   /// enough capacity for.
00408   ///
00409   /// This does not construct or destroy any elements in the vector.
00410   ///
00411   /// Clients can use this in conjunction with capacity() to write past the end
00412   /// of the buffer when they know that more elements are available, and only
00413   /// update the size later. This avoids the cost of value initializing elements
00414   /// which will only be overwritten.
00415   void set_size(unsigned N) {
00416     assert(N <= capacity());
00417     End = Begin + N;
00418   }
00419 
00420 private:
00421   /// isSmall - Return true if this is a smallvector which has not had dynamic
00422   /// memory allocated for it.
00423   bool isSmall() const {
00424     return static_cast<const void*>(Begin) ==
00425            static_cast<const void*>(&FirstEl);
00426   }
00427 
00428   /// grow - double the size of the allocated memory, guaranteeing space for at
00429   /// least one more element or MinSize if specified.
00430   void grow(size_type MinSize = 0);
00431 
00432   void construct_range(T *S, T *E, const T &Elt) {
00433     for (; S != E; ++S)
00434       new (S) T(Elt);
00435   }
00436 
00437   void destroy_range(T *S, T *E) {
00438     while (S != E) {
00439       --E;
00440       E->~T();
00441     }
00442   }
00443 };
00444 
00445 // Define this out-of-line to dissuade the C++ compiler from inlining it.
00446 template <typename T>
00447 void SmallVectorImpl<T>::grow(size_t MinSize) {
00448   size_t CurCapacity = Capacity-Begin;
00449   size_t CurSize = size();
00450   size_t NewCapacity = 2*CurCapacity;
00451   if (NewCapacity < MinSize)
00452     NewCapacity = MinSize;
00453   T *NewElts = static_cast<T*>(operator new(NewCapacity*sizeof(T)));
00454 
00455   // Copy the elements over.
00456   if (is_class<T>::value)
00457     std::uninitialized_copy(Begin, End, NewElts);
00458   else
00459     // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
00460     memcpy(NewElts, Begin, CurSize * sizeof(T));
00461 
00462   // Destroy the original elements.
00463   destroy_range(Begin, End);
00464 
00465   // If this wasn't grown from the inline copy, deallocate the old space.
00466   if (!isSmall())
00467     operator delete(Begin);
00468 
00469   Begin = NewElts;
00470   End = NewElts+CurSize;
00471   Capacity = Begin+NewCapacity;
00472 }
00473 
00474 template <typename T>
00475 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
00476   if (this == &RHS) return;
00477 
00478   // We can only avoid copying elements if neither vector is small.
00479   if (!isSmall() && !RHS.isSmall()) {
00480     std::swap(Begin, RHS.Begin);
00481     std::swap(End, RHS.End);
00482     std::swap(Capacity, RHS.Capacity);
00483     return;
00484   }
00485   if (RHS.size() > size_type(Capacity-Begin))
00486     grow(RHS.size());
00487   if (size() > size_type(RHS.Capacity-RHS.begin()))
00488     RHS.grow(size());
00489 
00490   // Swap the shared elements.
00491   size_t NumShared = size();
00492   if (NumShared > RHS.size()) NumShared = RHS.size();
00493   for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i)
00494     std::swap(Begin[i], RHS[i]);
00495 
00496   // Copy over the extra elts.
00497   if (size() > RHS.size()) {
00498     size_t EltDiff = size() - RHS.size();
00499     std::uninitialized_copy(Begin+NumShared, End, RHS.End);
00500     RHS.End += EltDiff;
00501     destroy_range(Begin+NumShared, End);
00502     End = Begin+NumShared;
00503   } else if (RHS.size() > size()) {
00504     size_t EltDiff = RHS.size() - size();
00505     std::uninitialized_copy(RHS.Begin+NumShared, RHS.End, End);
00506     End += EltDiff;
00507     destroy_range(RHS.Begin+NumShared, RHS.End);
00508     RHS.End = RHS.Begin+NumShared;
00509   }
00510 }
00511 
00512 template <typename T>
00513 const SmallVectorImpl<T> &
00514 SmallVectorImpl<T>::operator=(const SmallVectorImpl<T> &RHS) {
00515   // Avoid self-assignment.
00516   if (this == &RHS) return *this;
00517 
00518   // If we already have sufficient space, assign the common elements, then
00519   // destroy any excess.
00520   unsigned RHSSize = unsigned(RHS.size());
00521   unsigned CurSize = unsigned(size());
00522   if (CurSize >= RHSSize) {
00523     // Assign common elements.
00524     iterator NewEnd;
00525     if (RHSSize)
00526       NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);
00527     else
00528       NewEnd = Begin;
00529 
00530     // Destroy excess elements.
00531     destroy_range(NewEnd, End);
00532 
00533     // Trim.
00534     End = NewEnd;
00535     return *this;
00536   }
00537 
00538   // If we have to grow to have enough elements, destroy the current elements.
00539   // This allows us to avoid copying them during the grow.
00540   if (unsigned(Capacity-Begin) < RHSSize) {
00541     // Destroy current elements.
00542     destroy_range(Begin, End);
00543     End = Begin;
00544     CurSize = 0;
00545     grow(RHSSize);
00546   } else if (CurSize) {
00547     // Otherwise, use assignment for the already-constructed elements.
00548     std::copy(RHS.Begin, RHS.Begin+CurSize, Begin);
00549   }
00550 
00551   // Copy construct the new elements in place.
00552   std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize);
00553 
00554   // Set end.
00555   End = Begin+RHSSize;
00556   return *this;
00557 }
00558 
00559 /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
00560 /// for the case when the array is small.  It contains some number of elements
00561 /// in-place, which allows it to avoid heap allocation when the actual number of
00562 /// elements is below that threshold.  This allows normal "small" cases to be
00563 /// fast without losing generality for large inputs.
00564 ///
00565 /// Note that this does not attempt to be exception safe.
00566 ///
00567 template <typename T, unsigned N>
00568 class SmallVector : public SmallVectorImpl<T> {
00569   /// InlineElts - These are 'N-1' elements that are stored inline in the body
00570   /// of the vector.  The extra '1' element is stored in SmallVectorImpl.
00571   typedef typename SmallVectorImpl<T>::U U;
00572   enum {
00573     // MinUs - The number of U's require to cover N T's.
00574     MinUs = (static_cast<unsigned int>(sizeof(T))*N +
00575              static_cast<unsigned int>(sizeof(U)) - 1) /
00576             static_cast<unsigned int>(sizeof(U)),
00577 
00578     // NumInlineEltsElts - The number of elements actually in this array.  There
00579     // is already one in the parent class, and we have to round up to avoid
00580     // having a zero-element array.
00581     NumInlineEltsElts = MinUs > 1 ? (MinUs - 1) : 1,
00582 
00583     // NumTsAvailable - The number of T's we actually have space for, which may
00584     // be more than N due to rounding.
00585     NumTsAvailable = (NumInlineEltsElts+1)*static_cast<unsigned int>(sizeof(U))/
00586                      static_cast<unsigned int>(sizeof(T))
00587   };
00588   U InlineElts[NumInlineEltsElts];
00589 public:
00590   SmallVector() : SmallVectorImpl<T>(NumTsAvailable) {
00591   }
00592 
00593   explicit SmallVector(unsigned Size, const T &Value = T())
00594     : SmallVectorImpl<T>(NumTsAvailable) {
00595     this->reserve(Size);
00596     while (Size--)
00597       this->push_back(Value);
00598   }
00599 
00600   template<typename ItTy>
00601   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(NumTsAvailable) {
00602     this->append(S, E);
00603   }
00604 
00605   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(NumTsAvailable) {
00606     if (!RHS.empty())
00607       SmallVectorImpl<T>::operator=(RHS);
00608   }
00609 
00610   const SmallVector &operator=(const SmallVector &RHS) {
00611     SmallVectorImpl<T>::operator=(RHS);
00612     return *this;
00613   }
00614 
00615 };
00616 
00617 } // End llvm namespace
00618 
00619 namespace std {
00620   /// Implement std::swap in terms of SmallVector swap.
00621   template<typename T>
00622   inline void
00623   swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
00624     LHS.swap(RHS);
00625   }
00626 
00627   /// Implement std::swap in terms of SmallVector swap.
00628   template<typename T, unsigned N>
00629   inline void
00630   swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
00631     LHS.swap(RHS);
00632   }
00633 }
00634 
00635 #endif