[svn] commit: r3854 - in /branches/trac397focused/src/lib/datasrc: rbtree.h tests/rbtree_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Thu Dec 16 05:57:09 UTC 2010
Author: hanfeng
Date: Thu Dec 16 05:57:08 2010
New Revision: 3854
Log:
remove setData for raw pointer interface, move the RBTree color definition into RBNode, add more comment
Modified:
branches/trac397focused/src/lib/datasrc/rbtree.h
branches/trac397focused/src/lib/datasrc/tests/rbtree_unittest.cc
Modified: branches/trac397focused/src/lib/datasrc/rbtree.h
==============================================================================
--- branches/trac397focused/src/lib/datasrc/rbtree.h (original)
+++ branches/trac397focused/src/lib/datasrc/rbtree.h Thu Dec 16 05:57:08 2010
@@ -40,11 +40,6 @@
sub_name.getLabelCount()));
}
}
-
-/// \brief Define rbtree color
-/// the enum isnot put into RBTree template, because no matter the RBTree
-/// will be instantiated to whatever class, the color is same.
-enum RBTreeColor {BLACK, RED};
template <typename T>
class RBTree;
@@ -112,18 +107,16 @@
/// \name Modify functions
//@{
- /// \brief set the data stored in the node
- /// this function also means ownership transfer, then data is owned by
- /// \c RBNode, and RBNode will in charge of the memory management
- /// \note when set new data, old data will be deleted first
- void setData(T* data);
-
/// \breif set the data stored in the node
- void setData(const NodeDataType& data);
+ void setData(const NodeDataType& data) { data_ = data;}
//@}
private:
+ /// \brief Define rbnode color
+ enum RBNodeColor {BLACK, RED};
+
+
/// \name Constructors
/// \note \c Single RBNode is meaningless without living inside one \c RBTree
/// the creation and destroy of one \c RBNode is handle by host \c RBTree, so
@@ -153,7 +146,7 @@
RBNode<T>* parent_;
RBNode<T>* left_;
RBNode<T>* right_;
- RBTreeColor color_;
+ RBNodeColor color_;
isc::dns::Name name_;
@@ -196,21 +189,6 @@
template <typename T>
RBNode<T>::~RBNode() {
-}
-
-
-template <typename T>
-void
-RBNode<T>::setData(T* data) {
- if (data_.get() != data) {
- data_.reset(data);
- }
-}
-
-template <typename T>
-void
-RBNode<T>::setData(const RBNode<T>::NodeDataType& data) {
- data_ = data;
}
/// \brief \c RBTree class represents all the domains with the same suffix,
/// so it can be used to store the domains in one zone.
@@ -524,14 +502,15 @@
RBNode<T>** current_root = (up_node != NULLNODE) ?
&(up_node->down_) : &root_;
// using auto_ptr here is avoid memory leak in case of exceptoin raised
- // after the RBNode creation
+ // after the RBNode creation, if we can make sure no exception will be
+ // raised until the end of the function, we use remove it for optimization
std::auto_ptr<RBNode<T> > node(new RBNode<T>(name));
node->parent_ = parent;
if (parent == NULLNODE) {
*current_root = node.get();
//node is the new root of sub tree, so its init color
// is BLACK
- node->color_ = BLACK;
+ node->color_ = RBNode<T>::BLACK;
} else if (order < 0) {
parent->left_ = node.get();
} else {
@@ -560,7 +539,7 @@
node.name_ = base_name;
node.down_ = down_node.get();
//root node of sub tree, the initial color is BLACK
- down_node->color_ = BLACK;
+ down_node->color_ = RBNode<T>::BLACK;
++node_count_;
down_node.release();
}
@@ -570,44 +549,44 @@
RBTree<T>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* uncle;
- while (node != *root && node->parent_->color_ == RED) {
+ while (node != *root && node->parent_->color_ == RBNode<T>::RED) {
if (node->parent_ == node->parent_->parent_->left_) {
uncle = node->parent_->parent_->right_;
- if (uncle->color_ == RED) {
- node->parent_->color_ = BLACK;
- uncle->color_ = BLACK;
- node->parent_->parent_->color_ = RED;
+ if (uncle->color_ == RBNode<T>::RED) {
+ node->parent_->color_ = RBNode<T>::BLACK;
+ uncle->color_ = RBNode<T>::BLACK;
+ node->parent_->parent_->color_ = RBNode<T>::RED;
node = node->parent_->parent_;
} else {
if (node == node->parent_->right_) {
node = node->parent_;
leftRotate(root, node);
}
- node->parent_->color_ = BLACK;
- node->parent_->parent_->color_ = RED;
+ node->parent_->color_ = RBNode<T>::BLACK;
+ node->parent_->parent_->color_ = RBNode<T>::RED;
rightRotate(root, node->parent_->parent_);
}
} else {
uncle = node->parent_->parent_->left_;
- if (uncle->color_ == RED) {
- node->parent_->color_ = BLACK;
- uncle->color_ = BLACK;
- node->parent_->parent_->color_ = RED;
+ if (uncle->color_ == RBNode<T>::RED) {
+ node->parent_->color_ = RBNode<T>::BLACK;
+ uncle->color_ = RBNode<T>::BLACK;
+ node->parent_->parent_->color_ = RBNode<T>::RED;
node = node->parent_->parent_;
} else {
if (node == node->parent_->left_) {
node = node->parent_;
rightRotate(root, node);
}
- node->parent_->color_ = BLACK;
- node->parent_->parent_->color_ = RED;
+ node->parent_->color_ = RBNode<T>::BLACK;
+ node->parent_->parent_->color_ = RBNode<T>::RED;
leftRotate(root, node->parent_->parent_);
}
}
}
- (*root)->color_ = BLACK;
+ (*root)->color_ = RBNode<T>::BLACK;
}
@@ -682,7 +661,7 @@
indent(os, depth);
os << node->name_.toText() << " ("
- << ((node->color_ == BLACK) ? "black" : "red") << ")";
+ << ((node->color_ == RBNode<T>::BLACK) ? "black" : "red") << ")";
os << ((node->isEmpty()) ? "[invisible] \n" : "\n");
if (node->down_ != NULLNODE) {
Modified: branches/trac397focused/src/lib/datasrc/tests/rbtree_unittest.cc
==============================================================================
--- branches/trac397focused/src/lib/datasrc/tests/rbtree_unittest.cc (original)
+++ branches/trac397focused/src/lib/datasrc/tests/rbtree_unittest.cc Thu Dec 16 05:57:08 2010
@@ -52,27 +52,27 @@
protected:
RBTreeTest() : rbtree() {
rbtree.insert(Name("c"), &rbtnode);
- rbtnode->setData(new int(1));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(1)));
rbtree.insert(Name("b"), &rbtnode);
- rbtnode->setData(new int(2));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(2)));
rbtree.insert(Name("a"), &rbtnode);
- rbtnode->setData(new int(3));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(3)));
rbtree.insert(Name("x.d.e.f"), &rbtnode);
- rbtnode->setData(new int(4));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(4)));
rbtree.insert(Name("z.d.e.f"), &rbtnode);
- rbtnode->setData(new int(5));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(5)));
rbtree.insert(Name("g.h"), &rbtnode);
- rbtnode->setData(new int(6));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(6)));
rbtree.insert(Name("i.g.h"), &rbtnode);
- rbtnode->setData(new int(7));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(7)));
rbtree.insert(Name("o.w.y.d.e.f"), &rbtnode);
- rbtnode->setData(new int(8));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(8)));
rbtree.insert(Name("j.z.d.e.f"), &rbtnode);
- rbtnode->setData(new int(8));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(9)));
rbtree.insert(Name("p.w.y.d.e.f"), &rbtnode);
- rbtnode->setData(new int(9));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(10)));
rbtree.insert(Name("q.w.y.d.e.f"), &rbtnode);
- rbtnode->setData(RBNode<int>::NodeDataType(new int(10)));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(11)));
}
RBTree<int> rbtree;
RBNode<int>* rbtnode;
@@ -85,7 +85,7 @@
}
TEST_F(RBTreeTest, setGetData) {
- rbtnode->setData(new int(11));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(11)));
EXPECT_EQ(11, *(rbtnode->getData()));
}
@@ -100,7 +100,7 @@
EXPECT_EQ(RBTree<int>::SUCCEED, rbtree.insert(Name("example.com"), &rbtnode));
EXPECT_EQ(15, rbtree.getNodeCount());
- rbtnode->setData(new int(12));
+ rbtnode->setData(RBNode<int>::NodeDataType(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));
More information about the bind10-changes
mailing list