BIND 10 trac517, updated. 6fb3a7ca7f9f1b7018493a263b3063b0b0962b5e fix trivial comment issue

BIND 10 source code commits bind10-changes at lists.isc.org
Wed Jan 26 06:45:43 UTC 2011


The branch, trac517 has been updated
       via  6fb3a7ca7f9f1b7018493a263b3063b0b0962b5e (commit)
       via  b211d93037f31731426dbf073098ebfa8ae16bc4 (commit)
      from  89cbb6aafeaf5cbc51b50a0caa4542c7b0f43eb4 (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 6fb3a7ca7f9f1b7018493a263b3063b0b0962b5e
Author: hanfeng <ben.han.cn at gmail.com>
Date:   Wed Jan 26 14:45:07 2011 +0800

    fix trivial comment issue

commit b211d93037f31731426dbf073098ebfa8ae16bc4
Author: hanfeng <ben.han.cn at gmail.com>
Date:   Wed Jan 26 14:14:09 2011 +0800

    fix efficiency problem for node chain, merge interface

-----------------------------------------------------------------------

Summary of changes:
 src/lib/datasrc/rbtree.h                 |  275 ++++++++++++++----------------
 src/lib/datasrc/tests/rbtree_unittest.cc |   22 ++--
 2 files changed, 142 insertions(+), 155 deletions(-)

-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index 013da19..3ebc8e8 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -29,7 +29,7 @@
 #include <exception>
 #include <ostream>
 #include <algorithm>
-#include <stack>
+#include <cassert>
 
 namespace isc {
 namespace datasrc {
@@ -55,9 +55,6 @@ operator-(const isc::dns::Name& super_name, const isc::dns::Name& sub_name) {
 }
 }
 
-template <typename T>
-class RBTree;
-
 /// \brief \c RBNode is used by RBTree to store any data related to one domain
 ///     name.
 ///
@@ -144,16 +141,7 @@ public:
     /// empty nodes anywhere.
     bool isEmpty() const { return (data_.get() == NULL); }
 
-    /// \brief return the next node which is bigger than current node
-    /// in the same tree
-    ///
-    /// The next successor for this node is the node in the same tree which
-    /// name is bigger than current node, since RBTree is a tree in tree,
-    /// so the successor maybe NOT the cloest next node for current node,
-    /// especially when current node has sub domains, the next node is the
-    /// smallest node in the sub domain tree.
-    const RBNode<T>* successor() const;
-    //@}
+   //@}
 
     /// \name Setter functions.
     //@{
@@ -187,6 +175,16 @@ private:
         return (&null_node);
     }
 
+    /// \brief return the next node which is bigger than current node
+    /// in the same tree
+    ///
+    /// The next successor for this node is the node in the same tree which
+    /// name is bigger than current node, since RBTree is a tree in tree,
+    /// so the successor maybe NOT the cloest next node for current node,
+    /// especially when current node has sub domains, the next node is the
+    /// smallest node in the sub domain tree.
+    const RBNode<T>* successor() const;
+
     /// \name Data to maintain the rbtree structure.
     //@{
     RBNode<T>*  parent_;
@@ -276,6 +274,56 @@ RBNode<T>::successor() const {
     return (parent);
 }
 
+
+/// A chain is used to keep track of the sequence of nodes to reach any
+/// given node from the root of rbtree.  RBNode did not have parent
+/// pointers in them (for memory usage reasons) so there was no way to find
+/// the path back to the root from any given node.
+template <typename T>
+class NodeChain {
+    public:
+        NodeChain() : node_count_(0) {}
+        NodeChain(const NodeChain<T> &node_path) {
+            node_count_ = node_path.node_count_;
+            if (node_count_ > 0) {
+                memcpy(nodes_, node_path.nodes_, node_count_ * sizeof(RBNode<T> *));
+            }
+        }
+
+        NodeChain<T> &operator=(const NodeChain<T> &node_path) {
+            node_count_ = node_path.node_count_;
+            if (node_count_ > 0) {
+                memcpy(nodes_, node_path.nodes_, node_count_ * sizeof(RBNode<T> *));
+            }
+            return(*this);
+        }
+
+        bool isEmpty() const { return(node_count_ == 0); }
+
+        const RBNode<T>* top() const {
+            assert(node_count_ > 0);
+            return(nodes_[node_count_ - 1]);
+        }
+
+        void pop() {
+            assert(node_count_ > 0);
+            --node_count_;
+        }
+
+        void push(const RBNode<T>* node) {
+            assert(node_count_ < RBT_MAX_LEVEL);
+            nodes_[node_count_++] = node;
+        }
+
+    private:
+        /// DNSSEC restricts the number of "logical" labels in a name to
+        /// 255, meaning only 254 pointers are needed in the worst case.
+        enum {RBT_MAX_LEVEL = 254};
+        const RBNode<T>* nodes_[RBT_MAX_LEVEL];
+        int node_count_;
+};
+
+
 // note: the following class description is documented using multiline comments
 // because the verbatim diagram contain a backslash, which could be interpreted
 // as escape of newline in singleline comment.
@@ -296,13 +344,13 @@ RBNode<T>::successor() const {
  *
  *  Depending on different usage, rbtree will support different search policy.
  *  Whether return empty node to end user is one policy among them. the default
- *  policy will NOT return empty node to end user, pass ture will get empty node
+ *  policy will NOT return empty node to end user, pass true will get empty node
  *  during find is needed.
- *  \note The search policy only affect find behavior of rbtree, but when
- *  inserting one name, if the node already exist not matter it's insert
- *  explictly by end user or empty node created by the rbtree itself,
- *  insert will return ALREADYEXISTS not matter we want expose empty node
- *  or not.
+ *  \note The search policy only affect find behavior of rbtree. When
+ *  inserting one name into RBTree, if the node with the name  already exists
+ *  in the rbtree and it's empty node which doesn't have any data, even the
+ *  search policy is not return empty node to end user, the insert function
+ *  will still return ALREADYEXISTS.
  *
  * \anchor diagram
  *
@@ -353,9 +401,6 @@ public:
         ALREADYEXISTS,
     };
 
-    /// save the nodes along the path from root to the target node
-    typedef typename std::stack<const RBNode<T>*> NodeChain;
-
     /// \name Constructor and Destructor
     //@{
     /// The constructor.
@@ -410,9 +455,36 @@ public:
     ///    of it. In that case, node parameter is left intact.
     //@{
 
+    /// \brief Simple find.
+    ///
+    /// Acts as described in the \ref find section.
+    Result find(const isc::dns::Name& name, RBNode<T>** node) const {
+        NodeChain<T> node_path;
+        return (find<void*>(name, node, node_path, NULL, NULL));
+    }
+
+    /// \brief Simple find returning immutable node.
+    ///
+    /// Acts as described in the \ref find section, but returns immutable node
+    /// pointer.
+    Result find(const isc::dns::Name& name, const RBNode<T>** node) const {
+        NodeChain<T> node_path;
+        RBNode<T> *target_node = NULL;
+        Result ret = (find<void*>(name, &target_node, node_path, NULL, NULL));
+        if (ret != NOTFOUND) {
+            *node = target_node;
+        }
+        return (ret);
+    }
+
     /// \brief Find with callback.
     ///
     /// \anchor callback
+    /// Returning all the ancesotr nodes is quite useful, since each node
+    /// has down pointer pointing the subdomains so we can travel downside
+    /// from one node, but there is no way to traval upside, with all the
+    /// ancestors we can get the absolute name for the node, also we can
+    /// use the ancestors to find the next node in the tree.
     ///
     /// This version of find calls the callback whenever traversing (on the
     /// way from root down the tree) a marked node on the way down through the
@@ -432,6 +504,10 @@ public:
     /// \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
+    /// \param node_path It will save all the ancestor nodes
+    ///     to the tree containing node. If we looked for o.w.y.d.e.f in the
+    ///     \ref diagram, the node_path will have w.y node and d.e.f node.
+    /// with the node path, we can also get the next node of current node
     /// \param callback If non \c NULL, a call back function to be called
     ///     at marked nodes (see above).
     /// \param callback_arg A caller supplied argument to be passed to
@@ -440,69 +516,31 @@ public:
     /// \return As described above, but in case of callback returning true,
     ///     it returns immediately with the current node.
     template <typename CBARG>
-    Result find(const isc::dns::Name& name, RBNode<T>** node,
-                bool (*callback)(const RBNode<T>&, CBARG),
-                CBARG callback_arg) const;
-
-    /// \brief Find with callback returning immutable node.
-    ///
-    /// It has the same behaviour as the find with \ref callback version.
-    template <typename CBARG>
-    Result find(const isc::dns::Name& name, const RBNode<T>** node,
+    Result find(const isc::dns::Name& name,
+                RBNode<T>** node,
+                NodeChain<T> &node_path,
                 bool (*callback)(const RBNode<T>&, CBARG),
                 CBARG callback_arg) const;
 
-    /// \brief Simple find.
-    ///
-    /// Acts as described in the \ref find section.
-    Result find(const isc::dns::Name& name, RBNode<T>** node) const {
-        return (find<void*>(name, node, NULL, NULL));
-    }
-
     /// \brief Simple find returning immutable node.
     ///
-    /// Acts as described in the \ref find section, but returns immutable node
-    /// pointer.
-    Result find(const isc::dns::Name& name, const RBNode<T>** node) const {
-        return (find<void*>(name, node, NULL, NULL));
-    }
-
-    /// \brief extensive versoin of find
-    ///
-    /// This version of find, not only return the longest node matching
-    /// target name but also return all the ancestors for the node returned.
-    /// Actually it's the underlaying implementation for other version of
-    /// find.
-    ///
-    /// Returning all the ancesotr nodes is quite useful, since each node
-    /// has down pointer pointing the subdomains so we can travel downside
-    /// from one node, but there is no way to traval upside, with all the
-    /// ancestors we can get the absolute name for the node, also we can
-    /// use the ancestors to find the next node in the tree.
-    ///
-    /// \param name What should be found.
-    /// \param node_path It will save all the ancestor nodes
-    ///     to the tree containing node. If we looked for o.w.y.d.e.f in the
-    ///     \ref diagram, the node_path will have w.y node and d.e.f node.
-    /// with the node path, we can also get the next node of current node
-    /// \param node The found node.
-    template <typename CBARG>
-    Result findEx(const isc::dns::Name& name, NodeChain& node_path,
-                  RBNode<T>** node,
-                  bool (*callback)(const RBNode<T>&, CBARG),
-                  CBARG callback_arg) const;
-
-    /// \brief Simple findEx returning immutable node.
-    ///
-    /// Acts as described in the \ref findEx section, but returns immutable
+    /// Acts as described in the \ref find section, but returns immutable
     /// node pointer.
     template <typename CBARG>
-    Result findEx(const isc::dns::Name& name, NodeChain& node_path,
-                  const RBNode<T>** node,
-                  bool (*callback)(const RBNode<T>&, CBARG),
-                  CBARG callback_arg) const;
-
-
+    Result find(const isc::dns::Name& name,
+                const RBNode<T>** node,
+                NodeChain<T>& node_path,
+                bool (*callback)(const RBNode<T>&, CBARG),
+                CBARG callback_arg) const
+    {
+        RBNode<T> *target_node = NULL;
+        Result ret = find(name, &target_node, node_path, callback, callback_arg);
+        if (ret != NOTFOUND) {
+            *node = target_node;
+        }
+        return (ret);
+    }
+    //@}
     /// \brief return the next node which is bigger than node
     ///
     /// Each node in the tree has down pointer pointing to its subdomains,
@@ -512,20 +550,16 @@ public:
     /// keep moving to up level, and this is the reason why we needs to provide
     /// all the ancestor nodes in node_path
     ///
+    ///
     /// Return the node_path for next node is convinent in case we want to get
     /// the next node of next node, so in this way, we can iterator the whole
     /// domain trees from root node, and the node_path for root is empty.
     ///
-    /// \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, which can be used in turn 
-    /// to find the next node of next node.
+    /// \param node_path store all the nodes along the path from root to node
+    /// node_path is fetched through find function call, after function call
+    /// node_path will be the node chain for the next node
     const RBNode<T>* nextNode(const RBNode<T>* node,
-                              const NodeChain& node_path,
-                              NodeChain& next_node_path) const;
-
-
-    //@}
+                              NodeChain<T>& node_path) const;
 
     /// \brief Get the total number of nodes in the tree
     ///
@@ -675,40 +709,12 @@ RBTree<T>::deleteHelper(RBNode<T>* root) {
 template <typename T>
 template <typename CBARG>
 typename RBTree<T>::Result
-RBTree<T>::find(const isc::dns::Name& name, RBNode<T>** node,
-                bool (*callback)(const RBNode<T>&, CBARG),
-                CBARG callback_arg) const
-{
-    NodeChain node_path;
-    return (findEx(name, node_path, node, callback, callback_arg));
-}
-
-template <typename T>
-template <typename CBARG>
-typename RBTree<T>::Result
-RBTree<T>::find(const isc::dns::Name& name, const RBNode<T>** node,
+RBTree<T>::find(const isc::dns::Name& target_name,
+                RBNode<T>** target,
+                NodeChain<T>& node_path,
                 bool (*callback)(const RBNode<T>&, CBARG),
                 CBARG callback_arg) const
 {
-    NodeChain node_path;
-    RBNode<T>* target_node = NULLNODE;
-    const Result ret =
-        findEx(name, node_path, &target_node, callback, callback_arg);
-    if (ret != NOTFOUND) {
-        *node = target_node;
-    }
-    return (ret);
-}
-
-template <typename T>
-template <typename CBARG>
-typename RBTree<T>::Result
-RBTree<T>::findEx(const isc::dns::Name& target_name,
-                  NodeChain& node_path,
-                  RBNode<T>** target,
-                  bool (*callback)(const RBNode<T>&, CBARG),
-                  CBARG callback_arg) const
-{
     using namespace helper;
 
     RBNode<T>* node = root_;
@@ -756,33 +762,14 @@ RBTree<T>::findEx(const isc::dns::Name& target_name,
 }
 
 template <typename T>
-template <typename CBARG>
-typename RBTree<T>::Result
-RBTree<T>::findEx(const isc::dns::Name& target_name,
-                  NodeChain& node_path,
-                  const RBNode<T>** target,
-                  bool (*callback)(const RBNode<T>&, CBARG),
-                  CBARG callback_arg) const
-{
-    RBNode<T>* node = NULLNODE;
-    const Result ret =
-        findEx(target_name, node_path, &node, callback, callback_arg);
-    if (ret != NOTFOUND) {
-        *target = node;
-    }
-    return (ret);
-}
-
-template <typename T>
 const RBNode<T>*
-RBTree<T>::nextNode(const RBNode<T>* node, const NodeChain& node_path,
-                    NodeChain& next_node_path) const
+RBTree<T>::nextNode(const RBNode<T>* node,
+                    NodeChain<T>& node_path) const
 {
-    next_node_path = node_path;
     // if node has sub domain, the next domain is the smallest
     // domain in sub domain tree
     if (node->down_ != NULLNODE) {
-        next_node_path.push(node);
+        node_path.push(node);
         const RBNode<T>* left_most = node->down_;
         while (left_most->left_ != NULLNODE) {
             left_most = left_most->left_;
@@ -800,9 +787,9 @@ RBTree<T>::nextNode(const RBNode<T>* node, const NodeChain& node_path,
     // 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();
+    while (!node_path.isEmpty()) {
+        const RBNode<T>* up_node_successor = node_path.top()->successor();
+        node_path.pop();
         if (up_node_successor != NULLNODE) {
             return (up_node_successor);
         }
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index f948cdc..edb779e 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -184,6 +184,7 @@ testCallback(const RBNode<int>&, bool* callack_checker) {
 }
 
 TEST_F(RBTreeTest, callback) {
+    NodeChain<int> node_path;
     // by default callback isn't enabled
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("callback.example"),
                                                   &rbtnode));
@@ -218,7 +219,7 @@ TEST_F(RBTreeTest, callback) {
     // check if the callback is called from find()
     bool callback_called = false;
     EXPECT_EQ(RBTree<int>::EXACTMATCH,
-              rbtree.find(Name("sub.callback.example"), &crbtnode,
+              rbtree.find(Name("sub.callback.example"), &crbtnode, node_path,
                           testCallback, &callback_called));
     EXPECT_TRUE(callback_called);
 
@@ -227,7 +228,7 @@ TEST_F(RBTreeTest, callback) {
     parentrbtnode->enableCallback();
     callback_called = false;
     EXPECT_EQ(RBTree<int>::EXACTMATCH,
-              rbtree.find(Name("callback.example"), &crbtnode,
+              rbtree.find(Name("callback.example"), &crbtnode, node_path,
                           testCallback, &callback_called));
     EXPECT_FALSE(callback_called);
 }
@@ -252,11 +253,11 @@ TEST_F(RBTreeTest, callback) {
  */
 Name
 nodeAbsoluteName(const RBNode<int>* node,
-                 const RBTree<int>::NodeChain& node_path)
+                 const NodeChain<int>& node_path)
 {
     isc::dns::Name absoluteName = node->getName();
-    RBTree<int>::NodeChain node_path_copy = node_path;
-    while (!node_path_copy.empty()) {
+    NodeChain<int> node_path_copy = node_path;
+    while (!node_path_copy.isEmpty()) {
         absoluteName = absoluteName.concatenate(node_path_copy.top()->getName());
         node_path_copy.pop();
     }
@@ -267,13 +268,12 @@ void
 testNodeAdjacentHelper(const RBTree<int>& tree, const Name& currentDomain,
                        const Name& nextDomain)
 {
-    RBTree<int>::NodeChain node_path;
-    RBTree<int>::NodeChain next_node_path;
-    const RBNode<int>* node;
+    NodeChain<int> node_path;
+    const RBNode<int>* node = NULL;
     EXPECT_EQ(RBTree<int>::EXACTMATCH,
-              tree.findEx<void*>(currentDomain, node_path, &node, NULL, NULL));
-    node = tree.nextNode(node, node_path, next_node_path);
-    EXPECT_EQ(nextDomain, nodeAbsoluteName(node,  next_node_path));
+              tree.find<void*>(currentDomain, &node, node_path, NULL, NULL));
+    node = tree.nextNode(node, node_path);
+    EXPECT_EQ(nextDomain, nodeAbsoluteName(node,  node_path));
 }
 
 TEST_F(RBTreeTest, nextNode) {




More information about the bind10-changes mailing list