[svn] commit: r3457 - in /branches/trac397/src/bin/auth: auth_srv.cc rbt_datasrc.cc rbt_datasrc.h tests/rbt_datasrc_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Fri Nov 5 07:01:13 UTC 2010
Author: chenzhengzhang
Date: Fri Nov 5 07:01:13 2010
New Revision: 3457
Log:
add more unittest for rbtree
Modified:
branches/trac397/src/bin/auth/auth_srv.cc
branches/trac397/src/bin/auth/rbt_datasrc.cc
branches/trac397/src/bin/auth/rbt_datasrc.h
branches/trac397/src/bin/auth/tests/rbt_datasrc_unittest.cc
Modified: branches/trac397/src/bin/auth/auth_srv.cc
==============================================================================
--- branches/trac397/src/bin/auth/auth_srv.cc (original)
+++ branches/trac397/src/bin/auth/auth_srv.cc Fri Nov 5 07:01:13 2010
@@ -435,7 +435,7 @@
}
return (false);
}
-
+
const string remote_ip_address =
io_message.getRemoteEndpoint().getAddress().toText();
static const string command_template_start =
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 Fri Nov 5 07:01:13 2010
@@ -46,7 +46,7 @@
delete down_;
}
-RBNode*
+RBNode*
RBNode::successor() {
RBNode* current = this;
@@ -128,14 +128,14 @@
root_ = NULL;
}
-RBTree::FindResult
+RBTree::FindResult
RBTree::find(const Name &name, RBNode **node)const {
RBTree *tree;
return findHelper(name, &tree, node);
}
-RBTree::FindResult
+RBTree::FindResult
RBTree::findHelper(const Name &name, RBTree **tree, RBNode **ret)const {
RBNode* node = root_;
while (node != NULLNODE) {
@@ -187,7 +187,7 @@
return 1 + sub_tree_node_count + getNodeCountHelper(node->left_) + getNodeCountHelper(node->right_);
}
-int
+int
RBTree::insert(const Name &name, RBNode **new_node) {
RBNode* parent = NULLNODE;
RBNode* current = root_;
@@ -262,7 +262,7 @@
return 0;
}
-void
+void
RBTree::insertRebalance(RBNode * node) {
RBNode* uncle;
@@ -313,7 +313,7 @@
}
-RBNode*
+RBNode*
RBTree::leftRotate(RBNode * p) {
RBNode* c = p->right_;
@@ -337,7 +337,7 @@
return c;
}
-RBNode*
+RBNode*
RBTree::rightRotate(RBNode * p) {
RBNode* c = p->left_;
@@ -362,7 +362,7 @@
}
-int
+int
RBTree::erase(const Name &name) {
RBNode *node;
RBTree *tree;
@@ -393,7 +393,7 @@
}
-void
+void
RBTree::eraseNode(RBNode *node) {
RBNode* y = NULLNODE;
RBNode* x = NULLNODE;
@@ -436,7 +436,7 @@
--node_count_;
}
-void
+void
RBTree::deleteRebalance(RBNode * node) {
RBNode* w = NULLNODE;
Modified: branches/trac397/src/bin/auth/rbt_datasrc.h
==============================================================================
--- branches/trac397/src/bin/auth/rbt_datasrc.h (original)
+++ branches/trac397/src/bin/auth/rbt_datasrc.h Fri Nov 5 07:01:13 2010
@@ -74,7 +74,7 @@
};
/// RBTree is a generic red black tree, it contains all the node with same suffix
-/// So for one zone, severl RBTrees are involved. But from outside, the sub tree is
+/// So for one zone, severl RBTrees are involved. But from outside, the sub tree is
/// opaque for end user. if the sub tree only has one node and the base node which is pointed by the
/// "up_" pointer is one non-terminal, the single node will merge with the "up_" node then the sub tree will
/// be deleted
@@ -95,10 +95,10 @@
/// the interface just used for test the tree logic, later will be removed
int getNodeCount() const;
-
+
void printTree(int depth = 0)const;
-
- /// if the name exists, return value will be one, and inserted_node will point to
+
+ /// if the name exists, return value will be one, and inserted_node will point to
/// the existed node, otherwise return value is zero, and inserted_node points to
/// new created node
int insert(const Name &name, RBNode **inserted_node);
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 Fri Nov 5 07:01:13 2010
@@ -34,14 +34,14 @@
* b
* / \
* a d.e.f
- * / | \
- * c | g.h
- * |
- * w.y
- * / | \
- * x | z
- * |
- * p
+ * / | \
+ * c | g.h
+ * | |
+ * w.y i
+ * / | \
+ * x | z
+ * | |
+ * p j
* / \
* o q
*/
@@ -57,7 +57,9 @@
rbtree.insert(Name("x.d.e.f"), &rbtnode);
rbtree.insert(Name("z.d.e.f"), &rbtnode);
rbtree.insert(Name("g.h"), &rbtnode);
+ rbtree.insert(Name("i.g.h"), &rbtnode);
rbtree.insert(Name("o.w.y.d.e.f"), &rbtnode);
+ rbtree.insert(Name("j.z.d.e.f"), &rbtnode);
rbtree.insert(Name("p.w.y.d.e.f"), &rbtnode);
rbtree.insert(Name("q.w.y.d.e.f"), &rbtnode);
}
@@ -67,41 +69,54 @@
TEST_F(RBTreeTest, getNodeCount) {
- EXPECT_EQ(11, rbtree.getNodeCount());
+ EXPECT_EQ(13, rbtree.getNodeCount());
}
TEST_F(RBTreeTest, insertNames) {
// a node is considered to "formally" exist only if it has data
// associated with it
+ // EXPECT_EQ(0, rbtree.insert(Name("r"), &rbtnode));
// return 0, since node "d.e.f" doesn't have data
EXPECT_EQ(0, rbtree.insert(Name("d.e.f"), &rbtnode));
EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
- EXPECT_EQ(11, rbtree.getNodeCount());
+ EXPECT_EQ(13, rbtree.getNodeCount());
EXPECT_EQ(0, rbtree.insert(Name("."), &rbtnode));
EXPECT_EQ(Name("."), rbtnode->getName());
- EXPECT_EQ(12, rbtree.getNodeCount());
+ EXPECT_EQ(14, rbtree.getNodeCount());
EXPECT_EQ(0, rbtree.insert(Name("example.com"), &rbtnode));
- EXPECT_EQ(13, rbtree.getNodeCount());
+ EXPECT_EQ(15, rbtree.getNodeCount());
// return 1, since node "d.e.f" already has data associated with it
RRsetPtr rrset = RRsetPtr(new RRset(Name("example.com"), RRClass::IN(), RRType::NS(),
RRTTL(3600)));
rbtnode->addRRset(rrset);
EXPECT_EQ(1, rbtree.insert(Name("example.com"), &rbtnode));
- EXPECT_EQ(13, rbtree.getNodeCount());
+ EXPECT_EQ(15, rbtree.getNodeCount());
// split the node "d.e.f"
EXPECT_EQ(0, rbtree.insert(Name("k.e.f"), &rbtnode));
EXPECT_EQ(Name("k"), rbtnode->getName());
- EXPECT_EQ(15, rbtree.getNodeCount());
+ EXPECT_EQ(17, rbtree.getNodeCount());
// split the node "g.h"
EXPECT_EQ(0, rbtree.insert(Name("h"), &rbtnode));
EXPECT_EQ(Name("h"), rbtnode->getName());
- EXPECT_EQ(16, rbtree.getNodeCount());
+ EXPECT_EQ(18, rbtree.getNodeCount());
+
+ // add child domain
+ EXPECT_EQ(0, rbtree.insert(Name("m.p.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(Name("m"), rbtnode->getName());
+ EXPECT_EQ(19, rbtree.getNodeCount());
+ EXPECT_EQ(0, rbtree.insert(Name("n.p.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(Name("n"), rbtnode->getName());
+ EXPECT_EQ(20, rbtree.getNodeCount());
+
+ EXPECT_EQ(0, rbtree.insert(Name("l.a"), &rbtnode));
+ EXPECT_EQ(Name("l"), rbtnode->getName());
+ EXPECT_EQ(21, rbtree.getNodeCount());
}
TEST_F(RBTreeTest, findName) {
@@ -114,7 +129,8 @@
// 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.d.e.f"), &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));
// find referral
RRsetPtr rrset = RRsetPtr(new RRset(Name("d.e.f"), RRClass::IN(), RRType::NS(),
@@ -124,20 +140,51 @@
EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
}
+TEST_F(RBTreeTest, successor) {
+ // traverse the trees
+ EXPECT_EQ(RBTree::EXACTMATCH, rbtree.find(Name("a"), &rbtnode));
+ RBNode *successor_node = rbtnode->successor();
+ EXPECT_EQ(Name("b"), successor_node->getName());
+ successor_node = successor_node->successor();
+ EXPECT_EQ(Name("c"), successor_node->getName());
+ successor_node = successor_node->successor();
+ EXPECT_EQ(Name("d.e.f"), successor_node->getName());
+ successor_node = successor_node->successor();
+ EXPECT_EQ(Name("g.h"), successor_node->getName());
+ successor_node = successor_node->successor();
+
+ EXPECT_EQ(RBTree::EXACTMATCH, rbtree.find(Name("x.d.e.f"), &rbtnode));
+ EXPECT_EQ(Name("x"), rbtnode->getName());
+ successor_node = rbtnode->successor();
+ EXPECT_EQ(Name("w.y"), successor_node->getName());
+ successor_node = successor_node->successor();
+ EXPECT_EQ(Name("z"), successor_node->getName());
+
+ EXPECT_EQ(RBTree::EXACTMATCH, rbtree.find(Name("o.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(Name("o"), rbtnode->getName());
+ successor_node = rbtnode->successor();
+ EXPECT_EQ(Name("p"), successor_node->getName());
+ successor_node = successor_node->successor();
+ EXPECT_EQ(Name("q"), successor_node->getName());
+}
+
TEST_F(RBTreeTest, eraseName) {
- EXPECT_EQ(11, rbtree.getNodeCount());
+ EXPECT_EQ(13, rbtree.getNodeCount());
+ // can't delete non terminal
+ int ret = rbtree.erase(Name("d.e.f"));
+ EXPECT_EQ(1, ret);
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);
- int ret = rbtree.erase(Name("p.w.y.d.e.f"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(10, rbtree.getNodeCount());
+ ret = rbtree.erase(Name("p.w.y.d.e.f"));
+ EXPECT_EQ(0, ret);
+ EXPECT_EQ(12, 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(9, rbtree.getNodeCount());
+ EXPECT_EQ(11, rbtree.getNodeCount());
EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("q.w.y.d.e.f"), &rbtnode));
// o would not be rejoined with w.y if w.y had data
@@ -150,30 +197,32 @@
* a d.e.f
* / | \
* c | g.h
- * |
- * w.y
+ * | |
+ * w.y i
* / | \
* x | z
- * |
- * o
+ * | |
+ * 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(8, rbtree.getNodeCount());
+
+ EXPECT_EQ(0, ret);
+ EXPECT_EQ(10, rbtree.getNodeCount());
ret = rbtree.erase(Name("w.y.d.e.f"));
EXPECT_EQ(0, ret);
+ EXPECT_EQ(9, rbtree.getNodeCount());
+ ret = rbtree.erase(Name("x.d.e.f"));
+ EXPECT_EQ(0, ret);
EXPECT_EQ(7, rbtree.getNodeCount());
- ret = rbtree.erase(Name("x.d.e.f"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(5, rbtree.getNodeCount());
/*
* b
* / \
* a z.d.e.f
- * / \
- * c g.h
- *
+ * / | \
+ * c j g.h
+ * |
+ * i
*/
// erase a non-exist node
ret = rbtree.erase(Name("x.d.e.f"));
@@ -182,14 +231,23 @@
// delete all the nodes one by one
ret = rbtree.erase(Name("a"));
EXPECT_EQ(0, ret);
+ EXPECT_EQ(6, rbtree.getNodeCount());
+ ret = rbtree.erase(Name("g.h"));
+ EXPECT_EQ(1, ret);
+ EXPECT_EQ(6, rbtree.getNodeCount());
+ ret = rbtree.erase(Name("c"));
+ EXPECT_EQ(0, ret);
+ EXPECT_EQ(5, rbtree.getNodeCount());
+ ret = rbtree.erase(Name("b"));
+ EXPECT_EQ(0, ret);
EXPECT_EQ(4, rbtree.getNodeCount());
+ ret = rbtree.erase(Name("i.g.h"));
+ EXPECT_EQ(0, ret);
+ EXPECT_EQ(3, rbtree.getNodeCount());
+ ret = rbtree.erase(Name("j.z.d.e.f"));
+ EXPECT_EQ(0, ret);
+ EXPECT_EQ(2, rbtree.getNodeCount());
ret = rbtree.erase(Name("g.h"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(3, rbtree.getNodeCount());
- ret = rbtree.erase(Name("b"));
- EXPECT_EQ(0, ret);
- EXPECT_EQ(2, rbtree.getNodeCount());
- ret = rbtree.erase(Name("c"));
EXPECT_EQ(0, ret);
EXPECT_EQ(1, rbtree.getNodeCount());
ret = rbtree.erase(Name("z.d.e.f"));
More information about the bind10-changes
mailing list