BIND 10 trac1803, updated. 3706d7583e672d807273ed9fe4dcad66d7f5774a [1803] Document the tests little bit more
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon May 7 13:40:16 UTC 2012
The branch, trac1803 has been updated
via 3706d7583e672d807273ed9fe4dcad66d7f5774a (commit)
via 6b7e514528109978fe9b731e3690331bc5ebf10b (commit)
via 02d9aacf0a7c244a60e436237fdac09062389f48 (commit)
from 6abb27b31deb6c5bbbe18a97bb7e0a719ee9a9ce (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 3706d7583e672d807273ed9fe4dcad66d7f5774a
Author: Michal 'vorner' Vaner <michal.vaner at nic.cz>
Date: Mon May 7 15:03:38 2012 +0200
[1803] Document the tests little bit more
commit 6b7e514528109978fe9b731e3690331bc5ebf10b
Author: Michal 'vorner' Vaner <michal.vaner at nic.cz>
Date: Mon May 7 14:54:39 2012 +0200
[1803] Implement the previousNode start match
In case the find didn't give us an exact node, we need to correct the
search at the beginning. The code is slightly dense, but should be well
commented. Also, the tests are fixed slightly and one more added.
commit 02d9aacf0a7c244a60e436237fdac09062389f48
Author: Michal 'vorner' Vaner <michal.vaner at nic.cz>
Date: Mon May 7 13:24:22 2012 +0200
[1803] Special-case handling in previousNode
The empty chain may mean we did not call find previously. But it also
can mean we just run out of nodes or that we did not find the correct
node. We also handle empty tree specially.
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/rbtree.h | 106 ++++++++++++++++++++++++++++--
src/lib/datasrc/tests/rbtree_unittest.cc | 46 +++++++++++--
2 files changed, 138 insertions(+), 14 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index 5e17ee6..0a229fb 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -892,6 +892,8 @@ public:
///
/// \param node_path A node chain that stores all the nodes along the path
/// from root to node and the result of \c find(). This will get modified.
+ /// You should not use the node_path again except for repetetive calls
+ /// of this method.
///
/// \return An \c RBNode that is next smaller than \c node; if \c node is
/// the smallest, \c NULL will be returned.
@@ -1158,9 +1160,99 @@ RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const {
template <typename T>
const RBNode<T>*
RBTree<T>::previousNode(RBTreeNodeChain<T>& node_path) const {
- if (node_path.isEmpty()) {
+ if (getNodeCount() == 0) {
+ // Special case for empty trees. It would look every time like
+ // we didn't search, because the last compared is empty. This is
+ // a slight hack and not perfect, but this is better than throwing
+ // on empty tree. And we probably won't meet an empty tree in practice
+ // anyway.
+ return (NULL);
+ }
+ if (node_path.getLastComparedNode() == NULL) {
isc_throw(isc::BadValue,
- "RBTree::previousNode is given an empty chain");
+ "RBTree::previousNode called before find");
+ }
+
+ // If the relation isn't EQUAL, it means the find was called previously
+ // and didn't find the exact node. Therefore we need to locate the place
+ // to start iterating the chain of domains.
+ //
+ // The logic here is not too complex, we just need to take care to handle
+ // all the cases and decide where to go from there.
+ switch (node_path.getLastComparisonResult().getRelation()) {
+ case dns::NameComparisonResult::COMMONANCESTOR:
+ // We compared with a leaf in the tree and wanted to go to one of
+ // the sons. But the son was not there. It now depends on the
+ // direction in which we wanted to go.
+ if (node_path.getLastComparisonResult().getOrder() < 0) {
+ // We wanted to go left. So the one we compared with is
+ // the one higher than we wanted. If we just put it into
+ // the node_path, then the following algorithm below will find
+ // the smaller one.
+ //
+ // This is exactly the same as with superdomain below.
+ // Therefore, we just fall through to the next case.
+ } else {
+ // We wanted to go right. That means we want to output the
+ // one which is the largest in the tree defined by the
+ // compared one (it is either the compared one, or some
+ // subdomain of it). There probably is not an easy trick
+ // for this, so we just find the correct place.
+ const RBNode<T>* current(node_path.getLastComparedNode());
+ while (current != NULLNODE) {
+ node_path.push(current);
+ // Go a level down and as much right there as possible
+ current = current->down_;
+ while (current->right_ != NULLNODE) {
+ // A small trick. The current may be NULLNODE, but
+ // such node has the right_ pointer and it is equal
+ // to NULLNODE.
+ current = current->right_;
+ }
+ }
+ // Now, the one on top of the path is the one we want. We
+ // return it now and leave it there, so we can search for
+ // previous of it the next time we'are called.
+ node_path.last_comparison_ =
+ dns::NameComparisonResult(0, 0,
+ dns::NameComparisonResult::EQUAL);
+ return (node_path.top());
+ }
+ // No break; here - we want to fall through. See above.
+ case dns::NameComparisonResult::SUPERDOMAIN:
+ // This is the case there's a "compressed" node and we looked for
+ // only part of it. The node itself is larger than we wanted, but
+ // if we put it to the node_path and then go one step left from it,
+ // we get the correct result.
+ node_path.push(node_path.getLastComparedNode());
+ // Correct the comparison result, so we won't trigger this case
+ // next time previousNode is called. We already located the correct
+ // place to start. The value is partly nonsense, but that doesn't
+ // matter any more.
+ node_path.last_comparison_ =
+ dns::NameComparisonResult(0, 0,
+ dns::NameComparisonResult::EQUAL);
+ break;
+ case dns::NameComparisonResult::SUBDOMAIN:
+ // A subdomain means we returned the one above the searched one
+ // already and it is on top of the stack. This is was smaller
+ // than the one already, but we want to return yet smaller one.
+ // So we act as if it was EQUAL.
+ break;
+ case dns::NameComparisonResult::EQUAL:
+ // The find gave us an exact match or the previousNode was called
+ // already, which located the exact node. The rest of the function
+ // goes one domain left and returns it for us.
+ break;
+ }
+
+ // So, the node_path now contains the path to a node we want previous for.
+ // We just need to go one step left.
+
+ if (node_path.getLevelCount() == 0) {
+ // We got past the first one. So, we're returning NULL from
+ // now on.
+ return (NULL);
}
const RBNode<T>* node(node_path.top());
@@ -1171,13 +1263,13 @@ RBTree<T>::previousNode(RBTreeNodeChain<T>& node_path) const {
// We are the smallest ones in this tree. We go one level
// up. That one is the smaller one than us.
- if (node_path.getLevelCount() == 1) {
- // This was the root of the tree. We can't go up, sorry, we end.
+ node_path.pop();
+ if (node_path.getLevelCount() == 0) {
+ // We're past the first one
return (NULL);
+ } else {
+ return (node_path.top());
}
-
- node_path.pop();
- return (node_path.top());
}
// Exchange the node at the top of the path, as we move horizontaly
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 1d5f3c2..f7f59e4 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -364,24 +364,37 @@ TEST_F(RBTreeTest, nextNode) {
EXPECT_EQ(static_cast<void*>(NULL), node);
}
-// Just walk until the beginning of the tree and check it is OK
+// Just walk using previousNode until the beginning of the tree and check it is
+// OK
+//
+// rbtree - the tree to walk
+// node - result of previous call to find(), starting position of the walk
+// node_path - the path from the previous call to find(), will be modified
+// chain_length - the number of names that should be in the chain to be walked
+// (0 means it should be empty, 3 means 'a', 'b' and 'c' should be there -
+// this is always from the beginning of the names[] list).
+// skip_first - if this is false, the node should already contain the node with
+// the first name of the chain. If it is true, the node should be NULL
+// (true is for finds that return no match, false for the ones that return
+// match)
void
previousWalk(RBTree<int>& rbtree, const RBNode<int>* node,
- RBTreeNodeChain<int>& node_path, size_t position, bool skipFirst)
+ RBTreeNodeChain<int>& node_path, size_t chain_length,
+ bool skip_first)
{
- if (skipFirst) {
+ if (skip_first) {
// If the first is not found, this is supposed to be NULL and we skip
// it in our checks.
EXPECT_EQ(static_cast<void*>(NULL), node);
node = rbtree.previousNode(node_path);
}
- for (size_t i(position); i > 0; --i) {
+ for (size_t i(chain_length); i > 0; --i) {
EXPECT_NE(static_cast<void*>(NULL), node);
EXPECT_EQ(Name(names[i - 1]), node_path.getAbsoluteName());
// Find the node at the path and check the value is the same
// (that it really returns the correct corresponding node)
//
- // The "hidden" nodes can not be found
+ // The "empty" nodes can not be found
if (node->getData()) {
const RBNode<int>* node2(NULL);
RBTreeNodeChain<int> node_path2;
@@ -461,10 +474,26 @@ TEST_F(RBTreeTest, previousNode) {
}
{
+ SCOPED_TRACE("Start below a leaf");
+ // We exit a leaf by going down. We should start by the one
+ // we exited - 'c' (actually, we should get it by the find, as partial
+ // match).
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ rbtree.find<void*>(Name("b.c"), &node, node_path, NULL,
+ NULL));
+ previousWalk(rbtree, node, node_path, 3, false);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
SCOPED_TRACE("Start to the right of a leaf");
// When searching for this, we exit the 'x' node to the right side,
// so we should go x afterwards.
- EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+
+ // The d.e.f is empty node, so it is hidden by find. Therefore NOTFOUND
+ // and not PARTIALMATCH.
+ EXPECT_EQ(RBTree<int>::NOTFOUND,
rbtree.find<void*>(Name("xy.d.e.f"), &node, node_path,
NULL, NULL));
previousWalk(rbtree, node, node_path, 5, true);
@@ -476,7 +505,10 @@ TEST_F(RBTreeTest, previousNode) {
SCOPED_TRACE("Start to the left of a leaf");
// This is similar to the previous, but we exit the 'z' leaf to the
// left side, so should not visit z at all then.
- EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+
+ // The d.e.f is empty node, so it is hidden by find. Therefore NOTFOUND
+ // and not PARTIALMATCH.
+ EXPECT_EQ(RBTree<int>::NOTFOUND,
rbtree.find<void*>(Name("yz.d.e.f"), &node, node_path,
NULL, NULL));
previousWalk(rbtree, node, node_path, 9, true);
More information about the bind10-changes
mailing list