BIND 10 trac507, updated. 3032690d227ee2fe8f660bdcd6c0782c6a635ef0 [trac507] Revert "[trac507] prepare work for #507 based on a snapshot of #517"
BIND 10 source code commits
bind10-changes at lists.isc.org
Tue Feb 8 18:13:14 UTC 2011
The branch, trac507 has been updated
via 3032690d227ee2fe8f660bdcd6c0782c6a635ef0 (commit)
from 92d766ce1407da1d1bed05e64c2b62b25af63303 (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 3032690d227ee2fe8f660bdcd6c0782c6a635ef0
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Tue Feb 8 10:11:28 2011 -0800
[trac507] Revert "[trac507] prepare work for #507 based on a snapshot of #517"
it effectively makes this branch with trac517 (which has been merged to
master since then). it will help merge this branch to master.
also resolved trivial conflicts in src/lib/datasrc/tests/rbtree_unittest.cc.
This reverts commit 1ab958cdc6f1ebdbf88f863a4a15d6a5783035bc.
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/rbtree.h | 154 ++++++++++++++++++++++++++++++
src/lib/datasrc/tests/rbtree_unittest.cc | 107 +++++++++++++++++++++
2 files changed, 261 insertions(+), 0 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index 39fd1d5..8ceb7e0 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -390,6 +390,84 @@ public:
return (last_comparison_);
}
+ /// \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 isc::BadValue the chain is empty.
+ /// \exception std::bad_alloc memory allocation for the new name fails.
+ isc::dns::Name getAbsoluteName() const {
+ 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) {
+ top_node = nodes_[node_count - 1];
+ absolute_name = absolute_name.concatenate(top_node->getName());
+ --node_count;
+ }
+ return (absolute_name);
+ }
+
+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.
+ ///
+ /// \exception None
+ 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 None
+ const RBNode<T>* top() const {
+ assert(!isEmpty());
+ return (nodes_[node_count_ - 1]);
+ }
+
+ /// \brief pop the top node from the node chain
+ ///
+ /// After pop, up/super node of original top node will be
+ /// the top node
+ ///
+ /// \exception None
+ void pop() {
+ 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 None
+ void push(const RBNode<T>* node) {
+ assert(node_count_ < RBT_MAX_LEVEL);
+ nodes_[node_count_++] = node;
+ }
+
private:
// 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
@@ -653,6 +731,31 @@ public:
}
//@}
+ /// \brief return the next bigger node in DNSSEC order from a given node
+ /// chain.
+ ///
+ /// 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.
+ ///
+ /// \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.
+ ///
+ /// \return An \c RBNode that is next bigger than \c node; if \c node is
+ /// the largest, \c NULL will be returned.
+ const RBNode<T>* nextNode(RBTreeNodeChain<T>& node_path) const;
+
/// \brief Get the total number of nodes in the tree
///
/// It includes nodes internally created as a result of adding a domain
@@ -808,6 +911,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;
@@ -820,6 +927,7 @@ RBTree<T>::find(const isc::dns::Name& target_name,
if (relation == isc::dns::NameComparisonResult::EQUAL) {
if (needsReturnEmptyNode_ || !node->isEmpty()) {
+ node_path.push(node);
*target = node;
ret = EXACTMATCH;
}
@@ -842,6 +950,7 @@ RBTree<T>::find(const isc::dns::Name& target_name,
}
}
}
+ node_path.push(node);
name = name - node->name_;
node = node->down_;
} else {
@@ -854,6 +963,51 @@ RBTree<T>::find(const isc::dns::Name& target_name,
}
template <typename T>
+const RBNode<T>*
+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
+ if (node->down_ != NULLNODE) {
+ const RBNode<T>* left_most = node->down_;
+ while (left_most->left_ != NULLNODE) {
+ left_most = left_most->left_;
+ }
+ node_path.push(left_most);
+ return (left_most);
+ }
+
+ // node_path go to up level
+ node_path.pop();
+ // otherwise found the successor node in current level
+ const RBNode<T>* successor = node->successor();
+ if (successor != NULLNODE) {
+ node_path.push(successor);
+ return (successor);
+ }
+
+ // if no successor found move to up level, the next successor
+ // is the successor of up node in the up level tree, if
+ // up node doesn't have successor we gonna keep moving to up
+ // level
+ while (!node_path.isEmpty()) {
+ const RBNode<T>* up_node_successor = node_path.top()->successor();
+ node_path.pop();
+ if (up_node_successor != NULLNODE) {
+ node_path.push(up_node_successor);
+ return (up_node_successor);
+ }
+ }
+
+ return (NULL);
+}
+
+
+template <typename T>
typename RBTree<T>::Result
RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
using namespace helper;
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 3fbe256..94c755c 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -186,6 +186,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;
@@ -243,6 +253,103 @@ TEST_F(RBTreeTest, callback) {
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,
+ * z.d.e.f, j.z.d.e.f, g.h, i.g.h
+ * b
+ * / \
+ * a d.e.f
+ * / | \
+ * c | g.h
+ * | |
+ * w.y i
+ * / | \
+ * x | z
+ * | |
+ * p j
+ * / \
+ * o q
+ */
+TEST_F(RBTreeTest, nextNode) {
+ const char* const names[] = {
+ "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", "z.d.e.f", "j.z.d.e.f", "g.h", "i.g.h"};
+ const int name_count = sizeof(names) / sizeof(names[0]);
+ 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; ++i) {
+ EXPECT_NE(static_cast<void*>(NULL), node);
+ EXPECT_EQ(Name(names[i]), node_path.getAbsoluteName());
+ 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);
+}
+
// A helper function for getLastComparedNode() below.
void
comparisonChecks(const RBTreeNodeChain<int>& chain,
More information about the bind10-changes
mailing list