[svn] commit: r3523 - in /branches/trac397/src/bin/auth: rbt_datasrc.cc rbt_datasrc.h tests/rbt_datasrc_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Nov 15 06:15:56 UTC 2010
Author: jinmei
Date: Mon Nov 15 06:15:56 2010
New Revision: 3523
Log:
some editorial cleanups
- missing braces
- removed redundant blank lines
- folded long lines
- improved consistency about indentation
- grammar/wording changes to the doxygen document
Modified:
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/rbt_datasrc.cc
==============================================================================
--- branches/trac397/src/bin/auth/rbt_datasrc.cc (original)
+++ branches/trac397/src/bin/auth/rbt_datasrc.cc Mon Nov 15 06:15:56 2010
@@ -20,17 +20,20 @@
using namespace isc::dns;
namespace {
- /// helper function to remove the base domain from super domain
- /// the precondition of this function is the super_name contains the sub_name
- Name operator-(const Name& super_name, const Name& sub_name) {
- return (super_name.split(0, super_name.getLabelCount() - sub_name.getLabelCount()));
- }
+/// helper function to remove the base domain from super domain
+/// the precondition of this function is the super_name contains the
+/// sub_name
+Name
+operator-(const Name& super_name, const Name& sub_name) {
+ return (super_name.split(0, super_name.getLabelCount() -
+ sub_name.getLabelCount()));
+}
}
namespace isc {
namespace datasrc {
-RBNode::RBNode(const Name& name, RRsetListPtr rrsets, RBNode* nullnode)
-: parent_(nullnode),
+RBNode::RBNode(const Name& name, RRsetListPtr rrsets, RBNode* nullnode) :
+ parent_(nullnode),
left_(nullnode),
right_(nullnode),
color_(RED),
@@ -38,12 +41,12 @@
rrsets_(rrsets),
down_(NULL),
is_delegate_(false),
- is_nonterminal_(false) {
+ is_nonterminal_(false)
+{
}
RBNode::~RBNode() {
- if (down_)
- delete down_;
+ delete down_;
}
RBNode*
@@ -53,8 +56,9 @@
/// if has right node, the successor is the left-most node
if (right_ != right_->right_) {
current = right_;
- while (current->left_ != current->left_->left_)
+ while (current->left_ != current->left_->left_) {
current = current->left_;
+ }
return (current);
}
@@ -70,10 +74,12 @@
int
RBNode::addRRset(RRsetPtr rrset) {
- if (rrset->getType() == RRType::NS())
+ if (rrset->getType() == RRType::NS()) {
is_delegate_ = true;
- if (rrsets_.get() == NULL)
+ }
+ if (rrsets_.get() == NULL) {
rrsets_.reset(new RRsetList());
+ }
rrsets_->addRRset(rrset);
is_nonterminal_ = false;
return (0);
@@ -128,19 +134,22 @@
assert(root_ != NULL);
delete NULLNODE;
- if (root_ == NULLNODE)
+ if (root_ == NULLNODE) {
return;
+ }
RBNode* node = root_;
while (root_->left_ != NULLNODE || root_->right_ != NULLNODE) {
- while (node->left_ != NULLNODE || node->right_ != NULLNODE)
+ while (node->left_ != NULLNODE || node->right_ != NULLNODE) {
node = (node->left_ != NULLNODE) ? node->left_ : node->right_;
+ }
RBNode* parent = node->parent_;
- if (parent->left_ == node)
+ if (parent->left_ == node) {
parent->left_ = NULLNODE;
- else
+ } else {
parent->right_ = NULLNODE;
+ }
delete node;
node = parent;
}
@@ -161,7 +170,8 @@
RBNode* node = root_;
while (node != NULLNODE) {
NameComparisonResult compare_result = name.compare(node->name_);
- NameComparisonResult::NameRelation relation = compare_result.getRelation();
+ NameComparisonResult::NameRelation relation =
+ compare_result.getRelation();
if (relation == NameComparisonResult::EQUAL) {
*tree = (RBTree*)this;
*ret = node;
@@ -169,24 +179,27 @@
}
else {
int common_label_count = compare_result.getCommonLabels();
- /// common label count equal one means, there is no common between two names
- if (common_label_count == 1)
- node = (compare_result.getOrder() < 0) ? node->left_ : node->right_;
- else if (NameComparisonResult::SUBDOMAIN == relation) {
+ // common label count equal one means, there is no common between
+ // two names
+ if (common_label_count == 1) {
+ node = (compare_result.getOrder() < 0) ?
+ node->left_ : node->right_;
+ } else if (NameComparisonResult::SUBDOMAIN == relation) {
if (node->isDelegate()) {
*tree = (RBTree*)this;
*ret = node;
return (RBTree::FINDREFERRAL);
+ } else if (node->down_) {
+ // the node all save the relative name, so we need to
+ // remove the suffix
+ return (node->down_->findHelper(name - node->name_, tree,
+ ret));
+ } else {
+ return (RBTree::NOTFOUND);
}
- else if (node->down_)
- /// the node all save the relative name, so we need to remove the suffix
- return (node->down_->findHelper(name - node->name_, tree, ret));
- else
- return (RBTree::NOTFOUND);
-
- }
- else
+ } else {
return (RBTree::NOTFOUND);
+ }
}
}
@@ -196,16 +209,17 @@
int
RBTree::getNodeCount() const {
return (getNodeCountHelper(root_));
-
}
int
RBTree::getNodeCountHelper(const RBNode *node) const {
- if (NULLNODE == node)
+ if (NULLNODE == node) {
return (0);
+ }
int sub_tree_node_count = node->down_ ? node->down_->getNodeCount() : 0;
- return (1 + sub_tree_node_count + getNodeCountHelper(node->left_) + getNodeCountHelper(node->right_));
+ return (1 + sub_tree_node_count + getNodeCountHelper(node->left_) +
+ getNodeCountHelper(node->right_));
}
int
@@ -218,11 +232,13 @@
parent = current;
NameComparisonResult compare_result = name.compare(current->name_);
- NameComparisonResult::NameRelation relation = compare_result.getRelation();
+ NameComparisonResult::NameRelation relation =
+ compare_result.getRelation();
if (relation == NameComparisonResult::EQUAL) {
- if (new_node)
+ if (new_node) {
*new_node = current;
- /// if the node is non-ternimal, it doesnot exist, so we return 0
+ }
+ // if the node is non-ternimal, it does not exist, so we return 0
return (current->rrsets_.get() ? 1 : 0);
} else {
int common_label_count = compare_result.getCommonLabels();
@@ -230,15 +246,20 @@
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_)
+ if (NULL == current->down_) {
current->setDownTree(new RBTree());
- return (current->down_->insert(name - current->name_, new_node));
+ }
+ 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
- Name common_ancestor = name.split(name.getLabelCount() - common_label_count, common_label_count);
+ // 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;
RBTree* down_old = current->down_;
@@ -251,33 +272,36 @@
sub_root->name_ = sub_name;
current->rrsets_.reset();
- /// if insert name is the super domain of current node, no need insert again
- /// 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);
} else {
current->is_nonterminal_ = true;
- return (current->down_->insert(name - common_ancestor, new_node));
+ return (current->down_->insert(name - common_ancestor,
+ new_node));
}
}
}
-
}
}
RBNode* node = new RBNode(name, RBNode::RRsetListPtr(), NULLNODE);
node->parent_ = parent;
- if (parent == NULLNODE)
+ if (parent == NULLNODE) {
root_ = node;
- else if (order < 0)
+ } else if (order < 0) {
parent->left_ = node;
- else
+ } else {
parent->right_ = node;
+ }
insertRebalance(node);
- if (new_node)
+ if (new_node) {
*new_node = node;
+ }
++node_count_;
return (0);
}
@@ -325,7 +349,6 @@
leftRotate(node->parent_->parent_);
}
-
}
}
@@ -339,17 +362,19 @@
p->right_ = c->left_;
- if (c->left_ != NULLNODE)
+ if (c->left_ != NULLNODE) {
c->left_->parent_ = p;
+ }
c->parent_ = p->parent_;
- if (p->parent_ == NULLNODE)
+ if (p->parent_ == NULLNODE) {
root_ = c;
- else if (p == p->parent_->left_)
+ } else if (p == p->parent_->left_) {
p->parent_->left_ = c;
- else
+ } else {
p->parent_->right_ = c;
+ }
c->left_ = p;
p->parent_ = c;
@@ -363,17 +388,19 @@
p->left_ = c->right_;
- if (c->right_ != NULLNODE)
+ if (c->right_ != NULLNODE) {
c->right_->parent_ = p;
+ }
c->parent_ = p->parent_;
- if (p->parent_ == NULLNODE)
+ if (p->parent_ == NULLNODE) {
root_ = c;
- else if (p == p->parent_->left_)
+ } else if (p == p->parent_->left_) {
p->parent_->left_ = c;
- else
+ } else {
p->parent_->right_ = c;
+ }
c->right_ = p;
p->parent_ = c;
@@ -386,16 +413,19 @@
RBTree::erase(const Name& name) {
RBNode* node;
RBTree* tree;
- if (findHelper(name, &tree, &node) != RBTree::EXACTMATCH)
+ if (findHelper(name, &tree, &node) != RBTree::EXACTMATCH) {
return (1);
+ }
/// cannot delete non terminal
- if (node->down_ != NULL)
+ if (node->down_ != NULL) {
return (1);
+ }
tree->eraseNode(node);
/// merge down to up
- if (tree->node_count_ == 1 && tree->up_ != NULL && tree->up_->isNonterminal()) {
+ if (tree->node_count_ == 1 && tree->up_ != NULL &&
+ tree->up_->isNonterminal()) {
RBNode* up = tree->up_;
Name merged_name = tree->root_->name_.concatenate(up->name_);
tree->root_->cloneDNSData(*up);
@@ -404,7 +434,7 @@
up->name_ = merged_name;
up->is_nonterminal_ = false;
delete tree;
- } else if (tree->node_count_ == 0 && tree->up_) { ///delete empty tree
+ } else if (tree->node_count_ == 0 && tree->up_) { // delete empty tree
tree->up_->setDownTree(NULL);
delete tree;
}
@@ -418,24 +448,27 @@
RBNode* y = NULLNODE;
RBNode* x = NULLNODE;
- if (node->left_ == NULLNODE || node->right_ == NULLNODE)
+ if (node->left_ == NULLNODE || node->right_ == NULLNODE) {
y = node;
- else
+ } else {
y = node->successor();
-
- if (y->left_ != NULLNODE)
+ }
+
+ if (y->left_ != NULLNODE) {
x = y->left_;
- else
+ } else {
x = y->right_;
+ }
x->parent_ = y->parent_;
- if (y->parent_ == NULLNODE)
+ if (y->parent_ == NULLNODE) {
root_ = x;
- else if ( y == y->parent_->left_ )
+ } else if ( y == y->parent_->left_ ) {
y->parent_->left_ = x;
- else
+ } else {
y->parent_->right_ = x;
+ }
if (y != node) {
y->cloneDNSData(*node);
@@ -443,8 +476,9 @@
y->down_ = NULL;
}
- if (y->color_ == BLACK)
+ if (y->color_ == BLACK) {
deleteRebalance(x);
+ }
y->left_ = NULL;
y->right_ = NULL;
@@ -528,12 +562,11 @@
printTreeHelper(root_, depth);
}
-
void
RBTree::printTreeHelper(RBNode* node, int depth) const {
-
INDNET(depth);
- std::cout << node->name_.toText() << " (" << ((node->color_ == BLACK) ? "black" : "red") << ")\n";
+ std::cout << node->name_.toText() << " ("
+ << ((node->color_ == BLACK) ? "black" : "red") << ")\n";
std::cout << ((node->isNonterminal()) ? "[non-terminal] \n" : "\n");
if (node->down_) {
assert(node->down_->up_ == node);
@@ -544,16 +577,16 @@
std::cout << "end down from" << node->name_.toText() <<"\n";
}
- if (node->left_ != NULLNODE)
+ if (node->left_ != NULLNODE) {
printTreeHelper(node->left_, depth + 1);
- else {
+ } else {
INDNET(depth + 1);
std::cout << "NULL\n";
}
- if (node->right_ != NULLNODE)
+ if (node->right_ != NULLNODE) {
printTreeHelper(node->right_, depth + 1);
- else {
+ } else {
INDNET(depth + 1);
std::cout << "NULL\n";
}
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 06:15:56 2010
@@ -12,7 +12,6 @@
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.
-
#ifndef _RBTREE_H
#define _RBTREE_H 1
@@ -32,177 +31,194 @@
/// \brief \c RBNode class represents 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 keep the balance of the \c RBTree. As for the second role,
-// it stores the rrsets belong 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.
+/// It has two roles, the first one is as one node in the \c RBTree,
+/// the second one is to store the data related to DNS. As for the first role,
+/// it has left, right, parent and color members
+/// which is used to keep the balance of the \c RBTree. As for the second role,
+// it stores the RRsets that belong 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 have any rrsets
+/// which has subdomains with RRset but itself doesn't have any RRsets.
///
-/// \b Note: \c RBNode should be created or destroyed 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;
-
- /// \name Test functions
- ///
- //@{
- /// \brief return whether current domain name has ns records
- bool isDelegate() const { return is_delegate_;}
-
- /// \brief return whether current domain name is non-terminal
- /// A non-terminal domain has no rrsets but at least one of 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 the same with the node or not
- /// All of above is rely on interface user
- int addRRset(RRsetPtr rrset);
- //@}
-
- 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);
-
- /// 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
- RBNode* parent_;
- RBNode* left_;
- RBNode* right_;
- int color_;
-
- /// data to carry dns info
- Name name_;
- RRsetListPtr rrsets_;
- RBTree* down_;
- bool is_delegate_;
- bool is_nonterminal_;
+/// \b Note: \c RBNode should be created or destroyed 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;
+
+ /// \name Test functions
+ ///
+ //@{
+ /// \brief return whether current domain name has NS records
+ bool isDelegate() const { return (is_delegate_); }
+
+ /// \brief return whether current domain name is non-terminal
+ /// A non-terminal domain has no rrsets but at least one of 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 the same with the
+ /// node or not.
+ /// All of above is rely on interface user
+ int addRRset(RRsetPtr rrset);
+ //@}
+
+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);
+
+ /// the class isn't left to be inherited
+ ~RBNode();
+ //@}
+
+ /// \brief copy the DNS related data 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
+ RBNode* parent_;
+ RBNode* left_;
+ RBNode* right_;
+ int color_;
+
+ /// data to carry dns info
+ Name name_;
+ RRsetListPtr rrsets_;
+ RBTree* down_;
+ bool is_delegate_;
+ bool is_nonterminal_;
};
-/// \brief \c RBTree class represents all the domains with the same suffix, so it can be used to store
-/// the domains in one zone
+/// \brief \c RBTree class represents all the domains with the 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 nodes with the 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, several RBTrees are involved. But from outside, the sub tree is
-/// opaque for end users.
-class RBTree : public boost::noncopyable{
+/// \c RBTree is a generic red black tree, and contains all the nodes with
+/// the same suffix, since each
+/// name may have sub domain names so \c RBTree is a recursive data structure
+/// or tree in tree.
+/// So for one zone, several RBTrees may be involved. But from outside, the sub
+/// tree is opaque for end users.
+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();
- //@}
-
- /// \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
- /// the return value is NOTFOUND, the value of node is \c unknown
- FindResult find(const Name& name, RBNode** node)const;
-
- /// \brief Get the total node count in the tree
- int getNodeCount() const;
- //@}
-
- /// \name Debug function
- //@{
- /// \brief print the nodes in the trees
- /// \todo is it better to return one string instead of print to the stdout?
- void printTree(int depth = 0)const;
- //@}
-
- /// \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);
-
- /// \brief erase the node with the domain name
- /// \return If no node with the name, return 1 otherwise return 0
- 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);
- //@}
-
- /// \name Helper function
- //@{
- /// Each public function has related recursive helper function
- void eraseNode(RBNode* node);
- FindResult findHelper(const Name& name, RBTree** tree, RBNode** node)const;
- int getNodeCountHelper(const RBNode* node) const;
- void printTreeHelper(RBNode* node, int depth)const;
- //@}
-
-
- RBNode* root_;
- RBNode* NULLNODE;
- RBNode* up_;
- /// the node count of current tree except the sub domain trees
- unsigned int node_count_;
+public:
+ /// \brief The return value for the \c find() method
+ /// - EXACTMATCH: return the node in the tree exactly same with the target
+ /// - FINDREFERRAL: return the node which is an 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
+ /// is not virtual
+ ~RBTree();
+ //@}
+
+ /// \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 the return value is NOTFOUND, the value of node is
+ /// \c unknown
+ FindResult find(const Name& name, RBNode** node) const;
+
+ /// \brief Get the total node count in the tree
+ int getNodeCount() const;
+ //@}
+
+ /// \name Debug function
+ //@{
+ /// \brief print the nodes in the trees
+ /// \todo is it better to return one string instead of print to the stdout?
+ void printTree(int depth = 0) const;
+ //@}
+
+ /// \name Modify function
+ //@{
+ /// \brief Insert the domain name into the tree
+ /// \param name The name 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 assigned 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
+ //
+ /// To add an RRset into one node when it's not known whether the node
+ /// already exists, it is better to call \c insert and then call the
+ /// RBNode interface instead of calling \c find().
+ int insert(const Name& name, RBNode** inserted_node);
+
+ /// \brief Erase the node with the domain name
+ /// \return If no node with the name, return 1; otherwise return 0
+ int erase(const Name& name);
+ //@}
+
+private:
+ /// \name RBTree balance functions
+ //@{
+ void deleteRebalance(RBNode* node);
+ void insertRebalance(RBNode* node);
+ RBNode* rightRotate(RBNode* p);
+ RBNode* leftRotate(RBNode* p);
+ //@}
+
+ /// \name Helper functions
+ //@{
+ /// Each public function has related recursive helper function
+ void eraseNode(RBNode* node);
+ FindResult findHelper(const Name& name, RBTree** tree,
+ RBNode** node) const;
+ int getNodeCountHelper(const RBNode* node) const;
+ void printTreeHelper(RBNode* node, int depth) const;
+ //@}
+
+ RBNode* root_;
+ RBNode* NULLNODE;
+ RBNode* up_;
+ /// the node count of current tree except the sub domain trees
+ unsigned int node_count_;
};
}
}
-
-#endif
-
+#endif // _RBTREE_H
+
+// Local Variables:
+// mode: c++
+// End:
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 Mon Nov 15 06:15:56 2010
@@ -49,8 +49,7 @@
namespace {
class RBTreeTest : public::testing::Test {
protected:
- RBTreeTest() : rbtree()
- {
+ RBTreeTest() : rbtree() {
rbtree.insert(Name("a"), &rbtnode);
rbtree.insert(Name("b"), &rbtnode);
rbtree.insert(Name("c"), &rbtnode);
@@ -88,8 +87,8 @@
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)));
+ RRsetPtr rrset(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(15, rbtree.getNodeCount());
@@ -136,8 +135,8 @@
EXPECT_EQ(RBTree::NOTFOUND, rbtree.find(Name("m.e.f"), &rbtnode));
// find referral
- RRsetPtr rrset = RRsetPtr(new RRset(Name("d.e.f"), RRClass::IN(), RRType::NS(),
- RRTTL(3600)));
+ RRsetPtr rrset(new RRset(Name("d.e.f"), RRClass::IN(), RRType::NS(),
+ RRTTL(3600)));
rbtnode->addRRset(rrset);
EXPECT_EQ(RBTree::FINDREFERRAL, rbtree.find(Name("m.d.e.f"), &rbtnode));
EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
@@ -201,8 +200,8 @@
// can't delete non terminal
EXPECT_EQ(1, rbtree.erase(Name("d.e.f")));
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)));
+ RRsetPtr rrset(new RRset(Name("w.y.d.e.f"), RRClass::IN(), RRType::A(),
+ RRTTL(3600)));
rbtnode->addRRset(rrset);
EXPECT_EQ(0, rbtree.erase(Name("p.w.y.d.e.f")));
EXPECT_EQ(14, rbtree.getNodeCount());
@@ -287,7 +286,7 @@
EXPECT_EQ(0, rbtree.erase(Name("g.h")));
EXPECT_EQ(1, rbtree.getNodeCount());
- // rebuild rbtree to cover different execution paths
+ // rebuild rbtree to cover different execution paths
EXPECT_EQ(0, rbtree.insert(Name("a"), &rbtnode));
EXPECT_EQ(0, rbtree.insert(Name("g"), &rbtnode));
EXPECT_EQ(0, rbtree.insert(Name("b"), &rbtnode));
@@ -376,14 +375,14 @@
EXPECT_FALSE(rbtnode->isDelegate());
// add a rrset
- RRsetPtr a_rrset = RRsetPtr(new RRset(Name("d.e.f"), RRClass::IN(), RRType::A(),
- RRTTL(3600)));
+ RRsetPtr a_rrset(new RRset(Name("d.e.f"), RRClass::IN(), RRType::A(),
+ RRTTL(3600)));
rbtnode->addRRset(a_rrset);
EXPECT_FALSE(rbtnode->isDelegate());
// add ns rrset
- RRsetPtr ns_rrset = RRsetPtr(new RRset(Name("d.e.f"), RRClass::IN(), RRType::NS(),
- RRTTL(3600)));
+ RRsetPtr ns_rrset(new RRset(Name("d.e.f"), RRClass::IN(), RRType::NS(),
+ RRTTL(3600)));
rbtnode->addRRset(ns_rrset);
EXPECT_TRUE(rbtnode->isDelegate());
}
More information about the bind10-changes
mailing list