[svn] commit: r3521 - in /branches/trac397/src/bin/auth: rbt_datasrc.cc rbt_datasrc.h
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Nov 15 01:27:11 UTC 2010
Author: hanfeng
Date: Mon Nov 15 01:27:11 2010
New Revision: 3521
Log:
add more document for red black tree also the disable copy feature
Modified:
branches/trac397/src/bin/auth/rbt_datasrc.cc
branches/trac397/src/bin/auth/rbt_datasrc.h
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 15 01:27:11 2010
@@ -50,6 +50,7 @@
RBNode::successor() {
RBNode* current = this;
+ /// if has right node, the successor is the most left node
if (right_ != right_->right_) {
current = right_;
while (current->left_ != current->left_->left_)
@@ -57,6 +58,8 @@
return (current);
}
+ /// otherwise return the parent without left child or
+ /// current node isnot its right child
RBNode* s = current->parent_;
while (s != s->left_ && current == s->right_) {
current = s;
@@ -65,7 +68,6 @@
return (s);
}
-/// no duplication is checked now
int
RBNode::addRRset(RRsetPtr rrset) {
if (rrset->getType() == RRType::NS())
@@ -92,7 +94,26 @@
down->up_ = this;
}
-
+/*
+ with the following names:
+ a x.d.e.f o.w.y.d.e.f
+ b z.d.e.f p.w.y.d.e.f
+ c g.h q.w.y.d.e.f
+ the tree will looks like:
+ b
+ / \
+ a d.e.f
+ /|\
+ c | g.h
+ |
+ w.y
+ /|\
+ x | z
+ |
+ p
+ / \
+ o q
+*/
RBTree::RBTree() {
NULLNODE = new RBNode(Name(" "));
NULLNODE->parent_ = NULLNODE->left_ = NULLNODE->right_ = NULLNODE;
@@ -129,14 +150,14 @@
}
RBTree::FindResult
-RBTree::find(const Name& name, RBNode** node)const {
+RBTree::find(const Name& name, RBNode** node) const {
RBTree* tree;
return (findHelper(name, &tree, node));
}
RBTree::FindResult
-RBTree::findHelper(const Name& name, RBTree** tree, RBNode** ret)const {
+RBTree::findHelper(const Name& name, RBTree** tree, RBNode** ret) const {
RBNode* node = root_;
while (node != NULLNODE) {
NameComparisonResult compare_result = name.compare(node->name_);
@@ -209,14 +230,14 @@
order = compare_result.getOrder();
current = order < 0 ? current->left_ : current->right_;
} else {
- //insert sub domain to sub tree
+ /// insert sub domain to sub tree
if (relation == NameComparisonResult::SUBDOMAIN) {
if (NULL == current->down_)
current->setDownTree(new RBTree());
return (current->down_->insert(name - current->name_, new_node));
} else {
- // for super domain or has common label domain, create common node first
- // then insert current name and new name into the sub tree
+ /// for super domain or has common label domain, create common node first
+ /// then insert current name and new name into the sub tree
Name common_ancestor = name.split(name.getLabelCount() - common_label_count, common_label_count);
Name sub_name = current->name_ - common_ancestor;
current->name_ = common_ancestor;
@@ -230,8 +251,8 @@
sub_root->name_ = sub_name;
current->rrsets_.reset();
- //if insert name is the super domain of current node, no need insert
- //otherwise insert it into the down tree
+ /// if insert name is the super domain of current node, no need insert again
+ /// otherwise insert it into the down tree
if (name.getLabelCount() == common_label_count) {
*new_node = current;
return (0);
@@ -373,7 +394,7 @@
return (1);
tree->eraseNode(node);
- ///merge down to up
+ /// merge down to up
if (tree->node_count_ == 1 && tree->up_ != NULL && tree->up_->isNonterminal()) {
RBNode* up = tree->up_;
Name merged_name = tree->root_->name_.concatenate(up->name_);
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 Mon Nov 15 01:27:11 2010
@@ -20,43 +20,83 @@
#include <dns/rrset.h>
#include <dns/rrsetlist.h>
#include <boost/shared_ptr.hpp>
+#include <boost/utility.hpp>
using namespace isc::dns;
namespace isc {
namespace datasrc {
+/// \brief rbtree color define
enum RBTreeColor {BLACK = 1, RED};
class RBTree;
-/// RBNode generally contains the data for one domain name
-/// It's a general node of one rbtree with left, right, parent and color
-/// It also carray the dns data like the rrsets belongs to the domain name
-/// and a rbtree which is the subdomain of this node
-/// the name of the node is relative. One special kind of node is non-terminal node
+/// \brief \c RBNode class represent one domain name in the domain space
+
+/// It has two roles, the first one is as one node in the \c RBTree the second one
+/// is store the data related to DNS. As for the first role, it has left, right, parent and color memebers
+/// which used to keey the balance of the \c RBTree. As for the second role,
+// it stores the rrsets belongs to the domain name and a rbtree which includes all the subdomains of this node
+/// the name stored in the node is relative related to its parent node.
+/// One special kind of node is non-terminal node
/// which has subdomains with rrset but it self doesn't has any rrset
///
-///
-/// RBNode memory management is totally handled by rbtree, so no constructor and destructor function is exposed
-
-class RBNode {
+/// \b Note: \c RBNode should create or destroied only by \c RBTree so constructor and destructor function aren't exposed
+
+
+class RBNode : public boost::noncopyable{
public:
+ /// only /c RBTree can create and destroy \c RBNode
friend class RBTree;
typedef boost::shared_ptr<RRsetList> RRsetListPtr;
- ///whether current domain name contains ns records
+ /// \name Test functions
+ ///
+ //@{
+ /// \brief return whether current domain name has ns records
bool isDelegate() const { return is_delegate_;}
- //subname has rrset, but it self doesn't has
+
+ /// \brief return whether current domain name is non-terminal
+ /// A non-terminal domain has no rrsets but at least one its descendant
+ /// domain has rrset
bool isNonterminal() const { return is_nonterminal_;}
+
+ /// \brief return the name of current node, it's relative to its parents
+ //
+ /// \todo Is it meaningful to return the absolute of the node?
+ const Name &getName() const {return name_;}
+
+ // \brief return next node whose name is bigger than current node
+ RBNode* successor();
+ //@}
+
+
+ /// \name modify function
+ //@{
+
+ /// \brief add the rrset to the node
+ /// \Note: there is no check whether the node already has the rrset or not
+ /// and no check about whether the name of the rrset is same with the node or not
+ /// All of above is rely on interface user
int addRRset(RRsetPtr rrset);
- const Name &getName() const {return name_;}
-
- //next domain name which is bigger than current one
- RBNode* successor();
+ //@}
private:
+ /// \name Constructors and destructor
+ //@{
+ /// \param nullnode The null point for \c RBNode isnot use \c NULL, but use one specified
+ /// default node singled as null node, this is intended to keep the code more unify
RBNode(const Name& name, RRsetListPtr rrsets = RRsetListPtr(), RBNode* nullnode = NULL);
- ~RBNode(); //the class isn't left to be inherited
+
+ /// the class isn't left to be inherted
+ ~RBNode();
+ //@}
+
+
+ /// \brief copy the DNS related date to another node except the sub domain tree
void cloneDNSData(RBNode& node);
+ /// \brief when copy the DNS data from one node to another, except the rrsets, name etc,
+ /// also needs to maintain the down and up relationship, which includes set the down point of current
+ /// node and up point of sub domain tree
void setDownTree(RBTree* down);
/// data to maintain the rbtree balance
@@ -73,57 +113,92 @@
bool is_nonterminal_;
};
-/// RBTree is a generic red black tree, it contains all the node with same suffix
+/// \brief \c RBTree class represent all the domains with same suffix, so it can be used to store
+/// the domains in one zone
+///
+/// \c RBTree is a generic red black tree, and contains all the node with same suffix, since each
+/// name may have sub domain names so \c RBTree is a recursive data struct or tree in tree
/// 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
-class RBTree {
+/// opaque for end user.
+class RBTree : public boost::noncopyable{
friend class RBNode;
public:
+ /// \brief The return value for find method
+ /// - EXACTMATCH: return the node in the tree exactly same with the target
+ /// - FINDREFERRAL: return the node which is the ancestor of the target containing ns record
+ /// - NOTFOUND: other conditions except EXACTMATCH & FINDREFERRAL
enum FindResult{EXACTMATCH, FINDREFERRAL, NOTFOUND};
+ /// \name Constructor and Destructor
+ //@{
RBTree();
+ /// \b Note: RBTree is not intended to be inherited so the destructor isnot virtual
~RBTree();
-
- /// if find result isn't NOTFOUND, the node will point to the result
- /// with return value equal to NOTFOUND, the value of node is undetermined
+ //@}
+
+ /// \name Inquery methods
+ //@{
+ /// \brief find the node with the name
+ /// \param name Target to be found
+ /// \param node Point to the node when the return vaule is \c not NOTFOUND, if
+ /// if the return value is NOTFOUND, the value of node is \c unknown
FindResult find(const Name& name, RBNode** node)const;
- /// get all the node count recursively, including the sub trees
- /// note that the return value isn't same with valid domain names in the tree
- /// the interface just used for test the tree logic, later will be removed
+ /// \brief Get all the node count in the tree
int getNodeCount() const;
-
-
+ //@}
+
+ /// \name Debug function
+ //@{
+ /// \brief print the node in the trees
+ /// \todo is it better to return one string instead of print to the stdout?
void printTree(int depth = 0)const;
-
- /// 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
+ //@}
+
+ /// \name Modify function
+ //@{
+ /// \brief insert the domain name into the tree
+ /// \param name The name want to be inserted into the tree
+ /// \param inserted_node If no node with the name in the tree,
+ /// new \c RBNode will be created, otherwise nothing will be done
+ /// anyway the pointer point to the node with the name will be assign to inserted_node
+ /// \return return 0 means no node exists in the tree with the name before insert
+ /// return 1 means already has the node with the given name
+ //
+ /// If want to add rrset into one node, but not sure whether the node already exist
+ /// Instead of call \c find, call \c insert and then call the RBNode interface to
+ /// add rrset into the node is a better way
int insert(const Name& name, RBNode** inserted_node);
- /// if the node doesn't exist, return value will be one otherwise zero
+ /// \brief erase the node with the domain name
+ /// \return If no node with the name, return one otherwise return zero
int erase(const Name& name);
+ //@}
private:
+ /// \name RBTree balance function
+ //@{
void deleteRebalance(RBNode* node);
void insertRebalance(RBNode* node);
RBNode* rightRotate(RBNode* p);
RBNode* leftRotate(RBNode* p);
- void printTreeHelper(RBNode* node, int depth)const;
+ //@}
+
+ /// \name Helper function
+ //@{
+ /// All the public function has related recursive helper function
void eraseNode(RBNode* node);
-
- /// recursive find one name in the tree, and return the exact tree has the name
FindResult findHelper(const Name& name, RBTree** tree, RBNode** node)const;
int getNodeCountHelper(const RBNode* node) const;
-
- void setUpNode(RBNode *node);
+ void printTreeHelper(RBNode* node, int depth)const;
+ //@}
+
RBNode* root_;
RBNode* NULLNODE;
RBNode* up_;
- unsigned int node_count_; //current tree node count exclude the node in down pointing trees
+ /// the node count of current tree except the sub domain trees
+ unsigned int node_count_;
};
}
}
More information about the bind10-changes
mailing list