BIND 10 master, updated. d3dbe8e1643358d4f88cdbb7a16a32fd384b85b1 Merge branch 'trac2750'
BIND 10 source code commits
bind10-changes at lists.isc.org
Tue Oct 1 11:18:48 UTC 2013
The branch, master has been updated
via d3dbe8e1643358d4f88cdbb7a16a32fd384b85b1 (commit)
via 08bc7db55cafdd916ae227ff7ca524542de280f4 (commit)
via a0aaef8644a889594af32cd5a3898a63a225b7cb (commit)
via bd9f2d3c9e45d945b8e6ad9db79f93954ee0dcf9 (commit)
via 52d44bc5004ae501ca039896db099b734781f00b (commit)
via 339f201e9a6c58980f8cc9e6577e80254f04e951 (commit)
via 8b88f186238c9dc920a3a4dac668c8e5bf68927b (commit)
via b1e65b902324572544555903b45bc63ffcefcd2b (commit)
via c5c85a0d56fc30c9c0fc3b7040306360c961350b (commit)
via d79db92249d8e529bd8346cffbaf5c19680923f5 (commit)
via 3984b23014333a678d3c78f8253312bede64a213 (commit)
via 0edf1c3dd2e12a28ecb74e47bdc969d6dc15fcd4 (commit)
via 9eeab2e6b02fcf316b81bcc72c0dadef84b9a07d (commit)
via 63a7f8bf4e61b69fd29a189f9bc683b5de0ce57b (commit)
via 8090d2c5186a96d80378072761625da2d8d421b0 (commit)
via 05b3886971fb003b0bbd735975bbbf0c38a1970c (commit)
via 151a2b857e77b32b10c007e9a37f37ddcfb03b8b (commit)
via a47c17e54da2b08afb9dae8f46a97ac3a5e5bda0 (commit)
via a50e4235990f2b1b7090092e5fb19c7662480dd3 (commit)
via 663bc38be6ba6371ac5d2c0e4e2db845fd384037 (commit)
via 49c71998445264c8882c3b8389edd4bbd74c22f1 (commit)
via 0a5bd2ebb43c45ebab9f466d102a3c9e4c024efa (commit)
via 8380acd2fcbd511f0a72f1854e19baa874e34175 (commit)
via c0e91c529e7e110f68c30c127a8370643a1a9b78 (commit)
via b30ae178084dbfda0da6ccfee9f8d1e27c926b0d (commit)
via e2cb0a39c9819482df8e7cd32ba37ed405d715fd (commit)
via 63e54b17e5b43ee480cb83a4fa0fa6ba08e2ccfa (commit)
via da0e9a81e8a4e4fac77caf257607bf4fe1bb0f0d (commit)
via b403553a567421006bccbf4b4f598b7aca738d54 (commit)
via 49fa0bad8fa7bcc0355acadede93b9f3ce679f14 (commit)
via 7cf392993b65c0b69443f1e749ae067c3d6f142c (commit)
via 0467d75d487b5c7d559ccf9a73e9fe105cd485cd (commit)
via 6024678d9b397613cf8f9b5454b14f9b98e1b176 (commit)
via 967e79e9748de98d874df011184c03bf27c5e8dd (commit)
via ec1cb0b7b54e161404079ca63124aa85d1553104 (commit)
via 1d38fe32f5f891958d302b46044cd961a074ec41 (commit)
via 4ee1f3305b8704b7c5da130e163285bbfcbf36d7 (commit)
via d15a492eb3479310af51cb1a9dde60faa1d57249 (commit)
via 313c564232efbcfc2cc8d34593ce9494ba96d629 (commit)
via 8a4c8c4fec6d869d9ecbbbab9c0374658cfd7a99 (commit)
via 091b8584615ed5da2441c579bc37cf1e9681db80 (commit)
via 2a07912bb6cb95f4df5caffdc6df4b07219b5dc3 (commit)
via 275d63283fe322e93ede93045b6ad870a6eaac68 (commit)
via 23078e9f9718a8dd92180f15a419ef2db1e4c69b (commit)
via 73d7a9538986f78b96584f5f9ce4946f86f05536 (commit)
via 927411d1d221265f82608e62a22683c203103209 (commit)
via b6ca9a816726b573004d1a9140ad38522bec50f8 (commit)
via 4798d92c50c4b6ec09931646f1ba823882b268d2 (commit)
via 8829d940017a15fc738f2ebf6dfb3c8da61c54cc (commit)
via bf298463e636da9989a877145fee8853733f7030 (commit)
via 8a6e0a611829250157c74d6fe8a329629d66b537 (commit)
via 65d3cd24fbee716e9e331a9f4541e34341e5e15b (commit)
via 82fded3b3266bfe0c30dc89572b716898b5aaf8e (commit)
via 4d5859d8e390631a868339c2d435916e75112674 (commit)
via 99b2d6f764a574071486cadf72e4eee3d3054ced (commit)
via 31e8258bbee3b576531a1fcf762c3a1f61e27785 (commit)
via 1d32d636d7f81e1a5385a9107fb7da355aa26c08 (commit)
via b27c26f22c147e9bfe4eaf411ce2247f5a5218e9 (commit)
via 9801de556f82d5c6156d120a2d70a23487524044 (commit)
via a2bc0e20d045d1009438c4c1565689931d66b213 (commit)
via 8bda455d6c105e505ed0d11223c708e2bd3b6f7a (commit)
via 6be8194bd8c4dc90dc0b702ba1450e59184689a5 (commit)
via 038082d3a8df1904538a11a6b803bec1804f9c8b (commit)
via 918419085f722e43c567d4498e6ca581d925ce26 (commit)
via 7b722a23d6a85ad0c3d903323e9a36ea2baefa0a (commit)
via 730aac841ed98bd35582d0a7c39a9b00835016a1 (commit)
via 5ffd53da7b10bec4ade51ef974a9b9a23e1a0085 (commit)
via 702505336da1317a8cfeeb5a04e8c5d1ac439469 (commit)
via 7f0bb9294f71b325836f3c4fd8989b382627c19a (commit)
via c369c2c9a3bcb252843bd25680627484486b8802 (commit)
via 3674f8287a482a77b9bc2f8a0f161ce2dc4e3f9f (commit)
via 79c66d327a479ff5d6dca45c17e438a404bc9dec (commit)
via 9b06e690a16a338fc943fd039d6cee03e5c9ca45 (commit)
via 0b3041d1b0191e610a5ed3f8b4e93e846823041c (commit)
via 36db9cbd518e50baabd62f645965d656c3cd7531 (commit)
via 4d4b0dcd1dc2571a98b4e60bf846dd704ed7200d (commit)
via 004adb24a8aac2527b2729aee398717b5ff505cd (commit)
via 8ee0490dae879424b7e20fe1994ae4f2b294e3ef (commit)
from 6f1227c27cded2a283ea3ec78e7497a825fdc005 (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 d3dbe8e1643358d4f88cdbb7a16a32fd384b85b1
Merge: 6f1227c 08bc7db
Author: Mukund Sivaraman <muks at isc.org>
Date: Tue Oct 1 16:36:50 2013 +0530
Merge branch 'trac2750'
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/domaintree.h | 1045 ++++++++++++++++++--
.../datasrc/tests/memory/domaintree_unittest.cc | 504 ++++++++--
2 files changed, 1356 insertions(+), 193 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
index 5f41371..05d9795 100644
--- a/src/lib/datasrc/memory/domaintree.h
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -361,11 +361,26 @@ private:
return (getColor() == BLACK);
}
+ /// \brief Static variant of isBlack() that also allows NULL nodes.
+ static bool isBlack(const DomainTreeNode<T>* node) {
+ if (!node) {
+ // NULL nodes are black.
+ return (true);
+ }
+
+ return (node->isBlack());
+ }
+
/// \brief Returns if the node color is red
bool isRed() const {
return (!isBlack());
}
+ /// \brief Static variant of isRed() that also allows NULL nodes.
+ static bool isRed(const DomainTreeNode<T>* node) {
+ return (!isBlack(node));
+ }
+
/// \brief Sets the color of this node
void setColor(const DomainTreeNodeColor color) {
if (color == RED) {
@@ -393,11 +408,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 +433,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 +454,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 +475,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
@@ -472,12 +508,13 @@ private:
/// The overhead of the member pointers should be optimised out, as this
/// will probably get completely inlined into predecessor and successor
/// methods.
- const DomainTreeNode<T>*
- abstractSuccessor(typename DomainTreeNode<T>::DomainTreeNodePtr
+ template <typename TT>
+ static TT*
+ abstractSuccessor(TT* node,
+ typename DomainTreeNode<T>::DomainTreeNodePtr
DomainTreeNode<T>::*left,
- typename DomainTreeNode<T>::DomainTreeNodePtr
- DomainTreeNode<T>::*right)
- const;
+ typename DomainTreeNode<T>::DomainTreeNodePtr
+ DomainTreeNode<T>::*right);
/// \name Data to maintain the rbtree structure.
///
@@ -530,6 +567,24 @@ private:
}
}
+ /// \brief Access sibling node as bare pointer.
+ ///
+ /// A sibling node is defined as the parent's other child. It exists
+ /// at the same level as child. Note that child can be NULL here,
+ /// which is why this is a static function.
+ ///
+ /// \return the sibling node if one exists, NULL otherwise.
+ static DomainTreeNode<T>* getSibling(DomainTreeNode<T>* parent,
+ DomainTreeNode<T>* child)
+ {
+ if (!parent) {
+ return (NULL);
+ }
+
+ return ((parent->getLeft() == child) ?
+ parent->getRight() : parent->getLeft());
+ }
+
/// \brief Access uncle node as bare pointer.
///
/// An uncle node is defined as the parent node's sibling. It exists
@@ -570,6 +625,96 @@ private:
return (down_.get());
}
+ /// \brief Helper method used in many places in code to set parent's
+ /// child links.
+ void connectChild(DomainTreeNode<T>* oldnode,
+ DomainTreeNode<T>* newnode,
+ DomainTreeNodePtr* root_ptr,
+ DomainTreeNode<T>* thisnode = NULL)
+ {
+ if (!thisnode) {
+ thisnode = this;
+ }
+
+ if (getParent() != NULL) {
+ if (getParent()->getLeft() == oldnode) {
+ thisnode->getParent()->left_ = newnode;
+ } else if (getParent()->getRight() == oldnode) {
+ thisnode->getParent()->right_ = newnode;
+ } else {
+ thisnode->getParent()->down_ = newnode;
+ }
+ } else {
+ *root_ptr = newnode;
+ }
+ }
+
+ /// \brief Exchanges the location of two nodes (this and
+ /// lower). Their data remain the same, but their location in the
+ /// tree, colors and sub-tree root status may change. Note that this
+ /// is different from std::swap()-like behavior.
+ ///
+ /// IMPORTANT: A necessary pre-condition is that lower node must be
+ /// at a lower level in the tree than this node. This method is
+ /// primarily used in remove() and this pre-condition is followed
+ /// there.
+ ///
+ /// This method doesn't throw any exceptions.
+ void exchange(DomainTreeNode<T>* lower, DomainTreeNodePtr* root_ptr) {
+ // Swap the pointers first. down should not be swapped as it
+ // belongs to the node's data, and not to its position in the
+ // tree.
+
+ // NOTE: The conditions following the swaps below are
+ // asymmetric. We only need to check this for the lower node, as
+ // it can be a direct child of this node. The reverse is not
+ // possible.
+
+ std::swap(left_, lower->left_);
+ if (lower->getLeft() == lower) {
+ lower->left_ = this;
+ }
+
+ std::swap(right_, lower->right_);
+ if (lower->getRight() == lower) {
+ lower->right_ = this;
+ }
+
+ std::swap(parent_, lower->parent_);
+ if (getParent() == this) {
+ parent_ = lower;
+ }
+
+ // Update FLAG_RED and FLAG_SUBTREE_ROOT as these two are
+ // associated with the node's position.
+ const DomainTreeNodeColor this_color = getColor();
+ const bool this_is_subtree_root = isSubTreeRoot();
+ const DomainTreeNodeColor lower_color = lower->getColor();
+ const bool lower_is_subtree_root = lower->isSubTreeRoot();
+
+ lower->setColor(this_color);
+ setColor(lower_color);
+
+ setSubTreeRoot(lower_is_subtree_root);
+ lower->setSubTreeRoot(this_is_subtree_root);
+
+ lower->connectChild(this, lower, root_ptr);
+
+ if (getParent()->getLeft() == lower) {
+ getParent()->left_ = this;
+ } else if (getParent()->getRight() == lower) {
+ getParent()->right_ = this;
+ }
+
+ if (lower->getRight()) {
+ lower->getRight()->parent_ = lower;
+ }
+
+ if (lower->getLeft()) {
+ lower->getLeft()->parent_ = lower;
+ }
+ }
+
/// \brief Data stored here.
boost::interprocess::offset_ptr<T> data_;
@@ -610,17 +755,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 +819,39 @@ DomainTreeNode<T>::getAbsoluteLabels(
}
template <typename T>
-const DomainTreeNode<T>*
-DomainTreeNode<T>::abstractSuccessor(
+template <typename TT>
+TT*
+DomainTreeNode<T>::abstractSuccessor(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,18 +859,33 @@ DomainTreeNode<T>::abstractSuccessor(
}
template <typename T>
+DomainTreeNode<T>*
+DomainTreeNode<T>::successor() {
+ return (abstractSuccessor<DomainTreeNode<T> >
+ (this, &DomainTreeNode<T>::left_, &DomainTreeNode<T>::right_));
+}
+
+template <typename T>
const DomainTreeNode<T>*
DomainTreeNode<T>::successor() const {
- return (abstractSuccessor(&DomainTreeNode<T>::left_,
- &DomainTreeNode<T>::right_));
+ return (abstractSuccessor<const DomainTreeNode<T> >
+ (this, &DomainTreeNode<T>::left_, &DomainTreeNode<T>::right_));
+}
+
+template <typename T>
+DomainTreeNode<T>*
+DomainTreeNode<T>::predecessor() {
+ // Swap the left and right pointers for the abstractSuccessor
+ return (abstractSuccessor<DomainTreeNode<T> >
+ (this, &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
- return (abstractSuccessor(&DomainTreeNode<T>::right_,
- &DomainTreeNode<T>::left_));
+ return (abstractSuccessor<const DomainTreeNode<T> >
+ (this, &DomainTreeNode<T>::right_, &DomainTreeNode<T>::left_));
}
/// \brief DomainTreeNodeChain stores detailed information of \c
@@ -1072,7 +1250,7 @@ public:
DomainTree<T>* tree,
DataDeleter deleter)
{
- tree->deleteAllNodes(mem_sgmt, deleter);
+ tree->removeAllNodes(mem_sgmt, deleter);
tree->~DomainTree<T>();
mem_sgmt.deallocate(tree, sizeof(DomainTree<T>));
}
@@ -1148,45 +1326,19 @@ 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,
- const DomainTreeNode<T>** node) const {
- DomainTreeNodeChain<T> node_path;
- const isc::dns::LabelSequence ls(name);
- Result ret = (find<void*>(ls, node, node_path, NULL, NULL));
- return (ret);
- }
-
- /// \brief Simple find, with node_path tracking
- ///
- /// Acts as described in the \ref find section.
- Result find(const isc::dns::Name& name, const DomainTreeNode<T>** node,
- DomainTreeNodeChain<T>& node_path) const
- {
- const isc::dns::LabelSequence ls(name);
- Result ret = (find<void*>(ls, node, node_path, NULL, NULL));
- return (ret);
- }
-
- /// \brief Simple find returning immutable node.
- ///
- /// Acts as described in the \ref find section, but returns immutable
- /// node pointer.
- template <typename CBARG>
- Result find(const isc::dns::Name& name,
- const DomainTreeNode<T>** node,
- DomainTreeNodeChain<T>& node_path,
- bool (*callback)(const DomainTreeNode<T>&, CBARG),
- CBARG callback_arg) const
- {
- const isc::dns::LabelSequence ls(name);
- Result ret = find(ls, node, node_path, callback,
- callback_arg);
- return (ret);
- }
+private:
+ /// \brief Static helper function used by const and non-const
+ /// variants of find() below
+ template <typename TT, typename TTN, typename CBARG>
+ static Result findImpl(TT* tree,
+ const isc::dns::LabelSequence& target_labels_orig,
+ TTN** target,
+ TTN* node,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg);
+public:
/// \brief Find with callback and node chain
/// \anchor callback
///
@@ -1263,10 +1415,79 @@ public:
/// \c true, it returns immediately with the current node.
template <typename CBARG>
Result find(const isc::dns::LabelSequence& target_labels_orig,
+ DomainTreeNode<T>** node,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg);
+
+ /// \brief Find with callback and node chain (const variant)
+ template <typename CBARG>
+ Result find(const isc::dns::LabelSequence& target_labels_orig,
const DomainTreeNode<T>** node,
DomainTreeNodeChain<T>& node_path,
bool (*callback)(const DomainTreeNode<T>&, CBARG),
CBARG callback_arg) const;
+
+ /// \brief Simple find
+ ///
+ /// Acts as described in the \ref find section.
+ Result find(const isc::dns::Name& name,
+ DomainTreeNode<T>** node) {
+ const isc::dns::LabelSequence ls(name);
+ DomainTreeNodeChain<T> node_path;
+ return (find<void*>(ls, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Simple find (const variant)
+ Result find(const isc::dns::Name& name,
+ const DomainTreeNode<T>** node) const {
+ const isc::dns::LabelSequence ls(name);
+ DomainTreeNodeChain<T> node_path;
+ return (find<void*>(ls, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Simple find, with node_path tracking
+ ///
+ /// Acts as described in the \ref find section.
+ Result find(const isc::dns::Name& name, DomainTreeNode<T>** node,
+ DomainTreeNodeChain<T>& node_path)
+ {
+ const isc::dns::LabelSequence ls(name);
+ return (find<void*>(ls, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Simple find, with node_path tracking (const variant)
+ Result find(const isc::dns::Name& name, const DomainTreeNode<T>** node,
+ DomainTreeNodeChain<T>& node_path) const
+ {
+ const isc::dns::LabelSequence ls(name);
+ return (find<void*>(ls, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Simple find with callback
+ template <typename CBARG>
+ Result find(const isc::dns::Name& name,
+ DomainTreeNode<T>** node,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg)
+ {
+ const isc::dns::LabelSequence ls(name);
+ return (find<CBARG>(ls, node, node_path, callback, callback_arg));
+ }
+
+ /// \brief Simple find with callback (const variant)
+ template <typename CBARG>
+ Result find(const isc::dns::Name& name,
+ const DomainTreeNode<T>** node,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg) const
+ {
+ const isc::dns::LabelSequence ls(name);
+ return (find<CBARG>(ls, node, node_path, callback, callback_arg));
+ }
+
//@}
/// \brief return the next bigger node in DNSSEC order from a given node
@@ -1320,12 +1541,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
@@ -1335,6 +1568,39 @@ public:
/// This function is mainly intended to be used for debugging.
uint32_t getNodeCount() const { return (node_count_); }
+private:
+ /// \brief Helper method for getHeight()
+ size_t getHeightHelper(const DomainTreeNode<T>* node) const;
+
+public:
+ /// \brief Return the maximum height of sub-root nodes found in the
+ /// DomainTree forest.
+ ///
+ /// The height of a node is defined as the number of nodes in the
+ /// longest path from the node to a leaf. For each subtree in the
+ /// DomainTree forest, this method determines the height of its root
+ /// node. Then it returns the maximum such height in the forest.
+ ///
+ /// Note: This method exists for testing purposes. Non-test code
+ /// must not use it.
+ size_t getHeight() const;
+
+private:
+ /// \brief Helper method for checkProperties()
+ bool checkPropertiesHelper(const DomainTreeNode<T>* node) const;
+
+ /// \brief Helper for checkProperties()
+ bool checkBlackDistanceHelper(const DomainTreeNode<T>* node,
+ size_t* distance)
+ const;
+
+public:
+ /// \brief Check red-black properties of the DomainTree.
+ ///
+ /// Note: This method exists for testing purposes. Non-test code
+ /// must not use it.
+ bool checkProperties() const;
+
/// \name Debug function
//@{
/// \brief Print the nodes in the trees.
@@ -1402,15 +1668,31 @@ public:
Result insert(util::MemorySegment& mem_sgmt, const isc::dns::Name& name,
DomainTreeNode<T>** inserted_node);
+ /// \brief Delete a tree node.
+ ///
+ /// \throw none.
+ ///
+ /// \param mem_sgmt The \c MemorySegment object used to insert the nodes
+ /// (which was also used for creating the tree due to the requirement of
+ /// \c insert()).
+ /// \param node The node to delete.
+ /// \param deleter The \c DataDeleter used to destroy data stored in
+ /// the tree nodes.
+ template <typename DataDeleter>
+ void remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
+ DataDeleter deleter);
+
/// \brief Delete all tree nodes.
///
/// \throw none.
///
/// \param mem_sgmt The \c MemorySegment object used to insert the nodes
/// (which was also used for creating the tree due to the requirement of
- /// \c inert()).
+ /// \c insert()).
+ /// \param deleter The \c DataDeleter used to destroy data stored in
+ /// the tree nodes.
template <typename DataDeleter>
- void deleteAllNodes(util::MemorySegment& mem_sgmt, DataDeleter deleter);
+ void removeAllNodes(util::MemorySegment& mem_sgmt, DataDeleter deleter);
/// \brief Swaps two tree's contents.
///
@@ -1433,6 +1715,10 @@ private:
insertRebalance(typename DomainTreeNode<T>::DomainTreeNodePtr* root,
DomainTreeNode<T>* node);
+ void
+ removeRebalance(typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr,
+ DomainTreeNode<T>* child, DomainTreeNode<T>* parent);
+
DomainTreeNode<T>*
rightRotate(typename DomainTreeNode<T>::DomainTreeNodePtr* root,
DomainTreeNode<T>* node);
@@ -1471,6 +1757,7 @@ private:
void nodeFission(util::MemorySegment& mem_sgmt, DomainTreeNode<T>& node,
const isc::dns::LabelSequence& new_prefix,
const isc::dns::LabelSequence& new_suffix);
+
//@}
typename DomainTreeNode<T>::DomainTreeNodePtr root_;
@@ -1535,13 +1822,15 @@ DomainTree<T>::deleteHelper(util::MemorySegment& mem_sgmt,
}
template <typename T>
-template <typename CBARG>
+template <typename TT, typename TTN, typename CBARG>
typename DomainTree<T>::Result
-DomainTree<T>::find(const isc::dns::LabelSequence& target_labels_orig,
- const DomainTreeNode<T>** target,
- DomainTreeNodeChain<T>& node_path,
- bool (*callback)(const DomainTreeNode<T>&, CBARG),
- CBARG callback_arg) const
+DomainTree<T>::findImpl(TT* tree,
+ const isc::dns::LabelSequence& target_labels_orig,
+ TTN** target,
+ TTN* node,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg)
{
if (node_path.isEmpty() ^ target_labels_orig.isAbsolute()) {
isc_throw(isc::BadValue,
@@ -1549,17 +1838,6 @@ DomainTree<T>::find(const isc::dns::LabelSequence& target_labels_orig,
" and label sequence");
}
- const DomainTreeNode<T>* node;
-
- if (!node_path.isEmpty()) {
- // Get the top node in the node chain
- node = node_path.top();
- // Start searching from its down pointer
- node = node->getDown();
- } else {
- node = root_.get();
- }
-
Result ret = NOTFOUND;
dns::LabelSequence target_labels(target_labels_orig);
@@ -1570,7 +1848,7 @@ DomainTree<T>::find(const isc::dns::LabelSequence& target_labels_orig,
node_path.last_comparison_.getRelation();
if (relation == isc::dns::NameComparisonResult::EQUAL) {
- if (needsReturnEmptyNode_ || !node->isEmpty()) {
+ if (tree->needsReturnEmptyNode_ || !node->isEmpty()) {
node_path.push(node);
*target = node;
ret = EXACTMATCH;
@@ -1583,7 +1861,7 @@ DomainTree<T>::find(const isc::dns::LabelSequence& target_labels_orig,
node->getLeft() : node->getRight();
} else {
if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
- if (needsReturnEmptyNode_ || !node->isEmpty()) {
+ if (tree->needsReturnEmptyNode_ || !node->isEmpty()) {
ret = PARTIALMATCH;
*target = node;
if (callback != NULL &&
@@ -1607,6 +1885,53 @@ DomainTree<T>::find(const isc::dns::LabelSequence& target_labels_orig,
}
template <typename T>
+template <typename CBARG>
+typename DomainTree<T>::Result
+DomainTree<T>::find(const isc::dns::LabelSequence& target_labels_orig,
+ DomainTreeNode<T>** target,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg)
+{
+ if (!node_path.isEmpty()) {
+ isc_throw(isc::BadValue,
+ "DomainTree::find() non-const method is given "
+ "non-empty node chain");
+ }
+
+ DomainTreeNode<T>* node = root_.get();
+
+ return (findImpl<DomainTree<T>, DomainTreeNode<T>, CBARG >
+ (this, target_labels_orig, target, node, node_path,
+ callback, callback_arg));
+}
+
+template <typename T>
+template <typename CBARG>
+typename DomainTree<T>::Result
+DomainTree<T>::find(const isc::dns::LabelSequence& target_labels_orig,
+ const DomainTreeNode<T>** target,
+ DomainTreeNodeChain<T>& node_path,
+ bool (*callback)(const DomainTreeNode<T>&, CBARG),
+ CBARG callback_arg) const
+{
+ const DomainTreeNode<T>* node;
+
+ if (!node_path.isEmpty()) {
+ // Get the top node in the node chain
+ node = node_path.top();
+ // Start searching from its down pointer
+ node = node->getDown();
+ } else {
+ node = root_.get();
+ }
+
+ return (findImpl<const DomainTree<T>, const DomainTreeNode<T>, CBARG >
+ (this, target_labels_orig, target, node, node_path,
+ callback, callback_arg));
+}
+
+template <typename T>
const DomainTreeNode<T>*
DomainTree<T>::nextNode(DomainTreeNodeChain<T>& node_path) const {
if (node_path.isEmpty()) {
@@ -1789,9 +2114,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 +2133,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,
@@ -1892,7 +2231,127 @@ DomainTree<T>::insert(util::MemorySegment& mem_sgmt,
template <typename T>
template <typename DataDeleter>
void
-DomainTree<T>::deleteAllNodes(util::MemorySegment& mem_sgmt,
+DomainTree<T>::remove(util::MemorySegment& mem_sgmt, DomainTreeNode<T>* node,
+ DataDeleter deleter)
+{
+ // If node has a down pointer, we cannot remove this node from the
+ // DomainTree forest. We merely clear its data (destroying the data)
+ // and return.
+ if (node->getDown()) {
+ T* data = node->setData(NULL);
+ if (data) {
+ deleter(data);
+ }
+ return;
+ }
+
+ while (true) {
+ // Save subtree root's parent for use later.
+ DomainTreeNode<T>* upper_node = node->getUpperNode();
+
+ // node points to the node to be deleted in the BST. It first
+ // has to be exchanged with the right-most node in the left
+ // sub-tree or the left-most node in the right sub-tree. (Here,
+ // sub-tree is inside this RB tree itself, not in the
+ // tree-of-trees forest.) The node then ends up having a maximum
+ // of 1 child. Note that this is not an in-place value swap of
+ // node data, but the actual node locations are swapped in
+ // exchange(). Unlike normal BSTs, we have to do this as our
+ // label data is at address (this + 1).
+ if (node->getLeft() && node->getRight()) {
+ DomainTreeNode<T>* rightmost = node->getLeft();
+ while (rightmost->getRight() != NULL) {
+ rightmost = rightmost->getRight();
+ }
+
+ node->exchange(rightmost, &root_);
+ }
+
+ // Now, node has 0 or 1 children, as from above, either its
+ // right or left child definitely doesn't exist (and is NULL).
+ // Pick the child node, or if no children exist, just use NULL.
+ DomainTreeNode<T>* child;
+ if (node->getRight()) {
+ child = node->getRight();
+ } else {
+ child = node->getLeft();
+ }
+
+ // Set it as the node's parent's child, effectively removing
+ // node from the tree.
+ node->connectChild(node, child, &root_);
+
+ // Child can be NULL here if node was a leaf.
+ if (child) {
+ child->parent_ = node->getParent();
+ // Even if node is not a leaf node, we don't always do an
+ // exchange() with another node, so we have to set the
+ // child's FLAG_SUBTREE_ROOT explicitly.
+ if ((!child->getParent()) ||
+ (child->getParent()->getDown() == child))
+ {
+ child->setSubTreeRoot(node->isSubTreeRoot());
+ }
+ }
+
+ // If node is RED, it is a valid red-black tree already as
+ // (node's) child must be BLACK or NULL (which is
+ // BLACK). Deleting (the RED) node will not have any effect on
+ // the number of BLACK nodes through this path (involving node's
+ // parent and its new child). In this case, we can skip the
+ // following block.
+ if (node->isBlack()) {
+ if (child && child->isRed()) {
+ // If node is BLACK and child is RED, removing node
+ // would decrease the number of BLACK nodes through this
+ // path (involving node's parent and its new child). So
+ // we color child to be BLACK to restore the old count
+ // of black nodes through this path. It is now a valid
+ // red-black tree.
+ child->setColor(DomainTreeNode<T>::BLACK);
+ } else {
+ // If node is BLACK and child is also BLACK or NULL
+ // (which is BLACK), we need to do re-balancing to make
+ // it a valid red-black tree again.
+ typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr =
+ upper_node ? &(upper_node->down_) : &root_;
+ removeRebalance(root_ptr, child, node->getParent());
+ }
+ }
+
+ // Finally, destroy the node.
+ if (node->data_.get()) {
+ deleter(node->data_.get());
+ }
+ DomainTreeNode<T>::destroy(mem_sgmt, node);
+ --node_count_;
+
+ // If the node deletion did not cause the subtree to disappear
+ // completely, return early.
+ if (upper_node->getDown()) {
+ break;
+ }
+
+ // If the upper node is not empty, it cannot be deleted.
+ if (!upper_node->isEmpty()) {
+ break;
+ }
+
+ // If upper node is the root node (.), don't attempt to delete
+ // it. The root node must always exist.
+ if (upper_node == root_.get()) {
+ break;
+ }
+
+ // Ascend up the tree and delete the upper node.
+ node = upper_node;
+ }
+}
+
+template <typename T>
+template <typename DataDeleter>
+void
+DomainTree<T>::removeAllNodes(util::MemorySegment& mem_sgmt,
DataDeleter deleter)
{
deleteHelper(mem_sgmt, root_.get(), deleter);
@@ -1916,17 +2375,8 @@ DomainTree<T>::nodeFission(util::MemorySegment& mem_sgmt,
node.resetLabels(new_prefix);
up_node->parent_ = node.getParent();
- if (node.getParent() != NULL) {
- if (node.getParent()->getLeft() == &node) {
- node.getParent()->left_ = up_node;
- } else if (node.getParent()->getRight() == &node) {
- node.getParent()->right_ = up_node;
- } else {
- node.getParent()->down_ = up_node;
- }
- } else {
- root_ = up_node;
- }
+
+ node.connectChild(&node, up_node, &root_);
up_node->down_ = &node;
node.parent_ = up_node;
@@ -2095,6 +2545,283 @@ DomainTree<T>::insertRebalance
(*subtree_root)->setColor(DomainTreeNode<T>::BLACK);
}
+template <typename T>
+void
+DomainTree<T>::removeRebalance
+ (typename DomainTreeNode<T>::DomainTreeNodePtr* root_ptr,
+ DomainTreeNode<T>* child, DomainTreeNode<T>* parent)
+{
+ // Case 1. Repeat until we reach the root node of this subtree in
+ // the forest. Note that child can be NULL here, so we can only test
+ // the parent pointer and see if it has escaped to the upper tree.
+ while (&(parent->down_) != root_ptr) {
+ // A sibling node is defined as the parent's other child. It
+ // exists at the same level as child. Note that child can be
+ // NULL here.
+ DomainTreeNode<T>* sibling =
+ DomainTreeNode<T>::getSibling(parent, child);
+
+ // NOTE #1: Understand this clearly. We are here only because in
+ // the path through parent--child, a BLACK node was removed,
+ // i.e., the sibling's side in the path through parent--sibling
+ // is heavier by 1 extra BLACK node in its path. Because this
+ // can be an iterative process up the tree, the key is to
+ // understand this point when entering the block here.
+
+ // NOTE #2: sibling cannot be NULL here as parent--child has
+ // fewer BLACK nodes than parent--sibling.
+ assert(sibling);
+
+ // If sibling is RED, convert the tree to a form where sibling
+ // is BLACK.
+ if (sibling->isRed()) {
+ // Case 2. Here, the sibling is RED. We do a tree rotation
+ // at the parent such that sibling is the new parent, and
+ // the old parent is sibling's child. We also invert the
+ // colors of the two nodes.
+ //
+ // This step is done to convert the tree to a form for
+ // further cases below.
+
+ /* Parent (P) has to be BLACK here as its child sibling (S)
+ * is RED.
+ *
+ * P(B) S(B)
+ * / \ / \
+ * C(?) S(R) => P(R) y(B)
+ * / \ / \ / \
+ * x(B) y(B) C(?) x(B)
+ * / \
+ */
+
+ parent->setColor(DomainTreeNode<T>::RED);
+ sibling->setColor(DomainTreeNode<T>::BLACK);
+
+ if (parent->getLeft() == child) {
+ leftRotate(root_ptr, parent);
+ } else {
+ rightRotate(root_ptr, parent);
+ }
+
+ // Re-compute child's sibling due to the tree adjustment
+ // above.
+ sibling = DomainTreeNode<T>::getSibling(parent, child);
+ }
+
+ // NOTE #3: sibling still cannot be NULL here as parent--child
+ // has fewer BLACK nodes than parent--sibling.
+ assert(sibling);
+
+ // NOTE #4: From above, sibling must be BLACK here.
+ assert(sibling->isBlack());
+
+ // NOTE #5: If a tree rotation happened above, the new sibling's
+ // side through parent--sibling [x(B)] above is still heavier
+ // than parent--child by 1 extra BLACK node in its path.
+
+ // Case 3. If both of sibling's children are BLACK, then set the
+ // sibling's color to RED. This reduces the number of BLACK
+ // nodes in parent--sibling path by 1 and balances the BLACK
+ // nodes count on both sides of parent. But this introduces
+ // another issue which is that the path through one child
+ // (=parent) of parent's parent (child's grandparent) has fewer
+ // BLACK nodes now than the other child (parent's sibling).
+ //
+ // To fix this: (a) if parent is colored RED, we can change its
+ // color to BLACK (to increment the number of black nodes in
+ // grandparent--parent-->path) and we're done with the
+ // rebalancing; (b) if parent is colored BLACK, then we set
+ // child=parent and go back to the beginning of the loop to
+ // repeat the original rebalancing problem 1 node higher up the
+ // tree (see NOTE #1 above).
+
+ /* (a):
+ *
+ * G(?) G(?)
+ * / \ / \
+ * P(R) => P(B) (Rebalancing is complete)
+ * / \ / \
+ * C(?) S(B) C(?) S(R)
+ * / \ / \ / \ / \
+ * ss1(B) ss2(B) ss1(B) ss2(B)
+ *
+ *
+ * (b):
+ *
+ * G(?) G(?) <----------(New parent)
+ * / \ / \
+ * P(B) => P(B) <------------(New child)
+ * / \ / \
+ * C(?) S(B) C(?) S(R)
+ * / \ / \ / \ / \
+ * ss1(B) ss2(B) ss1(B) ss2(B)
+ */
+
+ if ((DomainTreeNode<T>::isBlack(sibling->getLeft()) &&
+ DomainTreeNode<T>::isBlack(sibling->getRight())))
+ {
+ sibling->setColor(DomainTreeNode<T>::RED);
+
+ if (parent->isBlack()) {
+ child = parent;
+ parent = parent->getParent();
+ continue;
+ } else {
+ parent->setColor(DomainTreeNode<T>::BLACK);
+ break;
+ }
+ }
+
+ // NOTE #3 and NOTE #4 asserted above still hold here.
+ assert(sibling);
+ assert(sibling->isBlack());
+
+ // NOTE #6: The path through parent--sibling is still heavier
+ // than parent--child by 1 extra BLACK node in its path. This is
+ // the key point, and this is why we are still doing the
+ // rebalancing.
+
+ // Case 4. Now, one or both of sibling's children are not
+ // BLACK. (a) We consider the case where child is the left-child
+ // of parent, and the left-child of sibling is RED and the
+ // right-child of sibling is BLACK. (b) We also consider its
+ // mirror, arrangement, i.e., the case where child is the
+ // right-child of parent, and the right-child of sibling is RED
+ // and the left-child of sibling is BLACK.
+ //
+ // In both cases, we change sibling's color to RED, the color of
+ // the RED child of sibling to BLACK (so both children of
+ // sibling are BLACK), and we do a tree rotation around sibling
+ // node in the opposite direction of the old RED child of
+ // sibling.
+ //
+ // This step is done to convert the tree to a form for further
+ // cases below.
+
+ /* (a):
+ *
+ * P(?) => P(?)
+ * / \ / \
+ * C(?) S(B) C(?) ss1(B)
+ * / \ / \ / \ / \
+ * ss1(R) ss2(B) x(B) S(R)
+ * / \ / \
+ * x(B) y(B) y(B) ss2(B)
+ *
+ *
+ * (b):
+ *
+ * P(?) => P(?)
+ * / \ / \
+ * S(B) C(?) ss1(B) C(?)
+ * / \ / \ / \ / \
+ * ss2(B) ss1(R) S(R) x(B)
+ * / \ / \
+ * y(B) x(B) ss2(B) y(B)
+ */
+
+ DomainTreeNode<T>* ss1 = sibling->getLeft();
+ DomainTreeNode<T>* ss2 = sibling->getRight();
+ if (parent->getLeft() != child) {
+ // Swap for the mirror arrangement described in case 4 (b)
+ // above.
+ std::swap(ss1, ss2);
+ }
+
+ if (DomainTreeNode<T>::isBlack(ss2)) {
+ // It is implied by ss2 being BLACK that ss1 is RED.
+
+ sibling->setColor(DomainTreeNode<T>::RED);
+ // ss1 cannot be NULL here as it is a RED node.
+ ss1->setColor(DomainTreeNode<T>::BLACK);
+
+ if (parent->getLeft() == child) {
+ rightRotate(root_ptr, sibling);
+ } else {
+ leftRotate(root_ptr, sibling);
+ }
+ // Re-compute child's sibling due to the tree adjustment
+ // above.
+ sibling = DomainTreeNode<T>::getSibling(parent, child);
+ }
+
+ // NOTE #7: sibling cannot be NULL here as even if the sibling
+ // variable was assigned in the node above, it was set to ss1
+ // which was a RED node before (non-NULL).
+ assert(sibling);
+
+ // NOTE #8: sibling is still BLACK, even if the sibling variable
+ // was assigned in the node above, it was set to ss1 which is
+ // now a BLACK node.
+ assert(sibling->isBlack());
+
+ // NOTE #9: The path through parent--sibling is still heavier
+ // than parent--child by 1 extra BLACK node in its path. This is
+ // the key point, and this is why we are still doing the
+ // rebalancing.
+
+ // Case 5. After case 4 above, we are in a canonical form now
+ // where sibling is BLACK, and either (a) if child is the
+ // left-child of parent, the right-child (ss2) of sibling is
+ // definitely RED, or (b) if child is the right-child of parent,
+ // the left-child (ss2) of sibling is definitely RED.
+ //
+ // Here, we set sibling's color to that of the parent, and set
+ // the parent's color to BLACK. We set ss2's color to BLACK (it
+ // was previously RED). Then we do a tree-rotation around parent
+ // in the direction of child to pull in the BLACK parent into
+ // its sub-tree. These steps effectively balances the tree as
+ // you can see from the graph below. Before starting, the graph
+ // on the child's side is lighter by 1 BLACK node than the graph
+ // on the sibling's side. After these steps, both sides of S(x)
+ // have the same number of BLACK nodes in any path through it.
+
+ /* (a):
+ *
+ * P(x) S(x)
+ * / \ / \
+ * C(?) S(B) => P(B) ss2(B)
+ * / \ / \ / \ / \
+ * ss1(?) ss2(R) C(?) ss1(?) (B) (B)
+ * / \ / \
+ * (B) (B)
+ *
+ * (Here, 'x' is the parent's color. In the resulting tree,
+ * it is set as S node's color.)
+ *
+ * (b):
+ * This is just the mirror of above.
+ */
+
+ sibling->setColor(parent->getColor());
+ parent->setColor(DomainTreeNode<T>::BLACK);
+
+ ss1 = sibling->getLeft();
+ ss2 = sibling->getRight();
+ if (parent->getLeft() != child) {
+ // Swap for the mirror arrangement described in case 4 (b)
+ // above.
+ std::swap(ss1, ss2);
+ }
+
+ // ss2 cannot be NULL here as it is a RED node.
+ ss2->setColor(DomainTreeNode<T>::BLACK);
+
+ if (parent->getLeft() == child) {
+ leftRotate(root_ptr, parent);
+ } else {
+ rightRotate(root_ptr, parent);
+ }
+
+ // NOTE #10: Now, sibling is parent's parent. All paths through
+ // sibling have the same number of BLACK nodes.
+
+ // We are completely finished and the tree is now
+ // balanced. Phew. Now let's take a coffee-break.
+
+ break;
+ }
+}
template <typename T>
DomainTreeNode<T>*
@@ -2164,6 +2891,112 @@ DomainTree<T>::rightRotate
return (node);
}
+template <typename T>
+size_t
+DomainTree<T>::getHeightHelper(const DomainTreeNode<T>* node) const {
+ if (node == NULL) {
+ return (0);
+ }
+
+ const size_t dl = getHeightHelper(node->getLeft());
+ const size_t dr = getHeightHelper(node->getRight());
+
+ const size_t this_height = std::max(dl + 1, dr + 1);
+ const size_t down_height = getHeightHelper(node->getDown());
+
+ return (std::max(this_height, down_height));
+}
+
+template <typename T>
+size_t
+DomainTree<T>::getHeight() const {
+ return (getHeightHelper(root_.get()));
+}
+
+template <typename T>
+bool
+DomainTree<T>::checkPropertiesHelper(const DomainTreeNode<T>* node) const {
+ if (node == NULL) {
+ return (true);
+ }
+
+ if (node->isRed()) {
+ // Root nodes must be BLACK.
+ if (node->isSubTreeRoot()) {
+ return (false);
+ }
+
+ // Both children of RED nodes must be BLACK.
+ if (DomainTreeNode<T>::isRed(node->getLeft()) ||
+ DomainTreeNode<T>::isRed(node->getRight()))
+ {
+ return (false);
+ }
+ }
+
+ // If node is assigned to the down_ pointer of its parent, it is a
+ // subtree root and must have the flag set.
+ if (((!node->getParent()) ||
+ (node->getParent()->getDown() == node)) &&
+ (!node->isSubTreeRoot()))
+ {
+ return (false);
+ }
+
+ // Repeat tests with this node's children.
+ return (checkPropertiesHelper(node->getLeft()) &&
+ checkPropertiesHelper(node->getRight()) &&
+ checkPropertiesHelper(node->getDown()));
+}
+
+template <typename T>
+bool
+DomainTree<T>::checkBlackDistanceHelper(const DomainTreeNode<T>* node,
+ size_t* distance) const
+{
+ if (node == NULL) {
+ *distance = 1;
+ return (true);
+ }
+
+ size_t dl, dr, dd;
+ if (!checkBlackDistanceHelper(node->getLeft(), &dl)) {
+ return (false);
+ }
+ if (!checkBlackDistanceHelper(node->getRight(), &dr)) {
+ return (false);
+ }
+ if (!checkBlackDistanceHelper(node->getDown(), &dd)) {
+ return (false);
+ }
+
+ if (dl != dr) {
+ return (false);
+ }
+
+ if (node->isBlack()) {
+ ++dl;
+ }
+
+ *distance = dl;
+
+ return (true);
+}
+
+template <typename T>
+bool
+DomainTree<T>::checkProperties() const {
+ if (!checkPropertiesHelper(root_.get())) {
+ return (false);
+ }
+
+ // Path from a given node to all its leaves must contain the same
+ // number of BLACK child nodes. This is done separately here instead
+ // of inside checkPropertiesHelper() as it would take (n log n)
+ // complexity otherwise.
+ size_t dd;
+ return (checkBlackDistanceHelper(root_.get(), &dd));
+}
template <typename T>
void
diff --git a/src/lib/datasrc/tests/memory/domaintree_unittest.cc b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
index 3e6bceb..0d8159b 100644
--- a/src/lib/datasrc/tests/memory/domaintree_unittest.cc
+++ b/src/lib/datasrc/tests/memory/domaintree_unittest.cc
@@ -31,11 +31,17 @@
#include <boost/format.hpp>
+#include <stdlib.h>
+
+#include <set>
+#include <algorithm>
+
using namespace std;
using namespace isc;
using namespace isc::dns;
using isc::UnitTestUtil;
using namespace isc::datasrc::memory;
+using isc::util::random::UniformRandomIntegerGenerator;
// XXX: some compilers cannot find class static constants used in
// EXPECT_xxx macros, for which we need an explicit empty definition.
@@ -62,6 +68,53 @@ const size_t Name::MAX_LABELS;
namespace {
+// The full absolute names of the nodes in the tree with the addition of
+// the explicit root node.
+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", "k.g.h"
+};
+
+// These are set as the node data.
+const int node_distances[] = {
+ 3, 1, 2, 2, 2, 3, 1, 2, 1, 1, 2, 2
+};
+
+const int name_count = sizeof(domain_names) / sizeof(domain_names[0]);
+
+/*
+ * 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, k.g.h
+ * . (no data, can't be found)
+ * |
+ * b
+ * / \
+ * a d.e.f
+ * / | \
+ * c | g.h
+ * | |
+ * w.y i
+ * / | \ \
+ * x | z k
+ * | |
+ * p j
+ * / \
+ * o q
+ */
+
+const char* const ordered_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", "k.g.h"};
+const size_t ordered_names_count(sizeof(ordered_names) /
+ sizeof(*ordered_names));
+
+const char* const upper_node_names[] = {
+ ".", ".", ".", ".", "d.e.f", "d.e.f", "w.y.d.e.f",
+ "w.y.d.e.f", "w.y.d.e.f", "d.e.f", "z.d.e.f",
+ ".", "g.h", "g.h"};
+
void deleteData(int* i) {
delete i;
}
@@ -88,20 +141,13 @@ class DomainTreeTest : public::testing::Test {
protected:
DomainTreeTest() :
dtree_holder_(mem_sgmt_, TestDomainTree::create(mem_sgmt_)),
- dtree_expose_empty_node_holder_(mem_sgmt_,
- TestDomainTree::create(mem_sgmt_, true)),
+ dtree_expose_empty_node_holder_
+ (mem_sgmt_, TestDomainTree::create(mem_sgmt_, true)),
dtree(*dtree_holder_.get()),
dtree_expose_empty_node(*dtree_expose_empty_node_holder_.get()),
- cdtnode(NULL)
+ cdtnode(NULL),
+ name_gen_('a', 'z')
{
- 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", "k.g.h"};
- const int node_distances[] = {
- 3, 1, 2, 2, 2, 3, 1, 2, 1, 1, 2, 2
- };
-
- int name_count = sizeof(domain_names) / sizeof(domain_names[0]);
for (int i = 0; i < name_count; ++i) {
dtree.insert(mem_sgmt_, Name(domain_names[i]), &dtnode);
// Check the node doesn't have any data initially.
@@ -113,6 +159,8 @@ protected:
EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(
new int(node_distances[i])));
}
+
+ srandom(time(NULL));
}
util::MemorySegmentLocal mem_sgmt_;
@@ -122,6 +170,7 @@ protected:
TestDomainTree& dtree_expose_empty_node;
TestDomainTreeNode* dtnode;
const TestDomainTreeNode* cdtnode;
+ UniformRandomIntegerGenerator name_gen_;
uint8_t buf[LabelSequence::MAX_SERIALIZED_LENGTH];
};
@@ -129,8 +178,8 @@ TEST_F(DomainTreeTest, nodeCount) {
EXPECT_EQ(15, dtree.getNodeCount());
// Delete all nodes, then the count should be set to 0. This also tests
- // the behavior of deleteAllNodes().
- dtree.deleteAllNodes(mem_sgmt_, deleteData);
+ // the behavior of removeAllNodes().
+ dtree.removeAllNodes(mem_sgmt_, deleteData);
EXPECT_EQ(0, dtree.getNodeCount());
}
@@ -150,22 +199,6 @@ TEST_F(DomainTreeTest, getDistance) {
}
}
-void
-checkDistances(const TestDomainTree& tree, int distance) {
- TestDomainTreeNodeChain node_path;
- const TestDomainTreeNode* node = NULL;
-
- // Try to find a node left of the left-most node, and start from its
- // next node (which is the left-most node in its subtree).
- EXPECT_EQ(TestDomainTree::NOTFOUND,
- tree.find<void*>(Name("0"), &node, node_path, NULL, NULL));
- while ((node = tree.nextNode(node_path)) != NULL) {
- // The distance from each node to its sub-tree root must be less
- // than 2 * log(n).
- EXPECT_GE(2 * distance, node->getDistance());
- }
-}
-
TEST_F(DomainTreeTest, checkDistanceRandom) {
// This test checks an important performance-related property of the
// DomainTree (a red-black tree), which is important for us: the
@@ -176,7 +209,6 @@ TEST_F(DomainTreeTest, checkDistanceRandom) {
TreeHolder mytree_holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_));
TestDomainTree& mytree = *mytree_holder.get();
- isc::util::random::UniformRandomIntegerGenerator gen('a', 'z');
const int log_num_nodes = 20;
// Make a large million+ node top-level domain tree, i.e., the
@@ -191,7 +223,7 @@ TEST_F(DomainTreeTest, checkDistanceRandom) {
string namestr;
while (true) {
for (int j = 0; j < 32; j++) {
- namestr += gen();
+ namestr += name_gen_();
}
namestr += '.';
@@ -206,7 +238,12 @@ TEST_F(DomainTreeTest, checkDistanceRandom) {
EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(new int(i + 1)));
}
- checkDistances(mytree, log_num_nodes);
+ // The distance from each node to its sub-tree root must be less
+ // than 2 * log(n).
+ EXPECT_GE(2 * log_num_nodes, mytree.getHeight());
+
+ // Also check RB tree properties
+ EXPECT_TRUE(mytree.checkProperties());
}
TEST_F(DomainTreeTest, checkDistanceSorted) {
@@ -235,7 +272,12 @@ TEST_F(DomainTreeTest, checkDistanceSorted) {
EXPECT_EQ(static_cast<int*>(NULL), dtnode->setData(new int(i + 1)));
}
- checkDistances(mytree, log_num_nodes);
+ // The distance from each node to its sub-tree root must be less
+ // than 2 * log(n).
+ EXPECT_GE(2 * log_num_nodes, mytree.getHeight());
+
+ // Also check RB tree properties
+ EXPECT_TRUE(mytree.checkProperties());
}
TEST_F(DomainTreeTest, setGetData) {
@@ -344,6 +386,329 @@ TEST_F(DomainTreeTest, insertNames) {
&dtnode));
}
+TEST_F(DomainTreeTest, remove) {
+ // This testcase checks that after node removal, the binary-search
+ // tree is valid and all nodes that are supposed to exist are
+ // present in the correct order. It mainly tests DomainTree as a
+ // BST, and not particularly as a red-black tree. This test checks
+ // node deletion when upper nodes have data.
+
+ // Delete single nodes and check if the rest of the nodes exist
+ for (int j = 0; j < ordered_names_count; ++j) {
+ TreeHolder holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_, true));
+ TestDomainTree& tree(*holder.get());
+ TestDomainTreeNode* node;
+
+ for (int i = 0; i < name_count; ++i) {
+ tree.insert(mem_sgmt_, Name(domain_names[i]), NULL);
+ }
+
+ for (int i = 0; i < ordered_names_count; ++i) {
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[i]), &node));
+ // Check nodes are not empty.
+ EXPECT_EQ(static_cast<int*>(NULL), node->setData(new int(i)));
+ EXPECT_FALSE(node->isEmpty());
+ }
+
+ // Now, delete the j'th node from the tree.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[j]), &node));
+ tree.remove(mem_sgmt_, node, deleteData);
+
+ // Check RB tree properties
+ ASSERT_TRUE(tree.checkProperties());
+
+ // Now, walk through nodes in order.
+ TestDomainTreeNodeChain node_path;
+ const TestDomainTreeNode* cnode;
+ int start_node;
+
+ if (j == 0) {
+ EXPECT_NE(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[0]),
+ &cnode));
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[1]),
+ &cnode, node_path));
+ start_node = 1;
+ } else {
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[0]),
+ &cnode, node_path));
+ start_node = 0;
+ }
+
+ for (int i = start_node; i < ordered_names_count; ++i) {
+ const Name nj(ordered_names[j]);
+ const Name ni(ordered_names[i]);
+
+ if (ni == nj) {
+ // This may be true for the last node if we seek ahead
+ // in the loop using nextNode() below.
+ if (!cnode) {
+ break;
+ }
+ // All ordered nodes have data initially. If any node is
+ // empty, it means it was remove()d, but an empty node
+ // exists because it is a super-domain. Just skip it.
+ if (cnode->isEmpty()) {
+ cnode = tree.nextNode(node_path);
+ }
+ continue;
+ }
+
+ ASSERT_NE(static_cast<void*>(NULL), cnode);
+ const int* data = cnode->getData();
+
+ if (data) {
+ EXPECT_EQ(i, *data);
+ }
+
+ uint8_t buf[isc::dns::LabelSequence::MAX_SERIALIZED_LENGTH];
+ const LabelSequence ls(cnode->getAbsoluteLabels(buf));
+ EXPECT_EQ(LabelSequence(ni), ls);
+
+ cnode = tree.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ ASSERT_EQ(static_cast<void*>(NULL), cnode);
+ }
+}
+
+TEST_F(DomainTreeTest, removeEmpty) {
+ // This test is similar to the .remove test. But it checks node
+ // deletion when upper nodes are empty.
+
+ // Delete single nodes and check if the rest of the nodes exist
+ for (int j = 0; j < ordered_names_count; ++j) {
+ TreeHolder holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_, true));
+ TestDomainTree& tree(*holder.get());
+ TestDomainTreeNode* node;
+
+ for (int i = 0; i < name_count; ++i) {
+ tree.insert(mem_sgmt_, Name(domain_names[i]), NULL);
+ }
+
+ for (int i = 0; i < ordered_names_count; ++i) {
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[i]), &node));
+ // Check nodes are empty.
+ EXPECT_TRUE(node->isEmpty());
+ }
+
+ // Now, delete the j'th node from the tree.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[j]), &node));
+ tree.remove(mem_sgmt_, node, deleteData);
+
+ // Check RB tree properties
+ ASSERT_TRUE(tree.checkProperties());
+
+ // Now, walk through nodes in order.
+ TestDomainTreeNodeChain node_path;
+ const TestDomainTreeNode* cnode;
+ int start_node;
+
+ if (j == 0) {
+ EXPECT_NE(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[0]),
+ &cnode));
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[1]),
+ &cnode, node_path));
+ start_node = 1;
+ } else {
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(ordered_names[0]),
+ &cnode, node_path));
+ start_node = 0;
+ }
+
+ for (int i = start_node; i < ordered_names_count; ++i) {
+ const Name nj(ordered_names[j]);
+ const Name ni(ordered_names[i]);
+
+ if ((nj == Name("j.z.d.e.f")) &&
+ (ni == Name("z.d.e.f")))
+ {
+ // The only special case in the tree. Here, "z.d.e.f"
+ // will not exist as it would have been removed during
+ // removal of "j.z.d.e.f".
+ continue;
+ }
+
+ if (ni == nj) {
+ // This may be true for the last node if we seek ahead
+ // in the loop using nextNode() below.
+ if (!cnode) {
+ break;
+ }
+ // All ordered nodes are empty initially. If an empty
+ // removed node exists because it is a super-domain,
+ // just skip it.
+ if ((nj == Name("d.e.f")) ||
+ (nj == Name("w.y.d.e.f")) ||
+ (nj == Name("z.d.e.f")) ||
+ (nj == Name("g.h")))
+ {
+ cnode = tree.nextNode(node_path);
+ }
+ continue;
+ }
+
+ ASSERT_NE(static_cast<void*>(NULL), cnode);
+
+ uint8_t buf[isc::dns::LabelSequence::MAX_SERIALIZED_LENGTH];
+ const LabelSequence ls(cnode->getAbsoluteLabels(buf));
+ EXPECT_EQ(LabelSequence(ni), ls);
+
+ cnode = tree.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ ASSERT_EQ(static_cast<void*>(NULL), cnode);
+ }
+}
+
+void
+insertNodes(util::MemorySegment& mem_sgmt, TestDomainTree& tree,
+ std::set<std::string>& names, size_t num_nodes,
+ UniformRandomIntegerGenerator& name_gen)
+{
+ for (size_t i = 0; i < num_nodes; ++i) {
+ std::string namestr;
+ while (true) {
+ for (int j = 0; j < 32; j++) {
+ namestr += name_gen();
+ }
+ namestr += '.';
+
+ TestDomainTreeNode* cnode;
+ if (tree.insert(mem_sgmt, Name(namestr), &cnode) ==
+ TestDomainTree::SUCCESS) {
+ names.insert(namestr);
+ break;
+ }
+
+ namestr.clear();
+ }
+ }
+}
+
+void
+removeNodes(util::MemorySegment& mem_sgmt, TestDomainTree& tree,
+ std::set<std::string>& names, size_t num_nodes)
+{
+ size_t set_size = names.size();
+
+ for (size_t i = 0; i < num_nodes; ++i) {
+ // Here, UniformRandomIntegerGenerator is not a great RNG as
+ // it'll likely get seeded with the same seed throughout this
+ // testcase, and the size of the names set keeps changing.
+
+ std::set<std::string>::iterator it(names.begin());
+ // This is rather inefficient, but it's a test...
+ std::advance(it, random() % set_size);
+ std::string nstr(*it);
+
+ TestDomainTreeNode* node;
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name(nstr), &node));
+
+ tree.remove(mem_sgmt, node, deleteData);
+
+ names.erase(*it);
+ --set_size;
+ }
+}
+
+void
+checkTree(const TestDomainTree& tree,
+ const std::set<std::string>& names)
+{
+ // The distance from each node to its sub-tree root must be less
+ // than 2 * log_2(1024).
+ EXPECT_GE(2 * 10, tree.getHeight());
+
+ // Also check RB tree properties
+ EXPECT_TRUE(tree.checkProperties());
+
+ // Now, walk through nodes in order.
+ TestDomainTreeNodeChain node_path;
+ const TestDomainTreeNode* cnode;
+
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name("."), &cnode, node_path));
+
+ // Skip to the next node after "."
+ cnode = tree.nextNode(node_path);
+ if (names.empty()) {
+ // Empty tree.
+ EXPECT_EQ(static_cast<void*>(NULL), cnode);
+ return;
+ }
+
+ for (std::set<std::string>::const_iterator it = names.begin();
+ it != names.end(); ++it)
+ {
+ const Name n1(*it);
+ const Name n2(cnode->getName());
+
+ const NameComparisonResult result = n1.compare(n2);
+ EXPECT_EQ(NameComparisonResult::EQUAL, result.getRelation());
+
+ cnode = tree.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ EXPECT_EQ(static_cast<void*>(NULL), cnode);
+}
+
+TEST_F(DomainTreeTest, insertAndRemove) {
+ // What is the best way to test our red-black tree code? It is not a
+ // good method to test every case handled in the actual code itself
+ // (such as in insertRebalance() and removeRebalance()). This is
+ // because our approach itself may be incorrect.
+ //
+ // We test our code at the interface level here by exercising the
+ // tree randomly multiple times, checking that red-black tree
+ // properties are valid, and all the nodes that are supposed to be
+ // in the tree exist and are in order.
+
+ // NOTE: These tests are run within a single tree in the
+ // forest. Fusion, etc. are tested elsewhere. The number of nodes in
+ // the tree doesn't grow over 1024.
+
+ TreeHolder holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_, true));
+ TestDomainTree& tree(*holder.get());
+ std::set<std::string> names;
+
+ size_t node_count = 0;
+
+ // Repeat the insert/remove test some 4096 times
+ for (int i = 0; i < 4096; ++i) {
+ UniformRandomIntegerGenerator gen(1, 1024 - node_count);
+ size_t num_nodes = gen();
+ node_count += num_nodes;
+
+ insertNodes(mem_sgmt_, tree, names, num_nodes, name_gen_);
+ checkTree(tree, names);
+
+ UniformRandomIntegerGenerator gen2(1, node_count);
+ num_nodes = gen2();
+ node_count -= num_nodes;
+
+ removeNodes(mem_sgmt_, tree, names, num_nodes);
+ checkTree(tree, names);
+ }
+
+ // Remove the rest of the nodes.
+ removeNodes(mem_sgmt_, tree, names, node_count);
+ checkTree(tree, names);
+}
+
TEST_F(DomainTreeTest, subTreeRoot) {
// This is a testcase for a particular issue that went unchecked in
// #2089's implementation, but was fixed in #2092. The issue was
@@ -778,45 +1143,14 @@ TEST_F(DomainTreeTest, getAbsoluteNameError) {
EXPECT_THROW(chain.getAbsoluteName(), BadValue);
}
-/*
- * 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, k.g.h
- * . (no data, can't be found)
- * |
- * b
- * / \
- * a d.e.f
- * / | \
- * c | g.h
- * | |
- * w.y i
- * / | \ \
- * x | z k
- * | |
- * p j
- * / \
- * o q
- */
-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", "k.g.h"};
-const size_t name_count(sizeof(names) / sizeof(*names));
-
-const char* const upper_node_names[] = {
- ".", ".", ".", ".", "d.e.f", "d.e.f", "w.y.d.e.f",
- "w.y.d.e.f", "w.y.d.e.f", "d.e.f", "z.d.e.f",
- ".", "g.h", "g.h"};
-
TEST_F(DomainTreeTest, getUpperNode) {
TestDomainTreeNodeChain node_path;
const TestDomainTreeNode* node = NULL;
EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name(names[0]),
- &node,
- node_path));
- for (int i = 0; i < name_count; ++i) {
+ dtree_expose_empty_node.find(Name(ordered_names[0]),
+ &node,
+ node_path));
+ for (int i = 0; i < ordered_names_count; ++i) {
EXPECT_NE(static_cast<void*>(NULL), node);
const TestDomainTreeNode* upper_node = node->getUpperNode();
@@ -852,7 +1186,7 @@ TEST_F(DomainTreeTest, getSubTreeRoot) {
TestDomainTreeNodeChain node_path;
const TestDomainTreeNode* node = NULL;
EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree_expose_empty_node.find(Name(names[0]),
+ dtree_expose_empty_node.find(Name(ordered_names[0]),
&node,
node_path));
for (int i = 0; i < name_count; ++i) {
@@ -884,10 +1218,10 @@ TEST_F(DomainTreeTest, nextNode) {
TestDomainTreeNodeChain node_path;
const TestDomainTreeNode* node = NULL;
EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree.find(Name(names[0]), &node, node_path));
- for (int i = 0; i < name_count; ++i) {
+ dtree.find(Name(ordered_names[0]), &node, node_path));
+ for (int i = 0; i < ordered_names_count; ++i) {
EXPECT_NE(static_cast<void*>(NULL), node);
- EXPECT_EQ(Name(names[i]), node_path.getAbsoluteName());
+ EXPECT_EQ(Name(ordered_names[i]), node_path.getAbsoluteName());
node = dtree.nextNode(node_path);
}
@@ -903,7 +1237,7 @@ TEST_F(DomainTreeTest, nextNode) {
// node_path - the path from the previous call to find(), will be modified
// chain_length - the number of names that should be in the chain to be walked
// (0 means it should be empty, 3 means 'a', 'b' and 'c' should be there -
-// this is always from the beginning of the names[] list).
+// this is always from the beginning of the ordered_names[] list).
// skip_first - if this is false, the node should already contain the node with
// the first name of the chain. If it is true, the node should be NULL
// (true is for finds that return no match, false for the ones that return
@@ -921,7 +1255,7 @@ previousWalk(TestDomainTree& dtree, const TestDomainTreeNode* node,
}
for (size_t i(chain_length); i > 0; --i) {
EXPECT_NE(static_cast<void*>(NULL), node);
- EXPECT_EQ(Name(names[i - 1]), node_path.getAbsoluteName());
+ EXPECT_EQ(Name(ordered_names[i - 1]), node_path.getAbsoluteName());
// Find the node at the path and check the value is the same
// (that it really returns the correct corresponding node)
//
@@ -930,7 +1264,8 @@ previousWalk(TestDomainTree& dtree, const TestDomainTreeNode* node,
const TestDomainTreeNode* node2(NULL);
TestDomainTreeNodeChain node_path2;
EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree.find(Name(names[i - 1]), &node2, node_path2));
+ dtree.find(Name(ordered_names[i - 1]),
+ &node2, node_path2));
EXPECT_EQ(node, node2);
}
node = dtree.previousNode(node_path);
@@ -960,8 +1295,9 @@ TEST_F(DomainTreeTest, previousNode) {
{
SCOPED_TRACE("Iterate through");
EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree.find(Name(names[name_count - 1]), &node, node_path));
- previousWalk(dtree, node, node_path, name_count, false);
+ dtree.find(Name(ordered_names[ordered_names_count - 1]),
+ &node, node_path));
+ previousWalk(dtree, node, node_path, ordered_names_count, false);
node = NULL;
node_path.clear();
}
@@ -970,7 +1306,7 @@ TEST_F(DomainTreeTest, previousNode) {
SCOPED_TRACE("Iterate from the middle");
// Now, start somewhere in the middle, but within the real node.
EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree.find(Name(names[4]), &node, node_path));
+ dtree.find(Name(ordered_names[4]), &node, node_path));
previousWalk(dtree, node, node_path, 5, false);
node = NULL;
node_path.clear();
@@ -981,7 +1317,7 @@ TEST_F(DomainTreeTest, previousNode) {
// If we start at the lowest (which is "a"), we get to the beginning
// right away.
EXPECT_EQ(TestDomainTree::EXACTMATCH,
- dtree.find(Name(names[0]), &node, node_path));
+ dtree.find(Name(ordered_names[0]), &node, node_path));
EXPECT_NE(static_cast<void*>(NULL), node);
node = dtree.previousNode(node_path);
ASSERT_NE(static_cast<void*>(NULL), node);
@@ -1008,7 +1344,7 @@ TEST_F(DomainTreeTest, previousNode) {
SCOPED_TRACE("Start after the last");
EXPECT_EQ(TestDomainTree::NOTFOUND,
dtree.find(Name("z"), &node, node_path));
- previousWalk(dtree, node, node_path, name_count, true);
+ previousWalk(dtree, node, node_path, ordered_names_count, true);
node = NULL;
node_path.clear();
}
@@ -1070,7 +1406,7 @@ TEST_F(DomainTreeTest, previousNode) {
EXPECT_GT(node_path.getLastComparisonResult().getOrder(), 0);
// We then descend into 'i.g.h' and walk all the nodes in the
// tree.
- previousWalk(dtree, node, node_path, name_count, true);
+ previousWalk(dtree, node, node_path, ordered_names_count, true);
node = NULL;
node_path.clear();
}
@@ -1364,17 +1700,11 @@ TEST_F(DomainTreeTest, root) {
}
TEST_F(DomainTreeTest, getAbsoluteLabels) {
- // The full absolute names of the nodes in the tree
- // with the addition of the explicit root node
- 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", "k.g.h"};
// The names of the nodes themselves, as they end up in the tree
const char* const first_labels[] = {
"c", "b", "a", "x", "z", "g.h", "i", "o",
"j", "p", "q", "k"};
- const int name_count = sizeof(domain_names) / sizeof(domain_names[0]);
for (int i = 0; i < name_count; ++i) {
EXPECT_EQ(TestDomainTree::EXACTMATCH, dtree.find(Name(domain_names[i]),
&cdtnode));
More information about the bind10-changes
mailing list