BIND 10 trac2750, updated. 9b06e690a16a338fc943fd039d6cee03e5c9ca45 [2750] Add non-const variant of largestNode()
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Aug 26 02:10:28 UTC 2013
The branch, trac2750 has been updated
via 9b06e690a16a338fc943fd039d6cee03e5c9ca45 (commit)
via 0b3041d1b0191e610a5ed3f8b4e93e846823041c (commit)
via 36db9cbd518e50baabd62f645965d656c3cd7531 (commit)
via 4d4b0dcd1dc2571a98b4e60bf846dd704ed7200d (commit)
via 004adb24a8aac2527b2729aee398717b5ff505cd (commit)
via 8ee0490dae879424b7e20fe1994ae4f2b294e3ef (commit)
from e40e2e96bee958e49a7bb389435add5d980419f5 (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 9b06e690a16a338fc943fd039d6cee03e5c9ca45
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 26 07:37:40 2013 +0530
[2750] Add non-const variant of largestNode()
commit 0b3041d1b0191e610a5ed3f8b4e93e846823041c
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 26 07:20:57 2013 +0530
[2750] Add non-const variants of successor() and predecessor()
commit 36db9cbd518e50baabd62f645965d656c3cd7531
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 26 07:17:20 2013 +0530
[2750] Remove redundant variable
commit 4d4b0dcd1dc2571a98b4e60bf846dd704ed7200d
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 26 07:16:00 2013 +0530
[2750] Add non-const variant of abstractSuccessor()
commit 004adb24a8aac2527b2729aee398717b5ff505cd
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 26 07:04:00 2013 +0530
[2750] Add non-const variant of getUpperNode()
commit 8ee0490dae879424b7e20fe1994ae4f2b294e3ef
Author: Mukund Sivaraman <muks at isc.org>
Date: Mon Aug 26 06:55:58 2013 +0530
[2750] Add non-const variant of getSubTreeRoot()
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 172 +++++++++++++++++++++++++++++------
1 file changed, 145 insertions(+), 27 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 5f41371..ffba88c 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -393,11 +393,20 @@ private:
return ((flags_ & FLAG_SUBTREE_ROOT) != 0);
}
+ /// \brief Static helper function used by const and non-const
+ /// variants of getSubTreeRoot()
+ template <typename TT>
+ static TT*
+ getSubTreeRootImpl(TT* node);
+
/// \brief returns the root of its subtree
///
/// This method takes a node and returns the root of its subtree.
///
/// This method never throws an exception.
+ DomainTreeNode<T>* getSubTreeRoot();
+
+ /// \brief returns the root of its subtree (const variant)
const DomainTreeNode<T>* getSubTreeRoot() const;
public:
@@ -409,6 +418,10 @@ public:
/// (which should be absolute), it will return \c NULL.
///
/// This method never throws an exception.
+ DomainTreeNode<T>* getUpperNode();
+
+ /// \brief returns the parent of the root of its subtree (const
+ /// variant)
const DomainTreeNode<T>* getUpperNode() const;
/// \brief return the next node which is bigger than current node
@@ -426,6 +439,10 @@ public:
/// returns \c NULL.
///
/// This method never throws an exception.
+ DomainTreeNode<T>* successor();
+
+ /// \brief return the next node which is bigger than current node
+ /// in the same subtree (const variant)
const DomainTreeNode<T>* successor() const;
/// \brief return the next node which is smaller than current node
@@ -443,6 +460,10 @@ public:
/// returns \c NULL.
///
/// This method never throws an exception.
+ DomainTreeNode<T>* predecessor();
+
+ /// \brief return the next node which is smaller than current node
+ /// in the same subtree (const variant)
const DomainTreeNode<T>* predecessor() const;
/// \brief returns the node distance from the root of its subtree
@@ -461,6 +482,16 @@ public:
}
private:
+ /// \brief Static helper function used by const and non-const
+ /// variants of abstractSuccessor()
+ template <typename TT>
+ static TT*
+ abstractSuccessorImpl(TT* node,
+ typename DomainTreeNode<T>::DomainTreeNodePtr
+ DomainTreeNode<T>::*left,
+ typename DomainTreeNode<T>::DomainTreeNodePtr
+ DomainTreeNode<T>::*right);
+
/// \brief private shared implementation of successor and predecessor
///
/// As the two mentioned functions are merely mirror images of each other,
@@ -472,10 +503,18 @@ private:
/// The overhead of the member pointers should be optimised out, as this
/// will probably get completely inlined into predecessor and successor
/// methods.
+ DomainTreeNode<T>*
+ abstractSuccessor(typename DomainTreeNode<T>::DomainTreeNodePtr
+ DomainTreeNode<T>::*left,
+ typename DomainTreeNode<T>::DomainTreeNodePtr
+ DomainTreeNode<T>::*right);
+
+ /// \brief private shared implementation of successor and
+ /// predecessor (const variant)
const DomainTreeNode<T>*
- abstractSuccessor(typename DomainTreeNode<T>::DomainTreeNodePtr
+ abstractSuccessor(typename DomainTreeNode<T>::DomainTreeNodePtr
DomainTreeNode<T>::*left,
- typename DomainTreeNode<T>::DomainTreeNodePtr
+ typename DomainTreeNode<T>::DomainTreeNodePtr
DomainTreeNode<T>::*right)
const;
@@ -610,17 +649,36 @@ DomainTreeNode<T>::~DomainTreeNode() {
}
template <typename T>
-const DomainTreeNode<T>*
-DomainTreeNode<T>::getSubTreeRoot() const {
- const DomainTreeNode<T>* current = this;
-
- // current would never be equal to NULL here (in a correct tree
+template <typename TT>
+TT*
+DomainTreeNode<T>::getSubTreeRootImpl(TT* node) {
+ // node would never be equal to NULL here (in a correct tree
// implementation)
- while (!current->isSubTreeRoot()) {
- current = current->getParent();
+ assert(node != NULL);
+
+ while (!node->isSubTreeRoot()) {
+ node = node->getParent();
}
- return (current);
+ return (node);
+}
+
+template <typename T>
+DomainTreeNode<T>*
+DomainTreeNode<T>::getSubTreeRoot() {
+ return (getSubTreeRootImpl<DomainTreeNode<T> >(this));
+}
+
+template <typename T>
+const DomainTreeNode<T>*
+DomainTreeNode<T>::getSubTreeRoot() const {
+ return (getSubTreeRootImpl<const DomainTreeNode<T> >(this));
+}
+
+template <typename T>
+DomainTreeNode<T>*
+DomainTreeNode<T>::getUpperNode() {
+ return (getSubTreeRoot()->getParent());
}
template <typename T>
@@ -655,40 +713,39 @@ DomainTreeNode<T>::getAbsoluteLabels(
}
template <typename T>
-const DomainTreeNode<T>*
-DomainTreeNode<T>::abstractSuccessor(
+template <typename TT>
+TT*
+DomainTreeNode<T>::abstractSuccessorImpl(TT* node,
typename DomainTreeNode<T>::DomainTreeNodePtr DomainTreeNode<T>::*left,
typename DomainTreeNode<T>::DomainTreeNodePtr DomainTreeNode<T>::*right)
- const
{
// This function is written as a successor. It becomes predecessor if
// the left and right pointers are swapped. So in case of predecessor,
// the left pointer points to right and vice versa. Don't get confused
// by the idea, just imagine the pointers look into a mirror.
- const DomainTreeNode<T>* current = this;
// If it has right node, the successor is the left-most node of the right
// subtree.
- if ((current->*right).get() != NULL) {
- current = (current->*right).get();
+ if ((node->*right).get() != NULL) {
+ node = (node->*right).get();
const DomainTreeNode<T>* left_n;
- while ((left_n = (current->*left).get()) != NULL) {
- current = left_n;
+ while ((left_n = (node->*left).get()) != NULL) {
+ node = left_n;
}
- return (current);
+ return (node);
}
// 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 DomainTreeNode<T>* parent = current->getParent();
- while ((!current->isSubTreeRoot()) &&
- (current == (parent->*right).get())) {
- current = parent;
+ const DomainTreeNode<T>* parent = node->getParent();
+ while ((!node->isSubTreeRoot()) &&
+ (node == (parent->*right).get())) {
+ node = parent;
parent = parent->getParent();
}
- if (!current->isSubTreeRoot()) {
+ if (!node->isSubTreeRoot()) {
return (parent);
} else {
return (NULL);
@@ -696,6 +753,33 @@ DomainTreeNode<T>::abstractSuccessor(
}
template <typename T>
+DomainTreeNode<T>*
+DomainTreeNode<T>::abstractSuccessor(
+ typename DomainTreeNode<T>::DomainTreeNodePtr DomainTreeNode<T>::*left,
+ typename DomainTreeNode<T>::DomainTreeNodePtr DomainTreeNode<T>::*right)
+{
+ return (abstractSuccessorImpl<DomainTreeNode<T> >(this, left, right));
+}
+
+template <typename T>
+const DomainTreeNode<T>*
+DomainTreeNode<T>::abstractSuccessor(
+ typename DomainTreeNode<T>::DomainTreeNodePtr DomainTreeNode<T>::*left,
+ typename DomainTreeNode<T>::DomainTreeNodePtr DomainTreeNode<T>::*right)
+ const
+{
+ return (abstractSuccessorImpl<const DomainTreeNode<T> >
+ (this, left, right));
+}
+
+template <typename T>
+DomainTreeNode<T>*
+DomainTreeNode<T>::successor() {
+ return (abstractSuccessor(&DomainTreeNode<T>::left_,
+ &DomainTreeNode<T>::right_));
+}
+
+template <typename T>
const DomainTreeNode<T>*
DomainTreeNode<T>::successor() const {
return (abstractSuccessor(&DomainTreeNode<T>::left_,
@@ -703,6 +787,14 @@ DomainTreeNode<T>::successor() const {
}
template <typename T>
+DomainTreeNode<T>*
+DomainTreeNode<T>::predecessor() {
+ // Swap the left and right pointers for the abstractSuccessor
+ return (abstractSuccessor(&DomainTreeNode<T>::right_,
+ &DomainTreeNode<T>::left_));
+}
+
+template <typename T>
const DomainTreeNode<T>*
DomainTreeNode<T>::predecessor() const {
// Swap the left and right pointers for the abstractSuccessor
@@ -1320,12 +1412,24 @@ public:
const DomainTreeNode<T>*
previousNode(DomainTreeNodeChain<T>& node_path) const;
+private:
+ /// \brief Static helper function used by const and non-const
+ /// variants of largestNode()
+ template <typename TT, typename TTN>
+ static TTN*
+ largestNodeImpl(TT* node);
+
+public:
/// \brief return the largest node in the tree of trees.
///
/// \throw none
///
/// \return A \c DomainTreeNode that is the largest node in the
/// tree. If there are no nodes, then \c NULL is returned.
+ DomainTreeNode<T>* largestNode();
+
+ /// \brief return the largest node in the tree of trees (const
+ /// variant).
const DomainTreeNode<T>* largestNode() const;
/// \brief Get the total number of nodes in the tree
@@ -1789,9 +1893,10 @@ DomainTree<T>::previousNode(DomainTreeNodeChain<T>& node_path) const {
}
template <typename T>
-const DomainTreeNode<T>*
-DomainTree<T>::largestNode() const {
- const DomainTreeNode<T>* node = root_.get();
+template <typename TT, typename TTN>
+TTN*
+DomainTree<T>::largestNodeImpl(TT* tree) {
+ TTN* node = tree->root_.get();
while (node != NULL) {
// We go right first, then down.
if (node->getRight() != NULL) {
@@ -1807,6 +1912,19 @@ DomainTree<T>::largestNode() const {
}
template <typename T>
+DomainTreeNode<T>*
+DomainTree<T>::largestNode() {
+ return (largestNodeImpl<DomainTree<T>, DomainTreeNode<T> >(this));
+}
+
+template <typename T>
+const DomainTreeNode<T>*
+DomainTree<T>::largestNode() const {
+ return (largestNodeImpl<const DomainTree<T>, const DomainTreeNode<T> >
+ (this));
+}
+
+template <typename T>
typename DomainTree<T>::Result
DomainTree<T>::insert(util::MemorySegment& mem_sgmt,
const isc::dns::Name& target_name,
More information about the bind10-changes
mailing list