BIND 10 trac2750, updated. a47c17e54da2b08afb9dae8f46a97ac3a5e5bda0 [2750] Remove node fusion functionality completely
BIND 10 source code commits
bind10-changes at lists.isc.org
Thu Sep 5 14:10:55 UTC 2013
The branch, trac2750 has been updated
via a47c17e54da2b08afb9dae8f46a97ac3a5e5bda0 (commit)
from a50e4235990f2b1b7090092e5fb19c7662480dd3 (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 a47c17e54da2b08afb9dae8f46a97ac3a5e5bda0
Author: Mukund Sivaraman <muks at isc.org>
Date: Thu Sep 5 19:40:06 2013 +0530
[2750] Remove node fusion functionality completely
... as discussed on the bind10-dev@ mailing list.
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 125 ---------
.../datasrc/tests/memory/domaintree_unittest.cc | 271 --------------------
2 files changed, 396 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 7372530..14faaf9 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -1695,16 +1695,6 @@ public:
/// \brief Delete a tree node.
///
- /// When a node is deleted, a process called node fusion occurs
- /// where nodes that satisfy some conditions are combined together
- /// into a new node, and the old nodes are deleted from the
- /// tree. From the DomainTree user's perspective, such node fusion
- /// will not cause any disturbance in the content of the DomainTree
- /// itself, but any existing pointers that the user code contains to
- /// DomainTreeNodes may be invalidated. In this case, the user code
- /// is required to re-lookup the node using \c find() and other seek
- /// methods.
- ///
/// \throw none.
///
/// \param mem_sgmt The \c MemorySegment object used to insert the nodes
@@ -1793,14 +1783,6 @@ private:
const isc::dns::LabelSequence& new_prefix,
const isc::dns::LabelSequence& new_suffix);
- /// Try to replace the upper node and its down node into a single
- /// new node, deleting the old nodes in the process. This happens
- /// iteratively up the tree until no pair of nodes can be fused
- /// anymore. Note that after deletion operation, a pointer to a node
- /// may be invalid.
- void tryNodeFusion(util::MemorySegment& mem_sgmt,
- DomainTreeNode<T>* upper_node);
-
//@}
typename DomainTreeNode<T>::DomainTreeNodePtr root_;
@@ -2384,8 +2366,6 @@ DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
deleteHelper(mem_sgmt, node->getDown(), deleter);
}
- tryNodeFusion(mem_sgmt, upper_node);
-
// Finally, destroy the node.
deleter(node->data_.get());
DomainTreeNode<T>::destroy(mem_sgmt, node);
@@ -2404,111 +2384,6 @@ DomainTree<T>::removeAllNodes(util::MemorySegment& mem_sgmt,
template <typename T>
void
-DomainTree<T>::tryNodeFusion(util::MemorySegment& mem_sgmt,
- DomainTreeNode<T>* upper_node)
-{
- // Keep doing node fusion up the tree until it's no longer possible.
- while (upper_node) {
- DomainTreeNode<T>* subtree_root = upper_node->getDown();
-
- // If the node deletion caused the subtree root to disappear
- // completely, return early.
- if (!subtree_root) {
- if (upper_node->isSubTreeRoot()) {
- upper_node = upper_node->getParent();
- continue;
- } else {
- break;
- }
- }
-
- // If the subtree root has left or right children, the subtree
- // has more than 1 nodes, so fusion cannot be done.
- if (subtree_root->getLeft() || subtree_root->getRight()) {
- break;
- }
-
- // If the upper node is not empty, fusion cannot be done.
- if (!upper_node->isEmpty()) {
- break;
- }
-
- // If upper node is the root node (.), don't attempt node fusion
- // with it. The root node must always exist.
- if (upper_node == root_.get()) {
- break;
- }
-
- // Create a new label sequence with (subtree_root+upper_node)
- // labels.
- uint8_t buf[isc::dns::LabelSequence::MAX_SERIALIZED_LENGTH];
- isc::dns::LabelSequence ls(subtree_root->getLabels(), buf);
- ls.extend(upper_node->getLabels(), buf);
-
- // We create a new node to replace subtree_root and
- // upper_node. subtree_root and upper_node will be deleted at
- // the end.
- DomainTreeNode<T>* new_node = DomainTreeNode<T>::create(mem_sgmt, ls);
-
- new_node->parent_ = upper_node->getParent();
-
- upper_node->setParentChild(upper_node, new_node, &root_, new_node);
-
- new_node->left_ = upper_node->getLeft();
- if (new_node->getLeft() != NULL) {
- new_node->getLeft()->parent_ = new_node;
- }
-
- new_node->right_ = upper_node->getRight();
- if (new_node->getRight() != NULL) {
- new_node->getRight()->parent_ = new_node;
- }
-
- new_node->down_ = subtree_root->getDown();
- if (new_node->getDown() != NULL) {
- new_node->getDown()->parent_ = new_node;
- }
-
- // The color of the new node is the same as the upper node's.
- new_node->setColor(upper_node->getColor());
-
- new_node->setSubTreeRoot(upper_node->isSubTreeRoot());
-
- // The flags of the new node are the same as the upper node's.
- new_node->setFlag(DomainTreeNode<T>::FLAG_CALLBACK,
- upper_node->getFlag(DomainTreeNode<T>::FLAG_CALLBACK));
- new_node->setFlag(DomainTreeNode<T>::FLAG_USER1,
- upper_node->getFlag(DomainTreeNode<T>::FLAG_USER1));
- new_node->setFlag(DomainTreeNode<T>::FLAG_USER2,
- upper_node->getFlag(DomainTreeNode<T>::FLAG_USER2));
- new_node->setFlag(DomainTreeNode<T>::FLAG_USER3,
- upper_node->getFlag(DomainTreeNode<T>::FLAG_USER3));
-
- // The data on the new node is the same as the subtree
- // root's. Note that the upper node must be empty (contains no
- // data).
- T* data = subtree_root->setData(NULL);
- new_node->setData(data);
-
- // Destroy the old nodes (without destroying any data).
- DomainTreeNode<T>::destroy(mem_sgmt, upper_node);
- DomainTreeNode<T>::destroy(mem_sgmt, subtree_root);
-
- // We added 1 node and deleted 2.
- --node_count_;
-
- // Ascend one level up and iterate the whole process again if
- // the conditions exist to fuse more nodes.
- if (new_node->isSubTreeRoot()) {
- upper_node = new_node->getParent();
- } else {
- break;
- }
- }
-}
-
-template <typename T>
-void
DomainTree<T>::nodeFission(util::MemorySegment& mem_sgmt,
DomainTreeNode<T>& node,
const isc::dns::LabelSequence& new_prefix,
diff --git a/src/lib/datasrc/tests/memory/domaintree_unittest.cc b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
index c2b6003..6c12e70 100644
--- a/src/lib/datasrc/tests/memory/domaintree_unittest.cc
+++ b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
@@ -597,277 +597,6 @@ TEST_F(DomainTreeTest, insertAndRemove) {
checkTree(tree, names);
}
-TEST_F(DomainTreeTest, nodeFusion) {
- // Test that node fusion occurs when conditions permit.
-
- /* Original tree:
- * .
- * |
- * b
- * / \
- * a d.e.f
- * / | \
- * c | g.h
- * | |
- * w.y i
- * / | \ \
- * x | z k
- * | |
- * p j
- * / \
- * o q
- *
- */
-
- // First, check that "d.e.f" and "w.y" exist independently.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("d.e.f"), &cdtnode));
- EXPECT_EQ(Name("d.e.f"), cdtnode->getName());
-
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("w.y.d.e.f"), &cdtnode));
- EXPECT_EQ(Name("w.y"), cdtnode->getName());
-
- // Now, delete "x" node.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("x.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- // "d.e.f" should still exist independently as "w.y" still has a
- // left or right child.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("d.e.f"), &cdtnode));
- EXPECT_EQ(Name("d.e.f"), cdtnode->getName());
-
- // Now, delete "z" node.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("z.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- /* Deleting 'x' and 'z' should cause "w.y" to be fused with "d.e.f":
- * .
- * |
- * b
- * / \
- * a w.y.d.e.f
- * / | \
- * c | g.h
- * | |
- * p i
- * / \ \
- * o q k
- */
-
- // Check that "w.y" got fused with "d.e.f"
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("w.y.d.e.f"), &cdtnode));
- EXPECT_EQ(Name("w.y.d.e.f"), cdtnode->getName());
-
- // Check that "p" exists independently. This also checks that the
- // down pointer got saved correctly during the last fusion.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("p.w.y.d.e.f"), &cdtnode));
- EXPECT_EQ(Name("p"), cdtnode->getName());
-
- // Now, delete "o" and "q" nodes.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("o.w.y.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("q.w.y.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- /* Deleting 'o' and 'q' should cause "p" to be fused with "w.y.d.e.f":
- * .
- * |
- * b
- * / \
- * a p.w.y.d.e.f
- * / \
- * c g.h
- * |
- * i
- * \
- * k
- */
-
- // Check that "p" got fused with "w.y.d.e.f"
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("p.w.y.d.e.f"), &cdtnode));
- EXPECT_EQ(Name("p.w.y.d.e.f"), cdtnode->getName());
-}
-
-TEST_F(DomainTreeTest, nodeFusionWithData) {
- // Test that node fusion does not occur when there is data in the
- // parent node.
-
- /* Original tree:
- * .
- * |
- * b
- * / \
- * a d.e.f
- * / | \
- * c | g.h
- * | |
- * w.y i
- * / | \ \
- * x | z k
- * | |
- * p j
- * / \
- * o q
- *
- */
-
- // First, check that "d.e.f" and "w.y" exist independently.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("d.e.f"), &cdtnode));
- EXPECT_EQ(Name("d.e.f"), cdtnode->getName());
-
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("w.y.d.e.f"), &cdtnode));
- EXPECT_EQ(Name("w.y"), cdtnode->getName());
-
- // Set data (some value 42) in the "d.e.f" node
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("d.e.f"), &dtnode));
- EXPECT_EQ(static_cast<int*>(NULL),
- dtnode->setData(new int(42)));
-
- // Now, delete "x" and "z" nodes.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("x.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("z.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- /* Deleting 'x' and 'z' should not cause "w.y" to be fused with
- * "d.e.f" because "d.e.f" is not empty (has data) in this case.
- * .
- * |
- * b
- * / \
- * a d.e.f
- * / | \
- * c | g.h
- * | |
- * w.y i
- * | \
- * | k
- * |
- * p
- * / \
- * o q
- *
- */
-
- // Check that "w.y" did not get fused with "d.e.f"
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("d.e.f"), &cdtnode));
- EXPECT_EQ(Name("d.e.f"), cdtnode->getName());
-
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("w.y.d.e.f"), &cdtnode));
- EXPECT_EQ(Name("w.y"), cdtnode->getName());
-}
-
-TEST_F(DomainTreeTest, nodeFusionMultiple) {
- // Test that node fusion occurs up the tree multiple times when
- // conditions permit.
-
- /* Original tree:
- * .
- * |
- * b
- * / \
- * a d.e.f
- * / | \
- * c | g.h
- * | |
- * w.y i
- * / | \ \
- * x | z k
- * | |
- * p j
- * / \
- * o q
- *
- */
-
- // Set data (some value 42) in the "d.e.f" node
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("d.e.f"), &dtnode));
- EXPECT_EQ(static_cast<int*>(NULL),
- dtnode->setData(new int(42)));
-
- // Now, delete "x" and "z" nodes.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("x.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("z.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- /* Deleting 'x' and 'z' should not cause "w.y" to be fused with
- * "d.e.f" because "d.e.f" is not empty (has data) in this case.
- * .
- * |
- * b
- * / \
- * a d.e.f
- * / | \
- * c | g.h
- * | |
- * w.y i
- * | \
- * | k
- * |
- * p
- * / \
- * o q
- *
- */
-
- // Check that "w.y" did not get fused with "d.e.f"
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("d.e.f"), &cdtnode));
- EXPECT_EQ(Name("d.e.f"), cdtnode->getName());
-
- // Now, clear the data on "d.e.f". (Ideally, this itself should
- // cause fusion of "d.e.f" and "w.y" to occur, but we only do fusion
- // during deletion in our DomainTree implementation.)
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("d.e.f"), &dtnode));
- delete dtnode->setData(NULL);
-
- // Check that "p" exists independently.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("p.w.y.d.e.f"), &cdtnode));
- EXPECT_EQ(Name("p"), cdtnode->getName());
-
- // Now, delete "o" and "q" nodes.
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("o.w.y.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("q.w.y.d.e.f"), &dtnode));
- dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
-
- // The deletion of "o" and "q" should cause "p" to fuse with "w.y"
- // to form "p.w.y". Then, as "d.e.f" is now empty and conditions
- // permit, for a second time up the forest, "p.w.y" is fused with
- // "d.e.f" to form "p.w.y.d.e.f".
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("p.w.y.d.e.f"), &cdtnode));
- EXPECT_EQ(Name("p.w.y.d.e.f"), cdtnode->getName());
-}
-
TEST_F(DomainTreeTest, subTreeRoot) {
// This is a testcase for a particular issue that went unchecked in
// #2089's implementation, but was fixed in #2092. The issue was
More information about the bind10-changes
mailing list