BIND 10 trac2750, updated. 49fa0bad8fa7bcc0355acadede93b9f3ce679f14 [2750] Finish documenting the red-black tree remove rebalance operation

[BIND 10 source code commits]

The branch, trac2750 has been updated
       via  49fa0bad8fa7bcc0355acadede93b9f3ce679f14 (commit)
       via  7cf392993b65c0b69443f1e749ae067c3d6f142c (commit)
      from  0467d75d487b5c7d559ccf9a73e9fe105cd485cd (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 49fa0bad8fa7bcc0355acadede93b9f3ce679f14
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon Sep 2 19:37:35 2013 +0530

    [2750] Finish documenting the red-black tree remove rebalance operation

commit 7cf392993b65c0b69443f1e749ae067c3d6f142c
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon Sep 2 19:19:25 2013 +0530

    [2750] Remove redundant part of condition
    
    If ss2 is black, it implies that ss1 is red. This commit updates
    the shortcut && operator, but the result is the same.

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

Summary of changes:
 src/lib/datasrc/memory/domaintree.h |   40 ++++++++++++++++++++++++++++++-----
 1 file changed, 35 insertions(+), 5 deletions(-)

-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 4d1c99c..ab74515 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -2838,9 +2838,7 @@ DomainTree<T>::removeRebalance
             std::swap(ss1, ss2);
         }
 
-        if (DomainTreeNode<T>::isRed(ss1) &&
-            DomainTreeNode<T>::isBlack(ss2))
-        {
+        if (DomainTreeNode<T>::isBlack(ss2)) {
             sibling->setColor(DomainTreeNode<T>::RED);
             // ss1 cannot be NULL here as it is a RED node.
             ss1->setColor(DomainTreeNode<T>::BLACK);
@@ -2873,10 +2871,36 @@ DomainTree<T>::removeRebalance
 
         // 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
+        // left-child of parent, the right-child (ss2) of sibling is
         // definitely RED, or (b) if child is the right-child of parent,
-        // the left-child of sibling is definitely RED.
+        // the left-child (ss2) of sibling is definitely RED.
+        //
+        // Here, we set sibling's color to that of the parent, and set
+        // the parent's color to BLACK. We set ss2's color to BLACK (it
+        // was previously RED). Then we do a tree-rotation around parent
+        // in the direction of child to pull in the BLACK parent into
+        // its sub-tree. These steps effectively balances the tree as
+        // you can see from the graph below. Before starting, the graph
+        // on the child's side is lighter by 1 BLACK node than the graph
+        // on the sibling's side. After these steps, both sides of S(x)
+        // have the same number of BLACK nodes in any path through it.
 
+        /* (a):
+         *
+         *          P(x)                            S(x)
+         *         /    \                         /     \
+         *      C(?)     S(B)         =>      P(B)      ss2(B)
+         *       / \    /    \               /   \        /  \
+         *            ss1(?) ss2(R)       C(?) ss1(?)   (B)  (B)
+         *                    /  \        / \
+         *                  (B)  (B)
+         *
+         *     (Here, 'x' is the parent's color. In the resulting tree,
+         *      it is set as S node's color.)
+         *
+         * (b):
+         *      This is just the mirror of above.
+         */
 
         sibling->setColor(parent->getColor());
         parent->setColor(DomainTreeNode<T>::BLACK);
@@ -2898,6 +2922,12 @@ DomainTree<T>::removeRebalance
             rightRotate(root_ptr, parent);
         }
 
+        // NOTE #9: Now, sibling is parent's parent. All paths through
+        // sibling have the same number of BLACK nodes.
+
+        // We are completely finished and the tree is now
+        // balanced. Phew. Now let's take a coffee-break.
+
         break;
     }
 }