+ void grow(unsigned MinSize = 0);
+
+ void construct_range(T *S, T *E, const T &Elt) {
+ for (; S != E; ++S)
+ new (S) T(Elt);
+ }
+
+ void destroy_range(T *S, T *E) {
+ while (S != E) {
+ --E;
+ E->~T();
+ }
+ }
+};
+
+// Define this out-of-line to dissuade the C++ compiler from inlining it.
+template <typename T>
+void SmallVectorImpl<T>::grow(unsigned MinSize) {
+ unsigned CurCapacity = unsigned(Capacity-Begin);
+ unsigned CurSize = unsigned(size());
+ unsigned NewCapacity = 2*CurCapacity;
+ if (NewCapacity < MinSize)
+ NewCapacity = MinSize;
+ T *NewElts = reinterpret_cast<T*>(new char[NewCapacity*sizeof(T)]);
+
+ // Copy the elements over.
+ std::uninitialized_copy(Begin, End, NewElts);
+
+ // Destroy the original elements.
+ destroy_range(Begin, End);
+
+ // If this wasn't grown from the inline copy, deallocate the old space.
+ if (!isSmall())
+ delete[] (char*)Begin;
+
+ Begin = NewElts;
+ End = NewElts+CurSize;
+ Capacity = Begin+NewCapacity;
+}
+
+template <typename T>
+void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
+ if (this == &RHS) return;
+
+ // We can only avoid copying elements if neither vector is small.
+ if (!isSmall() && !RHS.isSmall()) {
+ std::swap(Begin, RHS.Begin);
+ std::swap(End, RHS.End);
+ std::swap(Capacity, RHS.Capacity);
+ return;
+ }
+ if (Begin+RHS.size() > Capacity)
+ grow(RHS.size());
+ if (RHS.begin()+size() > RHS.Capacity)
+ RHS.grow(size());
+
+ // Swap the shared elements.
+ unsigned NumShared = size();
+ if (NumShared > RHS.size()) NumShared = RHS.size();
+ for (unsigned i = 0; i != NumShared; ++i)
+ std::swap(Begin[i], RHS[i]);
+
+ // Copy over the extra elts.
+ if (size() > RHS.size()) {
+ unsigned EltDiff = size() - RHS.size();
+ std::uninitialized_copy(Begin+NumShared, End, RHS.End);
+ RHS.End += EltDiff;
+ destroy_range(Begin+NumShared, End);
+ End = Begin+NumShared;
+ } else if (RHS.size() > size()) {
+ unsigned EltDiff = RHS.size() - size();
+ std::uninitialized_copy(RHS.Begin+NumShared, RHS.End, End);
+ End += EltDiff;
+ destroy_range(RHS.Begin+NumShared, RHS.End);
+ RHS.End = RHS.Begin+NumShared;
+ }
+}
+
+template <typename T>
+const SmallVectorImpl<T> &
+SmallVectorImpl<T>::operator=(const SmallVectorImpl<T> &RHS) {
+ // Avoid self-assignment.
+ if (this == &RHS) return *this;
+
+ // If we already have sufficient space, assign the common elements, then
+ // destroy any excess.
+ unsigned RHSSize = unsigned(RHS.size());
+ unsigned CurSize = unsigned(size());
+ if (CurSize >= RHSSize) {
+ // Assign common elements.
+ iterator NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);