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 #if LLVM_HAS_VARIADIC_TEMPLATES
00241   template <typename... ArgTypes> void emplace_back(ArgTypes &&... Args) {
00242     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
00243       this->grow();
00244     ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
00245     this->setEnd(this->end() + 1);
00246   }
00247 #else
00248 private:
00249   template <typename Constructor> void emplace_back_impl(Constructor construct) {
00250     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
00251       this->grow();
00252     construct((void *)this->end());
00253     this->setEnd(this->end() + 1);
00254   }
00255 
00256 public:
00257   void emplace_back() {
00258     emplace_back_impl([](void *Mem) { ::new (Mem) T(); });
00259   }
00260   template <typename T1> void emplace_back(T1 &&A1) {
00261     emplace_back_impl([&](void *Mem) { ::new (Mem) T(std::forward<T1>(A1)); });
00262   }
00263   template <typename T1, typename T2> void emplace_back(T1 &&A1, T2 &&A2) {
00264     emplace_back_impl([&](void *Mem) {
00265       ::new (Mem) T(std::forward<T1>(A1), std::forward<T2>(A2));
00266     });
00267   }
00268   template <typename T1, typename T2, typename T3>
00269   void emplace_back(T1 &&A1, T2 &&A2, T3 &&A3) {
00270     T(std::forward<T1>(A1), std::forward<T2>(A2), std::forward<T3>(A3));
00271     emplace_back_impl([&](void *Mem) {
00272       ::new (Mem)
00273           T(std::forward<T1>(A1), std::forward<T2>(A2), std::forward<T3>(A3));
00274     });
00275   }
00276   template <typename T1, typename T2, typename T3, typename T4>
00277   void emplace_back(T1 &&A1, T2 &&A2, T3 &&A3, T4 &&A4) {
00278     emplace_back_impl([&](void *Mem) {
00279       ::new (Mem) T(std::forward<T1>(A1), std::forward<T2>(A2),
00280                     std::forward<T3>(A3), std::forward<T4>(A4));
00281     });
00282   }
00283 #endif // LLVM_HAS_VARIADIC_TEMPLATES
00284 };
00285 
00286 // Define this out-of-line to dissuade the C++ compiler from inlining it.
00287 template <typename T, bool isPodLike>
00288 void SmallVectorTemplateBase<T, isPodLike>::grow(size_t MinSize) {
00289   size_t CurCapacity = this->capacity();
00290   size_t CurSize = this->size();
00291   // Always grow, even from zero.
00292   size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2));
00293   if (NewCapacity < MinSize)
00294     NewCapacity = MinSize;
00295   T *NewElts = static_cast<T*>(malloc(NewCapacity*sizeof(T)));
00296 
00297   // Move the elements over.
00298   this->uninitialized_move(this->begin(), this->end(), NewElts);
00299 
00300   // Destroy the original elements.
00301   destroy_range(this->begin(), this->end());
00302 
00303   // If this wasn't grown from the inline copy, deallocate the old space.
00304   if (!this->isSmall())
00305     free(this->begin());
00306 
00307   this->setEnd(NewElts+CurSize);
00308   this->BeginX = NewElts;
00309   this->CapacityX = this->begin()+NewCapacity;
00310 }
00311 
00312 
00313 /// SmallVectorTemplateBase<isPodLike = true> - This is where we put method
00314 /// implementations that are designed to work with POD-like T's.
00315 template <typename T>
00316 class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
00317 protected:
00318   SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
00319 
00320   // No need to do a destroy loop for POD's.
00321   static void destroy_range(T *, T *) {}
00322 
00323   /// Use move-assignment to move the range [I, E) onto the
00324   /// objects starting with "Dest".  For PODs, this is just memcpy.
00325   template<typename It1, typename It2>
00326   static It2 move(It1 I, It1 E, It2 Dest) {
00327     return ::std::copy(I, E, Dest);
00328   }
00329 
00330   /// Use move-assignment to move the range [I, E) onto the objects ending at
00331   /// "Dest", moving objects in reverse order.
00332   template<typename It1, typename It2>
00333   static It2 move_backward(It1 I, It1 E, It2 Dest) {
00334     return ::std::copy_backward(I, E, Dest);
00335   }
00336 
00337   /// Move the range [I, E) onto the uninitialized memory
00338   /// starting with "Dest", constructing elements into it as needed.
00339   template<typename It1, typename It2>
00340   static void uninitialized_move(It1 I, It1 E, It2 Dest) {
00341     // Just do a copy.
00342     uninitialized_copy(I, E, Dest);
00343   }
00344 
00345   /// Copy the range [I, E) onto the uninitialized memory
00346   /// starting with "Dest", constructing elements into it as needed.
00347   template<typename It1, typename It2>
00348   static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
00349     // Arbitrary iterator types; just use the basic implementation.
00350     std::uninitialized_copy(I, E, Dest);
00351   }
00352 
00353   /// Copy the range [I, E) onto the uninitialized memory
00354   /// starting with "Dest", constructing elements into it as needed.
00355   template<typename T1, typename T2>
00356   static void uninitialized_copy(T1 *I, T1 *E, T2 *Dest) {
00357     // Use memcpy for PODs iterated by pointers (which includes SmallVector
00358     // iterators): std::uninitialized_copy optimizes to memmove, but we can
00359     // use memcpy here.
00360     memcpy(Dest, I, (E-I)*sizeof(T));
00361   }
00362 
00363   /// Double the size of the allocated memory, guaranteeing space for at
00364   /// least one more element or MinSize if specified.
00365   void grow(size_t MinSize = 0) {
00366     this->grow_pod(MinSize*sizeof(T), sizeof(T));
00367   }
00368 public:
00369   void push_back(const T &Elt) {
00370     if (LLVM_UNLIKELY(this->EndX >= this->CapacityX))
00371       this->grow();
00372     memcpy(this->end(), &Elt, sizeof(T));
00373     this->setEnd(this->end()+1);
00374   }
00375 
00376   void pop_back() {
00377     this->setEnd(this->end()-1);
00378   }
00379 };
00380 
00381 
00382 /// This class consists of common code factored out of the SmallVector class to
00383 /// reduce code duplication based on the SmallVector 'N' template parameter.
00384 template <typename T>
00385 class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
00386   typedef SmallVectorTemplateBase<T, isPodLike<T>::value > SuperClass;
00387 
00388   SmallVectorImpl(const SmallVectorImpl&) LLVM_DELETED_FUNCTION;
00389 public:
00390   typedef typename SuperClass::iterator iterator;
00391   typedef typename SuperClass::size_type size_type;
00392 
00393 protected:
00394   // Default ctor - Initialize to empty.
00395   explicit SmallVectorImpl(unsigned N)
00396     : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
00397   }
00398 
00399 public:
00400   ~SmallVectorImpl() {
00401     // Destroy the constructed elements in the vector.
00402     this->destroy_range(this->begin(), this->end());
00403 
00404     // If this wasn't grown from the inline copy, deallocate the old space.
00405     if (!this->isSmall())
00406       free(this->begin());
00407   }
00408 
00409 
00410   void clear() {
00411     this->destroy_range(this->begin(), this->end());
00412     this->EndX = this->BeginX;
00413   }
00414 
00415   void resize(size_type N) {
00416     if (N < this->size()) {
00417       this->destroy_range(this->begin()+N, this->end());
00418       this->setEnd(this->begin()+N);
00419     } else if (N > this->size()) {
00420       if (this->capacity() < N)
00421         this->grow(N);
00422       for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
00423         new (&*I) T();
00424       this->setEnd(this->begin()+N);
00425     }
00426   }
00427 
00428   void resize(size_type N, const T &NV) {
00429     if (N < this->size()) {
00430       this->destroy_range(this->begin()+N, this->end());
00431       this->setEnd(this->begin()+N);
00432     } else if (N > this->size()) {
00433       if (this->capacity() < N)
00434         this->grow(N);
00435       std::uninitialized_fill(this->end(), this->begin()+N, NV);
00436       this->setEnd(this->begin()+N);
00437     }
00438   }
00439 
00440   void reserve(size_type N) {
00441     if (this->capacity() < N)
00442       this->grow(N);
00443   }
00444 
00445   T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val() {
00446     T Result = ::std::move(this->back());
00447     this->pop_back();
00448     return Result;
00449   }
00450 
00451   void swap(SmallVectorImpl &RHS);
00452 
00453   /// Add the specified range to the end of the SmallVector.
00454   template<typename in_iter>
00455   void append(in_iter in_start, in_iter in_end) {
00456     size_type NumInputs = std::distance(in_start, in_end);
00457     // Grow allocated space if needed.
00458     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
00459       this->grow(this->size()+NumInputs);
00460 
00461     // Copy the new elements over.
00462     // TODO: NEED To compile time dispatch on whether in_iter is a random access
00463     // iterator to use the fast uninitialized_copy.
00464     std::uninitialized_copy(in_start, in_end, this->end());
00465     this->setEnd(this->end() + NumInputs);
00466   }
00467 
00468   /// Add the specified range to the end of the SmallVector.
00469   void append(size_type NumInputs, const T &Elt) {
00470     // Grow allocated space if needed.
00471     if (NumInputs > size_type(this->capacity_ptr()-this->end()))
00472       this->grow(this->size()+NumInputs);
00473 
00474     // Copy the new elements over.
00475     std::uninitialized_fill_n(this->end(), NumInputs, Elt);
00476     this->setEnd(this->end() + NumInputs);
00477   }
00478 
00479   void assign(size_type NumElts, const T &Elt) {
00480     clear();
00481     if (this->capacity() < NumElts)
00482       this->grow(NumElts);
00483     this->setEnd(this->begin()+NumElts);
00484     std::uninitialized_fill(this->begin(), this->end(), Elt);
00485   }
00486 
00487   iterator erase(iterator I) {
00488     assert(I >= this->begin() && "Iterator to erase is out of bounds.");
00489     assert(I < this->end() && "Erasing at past-the-end iterator.");
00490 
00491     iterator N = I;
00492     // Shift all elts down one.
00493     this->move(I+1, this->end(), I);
00494     // Drop the last elt.
00495     this->pop_back();
00496     return(N);
00497   }
00498 
00499   iterator erase(iterator S, iterator E) {
00500     assert(S >= this->begin() && "Range to erase is out of bounds.");
00501     assert(S <= E && "Trying to erase invalid range.");
00502     assert(E <= this->end() && "Trying to erase past the end.");
00503 
00504     iterator N = S;
00505     // Shift all elts down.
00506     iterator I = this->move(E, this->end(), S);
00507     // Drop the last elts.
00508     this->destroy_range(I, this->end());
00509     this->setEnd(I);
00510     return(N);
00511   }
00512 
00513   iterator insert(iterator I, T &&Elt) {
00514     if (I == this->end()) {  // Important special case for empty vector.
00515       this->push_back(::std::move(Elt));
00516       return this->end()-1;
00517     }
00518 
00519     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
00520     assert(I <= this->end() && "Inserting past the end of the vector.");
00521 
00522     if (this->EndX >= this->CapacityX) {
00523       size_t EltNo = I-this->begin();
00524       this->grow();
00525       I = this->begin()+EltNo;
00526     }
00527 
00528     ::new ((void*) this->end()) T(::std::move(this->back()));
00529     // Push everything else over.
00530     this->move_backward(I, this->end()-1, this->end());
00531     this->setEnd(this->end()+1);
00532 
00533     // If we just moved the element we're inserting, be sure to update
00534     // the reference.
00535     T *EltPtr = &Elt;
00536     if (I <= EltPtr && EltPtr < this->EndX)
00537       ++EltPtr;
00538 
00539     *I = ::std::move(*EltPtr);
00540     return I;
00541   }
00542 
00543   iterator insert(iterator I, const T &Elt) {
00544     if (I == this->end()) {  // Important special case for empty vector.
00545       this->push_back(Elt);
00546       return this->end()-1;
00547     }
00548 
00549     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
00550     assert(I <= this->end() && "Inserting past the end of the vector.");
00551 
00552     if (this->EndX >= this->CapacityX) {
00553       size_t EltNo = I-this->begin();
00554       this->grow();
00555       I = this->begin()+EltNo;
00556     }
00557     ::new ((void*) this->end()) T(std::move(this->back()));
00558     // Push everything else over.
00559     this->move_backward(I, this->end()-1, this->end());
00560     this->setEnd(this->end()+1);
00561 
00562     // If we just moved the element we're inserting, be sure to update
00563     // the reference.
00564     const T *EltPtr = &Elt;
00565     if (I <= EltPtr && EltPtr < this->EndX)
00566       ++EltPtr;
00567 
00568     *I = *EltPtr;
00569     return I;
00570   }
00571 
00572   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
00573     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
00574     size_t InsertElt = I - this->begin();
00575 
00576     if (I == this->end()) {  // Important special case for empty vector.
00577       append(NumToInsert, Elt);
00578       return this->begin()+InsertElt;
00579     }
00580 
00581     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
00582     assert(I <= this->end() && "Inserting past the end of the vector.");
00583 
00584     // Ensure there is enough space.
00585     reserve(this->size() + NumToInsert);
00586 
00587     // Uninvalidate the iterator.
00588     I = this->begin()+InsertElt;
00589 
00590     // If there are more elements between the insertion point and the end of the
00591     // range than there are being inserted, we can use a simple approach to
00592     // insertion.  Since we already reserved space, we know that this won't
00593     // reallocate the vector.
00594     if (size_t(this->end()-I) >= NumToInsert) {
00595       T *OldEnd = this->end();
00596       append(std::move_iterator<iterator>(this->end() - NumToInsert),
00597              std::move_iterator<iterator>(this->end()));
00598 
00599       // Copy the existing elements that get replaced.
00600       this->move_backward(I, OldEnd-NumToInsert, OldEnd);
00601 
00602       std::fill_n(I, NumToInsert, Elt);
00603       return I;
00604     }
00605 
00606     // Otherwise, we're inserting more elements than exist already, and we're
00607     // not inserting at the end.
00608 
00609     // Move over the elements that we're about to overwrite.
00610     T *OldEnd = this->end();
00611     this->setEnd(this->end() + NumToInsert);
00612     size_t NumOverwritten = OldEnd-I;
00613     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
00614 
00615     // Replace the overwritten part.
00616     std::fill_n(I, NumOverwritten, Elt);
00617 
00618     // Insert the non-overwritten middle part.
00619     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
00620     return I;
00621   }
00622 
00623   template<typename ItTy>
00624   iterator insert(iterator I, ItTy From, ItTy To) {
00625     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
00626     size_t InsertElt = I - this->begin();
00627 
00628     if (I == this->end()) {  // Important special case for empty vector.
00629       append(From, To);
00630       return this->begin()+InsertElt;
00631     }
00632 
00633     assert(I >= this->begin() && "Insertion iterator is out of bounds.");
00634     assert(I <= this->end() && "Inserting past the end of the vector.");
00635 
00636     size_t NumToInsert = std::distance(From, To);
00637 
00638     // Ensure there is enough space.
00639     reserve(this->size() + NumToInsert);
00640 
00641     // Uninvalidate the iterator.
00642     I = this->begin()+InsertElt;
00643 
00644     // If there are more elements between the insertion point and the end of the
00645     // range than there are being inserted, we can use a simple approach to
00646     // insertion.  Since we already reserved space, we know that this won't
00647     // reallocate the vector.
00648     if (size_t(this->end()-I) >= NumToInsert) {
00649       T *OldEnd = this->end();
00650       append(std::move_iterator<iterator>(this->end() - NumToInsert),
00651              std::move_iterator<iterator>(this->end()));
00652 
00653       // Copy the existing elements that get replaced.
00654       this->move_backward(I, OldEnd-NumToInsert, OldEnd);
00655 
00656       std::copy(From, To, I);
00657       return I;
00658     }
00659 
00660     // Otherwise, we're inserting more elements than exist already, and we're
00661     // not inserting at the end.
00662 
00663     // Move over the elements that we're about to overwrite.
00664     T *OldEnd = this->end();
00665     this->setEnd(this->end() + NumToInsert);
00666     size_t NumOverwritten = OldEnd-I;
00667     this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
00668 
00669     // Replace the overwritten part.
00670     for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
00671       *J = *From;
00672       ++J; ++From;
00673     }
00674 
00675     // Insert the non-overwritten middle part.
00676     this->uninitialized_copy(From, To, OldEnd);
00677     return I;
00678   }
00679 
00680   SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
00681 
00682   SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
00683 
00684   bool operator==(const SmallVectorImpl &RHS) const {
00685     if (this->size() != RHS.size()) return false;
00686     return std::equal(this->begin(), this->end(), RHS.begin());
00687   }
00688   bool operator!=(const SmallVectorImpl &RHS) const {
00689     return !(*this == RHS);
00690   }
00691 
00692   bool operator<(const SmallVectorImpl &RHS) const {
00693     return std::lexicographical_compare(this->begin(), this->end(),
00694                                         RHS.begin(), RHS.end());
00695   }
00696 
00697   /// Set the array size to \p N, which the current array must have enough
00698   /// capacity for.
00699   ///
00700   /// This does not construct or destroy any elements in the vector.
00701   ///
00702   /// Clients can use this in conjunction with capacity() to write past the end
00703   /// of the buffer when they know that more elements are available, and only
00704   /// update the size later. This avoids the cost of value initializing elements
00705   /// which will only be overwritten.
00706   void set_size(size_type N) {
00707     assert(N <= this->capacity());
00708     this->setEnd(this->begin() + N);
00709   }
00710 };
00711 
00712 
00713 template <typename T>
00714 void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
00715   if (this == &RHS) return;
00716 
00717   // We can only avoid copying elements if neither vector is small.
00718   if (!this->isSmall() && !RHS.isSmall()) {
00719     std::swap(this->BeginX, RHS.BeginX);
00720     std::swap(this->EndX, RHS.EndX);
00721     std::swap(this->CapacityX, RHS.CapacityX);
00722     return;
00723   }
00724   if (RHS.size() > this->capacity())
00725     this->grow(RHS.size());
00726   if (this->size() > RHS.capacity())
00727     RHS.grow(this->size());
00728 
00729   // Swap the shared elements.
00730   size_t NumShared = this->size();
00731   if (NumShared > RHS.size()) NumShared = RHS.size();
00732   for (size_type i = 0; i != NumShared; ++i)
00733     std::swap((*this)[i], RHS[i]);
00734 
00735   // Copy over the extra elts.
00736   if (this->size() > RHS.size()) {
00737     size_t EltDiff = this->size() - RHS.size();
00738     this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
00739     RHS.setEnd(RHS.end()+EltDiff);
00740     this->destroy_range(this->begin()+NumShared, this->end());
00741     this->setEnd(this->begin()+NumShared);
00742   } else if (RHS.size() > this->size()) {
00743     size_t EltDiff = RHS.size() - this->size();
00744     this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
00745     this->setEnd(this->end() + EltDiff);
00746     this->destroy_range(RHS.begin()+NumShared, RHS.end());
00747     RHS.setEnd(RHS.begin()+NumShared);
00748   }
00749 }
00750 
00751 template <typename T>
00752 SmallVectorImpl<T> &SmallVectorImpl<T>::
00753   operator=(const SmallVectorImpl<T> &RHS) {
00754   // Avoid self-assignment.
00755   if (this == &RHS) return *this;
00756 
00757   // If we already have sufficient space, assign the common elements, then
00758   // destroy any excess.
00759   size_t RHSSize = RHS.size();
00760   size_t CurSize = this->size();
00761   if (CurSize >= RHSSize) {
00762     // Assign common elements.
00763     iterator NewEnd;
00764     if (RHSSize)
00765       NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
00766     else
00767       NewEnd = this->begin();
00768 
00769     // Destroy excess elements.
00770     this->destroy_range(NewEnd, this->end());
00771 
00772     // Trim.
00773     this->setEnd(NewEnd);
00774     return *this;
00775   }
00776 
00777   // If we have to grow to have enough elements, destroy the current elements.
00778   // This allows us to avoid copying them during the grow.
00779   // FIXME: don't do this if they're efficiently moveable.
00780   if (this->capacity() < RHSSize) {
00781     // Destroy current elements.
00782     this->destroy_range(this->begin(), this->end());
00783     this->setEnd(this->begin());
00784     CurSize = 0;
00785     this->grow(RHSSize);
00786   } else if (CurSize) {
00787     // Otherwise, use assignment for the already-constructed elements.
00788     std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
00789   }
00790 
00791   // Copy construct the new elements in place.
00792   this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
00793                            this->begin()+CurSize);
00794 
00795   // Set end.
00796   this->setEnd(this->begin()+RHSSize);
00797   return *this;
00798 }
00799 
00800 template <typename T>
00801 SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
00802   // Avoid self-assignment.
00803   if (this == &RHS) return *this;
00804 
00805   // If the RHS isn't small, clear this vector and then steal its buffer.
00806   if (!RHS.isSmall()) {
00807     this->destroy_range(this->begin(), this->end());
00808     if (!this->isSmall()) free(this->begin());
00809     this->BeginX = RHS.BeginX;
00810     this->EndX = RHS.EndX;
00811     this->CapacityX = RHS.CapacityX;
00812     RHS.resetToSmall();
00813     return *this;
00814   }
00815 
00816   // If we already have sufficient space, assign the common elements, then
00817   // destroy any excess.
00818   size_t RHSSize = RHS.size();
00819   size_t CurSize = this->size();
00820   if (CurSize >= RHSSize) {
00821     // Assign common elements.
00822     iterator NewEnd = this->begin();
00823     if (RHSSize)
00824       NewEnd = this->move(RHS.begin(), RHS.end(), NewEnd);
00825 
00826     // Destroy excess elements and trim the bounds.
00827     this->destroy_range(NewEnd, this->end());
00828     this->setEnd(NewEnd);
00829 
00830     // Clear the RHS.
00831     RHS.clear();
00832 
00833     return *this;
00834   }
00835 
00836   // If we have to grow to have enough elements, destroy the current elements.
00837   // This allows us to avoid copying them during the grow.
00838   // FIXME: this may not actually make any sense if we can efficiently move
00839   // elements.
00840   if (this->capacity() < RHSSize) {
00841     // Destroy current elements.
00842     this->destroy_range(this->begin(), this->end());
00843     this->setEnd(this->begin());
00844     CurSize = 0;
00845     this->grow(RHSSize);
00846   } else if (CurSize) {
00847     // Otherwise, use assignment for the already-constructed elements.
00848     this->move(RHS.begin(), RHS.begin()+CurSize, this->begin());
00849   }
00850 
00851   // Move-construct the new elements in place.
00852   this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
00853                            this->begin()+CurSize);
00854 
00855   // Set end.
00856   this->setEnd(this->begin()+RHSSize);
00857 
00858   RHS.clear();
00859   return *this;
00860 }
00861 
00862 /// Storage for the SmallVector elements which aren't contained in
00863 /// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1'
00864 /// element is in the base class. This is specialized for the N=1 and N=0 cases
00865 /// to avoid allocating unnecessary storage.
00866 template <typename T, unsigned N>
00867 struct SmallVectorStorage {
00868   typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
00869 };
00870 template <typename T> struct SmallVectorStorage<T, 1> {};
00871 template <typename T> struct SmallVectorStorage<T, 0> {};
00872 
00873 /// This is a 'vector' (really, a variable-sized array), optimized
00874 /// for the case when the array is small.  It contains some number of elements
00875 /// in-place, which allows it to avoid heap allocation when the actual number of
00876 /// elements is below that threshold.  This allows normal "small" cases to be
00877 /// fast without losing generality for large inputs.
00878 ///
00879 /// Note that this does not attempt to be exception safe.
00880 ///
00881 template <typename T, unsigned N>
00882 class SmallVector : public SmallVectorImpl<T> {
00883   /// Inline space for elements which aren't stored in the base class.
00884   SmallVectorStorage<T, N> Storage;
00885 public:
00886   SmallVector() : SmallVectorImpl<T>(N) {
00887   }
00888 
00889   explicit SmallVector(size_t Size, const T &Value = T())
00890     : SmallVectorImpl<T>(N) {
00891     this->assign(Size, Value);
00892   }
00893 
00894   template<typename ItTy>
00895   SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
00896     this->append(S, E);
00897   }
00898 
00899   template <typename RangeTy>
00900   explicit SmallVector(const llvm::iterator_range<RangeTy> R)
00901       : SmallVectorImpl<T>(N) {
00902     this->append(R.begin(), R.end());
00903   }
00904 
00905   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
00906     if (!RHS.empty())
00907       SmallVectorImpl<T>::operator=(RHS);
00908   }
00909 
00910   const SmallVector &operator=(const SmallVector &RHS) {
00911     SmallVectorImpl<T>::operator=(RHS);
00912     return *this;
00913   }
00914 
00915   SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
00916     if (!RHS.empty())
00917       SmallVectorImpl<T>::operator=(::std::move(RHS));
00918   }
00919 
00920   const SmallVector &operator=(SmallVector &&RHS) {
00921     SmallVectorImpl<T>::operator=(::std::move(RHS));
00922     return *this;
00923   }
00924 };
00925 
00926 template<typename T, unsigned N>
00927 static inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
00928   return X.capacity_in_bytes();
00929 }
00930 
00931 } // End llvm namespace
00932 
00933 namespace std {
00934   /// Implement std::swap in terms of SmallVector swap.
00935   template<typename T>
00936   inline void
00937   swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
00938     LHS.swap(RHS);
00939   }
00940 
00941   /// Implement std::swap in terms of SmallVector swap.
00942   template<typename T, unsigned N>
00943   inline void
00944   swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
00945     LHS.swap(RHS);
00946   }
00947 }
00948 
00949 #endif