BIND 10 master, updated. 7356673c98e3ca56e1ed4adecab4818c018ccf81 [master] Merge branch 'trac507' with resolving conflicts in memory_datasrc.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Tue Feb 8 18:18:27 UTC 2011
The branch, master has been updated
via 7356673c98e3ca56e1ed4adecab4818c018ccf81 (commit)
via 3032690d227ee2fe8f660bdcd6c0782c6a635ef0 (commit)
via 92d766ce1407da1d1bed05e64c2b62b25af63303 (commit)
via 35d21690b35272d7046b54274ccbe87fd0279b30 (commit)
via 4aa5062b964d03a27adb9eef0d519aa26efa34a0 (commit)
via ab989937aef9282b9417a51ace071cdb199b290e (commit)
via bcac9ef1e7fb84fabbda7f41d360d4a437ae2102 (commit)
via 56baabf66b9a5224d0d2d545f65b82ab50ae781d (commit)
via dc5d961adfa0c6b05b911532535942c00eccda7d (commit)
via 1ab958cdc6f1ebdbf88f863a4a15d6a5783035bc (commit)
from 57fdfeac98e3519e64105849495c1557388bc402 (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 7356673c98e3ca56e1ed4adecab4818c018ccf81
Merge: 57fdfea 3032690
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Tue Feb 8 10:17:33 2011 -0800
[master] Merge branch 'trac507' with resolving conflicts in memory_datasrc.cc
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory_datasrc.cc | 26 ++++--
src/lib/datasrc/rbtree.h | 103 +++++++++++++++---
src/lib/datasrc/tests/memory_datasrc_unittest.cc | 39 +++++++
src/lib/datasrc/tests/rbtree_unittest.cc | 123 +++++++++++++++++++++-
4 files changed, 266 insertions(+), 25 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory_datasrc.cc b/src/lib/datasrc/memory_datasrc.cc
index 31c5a95..0691926 100644
--- a/src/lib/datasrc/memory_datasrc.cc
+++ b/src/lib/datasrc/memory_datasrc.cc
@@ -35,7 +35,8 @@ namespace datasrc {
struct MemoryZone::MemoryZoneImpl {
// Constructor
MemoryZoneImpl(const RRClass& zone_class, const Name& origin) :
- zone_class_(zone_class), origin_(origin), origin_data_(NULL)
+ zone_class_(zone_class), origin_(origin), origin_data_(NULL),
+ domains_(true)
{
// We create the node for origin (it needs to exist anyway in future)
domains_.insert(origin, &origin_data_);
@@ -319,10 +320,16 @@ struct MemoryZone::MemoryZoneImpl {
if (state.zonecut_node_ != NULL) {
return (FindResult(DELEGATION, state.rrset_));
}
- // TODO: we should also cover empty non-terminal cases, which
- // will require non trivial code and is deferred for later
- // development. For now, we regard any partial match that
- // didn't hit a zone cut as "not found".
+
+ // If the RBTree search stopped at a node for a super domain
+ // of the search name, it means the search name exists in
+ // the zone but is empty. Treat it as NXRRSET.
+ if (node_path.getLastComparisonResult().getRelation() ==
+ NameComparisonResult::SUPERDOMAIN) {
+ return (FindResult(NXRRSET, ConstRRsetPtr()));
+ }
+
+ // fall through
case DomainTree::NOTFOUND:
return (FindResult(NXDOMAIN, ConstRRsetPtr()));
case DomainTree::EXACTMATCH: // This one is OK, handle it
@@ -330,8 +337,13 @@ struct MemoryZone::MemoryZoneImpl {
default:
assert(0);
}
- assert(node);
- assert(!node->isEmpty());
+ assert(node != NULL);
+
+ // If there is an exact match but the node is empty, it's equivalent
+ // to NXRRSET.
+ if (node->isEmpty()) {
+ return (FindResult(NXRRSET, ConstRRsetPtr()));
+ }
Domain::const_iterator found;
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index cf413e8..8ceb7e0 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -286,8 +286,19 @@ RBNode<T>::successor() const {
}
-/// \brief RBTreeNodeChain is used to keep track of the sequence of
-/// nodes to reach any given node from the root of RBTree.
+/// \brief RBTreeNodeChain stores detailed information of \c RBTree::find()
+/// result.
+///
+/// - The \c RBNode that was last compared with the search name, and
+/// the comparison result at that point in the form of
+/// \c isc::dns::NameComparisonResult.
+/// - A sequence of nodes that forms a path to the found node (which is
+/// not yet implemented).
+///
+/// The comparison result can be used to handle some rare cases such as
+/// empty node processing.
+/// The node sequence keeps track of the nodes to reach any given node from
+/// the root of RBTree.
///
/// Currently, RBNode does not have "up" pointers in them (i.e., back pointers
/// from the root of one level of tree of trees to the node in the parent
@@ -299,6 +310,10 @@ RBNode<T>::successor() const {
/// quite likely we want to have that pointer if we want to optimize name
/// compression by exploiting the structure of the zone. If and when that
/// happens we should also revisit the need for the chaining.
+/// Also, the class name may not be appropriate now that it contains other
+/// information than a node "chain", and the chain itself may even be
+/// deprecated. Something like "RBTreeFindContext" may be a better name.
+/// This point should be revisited later.
///
/// RBTreeNodeChain is constructed and manipulated only inside the \c RBTree
/// class.
@@ -323,7 +338,11 @@ public:
/// The default constructor.
///
/// \exception None
- RBTreeNodeChain() : node_count_(0) {}
+ RBTreeNodeChain() : node_count_(0), last_compared_(NULL),
+ // XXX: meaningless initial values:
+ last_comparison_(0, 0,
+ isc::dns::NameComparisonResult::EQUAL)
+ {}
private:
RBTreeNodeChain(const RBTreeNodeChain<T>&);
@@ -331,6 +350,46 @@ private:
//@}
public:
+ /// Clear the state of the chain.
+ ///
+ /// This method re-initializes the internal state of the chain so that
+ /// it can be reused for subsequent operations.
+ ///
+ /// \exception None
+ void clear() {
+ node_count_ = 0;
+ last_compared_ = NULL;
+ }
+
+ /// Return the \c RBNode that was last compared in \c RBTree::find().
+ ///
+ /// If this chain has been passed to \c RBTree::find() and there has
+ /// been name comparison against the search name, the last compared
+ /// \c RBNode is recorded within the chain. This method returns that
+ /// node.
+ /// If \c RBTree::find() hasn't been called with this chain or name
+ /// comparison hasn't taken place (which is possible if the tree is empty),
+ /// this method returns \c NULL.
+ ///
+ /// \exception None
+ const RBNode<T>* getLastComparedNode() const {
+ return (last_compared_);
+ }
+
+ /// Return the result of last name comparison in \c RBTree::find().
+ ///
+ /// Like \c getLastComparedNode(), \c RBTree::find() records the result
+ /// of the last name comparison in the chain. This method returns the
+ /// result.
+ /// The return value of this method is only meaningful when comparison
+ /// has taken place, i.e, when \c getLastComparedNode() would return a
+ /// non \c NULL value.
+ ///
+ /// \exception None
+ const isc::dns::NameComparisonResult& getLastComparisonResult() const {
+ return (last_comparison_);
+ }
+
/// \brief Return the number of levels stored in the chain.
///
/// It's equal to the number of nodes in the chain; for an empty
@@ -418,8 +477,10 @@ private:
// It's also the possible maximum nodes stored in a chain.
const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS - 1;
- const RBNode<T>* nodes_[RBT_MAX_LEVEL];
int node_count_;
+ const RBNode<T>* nodes_[RBT_MAX_LEVEL];
+ const RBNode<T>* last_compared_;
+ isc::dns::NameComparisonResult last_comparison_;
};
@@ -603,12 +664,18 @@ public:
/// The callbacks are not general functors for the same reason - we don't
/// expect it to be needed.
///
- /// Another special feature of this version is the ability to provide
- /// a node chain containing a path to the found node. The chain will be
- /// returned via the \c node_path parameter.
+ /// Another special feature of this version is the ability to record
+ /// more detailed information regarding the search result.
+ ///
+ /// This information will be returned via the \c node_path parameter,
+ /// which is an object of class \c RBTreeNodeChain.
/// The passed parameter must be empty.
- /// On success, it will contain all the ancestor nodes from the found
- /// node towards the root.
+ ///
+ /// \note The rest of the description isn't yet implemented. It will be
+ /// handled in Trac ticket #517.
+ ///
+ /// On success, the node sequence stoed in \c node_path will contain all
+ /// the ancestor nodes from the found node towards the root.
/// For example, if we look for o.w.y.d.e.f in the example \ref diagram,
/// \c node_path will contain w.y and d.e.f; the \c top() node of the
/// chain will be o, w.f and d.e.f will be stored below it.
@@ -622,13 +689,13 @@ public:
/// node of a given node in the entire RBTree; the \c nextNode() method
/// takes a node chain as a parameter.
///
- /// \exception isc::BadValue node_path is not empty.
+ /// \exception isc::BadValue node_path is not empty (not yet implemented).
///
/// \param name Target to be found
/// \param node On success (either \c EXACTMATCH or \c PARTIALMATCH)
/// it will store a pointer to the matching node
- /// \param node_path It will store all the ancestor nodes in the RBTree
- /// from the found node to the root. The found node is stored.
+ /// \param node_path Other search details will be stored (see the
+ /// description)
/// \param callback If non \c NULL, a call back function to be called
/// at marked nodes (see above).
/// \param callback_arg A caller supplied argument to be passed to
@@ -853,10 +920,11 @@ RBTree<T>::find(const isc::dns::Name& target_name,
isc::dns::Name name = target_name;
while (node != NULLNODE) {
- const isc::dns::NameComparisonResult compare_result =
- name.compare(node->name_);
+ node_path.last_compared_ = node;
+ node_path.last_comparison_ = name.compare(node->name_);
const isc::dns::NameComparisonResult::NameRelation relation =
- compare_result.getRelation();
+ node_path.last_comparison_.getRelation();
+
if (relation == isc::dns::NameComparisonResult::EQUAL) {
if (needsReturnEmptyNode_ || !node->isEmpty()) {
node_path.push(node);
@@ -865,11 +933,12 @@ RBTree<T>::find(const isc::dns::Name& target_name,
}
break;
} else {
- const int common_label_count = compare_result.getCommonLabels();
+ const int common_label_count =
+ node_path.last_comparison_.getCommonLabels();
// If the common label count is 1, there is no common label between
// the two names, except the trailing "dot".
if (common_label_count == 1) {
- node = (compare_result.getOrder() < 0) ?
+ node = (node_path.last_comparison_.getOrder() < 0) ?
node->left_ : node->right_;
} else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
if (needsReturnEmptyNode_ || !node->isEmpty()) {
diff --git a/src/lib/datasrc/tests/memory_datasrc_unittest.cc b/src/lib/datasrc/tests/memory_datasrc_unittest.cc
index be71e7f..65b3c95 100644
--- a/src/lib/datasrc/tests/memory_datasrc_unittest.cc
+++ b/src/lib/datasrc/tests/memory_datasrc_unittest.cc
@@ -555,6 +555,45 @@ TEST_F(MemoryZoneTest, find) {
findTest(Name("example.net"), RRType::A(), Zone::NXDOMAIN);
}
+TEST_F(MemoryZoneTest, emptyNode) {
+ /*
+ * The backend RBTree for this test should look like as follows:
+ * example.org
+ * |
+ * baz (empty; easy case)
+ * / | \
+ * bar | x.foo ('foo' part is empty; a bit trickier)
+ * bbb
+ * /
+ * aaa
+ */
+
+ // Construct the test zone
+ const char* const names[] = {
+ "bar.example.org", "x.foo.example.org", "aaa.baz.example.org",
+ "bbb.baz.example.org.", NULL};
+ for (int i = 0; names[i] != NULL; ++i) {
+ ConstRRsetPtr rrset(new RRset(Name(names[i]), class_, RRType::A(),
+ RRTTL(300)));
+ EXPECT_EQ(SUCCESS, zone_.add(rrset));
+ }
+
+ // empty node matching, easy case: the node for 'baz' exists with
+ // no data.
+ findTest(Name("baz.example.org"), RRType::A(), Zone::NXRRSET);
+
+ // empty node matching, a trickier case: the node for 'foo' is part of
+ // "x.foo", which should be considered an empty node.
+ findTest(Name("foo.example.org"), RRType::A(), Zone::NXRRSET);
+
+ // "org" is contained in "example.org", but it shouldn't be treated as
+ // NXRRSET because it's out of zone.
+ // Note: basically we don't expect such a query to be performed (the common
+ // operation is to identify the best matching zone first then perform
+ // search it), but we shouldn't be confused even in the unexpected case.
+ findTest(Name("org"), RRType::A(), Zone::NXDOMAIN);
+}
+
TEST_F(MemoryZoneTest, load) {
// Put some data inside the zone
EXPECT_NO_THROW(EXPECT_EQ(result::SUCCESS, zone_.add(rr_ns_)));
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 24d94a3..2abe14d 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -12,7 +12,6 @@
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.
-
#include <gtest/gtest.h>
#include <exceptions/exceptions.h>
@@ -342,6 +341,128 @@ TEST_F(RBTreeTest, nextNodeError) {
EXPECT_THROW(rbtree.nextNode(chain), BadValue);
}
+// A helper function for getLastComparedNode() below.
+void
+comparisonChecks(const RBTreeNodeChain<int>& chain,
+ int expected_order, int expected_common_labels,
+ NameComparisonResult::NameRelation expected_reln)
+{
+ if (expected_order > 0) {
+ EXPECT_LT(0, chain.getLastComparisonResult().getOrder());
+ } else if (expected_order < 0) {
+ EXPECT_GT(0, chain.getLastComparisonResult().getOrder());
+ } else {
+ EXPECT_EQ(0, chain.getLastComparisonResult().getOrder());
+ }
+ EXPECT_EQ(expected_common_labels,
+ chain.getLastComparisonResult().getCommonLabels());
+ EXPECT_EQ(expected_reln,
+ chain.getLastComparisonResult().getRelation());
+}
+
+TEST_F(RBTreeTest, getLastComparedNode) {
+ RBTree<int>& tree = rbtree_expose_empty_node; // use the "empty OK" mode
+ RBTreeNodeChain<int> chain;
+
+ // initially there should be no 'last compared'.
+ EXPECT_EQ(static_cast<void*>(NULL), chain.getLastComparedNode());
+
+ // A search for an empty tree should result in no 'last compared', too.
+ RBTree<int> empty_tree;
+ EXPECT_EQ(RBTree<int>::NOTFOUND,
+ empty_tree.find<void*>(Name("a"), &crbtnode, chain, NULL, NULL));
+ EXPECT_EQ(static_cast<void*>(NULL), chain.getLastComparedNode());
+ chain.clear();
+
+ const RBNode<int>* expected_node;
+
+ // Exact match case. The returned node should be last compared.
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find<void*>(Name("x.d.e.f"), &expected_node, chain,
+ NULL, NULL));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // 2 = # labels of "x."
+ comparisonChecks(chain, 0, 2, NameComparisonResult::EQUAL);
+ chain.clear();
+
+ // Partial match, search stopped at the matching node, which should be
+ // the last compared node.
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find(Name("i.g.h"), &expected_node));
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ tree.find<void*>(Name("x.i.g.h"), &crbtnode, chain,
+ NULL, NULL));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // i.g.h < x.i.g.h, 2 = # labels of "i."
+ comparisonChecks(chain, 1, 2, NameComparisonResult::SUBDOMAIN);
+ chain.clear();
+
+ // Partial match, search stopped in the subtree below the matching node
+ // after following a left branch.
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find(Name("x.d.e.f"), &expected_node));
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ tree.find<void*>(Name("a.d.e.f"), &crbtnode, chain,
+ NULL, NULL));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // a < x, 1 = # labels of "." (trailing dot)
+ comparisonChecks(chain, -1, 1, NameComparisonResult::COMMONANCESTOR);
+ chain.clear();
+
+ // Partial match, search stopped in the subtree below the matching node
+ // after following a right branch.
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find(Name("z.d.e.f"), &expected_node));
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ tree.find<void*>(Name("zz.d.e.f"), &crbtnode, chain,
+ NULL, NULL));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // zz > z, 1 = # labels of "." (trailing dot)
+ comparisonChecks(chain, 1, 1, NameComparisonResult::COMMONANCESTOR);
+ chain.clear();
+
+ // Partial match, search stopped at a node for a super domain of the
+ // search name in the subtree below the matching node.
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find(Name("w.y.d.e.f"), &expected_node));
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ tree.find<void*>(Name("y.d.e.f"), &crbtnode, chain,
+ NULL, NULL));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // y < w.y, 2 = # labels of "y."
+ comparisonChecks(chain, -1, 2, NameComparisonResult::SUPERDOMAIN);
+ chain.clear();
+
+ // Partial match, search stopped at a node that share a common ancestor
+ // with the search name in the subtree below the matching node.
+ // (the expected node is the same as the previous case)
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ tree.find<void*>(Name("z.y.d.e.f"), &crbtnode, chain,
+ NULL, NULL));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // z.y > w.y, 2 = # labels of "y."
+ comparisonChecks(chain, 1, 2, NameComparisonResult::COMMONANCESTOR);
+ chain.clear();
+
+ // Search stops in the highest level after following a left branch.
+ EXPECT_EQ(RBTree<int>::EXACTMATCH, tree.find(Name("c"), &expected_node));
+ EXPECT_EQ(RBTree<int>::NOTFOUND,
+ tree.find<void*>(Name("bb"), &crbtnode, chain, NULL, NULL));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // bb < c, 1 = # labels of "." (trailing dot)
+ comparisonChecks(chain, -1, 1, NameComparisonResult::COMMONANCESTOR);
+ chain.clear();
+
+ // Search stops in the highest level after following a right branch.
+ // (the expected node is the same as the previous case)
+ EXPECT_EQ(RBTree<int>::NOTFOUND,
+ tree.find<void*>(Name("d"), &crbtnode, chain, NULL, NULL));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // d > c, 1 = # labels of "." (trailing dot)
+ comparisonChecks(chain, 1, 1, NameComparisonResult::COMMONANCESTOR);
+ chain.clear();
+}
+
TEST_F(RBTreeTest, dumpTree) {
std::ostringstream str;
std::ostringstream str2;
More information about the bind10-changes
mailing list