+// Define this out-of-line to dissuade the C++ compiler from inlining it.
+template <typename T>
+void SmallVectorImpl<T>::grow(size_t MinSize) {
+ size_t CurCapacity = Capacity-Begin;
+ size_t CurSize = size();
+ size_t NewCapacity = 2*CurCapacity;
+ if (NewCapacity < MinSize)
+ NewCapacity = MinSize;
+ T *NewElts = static_cast<T*>(operator new(NewCapacity*sizeof(T)));
+
+ // Copy the elements over.
+ if (is_class<T>::value)
+ std::uninitialized_copy(Begin, End, NewElts);
+ else
+ // Use memcpy for PODs (std::uninitialized_copy optimizes to memmove).
+ memcpy(NewElts, Begin, CurSize * sizeof(T));
+
+ // Destroy the original elements.
+ destroy_range(Begin, End);
+
+ // If this wasn't grown from the inline copy, deallocate the old space.
+ if (!isSmall())
+ operator delete(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.
+ size_t NumShared = size();
+ if (NumShared > RHS.size()) NumShared = RHS.size();
+ for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i)
+ std::swap(Begin[i], RHS[i]);
+
+ // Copy over the extra elts.
+ if (size() > RHS.size()) {
+ size_t 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()) {
+ size_t 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;
+ if (RHSSize)
+ NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin);
+ else
+ NewEnd = Begin;
+
+ // Destroy excess elements.
+ destroy_range(NewEnd, End);
+
+ // Trim.
+ End = NewEnd;
+ return *this;
+ }
+
+ // If we have to grow to have enough elements, destroy the current elements.
+ // This allows us to avoid copying them during the grow.
+ if (unsigned(Capacity-Begin) < RHSSize) {
+ // Destroy current elements.
+ destroy_range(Begin, End);
+ End = Begin;
+ CurSize = 0;
+ grow(RHSSize);
+ } else if (CurSize) {
+ // Otherwise, use assignment for the already-constructed elements.
+ std::copy(RHS.Begin, RHS.Begin+CurSize, Begin);
+ }
+
+ // Copy construct the new elements in place.
+ std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize);
+
+ // Set end.
+ End = Begin+RHSSize;
+ return *this;
+}
+