Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r54336 - in trunk/boost/intrusive: . detail
From: igaztanaga_at_[hidden]
Date: 2009-06-25 12:08:20


Author: igaztanaga
Date: 2009-06-25 12:08:20 EDT (Thu, 25 Jun 2009)
New Revision: 54336
URL: http://svn.boost.org/trac/boost/changeset/54336

Log:
Boost 1.40 changes
Text files modified:
   trunk/boost/intrusive/avltree_algorithms.hpp | 204 +++++++++------------------------------
   trunk/boost/intrusive/detail/tree_algorithms.hpp | 84 ++++++++-------
   2 files changed, 92 insertions(+), 196 deletions(-)

Modified: trunk/boost/intrusive/avltree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/avltree_algorithms.hpp (original)
+++ trunk/boost/intrusive/avltree_algorithms.hpp 2009-06-25 12:08:20 EDT (Thu, 25 Jun 2009)
@@ -664,8 +664,7 @@
 
    static void rebalance_after_erasure(node_ptr header, node_ptr x, node_ptr x_parent)
    {
- node_ptr root = NodeTraits::get_parent(header);
- while (x != root) {
+ for (node_ptr root = NodeTraits::get_parent(header); x != root; root = NodeTraits::get_parent(header)) {
          const balance x_parent_balance = NodeTraits::get_balance(x_parent);
          if(x_parent_balance == NodeTraits::zero()){
             NodeTraits::set_balance(x_parent,
@@ -686,16 +685,14 @@
                if (NodeTraits::get_balance(a) == NodeTraits::positive()) {
                   // a MUST have a right child
                   BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_right(a));
- rotate_left_right(x_parent, root);
-
+ rotate_left_right(x_parent, header);
                   x = NodeTraits::get_parent(x_parent);
                   x_parent = NodeTraits::get_parent(x);
                }
                else {
- rotate_right(x_parent, root);
+ rotate_right(x_parent, header);
                   x = NodeTraits::get_parent(x_parent);
                   x_parent = NodeTraits::get_parent(x);
-
                }
 
                // if changed from negative to NodeTraits::positive(), no need to check above
@@ -718,15 +715,15 @@
                if (NodeTraits::get_balance(a) == NodeTraits::negative()) {
                   // a MUST have then a left child
                   BOOST_INTRUSIVE_INVARIANT_ASSERT(NodeTraits::get_left(a));
- rotate_right_left(x_parent, root);
+ rotate_right_left(x_parent, header);
 
                   x = NodeTraits::get_parent(x_parent);
                   x_parent = NodeTraits::get_parent(x);
                }
                else {
- rotate_left(x_parent, root);
- x = NodeTraits::get_parent(x_parent);
- x_parent = NodeTraits::get_parent(x);
+ rotate_left(x_parent, header);
+ x = NodeTraits::get_parent(x_parent);
+ x_parent = NodeTraits::get_parent(x);
                }
                // if changed from NodeTraits::positive() to negative, no need to check above
                if (NodeTraits::get_balance(x) == NodeTraits::negative()){
@@ -738,17 +735,14 @@
             BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached
          }
       }
- NodeTraits::set_parent(header, root);
    }
 
-
    static void rebalance_after_insertion(node_ptr header, node_ptr x)
    {
- node_ptr root = NodeTraits::get_parent(header);
       NodeTraits::set_balance(x, NodeTraits::zero());
 
       // Rebalance.
- while (x != root){
+ for(node_ptr root = NodeTraits::get_parent(header); x != root; root = NodeTraits::get_parent(header)){
          const balance x_parent_balance = NodeTraits::get_balance(NodeTraits::get_parent(x));
 
          if(x_parent_balance == NodeTraits::zero()){
@@ -765,9 +759,9 @@
                NodeTraits::set_balance(NodeTraits::get_parent(x), NodeTraits::zero());
             else{ // x is a right child, needs rebalancing
                if (NodeTraits::get_balance(x) == NodeTraits::negative())
- rotate_right_left(NodeTraits::get_parent(x), root);
+ rotate_right_left(NodeTraits::get_parent(x), header);
                else
- rotate_left(NodeTraits::get_parent(x), root);
+ rotate_left(NodeTraits::get_parent(x), header);
             }
             break;
          }
@@ -775,9 +769,9 @@
             // if x is a left child, needs rebalancing
             if (x == NodeTraits::get_left(NodeTraits::get_parent(x))) {
                if (NodeTraits::get_balance(x) == NodeTraits::positive())
- rotate_left_right(NodeTraits::get_parent(x), root);
+ rotate_left_right(NodeTraits::get_parent(x), header);
                else
- rotate_right(NodeTraits::get_parent(x), root);
+ rotate_right(NodeTraits::get_parent(x), header);
             }
             else
                NodeTraits::set_balance(NodeTraits::get_parent(x), NodeTraits::zero());
@@ -787,67 +781,49 @@
             BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached
          }
       }
- NodeTraits::set_parent(header, root);
    }
 
- static void rotate_left_right(node_ptr a, node_ptr &root)
+ static void left_right_balancing(node_ptr a, node_ptr b, node_ptr c)
    {
- // | | //
- // a(-2) c //
- // / \ / \ //
- // / \ ==> / \ //
- // (pos)b [g] b a //
- // / \ / \ / \ //
- // [d] c [d] e f [g] //
- // / \ //
- // e f //
- node_ptr b = NodeTraits::get_left(a), c = NodeTraits::get_right(b);
-
- // switch
- NodeTraits::set_left(a, NodeTraits::get_right(c));
- NodeTraits::set_right(b, NodeTraits::get_left(c));
-
- NodeTraits::set_right(c, a);
- NodeTraits::set_left(c, b);
-
- // set the parents
- NodeTraits::set_parent(c, NodeTraits::get_parent(a));
- NodeTraits::set_parent(a, c);
- NodeTraits::set_parent(b, c);
-
- if (NodeTraits::get_left(a)) // do we have f?
- NodeTraits::set_parent(NodeTraits::get_left(a), a);
- if (NodeTraits::get_right(b)) // do we have e?
- NodeTraits::set_parent(NodeTraits::get_right(b), b);
-
- if (a==root) root = c;
- else // a had a parent, his child is now c
- if (a == NodeTraits::get_left(NodeTraits::get_parent(c)))
- NodeTraits::set_left(NodeTraits::get_parent(c), c);
- else
- NodeTraits::set_right(NodeTraits::get_parent(c), c);
-
       // balancing...
       const balance c_balance = NodeTraits::get_balance(c);
+ const balance zero_balance = NodeTraits::zero();
+ NodeTraits::set_balance(c, zero_balance);
       if(c_balance == NodeTraits::negative()){
          NodeTraits::set_balance(a, NodeTraits::positive());
- NodeTraits::set_balance(b, NodeTraits::zero());
+ NodeTraits::set_balance(b, zero_balance);
       }
- else if(c_balance == NodeTraits::zero()){
- NodeTraits::set_balance(a, NodeTraits::zero());
- NodeTraits::set_balance(b, NodeTraits::zero());
+ else if(c_balance == zero_balance){
+ NodeTraits::set_balance(a, zero_balance);
+ NodeTraits::set_balance(b, zero_balance);
       }
       else if(c_balance == NodeTraits::positive()){
- NodeTraits::set_balance(a, NodeTraits::zero());
+ NodeTraits::set_balance(a, zero_balance);
          NodeTraits::set_balance(b, NodeTraits::negative());
       }
       else{
          BOOST_INTRUSIVE_INVARIANT_ASSERT(false); // never reached
       }
- NodeTraits::set_balance(c, NodeTraits::zero());
    }
 
- static void rotate_right_left(node_ptr a, node_ptr &root)
+ static void rotate_left_right(const node_ptr a, node_ptr hdr)
+ {
+ // | | //
+ // a(-2) c //
+ // / \ / \ //
+ // / \ ==> / \ //
+ // (pos)b [g] b a //
+ // / \ / \ / \ //
+ // [d] c [d] e f [g] //
+ // / \ //
+ // e f //
+ node_ptr b = NodeTraits::get_left(a), c = NodeTraits::get_right(b);
+ tree_algorithms::rotate_left(b, hdr);
+ tree_algorithms::rotate_right(a, hdr);
+ left_right_balancing(a, b, c);
+ }
+
+ static void rotate_right_left(const node_ptr a, node_ptr hdr)
    {
       // | | //
       // a(pos) c //
@@ -859,81 +835,15 @@
       // / \ //
       // e f //
       node_ptr b = NodeTraits::get_right(a), c = NodeTraits::get_left(b);
-
- // switch
- NodeTraits::set_right(a, NodeTraits::get_left(c));
- NodeTraits::set_left(b, NodeTraits::get_right(c));
-
- NodeTraits::set_left(c, a);
- NodeTraits::set_right(c, b);
-
- // set the parents
- NodeTraits::set_parent(c, NodeTraits::get_parent(a));
- NodeTraits::set_parent(a, c);
- NodeTraits::set_parent(b, c);
-
- if (NodeTraits::get_right(a)) // do we have e?
- NodeTraits::set_parent(NodeTraits::get_right(a), a);
- if (NodeTraits::get_left(b)) // do we have f?
- NodeTraits::set_parent(NodeTraits::get_left(b), b);
-
- if (a==root) root = c;
- else // a had a parent, his child is now c
- if (a == NodeTraits::get_left(NodeTraits::get_parent(c)))
- NodeTraits::set_left(NodeTraits::get_parent(c), c);
- else
- NodeTraits::set_right(NodeTraits::get_parent(c), c);
-
- // balancing...
- const balance c_balance = NodeTraits::get_balance(c);
- if(c_balance == NodeTraits::negative()){
- NodeTraits::set_balance(a, NodeTraits::zero());
- NodeTraits::set_balance(b, NodeTraits::positive());
- }
- else if(c_balance == NodeTraits::zero()){
- NodeTraits::set_balance(a, NodeTraits::zero());
- NodeTraits::set_balance(b, NodeTraits::zero());
- }
- else if(c_balance == NodeTraits::positive()){
- NodeTraits::set_balance(a, NodeTraits::negative());
- NodeTraits::set_balance(b, NodeTraits::zero());
- }
- else{
- BOOST_INTRUSIVE_INVARIANT_ASSERT(false);
- }
- NodeTraits::set_balance(c, NodeTraits::zero());
+ tree_algorithms::rotate_right(b, hdr);
+ tree_algorithms::rotate_left(a, hdr);
+ left_right_balancing(b, a, c);
    }
 
- static void rotate_left(node_ptr x, node_ptr & root)
+ static void rotate_left(const node_ptr x, node_ptr hdr)
    {
- // | | //
- // x(2) y(0) //
- // / \ ==> / \ //
- // n[a] y(1)n+2 n+1(0)x [c]n+1 //
- // / \ / \ //
- // n[b] [c]n+1 n[a] [b]n //
- node_ptr y = NodeTraits::get_right(x);
-
- // switch
- NodeTraits::set_right(x, NodeTraits::get_left(y));
- NodeTraits::set_left(y, x);
-
- // rearrange parents
- NodeTraits::set_parent(y, NodeTraits::get_parent(x));
- NodeTraits::set_parent(x, y);
-
- // do we have [b]?
- if (NodeTraits::get_right(x))
- NodeTraits::set_parent(NodeTraits::get_right(x), x);
-
- if (x == root)
- root = y;
- else
- // need to reparent y
- if (NodeTraits::get_left(NodeTraits::get_parent(y)) == x)
- NodeTraits::set_left(NodeTraits::get_parent(y), y);
- else
- NodeTraits::set_right(NodeTraits::get_parent(y), y);
+ const node_ptr y = NodeTraits::get_right(x);
+ tree_algorithms::rotate_left(x, hdr);
 
       // reset the balancing factor
       if (NodeTraits::get_balance(y) == NodeTraits::positive()) {
@@ -946,30 +856,10 @@
       }
    }
 
- static void rotate_right(node_ptr x, node_ptr &root)
+ static void rotate_right(const node_ptr x, node_ptr hdr)
    {
- node_ptr y = NodeTraits::get_left(x);
-
- // switch
- NodeTraits::set_left(x, NodeTraits::get_right(y));
- NodeTraits::set_right(y, x);
-
- // rearrange parents
- NodeTraits::set_parent(y, NodeTraits::get_parent(x));
- NodeTraits::set_parent(x, y);
-
- // do we have [b]?
- if (NodeTraits::get_left(x))
- NodeTraits::set_parent(NodeTraits::get_left(x), x);
-
- if (x == root)
- root = y;
- else
- // need to reparent y
- if (NodeTraits::get_left(NodeTraits::get_parent(y)) == x)
- NodeTraits::set_left(NodeTraits::get_parent(y), y);
- else
- NodeTraits::set_right(NodeTraits::get_parent(y), y);
+ const node_ptr y = NodeTraits::get_left(x);
+ tree_algorithms::rotate_right(x, hdr);
 
       // reset the balancing factor
       if (NodeTraits::get_balance(y) == NodeTraits::negative()) {

Modified: trunk/boost/intrusive/detail/tree_algorithms.hpp
==============================================================================
--- trunk/boost/intrusive/detail/tree_algorithms.hpp (original)
+++ trunk/boost/intrusive/detail/tree_algorithms.hpp 2009-06-25 12:08:20 EDT (Thu, 25 Jun 2009)
@@ -1232,69 +1232,75 @@
    //! <b>Complexity</b>: Constant.
    //!
    //! <b>Throws</b>: Nothing.
- static bool is_right_child (node_ptr p)
+ static bool is_right_child(node_ptr p)
    { return NodeTraits::get_right(NodeTraits::get_parent(p)) == p; }
 
- static void replace_own (node_ptr own, node_ptr x, node_ptr header)
+ //Fix header and own's parent data when replacing x with own, providing own's old data with parent
+ static void replace_own_impl(node_ptr own, node_ptr x, node_ptr header, node_ptr own_parent, bool own_was_left)
    {
       if(NodeTraits::get_parent(header) == own)
          NodeTraits::set_parent(header, x);
- else if(is_left_child(own))
- NodeTraits::set_left(NodeTraits::get_parent(own), x);
+ else if(own_was_left)
+ NodeTraits::set_left(own_parent, x);
       else
- NodeTraits::set_right(NodeTraits::get_parent(own), x);
+ NodeTraits::set_right(own_parent, x);
    }
 
- static void rotate_left(node_ptr p, node_ptr header)
+ //Fix header and own's parent data when replacing x with own, supposing own
+ //links with its parent are still ok
+ static void replace_own(node_ptr own, node_ptr x, node_ptr header)
    {
- node_ptr x = NodeTraits::get_right(p);
- NodeTraits::set_right(p, NodeTraits::get_left(x));
- if(NodeTraits::get_left(x) != 0)
- NodeTraits::set_parent(NodeTraits::get_left(x), p);
- NodeTraits::set_parent(x, NodeTraits::get_parent(p));
- replace_own (p, x, header);
+ node_ptr own_parent(NodeTraits::get_parent(own));
+ bool own_is_left(NodeTraits::get_left(own_parent) == own);
+ replace_own_impl(own, x, header, own_parent, own_is_left);
+ }
+
+ // rotate parent p to left (no header and p's parent fixup)
+ static node_ptr rotate_left(node_ptr p)
+ {
+ node_ptr x(NodeTraits::get_right(p));
+ node_ptr x_left(NodeTraits::get_left(x));
+ NodeTraits::set_right(p, x_left);
+ if(x_left){
+ NodeTraits::set_parent(x_left, p);
+ }
       NodeTraits::set_left(x, p);
       NodeTraits::set_parent(p, x);
+ return x;
    }
 
- static void rotate_right(node_ptr p, node_ptr header)
+ // rotate parent p to left (with header and p's parent fixup)
+ static void rotate_left(node_ptr p, node_ptr header)
+ {
+ bool p_was_left(is_left_child(p));
+ node_ptr p_old_parent(NodeTraits::get_parent(p));
+ node_ptr x(rotate_left(p));
+ NodeTraits::set_parent(x, p_old_parent);
+ replace_own_impl(p, x, header, p_old_parent, p_was_left);
+ }
+
+ // rotate parent p to right (no header and p's parent fixup)
+ static node_ptr rotate_right(node_ptr p)
    {
       node_ptr x(NodeTraits::get_left(p));
       node_ptr x_right(NodeTraits::get_right(x));
       NodeTraits::set_left(p, x_right);
- if(x_right)
+ if(x_right){
          NodeTraits::set_parent(x_right, p);
- NodeTraits::set_parent(x, NodeTraits::get_parent(p));
- replace_own (p, x, header);
+ }
       NodeTraits::set_right(x, p);
       NodeTraits::set_parent(p, x);
- }
-
- // rotate node t with left child | complexity : constant | exception : nothrow
- static node_ptr rotate_left(node_ptr t)
- {
- node_ptr x = NodeTraits::get_right(t);
- NodeTraits::set_right(t, NodeTraits::get_left(x));
-
- if( NodeTraits::get_right(t) != 0 ){
- NodeTraits::set_parent(NodeTraits::get_right(t), t );
- }
- NodeTraits::set_left(x, t);
- NodeTraits::set_parent(t, x);
       return x;
    }
 
- // rotate node t with right child | complexity : constant | exception : nothrow
- static node_ptr rotate_right(node_ptr t)
+ // rotate parent p to right (with header and p's parent fixup)
+ static void rotate_right(node_ptr p, node_ptr header)
    {
- node_ptr x = NodeTraits::get_left(t);
- NodeTraits::set_left(t, NodeTraits::get_right(x));
- if( NodeTraits::get_left(t) != 0 ){
- NodeTraits::set_parent(NodeTraits::get_left(t), t);
- }
- NodeTraits::set_right(x, t);
- NodeTraits::set_parent(t, x);
- return x;
+ bool p_was_left(is_left_child(p));
+ node_ptr p_old_parent(NodeTraits::get_parent(p));
+ node_ptr x(rotate_right(p));
+ NodeTraits::set_parent(x, p_old_parent);
+ replace_own_impl(p, x, header, p_old_parent, p_was_left);
    }
 
    static void link(node_ptr header, node_ptr z, node_ptr par, bool left)


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk