From e6e55d79592fa0926175d6b17e3db89b298ada4e Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Wed, 16 Dec 2009 08:05:48 +0000
Subject: [PATCH] sink most of the meat in smallvector back from
 SmallVectorTemplateCommon down into SmallVectorImpl.  This requires sprinking
 a ton of this->'s in, but gives us a place to factor.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91522 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/SmallVector.h | 412 +++++++++++++++++----------------
 1 file changed, 210 insertions(+), 202 deletions(-)

diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h
index 4853bd14226..b166ab49323 100644
--- a/include/llvm/ADT/SmallVector.h
+++ b/include/llvm/ADT/SmallVector.h
@@ -86,19 +86,11 @@ public:
 
 template <typename T>
 class SmallVectorTemplateCommon : public SmallVectorBase {
+protected:
   void setEnd(T *P) { this->EndX = P; }
 public:
   SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(Size) {}
   
-  ~SmallVectorTemplateCommon() {
-    // Destroy the constructed elements in the vector.
-    destroy_range(begin(), end());
-    
-    // If this wasn't grown from the inline copy, deallocate the old space.
-    if (!this->isSmall())
-      operator delete(begin());
-  }
-  
   typedef size_t size_type;
   typedef ptrdiff_t difference_type;
   typedef T value_type;
@@ -118,7 +110,7 @@ public:
   const_iterator begin() const { return (const_iterator)this->BeginX; }
   iterator end() { return (iterator)this->EndX; }
   const_iterator end() const { return (const_iterator)this->EndX; }
-private:
+protected:
   iterator capacity_ptr() { return (iterator)this->CapacityX; }
   const_iterator capacity_ptr() const { return (const_iterator)this->CapacityX;}
 public:
@@ -163,253 +155,297 @@ public:
   const_reference back() const {
     return end()[-1];
   }
+};
+  
+  
+template <typename T, bool isPodLike>
+class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
+public:
+  SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
 
-  void push_back(const_reference Elt) {
-    if (this->EndX < this->CapacityX) {
-  Retry:
-      new (end()) T(Elt);
-      setEnd(end()+1);
-      return;
-    }
-    grow();
-    goto Retry;
-  }
+};
 
-  void pop_back() {
-    setEnd(end()-1);
-    end()->~T();
+template <typename T>
+class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
+public:
+  SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
+  
+};
+  
+  
+/// SmallVectorImpl - This class consists of common code factored out of the
+/// SmallVector class to reduce code duplication based on the SmallVector 'N'
+/// template parameter.
+template <typename T>
+class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
+public:
+  typedef typename SmallVectorTemplateBase<T, isPodLike<T>::value >::iterator
+    iterator;
+  typedef typename SmallVectorTemplateBase<T, isPodLike<T>::value >::size_type
+    size_type;
+  
+  // Default ctor - Initialize to empty.
+  explicit SmallVectorImpl(unsigned N)
+    : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
   }
-
-  T pop_back_val() {
-    T Result = back();
-    pop_back();
-    return Result;
+  
+  ~SmallVectorImpl() {
+    // Destroy the constructed elements in the vector.
+    destroy_range(this->begin(), this->end());
+    
+    // If this wasn't grown from the inline copy, deallocate the old space.
+    if (!this->isSmall())
+      operator delete(this->begin());
   }
-
+  
+  
   void clear() {
-    destroy_range(begin(), end());
+    destroy_range(this->begin(), this->end());
     this->EndX = this->BeginX;
   }
 
   void resize(unsigned N) {
-    if (N < size()) {
-      destroy_range(begin()+N, end());
-      setEnd(begin()+N);
-    } else if (N > size()) {
-      if (capacity() < N)
+    if (N < this->size()) {
+      this->destroy_range(this->begin()+N, this->end());
+      this->setEnd(this->begin()+N);
+    } else if (N > this->size()) {
+      if (this->capacity() < N)
         grow(N);
-      construct_range(end(), begin()+N, T());
-      setEnd(begin()+N);
+      this->construct_range(this->end(), this->begin()+N, T());
+      this->setEnd(this->begin()+N);
     }
   }
 
   void resize(unsigned N, const T &NV) {
-    if (N < size()) {
-      destroy_range(begin()+N, end());
-      setEnd(begin()+N);
-    } else if (N > size()) {
-      if (capacity() < N)
+    if (N < this->size()) {
+      destroy_range(this->begin()+N, this->end());
+      setEnd(this->begin()+N);
+    } else if (N > this->size()) {
+      if (this->capacity() < N)
         grow(N);
-      construct_range(end(), begin()+N, NV);
-      setEnd(begin()+N);
+      construct_range(this->end(), this->begin()+N, NV);
+      setEnd(this->begin()+N);
     }
   }
 
   void reserve(unsigned N) {
-    if (capacity() < N)
+    if (this->capacity() < N)
       grow(N);
   }
-
-  void swap(SmallVectorTemplateCommon &RHS);
-
+  
+  void push_back(const T &Elt) {
+    if (this->EndX < this->CapacityX) {
+    Retry:
+      new (this->end()) T(Elt);
+      setEnd(this->end()+1);
+      return;
+    }
+    this->grow();
+    goto Retry;
+  }
+  
+  void pop_back() {
+    setEnd(this->end()-1);
+    this->end()->~T();
+  }
+  
+  T pop_back_val() {
+    T Result = this->back();
+    pop_back();
+    return Result;
+  }
+  
+  
+  void swap(SmallVectorImpl &RHS);
+  
   /// append - Add the specified range to the end of the SmallVector.
   ///
   template<typename in_iter>
   void append(in_iter in_start, in_iter in_end) {
     size_type NumInputs = std::distance(in_start, in_end);
     // Grow allocated space if needed.
-    if (NumInputs > size_type(capacity_ptr()-end()))
-      grow(size()+NumInputs);
-
+    if (NumInputs > size_type(this->capacity_ptr()-this->end()))
+      grow(this->size()+NumInputs);
+    
     // Copy the new elements over.
     // TODO: NEED To compile time dispatch on whether in_iter is a random access
     // iterator to use the fast uninitialized_copy.
-    std::uninitialized_copy(in_start, in_end, end());
-    setEnd(end() + NumInputs);
+    std::uninitialized_copy(in_start, in_end, this->end());
+    setEnd(this->end() + NumInputs);
   }
-
+  
   /// append - Add the specified range to the end of the SmallVector.
   ///
   void append(size_type NumInputs, const T &Elt) {
     // Grow allocated space if needed.
-    if (NumInputs > size_type(capacity_ptr()-end()))
-      grow(size()+NumInputs);
-
+    if (NumInputs > size_type(this->capacity_ptr()-this->end()))
+      grow(this->size()+NumInputs);
+    
     // Copy the new elements over.
-    std::uninitialized_fill_n(end(), NumInputs, Elt);
-    setEnd(end() + NumInputs);
+    std::uninitialized_fill_n(this->end(), NumInputs, Elt);
+    setEnd(this->end() + NumInputs);
   }
-
+  
   void assign(unsigned NumElts, const T &Elt) {
     clear();
-    if (capacity() < NumElts)
+    if (this->capacity() < NumElts)
       grow(NumElts);
-    setEnd(begin()+NumElts);
-    construct_range(begin(), end(), Elt);
+    setEnd(this->begin()+NumElts);
+    construct_range(this->begin(), this->end(), Elt);
   }
-
+  
   iterator erase(iterator I) {
     iterator N = I;
     // Shift all elts down one.
-    std::copy(I+1, end(), I);
+    std::copy(I+1, this->end(), I);
     // Drop the last elt.
     pop_back();
     return(N);
   }
-
+  
   iterator erase(iterator S, iterator E) {
     iterator N = S;
     // Shift all elts down.
-    iterator I = std::copy(E, end(), S);
+    iterator I = std::copy(E, this->end(), S);
     // Drop the last elts.
-    destroy_range(I, end());
+    destroy_range(I, this->end());
     setEnd(I);
     return(N);
   }
-
+  
   iterator insert(iterator I, const T &Elt) {
-    if (I == end()) {  // Important special case for empty vector.
+    if (I == this->end()) {  // Important special case for empty vector.
       push_back(Elt);
-      return end()-1;
+      return this->end()-1;
     }
-
+    
     if (this->EndX < this->CapacityX) {
-  Retry:
-      new (end()) T(back());
-      setEnd(end()+1);
+    Retry:
+      new (this->end()) T(this->back());
+      this->setEnd(this->end()+1);
       // Push everything else over.
-      std::copy_backward(I, end()-1, end());
+      std::copy_backward(I, this->end()-1, this->end());
       *I = Elt;
       return I;
     }
-    size_t EltNo = I-begin();
-    grow();
-    I = begin()+EltNo;
+    size_t EltNo = I-this->begin();
+    this->grow();
+    I = this->begin()+EltNo;
     goto Retry;
   }
-
+  
   iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
-    if (I == end()) {  // Important special case for empty vector.
+    if (I == this->end()) {  // Important special case for empty vector.
       append(NumToInsert, Elt);
-      return end()-1;
+      return this->end()-1;
     }
-
+    
     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
-    size_t InsertElt = I-begin();
-
+    size_t InsertElt = I - this->begin();
+    
     // Ensure there is enough space.
-    reserve(static_cast<unsigned>(size() + NumToInsert));
-
+    reserve(static_cast<unsigned>(this->size() + NumToInsert));
+    
     // Uninvalidate the iterator.
-    I = begin()+InsertElt;
-
+    I = this->begin()+InsertElt;
+    
     // If there are more elements between the insertion point and the end of the
     // range than there are being inserted, we can use a simple approach to
     // insertion.  Since we already reserved space, we know that this won't
     // reallocate the vector.
-    if (size_t(end()-I) >= NumToInsert) {
-      T *OldEnd = end();
-      append(end()-NumToInsert, end());
-
+    if (size_t(this->end()-I) >= NumToInsert) {
+      T *OldEnd = this->end();
+      append(this->end()-NumToInsert, this->end());
+      
       // Copy the existing elements that get replaced.
       std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
-
+      
       std::fill_n(I, NumToInsert, Elt);
       return I;
     }
-
+    
     // Otherwise, we're inserting more elements than exist already, and we're
     // not inserting at the end.
-
+    
     // Copy over the elements that we're about to overwrite.
-    T *OldEnd = end();
-    setEnd(end() + NumToInsert);
+    T *OldEnd = this->end();
+    setEnd(this->end() + NumToInsert);
     size_t NumOverwritten = OldEnd-I;
-    uninitialized_copy(I, OldEnd, end()-NumOverwritten);
-
+    uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
+    
     // Replace the overwritten part.
     std::fill_n(I, NumOverwritten, Elt);
-
+    
     // Insert the non-overwritten middle part.
     std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
     return I;
   }
-
+  
   template<typename ItTy>
   iterator insert(iterator I, ItTy From, ItTy To) {
-    if (I == end()) {  // Important special case for empty vector.
+    if (I == this->end()) {  // Important special case for empty vector.
       append(From, To);
-      return end()-1;
+      return this->end()-1;
     }
-
+    
     size_t NumToInsert = std::distance(From, To);
     // Convert iterator to elt# to avoid invalidating iterator when we reserve()
-    size_t InsertElt = I-begin();
-
+    size_t InsertElt = I - this->begin();
+    
     // Ensure there is enough space.
-    reserve(static_cast<unsigned>(size() + NumToInsert));
-
+    reserve(static_cast<unsigned>(this->size() + NumToInsert));
+    
     // Uninvalidate the iterator.
-    I = begin()+InsertElt;
-
+    I = this->begin()+InsertElt;
+    
     // If there are more elements between the insertion point and the end of the
     // range than there are being inserted, we can use a simple approach to
     // insertion.  Since we already reserved space, we know that this won't
     // reallocate the vector.
-    if (size_t(end()-I) >= NumToInsert) {
-      T *OldEnd = end();
-      append(end()-NumToInsert, end());
-
+    if (size_t(this->end()-I) >= NumToInsert) {
+      T *OldEnd = this->end();
+      append(this->end()-NumToInsert, this->end());
+      
       // Copy the existing elements that get replaced.
       std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
-
+      
       std::copy(From, To, I);
       return I;
     }
-
+    
     // Otherwise, we're inserting more elements than exist already, and we're
     // not inserting at the end.
-
+    
     // Copy over the elements that we're about to overwrite.
-    T *OldEnd = end();
-    setEnd(end() + NumToInsert);
+    T *OldEnd = this->end();
+    setEnd(this->end() + NumToInsert);
     size_t NumOverwritten = OldEnd-I;
-    uninitialized_copy(I, OldEnd, end()-NumOverwritten);
-
+    uninitialized_copy(I, OldEnd, this->end()-NumOverwritten);
+    
     // Replace the overwritten part.
     std::copy(From, From+NumOverwritten, I);
-
+    
     // Insert the non-overwritten middle part.
     uninitialized_copy(From+NumOverwritten, To, OldEnd);
     return I;
   }
-
-  const SmallVectorTemplateCommon
-    &operator=(const SmallVectorTemplateCommon &RHS);
-
-  bool operator==(const SmallVectorTemplateCommon &RHS) const {
-    if (size() != RHS.size()) return false;
-    return std::equal(begin(), end(), RHS.begin());
+  
+  const SmallVectorImpl
+  &operator=(const SmallVectorImpl &RHS);
+  
+  bool operator==(const SmallVectorImpl &RHS) const {
+    if (this->size() != RHS.size()) return false;
+    return std::equal(this->begin(), this->end(), RHS.begin());
   }
-  bool operator!=(const SmallVectorTemplateCommon &RHS) const {
+  bool operator!=(const SmallVectorImpl &RHS) const {
     return !(*this == RHS);
   }
-
-  bool operator<(const SmallVectorTemplateCommon &RHS) const {
-    return std::lexicographical_compare(begin(), end(),
+  
+  bool operator<(const SmallVectorImpl &RHS) const {
+    return std::lexicographical_compare(this->begin(), this->end(),
                                         RHS.begin(), RHS.end());
   }
-
+  
   /// set_size - Set the array size to \arg N, which the current array must have
   /// enough capacity for.
   ///
@@ -420,20 +456,20 @@ public:
   /// update the size later. This avoids the cost of value initializing elements
   /// which will only be overwritten.
   void set_size(unsigned N) {
-    assert(N <= capacity());
-    setEnd(begin() + N);
+    assert(N <= this->capacity());
+    setEnd(this->begin() + N);
   }
-
+  
 private:
   /// grow - double the size of the allocated memory, guaranteeing space for at
   /// least one more element or MinSize if specified.
-  void grow(size_type MinSize = 0);
-
+  void grow(size_t MinSize = 0);
+  
   static void construct_range(T *S, T *E, const T &Elt) {
     for (; S != E; ++S)
       new (S) T(Elt);
   }
-
+  
   static void destroy_range(T *S, T *E) {
     // No need to do a destroy loop for POD's.
     if (isPodLike<T>::value) return;
@@ -459,31 +495,31 @@ private:
 
 // Define this out-of-line to dissuade the C++ compiler from inlining it.
 template <typename T>
-void SmallVectorTemplateCommon<T>::grow(size_t MinSize) {
-  size_t CurCapacity = capacity();
-  size_t CurSize = size();
+void SmallVectorImpl<T>::grow(size_t MinSize) {
+  size_t CurCapacity = this->capacity();
+  size_t CurSize = this->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.
-  uninitialized_copy(begin(), end(), NewElts);
+  uninitialized_copy(this->begin(), this->end(), NewElts);
 
   // Destroy the original elements.
-  destroy_range(begin(), end());
+  destroy_range(this->begin(), this->end());
 
   // If this wasn't grown from the inline copy, deallocate the old space.
   if (!this->isSmall())
-    operator delete(begin());
+    operator delete(this->begin());
 
   setEnd(NewElts+CurSize);
   this->BeginX = NewElts;
-  this->CapacityX = begin()+NewCapacity;
+  this->CapacityX = this->begin()+NewCapacity;
 }
 
 template <typename T>
-void SmallVectorTemplateCommon<T>::swap(SmallVectorTemplateCommon<T> &RHS) {
+void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
   if (this == &RHS) return;
 
   // We can only avoid copying elements if neither vector is small.
@@ -493,54 +529,53 @@ void SmallVectorTemplateCommon<T>::swap(SmallVectorTemplateCommon<T> &RHS) {
     std::swap(this->CapacityX, RHS.CapacityX);
     return;
   }
-  if (RHS.size() > capacity())
+  if (RHS.size() > this->capacity())
     grow(RHS.size());
-  if (size() > RHS.capacity())
-    RHS.grow(size());
+  if (this->size() > RHS.capacity())
+    RHS.grow(this->size());
 
   // Swap the shared elements.
-  size_t NumShared = size();
+  size_t NumShared = this->size();
   if (NumShared > RHS.size()) NumShared = RHS.size();
   for (unsigned i = 0; i != static_cast<unsigned>(NumShared); ++i)
     std::swap((*this)[i], RHS[i]);
 
   // Copy over the extra elts.
-  if (size() > RHS.size()) {
-    size_t EltDiff = size() - RHS.size();
-    uninitialized_copy(begin()+NumShared, end(), RHS.end());
+  if (this->size() > RHS.size()) {
+    size_t EltDiff = this->size() - RHS.size();
+    uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
     RHS.setEnd(RHS.end()+EltDiff);
-    destroy_range(begin()+NumShared, end());
-    setEnd(begin()+NumShared);
-  } else if (RHS.size() > size()) {
-    size_t EltDiff = RHS.size() - size();
-    uninitialized_copy(RHS.begin()+NumShared, RHS.end(), end());
-    setEnd(end() + EltDiff);
+    destroy_range(this->begin()+NumShared, this->end());
+    setEnd(this->begin()+NumShared);
+  } else if (RHS.size() > this->size()) {
+    size_t EltDiff = RHS.size() - this->size();
+    uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
+    setEnd(this->end() + EltDiff);
     destroy_range(RHS.begin()+NumShared, RHS.end());
     RHS.setEnd(RHS.begin()+NumShared);
   }
 }
 
 template <typename T>
-const SmallVectorTemplateCommon<T> &
-SmallVectorTemplateCommon<T>::
-  operator=(const SmallVectorTemplateCommon<T> &RHS) {
+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.
   size_t RHSSize = RHS.size();
-  size_t CurSize = size();
+  size_t CurSize = this->size();
   if (CurSize >= RHSSize) {
     // Assign common elements.
     iterator NewEnd;
     if (RHSSize)
-      NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, begin());
+      NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
     else
-      NewEnd = begin();
+      NewEnd = this->begin();
 
     // Destroy excess elements.
-    destroy_range(NewEnd, end());
+    destroy_range(NewEnd, this->end());
 
     // Trim.
     setEnd(NewEnd);
@@ -549,52 +584,25 @@ SmallVectorTemplateCommon<T>::
 
   // If we have to grow to have enough elements, destroy the current elements.
   // This allows us to avoid copying them during the grow.
-  if (capacity() < RHSSize) {
+  if (this->capacity() < RHSSize) {
     // Destroy current elements.
-    destroy_range(begin(), end());
-    setEnd(begin());
+    destroy_range(this->begin(), this->end());
+    setEnd(this->begin());
     CurSize = 0;
     grow(RHSSize);
   } else if (CurSize) {
     // Otherwise, use assignment for the already-constructed elements.
-    std::copy(RHS.begin(), RHS.begin()+CurSize, begin());
+    std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
   }
 
   // Copy construct the new elements in place.
-  uninitialized_copy(RHS.begin()+CurSize, RHS.end(), begin()+CurSize);
+  uninitialized_copy(RHS.begin()+CurSize, RHS.end(), this->begin()+CurSize);
 
   // Set end.
-  setEnd(begin()+RHSSize);
+  setEnd(this->begin()+RHSSize);
   return *this;
 }
 
-  
-template <typename T, bool isPodLike>
-class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
-public:
-  SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
-
-};
-
-template <typename T>
-class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
-public:
-  SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
-  
-};
-  
-  
-/// SmallVectorImpl - This class consists of common code factored out of the
-/// SmallVector class to reduce code duplication based on the SmallVector 'N'
-/// template parameter.
-template <typename T>
-class SmallVectorImpl : public SmallVectorTemplateBase<T, isPodLike<T>::value> {
-public:
-  // Default ctor - Initialize to empty.
-  explicit SmallVectorImpl(unsigned N)
-    : SmallVectorTemplateBase<T, isPodLike<T>::value>(N*sizeof(T)) {
-  }
-};
 
 /// 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
-- 
2.34.1