BIND 10 trac2750, updated. 8bda455d6c105e505ed0d11223c708e2bd3b6f7a [2750] Simplify code somewhat
BIND 10 source code commits
bind10-changes at lists.isc.org
Tue Aug 27 06:02:09 UTC 2013
The branch, trac2750 has been updated
via 8bda455d6c105e505ed0d11223c708e2bd3b6f7a (commit)
via 6be8194bd8c4dc90dc0b702ba1450e59184689a5 (commit)
from 038082d3a8df1904538a11a6b803bec1804f9c8b (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 8bda455d6c105e505ed0d11223c708e2bd3b6f7a
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Aug 27 11:29:13 2013 +0530
[2750] Simplify code somewhat
commit 6be8194bd8c4dc90dc0b702ba1450e59184689a5
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Aug 27 11:18:32 2013 +0530
[2750] Add remove() and tryNodeFusion() implementations
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 206 +++++++++++++++++---
.../datasrc/tests/memory/domaintree_unittest.cc | 9 +-
2 files changed, 190 insertions(+), 25 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 4887042..b091c67 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -631,7 +631,7 @@ private:
/// std::swap()-like behavior.
///
/// This method doesn't throw any exceptions.
- void exchange(DomainTreeNode<T>* other, DomainTreeNodePtr* subtree_root) {
+ void exchange(DomainTreeNode<T>* other, DomainTreeNodePtr* root_ptr) {
// Swap the pointers first. down should not be swapped as it
// belongs to the node's data, and not to its position in the
// tree.
@@ -672,18 +672,16 @@ private:
setSubTreeRoot(other_is_subtree_root);
other->setSubTreeRoot(this_is_subtree_root);
- if (other->isSubTreeRoot()) {
- if (other->getParent()) {
- other->getParent()->down_ = other;
- } else {
- *subtree_root = other;
- }
- } else {
+ if (other->getParent() != NULL) {
if (other->getParent()->getLeft() == this) {
other->getParent()->left_ = other;
} else if (other->getParent()->getRight() == this) {
other->getParent()->right_ = other;
+ } else {
+ other->getParent()->down_ = other;
}
+ } else {
+ *root_ptr = other;
}
if (getParent()->getLeft() == other) {
@@ -1723,6 +1721,10 @@ private:
insertRebalance(typename DomainTreeNode<T>::DomainTreeNodePtr* root,
DomainTreeNode<T>* node);
+ void
+ removeRebalance(typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr,
+ DomainTreeNode<T>* child, DomainTreeNode<T>* parent);
+
DomainTreeNode<T>*
rightRotate(typename DomainTreeNode<T>::DomainTreeNodePtr* root,
DomainTreeNode<T>* node);
@@ -1761,6 +1763,12 @@ private:
void nodeFission(util::MemorySegment& mem_sgmt, DomainTreeNode<T>& node,
const isc::dns::LabelSequence& new_prefix,
const isc::dns::LabelSequence& new_suffix);
+
+ /// Try to combine the upper node and its down node into one node,
+ /// deleting the parent in the process.
+ void tryNodeFusion(util::MemorySegment& mem_sgmt,
+ DomainTreeNode<T>* upper_node);
+
//@}
typename DomainTreeNode<T>::DomainTreeNodePtr root_;
@@ -2234,20 +2242,20 @@ DomainTree<T>::insert(util::MemorySegment& mem_sgmt,
template <typename T>
template <typename DataDeleter>
void
-DomainTree<T>::remove(util::MemorySegment&, DomainTreeNode<T>* node,
- DataDeleter)
+DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
+ DataDeleter deleter)
{
- assert(node != NULL);
-
- // node points to the node to be deleted. But unless it's a leaf
- // node, 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 becomes a leaf
- // node. Note that this is not an in-place value swap of node data,
- // but the actual node locations are swapped. Unlike normal BSTs, we
- // have to do this as our label data is at address (this + 1).
-
+ // Save subtree root's parent for use later.
+ DomainTreeNode<T>* upper_node = node->getUpperNode();
+
+ // node points to the node to be deleted. 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) {
@@ -2264,7 +2272,56 @@ DomainTree<T>::remove(util::MemorySegment&, DomainTreeNode<T>* node,
node->exchange(leftmost, &root_);
}
- // Now, node is a leaf node.
+ // 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();
+ }
+
+ // Set it as the node's parent's child, effectively removing node
+ // from the tree.
+ if (node->isSubTreeRoot()) {
+ // In this case, node is the only node in this forest sub-tree.
+ typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr =
+ node->getParent() ? &(node->getParent()->down_) : &root_;
+ *root_ptr = NULL;
+ } else {
+ if (node->getParent()->getLeft() == node) {
+ node->getParent()->left_ = child;
+ } else {
+ node->getParent()->right_ = child;
+ }
+
+ if (child) {
+ child->parent_ = node->getParent();
+ }
+
+ if (node->isBlack()) {
+ if (child && child->isRed()) {
+ child->setColor(DomainTreeNode<T>::BLACK);
+ } else {
+ typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr =
+ node->getParent() ? &(node->getParent()->down_) : &root_;
+ removeRebalance(root_ptr, child, node->getParent());
+ }
+ }
+ }
+
+ // If node has a subtree under it, delete it too.
+ if (node->getDown()) {
+ node->getDown()->parent_ = NULL;
+ deleteHelper(mem_sgmt, node->getDown(), deleter);
+ }
+
+ tryNodeFusion(mem_sgmt, upper_node);
+
+ deleter(node->data_.get());
+ DomainTreeNode<T>::destroy(mem_sgmt, node);
+ --node_count_;
}
template <typename T>
@@ -2279,6 +2336,104 @@ DomainTree<T>::removeAllNodes(util::MemorySegment& mem_sgmt,
template <typename T>
void
+DomainTree<T>::tryNodeFusion(util::MemorySegment& mem_sgmt,
+ DomainTreeNode<T>* upper_node)
+{
+ 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 and it cannot can be fused.
+ if (subtree_root->getLeft() || subtree_root->getRight()) {
+ break;
+ }
+
+ // If the upper node is not empty, fusion cannot be done.
+ if (!upper_node->isEmpty()) {
+ break;
+ }
+
+ uint8_t buf[isc::dns::LabelSequence::MAX_SERIALIZED_LENGTH];
+ isc::dns::LabelSequence ls(subtree_root->getLabels(), buf);
+ ls.extend(upper_node->getLabels(), buf);
+
+ DomainTreeNode<T>* new_node = DomainTreeNode<T>::create(mem_sgmt, ls);
+
+ new_node->parent_ = upper_node->getParent();
+ if (upper_node->getParent() != NULL) {
+ if (upper_node->getParent()->getLeft() == upper_node) {
+ new_node->getParent()->left_ = new_node;
+ } else if (upper_node->getParent()->getRight() == upper_node) {
+ new_node->getParent()->right_ = new_node;
+ } else {
+ new_node->getParent()->down_ = new_node;
+ }
+ } else {
+ 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;
+ }
+
+ if (upper_node->isRed()) {
+ new_node->setColor(DomainTreeNode<T>::RED);
+ } else {
+ new_node->setColor(DomainTreeNode<T>::BLACK);
+ }
+
+ new_node->setSubTreeRoot(upper_node->isSubTreeRoot());
+
+ // Set new_node's flags
+ 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));
+
+ // Set new_node's data
+ T* data = subtree_root->setData(NULL);
+ new_node->setData(data);
+
+ // Delete the old nodes.
+ 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,
@@ -2473,6 +2628,13 @@ DomainTree<T>::insertRebalance
(*subtree_root)->setColor(DomainTreeNode<T>::BLACK);
}
+template <typename T>
+void
+DomainTree<T>::removeRebalance
+ (typename DomainTreeNode<T>::DomainTreeNodePtr*,
+ DomainTreeNode<T>*, DomainTreeNode<T>*)
+{
+}
template <typename T>
DomainTreeNode<T>*
diff --git a/src/lib/datasrc/tests/memory/domaintree_unittest.cc b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
index 4ac86ec..1628b48 100644
--- a/src/lib/datasrc/tests/memory/domaintree_unittest.cc
+++ b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
@@ -347,13 +347,16 @@ TEST_F(DomainTreeTest, insertNames) {
}
TEST_F(DomainTreeTest, remove) {
- EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name("b"), &dtnode));
-
ofstream o1("d1.dot");
dtree_expose_empty_node.dumpDot(o1);
o1.close();
+ 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);
+
+ 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);
ofstream o2("d2.dot");
More information about the bind10-changes
mailing list