[2089] store subtreerootness in node flags

2 files changed, 37 insertions, 7 deletions

diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index b08accf156..a78a399f34 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -124,6 +124,7 @@ public:
     enum Flags {
         FLAG_CALLBACK = 1, ///< Callback enabled. See \ref callback
         FLAG_RED = 2, ///< Node color; 1 if node is red, 0 if node is black.
+        FLAG_SUBTREE_ROOT = 4, ///< Set if the node is the root of a subtree
         FLAG_USER1 = 0x80000000U, ///< Application specific flag
         FLAG_USER2 = 0x40000000U, ///< Application specific flag
         FLAG_USER3 = 0x20000000U  ///< Application specific flag
@@ -265,8 +266,16 @@ private:
         }
     }
 
+    void setSubTreeRoot(bool root) {
+        if (root) {
+            flags_ |= FLAG_SUBTREE_ROOT;
+        } else {
+            flags_ &= ~FLAG_SUBTREE_ROOT;
+        }
+    }
+
     bool isSubTreeRoot() const {
-        return (parent_ == NULL_NODE());
+        return ((flags_ & FLAG_SUBTREE_ROOT) != 0);
     }
 
     /// \brief return the next node which is bigger than current node
@@ -357,7 +366,7 @@ RBNode<T>::RBNode() :
     // dummy name, the value doesn't matter:
     name_(isc::dns::Name::ROOT_NAME()),
     down_(NULL),
-    flags_(0)
+    flags_(FLAG_SUBTREE_ROOT)
 {
     // Some compilers object to use of "this" in initializer lists.
     parent_ = this;
@@ -373,7 +382,7 @@ RBNode<T>::RBNode(const isc::dns::Name& name) :
     right_(NULL_NODE()),
     name_(name),
     down_(NULL_NODE()),
-    flags_(FLAG_RED)
+    flags_(FLAG_RED | FLAG_SUBTREE_ROOT)
 {
 }
 
@@ -1395,9 +1404,12 @@ RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
         //node is the new root of sub tree, so its init color
         // is BLACK
         node->setColor(RBNode<T>::BLACK);
+        node->setSubTreeRoot(true);
     } else if (order < 0) {
+        node->setSubTreeRoot(false);
         parent->left_ = node.get();
     } else {
+        node->setSubTreeRoot(false);
         parent->right_ = node.get();
     }
     insertRebalance(current_root, node.get());
@@ -1438,6 +1450,10 @@ RBTree<T>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
 
     // root node of sub tree, the initial color is BLACK
     down_node->setColor(RBNode<T>::BLACK);
+
+    // mark it as the root of a subtree
+    down_node->setSubTreeRoot(true);
+
     ++node_count_;
     down_node.release();
 }
@@ -1494,23 +1510,30 @@ RBNode<T>*
 RBTree<T>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
     RBNode<T>* right = node->right_;
     node->right_ = right->left_;
-    if (right->left_ != NULLNODE)
+    if (right->left_ != NULLNODE) {
         right->left_->parent_ = node;
+        right->left_->setSubTreeRoot(false);
+    } else {
+        right->left_->setSubTreeRoot(true);
+    }
 
     right->parent_ = node->parent_;
 
     if (node->parent_ != NULLNODE) {
+        right->setSubTreeRoot(false);
         if (node == node->parent_->left_) {
             node->parent_->left_ = right;
         } else  {
             node->parent_->right_ = right;
         }
     } else {
+        right->setSubTreeRoot(true);
         *root = right;
     }
 
     right->left_ = node;
     node->parent_ = right;
+    node->setSubTreeRoot(false);
     return (node);
 }
 
@@ -1519,22 +1542,30 @@ RBNode<T>*
 RBTree<T>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
     RBNode<T>* left = node->left_;
     node->left_ = left->right_;
-    if (left->right_ != NULLNODE)
+    if (left->right_ != NULLNODE) {
         left->right_->parent_ = node;
+        left->right_->setSubTreeRoot(false);
+    } else {
+        left->right_->setSubTreeRoot(true);
+    }
 
     left->parent_ = node->parent_;
 
     if (node->parent_ != NULLNODE) {
+        left->setSubTreeRoot(false);
         if (node == node->parent_->right_) {
             node->parent_->right_ = left;
         } else  {
             node->parent_->left_ = left;
         }
     } else {
+        left->setSubTreeRoot(true);
         *root = left;
     }
     left->right_ = node;
     node->parent_ = left;
+    node->setSubTreeRoot(false);
+
     return (node);
 }
 
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index cfde248838..b6d9985d95 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -77,7 +77,6 @@ protected:
     const RBNode<int>* crbtnode;
 };
 
-
 TEST_F(RBTreeTest, getNodeCount) {
     EXPECT_EQ(14, rbtree.getNodeCount());
 }
@@ -722,7 +721,7 @@ TEST_F(RBTreeTest, dumpTree) {
             "               end down from g.h.\n" <<
             "               NULL\n" <<
             "               NULL\n";
-    EXPECT_EQ(str.str(), str2.str());
+    EXPECT_EQ(str2.str(), str.str());
 }
 
 TEST_F(RBTreeTest, swap) {