2003-07-05 Gawain Bolton <gp.bolton@computer.org>

	* include/bits/stl_list.h: Performance and memory usage
	improvements.
	* include/bits/list.tcc: Likewise.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@68987 138bc75d-0d04-0410-961f-82ee72b054a4

3 files changed, 62 insertions, 26 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index c55d7840101..7d1d6262861 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,9 @@
+2003-07-05  Gawain Bolton  <gp.bolton@computer.org>
+
+	* include/bits/stl_list.h: Performance and memory usage
+	improvements.
+	* include/bits/list.tcc: Likewise.
+
 2003-07-05  Paolo Carlini  <pcarlini@unitus.it>
 
 	* include/std/std_complex.h: Fully qualify standard
diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index 428dc90e2e1..2afde96995a 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -69,19 +69,52 @@ namespace std
     __clear()
     {
       typedef _List_node<_Tp>  _Node;
-      _Node* __cur = static_cast<_Node*>(this->_M_node->_M_next);
-      while (__cur != this->_M_node)
+      _Node* __cur = static_cast<_Node*>(this->_M_node._M_next);
+      while (__cur != &this->_M_node)
       {
         _Node* __tmp = __cur;
         __cur = static_cast<_Node*>(__cur->_M_next);
         std::_Destroy(&__tmp->_M_data);
         _M_put_node(__tmp);
       }
-      this->_M_node->_M_next = this->_M_node;
-      this->_M_node->_M_prev = this->_M_node;
+      this->_M_node._M_next = &this->_M_node;
+      this->_M_node._M_prev = &this->_M_node;
     }
   
   template<typename _Tp, typename _Alloc>
+    void list<_Tp, _Alloc>::
+    swap(list<_Tp, _Alloc>& __x)
+    {
+      if ( this->_M_node._M_next == &this->_M_node )
+      {
+        if ( __x._M_node._M_next != &__x._M_node )
+        {
+          this->_M_node._M_next = __x._M_node._M_next;
+          this->_M_node._M_prev = __x._M_node._M_prev;
+          
+          this->_M_node._M_next->_M_prev = this->_M_node._M_prev->_M_next = &this->_M_node;
+          __x._M_node._M_next = __x._M_node._M_prev = &__x._M_node;
+        }
+      }
+      else if ( __x._M_node._M_next == &__x._M_node )
+      {
+        __x._M_node._M_next = this->_M_node._M_next;
+        __x._M_node._M_prev = this->_M_node._M_prev;
+        
+        __x._M_node._M_next->_M_prev = __x._M_node._M_prev->_M_next = &__x._M_node;
+        this->_M_node._M_next = this->_M_node._M_prev = &this->_M_node;
+      }
+      else
+      {
+        std::swap(this->_M_node._M_next,__x._M_node._M_next);
+        std::swap(this->_M_node._M_prev,__x._M_node._M_prev);
+      
+        this->_M_node._M_next->_M_prev = this->_M_node._M_prev->_M_next = &this->_M_node;
+        __x._M_node._M_next->_M_prev = __x._M_node._M_prev->_M_next = &__x._M_node;
+      } 
+    }
+ 
+  template<typename _Tp, typename _Alloc>
     typename list<_Tp,_Alloc>::iterator
     list<_Tp,_Alloc>::
     insert(iterator __position, const value_type& __x)
@@ -250,8 +283,8 @@ namespace std
     sort()
     {
       // Do nothing if the list has length 0 or 1.
-      if (this->_M_node->_M_next != this->_M_node 
-	  && this->_M_node->_M_next->_M_next != this->_M_node)
+      if (this->_M_node._M_next != &this->_M_node 
+	  && this->_M_node._M_next->_M_next != &this->_M_node)
       {
         list __carry;
         list __counter[64];
@@ -341,8 +374,8 @@ namespace std
     sort(_StrictWeakOrdering __comp)
     {
       // Do nothing if the list has length 0 or 1.
-      if (this->_M_node->_M_next != this->_M_node && 
-	  this->_M_node->_M_next->_M_next != this->_M_node)
+      if (this->_M_node._M_next != &this->_M_node && 
+	  this->_M_node._M_next->_M_next != &this->_M_node)
       {
         list __carry;
         list __counter[64];
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index 95fd78e07ea..6f5579e3770 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -247,7 +247,7 @@ namespace std
     typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
              _M_node_allocator;
   
-    _List_node<_Tp>* _M_node;
+    _List_node_base _M_node;
   };
   
   /// @if maint Specialization for instanceless allocators.  @endif
@@ -278,7 +278,7 @@ namespace std
     _M_put_node(_List_node<_Tp>* __p)
     { _Alloc_type::deallocate(__p, 1); }
   
-    _List_node<_Tp>* _M_node;
+    _List_node_base _M_node;
   };
   
   
@@ -301,16 +301,14 @@ namespace std
     _List_base(const allocator_type& __a)
     : _Base(__a)
     {
-      this->_M_node = _M_get_node();
-      this->_M_node->_M_next = this->_M_node;
-      this->_M_node->_M_prev = this->_M_node;
+      this->_M_node._M_next = &this->_M_node;
+      this->_M_node._M_prev = &this->_M_node;
     }
   
     // This is what actually destroys the list.
     ~_List_base()
     {
       __clear();
-      _M_put_node(this->_M_node);
     }
   
     void
@@ -376,8 +374,8 @@ namespace std
     typedef const value_type*                             const_pointer;
     typedef _List_iterator<_Tp,_Tp&,_Tp*>                 iterator;
     typedef _List_iterator<_Tp,const _Tp&,const _Tp*>     const_iterator;
-    typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
-    typedef std::reverse_iterator<iterator>                 reverse_iterator;
+    typedef std::reverse_iterator<const_iterator>         const_reverse_iterator;
+    typedef std::reverse_iterator<iterator>               reverse_iterator;
     typedef value_type&                                   reference;
     typedef const value_type&                             const_reference;
     typedef size_t                                        size_type;
@@ -506,11 +504,11 @@ namespace std
       { this->insert(begin(), __first, __last); }
   
     /**
-     *  The dtor only erases the elements, and note that if the elements
+     *  No explicit dtor needed as the _Base dtor takes care of things.
+     *  The _Base dtor only erases the elements, and note that if the elements
      *  themselves are pointers, the pointed-to memory is not touched in any
      *  way.  Managing the pointer is the user's responsibilty.
     */
-    ~list() { }
   
     /**
      *  @brief  %List assignment operator.
@@ -566,28 +564,28 @@ namespace std
      *  %list.  Iteration is done in ordinary element order.
     */
     iterator
-    begin() { return static_cast<_Node*>(this->_M_node->_M_next); }
+    begin() { return static_cast<_Node*>(this->_M_node._M_next); }
   
     /**
      *  Returns a read-only (constant) iterator that points to the first element
      *  in the %list.  Iteration is done in ordinary element order.
     */
     const_iterator
-    begin() const { return static_cast<_Node*>(this->_M_node->_M_next); }
+    begin() const { return static_cast<_Node*>(this->_M_node._M_next); }
   
     /**
      *  Returns a read/write iterator that points one past the last element in
      *  the %list.  Iteration is done in ordinary element order.
     */
     iterator
-    end() { return this->_M_node; }
+    end() { return static_cast<_Node*>(&this->_M_node); }
   
     /**
      *  Returns a read-only (constant) iterator that points one past the last
      *  element in the %list.  Iteration is done in ordinary element order.
     */
     const_iterator
-    end() const { return this->_M_node; }
+    end() const { return const_cast<_Node *>(static_cast<const _Node*>(&this->_M_node)); }
   
     /**
      *  Returns a read/write reverse iterator that points to the last element in
@@ -625,7 +623,7 @@ namespace std
      *  Returns true if the %list is empty.  (Thus begin() would equal end().)
     */
     bool
-    empty() const { return this->_M_node->_M_next == this->_M_node; }
+    empty() const { return this->_M_node._M_next == &this->_M_node; }
   
     /**  Returns the number of elements in the %list.  */
     size_type
@@ -848,12 +846,11 @@ namespace std
      *  @param  x  A %list of the same element and allocator types.
      *
      *  This exchanges the elements between two lists in constant time.
-     *  (It is only swapping a single pointer, so it should be quite fast.)
      *  Note that the global std::swap() function is specialized such that
      *  std::swap(l1,l2) will feed to this function.
     */
     void
-    swap(list& __x) { std::swap(this->_M_node, __x._M_node); }
+    swap(list& __x);
   
     /**
      *  Erases all the elements.  Note that this function only erases the
@@ -940,7 +937,7 @@ namespace std
      *  @doctodo
     */
     void
-    reverse() { __List_base_reverse(this->_M_node); }
+    reverse() { __List_base_reverse(&this->_M_node); }
   
     /**
      *  @doctodo