BIND 10 master, updated. c7a5a56e8269ad841c1b43a635fc3c49ea254638 [1971] Fix broken tree structure that didn't match the one in the figure

BIND 10 source code commits bind10-changes at lists.isc.org
Tue May 15 20:03:04 UTC 2012


The branch, master has been updated
       via  c7a5a56e8269ad841c1b43a635fc3c49ea254638 (commit)
       via  39b658ef4f5b272f727eb501d68caa30d9a5ebc3 (commit)
       via  e401615079a02327a9803abc01ab0cb2e36000fb (commit)
       via  94a2da0d06d02d1d5991e0f8d6cb19bed1e5d665 (commit)
       via  3692c48386327df01b447308fb39ca748c451f47 (commit)
       via  74ac6abb7e9bdf613d5aa6c93426ff7bf9f671ad (commit)
      from  a807c0d3ef2c845efdc1dae050cf52f951c21cbf (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 c7a5a56e8269ad841c1b43a635fc3c49ea254638
Author: Mukund Sivaraman <muks at isc.org>
Date:   Tue May 15 21:26:53 2012 +0530

    [1971] Fix broken tree structure that didn't match the one in the figure

commit 39b658ef4f5b272f727eb501d68caa30d9a5ebc3
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon May 14 13:15:20 2012 +0530

    [1971] Update test rbtree (of rbtrees) to suit our right-child testcase

commit e401615079a02327a9803abc01ab0cb2e36000fb
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon May 14 12:52:45 2012 +0530

    [master] Remove duplicate data

commit 94a2da0d06d02d1d5991e0f8d6cb19bed1e5d665
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon May 14 12:17:52 2012 +0530

    [1971] Add another testcase for untested code detected by lcov
    
    When find() returns COMMONANCESTOR and exits to the right of a
    last_compared_node which has a valid down pointer, previousNode() has to
    return nodes beginning at at the right-most leaf of subtrees in
    last_compared_node->down.

commit 3692c48386327df01b447308fb39ca748c451f47
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon May 14 12:08:20 2012 +0530

    [1971] Test the node_path.isEmpty() check
    
    If previousNode() has been called enough times that it has popped
    all nodes from the node chain when walking up the trees, the
    node chain is then empty. If previousNode() is called yet again
    on the empty tree, it should return NULL.

commit 74ac6abb7e9bdf613d5aa6c93426ff7bf9f671ad
Author: Mukund Sivaraman <muks at isc.org>
Date:   Mon May 14 10:54:01 2012 +0530

    [master] Update .gitignore

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

Summary of changes:
 .gitignore                               |    6 ++
 src/lib/datasrc/tests/rbtree_unittest.cc |   76 +++++++++++++++++++----------
 2 files changed, 56 insertions(+), 26 deletions(-)

-----------------------------------------------------------------------
diff --git a/.gitignore b/.gitignore
index da9d3b4..3480cb6 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,6 @@
+*.gcda
+*.gcno
+*.gcov
 *.la
 *.lo
 *.o
@@ -28,4 +31,7 @@ TAGS
 /py-compile
 /stamp-h1
 
+/all.info
+/coverage-cpp-html
 /dns++.pc
+/report.info
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 25eafb4..a11bff5 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -45,8 +45,8 @@ const size_t Name::MAX_LABELS;
  *             c   |    g.h
  *                 |     |
  *                w.y    i
- *              /  |  \
- *             x   |   z
+ *              /  |  \   \
+ *             x   |   z   k
  *                 |   |
  *                 p   j
  *               /   \
@@ -59,7 +59,7 @@ protected:
     RBTreeTest() : rbtree_expose_empty_node(true), crbtnode(NULL) {
         const char* const domain_names[] = {
             "c", "b", "a", "x.d.e.f", "z.d.e.f", "g.h", "i.g.h", "o.w.y.d.e.f",
-            "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f"};
+            "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f", "k.g.h"};
         int name_count = sizeof(domain_names) / sizeof(domain_names[0]);
         for (int i = 0; i < name_count; ++i) {
             rbtree.insert(Name(domain_names[i]), &rbtnode);
@@ -79,7 +79,7 @@ protected:
 
 
 TEST_F(RBTreeTest, getNodeCount) {
-    EXPECT_EQ(13, rbtree.getNodeCount());
+    EXPECT_EQ(14, rbtree.getNodeCount());
 }
 
 TEST_F(RBTreeTest, setGetData) {
@@ -91,46 +91,46 @@ TEST_F(RBTreeTest, insertNames) {
     EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("d.e.f"),
                                                         &rbtnode));
     EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
-    EXPECT_EQ(13, rbtree.getNodeCount());
+    EXPECT_EQ(14, rbtree.getNodeCount());
 
     //insert not exist node
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("."), &rbtnode));
     EXPECT_EQ(Name("."), rbtnode->getName());
-    EXPECT_EQ(14, rbtree.getNodeCount());
+    EXPECT_EQ(15, rbtree.getNodeCount());
 
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("example.com"), &rbtnode));
-    EXPECT_EQ(15, rbtree.getNodeCount());
+    EXPECT_EQ(16, rbtree.getNodeCount());
     rbtnode->setData(RBNode<int>::NodeDataPtr(new int(12)));
 
     // return ALREADYEXISTS, since node "example.com" already has been explicitly inserted
     EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("example.com"), &rbtnode));
-    EXPECT_EQ(15, rbtree.getNodeCount());
+    EXPECT_EQ(16, rbtree.getNodeCount());
 
     // split the node "d.e.f"
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("k.e.f"), &rbtnode));
     EXPECT_EQ(Name("k"), rbtnode->getName());
-    EXPECT_EQ(17, rbtree.getNodeCount());
+    EXPECT_EQ(18, rbtree.getNodeCount());
 
     // split the node "g.h"
     EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("h"), &rbtnode));
     EXPECT_EQ(Name("h"), rbtnode->getName());
-    EXPECT_EQ(18, rbtree.getNodeCount());
+    EXPECT_EQ(19, rbtree.getNodeCount());
 
     // add child domain
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("m.p.w.y.d.e.f"), &rbtnode));
     EXPECT_EQ(Name("m"), rbtnode->getName());
-    EXPECT_EQ(19, rbtree.getNodeCount());
+    EXPECT_EQ(20, rbtree.getNodeCount());
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("n.p.w.y.d.e.f"), &rbtnode));
     EXPECT_EQ(Name("n"), rbtnode->getName());
-    EXPECT_EQ(20, rbtree.getNodeCount());
+    EXPECT_EQ(21, rbtree.getNodeCount());
 
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("l.a"), &rbtnode));
     EXPECT_EQ(Name("l"), rbtnode->getName());
-    EXPECT_EQ(21, rbtree.getNodeCount());
+    EXPECT_EQ(22, rbtree.getNodeCount());
 
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("r.d.e.f"), &rbtnode));
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("s.d.e.f"), &rbtnode));
-    EXPECT_EQ(23, rbtree.getNodeCount());
+    EXPECT_EQ(24, rbtree.getNodeCount());
 
     EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("h.w.y.d.e.f"), &rbtnode));
 
@@ -323,7 +323,7 @@ TEST_F(RBTreeTest, getAbsoluteNameError) {
 /*
  *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
+ * z.d.e.f, j.z.d.e.f, g.h, i.g.h, k.g.h
  *             b
  *           /   \
  *          a    d.e.f
@@ -331,8 +331,8 @@ TEST_F(RBTreeTest, getAbsoluteNameError) {
  *             c   |    g.h
  *                 |     |
  *                w.y    i
- *              /  |  \
- *             x   |   z
+ *              /  |  \   \
+ *             x   |   z   k
  *                 |   |
  *                 p   j
  *               /   \
@@ -340,14 +340,11 @@ TEST_F(RBTreeTest, getAbsoluteNameError) {
  */
 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"};
+    "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", "k.g.h"};
 const size_t name_count(sizeof(names) / sizeof(*names));
 
 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,
@@ -405,6 +402,11 @@ previousWalk(RBTree<int>& rbtree, const RBNode<int>* node,
 
     // We should have reached the start of the tree.
     EXPECT_EQ(static_cast<void*>(NULL), node);
+
+    // Calling previousNode() yet again should still return NULL without
+    // fail.
+    node = rbtree.previousNode(node_path);
+    EXPECT_EQ(static_cast<void*>(NULL), node);
 }
 
 // Check the previousNode
@@ -506,6 +508,28 @@ TEST_F(RBTreeTest, previousNode) {
     }
 
     {
+        SCOPED_TRACE("Start to the right of a parent");
+        // When searching for this, we exit the 'g.h' node to the right
+        // side, so we should go to g.h's children afterwards.
+
+        // 'g.h' is an empty node, so we get a NOTFOUND and not
+        // PARTIALMATCH.
+        EXPECT_EQ(RBTree<int>::NOTFOUND,
+                  rbtree.find(Name("x.h"), &node, node_path));
+        // 'g.h' is the COMMONANCESTOR.
+        EXPECT_EQ(node_path.getLastComparedNode()->getName(), Name("g.h"));
+        EXPECT_EQ(NameComparisonResult::COMMONANCESTOR,
+                  node_path.getLastComparisonResult().getRelation());
+        // find() exits to the right of 'g.h'
+        EXPECT_GT(node_path.getLastComparisonResult().getOrder(), 0);
+        // We then descend into 'i.g.h' and walk all the nodes in the
+        // tree.
+        previousWalk(rbtree, node, node_path, name_count, true);
+        node = NULL;
+        node_path.clear();
+    }
+
+    {
         SCOPED_TRACE("Start inside a wrong node");
         // The d.e.f is a single node, but we want only part of it. We
         // should start iterating before it.
@@ -582,11 +606,11 @@ TEST_F(RBTreeTest, getLastComparedNode) {
     // Partial match, search stopped at the matching node, which should be
     // the last compared node.
     EXPECT_EQ(RBTree<int>::EXACTMATCH,
-              tree.find(Name("i.g.h"), &expected_node));
+              tree.find(Name("k.g.h"), &expected_node));
     EXPECT_EQ(RBTree<int>::PARTIALMATCH,
-              tree.find(Name("x.i.g.h"), &crbtnode, chain));
+              tree.find(Name("x.k.g.h"), &crbtnode, chain));
     EXPECT_EQ(expected_node, chain.getLastComparedNode());
-    // i.g.h < x.i.g.h, 2 = # labels of "i."
+    // k.g.h < x.k.g.h, 2 = # labels of "k."
     comparisonChecks(chain, 1, 2, NameComparisonResult::SUBDOMAIN);
     chain.clear();
 
@@ -656,7 +680,7 @@ TEST_F(RBTreeTest, dumpTree) {
     std::ostringstream str;
     std::ostringstream str2;
     rbtree.dumpTree(str);
-    str2 << "tree has 13 node(s)\nb. (black)\n     a. (black)\n          NULL\n          NULL\n     d.e.f. (black)[invisible] \n          begin down from d.e.f.\n          w.y. (black)[invisible] \n               begin down from w.y.\n               p. (black)\n                    o. (red)\n                         NULL\n                         NULL\n                    q. (red)\n                         NULL\n                         NULL\n               end down from w.y.\n               x. (red)\n                    NULL\n                    NULL\n               z. (red)\n                    begin down from z.\n                    j. (black)\n                         NULL\n                         NULL\n                    end down from z.\n                    NULL\n                    NULL\n          end down from d.e.f.\n          c. (red)\n               NULL\n               NULL\n          g.h. (red)\n               begin down from g.h.\n               i. (black)\n  
                   NULL\n                    NULL\n               end down from g.h.\n               NULL\n               NULL\n";
+    str2 << "tree has 14 node(s)\nb. (black)\n     a. (black)\n          NULL\n          NULL\n     d.e.f. (black)[invisible] \n          begin down from d.e.f.\n          w.y. (black)[invisible] \n               begin down from w.y.\n               p. (black)\n                    o. (red)\n                         NULL\n                         NULL\n                    q. (red)\n                         NULL\n                         NULL\n               end down from w.y.\n               x. (red)\n                    NULL\n                    NULL\n               z. (red)\n                    begin down from z.\n                    j. (black)\n                         NULL\n                         NULL\n                    end down from z.\n                    NULL\n                    NULL\n          end down from d.e.f.\n          c. (red)\n               NULL\n               NULL\n          g.h. (red)\n               begin down from g.h.\n               i. (black)\n  
                   NULL\n                    k. (red)\n                         NULL\n                         NULL\n               end down from g.h.\n               NULL\n               NULL\n";
     EXPECT_EQ(str.str(), str2.str());
 }
 



More information about the bind10-changes mailing list