BIND 10 trac2092, updated. af11f98278365797d64b4a3a607051db96c7ac51 [2092] Add support for showing pointers in Graphviz output
BIND 10 source code commits
bind10-changes at lists.isc.org
Fri Jul 20 07:28:13 UTC 2012
The branch, trac2092 has been updated
via af11f98278365797d64b4a3a607051db96c7ac51 (commit)
via bbbfbf53a1d4a949effceb0bf7c976e9ce703344 (commit)
from 5323d61fd48efe71365810a9d81bd469617df1bc (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 af11f98278365797d64b4a3a607051db96c7ac51
Author: Mukund Sivaraman <muks at isc.org>
Date: Fri Jul 20 12:57:52 2012 +0530
[2092] Add support for showing pointers in Graphviz output
commit bbbfbf53a1d4a949effceb0bf7c976e9ce703344
Author: Mukund Sivaraman <muks at isc.org>
Date: Fri Jul 20 12:56:06 2012 +0530
[2092] Add RBNode::getUpperNode()
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/rbtree.h | 49 ++++++++++++++++++++++++------
src/lib/datasrc/tests/rbtree_unittest.cc | 36 ++++++++++++++++++++++
2 files changed, 76 insertions(+), 9 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index 4943b06..7818747 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -175,6 +175,9 @@ public:
/// empty nodes anywhere.
bool isEmpty() const { return (data_.get() == NULL); }
+ /// \brief return whether the node is a null node.
+ bool isNull() const { return (this == NULL_NODE()); }
+
//@}
/// \name Setter functions.
@@ -278,6 +281,18 @@ private:
return ((flags_ & FLAG_SUBTREE_ROOT) != 0);
}
+public:
+ /// \brief returns the parent of the root of its subtree
+ ///
+ /// This method takes a node and returns the parent of the root of
+ /// its subtree (i.e, it returns the node's immediate ancestor in
+ /// the tree-of-tree hierarchy). If the node is at the top level
+ /// (which should be absolute), it will return \c NULL_NODE().
+ ///
+ /// This method never throws an exception.
+ const RBNode<T>* getUpperNode() const;
+
+private:
/// \brief return the next node which is bigger than current node
/// in the same subtree
///
@@ -393,6 +408,17 @@ RBNode<T>::~RBNode() {
template <typename T>
const RBNode<T>*
+RBNode<T>::getUpperNode() const {
+ const RBNode<T>* current = this;
+ while (!current->isSubTreeRoot()) {
+ current = current->parent_;
+ }
+
+ return (current->parent_);
+}
+
+template <typename T>
+const RBNode<T>*
RBNode<T>::abstractSuccessor(RBNode<T>* RBNode<T>::*left, RBNode<T>*
RBNode<T>::*right) const
{
@@ -978,7 +1004,8 @@ public:
/// Graphviz's dot.
///
/// \param os A \c std::ostream object to which the tree is printed.
- void dumpDot(std::ostream& os) const;
+ /// \param show_pointers Show node and parent pointers in the node
+ void dumpDot(std::ostream& os, bool show_pointers = false) const;
//@}
/// \name Modify functions
@@ -1045,7 +1072,7 @@ private:
/// \brief Print the information of given RBNode for dot.
int dumpDotHelper(std::ostream& os, const RBNode<T>* node,
- int* nodecount) const;
+ int* nodecount, bool show_pointers) const;
/// \brief Indentation helper function for dumpTree
static void indent(std::ostream& os, unsigned int depth);
@@ -1634,33 +1661,37 @@ RBTree<T>::indent(std::ostream& os, unsigned int depth) {
template <typename T>
void
-RBTree<T>::dumpDot(std::ostream& os) const {
+RBTree<T>::dumpDot(std::ostream& os, bool show_pointers) const {
int nodecount = 0;
os << "digraph g {\n";
os << "node [shape = record,height=.1];\n";
- dumpDotHelper(os, root_, &nodecount);
+ dumpDotHelper(os, root_, &nodecount, show_pointers);
os << "}\n";
}
template <typename T>
int
RBTree<T>::dumpDotHelper(std::ostream& os, const RBNode<T>* node,
- int* nodecount) const
+ int* nodecount, bool show_pointers) const
{
if (node == NULLNODE) {
return 0;
}
- int l = dumpDotHelper(os, node->left_, nodecount);
- int r = dumpDotHelper(os, node->right_, nodecount);
- int d = dumpDotHelper(os, node->down_, nodecount);
+ int l = dumpDotHelper(os, node->left_, nodecount, show_pointers);
+ int r = dumpDotHelper(os, node->right_, nodecount, show_pointers);
+ int d = dumpDotHelper(os, node->down_, nodecount, show_pointers);
*nodecount += 1;
os << "node" << *nodecount <<
"[label = \"<f0> |<f1> " << node->name_.toText() <<
- "|<f2>\"] [";
+ "|<f2>";
+ if (show_pointers) {
+ os << "|<f3> n=" << node << "|<f4> p=" << node->parent_;
+ }
+ os << "\"] [";
if (node->getColor() == RBNode<T>::RED) {
os << "color=red";
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index b6d9985..2fd696f 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -343,6 +343,42 @@ const char* const names[] = {
"g.h", "i.g.h", "k.g.h"};
const size_t name_count(sizeof(names) / sizeof(*names));
+const char* const upper_node_names[] = {
+ NULL, NULL, NULL, NULL, "d.e.f", "d.e.f", "w.y.d.e.f",
+ "w.y.d.e.f", "w.y.d.e.f", "d.e.f", "z.d.e.f",
+ NULL, "g.h", "g.h"};
+
+TEST_F(RBTreeTest, getUpperNode) {
+ RBTreeNodeChain<int> node_path;
+ const RBNode<int>* node = NULL;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree_expose_empty_node.find(Name(names[0]),
+ &node,
+ node_path));
+ for (int i = 0; i < name_count; ++i) {
+ EXPECT_NE(static_cast<void*>(NULL), node);
+
+ const RBNode<int>* upper_node = node->getUpperNode();
+ EXPECT_NE(static_cast<void*>(NULL), upper_node);
+
+ if (upper_node_names[i] != NULL) {
+ const RBNode<int>* upper_node2 = NULL;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree_expose_empty_node.find(Name(upper_node_names[i]),
+ &upper_node2));
+ EXPECT_NE(static_cast<void*>(NULL), upper_node2);
+ EXPECT_FALSE(upper_node2->isNull());
+
+ EXPECT_EQ(upper_node, upper_node2);
+ }
+
+ node = rbtree_expose_empty_node.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+}
+
TEST_F(RBTreeTest, nextNode) {
RBTreeNodeChain<int> node_path;
const RBNode<int>* node = NULL;
More information about the bind10-changes
mailing list