BIND 10 master, updated. 7f881cb954516c9f0b146c4f3bf35b296b102c4a Merge #2090
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Jul 23 09:12:59 UTC 2012
The branch, master has been updated
via 7f881cb954516c9f0b146c4f3bf35b296b102c4a (commit)
via 51cc7bb7a7ed494d4fdf80de77a057e2b3833699 (commit)
via f9ff329aa2fd6573f98201e4d3435dcc827f0820 (commit)
via 09dd3c3bfbea07a37971985f773235872d5a9057 (commit)
via be46391e9694530d17277ebb5dea84f2d2616604 (commit)
via 118ceb3b2229743a4f9ef8e9330bdbc278a7dbb9 (commit)
via b2395c8531d40b25eeb520c76379ffdead02a2ef (commit)
from 9bedc5ab8526c5da673786e93025ebd42c63b597 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 7f881cb954516c9f0b146c4f3bf35b296b102c4a
Merge: 9bedc5a 51cc7bb
Author: Michal 'vorner' Vaner <michal.vaner at nic.cz>
Date: Mon Jul 23 11:11:39 2012 +0200
Merge #2090
Conflicts:
src/lib/datasrc/rbtree.h
commit 51cc7bb7a7ed494d4fdf80de77a057e2b3833699
Author: Michal 'vorner' Vaner <michal.vaner at nic.cz>
Date: Mon Jul 23 10:29:17 2012 +0200
[2090] Comment on switch to bare pointers
commit f9ff329aa2fd6573f98201e4d3435dcc827f0820
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Fri Jul 20 10:25:42 2012 -0700
[2090] use offset_ptr::get() for comparison with raw pointers by !=
at least my version of boost doesn't seem to allow the direct comparison
with != between offset_ptr and raw pointers.
also made some trivial style fixes.
commit 09dd3c3bfbea07a37971985f773235872d5a9057
Author: Michal 'vorner' Vaner <michal.vaner at nic.cz>
Date: Fri Jul 20 11:09:51 2012 +0200
[2090] Fix segfault
The (left|right)Rotate might have changed the parent, so it needs to be
reacquired after it.
commit be46391e9694530d17277ebb5dea84f2d2616604
Author: Michal 'vorner' Vaner <michal.vaner at nic.cz>
Date: Thu Jul 19 14:41:52 2012 +0200
[2090] Limit number of calls to get*()
If they are called multiple times, it is stored into a variable.
Segfaults, needs a fix (again).
commit 118ceb3b2229743a4f9ef8e9330bdbc278a7dbb9
Author: Michal 'vorner' Vaner <michal.vaner at nic.cz>
Date: Thu Jul 19 13:49:16 2012 +0200
[2090] Fix the segfault
There was confusion about left_ and right_. After all, the left and
right depends on your point of view and on how many mirrors there are
around.
commit b2395c8531d40b25eeb520c76379ffdead02a2ef
Author: Michal 'vorner' Vaner <michal.vaner at nic.cz>
Date: Wed Jul 18 19:58:42 2012 +0200
[2090] Replace raw pointers with offset_ptr
At least the ones stored in RBNode. There are many changes to make it
compile after the change. It compiles, but segfaults at the tests.
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/rbtree.h | 267 +++++++++++++++++++++++++++++-----------------
1 file changed, 169 insertions(+), 98 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index a78a399..e777f8f 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -28,6 +28,7 @@
#include <dns/name.h>
#include <boost/utility.hpp>
#include <boost/shared_ptr.hpp>
+#include <boost/interprocess/offset_ptr.hpp>
#include <exceptions/exceptions.h>
#include <ostream>
#include <algorithm>
@@ -89,6 +90,12 @@ private:
/// it.
friend class RBTree<T>;
+ /// \brief Just a type alias
+ ///
+ /// We are going to use a lot of these offset pointers here and they
+ /// have a long name.
+ typedef boost::interprocess::offset_ptr<RBNode<T> > RBNodePtr;
+
/// \name Constructors
///
/// \note The existence of a RBNode without a RBTree is meaningless.
@@ -323,14 +330,47 @@ private:
/// The overhead of the member pointers should be optimised out, as this
/// will probably get completely inlined into predecessor and successor
/// methods.
- const RBNode<T>* abstractSuccessor(RBNode<T>* RBNode<T>::*left,
- RBNode<T>* RBNode<T>::*right) const;
+ const RBNode<T>*
+ abstractSuccessor(typename RBNode<T>::RBNodePtr RBNode<T>::*left,
+ typename RBNode<T>::RBNodePtr RBNode<T>::*right)
+ const;
/// \name Data to maintain the rbtree structure.
+ ///
+ /// We keep them as offset pointers. This is part of a future plan, when we
+ /// want to share the image of the tree between multiple processes.
+ /// However, whenever we have a chance, we switch to bare pointers during
+ /// the processing. The pointers on stack are never shared and the offset
+ /// pointers have non-trivial performance impact.
//@{
- RBNode<T>* parent_;
- RBNode<T>* left_;
- RBNode<T>* right_;
+ RBNodePtr parent_;
+ /// \brief Access the parent_ as bare pointer.
+ RBNode<T>* getParent() {
+ return (parent_.get());
+ }
+ /// \brief Access the parent_ as bare pointer, const.
+ const RBNode<T>* getParent() const {
+ return (parent_.get());
+ }
+ RBNodePtr left_;
+ /// \brief Access the left_ as bare pointer.
+ RBNode<T>* getLeft() {
+ return (left_.get());
+ }
+ /// \brief Access the left_ as bare pointer, const.
+ const RBNode<T>* getLeft() const {
+ return (left_.get());
+ }
+ RBNodePtr right_;
+ /// \brief Access the right_ as bare pointer.
+ RBNode<T>* getRight() {
+ return (right_.get());
+ }
+ /// \brief Access the right_ as bare pointer, const.
+ const RBNode<T>* getRight() const {
+ return (right_.get());
+ }
+ RBNodeColor color_;
//@}
/// \brief Relative name of the node.
@@ -347,7 +387,15 @@ private:
/// big flat tree into several hierarchy trees.
/// \li It saves memory usage as it allows storing only relative names,
/// avoiding storage of the same domain labels multiple times.
- RBNode<T>* down_;
+ RBNodePtr down_;
+ /// \brief Access the down_ as bare pointer.
+ RBNode<T>* getDown() {
+ return (down_.get());
+ }
+ /// \brief Access the down_ as bare pointer, const.
+ const RBNode<T>* getDown() const {
+ return (down_.get());
+ }
/// \brief If callback should be called when traversing this node in
/// RBTree::find().
@@ -393,8 +441,9 @@ RBNode<T>::~RBNode() {
template <typename T>
const RBNode<T>*
-RBNode<T>::abstractSuccessor(RBNode<T>* RBNode<T>::*left, RBNode<T>*
- RBNode<T>::*right) const
+RBNode<T>::abstractSuccessor(typename RBNode<T>::RBNodePtr RBNode<T>::*left,
+ typename RBNode<T>::RBNodePtr RBNode<T>::*right)
+ const
{
// This function is written as a successor. It becomes predecessor if
// the left and right pointers are swapped. So in case of predecessor,
@@ -404,10 +453,11 @@ RBNode<T>::abstractSuccessor(RBNode<T>* RBNode<T>::*left, RBNode<T>*
const RBNode<T>* current = this;
// If it has right node, the successor is the left-most node of the right
// subtree.
- if (current->*right != RBNode<T>::NULL_NODE()) {
- current = current->*right;
- while (current->*left != RBNode<T>::NULL_NODE()) {
- current = current->*left;
+ if ((current->*right).get() != RBNode<T>::NULL_NODE()) {
+ current = (current->*right).get();
+ const RBNode<T>* left_n;
+ while ((left_n = (current->*left).get()) != RBNode<T>::NULL_NODE()) {
+ current = left_n;
}
return (current);
}
@@ -415,10 +465,11 @@ RBNode<T>::abstractSuccessor(RBNode<T>* RBNode<T>::*left, RBNode<T>*
// Otherwise go up until we find the first left branch on our path to
// root. If found, the parent of the branch is the successor.
// Otherwise, we return the null node
- const RBNode<T>* parent = current->parent_;
- while (parent != RBNode<T>::NULL_NODE() && current == parent->*right) {
+ const RBNode<T>* parent = current->getParent();
+ while (parent != RBNode<T>::NULL_NODE() &&
+ current == (parent->*right).get()) {
current = parent;
- parent = parent->parent_;
+ parent = parent->getParent();
}
return (parent);
}
@@ -1018,9 +1069,11 @@ public:
private:
/// \name RBTree balance functions
//@{
- void insertRebalance(RBNode<T>** root, RBNode<T>* node);
- RBNode<T>* rightRotate(RBNode<T>** root, RBNode<T>* node);
- RBNode<T>* leftRotate(RBNode<T>** root, RBNode<T>* node);
+ void insertRebalance(typename RBNode<T>::RBNodePtr* root, RBNode<T>* node);
+ RBNode<T>* rightRotate(typename RBNode<T>::RBNodePtr* root,
+ RBNode<T>* node);
+ RBNode<T>* leftRotate(typename RBNode<T>::RBNodePtr* root,
+ RBNode<T>* node);
//@}
/// \name Helper functions
@@ -1042,8 +1095,8 @@ private:
void nodeFission(RBNode<T>& node, const isc::dns::Name& sub_name);
//@}
- RBNode<T>* NULLNODE;
- RBNode<T>* root_;
+ RBNode<T>* NULLNODE;
+ typename RBNode<T>::RBNodePtr root_;
/// the node count of current tree
unsigned int node_count_;
/// search policy for rbtree
@@ -1061,7 +1114,7 @@ RBTree<T>::RBTree(bool returnEmptyNode) :
template <typename T>
RBTree<T>::~RBTree() {
- deleteHelper(root_);
+ deleteHelper(root_.get());
assert(node_count_ == 0);
}
@@ -1073,25 +1126,28 @@ RBTree<T>::deleteHelper(RBNode<T>* root) {
}
RBNode<T>* node = root;
- while (root->left_ != NULLNODE || root->right_ != NULLNODE) {
- while (node->left_ != NULLNODE || node->right_ != NULLNODE) {
- node = (node->left_ != NULLNODE) ? node->left_ : node->right_;
+ while (root->getLeft() != NULLNODE || root->getRight() != NULLNODE) {
+ RBNode<T>* left(NULLNODE);
+ RBNode<T>* right(NULLNODE);
+ while ((left = node->getLeft()) != NULLNODE ||
+ (right = node->getRight()) != NULLNODE) {
+ node = (left != NULLNODE) ? left : right;
}
- RBNode<T>* parent = node->parent_;
- if (parent->left_ == node) {
+ RBNode<T>* parent = node->getParent();
+ if (parent->getLeft() == node) {
parent->left_ = NULLNODE;
} else {
parent->right_ = NULLNODE;
}
- deleteHelper(node->down_);
+ deleteHelper(node->getDown());
delete node;
--node_count_;
node = parent;
}
- deleteHelper(root->down_);
+ deleteHelper(root->getDown());
delete root;
--node_count_;
}
@@ -1111,7 +1167,7 @@ RBTree<T>::find(const isc::dns::Name& target_name,
isc_throw(isc::BadValue, "RBTree::find is given a non empty chain");
}
- RBNode<T>* node = root_;
+ RBNode<T>* node = root_.get();
Result ret = NOTFOUND;
isc::dns::Name name = target_name;
@@ -1142,7 +1198,7 @@ RBTree<T>::find(const isc::dns::Name& target_name,
// but cheaper way).
if (common_label_count == 1 && node->name_.getLength() != 1) {
node = (node_path.last_comparison_.getOrder() < 0) ?
- node->left_ : node->right_;
+ node->getLeft() : node->getRight();
} else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
if (needsReturnEmptyNode_ || !node->isEmpty()) {
ret = PARTIALMATCH;
@@ -1156,7 +1212,7 @@ RBTree<T>::find(const isc::dns::Name& target_name,
}
node_path.push(node);
name = name - node->name_;
- node = node->down_;
+ node = node->getDown();
} else {
break;
}
@@ -1176,10 +1232,11 @@ RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const {
const RBNode<T>* node = node_path.top();
// if node has sub domain, the next domain is the smallest
// domain in sub domain tree
- if (node->down_ != NULLNODE) {
- const RBNode<T>* left_most = node->down_;
- while (left_most->left_ != NULLNODE) {
- left_most = left_most->left_;
+ const RBNode<T>* down = node->getDown();
+ if (down != NULLNODE) {
+ const RBNode<T>* left_most = down;
+ while (left_most->getLeft() != NULLNODE) {
+ left_most = left_most->getLeft();
}
node_path.push(left_most);
return (left_most);
@@ -1247,12 +1304,13 @@ RBTree<T>::previousNode(RBTreeNodeChain<T>& node_path) const {
while (current != NULLNODE) {
node_path.push(current);
// Go a level down and as much right there as possible
- current = current->down_;
- while (current->right_ != NULLNODE) {
+ current = current->getDown();
+ const RBNode<T>* right(NULLNODE);
+ while ((right = current->getRight()) != NULLNODE) {
// A small trick. The current may be NULLNODE, but
// such node has the right_ pointer and it is equal
// to NULLNODE.
- current = current->right_;
+ current = right;
}
}
// Now, the one on top of the path is the one we want. We
@@ -1326,12 +1384,14 @@ RBTree<T>::previousNode(RBTreeNodeChain<T>& node_path) const {
node_path.push(node);
// Try going as deep as possible, keeping on the right side of the trees
- while (node->down_ != NULLNODE) {
+ const RBNode<T>* down;
+ while ((down = node->getDown()) != NULLNODE) {
// Move to the tree below
- node = node->down_;
+ node = down;
// And get as much to the right of the tree as possible
- while (node->right_ != NULLNODE) {
- node = node->right_;
+ const RBNode<T>* right(NULLNODE);
+ while ((right = node->getRight()) != NULLNODE) {
+ node = right;
}
// Now, we found the right-most node in the sub-tree, we need to
// include it in the path
@@ -1348,7 +1408,7 @@ typename RBTree<T>::Result
RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
using namespace helper;
RBNode<T>* parent = NULLNODE;
- RBNode<T>* current = root_;
+ RBNode<T>* current = root_.get();
RBNode<T>* up_node = NULLNODE;
isc::dns::Name name = target_name;
@@ -1369,14 +1429,14 @@ RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
if (common_label_count == 1 && current->name_.getLength() != 1) {
parent = current;
order = compare_result.getOrder();
- current = order < 0 ? current->left_ : current->right_;
+ current = order < 0 ? current->getLeft() : current->getRight();
} else {
// insert sub domain to sub tree
if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
parent = NULLNODE;
up_node = current;
name = name - current->name_;
- current = current->down_;
+ current = current->getDown();
} else {
// The number of labels in common is fewer
// than the number of labels at the current
@@ -1392,7 +1452,7 @@ RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
}
}
- RBNode<T>** current_root = (up_node != NULLNODE) ?
+ typename RBNode<T>::RBNodePtr* 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, if we can make sure no exception will be
@@ -1442,7 +1502,8 @@ RBTree<T>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
std::swap(node.data_, down_node->data_);
std::swap(node.flags_, down_node->flags_);
- down_node->down_ = node.down_;
+ down_node->down_ = node.getDown();
+
node.down_ = down_node.get();
// Restore the color of the node (may have gotten changed by the flags swap)
@@ -1461,42 +1522,47 @@ RBTree<T>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
template <typename T>
void
-RBTree<T>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
-
+RBTree<T>::insertRebalance(typename RBNode<T>::RBNodePtr* root,
+ RBNode<T>* node)
+{
RBNode<T>* uncle;
- while (node != *root && node->parent_->getColor() == RBNode<T>::RED) {
- if (node->parent_ == node->parent_->parent_->left_) {
- uncle = node->parent_->parent_->right_;
+ RBNode<T>* parent;
+ while (node != (*root).get() &&
+ (parent = node->getParent())->getColor() == RBNode<T>::RED) {
+ if (parent == parent->getParent()->getLeft()) {
+ uncle = parent->getParent()->getRight();
if (uncle->getColor() == RBNode<T>::RED) {
- node->parent_->setColor(RBNode<T>::BLACK);
+ parent->setColor(RBNode<T>::BLACK);
uncle->setColor(RBNode<T>::BLACK);
- node->parent_->parent_->setColor(RBNode<T>::RED);
- node = node->parent_->parent_;
+ parent->getParent()->setColor(RBNode<T>::RED);
+ node = parent->getParent();
} else {
- if (node == node->parent_->right_) {
- node = node->parent_;
+ if (node == parent->getRight()) {
+ node = parent;
leftRotate(root, node);
+ parent = node->getParent();
}
- node->parent_->setColor(RBNode<T>::BLACK);
- node->parent_->parent_->setColor(RBNode<T>::RED);
- rightRotate(root, node->parent_->parent_);
+ parent->setColor(RBNode<T>::BLACK);
+ parent->getParent()->setColor(RBNode<T>::RED);
+ rightRotate(root, parent->getParent());
}
} else {
- uncle = node->parent_->parent_->left_;
+ uncle = parent->getParent()->getLeft();
if (uncle->getColor() == RBNode<T>::RED) {
- node->parent_->setColor(RBNode<T>::BLACK);
+ parent->setColor(RBNode<T>::BLACK);
uncle->setColor(RBNode<T>::BLACK);
- node->parent_->parent_->setColor(RBNode<T>::RED);
- node = node->parent_->parent_;
+ parent->getParent()->setColor(RBNode<T>::RED);
+ node = parent->getParent();
} else {
- if (node == node->parent_->left_) {
- node = node->parent_;
+ if (node == parent->getLeft()) {
+ node = parent;
rightRotate(root, node);
+ parent = node->getParent();
}
- node->parent_->setColor(RBNode<T>::BLACK);
- node->parent_->parent_->setColor(RBNode<T>::RED);
- leftRotate(root, node->parent_->parent_);
+ parent->setColor(RBNode<T>::BLACK);
+ parent->getParent()->setColor(RBNode<T>::RED);
+ leftRotate(root, parent->getParent());
}
}
}
@@ -1507,24 +1573,26 @@ RBTree<T>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
template <typename T>
RBNode<T>*
-RBTree<T>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
- RBNode<T>* right = node->right_;
- node->right_ = right->left_;
- if (right->left_ != NULLNODE) {
- right->left_->parent_ = node;
- right->left_->setSubTreeRoot(false);
+RBTree<T>::leftRotate(typename RBNode<T>::RBNodePtr* root, RBNode<T>* node) {
+ RBNode<T>* const right = node->getRight();
+ RBNode<T>* const rleft = right->getLeft();
+ node->right_ = rleft;
+ if (rleft != NULLNODE) {
+ rleft->parent_ = node;
+ rleft->setSubTreeRoot(false);
} else {
- right->left_->setSubTreeRoot(true);
+ rleft->setSubTreeRoot(true);
}
- right->parent_ = node->parent_;
+ RBNode<T>* const parent = node->getParent();
+ right->parent_ = parent;
- if (node->parent_ != NULLNODE) {
+ if (parent != NULLNODE) {
right->setSubTreeRoot(false);
- if (node == node->parent_->left_) {
- node->parent_->left_ = right;
+ if (node == parent->getLeft()) {
+ parent->left_ = right;
} else {
- node->parent_->right_ = right;
+ parent->right_ = right;
}
} else {
right->setSubTreeRoot(true);
@@ -1539,24 +1607,26 @@ RBTree<T>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
template <typename T>
RBNode<T>*
-RBTree<T>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
- RBNode<T>* left = node->left_;
- node->left_ = left->right_;
- if (left->right_ != NULLNODE) {
- left->right_->parent_ = node;
- left->right_->setSubTreeRoot(false);
+RBTree<T>::rightRotate(typename RBNode<T>::RBNodePtr* root, RBNode<T>* node) {
+ RBNode<T>* const left = node->getLeft();
+ RBNode<T>* const lright = left->getRight();
+ node->left_ = lright;
+ if (lright != NULLNODE) {
+ lright->parent_ = node;
+ lright->setSubTreeRoot(false);
} else {
- left->right_->setSubTreeRoot(true);
+ lright->setSubTreeRoot(false);
}
- left->parent_ = node->parent_;
+ RBNode<T>* const parent = node->getParent();
+ left->parent_ = parent;
- if (node->parent_ != NULLNODE) {
+ if (node->getParent() != NULLNODE) {
left->setSubTreeRoot(false);
- if (node == node->parent_->right_) {
- node->parent_->right_ = left;
+ if (node == parent->getRight()) {
+ parent->right_ = left;
} else {
- node->parent_->left_ = left;
+ parent->left_ = left;
}
} else {
left->setSubTreeRoot(true);
@@ -1575,7 +1645,7 @@ void
RBTree<T>::dumpTree(std::ostream& os, unsigned int depth) const {
indent(os, depth);
os << "tree has " << node_count_ << " node(s)\n";
- dumpTreeHelper(os, root_, depth);
+ dumpTreeHelper(os, root_.get(), depth);
}
template <typename T>
@@ -1600,15 +1670,16 @@ RBTree<T>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
}
os << "\n";
- if (node->down_ != NULLNODE) {
+ const RBNode<T>* down = node->getDown();
+ if (down != NULLNODE) {
indent(os, depth + 1);
os << "begin down from " << node->name_.toText() << "\n";
- dumpTreeHelper(os, node->down_, depth + 1);
+ dumpTreeHelper(os, down, depth + 1);
indent(os, depth + 1);
os << "end down from " << node->name_.toText() << "\n";
}
- dumpTreeHelper(os, node->left_, depth + 1);
- dumpTreeHelper(os, node->right_, depth + 1);
+ dumpTreeHelper(os, node->getLeft(), depth + 1);
+ dumpTreeHelper(os, node->getRight(), depth + 1);
}
template <typename T>
More information about the bind10-changes
mailing list