BIND 10 trac2750, updated. 63e54b17e5b43ee480cb83a4fa0fa6ba08e2ccfa [2750] Add methods to check RB tree properties (and use them in tests)
BIND 10 source code commits
bind10-changes at lists.isc.org
Tue Sep 3 03:08:00 UTC 2013
The branch, trac2750 has been updated
via 63e54b17e5b43ee480cb83a4fa0fa6ba08e2ccfa (commit)
via da0e9a81e8a4e4fac77caf257607bf4fe1bb0f0d (commit)
from b403553a567421006bccbf4b4f598b7aca738d54 (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 63e54b17e5b43ee480cb83a4fa0fa6ba08e2ccfa
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Sep 3 08:37:46 2013 +0530
[2750] Add methods to check RB tree properties (and use them in tests)
commit da0e9a81e8a4e4fac77caf257607bf4fe1bb0f0d
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Sep 3 07:59:02 2013 +0530
[2750] Replace height check with getHeight() method
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 134 +++++++++++++++++++-
.../datasrc/tests/memory/domaintree_unittest.cc | 33 +++--
2 files changed, 147 insertions(+), 20 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 9e41de7..776603a 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -362,7 +362,7 @@ private:
}
/// \brief Static variant of isBlack() that also allows NULL nodes.
- static bool isBlack(DomainTreeNode<T>* node) {
+ static bool isBlack(const DomainTreeNode<T>* node) {
if (!node) {
// NULL nodes are black.
return (true);
@@ -377,7 +377,7 @@ private:
}
/// \brief Static variant of isRed() that also allows NULL nodes.
- static bool isRed(DomainTreeNode<T>* node) {
+ static bool isRed(const DomainTreeNode<T>* node) {
return (!isBlack(node));
}
@@ -1593,6 +1593,39 @@ public:
/// This function is mainly intended to be used for debugging.
uint32_t getNodeCount() const { return (node_count_); }
+private:
+ /// \brief Helper method for getHeight()
+ size_t getHeightHelper(const DomainTreeNode<T>* node) const;
+
+public:
+ /// \brief Return the maximum height of sub-root nodes found in the
+ /// DomainTree forest.
+ ///
+ /// The height of a node is defined as the number of nodes in the
+ /// longest path from the node to a leaf. For each subtree in the
+ /// DomainTree forest, this method determines the height of its root
+ /// node. Then it returns the maximum such height in the forest.
+ ///
+ /// Note: This method exists for testing purposes. Non-test code
+ /// must not use it.
+ size_t getHeight() const;
+
+private:
+ /// \brief Helper method for checkProperties()
+ bool checkPropertiesHelper(const DomainTreeNode<T>* node) const;
+
+ /// \brief Helper for checkProperties()
+ bool checkBlackDistanceHelper(const DomainTreeNode<T>* node,
+ size_t* distance)
+ const;
+
+public:
+ /// \brief Check red-black properties of the DomainTree.
+ ///
+ /// Note: This method exists for testing purposes. Non-test code
+ /// must not use it.
+ bool checkProperties() const;
+
/// \name Debug function
//@{
/// \brief Print the nodes in the trees.
@@ -3003,6 +3036,103 @@ DomainTree<T>::rightRotate
return (node);
}
+template <typename T>
+size_t
+DomainTree<T>::getHeightHelper(const DomainTreeNode<T>* node) const {
+ if (node == NULL) {
+ return (0);
+ }
+
+ const size_t dl = getHeightHelper(node->getLeft());
+ const size_t dr = getHeightHelper(node->getRight());
+
+ const size_t this_height = (dl > dr) ? (dl + 1) : (dr + 1);
+ const size_t down_height = getHeightHelper(node->getDown());
+
+ return ((this_height > down_height) ? this_height : down_height);
+}
+
+template <typename T>
+size_t
+DomainTree<T>::getHeight() const {
+ return (getHeightHelper(root_.get()));
+}
+
+template <typename T>
+bool
+DomainTree<T>::checkPropertiesHelper(const DomainTreeNode<T>* node) const {
+ if (node == NULL) {
+ return (true);
+ }
+
+ // Root nodes should be BLACK.
+ if (node->isSubTreeRoot() && node->isRed()) {
+ return (false);
+ }
+
+ // Both children of RED nodes must be BLACK.
+ if (node->isRed()) {
+ if (DomainTreeNode<T>::isRed(node->getLeft()) ||
+ DomainTreeNode<T>::isRed(node->getRight()))
+ {
+ return (false);
+ }
+ }
+
+ // Repeat tests with this node's children.
+ return (checkPropertiesHelper(node->getLeft()) &&
+ checkPropertiesHelper(node->getRight()) &&
+ checkPropertiesHelper(node->getDown()));
+}
+
+template <typename T>
+bool
+DomainTree<T>::checkBlackDistanceHelper(const DomainTreeNode<T>* node,
+ size_t* distance) const
+{
+ if (node == NULL) {
+ *distance = 1;
+ return (true);
+ }
+
+ size_t dl, dr, dd;
+ if (!checkBlackDistanceHelper(node->getLeft(), &dl)) {
+ return (false);
+ }
+ if (!checkBlackDistanceHelper(node->getRight(), &dr)) {
+ return (false);
+ }
+ if (!checkBlackDistanceHelper(node->getDown(), &dd)) {
+ return (false);
+ }
+
+ if (dl != dr) {
+ return (false);
+ }
+
+ if (node->isBlack()) {
+ ++dl;
+ }
+
+ *distance = dl;
+
+ return (true);
+}
+
+template <typename T>
+bool
+DomainTree<T>::checkProperties() const {
+ if (!checkPropertiesHelper(root_.get())) {
+ return (false);
+ }
+
+ // Path from a given node to all its leaves must contain the same
+ // number of BLACK child nodes. This is done separately here instead
+ // of inside checkPropertiesHelper() as it would take (n log n)
+ // complexity otherwise.
+ size_t dd;
+ return (checkBlackDistanceHelper(root_.get(), &dd));
+}
template <typename T>
void
diff --git a/src/lib/datasrc/tests/memory/domaintree_unittest.cc b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
index ae0073b..6058e44 100644
--- a/src/lib/datasrc/tests/memory/domaintree_unittest.cc
+++ b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
@@ -191,22 +191,6 @@ TEST_F(DomainTreeTest, getDistance) {
}
}
-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
@@ -247,7 +231,12 @@ TEST_F(DomainTreeTest, checkDistanceRandom) {
EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(new int(i + 1)));
}
- checkDistances(mytree, log_num_nodes);
+ // The distance from each node to its sub-tree root must be less
+ // than 2 * log(n).
+ EXPECT_GE(2 * log_num_nodes, mytree.getHeight());
+
+ // Also check RB tree properties
+ EXPECT_TRUE(mytree.checkProperties());
}
TEST_F(DomainTreeTest, checkDistanceSorted) {
@@ -276,7 +265,12 @@ TEST_F(DomainTreeTest, checkDistanceSorted) {
EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(new int(i + 1)));
}
- checkDistances(mytree, log_num_nodes);
+ // The distance from each node to its sub-tree root must be less
+ // than 2 * log(n).
+ EXPECT_GE(2 * log_num_nodes, mytree.getHeight());
+
+ // Also check RB tree properties
+ EXPECT_TRUE(mytree.checkProperties());
}
TEST_F(DomainTreeTest, setGetData) {
@@ -408,6 +402,9 @@ TEST_F(DomainTreeTest, remove) {
tree.find(Name(ordered_names[j]), &node));
tree.remove(mem_sgmt_, node, deleteData);
+ // Check RB tree properties
+ EXPECT_TRUE(tree.checkProperties());
+
// Now, walk through nodes in order.
TestDomainTreeNodeChain node_path;
const TestDomainTreeNode* cnode;
More information about the bind10-changes
mailing list