Opened 7 years ago

Closed 6 years ago

#2750 closed task (fixed)

support DomainTree::remove()

Reported by: jinmei Owned by: muks
Priority: medium Milestone: Sprint-20131015
Component: data source Version:
Keywords: Cc:
CVSS Scoring: Parent Tickets:
Sensitive: no Defect Severity: N/A
Sub-Project: DNS Feature Depending on Ticket: shared memory data source
Estimated Difficulty: 7 Add Hours to Ticket: 0
Total Hours: 0 Internal?: no

Description

We need this interface to complete incremental update to in-memory
zone data after IXFR-in or DDNS. This is largely to implement to
the delete operation for a red-black tree, so it's just a matter of
porting of existing BIND 9 or whatever code of the algorithm plus
careful tests. So, in some sense, it should be an easy task, but
deleting a node from redblack tree is complicated, so it will still
require some amount of time.

Also note: the tree-of-trees nature of DomainTree will make some
additional work.

Subtickets

Change History (23)

comment:1 Changed 7 years ago by jinmei

  • Milestone changed from Previous-Sprint-Proposed to Next-Sprint-Proposed

comment:2 Changed 7 years ago by muks

Please see #2838, which I think should be done before this ticket starts. #2811 is also related, but will be obsoleted by #2838.

comment:3 Changed 7 years ago by jinmei

  • Milestone changed from Previous-Sprint-Proposed to Next-Sprint-Proposed

comment:4 Changed 7 years ago by jinmei

  • Milestone changed from Previous-Sprint-Proposed to Next-Sprint-Proposed

comment:5 Changed 7 years ago by jinmei

  • Milestone changed from Previous-Sprint-Proposed to Next-Sprint-Proposed

comment:6 Changed 7 years ago by muks

  • Keywords shared memory data source added

Adding keywords so it's easy to track this for shared memory work.

comment:7 Changed 7 years ago by muks

  • Feature Depending on Ticket set to shared memory data source
  • Keywords shared memory data source removed

comment:8 Changed 7 years ago by muks

Adding feature depending on ticket so it's easy to track this for shared memory work.

comment:9 Changed 7 years ago by muks

  • Milestone set to Sprint-20130903

comment:10 Changed 7 years ago by muks

  • Owner set to muks
  • Status changed from new to assigned

Picking

comment:11 Changed 7 years ago by muks

  • Summary changed from support DomainTree::delete() to support DomainTree::remove()

comment:12 follow-up: Changed 7 years ago by muks

  • Owner changed from muks to UnAssigned
  • Status changed from assigned to reviewing

Hello

I feel the branch trac2750 is ready for review now. A few notes for
the reviewer:

  • It is easiest to review this whole work as a single patch. Don't attempt to review it commit by commit as a lot of the code has changed among the patches.
  • The changes to find() and other DomainTree methods are to add non-const variants of these methods so that we can use the resulting mutable nodes.
  • The patch may be big, but once you review the non-const changes, the rest should be straightforward. Begin by looking at the remove() method which first does a normal BST node removal. Then look at the tryNodeFusion() method. Go to the removeRebalance() call last. Note that even if removeRebalance() or tryNodeFusion() are not called, the resulting tree is still a valid binary-search tree. So I advise you to begin with the remove() method.
  • All methods are commented so that a developer can follow what is happening. If you are unable to follow some part of code, or think the comments are inadequate, please make a note of it, especially in methods such as removeRebalance().
  • We test at the interface, and not every single case of code in removeRebalance() directly. Why we do this is is explained in the comment for DomainTreeTest.insertAndRemove unittest. Note that all cases will be covered eventually, for the RB tree to be valid, and you can verify this with lcov.
  • The outstanding major problem with this branch is that it does not compile with clang++. clang++ does not seem to support templated static method calls (find<void*>() for the CBARG type). Please verify that this is indeed the case, or provide your observation.

comment:13 Changed 7 years ago by vorner

  • Owner changed from UnAssigned to vorner

comment:14 in reply to: ↑ 12 Changed 7 years ago by muks

Replying to muks:

  • The outstanding major problem with this branch is that it does not compile with clang++. clang++ does not seem to support templated static method calls (find<void*>() for the CBARG type). Please verify that this is indeed the case, or provide your observation.

Sorry, this problem is calling templated methods from a static member function. I had stated it the other way.

A minor code cleanup commit was also pushed to the branch.

comment:15 follow-up: Changed 7 years ago by vorner

  • Owner changed from vorner to muks

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?

    /// \brief Helper method used in many places in code to set
    /// parent-child links.
    void setParentChild(DomainTreeNode<T>* oldnode,

This condition looks asymetric:

        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?

        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.

    // 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:

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.

        DomainTreeNode<T>* sibling = (parent->getLeft() == child) ?
            parent->getRight() : parent->getLeft();

Would use of std::min simplify matters here?

    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.

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

comment:16 follow-up: Changed 7 years ago by muks

I'm blocked on fixing this ticket as I need clarification on whether empty nodes are to be deleted upwards in the forest if the DomainTree is constructed to return empty nodes. In this case, its constructor argument name would also likely have to be changed as it's very find()-specific currently.

Just removing empty nodes at the tree can also get rid of intentionally added empty nodes, so this needs clarification.

comment:17 in reply to: ↑ 15 ; follow-up: Changed 7 years ago by muks

  • Owner changed from muks to vorner

Hi Michal

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

    /// \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:

        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?

        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.

    // 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:

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.

        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?

    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.

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

comment:18 in reply to: ↑ 16 Changed 7 years ago by muks

Replying to muks:

I'm blocked on fixing this ticket as I need clarification on whether empty nodes are to be deleted upwards in the forest if the DomainTree is constructed to return empty nodes. In this case, its constructor argument name would also likely have to be changed as it's very find()-specific currently.

Just removing empty nodes at the tree can also get rid of intentionally added empty nodes, so this needs clarification.

#2752 gives some additional details and seems to want this behavior (of cleaning up empty nodes upwards).

comment:19 in reply to: ↑ 17 Changed 7 years ago by vorner

  • Owner changed from vorner to muks

Hello

Replying to muks:

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?

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

That s would indeed be an improvement. Or something like connectChild?

This seems to be unconditional. Is that OK?

        other->setParentChild(this, other, root_ptr);

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

I'm not sure something is wrong. But this sets the parent's child without any condition. Is it possible the lower might not be direct child of root_ptr in the modified tree? If not, why?

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?

The point is exactly the same as abstractAccessorImpl. I don't think we need the findImpl wrappers, these can be skipped and the resulting tree->find called directly. These are private.

I think this was copy-pasted so many times someone (not necessarily
you) lost the explicit root mentioned in the comment.

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

But then, would it say /explicit/ root there? The root node is implicit in this list.

comment:20 follow-up: Changed 7 years ago by vorner

Ah, also this one. Would it make sense to switch the condition to positive one, for readability?

        if (!node->getRight()) {
            child = node->getLeft();
        } else {
            child = node->getRight();
        }

comment:21 in reply to: ↑ 20 ; follow-up: Changed 7 years ago by muks

  • Owner changed from muks to vorner

Hi Michal

Replying to vorner:

Replying to muks:

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?

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

That s would indeed be an improvement. Or something like connectChild?

I've changed it to connectChild() now.

This seems to be unconditional. Is that OK?

        other->setParentChild(this, other, root_ptr);

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

I'm not sure something is wrong. But this sets the parent's child
without any condition. Is it possible the lower might not be direct
child of root_ptr in the modified tree? If not, why?

I'm sorry I'm still not following it. As lower takes the place of
this, it connects the parent's corresponding child ptr (either
left_, right_ or down_ as the case may be) that used to point to
this to point to lower.

Definitely lower may not be direct child of root_ptr (root_ptr
points to the root of the whole forest). In connectChild(), if the
initial lower->getParent() returns NULL, it means that the other
node (this in exchange()) being exchanged with lower was the root
node, and now, lower must become the new root node.

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?

The point is exactly the same as abstractAccessorImpl. I don't think
we need the findImpl wrappers, these can be skipped and the
resulting tree->find called directly. These are private.

These have been updated.

I think this was copy-pasted so many times someone (not necessarily
you) lost the explicit root mentioned in the comment.

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

But then, would it say /explicit/ root there? The root node is
implicit in this list.

Do you see the difference between:

// The full absolute names of the nodes in the tree.
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"
};


and:

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


This is why I think nothing needs to be changed here.

Replying to vorner:

Ah, also this one. Would it make sense to switch the condition to
positive one, for readability?

        if (!node->getRight()) {
            child = node->getLeft();
        } else {
            child = node->getRight();
        }

Updated. :)

I've checked that clang++ on FreeBSD builder (that used to fail
before) now passes. It also passes on my local workstation with
clang++ (with additional changes from #3172, but this is not required
for our builders that use older versions of this compiler).

I'll put #3172 to review individually, but if you want to check with
clang++ on your workstation, please merge trac3172 and try it.

comment:22 in reply to: ↑ 21 ; follow-up: Changed 6 years ago by vorner

  • Owner changed from vorner to muks

Hello

Replying to muks:

Definitely lower may not be direct child of root_ptr (root_ptr
points to the root of the whole forest). In connectChild(), if the
initial lower->getParent() returns NULL, it means that the other
node (this in exchange()) being exchanged with lower was the root
node, and now, lower must become the new root node.

Hmm. Probably I'm just confused. The tests are there, so it must work O:-).

Do you see the difference between:

// The full absolute names of the nodes in the tree.
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"
};


and:

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


This is why I think nothing needs to be changed here.

I see the difference. And that's exactly why I think it is confusing. Explicit addition into what? The list? The list does not contain it at all.

What about changing it to something like „The full absolute nodes of the tree (the tree also contains ".", which is not included in this list)“?

I'll put #3172 to review individually, but if you want to check with
clang++ on your workstation, please merge trac3172 and try it.

I can't ☹. I didn't manage to make clang++ work on my system. Every time, it complained about some libraries. But, well, whatever…

I think the branch is good enough for merge.

comment:23 in reply to: ↑ 22 Changed 6 years ago by muks

  • Resolution set to fixed
  • Status changed from reviewing to closed

Merged to master branch in commit d3dbe8e1643358d4f88cdbb7a16a32fd384b85b1:

* 08bc7db [2750] Reduce another layer of find() wrapper
* a0aaef8 [2750] Reduce the number of find() wrappers
* bd9f2d3 [2750] Rename method
* 52d44bc [2750] Invert condition statement, swapping respective blocks
* 339f201 [2750] Re-indent code
* 8b88f18 [2750] Add a test that does a remove() on tree with empty upper nodes
* b1e65b9 [2750] Add some more checks and comments to .remove test
* c5c85a0 [2750] Don't delete nodes with down pointers
* d79db92 [2750] Handle root of forest case too
* 3984b23 [2750] exchange() nodes only when node to be removed has both children
* 0edf1c3 [2750] Check that sub-tree roots have the flag set
* 9eeab2e [2750] Remove excess wrapper methods
* 63a7f8b [2750] Add comments in exchange() about asymmetric code
* 8090d2c [2750] Rename variable to lower
* 05b3886 [2750] Introduce getSibling() again as a static function
* 151a2b8 [2750] Use std::max()
* a47c17e [2750] Remove node fusion functionality completely
* a50e423 [2750] Fix typo
* 663bc38 [2750] Test the passed set instead of the tree (true at the end of the unittest)
* 49c7199 [2750] Simplify code
* 0a5bd2e [2750] Increase number of nodes to 1024
* 8380acd [2750] Remove some temporary tests
* c0e91c5 [2750] Add comprehensive test for DomainTree validity with insert() and remove()
* b30ae17 [2750] Add a comment describing the test
* e2cb0a3 [2750] Move the RNG to a class variable (so the same RNG can be reused)
* 63e54b1 [2750] Add methods to check RB tree properties (and use them in tests)
* da0e9a8 [2750] Replace height check with getHeight() method
* b403553 [2750] Use more optimal form of color testing where possible
* 49fa0ba [2750] Finish documenting the red-black tree remove rebalance operation
* 7cf3929 [2750] Remove redundant part of condition
* 0467d75 [2750] Add/update RB tree delete rebalancing comments
* 6024678 [2750] Rewrite code to use a similar block as previous case
* 967e79e [2750] Fix tree rotation direction
* ec1cb0b [2750] Remove redundant NULL test
* 1d38fe3 [2750] Reduce code by using getColor()
* 4ee1f33 [2750] Remove redundant condition to check if sibling is black
* d15a492 [2750] Update comment
* 313c564 [2750] Fix overall loop condition in removeRebalance()
* 8a4c8c4 [2750] Add graphs for case 3
* 091b858 [2750] Make various updates (see full log)
* 2a07912 [2750] Update some checks
* 275d632 [2750] Recompute sibling after rotations
* 23078e9 [2750] Remove redundant argument
* 73d7a95 [2750] Simplify condition
* 927411d [2750] Add comments for rebalancing code in remove()
* b6ca9a8 [2750] Add code comments
* 4798d92 [2750] Re-arrange find() methods so that protos come before uses
* 8829d94 [2750] Add documentation
* bf29846 [2750] Check that having 2 nodes in subtree doesn't cause node fusion
* 8a6e0a6 [2750] Update comment
* 65d3cd2 [2750] Test multiple occurrences of node fusion in a single step upwards in the forest
* 82fded3 [2750] Add node fusion test where there is data in the parent node
* 4d5859d [2750] Add node fusion tests
* 99b2d6f [2750] Add a first proper remove() unittest
* 31e8258 [2750] Unify copies of test data
* 1d32d63 [2750] Add initial delete rebalance implementation
* b27c26f [2750] Move common code into a helper method
* 9801de5 [2750] Simplify the code to set the parent-child relationship
* a2bc0e2 [2750] Set the new node's down pointer too
* 8bda455 [2750] Simplify code somewhat
* 6be8194 [2750] Add remove() and tryNodeFusion() implementations
* 038082d [2750] Adjust more pointers to make the exchange complete
* 9184190 [2750] Adjust a few more pointers to make the exchange complete
* 7b722a2 [2750] Add a comment about why down_ is not swapped
* 730aac8 [2750] Start to remove() with initial exchange with a leaf node
* 5ffd53d [2750] Add non-const variants of more find() methods
* 7025053 [2750] Make public method names consistent
* 7f0bb92 [2750] Add getSibling() method
* c369c2c [2750] Add proto for a method to delete a tree node
* 3674f82 [2750] Fix indent level
* 79c66d3 [2750] Add non-const variant of find()
* 9b06e69 [2750] Add non-const variant of largestNode()
* 0b3041d [2750] Add non-const variants of successor() and predecessor()
* 36db9cb [2750] Remove redundant variable
* 4d4b0dc [2750] Add non-const variant of abstractSuccessor()
* 004adb2 [2750] Add non-const variant of getUpperNode()
* 8ee0490 [2750] Add non-const variant of getSubTreeRoot()

Replying to vorner:

What about changing it to something like „The full absolute nodes of the tree (the tree also contains ".", which is not included in this list)“?

This has been changed in commit bb0ac07b4621308695146918e37d4f2a68e2a9bd on the master branch.

The following ChangeLog message was pushed for #2750 and #2751 in commit acbe4afb25b5f7eb6da8e259d9d8a78526bccd80 on the master branch:

+684.   [func]          muks, vorner
+       API support to delete zone data has been added. With this,
+       DomainTree and RdataSet which form the central zone data
+       structures of b10-auth allow deletion of names and RR data
+       respectively.
+       (Trac #2750, git d3dbe8e1643358d4f88cdbb7a16a32fd384b85b1)
+       (Trac #2751, git 7430591b4ae4c7052cab86ed17d0221db3b524a8)
+

Resolving as fixed. Thank you for the reviews Michal.

Note: See TracTickets for help on using tickets.