BIND 10 master, updated. 9c3f96ecec2fe57a90680b80fbee8079c94c87f3 [master] Add ChangeLog for #2811
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Aug 5 05:59:47 UTC 2013
The branch, master has been updated
via 9c3f96ecec2fe57a90680b80fbee8079c94c87f3 (commit)
via 7c0bad1643af13dedf9356e9fb3a51264b7481de (commit)
via 07f62405839389c802c751ddac3ca0dd43ceb754 (commit)
via ccdb49aa255c988dd3f03be21b9511794af288f5 (commit)
via f36f677e841adddbaa762480d0cf8b961c098df1 (commit)
via c386d06ac5239ae26446c3bb75143ac54820698b (commit)
via 56f41442f0a647c959e23d8b96ef949607ce98d4 (commit)
via f6fd9cc583267c0ddf779ee0d0fce7ffa697c554 (commit)
via e323b235b5cd03fda009b976fa7765f032e4ed35 (commit)
via 063f70ad570dfc5d8697341bf8643ebe3eb80d7c (commit)
via 363e37a380d7bbfca480e2008b3c135029647d69 (commit)
via ee0e068ef274d482659b11f444d67fa5d0b06de7 (commit)
from 59a4d0243d77ae0a12a8832e383892485157447a (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 9c3f96ecec2fe57a90680b80fbee8079c94c87f3
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 5 11:24:08 2013 +0530
[master] Add ChangeLog for #2811
commit 7c0bad1643af13dedf9356e9fb3a51264b7481de
Merge: 59a4d02 07f6240
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 5 11:15:33 2013 +0530
Merge branch 'trac2811_2'
-----------------------------------------------------------------------
Summary of changes:
ChangeLog | 7 +
src/lib/datasrc/memory/domaintree.h | 238 ++++++++++++++++----
.../datasrc/tests/memory/domaintree_unittest.cc | 114 +++++++++-
3 files changed, 311 insertions(+), 48 deletions(-)
-----------------------------------------------------------------------
diff --git a/ChangeLog b/ChangeLog
index 04bf723..9b43199 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+650. [func] muks
+ The DomainTree rebalancing code has been updated to be more
+ understandable. This ChangeLog entry is made just to make a note
+ of this change. The change should not cause any observable
+ difference whatsoever.
+ (Trac# 2811, git 7c0bad1643af13dedf9356e9fb3a51264b7481de)
+
649. [func] muks
The default b10-xfrout also_notify port has been changed from
0 to 53.
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 36e1bc9..5f41371 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -356,6 +356,16 @@ private:
}
}
+ /// \brief Returns if the node color is black
+ bool isBlack() const {
+ return (getColor() == BLACK);
+ }
+
+ /// \brief Returns if the node color is red
+ bool isRed() const {
+ return (!isBlack());
+ }
+
/// \brief Sets the color of this node
void setColor(const DomainTreeNodeColor color) {
if (color == RED) {
@@ -435,6 +445,21 @@ public:
/// This method never throws an exception.
const DomainTreeNode<T>* predecessor() const;
+ /// \brief returns the node distance from the root of its subtree
+ size_t getDistance() const {
+ size_t nodes = 1;
+ for (const DomainTreeNode<T>* node = this;
+ node != NULL;
+ node = node->getParent()) {
+ if (node->isSubTreeRoot()) {
+ break;
+ }
+ ++nodes;
+ }
+
+ return (nodes);
+ }
+
private:
/// \brief private shared implementation of successor and predecessor
///
@@ -489,6 +514,41 @@ private:
const DomainTreeNode<T>* getRight() const {
return (right_.get());
}
+
+ /// \brief Access grandparent node as bare pointer.
+ ///
+ /// The grandparent node is the parent's parent.
+ ///
+ /// \return the grandparent node if one exists, NULL otherwise.
+ DomainTreeNode<T>* getGrandParent() {
+ DomainTreeNode<T>* parent = getParent();
+ if (parent != NULL) {
+ return (parent->getParent());
+ } else {
+ // If there's no parent, there's no grandparent.
+ return (NULL);
+ }
+ }
+
+ /// \brief Access uncle node as bare pointer.
+ ///
+ /// An uncle node is defined as the parent node's sibling. It exists
+ /// at the same level as the parent.
+ ///
+ /// \return the uncle node if one exists, NULL otherwise.
+ DomainTreeNode<T>* getUncle() {
+ DomainTreeNode<T>* grandparent = getGrandParent();
+ if (grandparent == NULL) {
+ // If there's no grandparent, there's no uncle.
+ return (NULL);
+ }
+ if (getParent() == grandparent->getLeft()) {
+ return (grandparent->getRight());
+ } else {
+ return (grandparent->getLeft());
+ }
+ }
+
//@}
/// \brief The subdomain tree.
@@ -1814,11 +1874,13 @@ DomainTree<T>::insert(util::MemorySegment& mem_sgmt,
} else if (order < 0) {
node->setSubTreeRoot(false);
parent->left_ = node;
+ insertRebalance(current_root, node);
} else {
node->setSubTreeRoot(false);
parent->right_ = node;
+ insertRebalance(current_root, node);
}
- insertRebalance(current_root, node);
+
if (new_node != NULL) {
*new_node = node;
}
@@ -1894,61 +1956,143 @@ DomainTree<T>::nodeFission(util::MemorySegment& mem_sgmt,
}
+/// \brief Fix Red-Black tree properties after an ordinary BST
+/// insertion.
+///
+/// After a normal binary search tree insertion, the Red-Black tree
+/// properties may be violated. This method fixes these properties by
+/// doing tree rotations and recoloring nodes in the tree appropriately.
+///
+/// \param subtree_root The root of the current sub-tree where the node
+/// is being inserted.
+/// \param node The node which was inserted by ordinary BST insertion.
template <typename T>
void
DomainTree<T>::insertRebalance
- (typename DomainTreeNode<T>::DomainTreeNodePtr* root,
+ (typename DomainTreeNode<T>::DomainTreeNodePtr* subtree_root,
DomainTreeNode<T>* node)
{
- DomainTreeNode<T>* uncle;
- DomainTreeNode<T>* parent;
- while (node != (*root).get() &&
- ((parent = node->getParent())->getColor()) ==
- DomainTreeNode<T>::RED) {
- // Here, node->parent_ is not NULL and it is also red, so
- // node->parent_->parent_ is also not NULL.
- if (parent == parent->getParent()->getLeft()) {
- uncle = parent->getParent()->getRight();
-
- if (uncle != NULL && uncle->getColor() ==
- DomainTreeNode<T>::RED) {
- parent->setColor(DomainTreeNode<T>::BLACK);
- uncle->setColor(DomainTreeNode<T>::BLACK);
- parent->getParent()->setColor(DomainTreeNode<T>::RED);
- node = parent->getParent();
- } else {
- if (node == parent->getRight()) {
- node = parent;
- leftRotate(root, node);
- parent = node->getParent();
- }
- parent->setColor(DomainTreeNode<T>::BLACK);
- parent->getParent()->setColor(DomainTreeNode<T>::RED);
- rightRotate(root, parent->getParent());
- }
+ // The node enters this method colored RED. We assume in our
+ // red-black implementation that NULL values in left and right
+ // children are BLACK.
+ //
+ // Case 1. If node is at the subtree root, we don't need to change
+ // its position in the tree. We re-color it BLACK further below
+ // (right before we return).
+ while (node != (*subtree_root).get()) {
+ // Case 2. If the node is not subtree root, but its parent is
+ // colored BLACK, then we're done. This is because the new node
+ // introduces a RED node in the path through it (from its
+ // subtree root to its children colored BLACK) but doesn't
+ // change the red-black properties.
+ DomainTreeNode<T>* parent = node->getParent();
+ if (parent->isBlack()) {
+ break;
+ }
+
+ DomainTreeNode<T>* uncle = node->getUncle();
+ DomainTreeNode<T>* grandparent = node->getGrandParent();
+
+ if ((uncle != NULL) && uncle->isRed()) {
+ // Case 3. Here, the node's parent is colored RED and the
+ // uncle node is also RED. In this case, the grandparent
+ // must be BLACK (due to existing red-black state). We set
+ // both the parent and uncle nodes to BLACK then, change the
+ // grandparent to RED, and iterate the while loop with
+ // node = grandparent. This is the only case that causes
+ // insertion to have a max insertion time of log(n).
+ parent->setColor(DomainTreeNode<T>::BLACK);
+ uncle->setColor(DomainTreeNode<T>::BLACK);
+ grandparent->setColor(DomainTreeNode<T>::RED);
+ node = grandparent;
} else {
- uncle = parent->getParent()->getLeft();
-
- if (uncle != NULL && uncle->getColor() ==
- DomainTreeNode<T>::RED) {
- parent->setColor(DomainTreeNode<T>::BLACK);
- uncle->setColor(DomainTreeNode<T>::BLACK);
- parent->getParent()->setColor(DomainTreeNode<T>::RED);
- node = parent->getParent();
+ // Case 4. Here, the node and node's parent are colored RED,
+ // and the uncle node is BLACK. Only in this case, tree
+ // rotations are necessary.
+
+ /* First we check if we need to convert to a canonical form:
+ *
+ * (a) If the node is the right-child of its parent, and the
+ * node's parent is the left-child of the node's
+ * grandparent, rotate left about the parent so that the old
+ * 'node' becomes the new parent, and the old parent becomes
+ * the new 'node'.
+ *
+ * G(B) G(B)
+ * / \ / \
+ * P(R) U(B) => P*(R) U(B)
+ * \ /
+ * N(R) N*(R)
+ *
+ * (P* is old N, N* is old P)
+ *
+ * (b) If the node is the left-child of its parent, and the
+ * node's parent is the right-child of the node's
+ * grandparent, rotate right about the parent so that the
+ * old 'node' becomes the new parent, and the old parent
+ * becomes the new 'node'.
+ *
+ * G(B) G(B)
+ * / \ / \
+ * U(B) P(R) => U(B) P*(R)
+ * / \
+ * N(R) N*(R)
+ *
+ * (P* is old N, N* is old P)
+ */
+ if ((node == parent->getRight()) &&
+ (parent == grandparent->getLeft())) {
+ node = parent;
+ leftRotate(subtree_root, parent);
+ } else if ((node == parent->getLeft()) &&
+ (parent == grandparent->getRight())) {
+ node = parent;
+ rightRotate(subtree_root, parent);
+ }
+
+ // Also adjust the parent variable (node is already adjusted
+ // above). The grandparent variable need not be adjusted.
+ parent = node->getParent();
+
+ /* Here, we're in a canonical form where the uncle node is
+ * BLACK and both the node and its parent are together
+ * either left-children or right-children of their
+ * corresponding parents.
+ *
+ * G(B) or G(B)
+ * / \ / \
+ * P(R) U(B) U(B) P(R)
+ * / \
+ * N(R) N(R)
+ *
+ * We rotate around the grandparent, right or left,
+ * depending on the orientation above, color the old
+ * grandparent RED (it used to be BLACK) and color the
+ * parent BLACK (it used to be RED). This restores the
+ * red-black property that the number of BLACK nodes from
+ * subtree root to the leaves (the NULL children which are
+ * assumed BLACK) are equal, and that every RED node has a
+ * BLACK parent.
+ */
+ parent->setColor(DomainTreeNode<T>::BLACK);
+ grandparent->setColor(DomainTreeNode<T>::RED);
+
+ if (node == parent->getLeft()) {
+ rightRotate(subtree_root, grandparent);
} else {
- if (node == parent->getLeft()) {
- node = parent;
- rightRotate(root, node);
- parent = node->getParent();
- }
- parent->setColor(DomainTreeNode<T>::BLACK);
- parent->getParent()->setColor(DomainTreeNode<T>::RED);
- leftRotate(root, parent->getParent());
+ leftRotate(subtree_root, grandparent);
}
+
+ // In this case, the tree is ready now and we explicitly
+ // break out of the loop here. Even if we continue the loop,
+ // it will exit the loop in case 2 above, but that's not so
+ // obvious.
+ break;
}
}
- (*root)->setColor(DomainTreeNode<T>::BLACK);
+ // Color sub-tree roots black.
+ (*subtree_root)->setColor(DomainTreeNode<T>::BLACK);
}
@@ -2043,7 +2187,7 @@ DomainTree<T>::dumpTreeHelper(std::ostream& os,
indent(os, depth);
os << node->getLabels() << " ("
- << ((node->getColor() == DomainTreeNode<T>::BLACK) ? "black" : "red")
+ << (node->isBlack() ? "black" : "red")
<< ")";
if (node->isEmpty()) {
os << " [invisible]";
@@ -2107,7 +2251,7 @@ DomainTree<T>::dumpDotHelper(std::ostream& os,
}
os << "\"] [";
- if (node->getColor() == DomainTreeNode<T>::RED) {
+ if (node->isRed()) {
os << "color=red";
} else {
os << "color=black";
diff --git a/src/lib/datasrc/tests/memory/domaintree_unittest.cc b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
index 45e256a..3e6bceb 100644
--- a/src/lib/datasrc/tests/memory/domaintree_unittest.cc
+++ b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
@@ -17,6 +17,7 @@
#include <exceptions/exceptions.h>
#include <util/memory_segment_local.h>
+#include <util/random/random_number_generator.h>
#include <dns/name.h>
#include <dns/rrclass.h>
@@ -28,6 +29,8 @@
#include <dns/tests/unittest_util.h>
+#include <boost/format.hpp>
+
using namespace std;
using namespace isc;
using namespace isc::dns;
@@ -94,6 +97,10 @@ protected:
const char* const domain_names[] = {
"c", "b", "a", "x.d.e.f", "z.d.e.f", "g.h", "i.g.h", "o.w.y.d.e.f",
"j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f", "k.g.h"};
+ const int node_distances[] = {
+ 3, 1, 2, 2, 2, 3, 1, 2, 1, 1, 2, 2
+ };
+
int name_count = sizeof(domain_names) / sizeof(domain_names[0]);
for (int i = 0; i < name_count; ++i) {
dtree.insert(mem_sgmt_, Name(domain_names[i]), &dtnode);
@@ -103,7 +110,8 @@ protected:
dtree_expose_empty_node.insert(mem_sgmt_, Name(domain_names[i]),
&dtnode);
- EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(new int(i + 1)));
+ EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(
+ new int(node_distances[i])));
}
}
@@ -126,6 +134,110 @@ TEST_F(DomainTreeTest, nodeCount) {
EXPECT_EQ(0, dtree.getNodeCount());
}
+TEST_F(DomainTreeTest, getDistance) {
+ TestDomainTreeNodeChain node_path;
+ const TestDomainTreeNode* node = NULL;
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("a"),
+ &node,
+ node_path));
+ while (node != NULL) {
+ const int* distance = node->getData();
+ if (distance != NULL) {
+ EXPECT_EQ(*distance, node->getDistance());
+ }
+ node = dtree_expose_empty_node.nextNode(node_path);
+ }
+}
+
+void
+checkDistances(const TestDomainTree& tree, int distance) {
+ TestDomainTreeNodeChain node_path;
+ const TestDomainTreeNode* node = NULL;
+
+ // Try to find a node left of the left-most node, and start from its
+ // next node (which is the left-most node in its subtree).
+ EXPECT_EQ(TestDomainTree::NOTFOUND,
+ tree.find<void*>(Name("0"), &node, node_path, NULL, NULL));
+ while ((node = tree.nextNode(node_path)) != NULL) {
+ // The distance from each node to its sub-tree root must be less
+ // than 2 * log(n).
+ EXPECT_GE(2 * distance, node->getDistance());
+ }
+}
+
+TEST_F(DomainTreeTest, checkDistanceRandom) {
+ // This test checks an important performance-related property of the
+ // DomainTree (a red-black tree), which is important for us: the
+ // longest path from a sub-tree's root to a node is no more than
+ // 2log(n). This tests that the tree is balanced.
+
+ // Names are inserted in random order.
+
+ TreeHolder mytree_holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_));
+ TestDomainTree& mytree = *mytree_holder.get();
+ isc::util::random::UniformRandomIntegerGenerator gen('a', 'z');
+ const int log_num_nodes = 20;
+
+ // Make a large million+ node top-level domain tree, i.e., the
+ // following code inserts names such as:
+ //
+ // savoucnsrkrqzpkqypbygwoiliawpbmz.
+ // wkadamcbbpjtundbxcmuayuycposvngx.
+ // wzbpznemtooxdpjecdxynsfztvnuyfao.
+ // yueojmhyffslpvfmgyfwioxegfhepnqq.
+ //
+ for (int i = 0; i < (1 << log_num_nodes); i++) {
+ string namestr;
+ while (true) {
+ for (int j = 0; j < 32; j++) {
+ namestr += gen();
+ }
+ namestr += '.';
+
+ if (mytree.insert(mem_sgmt_, Name(namestr), &dtnode) ==
+ TestDomainTree::SUCCESS) {
+ break;
+ }
+
+ namestr.clear();
+ }
+
+ EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(new int(i + 1)));
+ }
+
+ checkDistances(mytree, log_num_nodes);
+}
+
+TEST_F(DomainTreeTest, checkDistanceSorted) {
+ // This test checks an important performance-related property of the
+ // DomainTree (a red-black tree), which is important for us: the
+ // longest path from a sub-tree's root to a node is no more than
+ // 2log(n). This tests that the tree is balanced.
+
+ // Names are inserted in sorted order.
+
+ TreeHolder mytree_holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_));
+ TestDomainTree& mytree = *mytree_holder.get();
+ const int log_num_nodes = 20;
+
+ // Make a large million+ node top-level domain tree, i.e., the
+ // following code inserts names such as:
+ //
+ // name00000000.
+ // name00000001.
+ // name00000002.
+ // name00000003.
+ //
+ for (int i = 0; i < (1 << log_num_nodes); i++) {
+ const string namestr(boost::str(boost::format("name%08x.") % i));
+ mytree.insert(mem_sgmt_, Name(namestr), &dtnode);
+ EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(new int(i + 1)));
+ }
+
+ checkDistances(mytree, log_num_nodes);
+}
+
TEST_F(DomainTreeTest, setGetData) {
// set new data to an existing node. It should have some data.
int* newdata = new int(11);
More information about the bind10-changes
mailing list