BIND 10 master, updated. 4f9f077ffae95f15f162d8f640c4896fe56b7934 Merge branch 'master' into trac2054
BIND 10 source code commits
bind10-changes at lists.isc.org
Thu Aug 2 05:17:21 UTC 2012
The branch, master has been updated
via 4f9f077ffae95f15f162d8f640c4896fe56b7934 (commit)
via dca052ba19feab373ef9c36e929abd19c663e051 (commit)
via 72539e992045e3b5b733d32660b6b939e5c67015 (commit)
via a82d0b162c3d651719128154301da4793ed22643 (commit)
via e9eec8d241bb11fcfba0ba4d04cfbfdb62832683 (commit)
from a3e59452b950dce4866fb62e36b1af2e6e9037db (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 4f9f077ffae95f15f162d8f640c4896fe56b7934
Merge: dca052b a3e5945
Author: Mukund Sivaraman <muks at isc.org>
Date: Thu Aug 2 10:39:23 2012 +0530
Merge branch 'master' into trac2054
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/rbtree.h | 76 ++++++++++++++++--------------
src/lib/datasrc/tests/rbtree_unittest.cc | 34 ++++++++++++-
2 files changed, 72 insertions(+), 38 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index 083c52a..4f15b0e 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -1312,10 +1312,11 @@ private:
/// Split one node into two nodes for "prefix" and "suffix" parts of
/// the labels of the original node, respectively. The given node
- /// will hold the suffix labels, while the new node will hold the prefix.
- /// The newly created node represents the labels that the original node
- /// did, so necessary data are swapped.
- /// (Note: as commented in the code, this behavior should be changed).
+ /// will hold the prefix, while a newly created node will hold the prefix.
+ /// Note that the original node still represents the same domain name in
+ /// the entire tree. This ensures that a pointer to a node keeps its
+ /// semantics even if the tree structure is changed (as long as the node
+ /// itself remains valid).
void nodeFission(util::MemorySegment& mem_sgmt, RBNode<T>& node,
const isc::dns::LabelSequence& new_prefix,
const isc::dns::LabelSequence& new_suffix);
@@ -1658,6 +1659,7 @@ RBTree<T>::insert(util::MemorySegment& mem_sgmt,
dns::LabelSequence new_prefix = current_labels;
new_prefix.stripRight(compare_result.getCommonLabels());
nodeFission(mem_sgmt, *current, new_prefix, common_ancestor);
+ current = current->getParent();
}
}
@@ -1696,11 +1698,6 @@ RBTree<T>::deleteAllNodes(util::MemorySegment& mem_sgmt) {
root_ = NULL;
}
-// Note: when we redesign this (still keeping the basic concept), we should
-// change this part so the newly created node will be used for the inserted
-// name (and therefore the name for the existing node doesn't change).
-// Otherwise, things like shortcut links between nodes won't work.
-// See Trac #2054.
template <typename T>
void
RBTree<T>::nodeFission(util::MemorySegment& mem_sgmt, RBNode<T>& node,
@@ -1712,38 +1709,45 @@ RBTree<T>::nodeFission(util::MemorySegment& mem_sgmt, RBNode<T>& node,
// the end of the function, and it will keep consistent behavior
// (i.e., a weak form of strong exception guarantee) even if code
// after the call to this function throws an exception.
- RBNode<T>* down_node = RBNode<T>::create(mem_sgmt, new_prefix);
- node.resetLabels(new_suffix);
-
- std::swap(node.data_, down_node->data_);
-
- // Swap flags bitfields; yes, this is ugly (it appears we cannot use
- // std::swap for bitfields). The right solution is to implement
- // the above note regarding #2054, then we won't have to swap the
- // flags in the first place.
- const bool is_root = node.isSubTreeRoot();
- const uint32_t tmp = node.flags_;
- node.flags_ = down_node->flags_;
- down_node->flags_ = tmp;
- node.setSubTreeRoot(is_root);
-
- down_node->down_ = node.getDown();
- if (down_node->down_ != NULL) {
- down_node->down_->parent_ = down_node;
+ RBNode<T>* up_node = RBNode<T>::create(mem_sgmt, new_suffix);
+ 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 {
+ this->root_ = up_node;
}
- node.down_ = down_node;
- down_node->parent_ = &node;
+ up_node->down_ = &node;
+ node.parent_ = up_node;
- // Restore the color of the node (may have gotten changed by the flags
- // swap)
- node.setColor(down_node->getColor());
+ // inherit the left/right pointers from the original node, and set
+ // the original node's left/right pointers to NULL.
+ up_node->left_ = node.getLeft();
+ if (node.getLeft() != NULL) {
+ node.getLeft()->parent_ = up_node;
+ }
+ up_node->right_ = node.getRight();
+ if (node.getRight() != NULL) {
+ node.getRight()->parent_ = up_node;
+ }
+ node.left_ = NULL;
+ node.right_ = NULL;
- // root node of sub tree, the initial color is BLACK
- down_node->setColor(RBNode<T>::BLACK);
+ // set color of both nodes; the initial subtree node color is BLACK
+ up_node->setColor(node.getColor());
+ node.setColor(RBNode<T>::BLACK);
- // mark it as the root of a subtree
- down_node->setSubTreeRoot(true);
+ // set the subtree root flag of both nodes
+ up_node->setSubTreeRoot(node.isSubTreeRoot());
+ node.setSubTreeRoot(true);
++node_count_;
}
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 918495e..2370631 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -40,7 +40,7 @@ const size_t Name::MAX_LABELS;
/* The initial structure of rbtree
*
-* .
+ * .
* |
* b
* / \
@@ -253,6 +253,36 @@ TEST_F(RBTreeTest, subTreeRoot) {
EXPECT_TRUE(rbtnode->getFlag(RBNode<int>::FLAG_SUBTREE_ROOT));
}
+TEST_F(RBTreeTest, additionalNodeFission) {
+ // These are additional nodeFission tests added by #2054's rewrite
+ // of RBTree::nodeFission(). These test specific corner cases that
+ // are not covered by other tests.
+
+ // Insert "t.0" (which becomes the left child of its parent)
+ EXPECT_EQ(RBTree<int>::SUCCESS,
+ rbtree_expose_empty_node.insert(mem_sgmt_, Name("t.0"),
+ &rbtnode));
+
+ // "t.0" is not a subtree root
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree_expose_empty_node.find(Name("t.0"), &rbtnode));
+ EXPECT_FALSE(rbtnode->getFlag(RBNode<int>::FLAG_SUBTREE_ROOT));
+
+ // fission the node "t.0"
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS,
+ rbtree_expose_empty_node.insert(mem_sgmt_, Name("0"),
+ &rbtnode));
+
+ // the node "0" ("0".down_ -> "t") should not be a subtree root. "t"
+ // should be a subtree root.
+ EXPECT_FALSE(rbtnode->getFlag(RBNode<int>::FLAG_SUBTREE_ROOT));
+
+ // "t.0" should be a subtree root now.
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree_expose_empty_node.find(Name("t.0"), &rbtnode));
+ EXPECT_TRUE(rbtnode->getFlag(RBNode<int>::FLAG_SUBTREE_ROOT));
+}
+
TEST_F(RBTreeTest, findName) {
// find const rbtnode
// exact match
@@ -470,7 +500,7 @@ TEST_F(RBTreeTest, getAbsoluteNameError) {
}
/*
- *the domain order should be:
+ * The domain order should be:
* ., a, b, c, d.e.f, x.d.e.f, w.y.d.e.f, o.w.y.d.e.f, p.w.y.d.e.f,
* q.w.y.d.e.f, z.d.e.f, j.z.d.e.f, g.h, i.g.h, k.g.h
* . (no data, can't be found)
More information about the bind10-changes
mailing list