BIND 10 trac2750, updated. 339f201e9a6c58980f8cc9e6577e80254f04e951 [2750] Re-indent code
BIND 10 source code commits
bind10-changes at lists.isc.org
Fri Sep 13 10:01:29 UTC 2013
The branch, trac2750 has been updated
via 339f201e9a6c58980f8cc9e6577e80254f04e951 (commit)
via 8b88f186238c9dc920a3a4dac668c8e5bf68927b (commit)
via b1e65b902324572544555903b45bc63ffcefcd2b (commit)
via c5c85a0d56fc30c9c0fc3b7040306360c961350b (commit)
from d79db92249d8e529bd8346cffbaf5c19680923f5 (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 339f201e9a6c58980f8cc9e6577e80254f04e951
Author: Mukund Sivaraman <muks at isc.org>
Date: Fri Sep 13 15:31:05 2013 +0530
[2750] Re-indent code
commit 8b88f186238c9dc920a3a4dac668c8e5bf68927b
Author: Mukund Sivaraman <muks at isc.org>
Date: Fri Sep 13 15:30:55 2013 +0530
[2750] Add a test that does a remove() on tree with empty upper nodes
commit b1e65b902324572544555903b45bc63ffcefcd2b
Author: Mukund Sivaraman <muks at isc.org>
Date: Fri Sep 13 15:30:28 2013 +0530
[2750] Add some more checks and comments to .remove test
commit c5c85a0d56fc30c9c0fc3b7040306360c961350b
Author: Mukund Sivaraman <muks at isc.org>
Date: Fri Sep 13 14:58:55 2013 +0530
[2750] Don't delete nodes with down pointers
With this mind, also clean up any empty upper nodes and
rebalance their trees if necessary.
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 173 ++++++++++++--------
.../datasrc/tests/memory/domaintree_unittest.cc | 140 ++++++++++++++--
2 files changed, 228 insertions(+), 85 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index f7ab4ea..aa29828 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -2282,87 +2282,118 @@ void
DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
DataDeleter deleter)
{
- // Save subtree root's parent for use later.
- DomainTreeNode<T>* upper_node = node->getUpperNode();
-
- // 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() && node->getRight()) {
- DomainTreeNode<T>* rightmost = node->getLeft();
- while (rightmost->getRight() != NULL) {
- rightmost = rightmost->getRight();
+ // If node has a down pointer, we cannot remove this node from the
+ // DomainTree forest. We merely clear its data (destroying the data)
+ // and return.
+ if (node->getDown()) {
+ T* data = node->setData(NULL);
+ if (data) {
+ deleter(data);
}
-
- node->exchange(rightmost, &root_);
- }
-
- // Now, node has 0 or 1 children, as from above, either its right or
- // left child definitely doesn't exist (and is NULL). Pick the
- // child node, or if no children exist, just use NULL.
- DomainTreeNode<T>* child;
- if (!node->getRight()) {
- child = node->getLeft();
- } else {
- child = node->getRight();
+ return;
}
- // Set it as the node's parent's child, effectively removing node
- // from the tree.
- node->setParentChild(node, child, &root_);
+ while (true) {
+ // Save subtree root's parent for use later.
+ DomainTreeNode<T>* upper_node = node->getUpperNode();
+
+ // 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() && node->getRight()) {
+ DomainTreeNode<T>* rightmost = node->getLeft();
+ while (rightmost->getRight() != NULL) {
+ rightmost = rightmost->getRight();
+ }
- // 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());
+ node->exchange(rightmost, &root_);
}
- }
- // 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);
+ // Now, node has 0 or 1 children, as from above, either its
+ // right or left child definitely doesn't exist (and is NULL).
+ // Pick the child node, or if no children exist, just use NULL.
+ DomainTreeNode<T>* child;
+ if (!node->getRight()) {
+ child = node->getLeft();
} 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());
+ child = node->getRight();
}
- }
- // If node has a sub red-black tree under it (down_ pointer), delete
- // it too. Here, we can use the simple subtree form of delete.
- if (node->getDown()) {
- node->getDown()->parent_ = NULL;
- deleteHelper(mem_sgmt, node->getDown(), deleter);
- }
+ // Set it as the node's parent's child, effectively removing
+ // node from the tree.
+ node->setParentChild(node, child, &root_);
+
+ // 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) 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());
+ }
+ }
+
+ // Finally, destroy the node.
+ if (node->data_.get()) {
+ deleter(node->data_.get());
+ }
+ DomainTreeNode<T>::destroy(mem_sgmt, node);
+ --node_count_;
+
+ // If the node deletion did not cause the subtree to disappear
+ // completely, return early.
+ if (upper_node->getDown()) {
+ break;
+ }
+
+ // If the upper node is not empty, it cannot be deleted.
+ if (!upper_node->isEmpty()) {
+ break;
+ }
- // Finally, destroy the node.
- deleter(node->data_.get());
- DomainTreeNode<T>::destroy(mem_sgmt, node);
- --node_count_;
+ // If upper node is the root node (.), don't attempt to delete
+ // it. The root node must always exist.
+ if (upper_node == root_.get()) {
+ break;
+ }
+
+ // Ascend up the tree and delete the upper node.
+ node = upper_node;
+ }
}
template <typename T>
diff --git a/src/lib/datasrc/tests/memory/domaintree_unittest.cc b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
index 6c12e70..0d8159b 100644
--- a/src/lib/datasrc/tests/memory/domaintree_unittest.cc
+++ b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
@@ -141,8 +141,8 @@ class DomainTreeTest : public::testing::Test {
protected:
DomainTreeTest() :
dtree_holder_(mem_sgmt_, TestDomainTree::create(mem_sgmt_)),
- dtree_expose_empty_node_holder_(mem_sgmt_,
- TestDomainTree::create(mem_sgmt_, true)),
+ dtree_expose_empty_node_holder_
+ (mem_sgmt_, TestDomainTree::create(mem_sgmt_, true)),
dtree(*dtree_holder_.get()),
dtree_expose_empty_node(*dtree_expose_empty_node_holder_.get()),
cdtnode(NULL),
@@ -390,7 +390,8 @@ TEST_F(DomainTreeTest, remove) {
// This testcase checks that after node removal, the binary-search
// tree is valid and all nodes that are supposed to exist are
// present in the correct order. It mainly tests DomainTree as a
- // BST, and not particularly as a red-black tree.
+ // BST, and not particularly as a red-black tree. This test checks
+ // node deletion when upper nodes have data.
// Delete single nodes and check if the rest of the nodes exist
for (int j = 0; j < ordered_names_count; ++j) {
@@ -405,8 +406,9 @@ TEST_F(DomainTreeTest, remove) {
for (int i = 0; i < ordered_names_count; ++i) {
EXPECT_EQ(TestDomainTree::EXACTMATCH,
tree.find(Name(ordered_names[i]), &node));
- EXPECT_EQ(static_cast<int*>(NULL),
- node->setData(new int(i)));
+ // Check nodes are not empty.
+ EXPECT_EQ(static_cast<int*>(NULL), node->setData(new int(i)));
+ EXPECT_FALSE(node->isEmpty());
}
// Now, delete the j'th node from the tree.
@@ -415,7 +417,7 @@ TEST_F(DomainTreeTest, remove) {
tree.remove(mem_sgmt_, node, deleteData);
// Check RB tree properties
- EXPECT_TRUE(tree.checkProperties());
+ ASSERT_TRUE(tree.checkProperties());
// Now, walk through nodes in order.
TestDomainTreeNodeChain node_path;
@@ -438,25 +440,135 @@ TEST_F(DomainTreeTest, remove) {
}
for (int i = start_node; i < ordered_names_count; ++i) {
- // If a superdomain is deleted, everything under that
- // sub-tree goes away.
const Name nj(ordered_names[j]);
const Name ni(ordered_names[i]);
- const NameComparisonResult result = nj.compare(ni);
- if ((result.getRelation() == NameComparisonResult::EQUAL) ||
- (result.getRelation() == NameComparisonResult::SUPERDOMAIN)) {
+
+ if (ni == nj) {
+ // This may be true for the last node if we seek ahead
+ // in the loop using nextNode() below.
+ if (!cnode) {
+ break;
+ }
+ // All ordered nodes have data initially. If any node is
+ // empty, it means it was remove()d, but an empty node
+ // exists because it is a super-domain. Just skip it.
+ if (cnode->isEmpty()) {
+ cnode = tree.nextNode(node_path);
+ }
continue;
}
- EXPECT_NE(static_cast<void*>(NULL), cnode);
+ ASSERT_NE(static_cast<void*>(NULL), cnode);
const int* data = cnode->getData();
- EXPECT_EQ(i, *data);
+
+ if (data) {
+ EXPECT_EQ(i, *data);
+ }
+
+ uint8_t buf[isc::dns::LabelSequence::MAX_SERIALIZED_LENGTH];
+ const LabelSequence ls(cnode->getAbsoluteLabels(buf));
+ EXPECT_EQ(LabelSequence(ni), ls);
cnode = tree.nextNode(node_path);
}
// We should have reached the end of the tree.
- EXPECT_EQ(static_cast<void*>(NULL), cnode);
+ ASSERT_EQ(static_cast<void*>(NULL), cnode);
+ }
+}
+
+TEST_F(DomainTreeTest, removeEmpty) {
+ // This test is similar to the .remove test. But it checks node
+ // deletion when upper nodes are empty.
+
+ // Delete single nodes and check if the rest of the nodes exist
+ for (int j = 0; j < ordered_names_count; ++j) {
+ TreeHolder holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_, true));
+ TestDomainTree& tree(*holder.get());
+ TestDomainTreeNode* node;
+
+ for (int i = 0; i < name_count; ++i) {
+ tree.insert(mem_sgmt_, Name(domain_names[i]), NULL);
+ }
+
+ for (int i = 0; i < ordered_names_count; ++i) {
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[i]), &node));
+ // Check nodes are empty.
+ EXPECT_TRUE(node->isEmpty());
+ }
+
+ // Now, delete the j'th node from the tree.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[j]), &node));
+ tree.remove(mem_sgmt_, node, deleteData);
+
+ // Check RB tree properties
+ ASSERT_TRUE(tree.checkProperties());
+
+ // Now, walk through nodes in order.
+ TestDomainTreeNodeChain node_path;
+ const TestDomainTreeNode* cnode;
+ int start_node;
+
+ if (j == 0) {
+ EXPECT_NE(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[0]),
+ &cnode));
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[1]),
+ &cnode, node_path));
+ start_node = 1;
+ } else {
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[0]),
+ &cnode, node_path));
+ start_node = 0;
+ }
+
+ for (int i = start_node; i < ordered_names_count; ++i) {
+ const Name nj(ordered_names[j]);
+ const Name ni(ordered_names[i]);
+
+ if ((nj == Name("j.z.d.e.f")) &&
+ (ni == Name("z.d.e.f")))
+ {
+ // The only special case in the tree. Here, "z.d.e.f"
+ // will not exist as it would have been removed during
+ // removal of "j.z.d.e.f".
+ continue;
+ }
+
+ if (ni == nj) {
+ // This may be true for the last node if we seek ahead
+ // in the loop using nextNode() below.
+ if (!cnode) {
+ break;
+ }
+ // All ordered nodes are empty initially. If an empty
+ // removed node exists because it is a super-domain,
+ // just skip it.
+ if ((nj == Name("d.e.f")) ||
+ (nj == Name("w.y.d.e.f")) ||
+ (nj == Name("z.d.e.f")) ||
+ (nj == Name("g.h")))
+ {
+ cnode = tree.nextNode(node_path);
+ }
+ continue;
+ }
+
+ ASSERT_NE(static_cast<void*>(NULL), cnode);
+
+ uint8_t buf[isc::dns::LabelSequence::MAX_SERIALIZED_LENGTH];
+ const LabelSequence ls(cnode->getAbsoluteLabels(buf));
+ EXPECT_EQ(LabelSequence(ni), ls);
+
+ cnode = tree.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ ASSERT_EQ(static_cast<void*>(NULL), cnode);
}
}
More information about the bind10-changes
mailing list