BIND 10 trac2750, updated. 3984b23014333a678d3c78f8253312bede64a213 [2750] exchange() nodes only when node to be removed has both children

[BIND 10 source code commits]

The branch, trac2750 has been updated
       via  3984b23014333a678d3c78f8253312bede64a213 (commit)
       via  0edf1c3dd2e12a28ecb74e47bdc969d6dc15fcd4 (commit)
      from  9eeab2e6b02fcf316b81bcc72c0dadef84b9a07d (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 3984b23014333a678d3c78f8253312bede64a213
Author: Mukund Sivaraman <muks at isc.org>
Date:   Fri Sep 6 11:32:25 2013 +0530

    [2750] exchange() nodes only when node to be removed has both children

commit 0edf1c3dd2e12a28ecb74e47bdc969d6dc15fcd4
Author: Mukund Sivaraman <muks at isc.org>
Date:   Fri Sep 6 11:28:33 2013 +0530

    [2750] Check that sub-tree roots have the flag set
    
    This did not matter during the remove() so far, but in the future
    we may not call exchange() even for some cases of non-leaf nodes.

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

Summary of changes:
 src/lib/datasrc/memory/domaintree.h |   26 ++++++++++++++++++--------
 1 file changed, 18 insertions(+), 8 deletions(-)

-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 7d5bc0e..af080e2 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -2293,20 +2293,13 @@ DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
     // an in-place value swap of node data, but the actual node
     // locations are swapped in exchange(). Unlike normal BSTs, we have
     // to do this as our label data is at address (this + 1).
-    if (node->getLeft() != NULL) {
+    if (node->getLeft() && node->getRight()) {
         DomainTreeNode<T>* rightmost = node->getLeft();
         while (rightmost->getRight() != NULL) {
             rightmost = rightmost->getRight();
         }
 
         node->exchange(rightmost, &root_);
-    } else if (node->getRight() != NULL) {
-        DomainTreeNode<T>* leftmost = node->getRight();
-        while (leftmost->getLeft() != NULL) {
-            leftmost = leftmost->getLeft();
-        }
-
-        node->exchange(leftmost, &root_);
     }
 
     // Now, node has 0 or 1 children, as from above, either its right or
@@ -2326,6 +2319,14 @@ DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
     // Child can be NULL here if node was a leaf.
     if (child) {
         child->parent_ = node->getParent();
+        // Even if node is not a leaf node, we don't always do an
+        // exchange() with another node, so we have to set the child's
+        // FLAG_SUBTREE_ROOT explicitly.
+        if (child->getParent() &&
+            (child->getParent()->getDown() == child))
+        {
+            child->setSubTreeRoot(node->isSubTreeRoot());
+        }
     }
 
     // If node is RED, it is a valid red-black tree already as (node's)
@@ -2950,6 +2951,15 @@ DomainTree<T>::checkPropertiesHelper(const DomainTreeNode<T>* node) const {
         }
     }
 
+    // If node is assigned to the down_ pointer of its parent, it is a
+    // subtree root and must have the flag set.
+    if (node->getParent() &&
+        (node->getParent()->getDown() == node) &&
+        (!node->isSubTreeRoot()))
+    {
+        return (false);
+    }
+
     // Repeat tests with this node's children.
     return (checkPropertiesHelper(node->getLeft()) &&
             checkPropertiesHelper(node->getRight()) &&