BIND 10 master, updated. c7a5a56e8269ad841c1b43a635fc3c49ea254638 [1971] Fix broken tree structure that didn't match the one in the figure
BIND 10 source code commits
bind10-changes at lists.isc.org
Tue May 15 20:03:04 UTC 2012
The branch, master has been updated
via c7a5a56e8269ad841c1b43a635fc3c49ea254638 (commit)
via 39b658ef4f5b272f727eb501d68caa30d9a5ebc3 (commit)
via e401615079a02327a9803abc01ab0cb2e36000fb (commit)
via 94a2da0d06d02d1d5991e0f8d6cb19bed1e5d665 (commit)
via 3692c48386327df01b447308fb39ca748c451f47 (commit)
via 74ac6abb7e9bdf613d5aa6c93426ff7bf9f671ad (commit)
from a807c0d3ef2c845efdc1dae050cf52f951c21cbf (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 c7a5a56e8269ad841c1b43a635fc3c49ea254638
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue May 15 21:26:53 2012 +0530
[1971] Fix broken tree structure that didn't match the one in the figure
commit 39b658ef4f5b272f727eb501d68caa30d9a5ebc3
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon May 14 13:15:20 2012 +0530
[1971] Update test rbtree (of rbtrees) to suit our right-child testcase
commit e401615079a02327a9803abc01ab0cb2e36000fb
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon May 14 12:52:45 2012 +0530
[master] Remove duplicate data
commit 94a2da0d06d02d1d5991e0f8d6cb19bed1e5d665
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon May 14 12:17:52 2012 +0530
[1971] Add another testcase for untested code detected by lcov
When find() returns COMMONANCESTOR and exits to the right of a
last_compared_node which has a valid down pointer, previousNode() has to
return nodes beginning at at the right-most leaf of subtrees in
last_compared_node->down.
commit 3692c48386327df01b447308fb39ca748c451f47
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon May 14 12:08:20 2012 +0530
[1971] Test the node_path.isEmpty() check
If previousNode() has been called enough times that it has popped
all nodes from the node chain when walking up the trees, the
node chain is then empty. If previousNode() is called yet again
on the empty tree, it should return NULL.
commit 74ac6abb7e9bdf613d5aa6c93426ff7bf9f671ad
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon May 14 10:54:01 2012 +0530
[master] Update .gitignore
-----------------------------------------------------------------------
Summary of changes:
.gitignore | 6 ++
src/lib/datasrc/tests/rbtree_unittest.cc | 76 +++++++++++++++++++----------
2 files changed, 56 insertions(+), 26 deletions(-)
-----------------------------------------------------------------------
diff --git a/.gitignore b/.gitignore
index da9d3b4..3480cb6 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,6 @@
+*.gcda
+*.gcno
+*.gcov
*.la
*.lo
*.o
@@ -28,4 +31,7 @@ TAGS
/py-compile
/stamp-h1
+/all.info
+/coverage-cpp-html
/dns++.pc
+/report.info
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 25eafb4..a11bff5 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -45,8 +45,8 @@ const size_t Name::MAX_LABELS;
* c | g.h
* | |
* w.y i
- * / | \
- * x | z
+ * / | \ \
+ * x | z k
* | |
* p j
* / \
@@ -59,7 +59,7 @@ protected:
RBTreeTest() : rbtree_expose_empty_node(true), crbtnode(NULL) {
const char* const domain_names[] = {
"c", "b", "a", "x.d.e.f", "z.d.e.f", "g.h", "i.g.h", "o.w.y.d.e.f",
- "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f"};
+ "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f", "k.g.h"};
int name_count = sizeof(domain_names) / sizeof(domain_names[0]);
for (int i = 0; i < name_count; ++i) {
rbtree.insert(Name(domain_names[i]), &rbtnode);
@@ -79,7 +79,7 @@ protected:
TEST_F(RBTreeTest, getNodeCount) {
- EXPECT_EQ(13, rbtree.getNodeCount());
+ EXPECT_EQ(14, rbtree.getNodeCount());
}
TEST_F(RBTreeTest, setGetData) {
@@ -91,46 +91,46 @@ TEST_F(RBTreeTest, insertNames) {
EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("d.e.f"),
&rbtnode));
EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
- EXPECT_EQ(13, rbtree.getNodeCount());
+ EXPECT_EQ(14, rbtree.getNodeCount());
//insert not exist node
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("."), &rbtnode));
EXPECT_EQ(Name("."), rbtnode->getName());
- EXPECT_EQ(14, rbtree.getNodeCount());
+ EXPECT_EQ(15, rbtree.getNodeCount());
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("example.com"), &rbtnode));
- EXPECT_EQ(15, rbtree.getNodeCount());
+ EXPECT_EQ(16, rbtree.getNodeCount());
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(12)));
// return ALREADYEXISTS, since node "example.com" already has been explicitly inserted
EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("example.com"), &rbtnode));
- EXPECT_EQ(15, rbtree.getNodeCount());
+ EXPECT_EQ(16, rbtree.getNodeCount());
// split the node "d.e.f"
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("k.e.f"), &rbtnode));
EXPECT_EQ(Name("k"), rbtnode->getName());
- EXPECT_EQ(17, rbtree.getNodeCount());
+ EXPECT_EQ(18, rbtree.getNodeCount());
// split the node "g.h"
EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("h"), &rbtnode));
EXPECT_EQ(Name("h"), rbtnode->getName());
- EXPECT_EQ(18, rbtree.getNodeCount());
+ EXPECT_EQ(19, rbtree.getNodeCount());
// add child domain
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("m.p.w.y.d.e.f"), &rbtnode));
EXPECT_EQ(Name("m"), rbtnode->getName());
- EXPECT_EQ(19, rbtree.getNodeCount());
+ EXPECT_EQ(20, rbtree.getNodeCount());
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("n.p.w.y.d.e.f"), &rbtnode));
EXPECT_EQ(Name("n"), rbtnode->getName());
- EXPECT_EQ(20, rbtree.getNodeCount());
+ EXPECT_EQ(21, rbtree.getNodeCount());
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("l.a"), &rbtnode));
EXPECT_EQ(Name("l"), rbtnode->getName());
- EXPECT_EQ(21, rbtree.getNodeCount());
+ EXPECT_EQ(22, rbtree.getNodeCount());
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("r.d.e.f"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("s.d.e.f"), &rbtnode));
- EXPECT_EQ(23, rbtree.getNodeCount());
+ EXPECT_EQ(24, rbtree.getNodeCount());
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("h.w.y.d.e.f"), &rbtnode));
@@ -323,7 +323,7 @@ TEST_F(RBTreeTest, getAbsoluteNameError) {
/*
*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
+ * z.d.e.f, j.z.d.e.f, g.h, i.g.h, k.g.h
* b
* / \
* a d.e.f
@@ -331,8 +331,8 @@ TEST_F(RBTreeTest, getAbsoluteNameError) {
* c | g.h
* | |
* w.y i
- * / | \
- * x | z
+ * / | \ \
+ * x | z k
* | |
* p j
* / \
@@ -340,14 +340,11 @@ TEST_F(RBTreeTest, getAbsoluteNameError) {
*/
const char* const names[] = {
"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"};
+ "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"};
const size_t name_count(sizeof(names) / sizeof(*names));
TEST_F(RBTreeTest, nextNode) {
- const char* const names[] = {
- "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"};
- const int name_count = sizeof(names) / sizeof(names[0]);
RBTreeNodeChain<int> node_path;
const RBNode<int>* node = NULL;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
@@ -405,6 +402,11 @@ previousWalk(RBTree<int>& rbtree, const RBNode<int>* node,
// We should have reached the start of the tree.
EXPECT_EQ(static_cast<void*>(NULL), node);
+
+ // Calling previousNode() yet again should still return NULL without
+ // fail.
+ node = rbtree.previousNode(node_path);
+ EXPECT_EQ(static_cast<void*>(NULL), node);
}
// Check the previousNode
@@ -506,6 +508,28 @@ TEST_F(RBTreeTest, previousNode) {
}
{
+ SCOPED_TRACE("Start to the right of a parent");
+ // When searching for this, we exit the 'g.h' node to the right
+ // side, so we should go to g.h's children afterwards.
+
+ // 'g.h' is an empty node, so we get a NOTFOUND and not
+ // PARTIALMATCH.
+ EXPECT_EQ(RBTree<int>::NOTFOUND,
+ rbtree.find(Name("x.h"), &node, node_path));
+ // 'g.h' is the COMMONANCESTOR.
+ EXPECT_EQ(node_path.getLastComparedNode()->getName(), Name("g.h"));
+ EXPECT_EQ(NameComparisonResult::COMMONANCESTOR,
+ node_path.getLastComparisonResult().getRelation());
+ // find() exits to the right of 'g.h'
+ EXPECT_GT(node_path.getLastComparisonResult().getOrder(), 0);
+ // We then descend into 'i.g.h' and walk all the nodes in the
+ // tree.
+ previousWalk(rbtree, node, node_path, name_count, true);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
SCOPED_TRACE("Start inside a wrong node");
// The d.e.f is a single node, but we want only part of it. We
// should start iterating before it.
@@ -582,11 +606,11 @@ TEST_F(RBTreeTest, getLastComparedNode) {
// 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));
+ tree.find(Name("k.g.h"), &expected_node));
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
- tree.find(Name("x.i.g.h"), &crbtnode, chain));
+ tree.find(Name("x.k.g.h"), &crbtnode, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
- // i.g.h < x.i.g.h, 2 = # labels of "i."
+ // k.g.h < x.k.g.h, 2 = # labels of "k."
comparisonChecks(chain, 1, 2, NameComparisonResult::SUBDOMAIN);
chain.clear();
@@ -656,7 +680,7 @@ TEST_F(RBTreeTest, dumpTree) {
std::ostringstream str;
std::ostringstream str2;
rbtree.dumpTree(str);
- str2 << "tree has 13 node(s)\nb. (black)\n a. (black)\n NULL\n NULL\n d.e.f. (black)[invisible] \n begin down from d.e.f.\n w.y. (black)[invisible] \n begin down from w.y.\n p. (black)\n o. (red)\n NULL\n NULL\n q. (red)\n NULL\n NULL\n end down from w.y.\n x. (red)\n NULL\n NULL\n z. (red)\n begin down from z.\n j. (black)\n NULL\n NULL\n end down from z.\n NULL\n NULL\n end down from d.e.f.\n c. (red)\n NULL\n NULL\n g.h. (red)\n begin down from g.h.\n i. (black)\n
NULL\n NULL\n end down from g.h.\n NULL\n NULL\n";
+ str2 << "tree has 14 node(s)\nb. (black)\n a. (black)\n NULL\n NULL\n d.e.f. (black)[invisible] \n begin down from d.e.f.\n w.y. (black)[invisible] \n begin down from w.y.\n p. (black)\n o. (red)\n NULL\n NULL\n q. (red)\n NULL\n NULL\n end down from w.y.\n x. (red)\n NULL\n NULL\n z. (red)\n begin down from z.\n j. (black)\n NULL\n NULL\n end down from z.\n NULL\n NULL\n end down from d.e.f.\n c. (red)\n NULL\n NULL\n g.h. (red)\n begin down from g.h.\n i. (black)\n
NULL\n k. (red)\n NULL\n NULL\n end down from g.h.\n NULL\n NULL\n";
EXPECT_EQ(str.str(), str2.str());
}
More information about the bind10-changes
mailing list