BIND 10 trac2750, updated. 0467d75d487b5c7d559ccf9a73e9fe105cd485cd [2750] Add/update RB tree delete rebalancing comments

BIND 10 source code commits bind10-changes at lists.isc.org
Mon Sep 2 13:46:26 UTC 2013


The branch, trac2750 has been updated
       via  0467d75d487b5c7d559ccf9a73e9fe105cd485cd (commit)
       via  6024678d9b397613cf8f9b5454b14f9b98e1b176 (commit)
       via  967e79e9748de98d874df011184c03bf27c5e8dd (commit)
       via  ec1cb0b7b54e161404079ca63124aa85d1553104 (commit)
       via  1d38fe32f5f891958d302b46044cd961a074ec41 (commit)
       via  4ee1f3305b8704b7c5da130e163285bbfcbf36d7 (commit)
      from  d15a492eb3479310af51cb1a9dde60faa1d57249 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit 0467d75d487b5c7d559ccf9a73e9fe105cd485cd
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon Sep 2 19:16:08 2013 +0530

    [2750] Add/update RB tree delete rebalancing comments

commit 6024678d9b397613cf8f9b5454b14f9b98e1b176
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon Sep 2 19:15:37 2013 +0530

    [2750] Rewrite code to use a similar block as previous case

commit 967e79e9748de98d874df011184c03bf27c5e8dd
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon Sep 2 19:15:02 2013 +0530

    [2750] Fix tree rotation direction

commit ec1cb0b7b54e161404079ca63124aa85d1553104
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon Sep 2 19:14:30 2013 +0530

    [2750] Remove redundant NULL test

commit 1d38fe32f5f891958d302b46044cd961a074ec41
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon Sep 2 19:13:04 2013 +0530

    [2750] Reduce code by using getColor()

commit 4ee1f3305b8704b7c5da130e163285bbfcbf36d7
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon Sep 2 16:05:19 2013 +0530

    [2750] Remove redundant condition to check if sibling is black
    
    Add appropriate pre-condition assertions.

-----------------------------------------------------------------------

Summary of changes:
 src/lib/datasrc/memory/domaintree.h |  179 +++++++++++++++++++++++------------
 1 file changed, 118 insertions(+), 61 deletions(-)

-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index c91fecd..4d1c99c 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -675,22 +675,13 @@ private:
 
         // Update FLAG_RED and FLAG_SUBTREE_ROOT as these two are
         // associated with the node's position.
-        const bool this_is_red = isRed();
+        const DomainTreeNodeColor this_color = getColor();
         const bool this_is_subtree_root = isSubTreeRoot();
-        const bool other_is_red = other->isRed();
+        const DomainTreeNodeColor other_color = other->getColor();
         const bool other_is_subtree_root = other->isSubTreeRoot();
 
-        if (this_is_red) {
-            other->setColor(RED);
-        } else {
-            other->setColor(BLACK);
-        }
-
-        if (other_is_red) {
-            setColor(RED);
-        } else {
-            setColor(BLACK);
-        }
+        other->setColor(this_color);
+        setColor(other_color);
 
         setSubTreeRoot(other_is_subtree_root);
         other->setSubTreeRoot(this_is_subtree_root);
@@ -2440,11 +2431,7 @@ DomainTree<T>::tryNodeFusion(util::MemorySegment& mem_sgmt,
         }
 
         // The color of the new node is the same as the upper node's.
-        if (upper_node->isRed()) {
-            new_node->setColor(DomainTreeNode<T>::RED);
-        } else {
-            new_node->setColor(DomainTreeNode<T>::BLACK);
-        }
+        new_node->setColor(upper_node->getColor());
 
         new_node->setSubTreeRoot(upper_node->isSubTreeRoot());
 
@@ -2701,8 +2688,10 @@ DomainTree<T>::removeRebalance
             // Case 2. Here, the sibling is RED. We do a tree rotation
             // at the parent such that sibling is the new parent, and
             // the old parent is sibling's child. We also invert the
-            // colors of the two nodes. This step is done to convert the
-            // tree to a form for steps below.
+            // colors of the two nodes.
+            //
+            // This step is done to convert the tree to a form for
+            // further cases below.
 
             /* Parent (P) has to be BLACK here as its child sibling (S)
              * is RED.
@@ -2760,22 +2749,22 @@ DomainTree<T>::removeRebalance
          *
          *         G(?)                   G(?)
          *         /  \                   /  \
-         *       P(R)        =>         P(B)      (Rebalancing is done)
+         *       P(R)        =>         P(B)      (Rebalancing is complete)
          *      /   \                  /   \
-         *   C(?)   S(B)            C(?)   S(R)
-         *   / \     /  \           / \     /  \
-         *        s1(B) s2(B)            s1(B) s2(B)
+         *   C(?)    S(B)           C(?)    S(R)
+         *   / \     /   \           / \    /   \
+         *        ss1(B)  ss2(B)         ss1(B)  ss2(B)
          *
          *
          * (b):
          *
-         *         G(?)                   G(?) <----------(new parent)
+         *         G(?)                   G(?) <----------(New parent)
          *         /   \                  /   \
-         *       P(B)        =>         P(B) <------------(new child)
+         *       P(B)        =>         P(B) <------------(New child)
          *      /   \                  /   \
-         *   C(?)   S(B)            C(?)   S(R)
-         *   / \     /  \           / \     /  \
-         *        s1(B) s2(B)            s1(B) s2(B)
+         *   C(?)    S(B)           C(?)    S(R)
+         *   / \     /   \           / \    /   \
+         *        ss1(B)  ss2(B)         ss1(B)  ss2(B)
          */
 
         if ((DomainTreeNode<T>::isBlack(sibling->getLeft()) &&
@@ -2793,51 +2782,119 @@ DomainTree<T>::removeRebalance
             }
         }
 
-        if (sibling->isBlack()) {
-            DomainTreeNode<T>* ss1 = sibling->getLeft();
-            DomainTreeNode<T>* ss2 = sibling->getRight();
+        // NOTE #3 and NOTE #4 asserted above still hold here.
+        assert(DomainTreeNode<T>::isBlack(sibling));
+        assert(sibling);
 
-            if (parent->getLeft() != child) {
-                std::swap(ss1, ss2);
-            }
+        // NOTE #5: The path through parent--sibling is still heavier
+        // than parent--child by 1 extra BLACK node in its path. This is
+        // the key point, and this is why we are still doing the
+        // rebalancing.
+
+        // Case 4. Now, one or both of sibling's children are not
+        // BLACK. (a) We consider the case where child is the left-child
+        // of parent, and the left-child of sibling is RED and the
+        // right-child of sibling is BLACK. (b) We also consider its
+        // mirror, arrangement, i.e., the case where child is the
+        // right-child of parent, and the right-child of sibling is RED
+        // and the left-child of sibling is BLACK.
+        //
+        // In both cases, we change sibling's color to RED, the color of
+        // the RED child of sibling to BLACK (so both children of
+        // sibling are BLACK), and we do a tree rotation around sibling
+        // node in the opposite direction of the old RED child of
+        // sibling.
+        //
+        // This step is done to convert the tree to a form for further
+        // cases below.
 
-            if (DomainTreeNode<T>::isRed(ss1) &&
-                DomainTreeNode<T>::isBlack(ss2))
-            {
-                sibling->setColor(DomainTreeNode<T>::RED);
-                if (ss1) {
-                    ss1->setColor(DomainTreeNode<T>::BLACK);
-                }
+        /* (a):
+         *
+         *       P(?)        =>         P(?)
+         *      /   \                  /   \
+         *   C(?)    S(B)           C(?)    ss1(B)
+         *   / \     /   \           / \    /    \
+         *        ss1(R)  ss2(B)          x(B)   S(R)
+         *        /  \                           /  \
+         *      x(B) y(B)                     y(B)   ss2(B)
+         *
+         *
+         * (b):
+         *
+         *           P(?)        =>          P(?)
+         *          /    \                  /    \
+         *       S(B)     C(?)          ss1(B)   C(?)
+         *       /  \      / \           /  \     / \
+         *  ss2(B) ss1(R)             S(R)  x(B)
+         *          /  \              /  \
+         *        y(B) x(B)       ss2(B) y(B)
+         */
 
-                if (parent->getLeft() != child) {
-                    rightRotate(root_ptr, sibling);
-                } else {
-                    leftRotate(root_ptr, sibling);
-                }
-                // Re-compute child's sibling due to the tree adjustment
-                // above.
-                sibling = (parent->getLeft() == child) ?
-                    parent->getRight() : parent->getLeft();
-            }
+        DomainTreeNode<T>* ss1 = sibling->getLeft();
+        DomainTreeNode<T>* ss2 = sibling->getRight();
+        if (parent->getLeft() != child) {
+            // Swap for the mirror arrangement described in case 4 (b)
+            // above.
+            std::swap(ss1, ss2);
         }
 
-        if (parent->isRed()) {
+        if (DomainTreeNode<T>::isRed(ss1) &&
+            DomainTreeNode<T>::isBlack(ss2))
+        {
             sibling->setColor(DomainTreeNode<T>::RED);
-        } else {
-            sibling->setColor(DomainTreeNode<T>::BLACK);
+            // ss1 cannot be NULL here as it is a RED node.
+            ss1->setColor(DomainTreeNode<T>::BLACK);
+
+            if (parent->getLeft() == child) {
+                rightRotate(root_ptr, sibling);
+            } else {
+                leftRotate(root_ptr, sibling);
+            }
+            // Re-compute child's sibling due to the tree adjustment
+            // above.
+            sibling = (parent->getLeft() == child) ?
+                parent->getRight() : parent->getLeft();
         }
 
+        // NOTE #6: sibling is still BLACK, even if the sibling variable
+        // was assigned in the node above, it was set to ss1 which is
+        // now a BLACK node.
+        assert(DomainTreeNode<T>::isBlack(sibling));
+
+        // NOTE #7: sibling cannot be NULL here as even if the sibling
+        // variable was assigned in the node above, it was set to ss1
+        // which was a RED node before (non-NULL).
+        assert(sibling);
+
+        // NOTE #8: The path through parent--sibling is still heavier
+        // than parent--child by 1 extra BLACK node in its path. This is
+        // the key point, and this is why we are still doing the
+        // rebalancing.
+
+        // Case 5. After case 4 above, we are in a canonical form now
+        // where sibling is BLACK, and either (a) if child is the
+        // left-child of parent, the right-child of sibling is
+        // definitely RED, or (b) if child is the right-child of parent,
+        // the left-child of sibling is definitely RED.
+
+
+        sibling->setColor(parent->getColor());
         parent->setColor(DomainTreeNode<T>::BLACK);
 
+        ss1 = sibling->getLeft();
+        ss2 = sibling->getRight();
+        if (parent->getLeft() != child) {
+            // Swap for the mirror arrangement described in case 4 (b)
+            // above.
+            std::swap(ss1, ss2);
+        }
+
+        // ss2 cannot be NULL here as it is a RED node.
+        ss2->setColor(DomainTreeNode<T>::BLACK);
+
         if (parent->getLeft() == child) {
-            if (sibling->getRight()) {
-                sibling->getRight()->setColor(DomainTreeNode<T>::BLACK);
-            }
             leftRotate(root_ptr, parent);
         } else {
-            if (sibling->getLeft()) {
-                sibling->getLeft()->setColor(DomainTreeNode<T>::BLACK);
-            }
             rightRotate(root_ptr, parent);
         }
 



More information about the bind10-changes mailing list