[svn] commit: r3486 - in /branches/trac397/src/bin/auth: rbt_datasrc.cc tests/rbt_datasrc_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Nov 8 06:34:44 UTC 2010
Author: chenzhengzhang
Date: Mon Nov 8 06:34:44 2010
New Revision: 3486
Log:
add unittest to improve test coverage
Modified:
branches/trac397/src/bin/auth/rbt_datasrc.cc
branches/trac397/src/bin/auth/tests/rbt_datasrc_unittest.cc
Modified: branches/trac397/src/bin/auth/rbt_datasrc.cc
==============================================================================
--- branches/trac397/src/bin/auth/rbt_datasrc.cc (original)
+++ branches/trac397/src/bin/auth/rbt_datasrc.cc Mon Nov 8 06:34:44 2010
@@ -203,8 +203,7 @@
*new_node = current;
/// if the node is non-ternimal, it doesn't exist, so we return 0
return (current->rrsets_.get() ? 1 : 0);
- }
- else {
+ } else {
int common_label_count = compare_result.getCommonLabels();
if (common_label_count == 1) {
order = compare_result.getOrder();
@@ -238,7 +237,7 @@
return (0);
} else {
current->is_nonterminal_ = true;
- return (current->down_->insert(name - common_ancestor, new_node));
+ return (current->down_->insert(name - common_ancestor, new_node));
}
}
}
@@ -426,8 +425,7 @@
if (y->color_ == BLACK)
deleteRebalance(x);
-
- if ( y == root_)
+ if (y == root_)
root_ = NULLNODE;
y->left_ = NULL;
@@ -443,7 +441,6 @@
while (node != root_ && node->color_ == BLACK) {
if (node == node->parent_->left_) {
w = node->parent_->right_;
-
if (w->color_ == RED) {
w->color_ = BLACK;
@@ -476,7 +473,9 @@
node->parent_->color_ = RED;
rightRotate(node->parent_);
w = node->parent_->left_;
- } if (w->right_->color_ == BLACK && w->left_->color_ == BLACK) {
+ }
+
+ if (w->right_->color_ == BLACK && w->left_->color_ == BLACK) {
w->color_ = RED;
node = node->parent_;
} else {
Modified: branches/trac397/src/bin/auth/tests/rbt_datasrc_unittest.cc
==============================================================================
--- branches/trac397/src/bin/auth/tests/rbt_datasrc_unittest.cc (original)
+++ branches/trac397/src/bin/auth/tests/rbt_datasrc_unittest.cc Mon Nov 8 06:34:44 2010
@@ -130,9 +130,10 @@
// not found
EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("x"), &rbtnode));
- EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("m.n"), &rbtnode));
+ EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("m.b"), &rbtnode));
EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("o.p.w.y.d.e.f"), &rbtnode));
EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("m.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("m.e.f"), &rbtnode));
// find referral
RRsetPtr rrset = RRsetPtr(new RRset(Name("d.e.f"), RRClass::IN(), RRType::NS(),
@@ -171,24 +172,43 @@
}
TEST_F(RBTreeTest, eraseName) {
+ EXPECT_EQ(0, rbtree.insert(Name("k"), &rbtnode));
EXPECT_EQ(0, rbtree.insert(Name("r.d.e.f"), &rbtnode));
EXPECT_EQ(0, rbtree.insert(Name("s.d.e.f"), &rbtnode));
- EXPECT_EQ(15, rbtree.getNodeCount());
+ EXPECT_EQ(0, rbtree.insert(Name("y"), &rbtnode));
+ EXPECT_EQ(17, rbtree.getNodeCount());
+ /*
+ * b
+ * / \
+ * a d.e.f
+ * / | \
+ * c | k
+ * | / \
+ * w.y g.h y
+ * / | \ |
+ * s | z i
+ * / \ | |
+ * r x p j
+ * / \
+ * o q
+ */
+
+ EXPECT_EQ(0, rbtree.erase(Name("a")));
+ EXPECT_EQ(0, rbtree.insert(Name("a"), &rbtnode));
+ EXPECT_EQ(0, rbtree.erase(Name("k")));
+ EXPECT_EQ(0, rbtree.erase(Name("y")));
// can't delete non terminal
- int ret = rbtree.erase(Name("d.e.f"));
- EXPECT_EQ(1, ret);
+ EXPECT_EQ(1, rbtree.erase(Name("d.e.f")));
EXPECT_EQ(RBTree::EXACTMATCH, rbtree.find(Name("w.y.d.e.f"), &rbtnode));
RRsetPtr rrset = RRsetPtr(new RRset(Name("w.y.d.e.f"), RRClass::IN(), RRType::A(),
RRTTL(3600)));
rbtnode->addRRset(rrset);
- ret = rbtree.erase(Name("p.w.y.d.e.f"));
- EXPECT_EQ(0, ret);
+ EXPECT_EQ(0, rbtree.erase(Name("p.w.y.d.e.f")));
EXPECT_EQ(14, rbtree.getNodeCount());
EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("p.w.y.d.e.f"), &rbtnode));
- ret = rbtree.erase(Name("q.w.y.d.e.f"));
- EXPECT_EQ(0, ret);
+ EXPECT_EQ(0, rbtree.erase(Name("q.w.y.d.e.f")));
EXPECT_EQ(13, rbtree.getNodeCount());
EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("q.w.y.d.e.f"), &rbtnode));
@@ -197,83 +217,156 @@
EXPECT_EQ(RBTree::EXACTMATCH, rbtree.find(Name("o.w.y.d.e.f"), &rbtnode));
EXPECT_EQ(RBTree::EXACTMATCH, rbtree.find(Name("w.y.d.e.f"), &rbtnode));
/*
- * b
- * / \
- * a d.e.f
+ * d.e.f
+ * / | \
+ * b | g.h
+ * / \ | |
+ * a c w.y i
* / | \
- * c | g.h
- * | |
- * w.y i
+ * s | z
+ * / \ | |
+ * r x o j
+ */
+ EXPECT_EQ(0, rbtree.erase(Name("o.w.y.d.e.f")));
+ EXPECT_EQ(12, rbtree.getNodeCount());
+ EXPECT_EQ(0, rbtree.erase(Name("w.y.d.e.f")));
+ EXPECT_EQ(11, rbtree.getNodeCount());
+ EXPECT_EQ(0, rbtree.erase(Name("x.d.e.f")));
+ EXPECT_EQ(10, rbtree.getNodeCount());
+ /*
+ * d.e.f
* / | \
- * s | z
- * / \ | |
- * r x o j
- */
- // z would be rejoined with d.e.f, since d.e.f has no data associated with the key
- ret = rbtree.erase(Name("o.w.y.d.e.f"));
-
- EXPECT_EQ(0, ret);
- EXPECT_EQ(12, rbtree.getNodeCount());
- ret = rbtree.erase(Name("w.y.d.e.f"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(11, rbtree.getNodeCount());
- ret = rbtree.erase(Name("x.d.e.f"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(10, rbtree.getNodeCount());
- /*
- * b
- * / \
- * a d.e.f
- * / | \
- * c s g.h
- * / \ |
- * r z i
- * |
- * j
- */
- // erase a non-exist node
- ret = rbtree.erase(Name("x.d.e.f"));
- EXPECT_EQ(1, ret);
-
- // delete all the nodes one by one
- ret = rbtree.erase(Name("c"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(9, rbtree.getNodeCount());
- ret = rbtree.erase(Name("g.h"));
- EXPECT_EQ(1, ret);
- EXPECT_EQ(9, rbtree.getNodeCount());
- ret = rbtree.erase(Name("a"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(8, rbtree.getNodeCount());
- ret = rbtree.erase(Name("b"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(7, rbtree.getNodeCount());
- ret = rbtree.erase(Name("i.g.h"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(6, rbtree.getNodeCount());
- /*
- * d.e.f
- * | \
- * s g.h
+ * b | g.h
+ * / \ | |
+ * a c s i
* / \
* r z
* |
* j
*/
- ret = rbtree.erase(Name("r.d.e.f"));
- EXPECT_EQ(0, ret);
+ // erase a non-exist node
+ EXPECT_EQ(1, rbtree.erase(Name("x.d.e.f")));
+ // delete all the nodes one by one
+ EXPECT_EQ(0, rbtree.erase(Name("c")));
+ EXPECT_EQ(9, rbtree.getNodeCount());
+ EXPECT_EQ(1, rbtree.erase(Name("g.h")));
+ EXPECT_EQ(9, rbtree.getNodeCount());
+ EXPECT_EQ(0, rbtree.erase(Name("a")));
+ EXPECT_EQ(8, rbtree.getNodeCount());
+ EXPECT_EQ(0, rbtree.erase(Name("b")));
+ EXPECT_EQ(7, rbtree.getNodeCount());
+ EXPECT_EQ(0, rbtree.erase(Name("i.g.h")));
+ EXPECT_EQ(6, rbtree.getNodeCount());
+ /*
+ * d.e.f
+ * | \
+ * | g.h
+ * |
+ * s
+ * / \
+ * r z
+ * |
+ * j
+ */
+ // can't delete non-terminal node
+ EXPECT_EQ(1, rbtree.erase(Name("z.d.e.f")));
+ EXPECT_EQ(6, rbtree.getNodeCount());
+ EXPECT_EQ(0, rbtree.erase(Name("j.z.d.e.f")));
EXPECT_EQ(5, rbtree.getNodeCount());
- ret = rbtree.erase(Name("j.z.d.e.f"));
- EXPECT_EQ(0, ret);
+ EXPECT_EQ(0, rbtree.erase(Name("r.d.e.f")));
EXPECT_EQ(4, rbtree.getNodeCount());
- ret = rbtree.erase(Name("z.d.e.f"));
- EXPECT_EQ(0, ret);
+ // z will rejoin with d.e.f since d.e.f has no data
+ EXPECT_EQ(0, rbtree.erase(Name("s.d.e.f")));
EXPECT_EQ(2, rbtree.getNodeCount());
- ret = rbtree.erase(Name("s.d.e.f"));
- EXPECT_EQ(0, ret);
+ /*
+ * z.d.e.f
+ * \
+ * g.h
+ */
+
+ EXPECT_EQ(0, rbtree.erase(Name("g.h")));
EXPECT_EQ(1, rbtree.getNodeCount());
- ret = rbtree.erase(Name("g.h"));
- EXPECT_EQ(0, ret);
+
+ // rebuild rbtree to cover different execution paths
+ EXPECT_EQ(0, rbtree.insert(Name("a"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("g"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("b"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("d"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("c"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("e"), &rbtnode));
+ /*
+ * z.d.e.f
+ * / \
+ * b g
+ * / \
+ * a d
+ * / \
+ * c e
+ */
+ EXPECT_EQ(0, rbtree.erase(Name("g")));
+ EXPECT_EQ(0, rbtree.erase(Name("z.d.e.f")));
+ EXPECT_EQ(5, rbtree.getNodeCount());
+
+ EXPECT_EQ(0, rbtree.insert(Name("da"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("aa"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("ba"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("ca"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("m"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("nm"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("om"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("da"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("k"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("l"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("fe"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("ge"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("i"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("ae"), &rbtnode));
+ EXPECT_EQ(0, rbtree.insert(Name("n"), &rbtnode));
+ EXPECT_EQ(19, rbtree.getNodeCount());
+ /*
+ * d
+ * / \
+ * b c
+ * / \ / \
+ * aa c e nm
+ * / \ / \ / \ /\
+ * a ae ba ca da ge m om
+ * / \ \
+ * fe k n
+ * /
+ * i
+ */
+ // delete rbtree node one by one
+ EXPECT_EQ(0, rbtree.erase(Name("nm")));
+ EXPECT_EQ(0, rbtree.erase(Name("n")));
+ EXPECT_EQ(0, rbtree.erase(Name("a")));
+ EXPECT_EQ(0, rbtree.erase(Name("ae")));
+ EXPECT_EQ(0, rbtree.erase(Name("i")));
+ EXPECT_EQ(0, rbtree.erase(Name("aa")));
+ EXPECT_EQ(0, rbtree.erase(Name("e")));
+ EXPECT_EQ(0, rbtree.erase(Name("ge")));
+ EXPECT_EQ(0, rbtree.erase(Name("k")));
+ EXPECT_EQ(0, rbtree.erase(Name("m")));
+ EXPECT_EQ(9, rbtree.getNodeCount());
+ /*
+ * d
+ * / \
+ * c c
+ * / \ / \
+ * b ca fe om
+ * \ /
+ * ba da
+ */
+ EXPECT_EQ(1, rbtree.erase(Name("am")));
+ EXPECT_EQ(0, rbtree.erase(Name("fe")));
+ EXPECT_EQ(0, rbtree.erase(Name("da")));
+ EXPECT_EQ(0, rbtree.erase(Name("om")));
+ EXPECT_EQ(0, rbtree.erase(Name("d")));
+ EXPECT_EQ(0, rbtree.erase(Name("b")));
+ EXPECT_EQ(0, rbtree.erase(Name("ba")));
+ EXPECT_EQ(0, rbtree.erase(Name("ca")));
+ EXPECT_EQ(0, rbtree.erase(Name("c")));
+ EXPECT_EQ(0, rbtree.erase(Name("l")));
EXPECT_EQ(0, rbtree.getNodeCount());
}
More information about the bind10-changes
mailing list