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_range.h"
00018 #include "llvm/Support/AlignOf.h"
00019 #include "llvm/Support/Compiler.h"
00020 #include "llvm/Support/MathExtras.h"
00021 #include "llvm/Support/type_traits.h"
00022 #include <algorithm>
00023 #include <cassert>
00024 #include <cstddef>
00025 #include <cstdlib>
00026 #include <cstring>
00027 #include <iterator>
00028 #include <memory>
00029 
00030 namespace llvm {
00031 
00032 /// This is all the non-templated stuff common to all SmallVectors.
00033 class SmallVectorBase {
00034 protected:
00035   void *BeginX, *EndX, *CapacityX;
00036 
00037 protected:
00038   SmallVectorBase(void *FirstEl, size_t Size)
00039     : BeginX(FirstEl), EndX(FirstEl), CapacityX((char*)FirstEl+Size) {}
00040 
00041   /// This is an implementation of the grow() method which only works
00042   /// on POD-like data types and is out of line to reduce code duplication.
00043   void grow_pod(void *FirstEl, size_t MinSizeInBytes, size_t TSize);
00044 
00045 public:
00046   /// This returns size()*sizeof(T).
00047   size_t size_in_bytes() const {
00048     return size_t((char*)EndX - (char*)BeginX);
00049   }
00050 
00051   /// capacity_in_bytes - This returns capacity()*sizeof(T).
00052   size_t capacity_in_bytes() const {
00053     return size_t((char*)CapacityX - (char*)BeginX);
00054   }
00055 
00056   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return BeginX == EndX; }
00057 };
00058 
00059 template <typename T, unsigned N> struct SmallVectorStorage;
00060 
00061 /// This is the part of SmallVectorTemplateBase which does not depend on whether
00062 /// the type T is a POD. The extra dummy template argument is used by ArrayRef
00063 /// to avoid unnecessarily requiring T to be complete.
00064 template <typename T, typename = void>
00065 class SmallVectorTemplateCommon : public SmallVectorBase {
00066 private:
00067   template <typename, unsigned> friend struct SmallVectorStorage;
00068 
00069   // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
00070   // don't want it to be automatically run, so we need to represent the space as
00071   // something else.  Use an array of char of sufficient alignment.
00072   typedef llvm::AlignedCharArrayUnion<T> U;
00073   U FirstEl;
00074   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
00075 
00076 protected:
00077   SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}
00078 
00079   void grow_pod(size_t MinSizeInBytes, size_t TSize) {
00080     SmallVectorBase::grow_pod(&FirstEl, MinSizeInBytes, TSize);
00081   }
00082 
00083   /// Return true if this is a smallvector which has not had dynamic
00084   /// memory allocated for it.
00085   bool isSmall() const {
00086     return BeginX == static_cast<const void*>(&FirstEl);
00087   }
00088 
00089   /// Put this vector in a state of being small.
00090   void resetToSmall() {
00091     BeginX = EndX = CapacityX = &FirstEl;
00092   }
00093 
00094   void setEnd(T *P) { this->EndX = P; }
00095 public:
00096   typedef size_t size_type;
00097   typedef ptrdiff_t difference_type;
00098   typedef T value_type;
00099   typedef T *iterator;
00100   typedef const T *const_iterator;
00101 
00102   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00103   typedef std::reverse_iterator<iterator> reverse_iterator;
00104 
00105   typedef T &reference;
00106   typedef const T &const_reference;
00107   typedef T *pointer;
00108   typedef const T *const_pointer;
00109 
00110   // forward iterator creation methods.
00111   iterator begin() { return (iterator)this->BeginX; }
00112   const_iterator begin() const { return (const_iterator)this->BeginX; }
00113   iterator end() { return (iterator)this->EndX; }
00114   const_iterator end() const { return (const_iterator)this->EndX; }
00115 protected:
00116   iterator capacity_ptr() { return (iterator)this->CapacityX; }
00117   const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}
00118 public:
00119 
00120   // reverse iterator creation methods.
00121   reverse_iterator rbegin()            { return reverse_iterator(end()); }
00122   const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
00123   reverse_iterator rend()              { return reverse_iterator(begin()); }
00124   const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
00125 
00126   size_type size() const { return end()-begin(); }
00127   size_type max_size() const { return size_type(-1) / sizeof(T); }
00128 
00129   /// Return the total number of elements in the currently allocated buffer.
00130   size_t capacity() const { return capacity_ptr() - begin(); }
00131 
00132   /// Return a pointer to the vector's buffer, even if empty().
00133   pointer data() { return pointer(begin()); }
00134   /// Return a pointer to the vector's buffer, even if empty().
00135   const_pointer data() const { return const_pointer(begin()); }
00136 
00137   reference operator[](size_type idx) {
00138     assert(begin() + idx < end());
00139     return begin()[idx];
00140   }
00141   const_reference operator[](size_type idx) const {
00142     assert(begin() + idx < end());
00143     return begin()[idx];
00144   }
00145 
00146   reference front() {
00147     assert(!empty());
00148     return begin()[0];
00149   }
00150   const_reference front() const {
00151     assert(!empty());
00152     return begin()[0];
00153   }
00154 
00155   reference back() {
00156     assert(!empty());
00157     return end()[-1];
00158   }
00159   const_reference back() const {
00160     assert(!empty());
00161     return end()[-1];
00162   }
00163 };
00164 
00165 /// SmallVectorTemplateBase<isPodLike = false> - This is where we put method
00166 /// implementations that are designed to work with non-POD-like T's.
00167 template <typename T, bool isPodLike>
00168 class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
00169 protected:
00170   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
00171 
00172   static void destroy_range(T *S, T *E) {
00173     while (S != E) {
00174       --E;
00175       E->~T();
00176     }
00177   }
00178 
00179   /// Use move-assignment to move the range [I, E) onto the
00180   /// objects starting with "Dest".  This is just <memory>'s
00181   /// std::move, but not all stdlibs actually provide that.
00182   template<typename It1, typename It2>
00183   static It2 move(It1 I, It1 E, It2 Dest) {
00184     for (; I != E; ++I, ++Dest)
00185       *Dest = ::std::move(*I);
00186     return Dest;
00187   }
00188 
00189   /// Use move-assignment to move the range
00190   /// [I, E) onto the objects ending at "Dest", moving objects
00191   /// in reverse order.  This is just <algorithm>'s
00192   /// std::move_backward, but not all stdlibs actually provide that.
00193   template<typename It1, typename It2>
00194   static It2 move_backward(It1 I, It1 E, It2 Dest) {
00195     while (I != E)
00196       *--Dest = ::std::move(*--E);
00197     return Dest;
00198   }
00199 
00200   /// Move the range [I, E) into the uninitialized memory starting with "Dest",
00201   /// constructing elements as needed.
00202   template<typename It1, typename It2>
00203   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
00204     for (; I != E; ++I, ++Dest)
00205       ::new ((void*) &*Dest) T(::std::move(*I));
00206   }
00207 
00208   /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
00209   /// constructing elements as needed.
00210   template<typename It1, typename It2>
00211   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
00212     std::uninitialized_copy(I, E, Dest);
00213   }
00214 
00215   /// Grow the allocated memory (without initializing new elements), doubling
00216   /// the size of the allocated memory. Guarantees space for at least one more
00217   /// element, or MinSize more elements if specified.
00218   void grow(size_t MinSize = 0);
00219 
00220 public:
00221   void push_back(const T &Elt) {
00222     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
00223       this->grow();
00224     ::new ((void*) this->end()) T(Elt);
00225     this->setEnd(this->end()+1);
00226   }
00227 
00228   void push_back(T &&Elt) {
00229     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
00230       this->grow();
00231     ::new ((void*) this->end()) T(::std::move(Elt));
00232     this->setEnd(this->end()+1);
00233   }
00234 
00235   void pop_back() {
00236     this->setEnd(this->end()-1);
00237     this->end()->~T();
00238   }
00239 };
00240 
00241 // Define this out-of-line to dissuade the C++ compiler from inlining it.
00242 template <typename T, bool isPodLike>
00243 void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
00244   size_t CurCapacity = this->capacity();
00245   size_t CurSize = this->size();
00246   // Always grow, even from zero.
00247   size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2));
00248   if (NewCapacity < MinSize)
00249     NewCapacity = MinSize;
00250   T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T)));
00251 
00252   // Move the elements over.
00253   this->uninitialized_move(this->begin(), this->end(), NewElts);
00254 
00255   // Destroy the original elements.
00256   destroy_range(this->begin(), this->end());
00257 
00258   // If this wasn't grown from the inline copy, deallocate the old space.
00259   if (!this->isSmall())
00260     free(this->begin());
00261 
00262   this->setEnd(NewElts+CurSize);
00263   this->BeginX = NewElts;
00264   this->CapacityX = this->begin()+NewCapacity;
00265 }
00266 
00267 
00268 /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method
00269 /// implementations that are designed to work with POD-like T's.
00270 template <typename T>
00271 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
00272 protected:
00273   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
00274 
00275   // No need to do a destroy loop for POD's.
00276   static void destroy_range(T *, T *) {}
00277 
00278   /// Use move-assignment to move the range [I, E) onto the
00279   /// objects starting with "Dest".  For PODs, this is just memcpy.
00280   template<typename It1, typename It2>
00281   static It2 move(It1 I, It1 E, It2 Dest) {
00282     return ::std::copy(I, E, Dest);
00283   }
00284 
00285   /// Use move-assignment to move the range [I, E) onto the objects ending at
00286   /// "Dest", moving objects in reverse order.
00287   template<typename It1, typename It2>
00288   static It2 move_backward(It1 I, It1 E, It2 Dest) {
00289     return ::std::copy_backward(I, E, Dest);
00290   }
00291 
00292   /// Move the range [I, E) onto the uninitialized memory
00293   /// starting with "Dest", constructing elements into it as needed.
00294   template<typename It1, typename It2>
00295   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
00296     // Just do a copy.
00297     uninitialized_copy(I, E, Dest);
00298   }
00299 
00300   /// Copy the range [I, E) onto the uninitialized memory
00301   /// starting with "Dest", constructing elements into it as needed.
00302   template<typename It1, typename It2>
00303   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
00304     // Arbitrary iterator types; just use the basic implementation.
00305     std::uninitialized_copy(I, E, Dest);
00306   }
00307 
00308   /// Copy the range [I, E) onto the uninitialized memory
00309   /// starting with "Dest", constructing elements into it as needed.
00310   template<typename T1, typename T2>
00311   static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest) {
00312     // Use memcpy for PODs iterated by pointers (which includes SmallVector
00313     // iterators): std::uninitialized_copy optimizes to memmove, but we can
00314     // use memcpy here.
00315     memcpy(Dest, I, (E-I)*sizeof(T));
00316   }
00317 
00318   /// Double the size of the allocated memory, guaranteeing space for at
00319   /// least one more element or MinSize if specified.
00320   void grow(size_t MinSize = 0) {
00321     this->grow_pod(MinSize*sizeof(T), sizeof(T));
00322   }
00323 public:
00324   void push_back(const T &Elt) {
00325     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
00326       this->grow();
00327     memcpy(this->end(), &Elt, sizeof(T));
00328     this->setEnd(this->end()+1);
00329   }
00330 
00331   void pop_back() {
00332     this->setEnd(this->end()-1);
00333   }
00334 };
00335 
00336 
00337 /// This class consists of common code factored out of the SmallVector class to
00338 /// reduce code duplication based on the SmallVector 'N' template parameter.
00339 template <typename T>
00340 class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
00341   typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass;
00342 
00343   SmallVectorImpl(const SmallVectorImpl&) LLVM_DELETED_FUNCTION;
00344 public:
00345   typedef typename SuperClass::iterator iterator;
00346   typedef typename SuperClass::size_type size_type;
00347 
00348 protected:
00349   // Default ctor - Initialize to empty.
00350   explicit SmallVectorImpl(unsigned N)
00351     : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
00352   }
00353 
00354 public:
00355   ~SmallVectorImpl() {
00356     // Destroy the constructed elements in the vector.
00357     this->destroy_range(this->begin(), this->end());
00358 
00359     // If this wasn't grown from the inline copy, deallocate the old space.
00360     if (!this->isSmall())
00361       free(this->begin());
00362   }
00363 
00364 
00365   void clear() {
00366     this->destroy_range(this->begin(), this->end());
00367     this->EndX = this->BeginX;
00368   }
00369 
00370   void resize(unsigned N) {
00371     if (N < this->size()) {
00372       this->destroy_range(this->begin()+N, this->end());
00373       this->setEnd(this->begin()+N);
00374     } else if (N > this->size()) {
00375       if (this->capacity() < N)
00376         this->grow(N);
00377       for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
00378         new (&*I) T();
00379       this->setEnd(this->begin()+N);
00380     }
00381   }
00382 
00383   void resize(unsigned N, const T &NV) {
00384     if (N < this->size()) {
00385       this->destroy_range(this->begin()+N, this->end());
00386       this->setEnd(this->begin()+N);
00387     } else if (N > this->size()) {
00388       if (this->capacity() < N)
00389         this->grow(N);
00390       std::uninitialized_fill(this->end(), this->begin()+N, NV);
00391       this->setEnd(this->begin()+N);
00392     }
00393   }
00394 
00395   void reserve(unsigned N) {
00396     if (this->capacity() < N)
00397       this->grow(N);
00398   }
00399 
00400   T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
00401     T Result = ::std::move(this->back());
00402     this->pop_back();
00403     return Result;
00404   }
00405 
00406   void swap(SmallVectorImpl &RHS);
00407 
00408   /// Add the specified range to the end of the SmallVector.
00409   template<typename in_iter>
00410   void append(in_iter in_start, in_iter in_end) {
00411     size_type NumInputs = std::distance(in_start, in_end);
00412     // Grow allocated space if needed.
00413     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
00414       this->grow(this->size()+NumInputs);
00415 
00416     // Copy the new elements over.
00417     // TODO: NEED To compile time dispatch on whether in_iter is a random access
00418     // iterator to use the fast uninitialized_copy.
00419     std::uninitialized_copy(in_start, in_end, this->end());
00420     this->setEnd(this->end() + NumInputs);
00421   }
00422 
00423   /// Add the specified range to the end of the SmallVector.
00424   void append(size_type NumInputs, const T &Elt) {
00425     // Grow allocated space if needed.
00426     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
00427       this->grow(this->size()+NumInputs);
00428 
00429     // Copy the new elements over.
00430     std::uninitialized_fill_n(this->end(), NumInputs, Elt);
00431     this->setEnd(this->end() + NumInputs);
00432   }
00433 
00434   void assign(unsigned NumElts, const T &Elt) {
00435     clear();
00436     if (this->capacity() < NumElts)
00437       this->grow(NumElts);
00438     this->setEnd(this->begin()+NumElts);
00439     std::uninitialized_fill(this->begin(), this->end(), Elt);
00440   }
00441 
00442   iterator erase(iterator I) {
00443     assert(I >= this->begin() && "Iterator to erase is out of bounds.");
00444     assert(I < this->end() && "Erasing at past-the-end iterator.");
00445 
00446     iterator N = I;
00447     // Shift all elts down one.
00448     this->move(I+1, this->end(), I);
00449     // Drop the last elt.
00450     this->pop_back();
00451     return(N);
00452   }
00453 
00454   iterator erase(iterator S, iterator E) {
00455     assert(S >= this->begin() && "Range to erase is out of bounds.");
00456     assert(S <= E && "Trying to erase invalid range.");
00457     assert(E <= this->end() && "Trying to erase past the end.");
00458 
00459     iterator N = S;
00460     // Shift all elts down.
00461     iterator I = this->move(E, this->end(), S);
00462     // Drop the last elts.
00463     this->destroy_range(I, this->end());
00464     this->setEnd(I);
00465     return(N);
00466   }
00467 
00468   iterator insert(iterator I, T &&Elt) {
00469     if (I == this->end()) {  // Important special case for empty vector.
00470       this->push_back(::std::move(Elt));
00471       return this->end()-1;
00472     }
00473 
00474     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
00475     assert(I <= this->end() && "Inserting past the end of the vector.");
00476 
00477     if (this->EndX >= this->CapacityX) {
00478       size_t EltNo = I-this->begin();
00479       this->grow();
00480       I = this->begin()+EltNo;
00481     }
00482 
00483     ::new ((void*) this->end()) T(::std::move(this->back()));
00484     // Push everything else over.
00485     this->move_backward(I, this->end()-1, this->end());
00486     this->setEnd(this->end()+1);
00487 
00488     // If we just moved the element we're inserting, be sure to update
00489     // the reference.
00490     T *EltPtr = &Elt;
00491     if (I <= EltPtr && EltPtr < this->EndX)
00492       ++EltPtr;
00493 
00494     *I = ::std::move(*EltPtr);
00495     return I;
00496   }
00497 
00498   iterator insert(iterator I, const T &Elt) {
00499     if (I == this->end()) {  // Important special case for empty vector.
00500       this->push_back(Elt);
00501       return this->end()-1;
00502     }
00503 
00504     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
00505     assert(I <= this->end() && "Inserting past the end of the vector.");
00506 
00507     if (this->EndX >= this->CapacityX) {
00508       size_t EltNo = I-this->begin();
00509       this->grow();
00510       I = this->begin()+EltNo;
00511     }
00512     ::new ((void*) this->end()) T(std::move(this->back()));
00513     // Push everything else over.
00514     this->move_backward(I, this->end()-1, this->end());
00515     this->setEnd(this->end()+1);
00516 
00517     // If we just moved the element we're inserting, be sure to update
00518     // the reference.
00519     const T *EltPtr = &Elt;
00520     if (I <= EltPtr && EltPtr < this->EndX)
00521       ++EltPtr;
00522 
00523     *I = *EltPtr;
00524     return I;
00525   }
00526 
00527   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
00528     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
00529     size_t InsertElt = I - this->begin();
00530 
00531     if (I == this->end()) {  // Important special case for empty vector.
00532       append(NumToInsert, Elt);
00533       return this->begin()+InsertElt;
00534     }
00535 
00536     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
00537     assert(I <= this->end() && "Inserting past the end of the vector.");
00538 
00539     // Ensure there is enough space.
00540     reserve(static_cast<unsigned>(this->size() + NumToInsert));
00541 
00542     // Uninvalidate the iterator.
00543     I = this->begin()+InsertElt;
00544 
00545     // If there are more elements between the insertion point and the end of the
00546     // range than there are being inserted, we can use a simple approach to
00547     // insertion.  Since we already reserved space, we know that this won't
00548     // reallocate the vector.
00549     if (size_t(this->end()-I) >= NumToInsert) {
00550       T *OldEnd = this->end();
00551       append(std::move_iterator<iterator>(this->end() - NumToInsert),
00552              std::move_iterator<iterator>(this->end()));
00553 
00554       // Copy the existing elements that get replaced.
00555       this->move_backward(I, OldEnd-NumToInsert, OldEnd);
00556 
00557       std::fill_n(I, NumToInsert, Elt);
00558       return I;
00559     }
00560 
00561     // Otherwise, we're inserting more elements than exist already, and we're
00562     // not inserting at the end.
00563 
00564     // Move over the elements that we're about to overwrite.
00565     T *OldEnd = this->end();
00566     this->setEnd(this->end() + NumToInsert);
00567     size_t NumOverwritten = OldEnd-I;
00568     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
00569 
00570     // Replace the overwritten part.
00571     std::fill_n(I, NumOverwritten, Elt);
00572 
00573     // Insert the non-overwritten middle part.
00574     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
00575     return I;
00576   }
00577 
00578   template<typename ItTy>
00579   iterator insert(iterator I, ItTy From, ItTy To) {
00580     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
00581     size_t InsertElt = I - this->begin();
00582 
00583     if (I == this->end()) {  // Important special case for empty vector.
00584       append(From, To);
00585       return this->begin()+InsertElt;
00586     }
00587 
00588     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
00589     assert(I <= this->end() && "Inserting past the end of the vector.");
00590 
00591     size_t NumToInsert = std::distance(From, To);
00592 
00593     // Ensure there is enough space.
00594     reserve(static_cast<unsigned>(this->size() + NumToInsert));
00595 
00596     // Uninvalidate the iterator.
00597     I = this->begin()+InsertElt;
00598 
00599     // If there are more elements between the insertion point and the end of the
00600     // range than there are being inserted, we can use a simple approach to
00601     // insertion.  Since we already reserved space, we know that this won't
00602     // reallocate the vector.
00603     if (size_t(this->end()-I) >= NumToInsert) {
00604       T *OldEnd = this->end();
00605       append(std::move_iterator<iterator>(this->end() - NumToInsert),
00606              std::move_iterator<iterator>(this->end()));
00607 
00608       // Copy the existing elements that get replaced.
00609       this->move_backward(I, OldEnd-NumToInsert, OldEnd);
00610 
00611       std::copy(From, To, I);
00612       return I;
00613     }
00614 
00615     // Otherwise, we're inserting more elements than exist already, and we're
00616     // not inserting at the end.
00617 
00618     // Move over the elements that we're about to overwrite.
00619     T *OldEnd = this->end();
00620     this->setEnd(this->end() + NumToInsert);
00621     size_t NumOverwritten = OldEnd-I;
00622     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
00623 
00624     // Replace the overwritten part.
00625     for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
00626       *J = *From;
00627       ++J; ++From;
00628     }
00629 
00630     // Insert the non-overwritten middle part.
00631     this->uninitialized_copy(From, To, OldEnd);
00632     return I;
00633   }
00634 
00635   SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
00636 
00637   SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
00638 
00639   bool operator==(const SmallVectorImpl &RHS) const {
00640     if (this->size() != RHS.size()) return false;
00641     return std::equal(this->begin(), this->end(), RHS.begin());
00642   }
00643   bool operator!=(const SmallVectorImpl &RHS) const {
00644     return !(*this == RHS);
00645   }
00646 
00647   bool operator<(const SmallVectorImpl &RHS) const {
00648     return std::lexicographical_compare(this->begin(), this->end(),
00649                                         RHS.begin(), RHS.end());
00650   }
00651 
00652   /// Set the array size to \p N, which the current array must have enough
00653   /// capacity for.
00654   ///
00655   /// This does not construct or destroy any elements in the vector.
00656   ///
00657   /// Clients can use this in conjunction with capacity() to write past the end
00658   /// of the buffer when they know that more elements are available, and only
00659   /// update the size later. This avoids the cost of value initializing elements
00660   /// which will only be overwritten.
00661   void set_size(unsigned N) {
00662     assert(N <= this->capacity());
00663     this->setEnd(this->begin() + N);
00664   }
00665 };
00666 
00667 
00668 template <typename T>
00669 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
00670   if (this == &RHS) return;
00671 
00672   // We can only avoid copying elements if neither vector is small.
00673   if (!this->isSmall() && !RHS.isSmall()) {
00674     std::swap(this->BeginX, RHS.BeginX);
00675     std::swap(this->EndX, RHS.EndX);
00676     std::swap(this->CapacityX, RHS.CapacityX);
00677     return;
00678   }
00679   if (RHS.size() > this->capacity())
00680     this->grow(RHS.size());
00681   if (this->size() > RHS.capacity())
00682     RHS.grow(this->size());
00683 
00684   // Swap the shared elements.
00685   size_t NumShared = this->size();
00686   if (NumShared > RHS.size()) NumShared = RHS.size();
00687   for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i)
00688     std::swap((*this)[i], RHS[i]);
00689 
00690   // Copy over the extra elts.
00691   if (this->size() > RHS.size()) {
00692     size_t EltDiff = this->size() - RHS.size();
00693     this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
00694     RHS.setEnd(RHS.end()+EltDiff);
00695     this->destroy_range(this->begin()+NumShared, this->end());
00696     this->setEnd(this->begin()+NumShared);
00697   } else if (RHS.size() > this->size()) {
00698     size_t EltDiff = RHS.size() - this->size();
00699     this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
00700     this->setEnd(this->end() + EltDiff);
00701     this->destroy_range(RHS.begin()+NumShared, RHS.end());
00702     RHS.setEnd(RHS.begin()+NumShared);
00703   }
00704 }
00705 
00706 template <typename T>
00707 SmallVectorImpl<T> &SmallVectorImpl<T>::
00708   operator=(const SmallVectorImpl<T> &RHS) {
00709   // Avoid self-assignment.
00710   if (this == &RHS) return *this;
00711 
00712   // If we already have sufficient space, assign the common elements, then
00713   // destroy any excess.
00714   size_t RHSSize = RHS.size();
00715   size_t CurSize = this->size();
00716   if (CurSize >= RHSSize) {
00717     // Assign common elements.
00718     iterator NewEnd;
00719     if (RHSSize)
00720       NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
00721     else
00722       NewEnd = this->begin();
00723 
00724     // Destroy excess elements.
00725     this->destroy_range(NewEnd, this->end());
00726 
00727     // Trim.
00728     this->setEnd(NewEnd);
00729     return *this;
00730   }
00731 
00732   // If we have to grow to have enough elements, destroy the current elements.
00733   // This allows us to avoid copying them during the grow.
00734   // FIXME: don't do this if they're efficiently moveable.
00735   if (this->capacity() < RHSSize) {
00736     // Destroy current elements.
00737     this->destroy_range(this->begin(), this->end());
00738     this->setEnd(this->begin());
00739     CurSize = 0;
00740     this->grow(RHSSize);
00741   } else if (CurSize) {
00742     // Otherwise, use assignment for the already-constructed elements.
00743     std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
00744   }
00745 
00746   // Copy construct the new elements in place.
00747   this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
00748                            this->begin()+CurSize);
00749 
00750   // Set end.
00751   this->setEnd(this->begin()+RHSSize);
00752   return *this;
00753 }
00754 
00755 template <typename T>
00756 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
00757   // Avoid self-assignment.
00758   if (this == &RHS) return *this;
00759 
00760   // If the RHS isn't small, clear this vector and then steal its buffer.
00761   if (!RHS.isSmall()) {
00762     this->destroy_range(this->begin(), this->end());
00763     if (!this->isSmall()) free(this->begin());
00764     this->BeginX = RHS.BeginX;
00765     this->EndX = RHS.EndX;
00766     this->CapacityX = RHS.CapacityX;
00767     RHS.resetToSmall();
00768     return *this;
00769   }
00770 
00771   // If we already have sufficient space, assign the common elements, then
00772   // destroy any excess.
00773   size_t RHSSize = RHS.size();
00774   size_t CurSize = this->size();
00775   if (CurSize >= RHSSize) {
00776     // Assign common elements.
00777     iterator NewEnd = this->begin();
00778     if (RHSSize)
00779       NewEnd = this->move(RHS.begin(), RHS.end(), NewEnd);
00780 
00781     // Destroy excess elements and trim the bounds.
00782     this->destroy_range(NewEnd, this->end());
00783     this->setEnd(NewEnd);
00784 
00785     // Clear the RHS.
00786     RHS.clear();
00787 
00788     return *this;
00789   }
00790 
00791   // If we have to grow to have enough elements, destroy the current elements.
00792   // This allows us to avoid copying them during the grow.
00793   // FIXME: this may not actually make any sense if we can efficiently move
00794   // elements.
00795   if (this->capacity() < RHSSize) {
00796     // Destroy current elements.
00797     this->destroy_range(this->begin(), this->end());
00798     this->setEnd(this->begin());
00799     CurSize = 0;
00800     this->grow(RHSSize);
00801   } else if (CurSize) {
00802     // Otherwise, use assignment for the already-constructed elements.
00803     this->move(RHS.begin(), RHS.begin()+CurSize, this->begin());
00804   }
00805 
00806   // Move-construct the new elements in place.
00807   this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
00808                            this->begin()+CurSize);
00809 
00810   // Set end.
00811   this->setEnd(this->begin()+RHSSize);
00812 
00813   RHS.clear();
00814   return *this;
00815 }
00816 
00817 /// Storage for the SmallVector elements which aren't contained in
00818 /// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1'
00819 /// element is in the base class. This is specialized for the N=1 and N=0 cases
00820 /// to avoid allocating unnecessary storage.
00821 template <typename T, unsigned N>
00822 struct SmallVectorStorage {
00823   typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
00824 };
00825 template <typename T> struct SmallVectorStorage<T, 1> {};
00826 template <typename T> struct SmallVectorStorage<T, 0> {};
00827 
00828 /// This is a 'vector' (really, a variable-sized array), optimized
00829 /// for the case when the array is small.  It contains some number of elements
00830 /// in-place, which allows it to avoid heap allocation when the actual number of
00831 /// elements is below that threshold.  This allows normal "small" cases to be
00832 /// fast without losing generality for large inputs.
00833 ///
00834 /// Note that this does not attempt to be exception safe.
00835 ///
00836 template <typename T, unsigned N>
00837 class SmallVector : public SmallVectorImpl<T> {
00838   /// Inline space for elements which aren't stored in the base class.
00839   SmallVectorStorage<T, N> Storage;
00840 public:
00841   SmallVector() : SmallVectorImpl<T>(N) {
00842   }
00843 
00844   explicit SmallVector(unsigned Size, const T &Value = T())
00845     : SmallVectorImpl<T>(N) {
00846     this->assign(Size, Value);
00847   }
00848 
00849   template<typename ItTy>
00850   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
00851     this->append(S, E);
00852   }
00853 
00854   template <typename RangeTy>
00855   explicit SmallVector(const llvm::iterator_range<RangeTy> R)
00856       : SmallVectorImpl<T>(N) {
00857     this->append(R.begin(), R.end());
00858   }
00859 
00860   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
00861     if (!RHS.empty())
00862       SmallVectorImpl<T>::operator=(RHS);
00863   }
00864 
00865   const SmallVector &operator=(const SmallVector &RHS) {
00866     SmallVectorImpl<T>::operator=(RHS);
00867     return *this;
00868   }
00869 
00870   SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
00871     if (!RHS.empty())
00872       SmallVectorImpl<T>::operator=(::std::move(RHS));
00873   }
00874 
00875   const SmallVector &operator=(SmallVector &&RHS) {
00876     SmallVectorImpl<T>::operator=(::std::move(RHS));
00877     return *this;
00878   }
00879 };
00880 
00881 template<typename T, unsigned N>
00882 static inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
00883   return X.capacity_in_bytes();
00884 }
00885 
00886 } // End llvm namespace
00887 
00888 namespace std {
00889   /// Implement std::swap in terms of SmallVector swap.
00890   template<typename T>
00891   inline void
00892   swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
00893     LHS.swap(RHS);
00894   }
00895 
00896   /// Implement std::swap in terms of SmallVector swap.
00897   template<typename T, unsigned N>
00898   inline void
00899   swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
00900     LHS.swap(RHS);
00901   }
00902 }
00903 
00904 #endif