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

[BIND 10 Development]

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

 * owner:  muks => vorner


Comment:

 Hi Michal

 Replying to [comment:15 vorner]:
 > 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?

 Even I'm not able to figure it out, but I'll give it some more work
 after getting `master` to compile with `clang++` on my workstation
 (there are other unrelated issues that prevent `clang++` build). For
 now, let's do another round of review of this branch except for this
 issue alone. We'll address this issue finally.

 > 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,
 > }}}

 Re-reading the code, all I can come up with is `setParentsChild()` (with
 an extra `s`) which is not much of an improvement. Can you suggest a
 name?

 > 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?

 I'm sorry there were no comments towards this. I must have missed
 thinking of it from a reader's point of view. This is asymmetric on
 purpose. I have added comments in the code now.

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

 I didn't understand this. What is wrong here?

 > 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).

 Nod. This has been updated.

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

 I'm not sure if we can avoid the `find()` changes as they are `public`
 methods. Or am I missing the point?

 > 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_);
 > }
 > }}}

 You're right. The code has been updated towards this. Because an
 `exchange()` that used to happen doesn't take place in some
 circumstances, some extra code had to be added. I've also added a test
 for it in `checkProperties()` list of checks.

 > 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).

 `largestNode()` is a forest-method.

 You're right that `predecessor()` will work, but given that this is just
 3 inlined statements and is easier to read over as BST removal code, I'm
 siding with keeping it as it is.

 > 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.

 For these special circumstances, I keep a paper bag to wear on my head
 on my desk. :)

 This's been updated. Note that this also removes empty nodes upward the
 tree during deletion now if possible, and rebalances higher trees as
 necessary.

 > 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();
 > }}}

 I had initially removed it, as the first versions of the rebalancing
 code were such that inlining it was simpler. Even now it has to be a
 `static` function, but it has been re-introduced now.

 > 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);
 > }
 > }}}

 Nod. Code was updated.

 > 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"
 > };
 > }}}

 From how I read it, the comment seems to say that these are the names in
 the tree, along with the "." node. If the "." node was already there, it
 wouldn't say that explicitly.

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