BIND 10 trac2218_2, updated. ca9f73e098180f9d5d188f1d1bd46031f9b81ce3 [2218] Use alternate DomainTree methods to get the covering node
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Sep 24 05:08:45 UTC 2012
The branch, trac2218_2 has been updated
via ca9f73e098180f9d5d188f1d1bd46031f9b81ce3 (commit)
via 055a8352580a73069b0745d3fbddec1c488f9e59 (commit)
via 3aeb78fd7a34c736a4ba3b985ef6a0f8432bfafa (commit)
from 6bf4ff4eb4a3a8095bdd5d622cab24f46a0d9834 (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 ca9f73e098180f9d5d188f1d1bd46031f9b81ce3
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Sep 24 10:36:28 2012 +0530
[2218] Use alternate DomainTree methods to get the covering node
This avoids the use of predecessor() and successor() and
getLargestInSubTree(), and uses previousNode() and largestNode()
instead.
commit 055a8352580a73069b0745d3fbddec1c488f9e59
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Sep 24 10:35:09 2012 +0530
[2218] Add DomainTree::largestNode() to return the largest node in tree-of-trees
There was an old version of this method, but that was buggy.
commit 3aeb78fd7a34c736a4ba3b985ef6a0f8432bfafa
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Sep 24 10:30:33 2012 +0530
[2218] Rearrange method in domaintree.h
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 41 ++++++++++++++++----
.../datasrc/memory/tests/domaintree_unittest.cc | 5 +++
src/lib/datasrc/memory/zone_finder.cc | 30 +++-----------
3 files changed, 44 insertions(+), 32 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 5d98d48..aa37006 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -391,6 +391,14 @@ public:
/// This method never throws an exception.
const DomainTreeNode<T>* getSubTreeRoot() const;
+ /// \brief returns the largest node of this node's subtree
+ ///
+ /// This method takes a node and returns the largest node in its
+ /// subtree.
+ ///
+ /// This method never throws an exception.
+ const DomainTreeNode<T>* getLargestInSubTree() const;
+
/// \brief returns the parent of the root of its subtree
///
/// This method takes a node and returns the parent of the root of
@@ -401,14 +409,6 @@ public:
/// This method never throws an exception.
const DomainTreeNode<T>* getUpperNode() const;
- /// \brief returns the largest node of this node's subtree
- ///
- /// This method takes a node and returns the largest node in its
- /// subtree.
- ///
- /// This method never throws an exception.
- const DomainTreeNode<T>* getLargestInSubTree() const;
-
/// \brief return the next node which is bigger than current node
/// in the same subtree
///
@@ -1303,6 +1303,13 @@ public:
const DomainTreeNode<T>*
previousNode(DomainTreeNodeChain<T>& node_path) const;
+ /// \brief return the largest node in the tree of trees.
+ ///
+ /// \return A \c DomainTreeNode that is the largest node in the
+ /// tree. If there are no nodes, then \c NULL is returned.
+ const DomainTreeNode<T>*
+ largestNode() const;
+
/// \brief Get the total number of nodes in the tree
///
/// It includes nodes internally created as a result of adding a domain
@@ -1748,6 +1755,24 @@ DomainTree<T>::previousNode(DomainTreeNodeChain<T>& node_path) const {
}
template <typename T>
+const DomainTreeNode<T>*
+DomainTree<T>::largestNode() const {
+ const DomainTreeNode<T>* node = root_.get();
+ while (node != NULL) {
+ // We go right first, then down.
+ if (node->getRight() != NULL) {
+ node = node->getRight();
+ } else if (node->getDown() != NULL) {
+ node = node->getDown();
+ } else {
+ break;
+ }
+ }
+
+ return (node);
+}
+
+template <typename T>
typename DomainTree<T>::Result
DomainTree<T>::insert(util::MemorySegment& mem_sgmt,
const isc::dns::Name& target_name,
diff --git a/src/lib/datasrc/memory/tests/domaintree_unittest.cc b/src/lib/datasrc/memory/tests/domaintree_unittest.cc
index b26c9b5..0793206 100644
--- a/src/lib/datasrc/memory/tests/domaintree_unittest.cc
+++ b/src/lib/datasrc/memory/tests/domaintree_unittest.cc
@@ -1005,6 +1005,11 @@ TEST_F(DomainTreeTest, previousNode) {
}
}
+TEST_F(DomainTreeTest, largestNode) {
+ cdtnode = dtree.largestNode();
+ EXPECT_EQ(Name("k"), cdtnode->getName());
+}
+
TEST_F(DomainTreeTest, nextNodeError) {
// Empty chain for nextNode() is invalid.
TestDomainTreeNodeChain chain;
diff --git a/src/lib/datasrc/memory/zone_finder.cc b/src/lib/datasrc/memory/zone_finder.cc
index da18cf0..f57fe7a 100644
--- a/src/lib/datasrc/memory/zone_finder.cc
+++ b/src/lib/datasrc/memory/zone_finder.cc
@@ -669,30 +669,12 @@ InMemoryZoneFinder::findNSEC3(const isc::dns::Name& name, bool recursive) {
return (FindNSEC3Result(true, labels, closest, next));
} else {
- const ZoneNode* last_node = chain.getLastComparedNode();
-
- const NameComparisonResult& last_cmp =
- chain.getLastComparisonResult();
- assert(last_cmp.getOrder() != 0);
-
- if (last_cmp.getOrder() < 0) {
- // We exited on the left side of the last compared node,
- // so the covering node is the previous one to the last
- // compared node.
- covering_node = last_node->predecessor();
- if (covering_node == NULL) {
- // If the given hash is smaller than everything, the
- // covering proof is the NSEC3 that has the largest
- // hash.
- covering_node = last_node->getLargestInSubTree();
- }
- } else {
- // We exited on the right side of the last compared
- // node, so the covering node is the last compared node.
- covering_node = last_node;
- // If the given hash is larger than everything, then
- // covering proof is the NSEC3 that has the largest
- // hash, which is automatically the last compared node.
+ while ((covering_node = tree.previousNode(chain)) != NULL &&
+ covering_node->isEmpty()) {
+ ;
+ }
+ if (covering_node == NULL) {
+ covering_node = tree.largestNode();
}
if (!recursive) { // in non recursive mode, we are done.
More information about the bind10-changes
mailing list