This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Updated patch for std::list: Performance and memory usage improvements.


Once again this is an updated patch (see attached), this time for std::list. The original patch was posted a while back:

http://gcc.gnu.org/ml/libstdc++/2003-02/msg00179.html

Here's the suggested change log entry:

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

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

Cheers,


Gawain


--
Gawain Bolton
Coignieres, France
PGP Info: Key server: http://wwwkeys.pgp.net
         Key id: 6EBEDEA6
         Fingerprint: 65C0 0030 21D1 7A01 546A  E7DB D60F 47E0 6EBE DEA6

Index: list.tcc
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/list.tcc,v
retrieving revision 1.6
diff -u -r1.6 list.tcc
--- list.tcc	5 Jul 2003 04:05:34 -0000	1.6
+++ list.tcc	5 Jul 2003 21:15:08 -0000
@@ -69,19 +69,52 @@
     __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 @@
     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 @@
     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];
Index: stl_list.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_list.h,v
retrieving revision 1.27
diff -u -r1.27 stl_list.h
--- stl_list.h	5 Jul 2003 04:05:35 -0000	1.27
+++ stl_list.h	5 Jul 2003 21:15:10 -0000
@@ -247,7 +247,7 @@
     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 @@
     _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 @@
     _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 @@
     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 @@
       { 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 @@
      *  %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 @@
      *  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 @@
      *  @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 @@
      *  @doctodo
     */
     void
-    reverse() { __List_base_reverse(this->_M_node); }
+    reverse() { __List_base_reverse(&this->_M_node); }
   
     /**
      *  @doctodo

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]