BIND 10 master, updated. 420ec42bd913fb83da37b26b75faae49c7957c46 Merge branch 'trac683'
BIND 10 source code commits
bind10-changes at lists.isc.org
Thu Mar 10 18:23:25 UTC 2011
The branch, master has been updated
via 420ec42bd913fb83da37b26b75faae49c7957c46 (commit)
via bf0b8426e2d05c1fc30a2b29929531c430f8bcda (commit)
from 1ecb969fc160370724527c3e2e1812463f2398ca (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 420ec42bd913fb83da37b26b75faae49c7957c46
Merge: 1ecb969 bf0b842
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Thu Mar 10 10:18:06 2011 -0800
Merge branch 'trac683'
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/rbtree.h | 23 ++++++++-----
src/lib/datasrc/tests/rbtree_unittest.cc | 52 ++++++++++++++++++++++++++---
2 files changed, 60 insertions(+), 15 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index bd04066..03a6967 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -533,12 +533,9 @@ private:
private:
// The max label count for one domain name is Name::MAX_LABELS (128).
- // Since each node in rbtree stores at least one label, and the root
- // name always shares the same level with some others (which means
- // all top level nodes except the one for the root name contain at least
- // two labels), the possible maximum level is MAX_LABELS - 1.
- // It's also the possible maximum nodes stored in a chain.
- const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS - 1;
+ // Since each node in rbtree stores at least one label, it's also equal
+ // to the possible maximum level.
+ const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS;
int node_count_;
const RBNode<T>* nodes_[RBT_MAX_LEVEL];
@@ -999,8 +996,15 @@ RBTree<T>::find(const isc::dns::Name& target_name,
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) {
+ // the two names, except the trailing "dot". In this case the two
+ // sequences of labels have essentially no hierarchical
+ // relationship in terms of matching, so we should continue the
+ // binary search. One important exception is when the node
+ // represents the root name ("."), in which case the comparison
+ // result must indeed be considered subdomain matching. (We use
+ // getLength() to check if the name is root, which is an equivalent
+ // but cheaper way).
+ if (common_label_count == 1 && node->name_.getLength() != 1) {
node = (node_path.last_comparison_.getOrder() < 0) ?
node->left_ : node->right_;
} else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
@@ -1093,7 +1097,8 @@ RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
return (ALREADYEXISTS);
} else {
const int common_label_count = compare_result.getCommonLabels();
- if (common_label_count == 1) {
+ // Note: see find() for the check of getLength().
+ if (common_label_count == 1 && current->name_.getLength() != 1) {
parent = current;
order = compare_result.getOrder();
current = order < 0 ? current->left_ : current->right_;
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 23b25f4..dd1b7fe 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -284,21 +284,21 @@ TEST_F(RBTreeTest, chainLevel) {
EXPECT_EQ(1, chain.getLevelCount());
/*
- * Now creating a possibly deepest tree with MAX_LABELS - 1 levels.
+ * Now creating a possibly deepest tree with MAX_LABELS levels.
* it should look like:
+ * (.)
+ * |
* a
- * /|
- * (.)a
* |
* a
* : (MAX_LABELS - 1) "a"'s
*
* then confirm that find() for the deepest name succeeds without any
* disruption, and the resulting chain has the expected level.
- * Note that "a." and the root name (".") belong to the same level.
- * So the possible maximum level is MAX_LABELS - 1, not MAX_LABELS.
+ * Note that the root name (".") solely belongs to a single level,
+ * so the levels begin with 2.
*/
- for (unsigned int i = 1; i < Name::MAX_LABELS; ++i) {
+ for (unsigned int i = 2; i <= Name::MAX_LABELS; ++i) {
node_name = Name("a.").concatenate(node_name);
EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
RBTreeNodeChain<int> found_chain;
@@ -523,4 +523,44 @@ TEST_F(RBTreeTest, swap) {
tree2.dumpTree(out);
ASSERT_EQ(str1.str(), out.str());
}
+
+// Matching in the "root zone" may be special (e.g. there's no parent,
+// any domain names should be considered a subdomain of it), so it makes
+// sense to test cases with the root zone explicitly.
+TEST_F(RBTreeTest, root) {
+ RBTree<int> root;
+ root.insert(Name::ROOT_NAME(), &rbtnode);
+ rbtnode->setData(RBNode<int>::NodeDataPtr(new int(1)));
+
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ root.find(Name::ROOT_NAME(), &crbtnode));
+ EXPECT_EQ(rbtnode, crbtnode);
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ root.find(Name("example.com"), &crbtnode));
+ EXPECT_EQ(rbtnode, crbtnode);
+
+ // Insert a new name that better matches the query name. find() should
+ // find the better one.
+ root.insert(Name("com"), &rbtnode);
+ rbtnode->setData(RBNode<int>::NodeDataPtr(new int(2)));
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ root.find(Name("example.com"), &crbtnode));
+ EXPECT_EQ(rbtnode, crbtnode);
+
+ // Perform the same tests for the tree that allows matching against empty
+ // nodes.
+ RBTree<int> root_emptyok(true);
+ root_emptyok.insert(Name::ROOT_NAME(), &rbtnode);
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ root_emptyok.find(Name::ROOT_NAME(), &crbtnode));
+ EXPECT_EQ(rbtnode, crbtnode);
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ root_emptyok.find(Name("example.com"), &crbtnode));
+ EXPECT_EQ(rbtnode, crbtnode);
+
+ root.insert(Name("com"), &rbtnode);
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ root.find(Name("example.com"), &crbtnode));
+ EXPECT_EQ(rbtnode, crbtnode);
+}
}
More information about the bind10-changes
mailing list