[svn] commit: r3454 - in /branches/trac397/src/bin/auth: rbt_datasrc.cc rbt_datasrc.h
BIND 10 source code commits
bind10-changes at lists.isc.org
Fri Nov 5 02:24:37 UTC 2010
Author: hanfeng
Date: Fri Nov 5 02:24:36 2010
New Revision: 3454
Log:
add some comment and fix bug that the relation between up and down doesn't maintain correctly
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 Fri Nov 5 02:24:36 2010
@@ -20,8 +20,9 @@
using namespace isc::dns;
namespace {
- Name operator-(const Name &super_name, const Name &sub_name)
- {
+ /// helper function to remove the base domain from super domain
+ /// the precondition of this function is thant super_name contains sub_name
+ Name operator-(const Name &super_name, const Name &sub_name) {
return super_name.split(0, super_name.getLabelCount() - sub_name.getLabelCount());
}
}
@@ -36,22 +37,20 @@
name_(name),
rrsets_(rrsets),
down_(NULL),
- is_delegate_(false)
-{
-}
-
-RBNode::~RBNode()
-{
+ is_delegate_(false),
+ is_nonterminal_(false) {
+}
+
+RBNode::~RBNode() {
if (down_)
delete down_;
}
-RBNode* RBNode::successor()
-{
+RBNode*
+RBNode::successor() {
RBNode* current = this;
- if (right_ != right_->right_)
- {
+ if (right_ != right_->right_) {
current = right_;
while (current->left_ != current->left_->left_)
current = current->left_;
@@ -59,50 +58,52 @@
}
RBNode* s = current->parent_;
- while (s != s->left_ && current == s->right_)
- {
+ while (s != s->left_ && current == s->right_) {
current = s;
s = s->parent_;
}
return s;
}
-
+/// no duplication is checked now
int
-RBNode::addRRset(RRsetPtr rrset)
-{
+RBNode::addRRset(RRsetPtr rrset) {
if (rrset->getType() == RRType::NS())
is_delegate_ = true;
if (rrsets_.get() == NULL)
rrsets_.reset(new RRsetList());
rrsets_->addRRset(rrset);
+ is_nonterminal_ = false;
return 0;
}
void
-RBNode::cloneDNSData(RBNode &node)
-{
+RBNode::cloneDNSData(RBNode &node) {
node.name_ = name_;
node.rrsets_ = rrsets_;
- node.down_ = down_;
node.is_delegate_ = is_delegate_;
-}
-
-RBTree::RBTree(RBNode *up)
-{
+ node.is_nonterminal_ = is_nonterminal_;
+}
+
+void
+RBNode::setDownTree(RBTree *down) {
+ down_ = down;
+ if (down)
+ down->up_ = this;
+}
+
+
+RBTree::RBTree() {
NULLNODE = new RBNode(Name(" "));
NULLNODE->parent_ = NULLNODE->left_ = NULLNODE->right_ = NULLNODE;
NULLNODE->color_ = BLACK;
root_ = NULLNODE;
node_count_ = 0;
- up_ = up;
- if (up)
- up->down_ = this;
-}
-
-
-RBTree::~RBTree()
-{
+ up_ = NULL;
+}
+
+
+RBTree::~RBTree() {
assert(root_ != NULL);
delete NULLNODE;
@@ -110,8 +111,7 @@
return;
RBNode* node = root_;
- while (root_->left_ != NULLNODE || root_->right_ != NULLNODE)
- {
+ while (root_->left_ != NULLNODE || root_->right_ != NULLNODE) {
while (node->left_ != NULLNODE || node->right_ != NULLNODE)
node = (node->left_ != NULLNODE) ? node->left_ : node->right_;
@@ -128,58 +128,37 @@
root_ = NULL;
}
-RBTree::FindResult RBTree::find(const Name &name, RBNode **node)const
-{
+RBTree::FindResult
+RBTree::find(const Name &name, RBNode **node)const {
RBTree *tree;
return findHelper(name, &tree, node);
}
-int
-RBTree::getNodeCount() const
-{
- return getNodeCountHelper(root_);
-
-}
-
-int
-RBTree::getNodeCountHelper(const RBNode *node) const
-{
- 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_);
-
-}
-
-RBTree::FindResult RBTree::findHelper(const Name &name, RBTree **tree, RBNode **ret)const
-{
+RBTree::FindResult
+RBTree::findHelper(const Name &name, RBTree **tree, RBNode **ret)const {
RBNode* node = root_;
- while (node != NULLNODE)
- {
+ while (node != NULLNODE) {
NameComparisonResult compare_result = name.compare(node->name_);
NameComparisonResult::NameRelation relation = compare_result.getRelation();
- if (relation == NameComparisonResult::EQUAL)
- {
+ if (relation == NameComparisonResult::EQUAL) {
*tree = (RBTree *)this;
*ret = node;
return RBTree::EXACTMATCH;
}
- else
- {
+ 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)
- {
- if (node->isDelegate())
- {
+ 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;
@@ -193,68 +172,74 @@
return RBTree::NOTFOUND;
}
-
-
-int RBTree::insert(const Name &name, RBNode **new_node)
-{
+int
+RBTree::getNodeCount() const {
+ return getNodeCountHelper(root_);
+
+}
+
+int
+RBTree::getNodeCountHelper(const RBNode *node) const {
+ 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_);
+}
+
+int
+RBTree::insert(const Name &name, RBNode **new_node) {
RBNode* parent = NULLNODE;
RBNode* current = root_;
int order = -1;
- while (current != NULLNODE)
- {
+ while (current != NULLNODE) {
parent = current;
NameComparisonResult compare_result = name.compare(current->name_);
NameComparisonResult::NameRelation relation = compare_result.getRelation();
- if (relation == NameComparisonResult::EQUAL)
- {
+ if (relation == NameComparisonResult::EQUAL) {
if (new_node)
*new_node = current;
+ /// if the node is non-ternimal, it doesn't exist, so we return 0
return current->rrsets_.get() ? 1 : 0;
}
- else
- {
+ else {
int common_label_count = compare_result.getCommonLabels();
- if (common_label_count == 1)
- {
+ if (common_label_count == 1) {
order = compare_result.getOrder();
current = order < 0 ? current->left_ : current->right_;
- }
- else
- {
- if (relation == NameComparisonResult::SUBDOMAIN)
- {
+ } else {
+ //insert sub domain to sub tree
+ if (relation == NameComparisonResult::SUBDOMAIN) {
if (NULL == current->down_)
- current->down_ = new RBTree(current);
+ current->setDownTree(new RBTree());
return current->down_->insert(name - current->name_, new_node);
- }
- else
- {
+ } 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);
Name sub_name = current->name_ - common_ancestor;
current->name_ = common_ancestor;
RBTree *down_old = current->down_;
- current->down_ = new RBTree(current);
+ current->setDownTree(new RBTree());
RBNode *sub_root;
current->down_->insert(sub_name, &sub_root);
current->cloneDNSData(*sub_root);
+ sub_root->setDownTree(down_old);
sub_root->name_ = sub_name;
- sub_root->down_ = down_old;
+
current->rrsets_.reset();
- if (down_old)
- down_old->up_ = sub_root;
-
//if insert name is the super domain of current node, no need insert
//otherwise insert it into the down tree
- if (name.getLabelCount() == common_label_count)
- {
+ 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);
}
- else
- return current->down_->insert(name - common_ancestor, new_node);
}
}
@@ -277,27 +262,21 @@
return 0;
}
-void RBTree::insertRebalance(RBNode * node)
-{
+void
+RBTree::insertRebalance(RBNode * node) {
RBNode* uncle;
- while (node->parent_->color_ == RED)
- {
- if (node->parent_ == node->parent_->parent_->left_)
- {
+ while (node->parent_->color_ == RED) {
+ if (node->parent_ == node->parent_->parent_->left_) {
uncle = node->parent_->parent_->right_;
- if (uncle->color_ == RED)
- {
+ if (uncle->color_ == RED) {
node->parent_->color_ = BLACK;
uncle->color_ = BLACK;
node->parent_->parent_->color_ = RED;
node = node->parent_->parent_;
- }
- else
- {
- if (node == node->parent_->right_)
- {
+ } else {
+ if (node == node->parent_->right_) {
node = node->parent_;
leftRotate(node);
}
@@ -307,22 +286,16 @@
rightRotate(node->parent_->parent_);
}
- }
- else
- {
+ } else {
uncle = node->parent_->parent_->left_;
- if (uncle->color_ == RED)
- {
+ if (uncle->color_ == RED) {
node->parent_->color_ = BLACK;
uncle->color_ = BLACK;
node->parent_->parent_->color_ = RED;
node = node->parent_->parent_;
- }
- else
- {
- if (node == node->parent_->left_)
- {
+ } else {
+ if (node == node->parent_->left_) {
node = node->parent_;
rightRotate(node);
}
@@ -340,8 +313,8 @@
}
-RBNode* RBTree::leftRotate(RBNode * p)
-{
+RBNode*
+RBTree::leftRotate(RBNode * p) {
RBNode* c = p->right_;
p->right_ = c->left_;
@@ -364,8 +337,8 @@
return c;
}
-RBNode* RBTree::rightRotate(RBNode * p)
-{
+RBNode*
+RBTree::rightRotate(RBNode * p) {
RBNode* c = p->left_;
p->left_ = c->right_;
@@ -389,31 +362,30 @@
}
-int RBTree::erase(const Name &name)
-{
+int
+RBTree::erase(const Name &name) {
RBNode *node;
RBTree *tree;
if (findHelper(name, &tree, &node) != RBTree::EXACTMATCH)
return 1;
- //cann't delete non terminal
+ /// cann't delete non terminal
if (node->down_ != NULL)
return 1;
tree->eraseNode(node);
- //merge down to up
- if (tree->node_count_ == 1 && tree->up_ != NULL && tree->up_->rrsets_.get() == NULL)
- {
+ ///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_);
tree->root_->cloneDNSData(*up);
+ up->setDownTree(tree->root_->down_);
+ tree->root_->setDownTree(NULL);
up->name_ = merged_name;
-
+ up->is_nonterminal_ = false;
delete tree;
- }
- else if (tree->node_count_ == 0 && tree->up_)
- {
- tree->up_->down_ = NULL;
+ } else if (tree->node_count_ == 0 && tree->up_) { ///delete empty tree
+ tree->up_->setDownTree(NULL);
delete tree;
}
@@ -421,8 +393,8 @@
}
-void RBTree::eraseNode(RBNode *node)
-{
+void
+RBTree::eraseNode(RBNode *node) {
RBNode* y = NULLNODE;
RBNode* x = NULLNODE;
@@ -445,12 +417,10 @@
else
y->parent_->right_ = x;
- if (y != node)
- {
- node->name_ = y->name_;
- node->down_ = y->down_;
- node->rrsets_= y->rrsets_;
- node->is_delegate_ = y->is_delegate_;
+ if (y != node) {
+ y->cloneDNSData(*node);
+ node->setDownTree(y->down_);
+ y->down_ = NULL;
}
if (y->color_ == BLACK)
@@ -462,40 +432,31 @@
y->left_ = NULL;
y->right_ = NULL;
- y->down_ = NULL;
delete y;
--node_count_;
}
-void RBTree::deleteRebalance(RBNode * node)
-{
+void
+RBTree::deleteRebalance(RBNode * node) {
RBNode* w = NULLNODE;
- while (node != root_ && node->color_ == BLACK)
- {
- if (node == node->parent_->left_)
- {
+ while (node != root_ && node->color_ == BLACK) {
+ if (node == node->parent_->left_) {
w = node->parent_->right_;
- if (w->color_ == RED)
- {
+ if (w->color_ == RED) {
w->color_ = BLACK;
node->parent_->color_ = RED;
leftRotate(node->parent_);
w = node->parent_->right_;
}
- if (w->left_->color_ == BLACK && w->right_->color_ == BLACK)
- {
+ if (w->left_->color_ == BLACK && w->right_->color_ == BLACK) {
w->color_ = RED;
node = node->parent_;
- }
-
- else
- {
- if (w->right_->color_ == BLACK)
- {
+ } else {
+ if (w->right_->color_ == BLACK) {
w->left_->color_ = BLACK;
w->color_ = RED;
rightRotate(w);
@@ -508,26 +469,18 @@
leftRotate(node->parent_);
node = root_;
}
- }
- else
- {
+ } else {
w = node->parent_->left_;
- if (w->color_ == RED)
- {
+ if (w->color_ == RED) {
w->color_ = BLACK;
node->parent_->color_ = RED;
rightRotate(node->parent_);
w = node->parent_->left_;
- }
- if (w->right_->color_ == BLACK && w->left_->color_ == BLACK)
- {
+ } if (w->right_->color_ == BLACK && w->left_->color_ == BLACK) {
w->color_ = RED;
node = node->parent_;
- }
- else
- {
- if (w->left_->color_ == BLACK)
- {
+ } else {
+ if (w->left_->color_ == BLACK) {
w->right_->color_ = BLACK;
w->color_ = RED;
leftRotate(w);
@@ -552,8 +505,7 @@
}while(0)
void
-RBTree::printTree(int depth)const
-{
+RBTree::printTree(int depth) const {
INDNET(depth);
std::cout << "tree has node " << node_count_ << "\n";
printTreeHelper(root_, depth);
@@ -561,13 +513,12 @@
void
-RBTree::printTreeHelper(RBNode *node, int depth)const
-{
+RBTree::printTreeHelper(RBNode *node, int depth) const {
INDNET(depth);
std::cout << node->name_.toText() << " (" << ((node->color_ == BLACK) ? "black" : "red") << ")\n";
- if (node->down_)
- {
+ std::cout << ((node->isNonterminal()) ? "[non-terminal] \n" : "\n");
+ if (node->down_) {
assert(node->down_->up_ == node);
INDNET(depth + 1);
std::cout << "begin down from "<< node->name_.toText() << "\n";
@@ -578,16 +529,14 @@
if (node->left_ != NULLNODE)
printTreeHelper(node->left_, depth + 1);
- else
- {
+ else {
INDNET(depth + 1);
std::cout << "NULL\n";
}
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 Fri Nov 5 02:24:36 2010
@@ -28,21 +28,36 @@
enum RBTreeColor {BLACK = 1, RED};
class RBTree;
-class RBNode
-{
+/// 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
+/// 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 {
public:
friend class RBTree;
typedef boost::shared_ptr<RRsetList> RRsetListPtr;
+ ///whether current domain name contains ns records
bool isDelegate() const { return is_delegate_;}
+ //subname has rrset, but it self doesn't has
+ bool isNonterminal() const { return is_nonterminal_;}
int addRRset(RRsetPtr rrset);
- Name getName() const {return name_;}
+ const Name &getName() const {return name_;}
+
+ //next domain name which is bigger than current one
+ RBNode * successor();
private:
RBNode(const Name &name, RRsetListPtr rrsets = RRsetListPtr(), RBNode* nullnode = NULL);
~RBNode(); //the class isn't left to be inherited
- RBNode * successor();
void cloneDNSData(RBNode &node);
+ void setDownTree(RBTree *down);
/// data to maintain the rbtree balance
RBNode * parent_;
@@ -52,27 +67,43 @@
/// data to carry dns info
Name name_;
-
RRsetListPtr rrsets_;
RBTree * down_;
bool is_delegate_;
-
+ bool is_nonterminal_;
};
-
-class RBTree
-{
+/// RBTree is a generic red black tree, it contains all the node with same suffix
+/// 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 {
+ friend class RBNode;
public:
enum FindResult{EXACTMATCH, FINDREFERRAL, NOTFOUND};
- RBTree(RBNode *up = NULL);
+ RBTree();
~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
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
int getNodeCount() const;
+
+
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
+ int insert(const Name &name, RBNode **inserted_node);
- int insert(const Name &name, RBNode **inserted_node);
+ /// if the node doesn't exist, return value will be one otherwise zero
int erase(const Name &name);
private:
@@ -82,8 +113,12 @@
RBNode * leftRotate(RBNode* p);
void printTreeHelper(RBNode *node, int depth)const;
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);
RBNode * root_;
RBNode * NULLNODE;
More information about the bind10-changes
mailing list