[Boost-commit] svn:boost r80575 - in trunk/boost/intrusive: . detail

Subject: [Boost-commit] svn:boost r80575 - in trunk/boost/intrusive: . detail
From: igaztanaga_at_[hidden]
Date: 2012-09-18 12:38:43

Author: igaztanaga
Date: 2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
New Revision: 80575
URL: http://svn.boost.org/trac/boost/changeset/80575

Log:
Applied pass by value to save copy constructors for pointers with non-trivial copy constructor and const node_ptr & to avoid creating temporaries.
Text files modified: 
   trunk/boost/intrusive/circular_slist_algorithms.hpp      |     9 ++++-----                               
   trunk/boost/intrusive/detail/avltree_node.hpp            |    12 ++++++++++++                            
   trunk/boost/intrusive/detail/common_slist_algorithms.hpp |     3 +--                                     
   trunk/boost/intrusive/detail/list_node.hpp               |     6 ++++++                                  
   trunk/boost/intrusive/detail/rbtree_node.hpp             |    24 ++++++++++++++++++++++++                
   trunk/boost/intrusive/detail/slist_node.hpp              |     3 +++                                     
   trunk/boost/intrusive/detail/tree_algorithms.hpp         |    35 +++++++++++++++--------------------     
   trunk/boost/intrusive/detail/tree_node.hpp               |     9 +++++++++                               
   trunk/boost/intrusive/rbtree_algorithms.hpp              |    21 ++++++++++-----------                   
   9 files changed, 84 insertions(+), 38 deletions(-)

Modified: trunk/boost/intrusive/circular_slist_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/circular_slist_algorithms.hpp	(original)
+++ trunk/boost/intrusive/circular_slist_algorithms.hpp	2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
@@ -172,18 +172,17 @@
    static node_ptr get_previous_previous_node(const node_ptr & this_node)
    {  return get_previous_previous_node(this_node, this_node); }
 
-   //! <b>Requires</b>: this_node and prev_prev_init_node must be in the same circular list.
+   //! <b>Requires</b>: this_node and p must be in the same circular list.
    //!
    //! <b>Effects</b>: Returns the previous node of the previous node of this_node in the
-   //!   circular list starting. the search from prev_init_node. The first node checked
-   //!   for equality is NodeTraits::get_next((NodeTraits::get_next(prev_prev_init_node)).
+   //!   circular list starting. the search from p. The first node checked
+   //!   for equality is NodeTraits::get_next((NodeTraits::get_next(p)).
    //!
    //! <b>Complexity</b>: Linear to the number of elements in the circular list.
    //!
    //! <b>Throws</b>: Nothing.
-   static node_ptr get_previous_previous_node(const node_ptr & prev_prev_init_node, const node_ptr & this_node)
+   static node_ptr get_previous_previous_node(node_ptr p, const node_ptr & this_node)
    {
-      node_ptr p = prev_prev_init_node;
       node_ptr p_next = NodeTraits::get_next(p);
       node_ptr p_next_next = NodeTraits::get_next(p_next);
       while (this_node != p_next_next){

Modified: trunk/boost/intrusive/detail/avltree_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/avltree_node.hpp	(original)
+++ trunk/boost/intrusive/detail/avltree_node.hpp	2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
@@ -71,24 +71,36 @@
    static node_ptr get_parent(const const_node_ptr & n)
    {  return n->parent_;  }
 
+   static node_ptr get_parent(const node_ptr & n)
+   {  return n->parent_;  }
+
    static void set_parent(const node_ptr & n, const node_ptr & p)
    {  n->parent_ = p;  }
 
    static node_ptr get_left(const const_node_ptr & n)
    {  return n->left_;  }
 
+   static node_ptr get_left(const node_ptr & n)
+   {  return n->left_;  }
+
    static void set_left(const node_ptr & n, const node_ptr & l)
    {  n->left_ = l;  }
 
    static node_ptr get_right(const const_node_ptr & n)
    {  return n->right_;  }
 
+   static node_ptr get_right(const node_ptr & n)
+   {  return n->right_;  }
+
    static void set_right(const node_ptr & n, const node_ptr & r)
    {  n->right_ = r;  }
 
    static balance get_balance(const const_node_ptr & n)
    {  return n->balance_;  }
 
+   static balance get_balance(const node_ptr & n)
+   {  return n->balance_;  }
+
    static void set_balance(const node_ptr & n, balance b)
    {  n->balance_ = b;  }
 

Modified: trunk/boost/intrusive/detail/common_slist_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/detail/common_slist_algorithms.hpp	(original)
+++ trunk/boost/intrusive/detail/common_slist_algorithms.hpp	2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
@@ -31,9 +31,8 @@
    typedef typename NodeTraits::const_node_ptr  const_node_ptr;
    typedef NodeTraits                           node_traits;
 
-   static node_ptr get_previous_node(const node_ptr & prev_init_node, const node_ptr & this_node)
+   static node_ptr get_previous_node(node_ptr p, const node_ptr & this_node)
    {
-      node_ptr p = prev_init_node;
       for( node_ptr p_next
          ; this_node != (p_next = NodeTraits::get_next(p))
          ; p = p_next){

Modified: trunk/boost/intrusive/detail/list_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/list_node.hpp	(original)
+++ trunk/boost/intrusive/detail/list_node.hpp	2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
@@ -47,12 +47,18 @@
    static node_ptr get_previous(const const_node_ptr & n)
    {  return n->prev_;  }
 
+   static node_ptr get_previous(const node_ptr & n)
+   {  return n->prev_;  }
+
    static void set_previous(const node_ptr & n, const node_ptr & prev)
    {  n->prev_ = prev;  }
 
    static node_ptr get_next(const const_node_ptr & n)
    {  return n->next_;  }
 
+   static node_ptr get_next(const node_ptr & n)
+   {  return n->next_;  }
+
    static void set_next(const node_ptr & n, const node_ptr & next)
    {  n->next_ = next;  }
 };

Modified: trunk/boost/intrusive/detail/rbtree_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/rbtree_node.hpp	(original)
+++ trunk/boost/intrusive/detail/rbtree_node.hpp	2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
@@ -71,24 +71,36 @@
    static node_ptr get_parent(const const_node_ptr & n)
    {  return n->parent_;  }
 
+   static node_ptr get_parent(const node_ptr & n)
+   {  return n->parent_;  }
+
    static void set_parent(const node_ptr & n, const node_ptr & p)
    {  n->parent_ = p;  }
 
    static node_ptr get_left(const const_node_ptr & n)
    {  return n->left_;  }
 
+   static node_ptr get_left(const node_ptr & n)
+   {  return n->left_;  }
+
    static void set_left(const node_ptr & n, const node_ptr & l)
    {  n->left_ = l;  }
 
    static node_ptr get_right(const const_node_ptr & n)
    {  return n->right_;  }
 
+   static node_ptr get_right(const node_ptr & n)
+   {  return n->right_;  }
+
    static void set_right(const node_ptr & n, const node_ptr & r)
    {  n->right_ = r;  }
 
    static color get_color(const const_node_ptr & n)
    {  return n->color_;  }
 
+   static color get_color(const node_ptr & n)
+   {  return n->color_;  }
+
    static void set_color(const node_ptr & n, color c)
    {  n->color_ = c;  }
 
@@ -117,24 +129,36 @@
    static node_ptr get_parent(const const_node_ptr & n)
    {  return ptr_bit::get_pointer(n->parent_);  }
 
+   static node_ptr get_parent(const node_ptr & n)
+   {  return ptr_bit::get_pointer(n->parent_);  }
+
    static void set_parent(const node_ptr & n, const node_ptr & p)
    {  ptr_bit::set_pointer(n->parent_, p);  }
 
    static node_ptr get_left(const const_node_ptr & n)
    {  return n->left_;  }
 
+   static node_ptr get_left(const node_ptr & n)
+   {  return n->left_;  }
+
    static void set_left(const node_ptr & n, const node_ptr & l)
    {  n->left_ = l;  }
 
    static node_ptr get_right(const const_node_ptr & n)
    {  return n->right_;  }
 
+   static node_ptr get_right(const node_ptr & n)
+   {  return n->right_;  }
+
    static void set_right(const node_ptr & n, const node_ptr & r)
    {  n->right_ = r;  }
 
    static color get_color(const const_node_ptr & n)
    {  return (color)ptr_bit::get_bits(n->parent_);  }
 
+   static color get_color(const node_ptr & n)
+   {  return (color)ptr_bit::get_bits(n->parent_);  }
+
    static void set_color(const node_ptr & n, color c)
    {  ptr_bit::set_bits(n->parent_, c != 0);  }
 

Modified: trunk/boost/intrusive/detail/slist_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/slist_node.hpp	(original)
+++ trunk/boost/intrusive/detail/slist_node.hpp	2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
@@ -45,6 +45,9 @@
    static node_ptr get_next(const const_node_ptr & n)
    {  return n->next_;  }
 
+   static node_ptr get_next(const node_ptr & n)
+   {  return n->next_;  }
+
    static void set_next(const node_ptr & n, const node_ptr & next)
    {  n->next_ = next;  }
 };

Modified: trunk/boost/intrusive/detail/tree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/detail/tree_algorithms.hpp	(original)
+++ trunk/boost/intrusive/detail/tree_algorithms.hpp	2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
@@ -485,15 +485,14 @@
    //! <b>Complexity</b>: Logarithmic to the size of the subtree.
    //!
    //! <b>Throws</b>: Nothing.
-   static node_ptr minimum (const node_ptr & node)
+   static node_ptr minimum (node_ptr node)
    {
-      node_ptr p(node);
-      for(node_ptr p_left = NodeTraits::get_left(p)
+      for(node_ptr p_left = NodeTraits::get_left(node)
          ;p_left
-         ;p_left = NodeTraits::get_left(p)){
-         p = p_left;
+         ;p_left = NodeTraits::get_left(node)){
+         node = p_left;
       }
-      return p;
+      return node;
    }
 
    //! <b>Requires</b>: 'node' is a node of a tree but not the header.
@@ -503,15 +502,14 @@
    //! <b>Complexity</b>: Logarithmic to the size of the subtree.
    //!
    //! <b>Throws</b>: Nothing.
-   static node_ptr maximum(const node_ptr & node)
+   static node_ptr maximum(node_ptr node)
    {
-      node_ptr p(node);
-      for(node_ptr p_right = NodeTraits::get_right(p)
+      for(node_ptr p_right = NodeTraits::get_right(node)
          ;p_right
-         ;p_right = NodeTraits::get_right(p)){
-         p = p_right;
+         ;p_right = NodeTraits::get_right(node)){
+         node = p_right;
       }
-      return p;
+      return node;
    }
 
    //! <b>Requires</b>: 'node' must not be part of any tree.
@@ -1171,14 +1169,13 @@
    //! <b>Complexity</b>: Logarithmic to the number of nodes in the tree.
    //!
    //! <b>Throws</b>: Nothing.
-   static std::size_t depth(const const_node_ptr & node)
+   static std::size_t depth(const_node_ptr node)
    {
-      const_node_ptr p(node);
       std::size_t depth = 0;
       node_ptr p_parent;
-      while(p != NodeTraits::get_parent(p_parent = NodeTraits::get_parent(p))){
+      while(node != NodeTraits::get_parent(p_parent = NodeTraits::get_parent(node))){
          ++depth;
-         p = p_parent;
+         node = p_parent;
       }
       return depth;
    }
@@ -1295,12 +1292,10 @@
    }
 
    template<class Disposer>
-   static void dispose_subtree(const node_ptr & node, Disposer disposer)
+   static void dispose_subtree(node_ptr x, Disposer disposer)
    {
-      node_ptr save;
-      node_ptr x(node);
       while (x){
-         save = NodeTraits::get_left(x);
+         node_ptr save(NodeTraits::get_left(x));
          if (save) {
             // Right rotation
             NodeTraits::set_left(x, NodeTraits::get_right(save));

Modified: trunk/boost/intrusive/detail/tree_node.hpp
==============================================================================
--- trunk/boost/intrusive/detail/tree_node.hpp	(original)
+++ trunk/boost/intrusive/detail/tree_node.hpp	2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
@@ -44,18 +44,27 @@
    static node_ptr get_parent(const const_node_ptr & n)
    {  return n->parent_;  }
 
+   static node_ptr get_parent(const node_ptr & n)
+   {  return n->parent_;  }
+
    static void set_parent(const node_ptr & n, const node_ptr & p)
    {  n->parent_ = p;  }
 
    static node_ptr get_left(const const_node_ptr & n)
    {  return n->left_;  }
 
+   static node_ptr get_left(const node_ptr & n)
+   {  return n->left_;  }
+
    static void set_left(const node_ptr & n, const node_ptr & l)
    {  n->left_ = l;  }
 
    static node_ptr get_right(const const_node_ptr & n)
    {  return n->right_;  }
 
+   static node_ptr get_right(const node_ptr & n)
+   {  return n->right_;  }
+
    static void set_right(const node_ptr & n, const node_ptr & r)
    {  n->right_ = r;  }
 };

Modified: trunk/boost/intrusive/rbtree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/rbtree_algorithms.hpp	(original)
+++ trunk/boost/intrusive/rbtree_algorithms.hpp	2012-09-18 12:38:42 EDT (Tue, 18 Sep 2012)
@@ -805,26 +805,26 @@
       //       NodeTraits::get_parent(NodeTraits::get_parent(p)) == p;
    }
 
-   static void rebalance_after_erasure(const node_ptr & header, const node_ptr &xnode, const node_ptr &xnode_parent)
+   static void rebalance_after_erasure(const node_ptr & header, node_ptr x, node_ptr x_parent)
    {
-      node_ptr x(xnode), x_parent(xnode_parent);
-      while(x != NodeTraits::get_parent(header) && (x == node_ptr() || NodeTraits::get_color(x) == NodeTraits::black())){
+      while(x != NodeTraits::get_parent(header) && (!x || NodeTraits::get_color(x) == NodeTraits::black())){
          if(x == NodeTraits::get_left(x_parent)){
             node_ptr w = NodeTraits::get_right(x_parent);
+            BOOST_ASSERT(w);
             if(NodeTraits::get_color(w) == NodeTraits::red()){
                NodeTraits::set_color(w, NodeTraits::black());
                NodeTraits::set_color(x_parent, NodeTraits::red());
                tree_algorithms::rotate_left(x_parent, header);
                w = NodeTraits::get_right(x_parent);
             }
-            if((NodeTraits::get_left(w) == node_ptr() || NodeTraits::get_color(NodeTraits::get_left(w))  == NodeTraits::black()) &&
-               (NodeTraits::get_right(w) == node_ptr() || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black())){
+            if((!NodeTraits::get_left(w) || NodeTraits::get_color(NodeTraits::get_left(w))  == NodeTraits::black()) &&
+               (!NodeTraits::get_right(w) || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black())){
                NodeTraits::set_color(w, NodeTraits::red());
                x = x_parent;
                x_parent = NodeTraits::get_parent(x_parent);
             }
             else {
-               if(NodeTraits::get_right(w) == node_ptr() || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()){
+               if(!NodeTraits::get_right(w) || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()){
                   NodeTraits::set_color(NodeTraits::get_left(w), NodeTraits::black());
                   NodeTraits::set_color(w, NodeTraits::red());
                   tree_algorithms::rotate_right(w, header);
@@ -847,14 +847,14 @@
                tree_algorithms::rotate_right(x_parent, header);
                w = NodeTraits::get_left(x_parent);
             }
-            if((NodeTraits::get_right(w) == node_ptr() || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()) &&
-               (NodeTraits::get_left(w) == node_ptr() || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black())){
+            if((!NodeTraits::get_right(w) || NodeTraits::get_color(NodeTraits::get_right(w)) == NodeTraits::black()) &&
+               (!NodeTraits::get_left(w) || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black())){
                NodeTraits::set_color(w, NodeTraits::red());
                x = x_parent;
                x_parent = NodeTraits::get_parent(x_parent);
             }
             else {
-               if(NodeTraits::get_left(w) == node_ptr() || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black()){
+               if(!NodeTraits::get_left(w) || NodeTraits::get_color(NodeTraits::get_left(w)) == NodeTraits::black()){
                   NodeTraits::set_color(NodeTraits::get_right(w), NodeTraits::black());
                   NodeTraits::set_color(w, NodeTraits::red());
                   tree_algorithms::rotate_left(w, header);
@@ -874,9 +874,8 @@
    }
 
 
-   static void rebalance_after_insertion(const node_ptr & header, const node_ptr &pnode)
+   static void rebalance_after_insertion(const node_ptr & header, node_ptr p)
    {
-      node_ptr p(pnode);
       NodeTraits::set_color(p, NodeTraits::red());
       while(p != NodeTraits::get_parent(header) && NodeTraits::get_color(NodeTraits::get_parent(p)) == NodeTraits::red()){
          node_ptr p_parent(NodeTraits::get_parent(p));