BIND 10 trac2750, updated. 1d32d636d7f81e1a5385a9107fb7da355aa26c08 [2750] Add initial delete rebalance implementation
BIND 10 source code commits
bind10-changes at lists.isc.org
Thu Aug 29 03:39:59 UTC 2013
The branch, trac2750 has been updated
via 1d32d636d7f81e1a5385a9107fb7da355aa26c08 (commit)
via b27c26f22c147e9bfe4eaf411ce2247f5a5218e9 (commit)
via 9801de556f82d5c6156d120a2d70a23487524044 (commit)
from a2bc0e20d045d1009438c4c1565689931d66b213 (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 1d32d636d7f81e1a5385a9107fb7da355aa26c08
Author: Mukund Sivaraman <muks at isc.org>
Date: Thu Aug 29 08:57:42 2013 +0530
[2750] Add initial delete rebalance implementation
commit b27c26f22c147e9bfe4eaf411ce2247f5a5218e9
Author: Mukund Sivaraman <muks at isc.org>
Date: Thu Aug 29 08:57:10 2013 +0530
[2750] Move common code into a helper method
commit 9801de556f82d5c6156d120a2d70a23487524044
Author: Mukund Sivaraman <muks at isc.org>
Date: Thu Aug 29 08:29:30 2013 +0530
[2750] Simplify the code to set the parent-child relationship
Also fix bugs where:
* root_ was being set to NULL instead of child
* rebalance code was not always executed
* rebalance was wrongly stopping at node, instead of root of sub-tree
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 199 +++++++++++++-------
.../datasrc/tests/memory/domaintree_unittest.cc | 50 ++++-
2 files changed, 175 insertions(+), 74 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 536ba24..26aceb8 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -569,22 +569,6 @@ private:
}
}
- /// \brief Access sibling node as bare pointer.
- ///
- /// A sibling node is defined as the parent's other child. It exists
- /// at the same level as this node.
- ///
- /// \return the sibling node if one exists, NULL otherwise.
- DomainTreeNode<T>* getSibling() {
- DomainTreeNode<T>* parent = getParent();
-
- if (parent->getLeft() == this) {
- return (parent->getRight());
- } else {
- return (parent->getLeft());
- }
- }
-
/// \brief Access uncle node as bare pointer.
///
/// An uncle node is defined as the parent node's sibling. It exists
@@ -625,6 +609,30 @@ private:
return (down_.get());
}
+ /// \brief Helper method used in many places in code to set
+ /// parent-child links.
+ void setParentChild(DomainTreeNode<T>* oldnode,
+ DomainTreeNode<T>* newnode,
+ DomainTreeNodePtr* root_ptr,
+ DomainTreeNode<T>* thisnode = NULL)
+ {
+ if (!thisnode) {
+ thisnode = this;
+ }
+
+ if (getParent() != NULL) {
+ if (getParent()->getLeft() == oldnode) {
+ thisnode->getParent()->left_ = newnode;
+ } else if (getParent()->getRight() == oldnode) {
+ thisnode->getParent()->right_ = newnode;
+ } else {
+ thisnode->getParent()->down_ = newnode;
+ }
+ } else {
+ *root_ptr = newnode;
+ }
+ }
+
/// \brief Exchanges the location of two nodes. Their data remain
/// the same, but their location in the tree, colors and sub-tree
/// root status may change. Note that this is different from
@@ -672,17 +680,7 @@ private:
setSubTreeRoot(other_is_subtree_root);
other->setSubTreeRoot(this_is_subtree_root);
- 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;
- }
+ other->setParentChild(this, other, root_ptr);
if (getParent()->getLeft() == other) {
getParent()->left_ = this;
@@ -2284,30 +2282,19 @@ DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
// 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;
- }
+ node->setParentChild(node, child, &root_);
- if (child) {
- child->parent_ = node->getParent();
- }
+ 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->isBlack()) {
+ if (child && child->isRed()) {
+ child->setColor(DomainTreeNode<T>::BLACK);
+ } else {
+ typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr =
+ upper_node ? &(upper_node->down_) : &root_;
+ removeRebalance(root_ptr, child, node->getParent());
}
}
@@ -2371,17 +2358,8 @@ DomainTree<T>::tryNodeFusion(util::MemorySegment& mem_sgmt,
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;
- }
+
+ upper_node->setParentChild(upper_node, new_node, &root_, new_node);
new_node->left_ = upper_node->getLeft();
if (new_node->getLeft() != NULL) {
@@ -2454,17 +2432,8 @@ DomainTree<T>::nodeFission(util::MemorySegment& mem_sgmt,
node.resetLabels(new_prefix);
up_node->parent_ = node.getParent();
- if (node.getParent() != NULL) {
- if (node.getParent()->getLeft() == &node) {
- node.getParent()->left_ = up_node;
- } else if (node.getParent()->getRight() == &node) {
- node.getParent()->right_ = up_node;
- } else {
- node.getParent()->down_ = up_node;
- }
- } else {
- root_ = up_node;
- }
+
+ node.setParentChild(&node, up_node, &root_);
up_node->down_ = &node;
node.parent_ = up_node;
@@ -2636,9 +2605,93 @@ DomainTree<T>::insertRebalance
template <typename T>
void
DomainTree<T>::removeRebalance
- (typename DomainTreeNode<T>::DomainTreeNodePtr*,
- DomainTreeNode<T>*, DomainTreeNode<T>*)
+ (typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr,
+ DomainTreeNode<T>* child, DomainTreeNode<T>* parent)
{
+ while (parent != *root_ptr) {
+ // A sibling node is defined as the parent's other child. It
+ // exists at the same level as child. Note that child can be
+ // NULL here.
+ DomainTreeNode<T>* sibling = (parent->getLeft() == child) ?
+ parent->getRight() : parent->getLeft();
+
+ if (sibling && sibling->isRed()) {
+ parent->setColor(DomainTreeNode<T>::RED);
+ sibling->setColor(DomainTreeNode<T>::BLACK);
+ if (parent->getLeft() == child) {
+ leftRotate(root_ptr, parent);
+ } else {
+ rightRotate(root_ptr, parent);
+ }
+ }
+
+ // FIXME: Can sibling be NULL here?
+ if (parent->isBlack() &&
+ sibling->isBlack() &&
+ ((!sibling->getLeft()) || sibling->getLeft()->isBlack()) &&
+ ((!sibling->getRight()) || sibling->getRight()->isBlack()))
+ {
+ sibling->setColor(DomainTreeNode<T>::RED);
+ child = parent;
+ parent = parent->getParent();
+ continue;
+ }
+
+ // FIXME: Can sibling be NULL here?
+ if (parent->isRed() &&
+ sibling->isBlack() &&
+ ((!sibling->getLeft()) || sibling->getLeft()->isBlack()) &&
+ ((!sibling->getRight()) || sibling->getRight()->isBlack()))
+ {
+ sibling->setColor(DomainTreeNode<T>::RED);
+ parent->setColor(DomainTreeNode<T>::BLACK);
+ break;
+ }
+
+ if (sibling->isBlack()) {
+ if ((parent->getLeft() == child) &&
+ (sibling->getLeft() && sibling->getLeft()->isRed()) &&
+ ((!sibling->getRight()) || sibling->getRight()->isBlack()))
+ {
+ sibling->setColor(DomainTreeNode<T>::RED);
+ if (sibling->getLeft()) {
+ sibling->getLeft()->setColor(DomainTreeNode<T>::BLACK);
+ }
+ rightRotate(root_ptr, sibling);
+ } else if ((parent->getRight() == child) &&
+ (sibling->getRight() && sibling->getRight()->isRed()) &&
+ ((!sibling->getLeft()) || sibling->getLeft()->isBlack()))
+ {
+ sibling->setColor(DomainTreeNode<T>::RED);
+ if (sibling->getRight()) {
+ sibling->getRight()->setColor(DomainTreeNode<T>::BLACK);
+ }
+ leftRotate(root_ptr, sibling);
+ }
+ }
+
+ if (parent->isRed()) {
+ sibling->setColor(DomainTreeNode<T>::RED);
+ } else {
+ sibling->setColor(DomainTreeNode<T>::BLACK);
+ }
+
+ parent->setColor(DomainTreeNode<T>::BLACK);
+
+ if (parent->getLeft() == child) {
+ if (sibling->getRight()) {
+ sibling->getRight()->setColor(DomainTreeNode<T>::BLACK);
+ }
+ leftRotate(root_ptr, parent);
+ } else {
+ if (sibling->getLeft()) {
+ sibling->getLeft()->setColor(DomainTreeNode<T>::BLACK);
+ }
+ rightRotate(root_ptr, parent);
+ }
+
+ break;
+ }
}
template <typename T>
diff --git a/src/lib/datasrc/tests/memory/domaintree_unittest.cc b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
index 1628b48..e7fd0b5 100644
--- a/src/lib/datasrc/tests/memory/domaintree_unittest.cc
+++ b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
@@ -352,14 +352,62 @@ TEST_F(DomainTreeTest, remove) {
o1.close();
EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("x.d.e.f"), &dtnode));
+ dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
+
+ ofstream o2("d2.dot");
+ dtree_expose_empty_node.dumpDot(o2);
+ o2.close();
+
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("z.d.e.f"), &dtnode));
+ dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
+
+ ofstream o3("d3.dot");
+ dtree_expose_empty_node.dumpDot(o3);
+ o3.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);
+ ofstream o4("d4.dot");
+ dtree_expose_empty_node.dumpDot(o4);
+ o4.close();
+
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");
+ ofstream o5("d5.dot");
+ dtree_expose_empty_node.dumpDot(o5);
+ o5.close();
+}
+
+TEST_F(DomainTreeTest, remove2) {
+ ofstream o1("g1.dot");
+ dtree_expose_empty_node.dumpDot(o1);
+ o1.close();
+
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("p.w.y.d.e.f"), &dtnode));
+ dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
+
+ ofstream o2("g2.dot");
+ dtree_expose_empty_node.dumpDot(o2);
+ o2.close();
+}
+
+TEST_F(DomainTreeTest, remove3) {
+ ofstream o1("g1.dot");
+ dtree_expose_empty_node.dumpDot(o1);
+ o1.close();
+
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("b"), &dtnode));
+ dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
+
+ ofstream o2("g2.dot");
dtree_expose_empty_node.dumpDot(o2);
o2.close();
}
More information about the bind10-changes
mailing list