+ 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;
+}
+
+/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized
+/// for the case when the array is small. It contains some number of elements
+/// in-place, which allows it to avoid heap allocation when the actual number of
+/// elements is below that threshold. This allows normal "small" cases to be
+/// fast without losing generality for large inputs.
+///
+/// Note that this does not attempt to be exception safe.
+///
+template <typename T, unsigned N>
+class SmallVector : public SmallVectorImpl<T> {
+ /// InlineElts - These are 'N-1' elements that are stored inline in the body
+ /// of the vector. The extra '1' element is stored in SmallVectorImpl.
+ typedef typename SmallVectorImpl<T>::U U;
+ enum {
+ // MinUs - The number of U's require to cover N T's.
+ MinUs = (static_cast<unsigned int>(sizeof(T))*N +
+ static_cast<unsigned int>(sizeof(U)) - 1) /
+ static_cast<unsigned int>(sizeof(U)),
+
+ // NumInlineEltsElts - The number of elements actually in this array. There
+ // is already one in the parent class, and we have to round up to avoid
+ // having a zero-element array.
+ NumInlineEltsElts = MinUs > 1 ? (MinUs - 1) : 1,
+
+ // NumTsAvailable - The number of T's we actually have space for, which may
+ // be more than N due to rounding.
+ NumTsAvailable = (NumInlineEltsElts+1)*static_cast<unsigned int>(sizeof(U))/
+ static_cast<unsigned int>(sizeof(T))
+ };
+ U InlineElts[NumInlineEltsElts];
+public:
+ SmallVector() : SmallVectorImpl<T>(NumTsAvailable) {
+ }
+
+ explicit SmallVector(unsigned Size, const T &Value = T())
+ : SmallVectorImpl<T>(NumTsAvailable) {
+ this->reserve(Size);
+ while (Size--)
+ this->push_back(Value);
+ }
+
+ template<typename ItTy>
+ SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(NumTsAvailable) {
+ this->append(S, E);
+ }
+
+ SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(NumTsAvailable) {
+ if (!RHS.empty())
+ SmallVectorImpl<T>::operator=(RHS);
+ }
+
+ const SmallVector &operator=(const SmallVector &RHS) {
+ SmallVectorImpl<T>::operator=(RHS);
+ return *this;
+ }
+