[svn] commit: r4119 - in /branches/trac461/src/lib/datasrc: rbtree.h tests/rbtree_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Sat Jan 1 15:33:05 UTC 2011
Author: hanfeng
Date: Sat Jan 1 15:33:05 2011
New Revision: 4119
Log:
the general design add node path to find and use it to get the next node
Modified:
branches/trac461/src/lib/datasrc/rbtree.h
branches/trac461/src/lib/datasrc/tests/rbtree_unittest.cc
Modified: branches/trac461/src/lib/datasrc/rbtree.h
==============================================================================
--- branches/trac461/src/lib/datasrc/rbtree.h (original)
+++ branches/trac461/src/lib/datasrc/rbtree.h Sat Jan 1 15:33:05 2011
@@ -29,6 +29,7 @@
#include <exception>
#include <ostream>
#include <algorithm>
+#include <stack>
namespace isc {
namespace datasrc {
@@ -140,6 +141,9 @@
return (&null_node);
}
+ /// \brief return the next node which is bigger than current node
+ /// in the same tree
+ const RBNode<T> *successor() const;
/// data to maintain the rbtree balance
RBNode<T>* parent_;
RBNode<T>* left_;
@@ -188,7 +192,31 @@
RBNode<T>::~RBNode() {
}
-
+template <typename T>
+const RBNode<T> *
+RBNode<T>::successor()const {
+ const RBNode<T> *current = this;
+ // If it has right node, the successor is the left-most node of the right
+ // subtree.
+ if (right_ != NULL_NODE()) {
+ current = right_;
+ while (current->left_ != NULL_NODE()) {
+ current = current->left_;
+ }
+ return (current);
+ }
+
+
+ // Otherwise go up until we find the first left branch on our path to
+ // root. If found, the parent of the branch is the successor.
+ // Otherwise, we return the null node
+ const RBNode<T>* parent = current->parent_;
+ while (parent != NULL_NODE() && current == parent->right_) {
+ current = parent;
+ parent = parent->parent_;
+ }
+ return (parent);
+}
/// \brief \c RBTree class represents all the domains with the same suffix,
/// so it can be used to store the domains in one zone.
///
@@ -245,6 +273,10 @@
class RBTree : public boost::noncopyable, public SearchPolicy {
friend class RBNode<T>;
public:
+
+ /// node chain save the path from super to sub domains
+ typedef typename std::stack<const RBNode<T> *> NodeChain;
+
/// \brief The return value for the \c find() insert() and erase() method
enum Result {
SUCCEED, //insert or erase succeed
@@ -252,6 +284,8 @@
PARTIALMATCH, //find part of target name
NOTFOUND, // for find function means no related name found
// for erase function means erase not exist name
+ NONTERMINAL, //the name searched is super domain of node in the tree
+ //but itself has no related data
ALREADYEXIST, //for insert operation, the name to insert already exist
};
@@ -273,6 +307,30 @@
/// \c unknown
Result find(const isc::dns::Name& name, RBNode<T>** node) const;
Result find(const isc::dns::Name& name, const RBNode<T>** node) const;
+
+ /// \brief same functionality as find, but also return the node path
+ /// which store the base domains of target name
+ /// \param name is the target, node_chain will store all the
+ /// base domain of the target domain, node will point to the
+ /// target node ,if we has exact same name or partical name in current tree.
+ /// so for example, in zone a, we has
+ /// b.a, c.b.a and d.b.a search c.b.a, node_path will store b.a. and a
+ /// node will points to c.b.a
+ Result findEx(const isc::dns::Name& name, RBNode<T>** node,
+ NodeChain &node_path) const;
+ Result findEx(const isc::dns::Name& name, const RBNode<T>** node,
+ NodeChain &node_path) const;
+
+ /// \brief return the next node which is bigger than node
+ /// \param node_path store the path from base to sub domains in reverse order
+ /// the node_path is fetched through findEx function call, next_node_path will
+ /// store the node path to next_node
+ const RBNode<T> *nextNode(const RBNode<T> *node, const NodeChain &node_path,
+ NodeChain &next_node_path) const;
+
+ /// \brief return the absolute name of node
+ /// \param node_path store all the ancestor domains of current node
+ isc::dns::Name nodeAbsoluteName(const RBNode<T> *node, const NodeChain &node_path) const;
/// \brief Get the total node count in the tree
/// the node count including the node created common suffix node,
@@ -326,17 +384,6 @@
//@{
/// \brief delete tree whose root is equal to node
void deleteHelper(RBNode<T> *node);
- /// \brief find the node with name
- /// \param name is the target, up will points to the base domain of
- /// the tree which name resides, node will point to the target node
- /// if we has exact same name or partical name in current tree.
- /// so for example, in zone a, we has
- /// b.a, c.b.a and d.b.a search c.b.a, up will points to b.a.
- /// and node will points to c.b.a
- /// \note parameter up now is not used by any funciton, but we are gonna
- /// need it soon to implement function like remove
- Result findHelper(const isc::dns::Name& name, const RBNode<T>** up,
- RBNode<T>** node) const;
void dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
unsigned int depth) const;
/// for indent purpose, add certian mount empty charachter to output stream
@@ -403,33 +450,30 @@
template <typename T, typename SearchPolicy>
typename RBTree<T,SearchPolicy>::Result
RBTree<T,SearchPolicy>::find(const isc::dns::Name& name, RBNode<T>** node) const {
- const RBNode<T>* up_node = NULLNODE;
- return (findHelper(name, &up_node, node));
+ NodeChain node_path;
+ return (findEx(name, node, node_path));
}
template <typename T, typename SearchPolicy>
typename RBTree<T,SearchPolicy>::Result
RBTree<T,SearchPolicy>::find(const isc::dns::Name& name, const RBNode<T>** node) const {
- const RBNode<T>* up_node;
- RBNode<T>* target_node;
+ RBNode<T>* target_node = NULLNODE;
+ NodeChain node_path;
const typename RBTree<T,SearchPolicy>::Result ret =
- findHelper(name, &up_node, &target_node);
- if (ret != NOTFOUND) {
- *node = target_node;
- }
+ findEx(name, &target_node, node_path);
+ *node = target_node;
return (ret);
}
template <typename T, typename SearchPolicy>
typename RBTree<T,SearchPolicy>::Result
-RBTree<T,SearchPolicy>::findHelper(const isc::dns::Name& target_name, const RBNode<T>** up_node,
- RBNode<T>** target) const
+RBTree<T,SearchPolicy>::findEx(const isc::dns::Name& target_name, RBNode<T>** target,
+ NodeChain &node_path) const
{
using namespace helper;
RBNode<T>* node = root_;
typename RBTree<T,SearchPolicy>::Result ret = NOTFOUND;
- *up_node = NULLNODE;
isc::dns::Name name = target_name;
while (node != NULLNODE) {
@@ -451,9 +495,9 @@
node = (compare_result.getOrder() < 0) ?
node->left_ : node->right_;
} else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
- *up_node = node;
+ node_path.push(node);
name = name - node->name_;
- if (!node->isEmpty()) {
+ if (SearchPolicy::returnEmptyNode() || !node->isEmpty()) {
ret = RBTree<T,SearchPolicy>::PARTIALMATCH;
*target = node;
}
@@ -465,6 +509,71 @@
}
return (ret);
+}
+
+template <typename T, typename SearchPolicy>
+typename RBTree<T,SearchPolicy>::Result
+RBTree<T,SearchPolicy>::findEx(const isc::dns::Name& name, const RBNode<T>** target,
+ NodeChain &node_path) const
+{
+ RBNode<T> *non_const_target;
+ const typename RBTree<T,SearchPolicy>::Result ret =
+ findEx(name, &non_const_target, node_path);
+ *target = non_const_target;
+ return (ret);
+}
+
+template <typename T, typename SearchPolicy>
+const RBNode<T> *
+RBTree<T, SearchPolicy>::nextNode(const RBNode<T> *node, const NodeChain &node_path,
+ NodeChain &next_node_path) const
+{
+ next_node_path = node_path;
+ // if node has sub domain, the next domain is the samllest
+ // domain in sub domain tree
+ if (node->down_ != NULLNODE) {
+ next_node_path.push(node);
+ const RBNode<T> *left_most = node->down_;
+ while (left_most->left_ != NULLNODE) {
+ left_most = left_most->left_;
+ }
+ return (left_most);
+ }
+
+ // otherwise found the successor node in current level
+ const RBNode<T> *successor = node->successor();
+ if (successor != NULLNODE) {
+ 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 has successor we gonna keep moving to up
+ // level
+ while (!next_node_path.empty()) {
+ const RBNode<T> *up_node_successor = next_node_path.top()->successor();
+ next_node_path.pop();
+ if (up_node_successor != NULLNODE) {
+ return (up_node_successor);
+ }
+ }
+
+ return (NULLNODE);
+}
+
+template <typename T, typename SearchPolicy>
+isc::dns::Name
+RBTree<T,SearchPolicy>::nodeAbsoluteName(const RBNode<T> *node,
+ const NodeChain &node_path) const
+{
+ isc::dns::Name absoluteName = node->getName();
+ NodeChain node_path_copy = node_path;
+ while (!node_path_copy.empty()) {
+ absoluteName = absoluteName.concatenate(node_path_copy.top()->getName());
+ node_path_copy.pop();
+ }
+
+ return (absoluteName);
}
template <typename T, typename SearchPolicy>
Modified: branches/trac461/src/lib/datasrc/tests/rbtree_unittest.cc
==============================================================================
--- branches/trac461/src/lib/datasrc/tests/rbtree_unittest.cc (original)
+++ branches/trac461/src/lib/datasrc/tests/rbtree_unittest.cc Sat Jan 1 15:33:05 2011
@@ -222,6 +222,45 @@
EXPECT_EQ(Name("q"), rbtnode->getName());
}
+
+/*
+ *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
+
+ * */
+void testNodeAdjacentHelper(const RBTree<int, ReturnEmptyNodePolicy> &tree, const Name ¤tDomain, const Name &nextDomain) {
+ RBTree<int>::NodeChain node_path;
+ RBTree<int>::NodeChain next_node_path;
+ const RBNode<int> *node;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH, tree.findEx(currentDomain, &node, node_path));
+ node = tree.nextNode(node, node_path, next_node_path);
+ EXPECT_EQ(nextDomain, tree.nodeAbsoluteName(node, next_node_path));
+}
+
+TEST_F(RBTreeTest, nextNode) {
+ const char *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"};
+ int name_count = sizeof(names) / sizeof(names[0]);
+ int i = 0;
+ for (; i < name_count - 1; ++i) {
+ testNodeAdjacentHelper(expose_empty_node_rbtree, Name(names[i]), Name(names[i + 1]));
+ }
+}
+
TEST_F(RBTreeTest, dumpTree) {
std::ostringstream str;
std::ostringstream str2;
More information about the bind10-changes
mailing list