[svn] commit: r3808 - in /branches/trac397focused/src/lib/datasrc: rbtree.h tests/rbtree_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Dec 13 05:29:09 UTC 2010
Author: hanfeng
Date: Mon Dec 13 05:29:08 2010
New Revision: 3808
Log:
modify the data of rbnode to use shared_ptr and other trival optimization
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 Mon Dec 13 05:29:08 2010
@@ -17,6 +17,7 @@
#include <dns/name.h>
#include <boost/utility.hpp>
+#include <boost/shared_ptr.hpp>
#include <exception>
#include <ostream>
#include <algorithm>
@@ -43,7 +44,10 @@
}
/// \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;
/// \brief \c RBNode use by RBTree to store any data related to one domain name
@@ -75,6 +79,7 @@
public:
/// only \c RBTree can create and destroy \c RBNode
friend class RBTree<T>;
+ typedef boost::shared_ptr<T> NodeDataType;
/// \name Deonstructor
/// \note it's seems a little strange that constructor is private
@@ -96,23 +101,28 @@
/// \brief return the data store in this node
/// \note, since the data is managed by RBNode, developer should not
/// free the pointer
- T* getData() { return (data_); }
+ NodeDataType& getData() { return (data_); }
/// \brief return the data stored in this node, read-only version
- const T* getData() const { return (data_); }
+ const NodeDataType& getData() const { return (data_); }
/// \brief return whether the node has related data
/// \note it's meaningless has empty \c RBNode in one RBTree, the only
/// exception is for non-terminal node which has sub domain nodes who
/// has data(rrset)
- bool isEmpty() const { return (data_ == NULL); }
+ bool isEmpty() const { return (data_.get() == NULL); }
//@}
/// \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);
+ //@}
private:
@@ -140,9 +150,6 @@
return (&null_node);
}
- /// \brief swap the content of two node, the content here refers to
- /// name, data, down
- void swap(RBNode<T>& node);
/// data to maintain the rbtree balance
RBNode<T>* parent_;
@@ -152,7 +159,7 @@
isc::dns::Name name_;
- T* data_;
+ NodeDataType data_;
/// the down pointer points to the root node of sub domains of current
/// domain
/// \par Adding down pointer to \c RBNode is for two purpose:
@@ -173,7 +180,6 @@
color_(BLACK),
// dummy name, the value doesn't matter:
name_(isc::dns::Name::ROOT_NAME()),
- data_(NULL),
down_(this)
{
}
@@ -185,7 +191,6 @@
right_(NULL_NODE()),
color_(RED),
name_(name),
- data_(NULL),
down_(NULL_NODE())
{
}
@@ -193,28 +198,22 @@
template <typename T>
RBNode<T>::~RBNode() {
- delete data_;
}
template <typename T>
void
RBNode<T>::setData(T* data) {
- if (data_ != data) {
- delete data_;
- data_ = data;
- }
-}
-
-template <typename T>
-void
-RBNode<T>::swap(RBNode<T>& node) {
- std::swap(node.name_, name_);
- std::swap(node.data_, data_);
- std::swap(node.down_, down_);
-}
-
-
+ 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.
///
@@ -342,12 +341,15 @@
/// so for example, in zone a, we has
/// b.a, c.b.a and d.b.a search c.b.a, up will points to b.a.
/// and node will points to c.b.a
+ /// \note parameter up now is not used by any funciton, but we gonna
+ /// need it soon to implement function like remove
Result findHelper(const isc::dns::Name& name, const RBNode<T>** up,
RBNode<T>** node) const;
void dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
unsigned int depth) const;
/// for indent purpose, add certian mount empty charachter to output stream
- /// according to the depth.
+ /// according to the depth. This is a helper function which is only used when
+ /// dump tree
static void indent(std::ostream& os, unsigned int depth);
/// Split one node into two nodes, keep the old node and create one new
@@ -459,13 +461,11 @@
} else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
*up_node = node;
name = name - node->name_;
- if (node->isEmpty()) {
- node = node->down_;
- } else {
+ if (!node->isEmpty()) {
ret = RBTree<T>::PARTIALMATCH;
*target = node;
- node = node->down_;
}
+ node = node->down_;
} else {
break;
}
@@ -555,10 +555,9 @@
const isc::dns::Name sub_name = node.name_ - base_name;
// using auto_ptr here is avoid memory leak in case of exceptoin raised
// after the RBNode creation
- std::auto_ptr<RBNode<T> > down_node(new RBNode<T>(node.name_ - base_name));
+ std::auto_ptr<RBNode<T> > down_node(new RBNode<T>(sub_name));
std::swap(node.data_, down_node->data_);
down_node->down_ = node.down_;
- down_node->name_ = sub_name;
node.name_ = base_name;
node.down_ = down_node.get();
//root node of sub tree, the initial color is BLACK
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 Mon Dec 13 05:29:08 2010
@@ -72,7 +72,7 @@
rbtree.insert(Name("p.w.y.d.e.f"), &rbtnode);
rbtnode->setData(new int(9));
rbtree.insert(Name("q.w.y.d.e.f"), &rbtnode);
- rbtnode->setData(new int(10));
+ rbtnode->setData(RBNode<int>::NodeDataType(new int(10)));
}
RBTree<int> rbtree;
RBNode<int>* rbtnode;
More information about the bind10-changes
mailing list