BIND 10 trac517, updated. 1a52db4373a1c4169b0bbd9bc6a550e5a3e68b39 [trac517] additioanl RBTreeNodeChain cleanups
BIND 10 source code commits
bind10-changes at lists.isc.org
Wed Feb 2 03:20:06 UTC 2011
The branch, trac517 has been updated
via 1a52db4373a1c4169b0bbd9bc6a550e5a3e68b39 (commit)
via bbd103fff6a6a6e775a075c5132bc1cdd38a5acf (commit)
via ad83fe6b6c31a54e39116f12eb5c70d9fce8d9ea (commit)
via 12aa5f7fd9f8ce0aa10b66cbd3608c363eb3390f (commit)
via 873ab3f9db15055ec293533202bc73d908ab73c1 (commit)
via a929e898df74d43fc590e8df793edeb5f355e29d (commit)
via c11ea16f0ce2d7eac933dfc9e7b57e0e82972205 (commit)
from 2565b9fe9daf6ba63234b06b9f0eb5b8168257b4 (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 1a52db4373a1c4169b0bbd9bc6a550e5a3e68b39
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Tue Feb 1 19:09:38 2011 -0800
[trac517] additioanl RBTreeNodeChain cleanups
- added more documentation while removing obsolete ones
- use assert() for private functions because the invariants should now be
guaranteed
- remove the dedicated exceptions as a result and use generic ones
- added more tests for invalid cases
commit bbd103fff6a6a6e775a075c5132bc1cdd38a5acf
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Tue Feb 1 15:46:25 2011 -0800
[trac517] updated RBTree<T>::nextNode.
- check invalid chain explicitly in the method. use a generic exception
on violation.
- updated doc
commit ad83fe6b6c31a54e39116f12eb5c70d9fce8d9ea
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Tue Feb 1 15:26:45 2011 -0800
[trac517] updated nextNode() test cases
- not all nodes were tested. fixed it.
- confirmed nextNode() returns NULL at the end of the tree.
commit 12aa5f7fd9f8ce0aa10b66cbd3608c363eb3390f
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Tue Feb 1 15:16:43 2011 -0800
[trac517] more documentation
commit 873ab3f9db15055ec293533202bc73d908ab73c1
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Tue Feb 1 15:13:13 2011 -0800
[trac517] added more tests and a new method for RBTreeNodeChain.
- the new tests confirm the maximum possible levels of RBTree/node chain.
- the new method: getLevelCount() helps the tests.
Also added some more documentation.
commit a929e898df74d43fc590e8df793edeb5f355e29d
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Tue Feb 1 13:58:03 2011 -0800
[trac517] more style fixes: brace position
commit c11ea16f0ce2d7eac933dfc9e7b57e0e82972205
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Tue Feb 1 13:56:09 2011 -0800
[trac517] proposed editorial fixes
- removed redundant space at EOL
- fixed usual breakage: s/foo &/foo& /
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/rbtree.h | 200 +++++++++++++++--------------
src/lib/datasrc/tests/rbtree_unittest.cc | 95 +++++++++++++-
2 files changed, 191 insertions(+), 104 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index 3e6cab9..518d244 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -55,27 +55,7 @@ operator-(const isc::dns::Name& super_name, const isc::dns::Name& sub_name) {
}
}
-/// \brief Invalid RBTreeNodeChain exception
-///
-/// Normally, RBTreeNodeChain is initialized and manipuate by RBTRee,
-/// this is thrown when using one RBTreeNodeChain which is created by default
-/// constructor but not initialized by RBTree through find function
-struct InvalidNodeChain : public isc::Exception {
- InvalidNodeChain(const char* file, size_t line, const char* what) :
- Exception(file, line, what){}
-};
-
-/// \brief Too long RBTreeNodeChain exception
-///
-/// RBTreeNodeChain has length limitation as 128, this exception is thrown
-/// when RBTreeNodeChain is longer than that limitation which is caused by
-/// too deep RBTree.
-struct TooLongNodeChain : public isc::Exception {
- TooLongNodeChain(const char *file, size_t line, const char *what) :
- Exception(file, line, what){}
-};
-
-/// Forward declare RBTree class here is convinent for following friend
+/// Forward declare RBTree class here is convinent for following friend
/// class declare inside RBNode and RBTreeNodeChain
template <typename T>
class RBTree;
@@ -306,58 +286,86 @@ RBNode<T>::successor() const {
}
-/// \brief RBTreeNodeChain is used to keep track of the sequence of
-/// nodes to reach any given node from the root of RBTree.
+/// \brief RBTreeNodeChain is used to keep track of the sequence of
+/// nodes to reach any given node from the root of RBTree.
+///
+/// Currently, RBNode does not have "up" pointers in them (i.e., back pointers
+/// from the root of one level of tree of trees to the node in the parent
+/// tree whose down pointer points to that root node) for memory usage
+/// reasons, so there is no other way to find the path back to the root from
+/// any given RBNode.
///
-/// RBNode did not have "up" pointers in them (for memory usage reasons)
-/// so there was no way to find the path back to the root from any given
-/// RBNode.
+/// \note This design may change in future versions. In particular, it's
+/// quite likely we want to have that pointer if we want to optimize name
+/// compression by exploiting the structure of the zone. If and when that
+/// happens we should also revisit the need for the chaining.
///
-/// RBTreeNodeChain is constructed and manipulate only by \c RBTree.
-/// RBTree use it as a inner data struct to iterator the whole RBTree.
-/// This is the reason why only construct function and getAbsoluteName
-/// function is public and others are private
+/// RBTreeNodeChain is constructed and manipulated only inside the \c RBTree
+/// class.
+/// \c RBTree uses it as an inner data structure to iterate over the whole
+/// RBTree.
+/// This is the reason why manipulation methods such as \c push() and \c pop()
+/// are private (and not shown in the doxygen document).
template <typename T>
class RBTreeNodeChain {
- /// RBTreeNodeChain is initialized by RBTree, only RBTree has
+ /// RBTreeNodeChain is initialized by RBTree, only RBTree has
/// knowledge to manipuate it.
friend class RBTree<T>;
public:
- /// \name Constructors
- ///
- /// \note empty RBTreeNodeChain isn't meaningful, use it
- /// as parameter for functions like getAbsoluteName or
- /// nextNode in \c RBTree will throw InvalidNodeChain exception
- /// empty RBTreeNodeChain has to be initialized by RBTree, through
- /// \c find function call.
+ /// \name Constructors and Assignment Operator.
+ ///
//{@
+ /// The default constructor.
+ ///
+ /// \exception None
RBTreeNodeChain() : node_count_(0) {}
+
+ /// Copy constructor.
+ ///
+ /// \exception None
RBTreeNodeChain(const RBTreeNodeChain<T>& node_path) {
node_count_ = node_path.node_count_;
if (node_count_ > 0) {
- memcpy(nodes_, node_path.nodes_,
- node_count_ * sizeof(RBNode<T>*));
+ memcpy(nodes_, node_path.nodes_, node_count_ * sizeof(RBNode<T>*));
}
}
- RBTreeNodeChain<T>&
+ /// Assignment operator.
+ ///
+ /// \exception None
+ RBTreeNodeChain<T>&
operator=(const RBTreeNodeChain<T>& node_path) {
node_count_ = node_path.node_count_;
if (node_count_ > 0) {
- memcpy(nodes_, node_path.nodes_,
- node_count_ * sizeof(RBNode<T>*));
+ memcpy(nodes_, node_path.nodes_, node_count_ * sizeof(RBNode<T>*));
}
return (*this);
}
//@}
-
- /// \brief return the absolute name for the node which current
- /// RBTreeNodeChain traces.
+
+ /// \brief Return the number of levels stored in the chain.
+ ///
+ /// It's equal to the number of nodes in the chain; for an empty
+ /// chain, 0 will be returned.
+ ///
+ /// \exception None
+ unsigned int getLevelCount() const { return (node_count_); }
+
+ /// \brief return the absolute name for the node which this
+ /// \c RBTreeNodeChain currently refers to.
+ ///
+ /// The chain must not be empty.
///
- /// \exception RBTreeNodeChain has to be initialized by RBtree,
- /// otherwise InvalidNodeChain exception will be thrown
+ /// \exception isc::BadValue the chain is empty.
+ /// \exception std::bad_alloc memory allocation for the new name fails.
isc::dns::Name getAbsoluteName() const {
- const RBNode<T> *top_node = top();
+ if (isEmpty()) {
+ isc_throw(isc::BadValue,
+ "RBTreeNodeChain::getAbsoluteName is called on an empty "
+ "chain");
+ }
+
+ const RBNode<T>* top_node = top();
isc::dns::Name absolute_name = top_node->getName();
int node_count = node_count_ - 1;
while (node_count > 0) {
@@ -369,6 +377,10 @@ public:
}
private:
+ // the following private functions check invariants about the internal
+ // state using assert() instead of exception. The state of a chain
+ // can only be modified operations within this file, so if any of the
+ // assumptions fails it means an internal bug.
/// \brief return whther node chain has node in it.
///
@@ -376,16 +388,13 @@ private:
bool isEmpty() const { return (node_count_ == 0); }
/// \brief return the top node for the node chain
- ///
+ ///
/// RBTreeNodeChain store all the nodes along top node to
/// root node of RBTree
///
- /// \exception If RBTreeNodeChain isn't initialized by RBTree
- /// InvalidNodeChain exception will be thrown
+ /// \exception None
const RBNode<T>* top() const {
- if (isEmpty()) {
- isc_throw(InvalidNodeChain, "empty node chain");
- }
+ assert(!isEmpty());
return (nodes_[node_count_ - 1]);
}
@@ -394,43 +403,33 @@ private:
/// After pop, up/super node of original top node will be
/// the top node
///
- /// \exception If RBTreeNodeChain isn't initialized by RBTree
- /// InvalidNodeChain exception will be thrown
+ /// \exception None
void pop() {
- if (isEmpty()) {
- isc_throw(InvalidNodeChain, "empty node chain");
- }
+ assert(!isEmpty());
--node_count_;
}
-
+
/// \brief add the node into the node chain
///
/// If the node chain isn't empty, the node should be
/// the sub domain of the original top node in node chain
/// otherwise the node should be the root node of RBTree.
///
- /// \exception If RBTreeNodeChain is initialized by RBTree who
- /// is too deep with level bigger than RBT_MAX_LEVEL, the node
- /// chain for leaf node will longer than RBT_MAX_LEVEL then
- /// exception TooLongNodeChain will be thrown
- ///
- /// \note Since RBTree grows through inserting new node
- /// and Name class has the check whether the name is too long
- /// or has too many labels, so TooLongNodeChain exception is
- /// hidden by TooLongName exception since it's impossible to create
- /// the RBTree which is deeper than MAX_LABELS of Name class.
+ /// \exception None
void push(const RBNode<T>* node) {
- if (node_count_ >= RBT_MAX_LEVEL) {
- isc_throw(TooLongNodeChain, "node chain is too long");
- }
+ assert(node_count_ < RBT_MAX_LEVEL);
nodes_[node_count_++] = node;
}
private:
- /// the max lable count for one domain name is 128
- /// since each node in rbtree stores at least one label
- /// so the max node count for one node chain is 128
- const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS;
+ // The max label count for one domain name is Name::MAX_LABELS (128).
+ // Since each node in rbtree stores at least one label, and the root
+ // name always shares the same level with some others (which means
+ // all top level nodes except the one for the root name contain at least
+ // two labels), the possible maximum level is MAX_LABELS - 1.
+ // It's also the possible maximum nodes stored in a chain.
+ const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS - 1;
+
const RBNode<T>* nodes_[RBT_MAX_LEVEL];
int node_count_;
};
@@ -635,6 +634,8 @@ public:
/// node of a given node in the entire RBTree; the \c nextNode() method
/// takes a node chain as a parameter.
///
+ /// \exception isc::BadValue node_path is not empty.
+ ///
/// \param name Target to be found
/// \param node On success (either \c EXACTMATCH or \c PARTIALMATCH)
/// it will store a pointer to the matching node
@@ -675,22 +676,23 @@ public:
}
//@}
- /// \brief return the next bigger node in DNSSEC order of the given node.
+ /// \brief return the next bigger node in DNSSEC order from a given node
+ /// chain.
///
- /// \note nextNode will iterator all the nodes in RBTree including empty
- /// nodes. If empty node isn't desired, it's easy to add logic to check
- /// return node and keep invoking nextNode until the non-empty node is
- /// retrived
- ///
- /// This method also updates the given \c node_path so that it will store
+ /// This method identifies the next bigger node of the node currently
+ /// referenced in \c node_path and returns it.
+ /// This method also updates the passed \c node_path so that it will store
/// the path for the returned next node.
/// It will be convenient when we want to iterate over the all nodes
/// of \c RBTree; we can do this by calling this method repeatedly
/// starting from the root node.
///
- /// \exception If the node_path isn't initalized by find function and not
- /// get from previous nextNode function call, InvalidNodeChain exception
- /// will be thrown
+ /// \note \c nextNode() will iterate over all the nodes in RBTree including
+ /// empty nodes. If empty node isn't desired, it's easy to add logic to
+ /// check return node and keep invoking \c nextNode() until the non-empty
+ /// node is retrieved.
+ ///
+ /// \exception isc::BadValue node_path is empty.
///
/// \param node_path A node chain that stores all the nodes along the path
/// from root to node.
@@ -774,12 +776,11 @@ private:
//@{
/// \brief delete tree whose root is equal to node
void deleteHelper(RBNode<T> *node);
- /// \brief find the node with name
- ///
- /// Internal searching function.
- ///
+
+ /// \brief Print the information of given RBNode.
void dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
unsigned int depth) const;
+
/// \brief Indentation helper function for dumpTree
static void indent(std::ostream& os, unsigned int depth);
@@ -855,6 +856,10 @@ RBTree<T>::find(const isc::dns::Name& target_name,
{
using namespace helper;
+ if (!node_path.isEmpty()) {
+ isc_throw(isc::BadValue, "RBTree::find is given a non empty chain");
+ }
+
RBNode<T>* node = root_;
Result ret = NOTFOUND;
isc::dns::Name name = target_name;
@@ -902,8 +907,11 @@ RBTree<T>::find(const isc::dns::Name& target_name,
template <typename T>
const RBNode<T>*
-RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const
-{
+RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const {
+ if (node_path.isEmpty()) {
+ isc_throw(isc::BadValue, "RBTree::nextNode is given an empty chain");
+ }
+
const RBNode<T>* node = node_path.top();
// if node has sub domain, the next domain is the smallest
// domain in sub domain tree
@@ -944,9 +952,7 @@ RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const
template <typename T>
typename RBTree<T>::Result
-RBTree<T>::insert(const isc::dns::Name& target_name,
- RBNode<T>** new_node)
-{
+RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
using namespace helper;
RBNode<T>* parent = NULLNODE;
RBNode<T>* current = root_;
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 74536de..7758536 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -15,6 +15,8 @@
#include <gtest/gtest.h>
+#include <exceptions/exceptions.h>
+
#include <dns/name.h>
#include <dns/rrclass.h>
#include <dns/rrset.h>
@@ -26,10 +28,15 @@
#include <dns/tests/unittest_util.h>
using namespace std;
+using namespace isc;
using namespace isc::dns;
using isc::UnitTestUtil;
using namespace isc::datasrc;
+// XXX: some compilers cannot find class static constants used in
+// EXPECT_xxx macros, for which we need an explicit empty definition.
+const size_t Name::MAX_LABELS;
+
/* The initial structure of rbtree
*
* b
@@ -151,7 +158,6 @@ TEST_F(RBTreeTest, insertNames) {
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("n"), &rbtnode));
}
-
TEST_F(RBTreeTest, findName) {
// find const rbtnode
// exact match
@@ -181,6 +187,16 @@ TEST_F(RBTreeTest, findName) {
EXPECT_EQ(Name("q"), rbtnode->getName());
}
+TEST_F(RBTreeTest, findError) {
+ // For the version that takes a node chain, the chain must be empty.
+ RBTreeNodeChain<int> chain;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH, rbtree.find<void*>(Name("a"), &crbtnode,
+ chain, NULL, NULL));
+ // trying to reuse the same chain. it should result in an exception.
+ EXPECT_THROW(rbtree.find<void*>(Name("a"), &crbtnode, chain, NULL, NULL),
+ BadValue);
+}
+
bool
testCallback(const RBNode<int>&, bool* callack_checker) {
*callack_checker = true;
@@ -188,7 +204,6 @@ testCallback(const RBNode<int>&, bool* callack_checker) {
}
TEST_F(RBTreeTest, callback) {
- RBTreeNodeChain<int> node_path;
// by default callback isn't enabled
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("callback.example"),
&rbtnode));
@@ -221,22 +236,77 @@ TEST_F(RBTreeTest, callback) {
EXPECT_FALSE(parentrbtnode->isCallbackEnabled());
// check if the callback is called from find()
+ RBTreeNodeChain<int> node_path1;
bool callback_called = false;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- rbtree.find(Name("sub.callback.example"), &crbtnode, node_path,
+ rbtree.find(Name("sub.callback.example"), &crbtnode, node_path1,
testCallback, &callback_called));
EXPECT_TRUE(callback_called);
// enable callback at the parent node, but it doesn't have data so
// the callback shouldn't be called.
+ RBTreeNodeChain<int> node_path2;
parentrbtnode->enableCallback();
callback_called = false;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- rbtree.find(Name("callback.example"), &crbtnode, node_path,
+ rbtree.find(Name("callback.example"), &crbtnode, node_path2,
testCallback, &callback_called));
EXPECT_FALSE(callback_called);
}
+TEST_F(RBTreeTest, chainLevel) {
+ RBTreeNodeChain<int> chain;
+
+ // by default there should be no level in the chain.
+ EXPECT_EQ(0, chain.getLevelCount());
+
+ // insert one node to the tree and find it. there should be exactly
+ // one level in the chain.
+ RBTree<int> tree(true);
+ Name node_name(Name::ROOT_NAME());
+ EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find<void*>(node_name, &crbtnode, chain, NULL, NULL));
+ EXPECT_EQ(1, chain.getLevelCount());
+
+ /*
+ * Now creating a possibly deepest tree with MAX_LABELS - 1 levels.
+ * it should look like:
+ * a
+ * /|
+ * (.)a
+ * |
+ * a
+ * : (MAX_LABELS - 1) "a"'s
+ *
+ * then confirm that find() for the deepest name succeeds without any
+ * disruption, and the resulting chain has the expected level.
+ * Note that "a." and the root name (".") belong to the same level.
+ * So the possible maximum level is MAX_LABELS - 1, not MAX_LABELS.
+ */
+ for (unsigned int i = 1; i < Name::MAX_LABELS; ++i) {
+ node_name = Name("a.").concatenate(node_name);
+ EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
+ RBTreeNodeChain<int> found_chain;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find<void*>(node_name, &crbtnode, found_chain,
+ NULL, NULL));
+ EXPECT_EQ(i, found_chain.getLevelCount());
+ }
+
+ // Confirm the last inserted name has the possible maximum length with
+ // maximum label count. This confirms the rbtree and chain level cannot
+ // be larger.
+ EXPECT_EQ(Name::MAX_LABELS, node_name.getLabelCount());
+ EXPECT_THROW(node_name.concatenate(Name("a.")), TooLongName);
+}
+
+TEST_F(RBTreeTest, getAbsoluteNameError) {
+ // an empty chain isn't allowed.
+ RBTreeNodeChain<int> chain;
+ EXPECT_THROW(chain.getAbsoluteName(), BadValue);
+}
+
/*
*the domain order should be:
* a, b, c, d.e.f, x.d.e.f, w.y.d.e.f, o.w.y.d.e.f, p.w.y.d.e.f, q.w.y.d.e.f,
@@ -263,11 +333,22 @@ TEST_F(RBTreeTest, nextNode) {
RBTreeNodeChain<int> node_path;
const RBNode<int>* node = NULL;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- rbtree.find<void*>(Name(names[0]), &node, node_path, NULL, NULL));
- for (int i = 0; i < name_count - 1; ++i) {
+ rbtree.find<void*>(Name(names[0]), &node, node_path, NULL,
+ NULL));
+ for (int i = 0; i < name_count; ++i) {
+ EXPECT_NE(static_cast<void*>(NULL), node);
EXPECT_EQ(Name(names[i]), node_path.getAbsoluteName());
- rbtree.nextNode(node_path);
+ node = rbtree.nextNode(node_path);
}
+
+ // We should have reached the end of the tree.
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+}
+
+TEST_F(RBTreeTest, nextNodeError) {
+ // Empty chain for nextNode() is invalid.
+ RBTreeNodeChain<int> chain;
+ EXPECT_THROW(rbtree.nextNode(chain), BadValue);
}
TEST_F(RBTreeTest, dumpTree) {
More information about the bind10-changes
mailing list