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 was developed by Chris Lattner and is distributed under
00006 // the University of Illinois Open Source 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 <algorithm>
00018 #include <cassert>
00019 #include <iterator>
00020 #include <memory>
00021 
00022 namespace llvm {
00023 
00024 /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
00025 /// for the case when the array is small.  It contains some number of elements
00026 /// in-place, which allows it to avoid heap allocation when the actual number of
00027 /// elements is below that threshold.  This allows normal "small" cases to be
00028 /// fast without losing generality for large inputs.
00029 ///
00030 /// Note that this does not attempt to be exception safe.
00031 ///
00032 template <typename T, unsigned N>
00033 class SmallVector {
00034   // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
00035   // don't want it to be automatically run, so we need to represent the space as
00036   // something else.  An array of char would work great, but might not be
00037   // aligned sufficiently.  Instead, we either use GCC extensions, or some
00038   // number of union instances for the space, which guarantee maximal alignment.
00039   union U {
00040     double D;
00041     long double LD;
00042     long long L;
00043     void *P;
00044   };
00045   
00046   /// InlineElts - These are the 'N' elements that are stored inline in the body
00047   /// of the vector
00048   U InlineElts[(sizeof(T)*N+sizeof(U)-1)/sizeof(U)];
00049   T *Begin, *End, *Capacity;
00050 public:
00051   // Default ctor - Initialize to empty.
00052   SmallVector() : Begin((T*)InlineElts), End(Begin), Capacity(Begin+N) {
00053   }
00054   
00055   SmallVector(const SmallVector &RHS) {
00056     unsigned RHSSize = RHS.size();
00057     Begin = (T*)InlineElts;
00058 
00059     // Doesn't fit in the small case?  Allocate space.
00060     if (RHSSize > N) {
00061       End = Capacity = Begin;
00062       grow(RHSSize);
00063     }
00064     End = Begin+RHSSize;
00065     Capacity = Begin+N;
00066     std::uninitialized_copy(RHS.begin(), RHS.end(), Begin);
00067   }
00068   ~SmallVector() {
00069     // If this wasn't grown from the inline copy, deallocate the old space.
00070     if ((void*)Begin != (void*)InlineElts)
00071       delete[] (char*)Begin;
00072   }
00073   
00074   typedef size_t size_type;
00075   typedef T* iterator;
00076   typedef const T* const_iterator;
00077   typedef T& reference;
00078   typedef const T& const_reference;
00079 
00080   bool empty() const { return Begin == End; }
00081   size_type size() const { return End-Begin; }
00082   
00083   iterator begin() { return Begin; }
00084   const_iterator begin() const { return Begin; }
00085 
00086   iterator end() { return End; }
00087   const_iterator end() const { return End; }
00088   
00089   reference operator[](unsigned idx) {
00090     assert(idx < size() && "out of range reference!");
00091     return Begin[idx];
00092   }
00093   const_reference operator[](unsigned idx) const {
00094     assert(idx < size() && "out of range reference!");
00095     return Begin[idx];
00096   }
00097   
00098   reference back() {
00099     assert(!empty() && "SmallVector is empty!");
00100     return end()[-1];
00101   }
00102   const_reference back() const {
00103     assert(!empty() && "SmallVector is empty!");
00104     return end()[-1];
00105   }
00106   
00107   void push_back(const_reference Elt) {
00108     if (End < Capacity) {
00109   Retry:
00110       new (End) T(Elt);
00111       ++End;
00112       return;
00113     }
00114     grow();
00115     goto Retry;
00116   }
00117   
00118   /// append - Add the specified range to the end of the SmallVector.
00119   ///
00120   template<typename in_iter>
00121   void append(in_iter in_start, in_iter in_end) {
00122     unsigned NumInputs = std::distance(in_start, in_end);
00123     // Grow allocated space if needed.
00124     if (End+NumInputs > Capacity)
00125       grow(size()+NumInputs);
00126 
00127     // Copy the new elements over.
00128     std::uninitialized_copy(in_start, in_end, End);
00129     End += NumInputs;
00130   }
00131   
00132   const SmallVector &operator=(const SmallVector &RHS) {
00133     // Avoid self-assignment.
00134     if (this == &RHS) return *this;
00135     
00136     // If we already have sufficient space, assign the common elements, then
00137     // destroy any excess.
00138     unsigned RHSSize = RHS.size();
00139     unsigned CurSize = size();
00140     if (CurSize >= RHSSize) {
00141       // Assign common elements.
00142       std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);
00143       
00144       // Destroy excess elements.
00145       for (unsigned i = RHSSize; i != CurSize; ++i)
00146         Begin[i].~T();
00147       
00148       // Trim.
00149       End = Begin + RHSSize;
00150       return *this;
00151     }
00152     
00153     // If we have to grow to have enough elements, destroy the current elements.
00154     // This allows us to avoid copying them during the grow.
00155     if (Capacity-Begin < RHSSize) {
00156       // Destroy current elements.
00157       for (T *I = Begin, E = End; I != E; ++I)
00158         I->~T();
00159       End = Begin;
00160       CurSize = 0;
00161       grow(RHSSize);
00162     } else if (CurSize) {
00163       // Otherwise, use assignment for the already-constructed elements.
00164       std::copy(RHS.Begin, RHS.Begin+CurSize, Begin);
00165     }
00166     
00167     // Copy construct the new elements in place.
00168     std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize);
00169     
00170     // Set end.
00171     End = Begin+RHSSize;
00172   }
00173   
00174 private:
00175   /// isSmall - Return true if this is a smallvector which has not had dynamic
00176   /// memory allocated for it.
00177   bool isSmall() const {
00178     return (void*)Begin == (void*)InlineElts;
00179   }
00180 
00181   /// grow - double the size of the allocated memory, guaranteeing space for at
00182   /// least one more element or MinSize if specified.
00183   void grow(unsigned MinSize = 0) {
00184     unsigned CurCapacity = Capacity-Begin;
00185     unsigned CurSize = size();
00186     unsigned NewCapacity = 2*CurCapacity;
00187     if (NewCapacity < MinSize)
00188       NewCapacity = MinSize;
00189     T *NewElts = reinterpret_cast<T*>(new char[NewCapacity*sizeof(T)]);
00190 
00191     // Copy the elements over.
00192     std::uninitialized_copy(Begin, End, NewElts);
00193     
00194     // Destroy the original elements.
00195     for (T *I = Begin, *E = End; I != E; ++I)
00196       I->~T();
00197     
00198     // If this wasn't grown from the inline copy, deallocate the old space.
00199     if (!isSmall())
00200       delete[] (char*)Begin;
00201     
00202     Begin = NewElts;
00203     End = NewElts+CurSize;
00204     Capacity = Begin+NewCapacity*2;
00205   }
00206 };
00207 
00208 } // End llvm namespace
00209 
00210 #endif