[svn] commit: r4074 - in /branches/trac461/src/lib/datasrc: rbtree.h tests/rbtree_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Wed Dec 29 10:30:53 UTC 2010
Author: hanfeng
Date: Wed Dec 29 10:30:53 2010
New Revision: 4074
Log:
add return non-empty node support
Modified:
branches/trac461/src/lib/datasrc/rbtree.h
branches/trac461/src/lib/datasrc/tests/rbtree_unittest.cc
Modified: branches/trac461/src/lib/datasrc/rbtree.h
==============================================================================
--- branches/trac461/src/lib/datasrc/rbtree.h (original)
+++ branches/trac461/src/lib/datasrc/rbtree.h Wed Dec 29 10:30:53 2010
@@ -49,7 +49,7 @@
}
}
-template <typename T>
+template <typename T, typename SearchPolicy>
class RBTree;
/// \brief \c RBNode use by RBTree to store any data related to one domain name
@@ -71,7 +71,8 @@
class RBNode : public boost::noncopyable {
public:
/// only \c RBTree can create and destroy \c RBNode
- friend class RBTree<T>;
+ template <typename U, typename SearchPolicy>
+ friend class RBTree;
typedef boost::shared_ptr<T> NodeDataPtr;
/// \name Deonstructor
@@ -186,6 +187,8 @@
template <typename T>
RBNode<T>::~RBNode() {
}
+
+
/// \brief \c RBTree class represents all the domains with the same suffix,
/// so it can be used to store the domains in one zone.
///
@@ -199,7 +202,11 @@
/// tree has the same base name. The benefit of this struct is that:
/// - enhance the query performace compared with one big flat red black tree
/// - decrase the memory footprint to save common labels only once.
-
+///
+/// \par Depending on different usage, rbtree will support different search policy
+/// current implementation support whether empty node is visible to end user or not
+/// This is as the last template parameter for end user, choose ReturnEmptyNodePolicy
+/// to make return non-empty, choose ReturnEmptyNodePolicy to get empty node
/*
/// \verbatim
/// with the following names:
@@ -231,8 +238,11 @@
/// - since \c RBNode only has down pointer without up pointer, the node path during finding
/// should be recorded for later use
*/
-template <typename T>
-class RBTree : public boost::noncopyable {
+class ReturnEmptyNodePolicy;
+class ReturnNonEmptyNodePolicy;
+
+template <typename T, typename SearchPolicy = ReturnNonEmptyNodePolicy>
+class RBTree : public boost::noncopyable, public SearchPolicy {
friend class RBNode<T>;
public:
/// \brief The return value for the \c find() insert() and erase() method
@@ -295,14 +305,14 @@
//@}
/// \brief Swaps two tree's contents.
- ///
+ ///
/// This acts the same as many std::*.swap functions, exchanges the
/// contents. This doesn't throw anything.
void swap(RBTree<T>& other) {
std::swap(root_, other.root_);
std::swap(NULLNODE, other.NULLNODE);
std::swap(node_count_, other.node_count_);
- }
+ }
private:
/// \name RBTree balance functions
@@ -347,21 +357,21 @@
unsigned int node_count_;
};
-template <typename T>
-RBTree<T>::RBTree() {
+template <typename T, typename SearchPolicy>
+RBTree<T,SearchPolicy>::RBTree() {
NULLNODE = RBNode<T>::NULL_NODE();
root_ = NULLNODE;
node_count_ = 0;
}
-template <typename T>
-RBTree<T>::~RBTree() {
+template <typename T, typename SearchPolicy>
+RBTree<T,SearchPolicy>::~RBTree() {
deleteHelper(root_);
assert(node_count_ == 0);
}
-template <typename T>
-void RBTree<T> ::deleteHelper(RBNode<T> *root) {
+template <typename T, typename SearchPolicy>
+void RBTree<T,SearchPolicy> ::deleteHelper(RBNode<T> *root) {
if (root == NULLNODE) {
return;
}
@@ -390,19 +400,19 @@
--node_count_;
}
-template <typename T>
-typename RBTree<T>::Result
-RBTree<T>::find(const isc::dns::Name& name, RBNode<T>** node) const {
+template <typename T, typename SearchPolicy>
+typename RBTree<T,SearchPolicy>::Result
+RBTree<T,SearchPolicy>::find(const isc::dns::Name& name, RBNode<T>** node) const {
const RBNode<T>* up_node = NULLNODE;
return (findHelper(name, &up_node, node));
}
-template <typename T>
-typename RBTree<T>::Result
-RBTree<T>::find(const isc::dns::Name& name, const RBNode<T>** node) const {
+template <typename T, typename SearchPolicy>
+typename RBTree<T,SearchPolicy>::Result
+RBTree<T,SearchPolicy>::find(const isc::dns::Name& name, const RBNode<T>** node) const {
const RBNode<T>* up_node;
RBNode<T>* target_node;
- const typename RBTree<T>::Result ret =
+ const typename RBTree<T,SearchPolicy>::Result ret =
findHelper(name, &up_node, &target_node);
if (ret != NOTFOUND) {
*node = target_node;
@@ -410,15 +420,15 @@
return (ret);
}
-template <typename T>
-typename RBTree<T>::Result
-RBTree<T>::findHelper(const isc::dns::Name& target_name, const RBNode<T>** up_node,
+template <typename T, typename SearchPolicy>
+typename RBTree<T,SearchPolicy>::Result
+RBTree<T,SearchPolicy>::findHelper(const isc::dns::Name& target_name, const RBNode<T>** up_node,
RBNode<T>** target) const
{
using namespace helper;
RBNode<T>* node = root_;
- typename RBTree<T>::Result ret = NOTFOUND;
+ typename RBTree<T,SearchPolicy>::Result ret = NOTFOUND;
*up_node = NULLNODE;
isc::dns::Name name = target_name;
@@ -428,7 +438,7 @@
const isc::dns::NameComparisonResult::NameRelation relation =
compare_result.getRelation();
if (relation == isc::dns::NameComparisonResult::EQUAL) {
- if (!node->isEmpty()) {
+ if (SearchPolicy::returnEmptyNode() || !node->isEmpty()) {
*target = node;
ret = EXACTMATCH;
}
@@ -444,7 +454,7 @@
*up_node = node;
name = name - node->name_;
if (!node->isEmpty()) {
- ret = RBTree<T>::PARTIALMATCH;
+ ret = RBTree<T,SearchPolicy>::PARTIALMATCH;
*target = node;
}
node = node->down_;
@@ -457,9 +467,9 @@
return (ret);
}
-template <typename T>
-typename RBTree<T>::Result
-RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
+template <typename T, typename SearchPolicy>
+typename RBTree<T,SearchPolicy>::Result
+RBTree<T,SearchPolicy>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
using namespace helper;
RBNode<T>* parent = NULLNODE;
RBNode<T>* current = root_;
@@ -476,7 +486,12 @@
if (new_node != NULL) {
*new_node = current;
}
- return (ALREADYEXIST);
+
+ if (current->isEmpty() && !SearchPolicy::returnEmptyNode()) {
+ return (SUCCEED);
+ } else {
+ return (ALREADYEXIST);
+ }
} else {
const int common_label_count = compare_result.getCommonLabels();
if (common_label_count == 1) {
@@ -532,9 +547,9 @@
return (SUCCEED);
}
-template <typename T>
+template <typename T, typename SearchPolicy>
void
-RBTree<T>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
+RBTree<T,SearchPolicy>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
using namespace helper;
const isc::dns::Name sub_name = node.name_ - base_name;
// using auto_ptr here is to avoid memory leak in case of exceptoin raised
@@ -550,9 +565,9 @@
down_node.release();
}
-template <typename T>
+template <typename T, typename SearchPolicy>
void
-RBTree<T>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
+RBTree<T,SearchPolicy>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* uncle;
while (node != *root && node->parent_->color_ == RBNode<T>::RED) {
@@ -596,9 +611,9 @@
}
-template <typename T>
+template <typename T, typename SearchPolicy>
RBNode<T>*
-RBTree<T>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
+RBTree<T,SearchPolicy>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* right = node->right_;
node->right_ = right->left_;
if (right->left_ != NULLNODE)
@@ -621,9 +636,9 @@
return (node);
}
-template <typename T>
+template <typename T, typename SearchPolicy>
RBNode<T>*
-RBTree<T>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
+RBTree<T,SearchPolicy>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* left = node->left_;
node->left_ = left->right_;
if (left->right_ != NULLNODE)
@@ -645,17 +660,17 @@
return (node);
}
-template <typename T>
+template <typename T, typename SearchPolicy>
void
-RBTree<T>::dumpTree(std::ostream& os, unsigned int depth) const {
+RBTree<T,SearchPolicy>::dumpTree(std::ostream& os, unsigned int depth) const {
indent(os, depth);
os << "tree has " << node_count_ << " node(s)\n";
dumpTreeHelper(os, root_, depth);
}
-template <typename T>
+template <typename T, typename SearchPolicy>
void
-RBTree<T>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
+RBTree<T,SearchPolicy>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
unsigned int depth) const
{
if (node == NULLNODE) {
@@ -680,12 +695,28 @@
dumpTreeHelper(os, node->right_, depth + 1);
}
-template <typename T>
+template <typename T, typename SearchPolicy>
void
-RBTree<T>::indent(std::ostream& os, unsigned int depth) {
+RBTree<T,SearchPolicy>::indent(std::ostream& os, unsigned int depth) {
static const unsigned int INDENT_FOR_EACH_DEPTH = 5;
os << std::string(depth * INDENT_FOR_EACH_DEPTH, ' ');
}
+
+/// \brief search policy for rbtree find, the default policy for rbtree is ReturnNonEmptyNode
+/// which will only return non-empty node to end user, since empty node is create by RBTree for inner
+/// useage, except special case, it's meaningless to return it to end user except some special case
+/// like using rbtree to store zone data
+class ReturnEmptyNodePolicy
+{
+ public:
+ bool returnEmptyNode()const { return true; }
+};
+
+class ReturnNonEmptyNodePolicy
+{
+ public:
+ bool returnEmptyNode()const { return false; }
+};
}
}
Modified: branches/trac461/src/lib/datasrc/tests/rbtree_unittest.cc
==============================================================================
--- branches/trac461/src/lib/datasrc/tests/rbtree_unittest.cc (original)
+++ branches/trac461/src/lib/datasrc/tests/rbtree_unittest.cc Wed Dec 29 10:30:53 2010
@@ -24,6 +24,7 @@
#include <datasrc/rbtree.h>
#include <dns/tests/unittest_util.h>
+#include <string>
using namespace std;
using namespace isc::dns;
@@ -51,30 +52,20 @@
class RBTreeTest : public::testing::Test {
protected:
RBTreeTest() : rbtree() {
- rbtree.insert(Name("c"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(1)));
- rbtree.insert(Name("b"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(2)));
- rbtree.insert(Name("a"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(3)));
- rbtree.insert(Name("x.d.e.f"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(4)));
- rbtree.insert(Name("z.d.e.f"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(5)));
- rbtree.insert(Name("g.h"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(6)));
- rbtree.insert(Name("i.g.h"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(7)));
- rbtree.insert(Name("o.w.y.d.e.f"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(8)));
- rbtree.insert(Name("j.z.d.e.f"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(9)));
- rbtree.insert(Name("p.w.y.d.e.f"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(10)));
- rbtree.insert(Name("q.w.y.d.e.f"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataPtr(new int(11)));
+ const char * 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"};
+ 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);
+ rbtnode->setData(RBNode<int>::NodeDataPtr(new int(i + 1)));
+
+ expose_empty_node_rbtree.insert(Name(domain_names[i]), &rbtnode);
+ rbtnode->setData(RBNode<int>::NodeDataPtr(new int(i + 1)));
+ }
+
}
RBTree<int> rbtree;
+ RBTree<int, ReturnEmptyNodePolicy> expose_empty_node_rbtree;
RBNode<int>* rbtnode;
const RBNode<int>* crbtnode;
};
@@ -82,6 +73,7 @@
TEST_F(RBTreeTest, getNodeCount) {
EXPECT_EQ(13, rbtree.getNodeCount());
+ EXPECT_EQ(13, expose_empty_node_rbtree.getNodeCount());
}
TEST_F(RBTreeTest, setGetData) {
@@ -90,31 +82,63 @@
}
TEST_F(RBTreeTest, insertNames) {
- EXPECT_EQ(RBTree<int>::ALREADYEXIST, rbtree.insert(Name("d.e.f"), &rbtnode));
+ //if don't expose empty node, even the node already exsit which is caused by node fission
+ //we will return succeed
+ EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("d.e.f"), &rbtnode));
EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
EXPECT_EQ(13, rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::ALREADYEXIST,
+ expose_empty_node_rbtree.insert(Name("d.e.f"), &rbtnode));
+ EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
+ EXPECT_EQ(13, expose_empty_node_rbtree.getNodeCount());
+
+
+ //insert not exist node
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("."), &rbtnode));
EXPECT_EQ(Name("."), rbtnode->getName());
EXPECT_EQ(14, rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("."), &rbtnode));
+ EXPECT_EQ(Name("."), rbtnode->getName());
+ EXPECT_EQ(14, expose_empty_node_rbtree.getNodeCount());
+
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("example.com"), &rbtnode));
EXPECT_EQ(15, rbtree.getNodeCount());
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(12)));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("example.com"), &rbtnode));
+ EXPECT_EQ(15, expose_empty_node_rbtree.getNodeCount());
+ rbtnode->setData(RBNode<int>::NodeDataPtr(new int(12)));
+
+
// return ALREADYEXIST, since node "example.com" already has been explicitly inserted
EXPECT_EQ(RBTree<int>::ALREADYEXIST, rbtree.insert(Name("example.com"), &rbtnode));
EXPECT_EQ(15, rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::ALREADYEXIST, expose_empty_node_rbtree.insert(Name("example.com"), &rbtnode));
+ EXPECT_EQ(15, expose_empty_node_rbtree.getNodeCount());
+
// split the node "d.e.f"
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("k.e.f"), &rbtnode));
EXPECT_EQ(Name("k"), rbtnode->getName());
EXPECT_EQ(17, rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("k.e.f"), &rbtnode));
+ EXPECT_EQ(Name("k"), rbtnode->getName());
+ EXPECT_EQ(17, expose_empty_node_rbtree.getNodeCount());
+
+
// split the node "g.h"
- EXPECT_EQ(RBTree<int>::ALREADYEXIST, rbtree.insert(Name("h"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("h"), &rbtnode));
EXPECT_EQ(Name("h"), rbtnode->getName());
EXPECT_EQ(18, rbtree.getNodeCount());
+
+ //node fission will create node "h"
+ EXPECT_EQ(RBTree<int>::ALREADYEXIST, expose_empty_node_rbtree.insert(Name("h"), &rbtnode));
+ EXPECT_EQ(Name("h"), rbtnode->getName());
+ EXPECT_EQ(18, expose_empty_node_rbtree.getNodeCount());
+
// add child domain
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("m.p.w.y.d.e.f"), &rbtnode));
@@ -124,18 +148,35 @@
EXPECT_EQ(Name("n"), rbtnode->getName());
EXPECT_EQ(20, rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("m.p.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(Name("m"), rbtnode->getName());
+ EXPECT_EQ(19, expose_empty_node_rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("n.p.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(Name("n"), rbtnode->getName());
+ EXPECT_EQ(20, expose_empty_node_rbtree.getNodeCount());
+
+
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("l.a"), &rbtnode));
EXPECT_EQ(Name("l"), rbtnode->getName());
EXPECT_EQ(21, rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("l.a"), &rbtnode));
+ EXPECT_EQ(Name("l"), rbtnode->getName());
+ EXPECT_EQ(21, expose_empty_node_rbtree.getNodeCount());
+
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("r.d.e.f"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("s.d.e.f"), &rbtnode));
EXPECT_EQ(23, rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("r.d.e.f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("s.d.e.f"), &rbtnode));
+ EXPECT_EQ(23, expose_empty_node_rbtree.getNodeCount());
+
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("h.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("h.w.y.d.e.f"), &rbtnode));
// add more nodes one by one to cover leftRotate and rightRotate
- EXPECT_EQ(RBTree<int>::ALREADYEXIST, rbtree.insert(Name("f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("f"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("m"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("nm"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("om"), &rbtnode));
@@ -146,6 +187,18 @@
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("i"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("ae"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("n"), &rbtnode));
+
+ EXPECT_EQ(RBTree<int>::ALREADYEXIST, expose_empty_node_rbtree.insert(Name("f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("m"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("nm"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("om"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("k"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("l"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("fe"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("ge"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("i"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("ae"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCEED, expose_empty_node_rbtree.insert(Name("n"), &rbtnode));
}
TEST_F(RBTreeTest, findName) {
More information about the bind10-changes
mailing list