BIND 10 #2750: support DomainTree::remove()

[BIND 10 Development]

#2750: support DomainTree::remove()
-------------------------------------+-------------------------------------
            Reporter:  jinmei        |                        Owner:  muks
                Type:  task          |                       Status:
            Priority:  medium        |  reviewing
           Component:  data source   |                    Milestone:
            Keywords:                |  Sprint-20130917
           Sensitive:  0             |                   Resolution:
         Sub-Project:  DNS           |                 CVSS Scoring:
Estimated Difficulty:  7             |              Defect Severity:  N/A
         Total Hours:  0             |  Feature Depending on Ticket:
                                     |  shared memory data source
                                     |          Add Hours to Ticket:  0
                                     |                    Internal?:  0
-------------------------------------+-------------------------------------
Changes (by vorner):

 * owner:  vorner => muks


Comment:

 Hello

 I'm not sure what the exact problem with clang++ is, but I believe it is
 one of our officially supported compilers and we should not break it.
 Could this be worked around in some way, like explicitly placing the class
 name (with the parameters) there, or something? Or using free-standing
 functions instead of static ones?

 Now, some details to the code.

 The name of methods and comment suggests it would set the pointers
 mutually (child to parent and parent to child), but it is not so. Should
 the comment be reformulated and/or renamed?
 {{{#!c++
     /// \brief Helper method used in many places in code to set
     /// parent-child links.
     void setParentChild(DomainTreeNode<T>* oldnode,
 }}}

 This condition looks asymetric:
 {{{#!c++
         std::swap(left_, other->left_);
         if (other->getLeft() == other) {
             other->left_ = this;
         }
 }}}

 Why don't we need to check if `left_` is pointing to itself. Or do we
 check it somewhere?

 This seems to be unconditional. Is that OK?
 {{{#!c++
         other->setParentChild(this, other, root_ptr);
 }}}

 Do I need to explicitly instantiate the const and non-const version of
 `abstractSuccessor`? That one is a private implementation for `successor`
 and `predecessor`, so these two could use the templated version directly.
 I think it would be less code and more readable (one less layer of wrapper
 functions).

 The same kind of double indirection is with the `find` methods.

 I mentioned this when we were trying to find the bug, but I think this is
 more work than necessary. I think that the exchange needs to be done only
 when both left and right pointers are non-NULL.

 {{{#!c++
     // node points to the node to be deleted in the BST. It first has to
     // be exchanged with the right-most node in the left sub-tree or the
     // left-most node in the right sub-tree. (Here, sub-tree is inside
     // this RB tree itself, not in the tree-of-trees forest.) The node
     // then ends up having a maximum of 1 child. Note that this is not
     // 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) {
         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_);
     }
 }}}

 I'd suggest using this instead:

 {{{#!c++
 if (node->getLeft() != NULL && node->getRight() != NULL) {
         DomainTreeNode<T>* rightmost = node->getLeft();
         while (rightmost->getRight() != NULL) {
             rightmost = rightmost->getRight();
         }

         node->exchange(rightmost, &root_);
 }
 }}}

 Also, isn't there a method for something like a biggest node in a subtree?
 Or, actually, either predecessor or successor would do as well (instead of
 doing a while cycle there).

 I'm not completely sure this is what we want in the functionality. If we
 have domains x.example.org and y.x.example.org and we decide to delete
 x.example.org, it does not mean we want y.x.example.org deleted too.

 Didn't I see a `getSibling` method somewhere? I've seen this at least
 twice in the `removeRebalance` method.
 {{{#!c++
         DomainTreeNode<T>* sibling = (parent->getLeft() == child) ?
             parent->getRight() : parent->getLeft();
 }}}

 Would use of `std::min` simplify matters here?
 {{{#!c++
     const size_t this_height = (dl > dr) ? (dl + 1) : (dr + 1);
     const size_t down_height = getHeightHelper(node->getDown());

     return ((this_height > down_height) ? this_height : down_height);
 }
 }}}

 I think this was copy-pasted so many times someone (not necessarily you)
 lost the explicit root mentioned in the comment.
 {{{#!c++
 // The full absolute names of the nodes in the tree with the addition of
 // the explicit root node.
 const char* const domain_names[] = {
     "c", "b", "a", "x.d.e.f", "z.d.e.f", "g.h", "i.g.h", "o.w.y.d.e.f",
     "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f", "k.g.h"
 };
 }}}

-- 
Ticket URL: <http://bind10.isc.org/ticket/2750#comment:15>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development