BIND 10 trac2750, updated. 927411d1d221265f82608e62a22683c203103209 [2750] Add comments for rebalancing code in remove()

[BIND 10 source code commits]

The branch, trac2750 has been updated
       via  927411d1d221265f82608e62a22683c203103209 (commit)
      from  b6ca9a816726b573004d1a9140ad38522bec50f8 (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 927411d1d221265f82608e62a22683c203103209
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon Sep 2 08:35:22 2013 +0530

    [2750] Add comments for rebalancing code in remove()

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

Summary of changes:
 src/lib/datasrc/memory/domaintree.h |   13 +++++++++++++
 1 file changed, 13 insertions(+)

-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index ffb6ec7..666db59 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -2315,10 +2315,23 @@ DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
         child->parent_ = node->getParent();
     }
 
+    // If node is RED, it is a valid red-black tree already as (node's)
+    // child must be BLACK or NULL (which is BLACK). Deleting (the RED)
+    // node will not have any effect on the number of BLACK nodes
+    // through this path (involving node's parent and its new child). In
+    // this case, we can skip the following block.
     if (node->isBlack()) {
         if (child && child->isRed()) {
+            // If node is BLACK and child is RED, removing node would
+            // decrease the number of BLACK nodes through this path
+            // (involving node's parent and its new child). So we color
+            // child to be BLACK to restore the old count of black nodes
+            // through this path. It is now a valid red-black tree.
             child->setColor(DomainTreeNode<T>::BLACK);
         } else {
+            // If node is BLACK and child is also BLACK or NULL (which
+            // is BLACK), we need to do re-balancing to make it a valid
+            // red-black tree again.
             typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr =
                 upper_node ? &(upper_node->down_) : &root_;
             removeRebalance(root_ptr, child, node->getParent());