BIND 10 master, updated. 6e31e88f3be72f3e774892b46e58dc00da565dac Merge branch 'master' of ssh://bind10.isc.org/var/bind10/git/bind10
BIND 10 source code commits
bind10-changes at lists.isc.org
Tue Feb 8 00:49:00 UTC 2011
The branch, master has been updated
via 6e31e88f3be72f3e774892b46e58dc00da565dac (commit)
via d2cb311448c6f9010ff2f614ca6ffbc0c0d668a8 (commit)
via c73a307cb41eb3e8bb6681dd963f6953973330ca (commit)
via 1a52db4373a1c4169b0bbd9bc6a550e5a3e68b39 (commit)
via bbd103fff6a6a6e775a075c5132bc1cdd38a5acf (commit)
via ad83fe6b6c31a54e39116f12eb5c70d9fce8d9ea (commit)
via 12aa5f7fd9f8ce0aa10b66cbd3608c363eb3390f (commit)
via 873ab3f9db15055ec293533202bc73d908ab73c1 (commit)
via a929e898df74d43fc590e8df793edeb5f355e29d (commit)
via c11ea16f0ce2d7eac933dfc9e7b57e0e82972205 (commit)
via 2565b9fe9daf6ba63234b06b9f0eb5b8168257b4 (commit)
via c2b374e5e2d608ce0236b7f49b63bf70b57c761f (commit)
via 2e93f9a6c23985a4e9968c13c3068c61f202ca4f (commit)
via 6031b9096d5a9c73468afa386a3e311984125522 (commit)
via ed3436f599952a3e070dbf19668e5bcb2e9dacac (commit)
via dd2f336165e9f974aaed88569b5e718493cd5757 (commit)
via 324b135b99582c63aa49f50d8c80e00d6e43e2f9 (commit)
via 6fb3a7ca7f9f1b7018493a263b3063b0b0962b5e (commit)
via b211d93037f31731426dbf073098ebfa8ae16bc4 (commit)
via 89cbb6aafeaf5cbc51b50a0caa4542c7b0f43eb4 (commit)
via 89f3a8b45f18f1bf4e1a2e6082a93513582b6d55 (commit)
via 64ebfb19dd4c42b8ba81b258a1a408345c3b1caf (commit)
via 9d0ec38ee3ef9e08778abd66c6946bdec5f2d25b (commit)
via fb981291afb0a4dc0fcbd16b9bb552e5fbb5c20b (commit)
via 2f151e47e2579aed8c124385dacb3c971978ed45 (commit)
via 94270478763c9c4000ca94afb94fb4762f56c3f9 (commit)
via bebfa15d5007c3ba8ce740403c8333ea6480b83e (commit)
via 597bb698382ffdd04cdd2869ce5d2570dd5ac875 (commit)
via e01dadd724cfe1274f45c6be4b5ba6f532df8c0e (commit)
from 731862b901f5530ac764db9605468d2a60ced17b (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 6e31e88f3be72f3e774892b46e58dc00da565dac
Merge: d2cb311448c6f9010ff2f614ca6ffbc0c0d668a8 731862b901f5530ac764db9605468d2a60ced17b
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Mon Feb 7 14:30:47 2011 -0800
Merge branch 'master' of ssh://bind10.isc.org/var/bind10/git/bind10
commit d2cb311448c6f9010ff2f614ca6ffbc0c0d668a8
Merge: 65ff9720f00bccc88590d09aa8f6feae5356e081 c73a307cb41eb3e8bb6681dd963f6953973330ca
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Mon Feb 7 14:30:15 2011 -0800
[master] Merge branch 'trac517' with resolving conflicts.
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory_datasrc.cc | 3 +-
src/lib/datasrc/rbtree.h | 544 ++++++++++++++++++++++--------
src/lib/datasrc/tests/rbtree_unittest.cc | 231 ++++++++------
3 files changed, 543 insertions(+), 235 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory_datasrc.cc b/src/lib/datasrc/memory_datasrc.cc
index 8f46aa4..31c5a95 100644
--- a/src/lib/datasrc/memory_datasrc.cc
+++ b/src/lib/datasrc/memory_datasrc.cc
@@ -290,7 +290,8 @@ struct MemoryZone::MemoryZoneImpl {
// Get the node
DomainNode* node(NULL);
FindState state(options);
- switch (domains_.find(name, &node, cutCallback, &state)) {
+ RBTreeNodeChain<Domain> node_path;
+ switch (domains_.find(name, &node, node_path, cutCallback, &state)) {
case DomainTree::PARTIALMATCH:
/*
* In fact, we could use a single variable instead of
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index 643b185..cf413e8 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -26,9 +26,10 @@
#include <dns/name.h>
#include <boost/utility.hpp>
#include <boost/shared_ptr.hpp>
-#include <exception>
+#include <exceptions/exceptions.h>
#include <ostream>
#include <algorithm>
+#include <cassert>
namespace isc {
namespace datasrc {
@@ -54,7 +55,9 @@ operator-(const isc::dns::Name& super_name, const isc::dns::Name& sub_name) {
}
}
-template <typename T, bool returnEmptyNode>
+/// Forward declare RBTree class here is convinent for following friend
+/// class declare inside RBNode and RBTreeNodeChain
+template <typename T>
class RBTree;
/// \brief \c RBNode is used by RBTree to store any data related to one domain
@@ -82,8 +85,7 @@ class RBNode : public boost::noncopyable {
private:
/// The RBNode is meant for use from within RBTree, so it has access to
/// it.
- template <typename U, bool returnEmptyNode>
- friend class RBTree;
+ friend class RBTree<T>;
/// \name Constructors
///
@@ -142,6 +144,7 @@ public:
/// non-terminal domains, but it is possible (yet probably meaningless)
/// empty nodes anywhere.
bool isEmpty() const { return (data_.get() == NULL); }
+
//@}
/// \name Setter functions.
@@ -176,6 +179,23 @@ private:
return (&null_node);
}
+ /// \brief return the next node which is bigger than current node
+ /// in the same subtree
+ ///
+ /// The next successor for this node is the next bigger node in terms of
+ /// the DNSSEC order relation within the same single subtree.
+ /// Note that it may NOT be the next bigger node in the entire RBTree;
+ /// RBTree is a tree in tree, and the real next node may reside in
+ /// an upper or lower subtree of the subtree where this node belongs.
+ /// For example, if this node has a sub domain, the real next node is
+ /// the smallest node in the sub domain tree.
+ ///
+ /// If this node is the biggest node within the subtree, this method
+ /// returns \c NULL_NODE().
+ ///
+ /// This method never throws an exception.
+ const RBNode<T>* successor() const;
+
/// \name Data to maintain the rbtree structure.
//@{
RBNode<T>* parent_;
@@ -239,6 +259,169 @@ template <typename T>
RBNode<T>::~RBNode() {
}
+template <typename T>
+const RBNode<T>*
+RBNode<T>::successor() const {
+ const RBNode<T>* current = this;
+ // If it has right node, the successor is the left-most node of the right
+ // subtree.
+ if (right_ != NULL_NODE()) {
+ current = right_;
+ while (current->left_ != NULL_NODE()) {
+ current = current->left_;
+ }
+ return (current);
+ }
+
+
+ // 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 RBNode<T>* parent = current->parent_;
+ while (parent != NULL_NODE() && current == parent->right_) {
+ current = parent;
+ parent = parent->parent_;
+ }
+ return (parent);
+}
+
+
+/// \brief RBTreeNodeChain is used to keep track of the sequence of
+/// nodes to reach any given node from the root of RBTree.
+///
+/// Currently, RBNode does not have "up" pointers in them (i.e., back pointers
+/// from the root of one level of tree of trees to the node in the parent
+/// tree whose down pointer points to that root node) for memory usage
+/// reasons, so there is no other way to find the path back to the root from
+/// any given RBNode.
+///
+/// \note This design may change in future versions. In particular, it's
+/// quite likely we want to have that pointer if we want to optimize name
+/// compression by exploiting the structure of the zone. If and when that
+/// happens we should also revisit the need for the chaining.
+///
+/// RBTreeNodeChain is constructed and manipulated only inside the \c RBTree
+/// class.
+/// \c RBTree uses it as an inner data structure to iterate over the whole
+/// RBTree.
+/// This is the reason why manipulation methods such as \c push() and \c pop()
+/// are private (and not shown in the doxygen document).
+template <typename T>
+class RBTreeNodeChain {
+ /// RBTreeNodeChain is initialized by RBTree, only RBTree has
+ /// knowledge to manipuate it.
+ friend class RBTree<T>;
+public:
+ /// \name Constructors and Assignment Operator.
+ ///
+ /// \note The copy constructor and the assignment operator are
+ /// intentionally defined as private, making this class non copyable.
+ /// This may have to be changed in a future version with newer need.
+ /// For now we explicitly disable copy to avoid accidental copy happens
+ /// unintentionally.
+ //{@
+ /// The default constructor.
+ ///
+ /// \exception None
+ RBTreeNodeChain() : node_count_(0) {}
+
+private:
+ RBTreeNodeChain(const RBTreeNodeChain<T>&);
+ RBTreeNodeChain<T>& operator=(const RBTreeNodeChain<T>&);
+ //@}
+
+public:
+ /// \brief Return the number of levels stored in the chain.
+ ///
+ /// It's equal to the number of nodes in the chain; for an empty
+ /// chain, 0 will be returned.
+ ///
+ /// \exception None
+ unsigned int getLevelCount() const { return (node_count_); }
+
+ /// \brief return the absolute name for the node which this
+ /// \c RBTreeNodeChain currently refers to.
+ ///
+ /// The chain must not be empty.
+ ///
+ /// \exception isc::BadValue the chain is empty.
+ /// \exception std::bad_alloc memory allocation for the new name fails.
+ isc::dns::Name getAbsoluteName() const {
+ if (isEmpty()) {
+ isc_throw(isc::BadValue,
+ "RBTreeNodeChain::getAbsoluteName is called on an empty "
+ "chain");
+ }
+
+ const RBNode<T>* top_node = top();
+ isc::dns::Name absolute_name = top_node->getName();
+ int node_count = node_count_ - 1;
+ while (node_count > 0) {
+ top_node = nodes_[node_count - 1];
+ absolute_name = absolute_name.concatenate(top_node->getName());
+ --node_count;
+ }
+ return (absolute_name);
+ }
+
+private:
+ // the following private functions check invariants about the internal
+ // state using assert() instead of exception. The state of a chain
+ // can only be modified operations within this file, so if any of the
+ // assumptions fails it means an internal bug.
+
+ /// \brief return whther node chain has node in it.
+ ///
+ /// \exception None
+ bool isEmpty() const { return (node_count_ == 0); }
+
+ /// \brief return the top node for the node chain
+ ///
+ /// RBTreeNodeChain store all the nodes along top node to
+ /// root node of RBTree
+ ///
+ /// \exception None
+ const RBNode<T>* top() const {
+ assert(!isEmpty());
+ return (nodes_[node_count_ - 1]);
+ }
+
+ /// \brief pop the top node from the node chain
+ ///
+ /// After pop, up/super node of original top node will be
+ /// the top node
+ ///
+ /// \exception None
+ void pop() {
+ assert(!isEmpty());
+ --node_count_;
+ }
+
+ /// \brief add the node into the node chain
+ ///
+ /// If the node chain isn't empty, the node should be
+ /// the sub domain of the original top node in node chain
+ /// otherwise the node should be the root node of RBTree.
+ ///
+ /// \exception None
+ void push(const RBNode<T>* node) {
+ assert(node_count_ < RBT_MAX_LEVEL);
+ nodes_[node_count_++] = node;
+ }
+
+private:
+ // The max label count for one domain name is Name::MAX_LABELS (128).
+ // Since each node in rbtree stores at least one label, and the root
+ // name always shares the same level with some others (which means
+ // all top level nodes except the one for the root name contain at least
+ // two labels), the possible maximum level is MAX_LABELS - 1.
+ // It's also the possible maximum nodes stored in a chain.
+ const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS - 1;
+
+ const RBNode<T>* nodes_[RBT_MAX_LEVEL];
+ int node_count_;
+};
+
// note: the following class description is documented using multiline comments
// because the verbatim diagram contain a backslash, which could be interpreted
@@ -258,11 +441,16 @@ RBNode<T>::~RBNode() {
* - Decreases the memory footprint, as it doesn't store the suffix labels
* multiple times.
*
- * Depending on different usage, rbtree will support different search policy.
- * Whether return empty node to end user is one policy among them. Search
- * policy is as the last template parameter, the default policy will NOT
- * return empty node to end user, pass ture will get empty node during find
- * is needed
+ * Depending on different usage, rbtree will support different search policies.
+ * Whether to return an empty node to end user is one policy among them.
+ * The default policy is to NOT return an empty node to end user;
+ * to change the behavior, specify \c true for the constructor parameter
+ * \c returnEmptyNode.
+ * \note The search policy only affects the \c find() behavior of RBTree.
+ * When inserting one name into RBTree, if the node with the name already
+ * exists in the RBTree and it's an empty node which doesn't have any data,
+ * the \c insert() method will still return \c ALREADYEXISTS regardless of
+ * the search policy.
*
* \anchor diagram
*
@@ -277,7 +465,7 @@ RBNode<T>::~RBNode() {
* - p.w.y.d.e.f
* - q.w.y.d.e.f
*
- * the tree will looks like:
+ * the tree will look like:
* \verbatim
b
/ \
@@ -297,10 +485,8 @@ RBNode<T>::~RBNode() {
* - add remove interface
* - add iterator to iterate over the whole \c RBTree. This may be necessary,
* for example, to support AXFR.
- * - since \c RBNode only has down pointer without up pointer, the node path
- * during finding should be recorded for later use
*/
-template <typename T, bool returnEmptyNode = false>
+template <typename T>
class RBTree : public boost::noncopyable {
friend class RBNode<T>;
public:
@@ -320,7 +506,7 @@ public:
/// The constructor.
///
/// It never throws an exception.
- explicit RBTree();
+ explicit RBTree(bool returnEmptyNode = false);
/// \b Note: RBTree is not intended to be inherited so the destructor
/// is not virtual
@@ -333,22 +519,25 @@ public:
///
/// \anchor find
///
- /// These methods search the RBTree for a node whose name is a longest
+ /// These methods search the RBTree for a node whose name is longest
/// against name. The found node, if any, is returned via the node pointer.
///
/// By default, nodes that don't have data (see RBNode::isEmpty) are
/// ignored and the result can be NOTFOUND even if there's a node whose
- /// name mathes. The plan is to introduce a "no data OK" mode for this
- /// method, that would match any node of the tree regardless of wheather
- /// the node has any data or not.
+ /// name matches. If the \c RBTree is constructed with its
+ /// \c returnEmptyNode parameter being \c true, an empty node will also
+ /// be match candidates.
///
- /// The case with "no data OK" mode is not as easy as it seems. For example
- /// in the diagram shown in the class description, the name y.d.e.f is
- /// logically contained in the tree as part of the node w.y. It cannot be
- /// identified simply by checking whether existing nodes (such as
- /// d.e.f or w.y) has data.
+ /// \note Even when \c returnEmptyNode is \c true, not all empty nodes
+ /// in terms of the DNS protocol may necessarily be found by this method.
+ /// For example, in the \ref diagram shown in the class description,
+ /// the name y.d.e.f is logically contained in the tree as part of the
+ /// node w.y, but the \c find() variants cannot find the former for
+ /// the search key of y.d.e.f, no matter how the \c RBTree is constructed.
+ /// The caller of this method must use a different way to identify the
+ /// hidden match when necessary.
///
- /// These methods involves operations on names that can throw an exception.
+ /// These methods involve operations on names that can throw an exception.
/// If that happens the exception will be propagated to the caller.
/// The callback function should generally not throw an exception, but
/// if it throws, the exception will be propagated to the caller.
@@ -369,13 +558,39 @@ public:
/// of it. In that case, node parameter is left intact.
//@{
- /// \brief Find with callback.
+ /// \brief Simple find.
+ ///
+ /// Acts as described in the \ref find section.
+ Result find(const isc::dns::Name& name, RBNode<T>** node) const {
+ RBTreeNodeChain<T> node_path;
+ return (find<void*>(name, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Simple find returning immutable node.
///
- /// \anchor callback
+ /// Acts as described in the \ref find section, but returns immutable node
+ /// pointer.
+ Result find(const isc::dns::Name& name, const RBNode<T>** node) const {
+ RBTreeNodeChain<T> node_path;
+ RBNode<T> *target_node = NULL;
+ Result ret = (find<void*>(name, &target_node, node_path, NULL, NULL));
+ if (ret != NOTFOUND) {
+ *node = target_node;
+ }
+ return (ret);
+ }
+
+ /// \brief Find with callback and node chain.
///
- /// This version of find calls the callback whenever traversing (on the
- /// way from root down the tree) a marked node on the way down through the
- /// domain namespace (see RBNode::enableCallback and related functions).
+ /// This version of \c find() is specifically designed for the backend
+ /// of the \c MemoryZone class, and implements all necessary features
+ /// for that purpose. Other applications shouldn't need these additional
+ /// features, and should normally use the simpler versions.
+ ///
+ /// This version of \c find() calls the callback whenever traversing (on
+ /// the way from root down the tree) a marked node on the way down through
+ /// the domain namespace (see RBNode::enableCallback and related
+ /// functions).
///
/// If you return true from the callback, the search is stopped and a
/// PARTIALMATCH is returned with the given node. Note that this node
@@ -388,9 +603,32 @@ public:
/// The callbacks are not general functors for the same reason - we don't
/// expect it to be needed.
///
+ /// Another special feature of this version is the ability to provide
+ /// a node chain containing a path to the found node. The chain will be
+ /// returned via the \c node_path parameter.
+ /// The passed parameter must be empty.
+ /// On success, it will contain all the ancestor nodes from the found
+ /// node towards the root.
+ /// For example, if we look for o.w.y.d.e.f in the example \ref diagram,
+ /// \c node_path will contain w.y and d.e.f; the \c top() node of the
+ /// chain will be o, w.f and d.e.f will be stored below it.
+ ///
+ /// This feature can be used to get the absolute name for a node;
+ /// to do so, we need to travel upside from the node toward the root,
+ /// concatenating all ancestor names. With the current implementation
+ /// it's not possible without a node chain, because there is a no pointer
+ /// from the root of a subtree to the parent subtree (this may change
+ /// in a future version). A node chain can also be used to find the next
+ /// node of a given node in the entire RBTree; the \c nextNode() method
+ /// takes a node chain as a parameter.
+ ///
+ /// \exception isc::BadValue node_path is not empty.
+ ///
/// \param name Target to be found
/// \param node On success (either \c EXACTMATCH or \c PARTIALMATCH)
/// it will store a pointer to the matching node
+ /// \param node_path It will store all the ancestor nodes in the RBTree
+ /// from the found node to the root. The found node is stored.
/// \param callback If non \c NULL, a call back function to be called
/// at marked nodes (see above).
/// \param callback_arg A caller supplied argument to be passed to
@@ -399,33 +637,57 @@ public:
/// \return As described above, but in case of callback returning true,
/// it returns immediately with the current node.
template <typename CBARG>
- Result find(const isc::dns::Name& name, RBNode<T>** node,
+ Result find(const isc::dns::Name& name,
+ RBNode<T>** node,
+ RBTreeNodeChain<T>& node_path,
bool (*callback)(const RBNode<T>&, CBARG),
CBARG callback_arg) const;
- /// \brief Find with callback returning immutable node.
+ /// \brief Simple find returning immutable node.
///
- /// It has the same behaviour as the find with \ref callback version.
+ /// Acts as described in the \ref find section, but returns immutable
+ /// node pointer.
template <typename CBARG>
- Result find(const isc::dns::Name& name, const RBNode<T>** node,
+ Result find(const isc::dns::Name& name,
+ const RBNode<T>** node,
+ RBTreeNodeChain<T>& node_path,
bool (*callback)(const RBNode<T>&, CBARG),
- CBARG callback_arg) const;
-
- /// \brief Simple find.
- ///
- /// Acts as described in the \ref find section.
- Result find(const isc::dns::Name& name, RBNode<T>** node) const {
- return (find<void*>(name, node, NULL, NULL));
+ CBARG callback_arg) const
+ {
+ RBNode<T>* target_node = NULL;
+ Result ret = find(name, &target_node, node_path, callback,
+ callback_arg);
+ if (ret != NOTFOUND) {
+ *node = target_node;
+ }
+ return (ret);
}
+ //@}
- /// \brieg Simple find returning immutable node.
+ /// \brief return the next bigger node in DNSSEC order from a given node
+ /// chain.
///
- /// Acts as described in the \ref find section, but returns immutable node
- /// pointer.
- Result find(const isc::dns::Name& name, const RBNode<T>** node) const {
- return (find<void*>(name, node, NULL, NULL));
- }
- //@}
+ /// This method identifies the next bigger node of the node currently
+ /// referenced in \c node_path and returns it.
+ /// This method also updates the passed \c node_path so that it will store
+ /// the path for the returned next node.
+ /// It will be convenient when we want to iterate over the all nodes
+ /// of \c RBTree; we can do this by calling this method repeatedly
+ /// starting from the root node.
+ ///
+ /// \note \c nextNode() will iterate over all the nodes in RBTree including
+ /// empty nodes. If empty node isn't desired, it's easy to add logic to
+ /// check return node and keep invoking \c nextNode() until the non-empty
+ /// node is retrieved.
+ ///
+ /// \exception isc::BadValue node_path is empty.
+ ///
+ /// \param node_path A node chain that stores all the nodes along the path
+ /// from root to node.
+ ///
+ /// \return An \c RBNode that is next bigger than \c node; if \c node is
+ /// the largest, \c NULL will be returned.
+ const RBNode<T>* nextNode(RBTreeNodeChain<T>& node_path) const;
/// \brief Get the total number of nodes in the tree
///
@@ -502,23 +764,11 @@ private:
//@{
/// \brief delete tree whose root is equal to node
void deleteHelper(RBNode<T> *node);
- /// \brief find the node with name
- ///
- /// Internal searching function.
- ///
- /// \param name What should be found.
- /// \param up It will point to the node whose down pointer points
- /// to the tree containing node. If we looked for o.w.y.d.e.f in the
- /// \ref diagram, the up would point to the w.y node.
- /// This parameter is not used currently, but it will be soon.
- /// \param node The found node.
- template <typename CBARG>
- Result findHelper(const isc::dns::Name& name, const RBNode<T>** up,
- RBNode<T>** node,
- bool (*callback)(const RBNode<T>&, CBARG),
- CBARG callback_arg) const;
+
+ /// \brief Print the information of given RBNode.
void dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
unsigned int depth) const;
+
/// \brief Indentation helper function for dumpTree
static void indent(std::ostream& os, unsigned int depth);
@@ -529,39 +779,43 @@ private:
void nodeFission(RBNode<T>& node, const isc::dns::Name& sub_name);
//@}
- RBNode<T>* root_;
RBNode<T>* NULLNODE;
+ RBNode<T>* root_;
/// the node count of current tree
unsigned int node_count_;
+ /// search policy for rbtree
+ const bool needsReturnEmptyNode_;
};
-template <typename T, bool S>
-RBTree<T,S>::RBTree() {
- NULLNODE = RBNode<T>::NULL_NODE();
- root_ = NULLNODE;
- node_count_ = 0;
+template <typename T>
+RBTree<T>::RBTree(bool returnEmptyNode) :
+ NULLNODE(RBNode<T>::NULL_NODE()),
+ root_(NULLNODE),
+ node_count_(0),
+ needsReturnEmptyNode_(returnEmptyNode)
+{
}
-template <typename T, bool S>
-RBTree<T,S>::~RBTree() {
+template <typename T>
+RBTree<T>::~RBTree() {
deleteHelper(root_);
assert(node_count_ == 0);
}
-template <typename T, bool S>
-void
-RBTree<T,S>::deleteHelper(RBNode<T> *root) {
+template <typename T>
+void
+RBTree<T>::deleteHelper(RBNode<T>* root) {
if (root == NULLNODE) {
return;
}
- RBNode<T> *node = root;
+ RBNode<T>* node = root;
while (root->left_ != NULLNODE || root->right_ != NULLNODE) {
while (node->left_ != NULLNODE || node->right_ != NULLNODE) {
node = (node->left_ != NULLNODE) ? node->left_ : node->right_;
}
- RBNode<T> *parent = node->parent_;
+ RBNode<T>* parent = node->parent_;
if (parent->left_ == node) {
parent->left_ = NULLNODE;
} else {
@@ -579,48 +833,23 @@ RBTree<T,S>::deleteHelper(RBNode<T> *root) {
--node_count_;
}
-template <typename T, bool S>
+template <typename T>
template <typename CBARG>
-typename RBTree<T,S>::Result
-RBTree<T,S>::find(const isc::dns::Name& name, RBNode<T>** node,
+typename RBTree<T>::Result
+RBTree<T>::find(const isc::dns::Name& target_name,
+ RBNode<T>** target,
+ RBTreeNodeChain<T>& node_path,
bool (*callback)(const RBNode<T>&, CBARG),
CBARG callback_arg) const
{
- const RBNode<T>* up_node = NULLNODE;
- return (findHelper(name, &up_node, node, callback, callback_arg));
-}
+ using namespace helper;
-template <typename T, bool S>
-template <typename CBARG>
-typename RBTree<T,S>::Result
-RBTree<T,S>::find(const isc::dns::Name& name, const RBNode<T>** node,
- bool (*callback)(const RBNode<T>&, CBARG),
- CBARG callback_arg) const
-{
- const RBNode<T>* up_node;
- RBNode<T>* target_node;
- const typename RBTree<T,S>::Result ret =
- findHelper(name, &up_node, &target_node, callback, callback_arg);
- if (ret != NOTFOUND) {
- *node = target_node;
+ if (!node_path.isEmpty()) {
+ isc_throw(isc::BadValue, "RBTree::find is given a non empty chain");
}
- return (ret);
-}
-
-template <typename T, bool returnEmptyNode>
-template <typename CBARG>
-typename RBTree<T,returnEmptyNode>::Result
-RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
- const RBNode<T>** up_node,
- RBNode<T>** target,
- bool (*callback)(const RBNode<T>&, CBARG),
- CBARG callback_arg) const
-{
- using namespace helper;
RBNode<T>* node = root_;
- typename RBTree<T,returnEmptyNode>::Result ret = NOTFOUND;
- *up_node = NULLNODE;
+ Result ret = NOTFOUND;
isc::dns::Name name = target_name;
while (node != NULLNODE) {
@@ -629,7 +858,8 @@ RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
const isc::dns::NameComparisonResult::NameRelation relation =
compare_result.getRelation();
if (relation == isc::dns::NameComparisonResult::EQUAL) {
- if (returnEmptyNode || !node->isEmpty()) {
+ if (needsReturnEmptyNode_ || !node->isEmpty()) {
+ node_path.push(node);
*target = node;
ret = EXACTMATCH;
}
@@ -642,8 +872,8 @@ RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
node = (compare_result.getOrder() < 0) ?
node->left_ : node->right_;
} else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
- if (returnEmptyNode || !node->isEmpty()) {
- ret = RBTree<T,returnEmptyNode>::PARTIALMATCH;
+ if (needsReturnEmptyNode_ || !node->isEmpty()) {
+ ret = PARTIALMATCH;
*target = node;
if (callback != NULL && node->callback_required_) {
if ((callback)(*node, callback_arg)) {
@@ -651,7 +881,7 @@ RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
}
}
}
- *up_node = node;
+ node_path.push(node);
name = name - node->name_;
node = node->down_;
} else {
@@ -663,11 +893,54 @@ RBTree<T,returnEmptyNode>::findHelper(const isc::dns::Name& target_name,
return (ret);
}
+template <typename T>
+const RBNode<T>*
+RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const {
+ if (node_path.isEmpty()) {
+ isc_throw(isc::BadValue, "RBTree::nextNode is given an empty chain");
+ }
+
+ const RBNode<T>* node = node_path.top();
+ // if node has sub domain, the next domain is the smallest
+ // domain in sub domain tree
+ if (node->down_ != NULLNODE) {
+ const RBNode<T>* left_most = node->down_;
+ while (left_most->left_ != NULLNODE) {
+ left_most = left_most->left_;
+ }
+ node_path.push(left_most);
+ return (left_most);
+ }
+
+ // node_path go to up level
+ node_path.pop();
+ // otherwise found the successor node in current level
+ const RBNode<T>* successor = node->successor();
+ if (successor != NULLNODE) {
+ node_path.push(successor);
+ return (successor);
+ }
+
+ // if no successor found move to up level, the next successor
+ // is the successor of up node in the up level tree, if
+ // up node doesn't have successor we gonna keep moving to up
+ // level
+ while (!node_path.isEmpty()) {
+ const RBNode<T>* up_node_successor = node_path.top()->successor();
+ node_path.pop();
+ if (up_node_successor != NULLNODE) {
+ node_path.push(up_node_successor);
+ return (up_node_successor);
+ }
+ }
+
+ return (NULL);
+}
+
-template <typename T, bool returnEmptyNode>
-typename RBTree<T,returnEmptyNode>::Result
-RBTree<T,returnEmptyNode>::insert(const isc::dns::Name& target_name,
- RBNode<T>** new_node) {
+template <typename T>
+typename RBTree<T>::Result
+RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
using namespace helper;
RBNode<T>* parent = NULLNODE;
RBNode<T>* current = root_;
@@ -684,12 +957,7 @@ RBTree<T,returnEmptyNode>::insert(const isc::dns::Name& target_name,
if (new_node != NULL) {
*new_node = current;
}
-
- if (current->isEmpty() && !returnEmptyNode) {
- return (SUCCESS);
- } else {
- return (ALREADYEXISTS);
- }
+ return (ALREADYEXISTS);
} else {
const int common_label_count = compare_result.getCommonLabels();
if (common_label_count == 1) {
@@ -746,9 +1014,9 @@ RBTree<T,returnEmptyNode>::insert(const isc::dns::Name& target_name,
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
+RBTree<T>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
using namespace helper;
const isc::dns::Name sub_name = node.name_ - base_name;
// using auto_ptr here is to avoid memory leak in case of exception raised
@@ -769,9 +1037,9 @@ RBTree<T,S>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
+RBTree<T>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* uncle;
while (node != *root && node->parent_->color_ == RBNode<T>::RED) {
@@ -815,9 +1083,9 @@ RBTree<T,S>::insertRebalance(RBNode<T>** root, RBNode<T>* node) {
}
-template <typename T, bool S>
+template <typename T>
RBNode<T>*
-RBTree<T,S>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
+RBTree<T>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* right = node->right_;
node->right_ = right->left_;
if (right->left_ != NULLNODE)
@@ -840,9 +1108,9 @@ RBTree<T,S>::leftRotate(RBNode<T>** root, RBNode<T>* node) {
return (node);
}
-template <typename T, bool S>
+template <typename T>
RBNode<T>*
-RBTree<T,S>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
+RBTree<T>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
RBNode<T>* left = node->left_;
node->left_ = left->right_;
if (left->right_ != NULLNODE)
@@ -865,17 +1133,17 @@ RBTree<T,S>::rightRotate(RBNode<T>** root, RBNode<T>* node) {
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::dumpTree(std::ostream& os, unsigned int depth) const {
+RBTree<T>::dumpTree(std::ostream& os, unsigned int depth) const {
indent(os, depth);
os << "tree has " << node_count_ << " node(s)\n";
dumpTreeHelper(os, root_, depth);
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
+RBTree<T>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
unsigned int depth) const
{
if (node == NULLNODE) {
@@ -900,15 +1168,13 @@ RBTree<T,S>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
dumpTreeHelper(os, node->right_, depth + 1);
}
-template <typename T, bool S>
+template <typename T>
void
-RBTree<T,S>::indent(std::ostream& os, unsigned int depth) {
+RBTree<T>::indent(std::ostream& os, unsigned int depth) {
static const unsigned int INDENT_FOR_EACH_DEPTH = 5;
os << std::string(depth * INDENT_FOR_EACH_DEPTH, ' ');
}
-
-
}
}
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 0105cad..24d94a3 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -15,6 +15,8 @@
#include <gtest/gtest.h>
+#include <exceptions/exceptions.h>
+
#include <dns/name.h>
#include <dns/rrclass.h>
#include <dns/rrset.h>
@@ -26,10 +28,15 @@
#include <dns/tests/unittest_util.h>
using namespace std;
+using namespace isc;
using namespace isc::dns;
using isc::UnitTestUtil;
using namespace isc::datasrc;
+// XXX: some compilers cannot find class static constants used in
+// EXPECT_xxx macros, for which we need an explicit empty definition.
+const size_t Name::MAX_LABELS;
+
/* The initial structure of rbtree
*
* b
@@ -50,9 +57,10 @@ using namespace isc::datasrc;
namespace {
class RBTreeTest : public::testing::Test {
protected:
- RBTreeTest() : rbtree() {
- const char * 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"};
+ RBTreeTest() : rbtree_expose_empty_node(true) {
+ 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"};
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);
@@ -65,8 +73,7 @@ protected:
}
RBTree<int> rbtree;
- typedef RBTree<int, true> ExposeRBTree;
- ExposeRBTree rbtree_expose_empty_node;
+ RBTree<int> rbtree_expose_empty_node;
RBNode<int>* rbtnode;
const RBNode<int>* crbtnode;
};
@@ -82,69 +89,34 @@ TEST_F(RBTreeTest, setGetData) {
}
TEST_F(RBTreeTest, insertNames) {
- //if don't expose empty node, even the node already exsit which is caused by node fission
- //we will return succeed
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("d.e.f"), &rbtnode));
+ 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(ExposeRBTree::ALREADYEXISTS,
- rbtree_expose_empty_node.insert(Name("d.e.f"), &rbtnode));
- EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
- EXPECT_EQ(13, rbtree_expose_empty_node.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(ExposeRBTree::SUCCESS, rbtree_expose_empty_node.insert(
- Name("."), &rbtnode));
- EXPECT_EQ(Name("."), rbtnode->getName());
- EXPECT_EQ(14, rbtree_expose_empty_node.getNodeCount());
-
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("example.com"), &rbtnode));
EXPECT_EQ(15, rbtree.getNodeCount());
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(12)));
- EXPECT_EQ(ExposeRBTree::SUCCESS, rbtree_expose_empty_node.insert(
- Name("example.com"), &rbtnode));
- EXPECT_EQ(15, rbtree_expose_empty_node.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(ExposeRBTree::ALREADYEXISTS,
- rbtree_expose_empty_node.insert(Name("example.com"), &rbtnode));
- EXPECT_EQ(15, rbtree_expose_empty_node.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(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("k.e.f"), &rbtnode));
- EXPECT_EQ(Name("k"), rbtnode->getName());
- EXPECT_EQ(17, rbtree_expose_empty_node.getNodeCount());
-
-
// split the node "g.h"
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("h"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("h"), &rbtnode));
EXPECT_EQ(Name("h"), rbtnode->getName());
EXPECT_EQ(18, rbtree.getNodeCount());
- //node fission will create node "h"
- EXPECT_EQ(ExposeRBTree::ALREADYEXISTS,
- rbtree_expose_empty_node.insert(Name("h"), &rbtnode));
- EXPECT_EQ(Name("h"), rbtnode->getName());
- EXPECT_EQ(18, rbtree_expose_empty_node.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());
@@ -153,41 +125,18 @@ TEST_F(RBTreeTest, insertNames) {
EXPECT_EQ(Name("n"), rbtnode->getName());
EXPECT_EQ(20, rbtree.getNodeCount());
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("m.p.w.y.d.e.f"), &rbtnode));
- EXPECT_EQ(Name("m"), rbtnode->getName());
- EXPECT_EQ(19, rbtree_expose_empty_node.getNodeCount());
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("n.p.w.y.d.e.f"), &rbtnode));
- EXPECT_EQ(Name("n"), rbtnode->getName());
- EXPECT_EQ(20, rbtree_expose_empty_node.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(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("l.a"), &rbtnode));
- EXPECT_EQ(Name("l"), rbtnode->getName());
- EXPECT_EQ(21, rbtree_expose_empty_node.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(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("r.d.e.f"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("s.d.e.f"), &rbtnode));
- EXPECT_EQ(23, rbtree_expose_empty_node.getNodeCount());
-
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("h.w.y.d.e.f"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("h.w.y.d.e.f"), &rbtnode));
// add more nodes one by one to cover leftRotate and rightRotate
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("f"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("m"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("nm"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("om"), &rbtnode));
@@ -198,32 +147,8 @@ TEST_F(RBTreeTest, insertNames) {
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("i"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("ae"), &rbtnode));
EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("n"), &rbtnode));
-
- EXPECT_EQ(ExposeRBTree::ALREADYEXISTS,
- rbtree_expose_empty_node.insert(Name("f"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("m"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("nm"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("om"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("k"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("l"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("fe"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("ge"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("i"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("ae"), &rbtnode));
- EXPECT_EQ(ExposeRBTree::SUCCESS,
- rbtree_expose_empty_node.insert(Name("n"), &rbtnode));
}
-
TEST_F(RBTreeTest, findName) {
// find const rbtnode
// exact match
@@ -236,15 +161,33 @@ TEST_F(RBTreeTest, findName) {
EXPECT_EQ(RBTree<int>::NOTFOUND, rbtree.find(Name("x"), &crbtnode));
EXPECT_EQ(RBTree<int>::NOTFOUND, rbtree.find(Name("m.n"), &crbtnode));
+ // if we expose empty node, we can get the empty node created during insert
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree_expose_empty_node.find(Name("d.e.f"), &crbtnode));
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree_expose_empty_node.find(Name("w.y.d.e.f"), &crbtnode));
+
// partial match
EXPECT_EQ(RBTree<int>::PARTIALMATCH, rbtree.find(Name("m.b"), &crbtnode));
EXPECT_EQ(Name("b"), crbtnode->getName());
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
+ rbtree_expose_empty_node.find(Name("m.d.e.f"), &crbtnode));
// find rbtnode
EXPECT_EQ(RBTree<int>::EXACTMATCH, rbtree.find(Name("q.w.y.d.e.f"), &rbtnode));
EXPECT_EQ(Name("q"), rbtnode->getName());
}
+TEST_F(RBTreeTest, findError) {
+ // For the version that takes a node chain, the chain must be empty.
+ RBTreeNodeChain<int> chain;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH, rbtree.find<void*>(Name("a"), &crbtnode,
+ chain, NULL, NULL));
+ // trying to reuse the same chain. it should result in an exception.
+ EXPECT_THROW(rbtree.find<void*>(Name("a"), &crbtnode, chain, NULL, NULL),
+ BadValue);
+}
+
bool
testCallback(const RBNode<int>&, bool* callack_checker) {
*callack_checker = true;
@@ -272,7 +215,7 @@ TEST_F(RBTreeTest, callback) {
&subrbtnode));
subrbtnode->setData(RBNode<int>::NodeDataPtr(new int(2)));
RBNode<int>* parentrbtnode;
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("example"),
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("example"),
&parentrbtnode));
// the chilld/parent nodes shouldn't "inherit" the callback flag.
// "rbtnode" may be invalid due to the insertion, so we need to re-find
@@ -284,22 +227,121 @@ TEST_F(RBTreeTest, callback) {
EXPECT_FALSE(parentrbtnode->isCallbackEnabled());
// check if the callback is called from find()
+ RBTreeNodeChain<int> node_path1;
bool callback_called = false;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- rbtree.find(Name("sub.callback.example"), &crbtnode,
+ rbtree.find(Name("sub.callback.example"), &crbtnode, node_path1,
testCallback, &callback_called));
EXPECT_TRUE(callback_called);
// enable callback at the parent node, but it doesn't have data so
// the callback shouldn't be called.
+ RBTreeNodeChain<int> node_path2;
parentrbtnode->enableCallback();
callback_called = false;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- rbtree.find(Name("callback.example"), &crbtnode,
+ rbtree.find(Name("callback.example"), &crbtnode, node_path2,
testCallback, &callback_called));
EXPECT_FALSE(callback_called);
}
+TEST_F(RBTreeTest, chainLevel) {
+ RBTreeNodeChain<int> chain;
+
+ // by default there should be no level in the chain.
+ EXPECT_EQ(0, chain.getLevelCount());
+
+ // insert one node to the tree and find it. there should be exactly
+ // one level in the chain.
+ RBTree<int> tree(true);
+ Name node_name(Name::ROOT_NAME());
+ EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find<void*>(node_name, &crbtnode, chain, NULL, NULL));
+ EXPECT_EQ(1, chain.getLevelCount());
+
+ /*
+ * Now creating a possibly deepest tree with MAX_LABELS - 1 levels.
+ * it should look like:
+ * a
+ * /|
+ * (.)a
+ * |
+ * a
+ * : (MAX_LABELS - 1) "a"'s
+ *
+ * then confirm that find() for the deepest name succeeds without any
+ * disruption, and the resulting chain has the expected level.
+ * Note that "a." and the root name (".") belong to the same level.
+ * So the possible maximum level is MAX_LABELS - 1, not MAX_LABELS.
+ */
+ for (unsigned int i = 1; i < Name::MAX_LABELS; ++i) {
+ node_name = Name("a.").concatenate(node_name);
+ EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
+ RBTreeNodeChain<int> found_chain;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ tree.find<void*>(node_name, &crbtnode, found_chain,
+ NULL, NULL));
+ EXPECT_EQ(i, found_chain.getLevelCount());
+ }
+
+ // Confirm the last inserted name has the possible maximum length with
+ // maximum label count. This confirms the rbtree and chain level cannot
+ // be larger.
+ EXPECT_EQ(Name::MAX_LABELS, node_name.getLabelCount());
+ EXPECT_THROW(node_name.concatenate(Name("a.")), TooLongName);
+}
+
+TEST_F(RBTreeTest, getAbsoluteNameError) {
+ // an empty chain isn't allowed.
+ RBTreeNodeChain<int> chain;
+ 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
+ * b
+ * / \
+ * a d.e.f
+ * / | \
+ * c | g.h
+ * | |
+ * w.y i
+ * / | \
+ * x | z
+ * | |
+ * p j
+ * / \
+ * o q
+ */
+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,
+ rbtree.find<void*>(Name(names[0]), &node, node_path, NULL,
+ NULL));
+ for (int i = 0; i < name_count; ++i) {
+ EXPECT_NE(static_cast<void*>(NULL), node);
+ EXPECT_EQ(Name(names[i]), node_path.getAbsoluteName());
+ node = rbtree.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+}
+
+TEST_F(RBTreeTest, nextNodeError) {
+ // Empty chain for nextNode() is invalid.
+ RBTreeNodeChain<int> chain;
+ EXPECT_THROW(rbtree.nextNode(chain), BadValue);
+}
+
TEST_F(RBTreeTest, dumpTree) {
std::ostringstream str;
std::ostringstream str2;
@@ -336,5 +378,4 @@ TEST_F(RBTreeTest, swap) {
tree2.dumpTree(out);
ASSERT_EQ(str1.str(), out.str());
}
-
}
More information about the bind10-changes
mailing list