BIND 10 trac2750, updated. 730aac841ed98bd35582d0a7c39a9b00835016a1 [2750] Start to remove() with initial exchange with a leaf node
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Aug 26 09:05:34 UTC 2013
The branch, trac2750 has been updated
via 730aac841ed98bd35582d0a7c39a9b00835016a1 (commit)
via 5ffd53da7b10bec4ade51ef974a9b9a23e1a0085 (commit)
from 702505336da1317a8cfeeb5a04e8c5d1ac439469 (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 730aac841ed98bd35582d0a7c39a9b00835016a1
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 26 14:09:17 2013 +0530
[2750] Start to remove() with initial exchange with a leaf node
commit 5ffd53da7b10bec4ade51ef974a9b9a23e1a0085
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 26 10:58:38 2013 +0530
[2750] Add non-const variants of more find() methods
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 198 +++++++++++++++++---
.../datasrc/tests/memory/domaintree_unittest.cc | 17 ++
2 files changed, 185 insertions(+), 30 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 2f0cb44..ace435f 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -625,6 +625,59 @@ private:
return (down_.get());
}
+ /// \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
+ /// std::swap()-like behavior.
+ ///
+ /// This method doesn't throw any exceptions.
+ void exchange(DomainTreeNode<T>* other, DomainTreeNodePtr* subtree_root) {
+ std::swap(left_, other->left_);
+ if (other->getLeft() == other) {
+ other->left_ = this;
+ }
+
+ std::swap(right_, other->right_);
+ if (other->getRight() == other) {
+ other->right_ = this;
+ }
+
+ std::swap(parent_, other->parent_);
+ if (getParent() == this) {
+ parent_ = other;
+ }
+
+ // Update FLAG_RED and FLAG_SUBTREE_ROOT as these two are
+ // associated with the node's position.
+ const bool this_is_red = isRed();
+ const bool this_is_subtree_root = isSubTreeRoot();
+ const bool other_is_red = other->isRed();
+ const bool other_is_subtree_root = other->isSubTreeRoot();
+
+ if (this_is_red) {
+ other->setColor(RED);
+ } else {
+ other->setColor(BLACK);
+ }
+
+ if (other_is_red) {
+ setColor(RED);
+ } else {
+ setColor(BLACK);
+ }
+
+ 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;
+ }
+ }
+ }
+
/// \brief Data stored here.
boost::interprocess::offset_ptr<T> data_;
@@ -1256,32 +1309,104 @@ public:
/// of it. In that case, node parameter is left intact.
//@{
+private:
+ /// \brief Static helper function used by const and non-const
+ /// variants of find() below
+ template <typename TT, typename TTN, typename CBARG>
+ static Result findImpl(TT* tree,
+ const isc::dns::LabelSequence& target_labels_orig,
+ TTN** target,
+ TTN* node,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg);
+
+ /// \brief Static helper function used by const and non-const
+ /// variants of find() below
+ template <typename TT, typename TTN>
+ static Result findImpl(TT* tree,
+ const isc::dns::Name& name,
+ TTN** node)
+ {
+ DomainTreeNodeChain<T> node_path;
+ const isc::dns::LabelSequence ls(name);
+ return (tree->find<void*>(ls, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Static helper function used by const and non-const
+ /// variants of find() below
+ template <typename TT, typename TTN>
+ static Result findImpl(TT* tree,
+ const isc::dns::Name& name,
+ TTN** node,
+ DomainTreeNodeChain<T>& node_path)
+ {
+ const isc::dns::LabelSequence ls(name);
+ return (tree->find<void*>(ls, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Static helper function used by const and non-const
+ /// variants of find() below
+ template <typename TT, typename TTN, typename CBARG>
+ static Result findImpl(TT* tree,
+ const isc::dns::Name& name,
+ TTN** node,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg)
+ {
+ const isc::dns::LabelSequence ls(name);
+ return (tree->find(ls, node, node_path, callback, callback_arg));
+ }
+
+public:
/// \brief Simple find
///
/// Acts as described in the \ref find section.
Result find(const isc::dns::Name& name,
+ DomainTreeNode<T>** node) {
+ return (findImpl<DomainTree<T>, DomainTreeNode<T> >
+ (this, name, node));
+ }
+
+ /// \brief Simple find (const variant)
+ Result find(const isc::dns::Name& name,
const DomainTreeNode<T>** node) const {
- DomainTreeNodeChain<T> node_path;
- const isc::dns::LabelSequence ls(name);
- Result ret = (find<void*>(ls, node, node_path, NULL, NULL));
- return (ret);
+ return (findImpl<const DomainTree<T>, const DomainTreeNode<T> >
+ (this, name, node));
}
/// \brief Simple find, with node_path tracking
///
/// Acts as described in the \ref find section.
+ Result find(const isc::dns::Name& name, DomainTreeNode<T>** node,
+ DomainTreeNodeChain<T>& node_path)
+ {
+ return (findImpl<DomainTree<T>, DomainTreeNode<T> >
+ (this, name, node, node_path));
+ }
+
+ /// \brief Simple find, with node_path tracking (const variant)
Result find(const isc::dns::Name& name, const DomainTreeNode<T>** node,
DomainTreeNodeChain<T>& node_path) const
{
- const isc::dns::LabelSequence ls(name);
- Result ret = (find<void*>(ls, node, node_path, NULL, NULL));
- return (ret);
+ return (findImpl<const DomainTree<T>, const DomainTreeNode<T> >
+ (this, name, node, node_path));
}
- /// \brief Simple find returning immutable node.
- ///
- /// Acts as described in the \ref find section, but returns immutable
- /// node pointer.
+ /// \brief Simple find with callback
+ template <typename CBARG>
+ Result find(const isc::dns::Name& name,
+ DomainTreeNode<T>** node,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg)
+ {
+ return (findImpl<DomainTree<T>, DomainTreeNode<T> >
+ (this, name, node, node_path, callback, callback_arg));
+ }
+
+ /// \brief Simple find with callback (const variant)
template <typename CBARG>
Result find(const isc::dns::Name& name,
const DomainTreeNode<T>** node,
@@ -1289,25 +1414,10 @@ public:
bool (*callback)(const DomainTreeNode<T>&, CBARG),
CBARG callback_arg) const
{
- const isc::dns::LabelSequence ls(name);
- Result ret = find(ls, node, node_path, callback,
- callback_arg);
- return (ret);
+ return (findImpl<const DomainTree<T>, const DomainTreeNode<T> >
+ (this, name, node, node_path, callback, callback_arg));
}
-private:
- /// \brief Static helper function used by const and non-const
- /// variants of find() below
- template <typename TT, typename TTN, typename CBARG>
- static Result findImpl(TT* tree,
- const isc::dns::LabelSequence& target_labels_orig,
- TTN** target,
- TTN* node,
- DomainTreeNodeChain<T>& node_path,
- bool (*callback)(const DomainTreeNode<T>&, CBARG),
- CBARG callback_arg);
-
-public:
/// \brief Find with callback and node chain
/// \anchor callback
///
@@ -2101,9 +2211,37 @@ DomainTree<T>::insert(util::MemorySegment& mem_sgmt,
template <typename T>
template <typename DataDeleter>
void
-DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
- DataDeleter deleter)
+DomainTree<T>::remove(util::MemorySegment&, DomainTreeNode<T>* node,
+ DataDeleter)
{
+ 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).
+
+ if (node->getLeft() != NULL) {
+ DomainTreeNode<T>* rightmost = node->getLeft();
+ while (rightmost->getRight() != NULL) {
+ rightmost = rightmost->getRight();
+ }
+
+ node->exchange(rightmost, &root_);
+ } else if (node->getRight() != NULL) {
+ DomainTreeNode<T>* leftmost = node->getRight();
+ while (leftmost->getLeft() != NULL) {
+ leftmost = leftmost->getLeft();
+ }
+
+ node->exchange(leftmost, &root_);
+ }
+
+ // Now, node is a leaf 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 a87c807..4ac86ec 100644
--- a/src/lib/datasrc/tests/memory/domaintree_unittest.cc
+++ b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
@@ -31,6 +31,8 @@
#include <boost/format.hpp>
+#include <fstream>
+
using namespace std;
using namespace isc;
using namespace isc::dns;
@@ -344,6 +346,21 @@ TEST_F(DomainTreeTest, insertNames) {
&dtnode));
}
+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();
+
+ dtree_expose_empty_node.remove(mem_sgmt_, dtnode, deleteData);
+
+ ofstream o2("d2.dot");
+ dtree_expose_empty_node.dumpDot(o2);
+ o2.close();
+}
+
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