BIND 10 master, updated. c149373122712acd20af00d9e327e9449e4f81f3 Merge branch 'master' into trac2105
BIND 10 source code commits
bind10-changes at lists.isc.org
Fri Aug 3 14:40:38 UTC 2012
The branch, master has been updated
via c149373122712acd20af00d9e327e9449e4f81f3 (commit)
via 2b062467de80d3fe2b3b255aed7f63a86ebd1d12 (commit)
via 13b16c09be05bd131dc7777e184035eed25e4617 (commit)
via 0ea32d7945125ac037b5914d7d0eea26960b92af (commit)
via 65976ab225438e0c1d295308f761d71b4c9a1e11 (commit)
via 9d416b80baba0fd5f44a8944fe219be49b4726ae (commit)
via 1319a26ec4a087dd154ee18270b708a12a205b15 (commit)
via 5eb12ef1deafb9fd9fd9ebfa722b5cd2b3b1d8ba (commit)
via ce3394fbd4d882fede52165151bad75459f1b7b1 (commit)
via 1fdb15bd59af353bf113ec3edafa5e372c740c3e (commit)
via ad0d2ac48fbafbf2f887a1144eab043c68eea52b (commit)
via 9dfe0921460b8b36ba6e08f40988bc0782435843 (commit)
via ff3f282be61fe6b5ec9f6a72c69375988ea7eeea (commit)
via 26d871cfc6ab5012937b0ca060e60e5871fb620a (commit)
from 862b15fc77654a9baf86106b26932335a50e22c4 (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 c149373122712acd20af00d9e327e9449e4f81f3
Merge: 2b06246 862b15f
Author: Mukund Sivaraman <muks at isc.org>
Date: Fri Aug 3 19:57:55 2012 +0530
Merge branch 'master' into trac2105
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/Makefile.am | 6 +-
src/lib/datasrc/{rbtree.h => memory/domaintree.h} | 925 +++++++++++---------
src/lib/datasrc/memory/tests/Makefile.am | 1 +
.../tests/domaintree_unittest.cc} | 805 ++++++++---------
4 files changed, 876 insertions(+), 861 deletions(-)
copy src/lib/datasrc/{rbtree.h => memory/domaintree.h} (69%)
copy src/lib/datasrc/{tests/rbtree_unittest.cc => memory/tests/domaintree_unittest.cc} (50%)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/Makefile.am b/src/lib/datasrc/memory/Makefile.am
index 0b061b6..90ab7b8 100644
--- a/src/lib/datasrc/memory/Makefile.am
+++ b/src/lib/datasrc/memory/Makefile.am
@@ -9,4 +9,8 @@ AM_CXXFLAGS = $(B10_CXXFLAGS)
CLEANFILES = *.gcno *.gcda datasrc_messages.h datasrc_messages.cc
noinst_LTLIBRARIES = libdatasrc_memory.la
-libdatasrc_memory_la_SOURCES = rdata_encoder.h rdata_encoder.cc
+
+libdatasrc_memory_la_SOURCES = \
+ rdata_encoder.h \
+ rdata_encoder.cc \
+ domaintree.h
diff --git a/src/lib/datasrc/memory/domaintree.h b/src/lib/datasrc/memory/domaintree.h
new file mode 100644
index 0000000..ad8f085
--- /dev/null
+++ b/src/lib/datasrc/memory/domaintree.h
@@ -0,0 +1,2038 @@
+// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC")
+//
+// Permission to use, copy, modify, and/or distribute this software for any
+// purpose with or without fee is hereby granted, provided that the above
+// copyright notice and this permission notice appear in all copies.
+//
+// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
+// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
+// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
+// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+// PERFORMANCE OF THIS SOFTWARE.
+
+#ifndef _DOMAINTREE_H
+#define _DOMAINTREE_H 1
+
+//! \file datasrc/memory/domaintree.h
+///
+/// \note The purpose of the DomainTree is to provide a generic map with
+/// domain names as the key that can be used by various BIND 10
+/// modules or even by other applications. However, because of some
+/// unresolved design issue, the design and interface are not fixed,
+/// and DomainTree isn't ready to be used as a base data structure
+/// by other modules.
+
+#include <exceptions/exceptions.h>
+#include <util/memory_segment.h>
+#include <dns/name.h>
+#include <dns/labelsequence.h>
+
+#include <boost/utility.hpp>
+#include <boost/shared_ptr.hpp>
+#include <boost/interprocess/offset_ptr.hpp>
+#include <boost/static_assert.hpp>
+
+#include <ostream>
+#include <algorithm>
+#include <cassert>
+
+namespace isc {
+namespace datasrc {
+namespace memory {
+
+/// Forward declare DomainTree class here is convinent for following
+/// friend class declare inside DomainTreeNode and DomainTreeNodeChain
+template <typename T, typename DT>
+class DomainTree;
+
+/// \brief \c DomainTreeNode is used by DomainTree to store any data
+/// related to one domain name.
+///
+/// This is meant to be used only from DomainTree. It is meaningless to
+/// inherit it or create instances of it from elsewhere. For that
+/// reason, the constructor (and the allocator, see below) is private.
+///
+/// It serves three roles. One is to keep structure of the \c DomainTree
+/// as a red-black tree. For that purpose, it has left, right and parent
+/// pointers and color member. These are private and accessed only from
+/// within the tree.
+///
+/// The second one is to store data for one domain name. The data
+/// related functions can be used to access and set the data.
+///
+/// The third role is to keep the hierarchy of domains. The down pointer
+/// points to a subtree of subdomains. The parent pointer of a subtree's
+/// root node points to the parent leaf of the upper tree.
+///
+/// One special kind of node is non-terminal node. It has subdomains
+/// with RRsets, but doesn't have any RRsets itself.
+///
+/// In order to keep memory footprint as small as possible, the node
+/// data are heavily packed. Specifically, some internal node
+/// properties (such as the node color) are encoded as part of "flags",
+/// some of the flag bits can also be set by the user application. Each
+/// node is associated with a sequence of domain name labels, which is
+/// essentially the search/insert key for the node (see also the
+/// description of DomainTree). This is encoded as opaque binary
+/// immediately following the main node object. The size of the
+/// allocated space for the labels data is encoded by borrowing some
+/// bits of the "flags" field.
+template <typename T, typename DT>
+class DomainTreeNode : public boost::noncopyable {
+private:
+ /// The DomainTreeNode is meant for use from within DomainTree, so
+ /// it has access to it.
+ friend class DomainTree<T, DT>;
+
+ /// \brief Just a type alias
+ ///
+ /// We are going to use a lot of these offset pointers here and they
+ /// have a long name.
+ typedef boost::interprocess::offset_ptr<DomainTreeNode<T, DT> >
+ DomainTreeNodePtr;
+
+ /// \name Constructors
+ ///
+ /// \note The existence of a DomainTreeNode without a DomainTree is
+ /// meaningless. Therefore the constructors are private.
+ //@{
+
+ /// \brief Constructor from normal nodes.
+ DomainTreeNode(size_t labels_capacity);
+
+ /// \brief Destructor
+ ~DomainTreeNode();
+
+ //@}
+
+ /// \brief Accessor to the memory region for node labels.
+ ///
+ /// The only valid usage of the returned pointer is to pass it to
+ /// the corresponding constructor of \c dns::LabelSequence.
+ const void* getLabelsData() const { return (this + 1); }
+
+ /// \brief Accessor to the memory region for node labels, mutable version.
+ ///
+ /// The only valid usage of the returned pointer is to pass it to
+ /// \c LabelSequence::serialize() with the node's labels_capacity_ member
+ /// (which should be sufficiently large for the \c LabelSequence in that
+ /// context).
+ void* getLabelsData() { return (this + 1); }
+
+ /// \brief Allocate and construct \c DomainTreeNode
+ ///
+ /// This static method allocates memory for a new \c DomainTreeNode
+ /// object from the given memory segment, constructs the object, and
+ /// returns a pointer to it.
+ ///
+ /// \throw std::bad_alloc Memory allocation fails.
+ ///
+ /// \param mem_sgmt A \c MemorySegment from which memory for the new
+ /// \c DomainTreeNode is allocated.
+ static DomainTreeNode<T, DT>* create(util::MemorySegment& mem_sgmt,
+ const dns::LabelSequence& labels)
+ {
+ const size_t labels_len = labels.getSerializedLength();
+ void* p = mem_sgmt.allocate(sizeof(DomainTreeNode<T, DT>) + labels_len);
+ DomainTreeNode<T, DT>* node = new(p) DomainTreeNode<T, DT>(labels_len);
+ labels.serialize(node->getLabelsData(), labels_len);
+ return (node);
+ }
+
+ /// \brief Destruct and deallocate \c DomainTreeNode
+ ///
+ /// \throw none
+ ///
+ /// \param mem_sgmt The \c MemorySegment that allocated memory for
+ /// \c node.
+ /// \param node A non NULL pointer to a valid \c DomainTreeNode object
+ /// that was originally created by the \c create() method (the behavior
+ /// is undefined if this condition isn't met).
+ static void destroy(util::MemorySegment& mem_sgmt,
+ DomainTreeNode<T, DT>* node) {
+ const size_t labels_capacity = node->labels_capacity_;
+ node->~DomainTreeNode<T, DT>();
+ mem_sgmt.deallocate(node,
+ sizeof(DomainTreeNode<T, DT>) + labels_capacity);
+ }
+
+ /// \brief Reset node's label sequence to a new one.
+ ///
+ /// The new labels must be a sub sequence of the current label sequence;
+ /// otherwise the serialize() method will throw an exception.
+ void resetLabels(const dns::LabelSequence& labels) {
+ labels.serialize(getLabelsData(), labels_capacity_);
+ }
+
+public:
+ /// Node flags.
+ ///
+ /// Each flag value defines a non default property for a specific node.
+ /// These are defined as bitmask type values for the convenience of
+ /// internal implementation, but applications are expected to use
+ /// each flag separately via the enum definitions.
+ ///
+ /// All (settable) flags are off by default; they must be explicitly
+ /// set to on by the \c setFlag() method.
+ enum Flags {
+ FLAG_CALLBACK = 1, ///< Callback enabled. See \ref callback
+ FLAG_RED = 2, ///< Node color; 1 if node is red, 0 if node is black.
+ FLAG_SUBTREE_ROOT = 4, ///< Set if the node is the root of a subtree
+ FLAG_USER1 = 0x400000U, ///< Application specific flag
+ FLAG_USER2 = 0x200000U, ///< Application specific flag
+ FLAG_USER3 = 0x100000U, ///< Application specific flag
+ FLAG_MAX = 0x400000U // for integrity check
+ };
+private:
+ // Some flag values are expected to be used for internal purposes
+ // (e.g., representing the node color) in future versions, so we
+ // limit the settable flags via the \c setFlag() method to those
+ // explicitly defined in \c Flags. This constant represents all
+ // such flags.
+ static const uint32_t SETTABLE_FLAGS = (FLAG_CALLBACK | FLAG_USER1 |
+ FLAG_USER2 | FLAG_USER3);
+
+public:
+
+ /// \name Getter functions.
+ //@{
+ /// \brief Return the name of current node.
+ ///
+ /// It's relative to its containing node.
+ ///
+ /// To get the absolute name of one node, the node path from the top node
+ /// to current node has to be recorded.
+ ///
+ /// \note We should eventually deprecate this method and revise all its
+ /// usage with \c getLabels(). At this point the only user of this method
+ /// is getAbsoluteName()::getAbsoluteName(), which would have to be revised
+ /// using \c LabelSequence. Until then we keep this interface as a
+ /// simplest form of wrapper; it's not efficient, but should be replaced
+ /// before we need to worry about that.
+ const isc::dns::Name getName() const {
+ return (dns::Name(dns::LabelSequence(getLabelsData()).toText()));
+ }
+
+ /// \brief Return the label sequence of the node.
+ ///
+ /// This method returns the label sequence corresponding to this node
+ /// in the form of \c dns::LabelSequence object. Any modification to
+ /// the tree can invalidate the returned \c LabelSequence object or copy
+ /// of it; in general, it's expected to be used in a very limited scope.
+ dns::LabelSequence getLabels() const {
+ return (dns::LabelSequence(getLabelsData()));
+ }
+
+ /// \brief Return the data stored in this node.
+ ///
+ /// You should not delete the data, it is deleted when the tree is
+ /// destroyed.
+ T* getData() { return (data_); }
+
+ /// \brief Return the data stored in this node (const).
+ const T* getData() const { return (data_); }
+
+ /// \brief return whether the node has related data.
+ ///
+ /// There can be empty nodes inside the DomainTree. They are usually the
+ /// non-terminal domains, but it is possible (yet probably meaningless)
+ /// empty nodes anywhere.
+ bool isEmpty() const { return (data_ == NULL); }
+ //@}
+
+ /// \name Setter functions.
+ //@{
+
+ /// \brief Set the data stored in the node. If there is old data, it
+ /// is either returned or destroyed based on what is passed in \c
+ /// old_data.
+ /// \param mem_sgmt The \c MemorySegment that allocated memory for
+ /// the node data.
+ /// \param data The new data to set.
+ /// \param old_data If \c NULL is passed here, any old data is
+ /// destroyed. Otherwise, the old data is returned
+ /// in this location.
+ void setData(util::MemorySegment& mem_sgmt, T* data, T** old_data = NULL) {
+ if (old_data != NULL) {
+ *old_data = data;
+ } else {
+ const DT deleter;
+ deleter(mem_sgmt, data_);
+ }
+ data_ = data;
+ }
+ //@}
+
+ /// \name Node flag manipulation methods
+ //@{
+ /// Get the status of a node flag.
+ ///
+ /// This method returns whether the given node flag is set (enabled)
+ /// on the node. The \c flag parameter is expected to be one of the
+ /// defined \c Flags constants. For simplicity, the method interface
+ /// does not prohibit passing an undefined flag or combined flags, but
+ /// the return value in such a case will be meaningless for the caller
+ /// (an application would have to use an ugly cast for such an unintended
+ /// form of call, which will hopefully avoid accidental misuse).
+ ///
+ /// \exception None
+ /// \param flag The flag to be tested.
+ /// \return \c true if the \c flag is set; \c false otherwise.
+ bool getFlag(Flags flag) const {
+ return ((flags_ & flag) != 0);
+ }
+
+ /// Set or clear a node flag.
+ ///
+ /// This method changes the status of the specified node flag to either
+ /// "on" (enabled) or "off" (disabled). The new status is specified by
+ /// the \c on parameter.
+ /// Like the \c getFlag() method, \c flag is expected to be one of the
+ /// defined \c Flags constants. If an undefined or unsettable flag is
+ /// specified, \c isc::InvalidParameter exception will be thrown.
+ ///
+ /// \exception isc::InvalidParameter Unsettable flag is specified
+ /// \exception None otherwise
+ /// \param flag The node flag to be changed.
+ /// \param on If \c true, set the flag to on; otherwise set it to off.
+ void setFlag(Flags flag, bool on = true) {
+ if ((flag & ~SETTABLE_FLAGS) != 0) {
+ isc_throw(isc::InvalidParameter,
+ "Unsettable DomainTree flag is being set");
+ }
+ if (on) {
+ flags_ |= flag;
+ } else {
+ flags_ &= ~flag;
+ }
+ }
+ //@}
+
+private:
+ /// \name Callback related methods
+ ///
+ /// See the description of \c DomainTree<T, DT>::find() at \ref callback
+ /// about callbacks.
+ ///
+ /// These methods never throw an exception.
+ //@{
+ /// Return if callback is enabled at the node.
+ //@}
+
+
+ /// \brief Define node color
+ enum DomainTreeNodeColor {BLACK, RED};
+
+ /// \brief Returns the color of this node
+ DomainTreeNodeColor getColor() const {
+ if ((flags_ & FLAG_RED) != 0) {
+ return (RED);
+ } else {
+ return (BLACK);
+ }
+ }
+
+ /// \brief Sets the color of this node
+ void setColor(const DomainTreeNodeColor color) {
+ if (color == RED) {
+ flags_ |= FLAG_RED;
+ } else {
+ flags_ &= ~FLAG_RED;
+ }
+ }
+
+ void setSubTreeRoot(bool root) {
+ if (root) {
+ flags_ |= FLAG_SUBTREE_ROOT;
+ } else {
+ flags_ &= ~FLAG_SUBTREE_ROOT;
+ }
+ }
+
+ bool isSubTreeRoot() const {
+ return ((flags_ & FLAG_SUBTREE_ROOT) != 0);
+ }
+
+public:
+ /// \brief returns the parent of the root of its subtree
+ ///
+ /// This method takes a node and returns the parent of the root of
+ /// its subtree (i.e, it returns the node's immediate ancestor in
+ /// the tree-of-tree hierarchy). If the node is at the top level
+ /// (which should be absolute), it will return \c NULL.
+ ///
+ /// This method never throws an exception.
+ const DomainTreeNode<T, DT>* getUpperNode() const;
+
+private:
+ /// \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 DomainTree;
+ /// DomainTree 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.
+ ///
+ /// This method never throws an exception.
+ const DomainTreeNode<T, DT>* successor() const;
+
+ /// \brief return the next node which is smaller than current node
+ /// in the same subtree
+ ///
+ /// The predecessor for this node is the next smaller node in terms of
+ /// the DNSSEC order relation within the same single subtree.
+ /// Note that it may NOT be the next smaller node in the entire DomainTree;
+ /// DomainTree 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 the predecessor node has a sub domain, the real next
+ /// node is the largest node in the sub domain tree.
+ ///
+ /// If this node is the smallest node within the subtree, this method
+ /// returns \c NULL.
+ ///
+ /// This method never throws an exception.
+ const DomainTreeNode<T, DT>* predecessor() const;
+
+ /// \brief private shared implementation of successor and predecessor
+ ///
+ /// As the two mentioned functions are merely mirror images of each other,
+ /// it makes little sense to keep both versions. So this is the body of the
+ /// functions and we call it with the correct pointers.
+ ///
+ /// Not to be called directly, not even by friends.
+ ///
+ /// 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, DT>*
+ abstractSuccessor(typename DomainTreeNode<T, DT>::DomainTreeNodePtr
+ DomainTreeNode<T, DT>::*left,
+ typename DomainTreeNode<T, DT>::DomainTreeNodePtr
+ DomainTreeNode<T, DT>::*right)
+ const;
+
+ /// \name Data to maintain the rbtree structure.
+ ///
+ /// We keep them as offset pointers. This is part of a future plan, when we
+ /// want to share the image of the tree between multiple processes.
+ /// However, whenever we have a chance, we switch to bare pointers during
+ /// the processing. The pointers on stack are never shared and the offset
+ /// pointers have non-trivial performance impact.
+ //@{
+ DomainTreeNodePtr parent_;
+ /// \brief Access the parent_ as bare pointer.
+ DomainTreeNode<T, DT>* getParent() {
+ return (parent_.get());
+ }
+ /// \brief Access the parent_ as bare pointer, const.
+ const DomainTreeNode<T, DT>* getParent() const {
+ return (parent_.get());
+ }
+ DomainTreeNodePtr left_;
+ /// \brief Access the left_ as bare pointer.
+ DomainTreeNode<T, DT>* getLeft() {
+ return (left_.get());
+ }
+ /// \brief Access the left_ as bare pointer, const.
+ const DomainTreeNode<T, DT>* getLeft() const {
+ return (left_.get());
+ }
+ DomainTreeNodePtr right_;
+ /// \brief Access the right_ as bare pointer.
+ DomainTreeNode<T, DT>* getRight() {
+ return (right_.get());
+ }
+ /// \brief Access the right_ as bare pointer, const.
+ const DomainTreeNode<T, DT>* getRight() const {
+ return (right_.get());
+ }
+ //@}
+
+ /// \brief The subdomain tree.
+ ///
+ /// This points to the root node of trees of subdomains of this domain.
+ ///
+ /// \par Adding down pointer to \c DomainTreeNode has two purposes:
+ /// \li Accelerate the search process, with sub domain tree, it splits the
+ /// big flat tree into several hierarchy trees.
+ /// \li It saves memory usage as it allows storing only relative names,
+ /// avoiding storage of the same domain labels multiple times.
+ DomainTreeNodePtr down_;
+ /// \brief Access the down_ as bare pointer.
+ DomainTreeNode<T, DT>* getDown() {
+ return (down_.get());
+ }
+ /// \brief Access the down_ as bare pointer, const.
+ const DomainTreeNode<T, DT>* getDown() const {
+ return (down_.get());
+ }
+
+ /// \brief Data stored here.
+ T* data_;
+
+ /// \brief Internal or user-configurable flags of node's properties.
+ ///
+ /// See the \c Flags enum for available flags.
+ ///
+ /// For memory efficiency reasons, we only use a subset of the 32-bit
+ /// space, and use the rest to store the allocated size for the node's
+ /// label sequence data.
+ uint32_t flags_ : 23; // largest flag being 0x400000
+ BOOST_STATIC_ASSERT((1 << 23) > FLAG_MAX); // assumption check
+
+ const uint32_t labels_capacity_ : 9; // size for labelseq; range is 0..511
+ // Make sure the reserved space for labels_capacity_ is sufficiently
+ // large. In effect, we use the knowledge of the implementation of the
+ // serialization, but we still only use its public interface, and the
+ // public interface of this class doesn't rely on this assumption.
+ // So we can change this implementation without affecting its users if
+ // a future change to LabelSequence breaks this assumption.
+ BOOST_STATIC_ASSERT((1 << 9) > dns::LabelSequence::MAX_SERIALIZED_LENGTH);
+};
+
+template <typename T, typename DT>
+DomainTreeNode<T, DT>::DomainTreeNode(size_t labels_capacity) :
+ parent_(NULL),
+ left_(NULL),
+ right_(NULL),
+ down_(NULL),
+ data_(NULL),
+ flags_(FLAG_RED | FLAG_SUBTREE_ROOT),
+ labels_capacity_(labels_capacity)
+{
+}
+
+template <typename T, typename DT>
+DomainTreeNode<T, DT>::~DomainTreeNode() {
+}
+
+template <typename T, typename DT>
+const DomainTreeNode<T, DT>*
+DomainTreeNode<T, DT>::getUpperNode() const {
+ const DomainTreeNode<T, DT>* current = this;
+
+ // current would never be equal to NULL here (in a correct tree
+ // implementation)
+ while (!current->isSubTreeRoot()) {
+ current = current->getParent();
+ }
+
+ return (current->getParent());
+}
+
+template <typename T, typename DT>
+const DomainTreeNode<T, DT>*
+DomainTreeNode<T, DT>::abstractSuccessor(typename DomainTreeNode<T, DT>::DomainTreeNodePtr
+ DomainTreeNode<T, DT>::*left,
+ typename DomainTreeNode<T, DT>::DomainTreeNodePtr
+ DomainTreeNode<T, DT>::*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, DT>* 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();
+ const DomainTreeNode<T, DT>* left_n;
+ while ((left_n = (current->*left).get()) != NULL) {
+ current = left_n;
+ }
+ 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 DomainTreeNode<T, DT>* parent = current->getParent();
+ while ((!current->isSubTreeRoot()) &&
+ (current == (parent->*right).get())) {
+ current = parent;
+ parent = parent->getParent();
+ }
+
+ if (!current->isSubTreeRoot()) {
+ return (parent);
+ } else {
+ return (NULL);
+ }
+}
+
+template <typename T, typename DT>
+const DomainTreeNode<T, DT>*
+DomainTreeNode<T, DT>::successor() const {
+ return (abstractSuccessor(&DomainTreeNode<T, DT>::left_,
+ &DomainTreeNode<T, DT>::right_));
+}
+
+template <typename T, typename DT>
+const DomainTreeNode<T, DT>*
+DomainTreeNode<T, DT>::predecessor() const {
+ // Swap the left and right pointers for the abstractSuccessor
+ return (abstractSuccessor(&DomainTreeNode<T, DT>::right_,
+ &DomainTreeNode<T, DT>::left_));
+}
+
+/// \brief DomainTreeNodeChain stores detailed information of \c
+/// DomainTree::find() result.
+///
+/// - The \c DomainTreeNode that was last compared with the search name, and
+/// the comparison result at that point in the form of
+/// \c isc::dns::NameComparisonResult.
+/// - A sequence of nodes that forms a path to the found node.
+///
+/// The comparison result can be used to handle some rare cases such as
+/// empty node processing.
+/// The node sequence keeps track of the nodes to reach any given node from
+/// the root of DomainTree.
+///
+/// Currently, DomainTreeNode 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 DomainTreeNode.
+///
+/// \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.
+/// Also, the class name may not be appropriate now that it contains other
+/// information than a node "chain", and the chain itself may even be
+/// deprecated. Something like "DomainTreeFindContext" may be a better name.
+/// This point should be revisited later.
+///
+/// DomainTreeNodeChain is constructed and manipulated only inside the
+/// \c DomainTree class.
+/// \c DomainTree uses it as an inner data structure to iterate over the whole
+/// DomainTree.
+/// 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, typename DT>
+class DomainTreeNodeChain {
+ /// DomainTreeNodeChain is initialized by DomainTree, only DomainTree has
+ /// knowledge to manipulate it.
+ friend class DomainTree<T, DT>;
+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
+ DomainTreeNodeChain() : node_count_(0), last_compared_(NULL),
+ // XXX: meaningless initial values:
+ last_comparison_(0, 0,
+ isc::dns::NameComparisonResult::EQUAL)
+ {}
+
+private:
+ DomainTreeNodeChain(const DomainTreeNodeChain<T, DT>&);
+ DomainTreeNodeChain<T, DT>& operator=(const DomainTreeNodeChain<T, DT>&);
+ //@}
+
+public:
+ /// Clear the state of the chain.
+ ///
+ /// This method re-initializes the internal state of the chain so that
+ /// it can be reused for subsequent operations.
+ ///
+ /// \exception None
+ void clear() {
+ node_count_ = 0;
+ last_compared_ = NULL;
+ }
+
+ /// Return the \c DomainTreeNode that was last compared in \c
+ /// DomainTree::find().
+ ///
+ /// If this chain has been passed to \c DomainTree::find() and there
+ /// has been name comparison against the search name, the last
+ /// compared \c DomainTreeNode is recorded within the chain. This
+ /// method returns that node.
+ ///
+ /// If \c DomainTree::find() hasn't been called with this chain or
+ /// name comparison hasn't taken place (which is possible if the
+ /// tree is empty), this method returns \c NULL.
+ ///
+ /// \exception None
+ const DomainTreeNode<T, DT>* getLastComparedNode() const {
+ return (last_compared_);
+ }
+
+ /// Return the result of last name comparison in \c DomainTree::find().
+ ///
+ /// Like \c getLastComparedNode(), \c DomainTree::find() records the result
+ /// of the last name comparison in the chain. This method returns the
+ /// result.
+ /// The return value of this method is only meaningful when comparison
+ /// has taken place, i.e, when \c getLastComparedNode() would return a
+ /// non \c NULL value.
+ ///
+ /// \exception None
+ const isc::dns::NameComparisonResult& getLastComparisonResult() const {
+ return (last_comparison_);
+ }
+
+ /// \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 DomainTreeNodeChain 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,
+ "DomainTreeNodeChain::getAbsoluteName is "
+ "called on an empty chain");
+ }
+
+ const DomainTreeNode<T, DT>* 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 by operations within this file, so if any of the
+ // assumptions fails it means an internal bug.
+
+ /// \brief return whether node chain has node in it.
+ ///
+ /// \exception None
+ bool isEmpty() const { return (node_count_ == 0); }
+
+ /// \brief return the top node for the node chain
+ ///
+ /// DomainTreeNodeChain store all the nodes along top node to
+ /// root node of DomainTree
+ ///
+ /// \exception None
+ const DomainTreeNode<T, DT>* 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 DomainTree.
+ ///
+ /// \exception None
+ void push(const DomainTreeNode<T, DT>* 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 domaintree stores at least one label,
+ // it's also equal to the possible maximum level.
+ const static int RBT_MAX_LEVEL = isc::dns::Name::MAX_LABELS;
+
+ int node_count_;
+ const DomainTreeNode<T, DT>* nodes_[RBT_MAX_LEVEL];
+ const DomainTreeNode<T, DT>* last_compared_;
+ isc::dns::NameComparisonResult last_comparison_;
+};
+
+
+// note: the following class description is documented using multiline comments
+// because the verbatim diagram contain a backslash, which could be interpreted
+// as escape of newline in singleline comment.
+/**
+ * \brief \c DomainTree class represents all the domains with the same suffix.
+ * It can be used to store the domains in one zone, for example.
+ *
+ * DomainTree is a generic map from domain names to any kind of
+ * data. Internally, it uses a red-black tree. However, it isn't one
+ * tree containing everything. Subdomains are trees, so this structure
+ * is recursive - trees inside trees. But, from the interface point of
+ * view, it is opaque data structure.
+ *
+ * \c DomainTree splits the domain space into hierarchy red black trees; nodes
+ * in one tree has the same base name. The benefit of this struct is that:
+ * - Enhances the query performance compared with one big flat red black tree.
+ * - Decreases the memory footprint, as it doesn't store the suffix labels
+ * multiple times.
+ *
+ * Depending on different usage, domaintree 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 DomainTree.
+ * When inserting one name into DomainTree, if the node with the name already
+ * exists in the DomainTree 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.
+ *
+ * The template parameters taken by \c DomainTree are \c T (the type of
+ * data which is stored by the tree) and \c DT (a type whose instance is
+ * used to destroy data stored in the tree). <code>operator()</code> is
+ * called on a \c DT instance and passed a pointer to the data
+ * (<code>T*</code>) to be destroyed. This method should be written to
+ * accept \c NULL arguments.
+ *
+ * \anchor diagram
+ *
+ * with the following names:
+ * - a
+ * - b
+ * - c
+ * - x.d.e.f
+ * - z.d.e.f
+ * - g.h
+ * - o.w.y.d.e.f
+ * - p.w.y.d.e.f
+ * - q.w.y.d.e.f
+ *
+ * the tree will look like:
+ * \verbatim
+ .
+ |
+ b
+ / \
+ a d.e.f
+ /|\
+ c | g.h
+ |
+ w.y
+ /|\
+ x | z
+ |
+ p
+ / \
+ o q
+ \endverbatim
+ * \todo
+ * - add remove interface
+ */
+template <typename T, typename DT>
+class DomainTree : public boost::noncopyable {
+ friend class DomainTreeNode<T, DT>;
+public:
+ /// \brief The return value for the \c find() and insert() methods
+ enum Result {
+ SUCCESS, ///< Insert was successful
+ /// \brief The node returned from find mathes exactly the name given
+ EXACTMATCH,
+ PARTIALMATCH, ///< A superdomain node was found
+ NOTFOUND, ///< Not even any superdomain was found
+ /// \brief Returned by insert() if a node of the name already exists
+ ALREADYEXISTS,
+ };
+
+ /// \brief Allocate and construct \c DomainTree
+ ///
+ /// This static method allocates memory for a new \c DomainTree object
+ /// from the given memory segment, constructs the object, and returns
+ /// a pointer to it.
+ ///
+ /// \throw std::bad_alloc Memory allocation fails.
+ ///
+ /// \param mem_sgmt A \c MemorySegment from which memory for the new
+ /// \c DomainTree is allocated.
+ static DomainTree* create(util::MemorySegment& mem_sgmt,
+ bool return_empty_node = false)
+ {
+ void* p = mem_sgmt.allocate(sizeof(DomainTree<T, DT>));
+ return (new(p) DomainTree<T, DT>(return_empty_node));
+ }
+
+ /// \brief Destruct and deallocate \c DomainTree
+ ///
+ /// This method also destroys and deallocates all nodes inserted to the
+ /// tree.
+ ///
+ /// \note The memory segment (\c mem_sgmt) must be the same one that
+ /// was originally used to allocate memory for the tree (and for all
+ /// nodes inserted to the tree, due to the requirement of \c insert()),
+ /// since the tree itself doesn't maintain a reference to the segment.
+ /// This is not a robust interface, but since we plan to share the tree
+ /// structure by multiple processes via shared memory or possibly allow
+ /// the memory image to be dumped to a file for later reload, there
+ /// doesn't seem to be an easy way to store such reference in the data
+ /// itself. We should probably consider a wrapper interface that
+ /// encapsulates the corresponding segment and always use it for any
+ /// allocation/deallocation of tree related data (the tree itself, their
+ /// nodes, and node data) to keep the usage as safe as possible.
+ ///
+ /// \throw none
+ ///
+ /// \param mem_sgmt The \c MemorySegment that allocated memory for
+ /// \c tree and for all nodes inserted to the tree.
+ /// \param tree A non NULL pointer to a valid \c DomainTree object
+ /// that was originally created by the \c create() method (the behavior
+ /// is undefined if this condition isn't met).
+ static void destroy(util::MemorySegment& mem_sgmt,
+ DomainTree<T, DT>* tree) {
+ tree->deleteAllNodes(mem_sgmt);
+ tree->~DomainTree<T, DT>();
+ mem_sgmt.deallocate(tree, sizeof(DomainTree<T, DT>));
+ }
+
+private:
+ /// \name Constructor and Destructor
+ //@{
+ /// \brief The constructor.
+ ///
+ /// An object of this class is always expected to be created by the
+ /// allocator (\c create()), so the constructor is hidden as private.
+ ///
+ /// It never throws an exception.
+ explicit DomainTree(bool returnEmptyNode = false);
+
+ /// \brief The destructor.
+ ///
+ /// An object of this class is always expected to be destroyed explicitly
+ /// by \c destroy(), so the constructor is hidden as private.
+ ///
+ /// \note DomainTree is not intended to be inherited so the destructor
+ /// is not virtual
+ ~DomainTree();
+ //@}
+
+public:
+
+ /// \name Find methods
+ ///
+ /// \brief Find the node that gives a longest match against the given name.
+ ///
+ /// \anchor find
+ ///
+ /// These methods search the DomainTree 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
+ /// DomainTreeNode::isEmpty) are ignored and the result can be
+ /// NOTFOUND even if there's a node whose name matches. If the \c
+ /// DomainTree is constructed with its \c returnEmptyNode parameter
+ /// being \c true, empty nodes will also be match candidates.
+ ///
+ /// \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 DomainTree is constructed. The caller of this method
+ /// must use a different way to identify the hidden match when
+ /// necessary.
+ ///
+ /// 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.
+ ///
+ /// The \c name parameter says what should be found. The node parameter
+ /// is output-only, and in case of EXACTMATCH or PARTIALMATCH, it is set
+ /// to a pointer to the found node.
+ ///
+ /// They return:
+ /// - EXACTMATCH when a node with the same name as requested exists.
+ /// - PARTIALMATCH when a node with the same name does not exist (or is
+ /// empty), but there's a (nonempty) superdomain of the requested one.
+ /// The superdomain with longest name is returned through the node
+ /// parameter. Beware that if you store a zone in the tree, you may get
+ /// PARTIALMATCH with zone apex when the given domain name is not there.
+ /// You should not try to delegate into another zone in that case.
+ /// - NOTFOUND if there's no node with the same name nor any superdomain
+ /// 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,
+ DomainTreeNode<T, DT>** node) const {
+ DomainTreeNodeChain<T, DT> node_path;
+ const isc::dns::LabelSequence ls(name);
+ return (find<void*>(ls, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Simple find returning immutable node.
+ ///
+ /// Acts as described in the \ref find section, but returns immutable node
+ /// pointer.
+ Result find(const isc::dns::Name& name,
+ const DomainTreeNode<T, DT>** node) const {
+ DomainTreeNodeChain<T, DT> node_path;
+ DomainTreeNode<T, DT> *target_node = NULL;
+ const isc::dns::LabelSequence ls(name);
+ Result ret = (find<void*>(ls, &target_node, node_path, NULL, NULL));
+ if (ret != NOTFOUND) {
+ *node = target_node;
+ }
+ return (ret);
+ }
+
+ /// \brief Simple find, with node_path tracking
+ ///
+ /// Acts as described in the \ref find section.
+ Result find(const isc::dns::Name& name, DomainTreeNode<T, DT>** node,
+ DomainTreeNodeChain<T, DT>& node_path) const
+ {
+ const isc::dns::LabelSequence ls(name);
+ return (find<void*>(ls, node, node_path, NULL, NULL));
+ }
+
+ /// \brief Simple find returning immutable node, with node_path tracking
+ ///
+ /// Acts as described in the \ref find section, but returns immutable node
+ /// pointer.
+ Result find(const isc::dns::Name& name, const DomainTreeNode<T, DT>** node,
+ DomainTreeNodeChain<T, DT>& node_path) const
+ {
+ DomainTreeNode<T, DT> *target_node = NULL;
+ const isc::dns::LabelSequence ls(name);
+ Result ret = (find<void*>(ls, &target_node, node_path, NULL, NULL));
+ if (ret != NOTFOUND) {
+ *node = target_node;
+ }
+ 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, DT>** node,
+ DomainTreeNodeChain<T, DT>& node_path,
+ bool (*callback)(const DomainTreeNode<T, DT>&, CBARG),
+ CBARG callback_arg) const
+ {
+ DomainTreeNode<T, DT>* target_node = NULL;
+ const isc::dns::LabelSequence ls(name);
+ Result ret = find(ls, &target_node, node_path, callback,
+ callback_arg);
+ if (ret != NOTFOUND) {
+ *node = target_node;
+ }
+ return (ret);
+ }
+
+ /// \brief Find with callback and node chain
+ /// \anchor callback
+ ///
+ /// This version of \c find() is specifically designed for the backend
+ /// of the \c InMemoryZoneFinder 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 \c DomainTreeNode::FLAG_CALLBACK).
+ ///
+ /// Also, this version takes a \c LabelSequence object, not a \c Name
+ /// object to be as efficient as possible; operations on the former
+ /// needed for the search are generally much more efficient than those
+ /// for the latter. Since \c Name objects are more commonly used
+ /// in other parts of the implementation, other versions take a \c Name
+ /// and convert it to \c LabelSequence. This conversion is cheap,
+ /// while the other direction isn't, and since there would be cases
+ /// where an implementation primarily handles \c LabelSequence objects
+ /// as an efficient representation of names, it would make most sense
+ /// to provide the interface that takes \c LabelSequence.
+ ///
+ /// If you return true from the callback, the search is stopped and a
+ /// PARTIALMATCH is returned with the given node. Note that this node
+ /// doesn't really need to be the one with longest possible match.
+ ///
+ /// The callback is not called for the node which matches exactly
+ /// (EXACTMATCH is returned). This is typically the last node in the
+ /// traversal during a successful search.
+ ///
+ /// This callback mechanism was designed with zone cut (delegation)
+ /// processing in mind. The marked nodes would be the ones at delegation
+ /// points. It is not expected that any other applications would need
+ /// callbacks; they should use the versions of find without callbacks.
+ /// 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 record
+ /// more detailed information regarding the search result.
+ ///
+ /// This information will be returned via the \c node_path parameter,
+ /// which is an object of class \c DomainTreeNodeChain.
+ /// The passed parameter must be empty.
+ ///
+ /// On success, the node sequence stored in \c node_path 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.y 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 labels. A node chain can also be
+ /// used to find the next and previous nodes of a given node in the
+ /// entire DomainTree; the \c nextNode() and \c previousNode()
+ /// methods take a node chain as a parameter.
+ ///
+ /// \exception isc::BadValue node_path is not empty.
+ ///
+ /// \param target_labels_orig 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 Other search details will be stored (see the
+ /// description)
+ /// \param callback If non- \c NULL, a call back function to be called
+ /// at marked nodes (see the description).
+ /// \param callback_arg A caller supplied argument to be passed to
+ /// \c callback.
+ ///
+ /// \return As in the description, but in case of callback returning
+ /// \c true, it returns immediately with the current node.
+ template <typename CBARG>
+ Result find(const isc::dns::LabelSequence& target_labels_orig,
+ DomainTreeNode<T, DT>** node,
+ DomainTreeNodeChain<T, DT>& node_path,
+ bool (*callback)(const DomainTreeNode<T, DT>&, CBARG),
+ CBARG callback_arg) const;
+
+ /// \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::LabelSequence& target_labels,
+ const DomainTreeNode<T, DT>** node,
+ DomainTreeNodeChain<T, DT>& node_path,
+ bool (*callback)(const DomainTreeNode<T, DT>&, CBARG),
+ CBARG callback_arg) const
+ {
+ DomainTreeNode<T, DT>* target_node = NULL;
+ Result ret = find(target_labels, &target_node, node_path,
+ callback, callback_arg);
+ if (ret != NOTFOUND) {
+ *node = target_node;
+ }
+ return (ret);
+ }
+ //@}
+
+ /// \brief return the next bigger node in DNSSEC order from a given node
+ /// chain.
+ ///
+ /// 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 DomainTree; we can do this by calling this method repeatedly
+ /// starting from the root node.
+ ///
+ /// \note \c nextNode() will iterate over all the nodes in
+ /// DomainTree 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 DomainTreeNode that is next bigger than \c node;
+ /// if \c node is the largest, \c NULL will be returned.
+ const DomainTreeNode<T, DT>*
+ nextNode(DomainTreeNodeChain<T, DT>& node_path) const;
+
+ /// \brief return the next smaller node in DNSSEC order from a node
+ /// searched by DomainTree::find().
+ ///
+ /// This acts similarly to \c nextNode(), but it walks in the other
+ /// direction. But unlike \c nextNode(), this can start even if the
+ /// node requested by \c find() was not found. In that case, it will
+ /// identify the node that is previous to the queried name.
+ ///
+ /// \note \c previousNode() will iterate over all the nodes in DomainTree
+ /// including empty nodes. If empty node isn't desired, it's easy to add
+ /// logic to check return node and keep invoking \c previousNode() 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 and the result of \c find(). This will get modified.
+ /// You should not use the node_path again except for repetitive calls
+ /// of this method.
+ ///
+ /// \return An \c DomainTreeNode that is next smaller than \c node;
+ /// if \c node is the smallest, \c NULL will be returned.
+ const DomainTreeNode<T, DT>*
+ previousNode(DomainTreeNodeChain<T, DT>& node_path) const;
+
+ /// \brief Get the total number of nodes in the tree
+ ///
+ /// It includes nodes internally created as a result of adding a domain
+ /// name that is a subdomain of an existing node of the tree.
+ /// This function is mainly intended to be used for debugging.
+ int getNodeCount() const { return (node_count_); }
+
+ /// \name Debug function
+ //@{
+ /// \brief Print the nodes in the trees.
+ ///
+ /// \param os A \c std::ostream object to which the tree is printed.
+ /// \param depth A factor of the initial indentation. Each line
+ /// will begin with space character repeating <code>5 * depth</code>
+ /// times.
+ void dumpTree(std::ostream& os, unsigned int depth = 0) const;
+
+ /// \brief Print the nodes in the trees for processing with
+ /// Graphviz's dot.
+ ///
+ /// \param os A \c std::ostream object to which the tree is printed.
+ /// \param show_pointers Show node and parent pointers in the node
+ void dumpDot(std::ostream& os, bool show_pointers = false) const;
+ //@}
+
+ /// \name Modify functions
+ //@{
+ /// \brief Insert the domain name into the tree.
+ ///
+ /// It either finds an already existing node of the given name, or
+ /// inserts a new one if none exists yet. In any case, the \c
+ /// inserted_node parameter is set to point to that node. You can
+ /// fill data into it or modify it. So, if you don't know if a node
+ /// exists or not and you need to modify it, just call insert and
+ /// act by the result.
+ ///
+ /// Please note that the tree can add some empty nodes by itself, so
+ /// don't assume that if you didn't insert a node of that name it
+ /// doesn't exist.
+ ///
+ /// This method normally involves resource allocation. If it fails
+ /// the corresponding standard exception will be thrown.
+ ///
+ /// This method does not provide the strong exception guarantee in its
+ /// strict sense; if an exception is thrown in the middle of this
+ /// method, the internal structure may change. However, it should
+ /// still retain the same property as a mapping container before this
+ /// method is called. For example, the result of \c find() should be
+ /// the same. This method provides the weak exception guarantee in its
+ /// normal sense.
+ ///
+ /// \param mem_sgmt A \c MemorySegment object for allocating memory of
+ /// a new node to be inserted. Must be the same segment as that used
+ /// for creating the tree itself.
+ /// \param name The name to be inserted into the tree.
+ /// \param inserted_node This is an output parameter and is set to the
+ /// node.
+ ///
+ /// \return
+ /// - SUCCESS The node was added.
+ /// - ALREADYEXISTS There was already a node of that name, so it was not
+ /// added.
+ Result insert(util::MemorySegment& mem_sgmt, const isc::dns::Name& name,
+ DomainTreeNode<T, DT>** inserted_node);
+
+ /// \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()).
+ void deleteAllNodes(util::MemorySegment& mem_sgmt);
+
+ /// \brief Swaps two tree's contents.
+ ///
+ /// This and \c other trees must have been created with the same
+ /// memory segment (see the discussion in \c create()); otherwise the
+ /// behavior is undefined.
+ ///
+ /// This acts the same as many std::*.swap functions, exchanges the
+ /// contents. This doesn't throw anything.
+ void swap(DomainTree<T, DT>& other) {
+ std::swap(root_, other.root_);
+ std::swap(node_count_, other.node_count_);
+ }
+ //@}
+
+private:
+ /// \name DomainTree balance functions
+ //@{
+ void
+ insertRebalance(typename DomainTreeNode<T, DT>::DomainTreeNodePtr* root,
+ DomainTreeNode<T, DT>* node);
+
+ DomainTreeNode<T, DT>*
+ rightRotate(typename DomainTreeNode<T, DT>::DomainTreeNodePtr* root,
+ DomainTreeNode<T, DT>* node);
+
+ DomainTreeNode<T, DT>*
+ leftRotate(typename DomainTreeNode<T, DT>::DomainTreeNodePtr* root,
+ DomainTreeNode<T, DT>* node);
+ //@}
+
+ /// \name Helper functions
+ //@{
+ /// \brief delete tree whose root is equal to node
+ void deleteHelper(util::MemorySegment& mem_sgmt,
+ DomainTreeNode<T, DT> *node,
+ const DT& deleter);
+
+ /// \brief Print the information of given DomainTreeNode.
+ void dumpTreeHelper(std::ostream& os, const DomainTreeNode<T, DT>* node,
+ unsigned int depth) const;
+
+ /// \brief Print the information of given DomainTreeNode for dot.
+ int dumpDotHelper(std::ostream& os, const DomainTreeNode<T, DT>* node,
+ int* nodecount, bool show_pointers) const;
+
+ /// \brief Indentation helper function for dumpTree
+ static void indent(std::ostream& os, unsigned int depth);
+
+ /// Split one node into two nodes for "prefix" and "suffix" parts of
+ /// the labels of the original node, respectively. The given node
+ /// will hold the prefix, while a newly created node will hold the prefix.
+ /// Note that the original node still represents the same domain name in
+ /// the entire tree. This ensures that a pointer to a node keeps its
+ /// semantics even if the tree structure is changed (as long as the node
+ /// itself remains valid).
+ void nodeFission(util::MemorySegment& mem_sgmt, DomainTreeNode<T, DT>& node,
+ const isc::dns::LabelSequence& new_prefix,
+ const isc::dns::LabelSequence& new_suffix);
+ //@}
+
+ typename DomainTreeNode<T, DT>::DomainTreeNodePtr root_;
+ /// the node count of current tree
+ unsigned int node_count_;
+ /// search policy for domaintree
+ const bool needsReturnEmptyNode_;
+};
+
+template <typename T, typename DT>
+DomainTree<T, DT>::DomainTree(bool returnEmptyNode) :
+ root_(NULL),
+ node_count_(0),
+ needsReturnEmptyNode_(returnEmptyNode)
+{
+}
+
+template <typename T, typename DT>
+DomainTree<T, DT>::~DomainTree() {
+ assert(node_count_ == 0);
+}
+
+template <typename T, typename DT>
+void
+DomainTree<T, DT>::deleteHelper(util::MemorySegment& mem_sgmt,
+ DomainTreeNode<T, DT>* root,
+ const DT& deleter) {
+ while (root != NULL) {
+ // If there is a left, right or down node, walk into it and
+ // iterate.
+ if (root->getLeft() != NULL) {
+ DomainTreeNode<T, DT>* node = root;
+ root = root->getLeft();
+ node->left_ = NULL;
+ } else if (root->getRight() != NULL) {
+ DomainTreeNode<T, DT>* node = root;
+ root = root->getRight();
+ node->right_ = NULL;
+ } else if (root->getDown() != NULL) {
+ DomainTreeNode<T, DT>* node = root;
+ root = root->getDown();
+ node->down_ = NULL;
+ } else {
+ // There are no left, right or down nodes, so we can
+ // free this one and go back to its parent.
+ DomainTreeNode<T, DT>* node = root;
+ root = root->getParent();
+ deleter(mem_sgmt, node->data_);
+ DomainTreeNode<T, DT>::destroy(mem_sgmt, node);
+ --node_count_;
+ }
+ }
+}
+
+template <typename T, typename DT>
+template <typename CBARG>
+typename DomainTree<T, DT>::Result
+DomainTree<T, DT>::find(const isc::dns::LabelSequence& target_labels_orig,
+ DomainTreeNode<T, DT>** target,
+ DomainTreeNodeChain<T, DT>& node_path,
+ bool (*callback)(const DomainTreeNode<T, DT>&, CBARG),
+ CBARG callback_arg) const
+{
+ if (!node_path.isEmpty()) {
+ isc_throw(isc::BadValue,
+ "DomainTree::find is given a non empty chain");
+ }
+
+ DomainTreeNode<T, DT>* node = root_.get();
+ Result ret = NOTFOUND;
+ dns::LabelSequence target_labels(target_labels_orig);
+
+ while (node != NULL) {
+ node_path.last_compared_ = node;
+ node_path.last_comparison_ = target_labels.compare(node->getLabels());
+ const isc::dns::NameComparisonResult::NameRelation relation =
+ node_path.last_comparison_.getRelation();
+
+ if (relation == isc::dns::NameComparisonResult::EQUAL) {
+ if (needsReturnEmptyNode_ || !node->isEmpty()) {
+ node_path.push(node);
+ *target = node;
+ ret = EXACTMATCH;
+ }
+ break;
+ } else if (relation == isc::dns::NameComparisonResult::NONE) {
+ // If the two labels have no hierarchical relationship in terms
+ // of matching, we should continue the binary search.
+ node = (node_path.last_comparison_.getOrder() < 0) ?
+ node->getLeft() : node->getRight();
+ } else {
+ if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
+ if (needsReturnEmptyNode_ || !node->isEmpty()) {
+ ret = PARTIALMATCH;
+ *target = node;
+ if (callback != NULL &&
+ node->getFlag(DomainTreeNode<T, DT>::FLAG_CALLBACK)) {
+ if ((callback)(*node, callback_arg)) {
+ break;
+ }
+ }
+ }
+ node_path.push(node);
+ target_labels.stripRight(
+ node_path.last_comparison_.getCommonLabels());
+ node = node->getDown();
+ } else {
+ break;
+ }
+ }
+ }
+
+ return (ret);
+}
+
+template <typename T, typename DT>
+const DomainTreeNode<T, DT>*
+DomainTree<T, DT>::nextNode(DomainTreeNodeChain<T, DT>& node_path) const {
+ if (node_path.isEmpty()) {
+ isc_throw(isc::BadValue,
+ "DomainTree::nextNode is given an empty chain");
+ }
+
+ const DomainTreeNode<T, DT>* node = node_path.top();
+ // if node has sub domain, the next domain is the smallest
+ // domain in sub domain tree
+ const DomainTreeNode<T, DT>* down = node->getDown();
+ if (down != NULL) {
+ const DomainTreeNode<T, DT>* left_most = down;
+ while (left_most->getLeft() != NULL) {
+ left_most = left_most->getLeft();
+ }
+ node_path.push(left_most);
+ return (left_most);
+ }
+
+ // try to find a 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 DomainTreeNode<T, DT>* up_node_successor =
+ node_path.top()->successor();
+ node_path.pop();
+ if (up_node_successor != NULL) {
+ node_path.push(up_node_successor);
+ return (up_node_successor);
+ }
+ }
+
+ return (NULL);
+}
+
+template <typename T, typename DT>
+const DomainTreeNode<T, DT>*
+DomainTree<T, DT>::previousNode(DomainTreeNodeChain<T, DT>& node_path) const {
+ if (getNodeCount() == 0) {
+ // Special case for empty trees. It would look every time like
+ // we didn't search, because the last compared is empty. This is
+ // a slight hack and not perfect, but this is better than throwing
+ // on empty tree. And we probably won't meet an empty tree in practice
+ // anyway.
+ return (NULL);
+ }
+ if (node_path.last_compared_ == NULL) {
+ isc_throw(isc::BadValue,
+ "DomainTree::previousNode() called before find()");
+ }
+
+ // If the relation isn't EQUAL, it means the find was called previously
+ // and didn't find the exact node. Therefore we need to locate the place
+ // to start iterating the chain of domains.
+ //
+ // The logic here is not too complex, we just need to take care to handle
+ // all the cases and decide where to go from there.
+ switch (node_path.last_comparison_.getRelation()) {
+ case dns::NameComparisonResult::COMMONANCESTOR:
+ case dns::NameComparisonResult::NONE:
+ // We compared with a leaf in the tree and wanted to go to one of
+ // the children. But the child was not there. It now depends on the
+ // direction in which we wanted to go.
+ if (node_path.last_comparison_.getOrder() < 0) {
+ // We wanted to go left. So the one we compared with is
+ // the one higher than we wanted. If we just put it into
+ // the node_path, then the following algorithm below will find
+ // the smaller one.
+ //
+ // This is exactly the same as with superdomain below.
+ // Therefore, we just fall through to the next case.
+ } else {
+ // We wanted to go right. That means we want to output the
+ // one which is the largest in the tree defined by the
+ // compared one (it is either the compared one, or some
+ // subdomain of it). There probably is not an easy trick
+ // for this, so we just find the correct place.
+ const DomainTreeNode<T, DT>* current(node_path.last_compared_);
+ while (current != NULL) {
+ node_path.push(current);
+ // Go a level down and as much right there as possible
+ current = current->getDown();
+ if (current != NULL) {
+ const DomainTreeNode<T, DT>* right;
+ while ((right = current->getRight()) != NULL) {
+ current = right;
+ }
+ }
+ }
+ // Now, the one on top of the path is the one we want. We
+ // return it now and leave it there, so we can search for
+ // previous of it the next time we'are called.
+ node_path.last_comparison_ =
+ dns::NameComparisonResult(0, 0,
+ dns::NameComparisonResult::EQUAL);
+ return (node_path.top());
+ }
+ // No break; here - we want to fall through. See above.
+ case dns::NameComparisonResult::SUPERDOMAIN:
+ // This is the case there's a "compressed" node and we looked for
+ // only part of it. The node itself is larger than we wanted, but
+ // if we put it to the node_path and then go one step left from it,
+ // we get the correct result.
+ node_path.push(node_path.last_compared_);
+ // Correct the comparison result, so we won't trigger this case
+ // next time previousNode is called. We already located the correct
+ // place to start. The value is partly nonsense, but that doesn't
+ // matter any more.
+ node_path.last_comparison_ =
+ dns::NameComparisonResult(0, 0,
+ dns::NameComparisonResult::EQUAL);
+ break;
+ case dns::NameComparisonResult::SUBDOMAIN:
+ // A subdomain means we returned the one above the searched one
+ // already and it is on top of the stack. This is was smaller
+ // than the one already, but we want to return yet smaller one.
+ // So we act as if it was EQUAL.
+ break;
+ case dns::NameComparisonResult::EQUAL:
+ // The find gave us an exact match or the previousNode was called
+ // already, which located the exact node. The rest of the function
+ // goes one domain left and returns it for us.
+ break;
+ }
+
+ // So, the node_path now contains the path to a node we want previous for.
+ // We just need to go one step left.
+
+ if (node_path.isEmpty()) {
+ // We got past the first one. So, we're returning NULL from
+ // now on.
+ return (NULL);
+ }
+
+ const DomainTreeNode<T, DT>* node(node_path.top());
+
+ // Try going left in this tree
+ node = node->predecessor();
+ if (node == NULL) {
+ // We are the smallest ones in this tree. We go one level
+ // up. That one is the smaller one than us.
+
+ node_path.pop();
+ if (node_path.isEmpty()) {
+ // We're past the first one
+ return (NULL);
+ } else {
+ return (node_path.top());
+ }
+ }
+
+ // Exchange the node at the top of the path, as we move horizontaly
+ // through the domain tree
+ node_path.pop();
+ node_path.push(node);
+
+ // Try going as deep as possible, keeping on the right side of the trees
+ const DomainTreeNode<T, DT>* down;
+ while ((down = node->getDown()) != NULL) {
+ // Move to the tree below
+ node = down;
+ if (node != NULL) {
+ // And get as much to the right of the tree as possible
+ const DomainTreeNode<T, DT>* right;
+ while ((right = node->getRight()) != NULL) {
+ node = right;
+ }
+ }
+ // Now, we found the right-most node in the sub-tree, we need to
+ // include it in the path
+ node_path.push(node);
+ }
+
+ // Now, if the current node has no down_ pointer any more, it's the
+ // correct one.
+ return (node);
+}
+
+template <typename T, typename DT>
+typename DomainTree<T, DT>::Result
+DomainTree<T, DT>::insert(util::MemorySegment& mem_sgmt,
+ const isc::dns::Name& target_name,
+ DomainTreeNode<T, DT>** new_node)
+{
+ DomainTreeNode<T, DT>* parent = NULL;
+ DomainTreeNode<T, DT>* current = root_.get();
+ DomainTreeNode<T, DT>* up_node = NULL;
+ isc::dns::LabelSequence target_labels(target_name);
+
+ int order = -1;
+ while (current != NULL) {
+ const dns::LabelSequence current_labels(current->getLabels());
+ const isc::dns::NameComparisonResult compare_result =
+ target_labels.compare(current_labels);
+ const isc::dns::NameComparisonResult::NameRelation relation =
+ compare_result.getRelation();
+ if (relation == isc::dns::NameComparisonResult::EQUAL) {
+ if (new_node != NULL) {
+ *new_node = current;
+ }
+ return (ALREADYEXISTS);
+ } else if (relation == isc::dns::NameComparisonResult::NONE) {
+ parent = current;
+ order = compare_result.getOrder();
+ current = order < 0 ? current->getLeft() : current->getRight();
+ } else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
+ // insert sub domain to sub tree
+ parent = NULL;
+ up_node = current;
+ target_labels.stripRight(compare_result.getCommonLabels());
+ current = current->getDown();
+ } else {
+ // The number of labels in common is fewer than the number of
+ // labels at the current node, so the current node must be
+ // adjusted to have just the common suffix, and a down pointer
+ // made to a new tree.
+ dns::LabelSequence common_ancestor = target_labels;
+ common_ancestor.stripLeft(target_labels.getLabelCount() -
+ compare_result.getCommonLabels());
+ dns::LabelSequence new_prefix = current_labels;
+ new_prefix.stripRight(compare_result.getCommonLabels());
+ nodeFission(mem_sgmt, *current, new_prefix, common_ancestor);
+ current = current->getParent();
+ }
+ }
+
+ typename DomainTreeNode<T, DT>::DomainTreeNodePtr* current_root =
+ (up_node != NULL) ? &(up_node->down_) : &root_;
+ // Once a new node is created, no exception will be thrown until the end
+ // of the function, so we can simply create and hold a new node pointer.
+ DomainTreeNode<T, DT>* node = DomainTreeNode<T, DT>::create(mem_sgmt,
+ target_labels);
+ node->parent_ = parent;
+ if (parent == NULL) {
+ *current_root = node;
+ // node is the new root of sub tree, so its init color is BLACK
+ node->setColor(DomainTreeNode<T, DT>::BLACK);
+ node->setSubTreeRoot(true);
+ node->parent_ = up_node;
+ } else if (order < 0) {
+ node->setSubTreeRoot(false);
+ parent->left_ = node;
+ } else {
+ node->setSubTreeRoot(false);
+ parent->right_ = node;
+ }
+ insertRebalance(current_root, node);
+ if (new_node != NULL) {
+ *new_node = node;
+ }
+
+ ++node_count_;
+ return (SUCCESS);
+}
+
+template <typename T, typename DT>
+void
+DomainTree<T, DT>::deleteAllNodes(util::MemorySegment& mem_sgmt) {
+ const DT deleter;
+ deleteHelper(mem_sgmt, root_.get(), deleter);
+ root_ = NULL;
+}
+
+template <typename T, typename DT>
+void
+DomainTree<T, DT>::nodeFission(util::MemorySegment& mem_sgmt,
+ DomainTreeNode<T, DT>& node,
+ const isc::dns::LabelSequence& new_prefix,
+ const isc::dns::LabelSequence& new_suffix)
+{
+ // Create and reset the labels.
+ // Once a new node is created, no exception will be thrown until
+ // the end of the function, and it will keep consistent behavior
+ // (i.e., a weak form of strong exception guarantee) even if code
+ // after the call to this function throws an exception.
+ DomainTreeNode<T, DT>* up_node = DomainTreeNode<T, DT>::create(mem_sgmt,
+ new_suffix);
+ 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 {
+ this->root_ = up_node;
+ }
+
+ up_node->down_ = &node;
+ node.parent_ = up_node;
+
+ // inherit the left/right pointers from the original node, and set
+ // the original node's left/right pointers to NULL.
+ up_node->left_ = node.getLeft();
+ if (node.getLeft() != NULL) {
+ node.getLeft()->parent_ = up_node;
+ }
+ up_node->right_ = node.getRight();
+ if (node.getRight() != NULL) {
+ node.getRight()->parent_ = up_node;
+ }
+ node.left_ = NULL;
+ node.right_ = NULL;
+
+ // set color of both nodes; the initial subtree node color is BLACK
+ up_node->setColor(node.getColor());
+ node.setColor(DomainTreeNode<T, DT>::BLACK);
+
+ // set the subtree root flag of both nodes
+ up_node->setSubTreeRoot(node.isSubTreeRoot());
+ node.setSubTreeRoot(true);
+
+ ++node_count_;
+}
+
+
+template <typename T, typename DT>
+void
+DomainTree<T, DT>::insertRebalance
+ (typename DomainTreeNode<T, DT>::DomainTreeNodePtr* root,
+ DomainTreeNode<T, DT>* node)
+{
+ DomainTreeNode<T, DT>* uncle;
+ DomainTreeNode<T, DT>* parent;
+ while (node != (*root).get() &&
+ ((parent = node->getParent())->getColor()) ==
+ DomainTreeNode<T, DT>::RED) {
+ // Here, node->parent_ is not NULL and it is also red, so
+ // node->parent_->parent_ is also not NULL.
+ if (parent == parent->getParent()->getLeft()) {
+ uncle = parent->getParent()->getRight();
+
+ if (uncle != NULL && uncle->getColor() ==
+ DomainTreeNode<T, DT>::RED) {
+ parent->setColor(DomainTreeNode<T, DT>::BLACK);
+ uncle->setColor(DomainTreeNode<T, DT>::BLACK);
+ parent->getParent()->setColor(DomainTreeNode<T, DT>::RED);
+ node = parent->getParent();
+ } else {
+ if (node == parent->getRight()) {
+ node = parent;
+ leftRotate(root, node);
+ parent = node->getParent();
+ }
+ parent->setColor(DomainTreeNode<T, DT>::BLACK);
+ parent->getParent()->setColor(DomainTreeNode<T, DT>::RED);
+ rightRotate(root, parent->getParent());
+ }
+ } else {
+ uncle = parent->getParent()->getLeft();
+
+ if (uncle != NULL && uncle->getColor() ==
+ DomainTreeNode<T, DT>::RED) {
+ parent->setColor(DomainTreeNode<T, DT>::BLACK);
+ uncle->setColor(DomainTreeNode<T, DT>::BLACK);
+ parent->getParent()->setColor(DomainTreeNode<T, DT>::RED);
+ node = parent->getParent();
+ } else {
+ if (node == parent->getLeft()) {
+ node = parent;
+ rightRotate(root, node);
+ parent = node->getParent();
+ }
+ parent->setColor(DomainTreeNode<T, DT>::BLACK);
+ parent->getParent()->setColor(DomainTreeNode<T, DT>::RED);
+ leftRotate(root, parent->getParent());
+ }
+ }
+ }
+
+ (*root)->setColor(DomainTreeNode<T, DT>::BLACK);
+}
+
+
+template <typename T, typename DT>
+DomainTreeNode<T, DT>*
+DomainTree<T, DT>::leftRotate
+ (typename DomainTreeNode<T, DT>::DomainTreeNodePtr* root,
+ DomainTreeNode<T, DT>* node)
+{
+ DomainTreeNode<T, DT>* const right = node->getRight();
+ DomainTreeNode<T, DT>* const rleft = right->getLeft();
+ node->right_ = rleft;
+ if (rleft != NULL) {
+ rleft->parent_ = node;
+ }
+
+ DomainTreeNode<T, DT>* const parent = node->getParent();
+ right->parent_ = parent;
+
+ if (!node->isSubTreeRoot()) {
+ right->setSubTreeRoot(false);
+ if (node == parent->getLeft()) {
+ parent->left_ = right;
+ } else {
+ parent->right_ = right;
+ }
+ } else {
+ right->setSubTreeRoot(true);
+ *root = right;
+ }
+
+ right->left_ = node;
+ node->parent_ = right;
+ node->setSubTreeRoot(false);
+ return (node);
+}
+
+template <typename T, typename DT>
+DomainTreeNode<T, DT>*
+DomainTree<T, DT>::rightRotate
+ (typename DomainTreeNode<T, DT>::DomainTreeNodePtr* root,
+ DomainTreeNode<T, DT>* node)
+{
+ DomainTreeNode<T, DT>* const left = node->getLeft();
+ DomainTreeNode<T, DT>* const lright = left->getRight();
+ node->left_ = lright;
+ if (lright != NULL) {
+ lright->parent_ = node;
+ }
+
+ DomainTreeNode<T, DT>* const parent = node->getParent();
+ left->parent_ = parent;
+
+ if (!node->isSubTreeRoot()) {
+ left->setSubTreeRoot(false);
+ if (node == parent->getRight()) {
+ parent->right_ = left;
+ } else {
+ parent->left_ = left;
+ }
+ } else {
+ left->setSubTreeRoot(true);
+ *root = left;
+ }
+ left->right_ = node;
+ node->parent_ = left;
+ node->setSubTreeRoot(false);
+
+ return (node);
+}
+
+
+template <typename T, typename DT>
+void
+DomainTree<T, DT>::dumpTree(std::ostream& os, unsigned int depth) const {
+ indent(os, depth);
+ os << "tree has " << node_count_ << " node(s)\n";
+ dumpTreeHelper(os, root_.get(), depth);
+}
+
+template <typename T, typename DT>
+void
+DomainTree<T, DT>::dumpTreeHelper(std::ostream& os,
+ const DomainTreeNode<T, DT>* node,
+ unsigned int depth) const
+{
+ if (node == NULL) {
+ indent(os, depth);
+ os << "NULL\n";
+ return;
+ }
+
+ indent(os, depth);
+ os << node->getLabels() << " ("
+ << ((node->getColor() == DomainTreeNode<T, DT>::BLACK) ? "black" : "red")
+ << ")";
+ if (node->isEmpty()) {
+ os << " [invisible]";
+ }
+ if (node->isSubTreeRoot()) {
+ os << " [subtreeroot]";
+ }
+ os << "\n";
+
+ const DomainTreeNode<T, DT>* down = node->getDown();
+ if (down != NULL) {
+ indent(os, depth + 1);
+ os << "begin down from " << node->getLabels() << "\n";
+ dumpTreeHelper(os, down, depth + 1);
+ indent(os, depth + 1);
+ os << "end down from " << node->getLabels() << "\n";
+ }
+ dumpTreeHelper(os, node->getLeft(), depth + 1);
+ dumpTreeHelper(os, node->getRight(), depth + 1);
+}
+
+template <typename T, typename DT>
+void
+DomainTree<T, DT>::indent(std::ostream& os, unsigned int depth) {
+ static const unsigned int INDENT_FOR_EACH_DEPTH = 5;
+ os << std::string(depth * INDENT_FOR_EACH_DEPTH, ' ');
+}
+
+template <typename T, typename DT>
+void
+DomainTree<T, DT>::dumpDot(std::ostream& os, bool show_pointers) const {
+ int nodecount = 0;
+
+ os << "digraph g {\n";
+ os << "node [shape = record,height=.1];\n";
+ dumpDotHelper(os, root_.get(), &nodecount, show_pointers);
+ os << "}\n";
+}
+
+template <typename T, typename DT>
+int
+DomainTree<T, DT>::dumpDotHelper(std::ostream& os,
+ const DomainTreeNode<T, DT>* node,
+ int* nodecount, bool show_pointers) const
+{
+ if (node == NULL) {
+ return 0;
+ }
+
+ int l = dumpDotHelper(os, node->getLeft(), nodecount, show_pointers);
+ int r = dumpDotHelper(os, node->getRight(), nodecount, show_pointers);
+ int d = dumpDotHelper(os, node->getDown(), nodecount, show_pointers);
+
+ *nodecount += 1;
+
+ os << "node" << *nodecount <<
+ "[label = \"<f0> |<f1> " << node->getLabels() <<
+ "|<f2>";
+ if (show_pointers) {
+ os << "|<f3> n=" << node << "|<f4> p=" << node->getParent();
+ }
+ os << "\"] [";
+
+ if (node->getColor() == DomainTreeNode<T, DT>::RED) {
+ os << "color=red";
+ } else {
+ os << "color=black";
+ }
+
+ if (node->isSubTreeRoot()) {
+ os << ",penwidth=3";
+ }
+
+ if (node->isEmpty()) {
+ os << ",style=filled,fillcolor=lightgrey";
+ }
+
+ os << "];\n";
+
+ if (node->getLeft() != NULL) {
+ os << "\"node" << *nodecount << "\":f0 -> \"node" << l << "\":f1;\n";
+ }
+
+ if (node->getDown() != NULL) {
+ os << "\"node" << *nodecount << "\":f1 -> \"node" << d <<
+ "\":f1 [penwidth=5];\n";
+ }
+
+ if (node->getRight() != NULL) {
+ os << "\"node" << *nodecount << "\":f2 -> \"node" << r << "\":f1;\n";
+ }
+
+ return (*nodecount);
+}
+
+} // namespace memory
+} // namespace datasrc
+} // namespace isc
+
+#endif // _DOMAINTREE_H
+
+// Local Variables:
+// mode: c++
+// End:
diff --git a/src/lib/datasrc/memory/tests/Makefile.am b/src/lib/datasrc/memory/tests/Makefile.am
index 73e9ebf..1396600 100644
--- a/src/lib/datasrc/memory/tests/Makefile.am
+++ b/src/lib/datasrc/memory/tests/Makefile.am
@@ -19,6 +19,7 @@ TESTS += run_unittests
run_unittests_SOURCES = run_unittests.cc
run_unittests_SOURCES += rdata_encoder_unittest.cc
+run_unittests_SOURCES += domaintree_unittest.cc
run_unittests_CPPFLAGS = $(AM_CPPFLAGS) $(GTEST_INCLUDES)
run_unittests_LDFLAGS = $(AM_LDFLAGS) $(GTEST_LDFLAGS)
diff --git a/src/lib/datasrc/memory/tests/domaintree_unittest.cc b/src/lib/datasrc/memory/tests/domaintree_unittest.cc
new file mode 100644
index 0000000..cfb223a
--- /dev/null
+++ b/src/lib/datasrc/memory/tests/domaintree_unittest.cc
@@ -0,0 +1,1035 @@
+// Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC")
+//
+// Permission to use, copy, modify, and/or distribute this software for any
+// purpose with or without fee is hereby granted, provided that the above
+// copyright notice and this permission notice appear in all copies.
+//
+// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
+// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+// AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
+// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
+// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+// PERFORMANCE OF THIS SOFTWARE.
+
+#include <gtest/gtest.h>
+
+#include <exceptions/exceptions.h>
+
+#include <util/memory_segment_local.h>
+
+#include <dns/name.h>
+#include <dns/rrclass.h>
+#include <dns/rrset.h>
+#include <dns/rrtype.h>
+#include <dns/rrttl.h>
+
+#include <datasrc/memory/domaintree.h>
+
+#include <dns/tests/unittest_util.h>
+
+using namespace std;
+using namespace isc;
+using namespace isc::dns;
+using isc::UnitTestUtil;
+using namespace isc::datasrc::memory;
+
+// 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 dtree
+ *
+ * .
+ * |
+ * b
+ * / \
+ * a d.e.f
+ * / | \
+ * c | g.h
+ * | |
+ * w.y i
+ * / | \ \
+ * x | z k
+ * | |
+ * p j
+ * / \
+ * o q
+ */
+
+namespace {
+
+class DeleterType {
+public:
+ DeleterType() {}
+
+ void operator()(util::MemorySegment&, int* i) const {
+ delete i;
+ }
+};
+
+typedef DomainTree<int, DeleterType> TestDomainTree;
+typedef DomainTreeNode<int, DeleterType> TestDomainTreeNode;
+typedef DomainTreeNodeChain<int, DeleterType> TestDomainTreeNodeChain;
+
+class TreeHolder {
+public:
+ TreeHolder(util::MemorySegment& mem_sgmt, TestDomainTree* tree) :
+ mem_sgmt_(mem_sgmt), tree_(tree)
+ {}
+ ~TreeHolder() {
+ TestDomainTree::destroy(mem_sgmt_, tree_);
+ }
+ TestDomainTree* get() { return (tree_); }
+private:
+ util::MemorySegment& mem_sgmt_;
+ TestDomainTree* tree_;
+};
+
+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(*dtree_holder_.get()),
+ dtree_expose_empty_node(*dtree_expose_empty_node_holder_.get()),
+ cdtnode(NULL)
+ {
+ const char* const domain_names[] = {
+ "c", "b", "a", "x.d.e.f", "z.d.e.f", "g.h", "i.g.h", "o.w.y.d.e.f",
+ "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f", "k.g.h"};
+ 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);
+ dtnode->setData(mem_sgmt_, new int(i + 1));
+
+ dtree_expose_empty_node.insert(mem_sgmt_, Name(domain_names[i]),
+ &dtnode);
+ dtnode->setData(mem_sgmt_, new int(i + 1));
+
+ }
+ }
+
+ util::MemorySegmentLocal mem_sgmt_;
+ TreeHolder dtree_holder_;
+ TreeHolder dtree_expose_empty_node_holder_;
+ TestDomainTree& dtree;
+ TestDomainTree& dtree_expose_empty_node;
+ TestDomainTreeNode* dtnode;
+ const TestDomainTreeNode* cdtnode;
+};
+
+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_);
+ EXPECT_EQ(0, dtree.getNodeCount());
+}
+
+TEST_F(DomainTreeTest, setGetData) {
+ dtnode->setData(mem_sgmt_, new int(11));
+ EXPECT_EQ(11, *(dtnode->getData()));
+}
+
+TEST_F(DomainTreeTest, insertNames) {
+ EXPECT_EQ(TestDomainTree::ALREADYEXISTS, dtree.insert(mem_sgmt_,
+ Name("d.e.f"),
+ &dtnode));
+ EXPECT_EQ(Name("d.e.f"), dtnode->getName());
+ EXPECT_EQ(15, dtree.getNodeCount());
+
+ // insert not exist node
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("0"),
+ &dtnode));
+ EXPECT_EQ(Name("0"), dtnode->getName());
+ EXPECT_EQ(16, dtree.getNodeCount());
+
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_,
+ Name("example.com"),
+ &dtnode));
+ EXPECT_EQ(17, dtree.getNodeCount());
+ dtnode->setData(mem_sgmt_, new int(12));
+
+ // return ALREADYEXISTS, since node "example.com" already has
+ // been explicitly inserted
+ EXPECT_EQ(TestDomainTree::ALREADYEXISTS, dtree.insert(mem_sgmt_,
+ Name("example.com"),
+ &dtnode));
+ EXPECT_EQ(17, dtree.getNodeCount());
+
+ // split the node "d.e.f"
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("k.e.f"),
+ &dtnode));
+ EXPECT_EQ(Name("k"), dtnode->getName());
+ EXPECT_EQ(19, dtree.getNodeCount());
+
+ // split the node "g.h"
+ EXPECT_EQ(TestDomainTree::ALREADYEXISTS, dtree.insert(mem_sgmt_, Name("h"),
+ &dtnode));
+ EXPECT_EQ(Name("h"), dtnode->getName());
+ EXPECT_EQ(20, dtree.getNodeCount());
+
+ // add child domain
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_,
+ Name("m.p.w.y.d.e.f"),
+ &dtnode));
+ EXPECT_EQ(Name("m"), dtnode->getName());
+ EXPECT_EQ(21, dtree.getNodeCount());
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_,
+ Name("n.p.w.y.d.e.f"),
+ &dtnode));
+ EXPECT_EQ(Name("n"), dtnode->getName());
+ EXPECT_EQ(22, dtree.getNodeCount());
+
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("l.a"),
+ &dtnode));
+ EXPECT_EQ(Name("l"), dtnode->getName());
+ EXPECT_EQ(23, dtree.getNodeCount());
+
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("r.d.e.f"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("s.d.e.f"),
+ &dtnode));
+ EXPECT_EQ(25, dtree.getNodeCount());
+
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_,
+ Name("h.w.y.d.e.f"),
+ &dtnode));
+
+ // add more nodes one by one to cover leftRotate and rightRotate
+ EXPECT_EQ(TestDomainTree::ALREADYEXISTS, dtree.insert(mem_sgmt_, Name("f"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("m"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("nm"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("om"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("k"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("l"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("fe"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("ge"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("i"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("ae"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_, Name("n"),
+ &dtnode));
+}
+
+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
+ // that when a node was fissioned, FLAG_SUBTREE_ROOT was not being
+ // copied correctly.
+
+ EXPECT_EQ(TestDomainTree::ALREADYEXISTS,
+ dtree_expose_empty_node.insert(mem_sgmt_, Name("d.e.f"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS,
+ dtree_expose_empty_node.insert(mem_sgmt_, Name("0"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS,
+ dtree_expose_empty_node.insert(mem_sgmt_, Name("example.com"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::ALREADYEXISTS,
+ dtree_expose_empty_node.insert(mem_sgmt_, Name("example.com"),
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::SUCCESS,
+ dtree_expose_empty_node.insert(mem_sgmt_, Name("k.e.f"),
+ &dtnode));
+
+ // "g.h" is not a subtree root
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("g.h"), &dtnode));
+ EXPECT_FALSE(dtnode->getFlag(TestDomainTreeNode::FLAG_SUBTREE_ROOT));
+
+ // fission the node "g.h"
+ EXPECT_EQ(TestDomainTree::ALREADYEXISTS,
+ dtree_expose_empty_node.insert(mem_sgmt_, Name("h"),
+ &dtnode));
+
+ // the node "h" (h.down_ -> "g") should not be a subtree root. "g"
+ // should be a subtree root.
+ EXPECT_FALSE(dtnode->getFlag(TestDomainTreeNode::FLAG_SUBTREE_ROOT));
+
+ // "g.h" should be a subtree root now.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("g.h"), &dtnode));
+ EXPECT_TRUE(dtnode->getFlag(TestDomainTreeNode::FLAG_SUBTREE_ROOT));
+}
+
+TEST_F(DomainTreeTest, additionalNodeFission) {
+ // These are additional nodeFission tests added by #2054's rewrite
+ // of DomainTree::nodeFission(). These test specific corner cases that
+ // are not covered by other tests.
+
+ // Insert "t.0" (which becomes the left child of its parent)
+ EXPECT_EQ(TestDomainTree::SUCCESS,
+ dtree_expose_empty_node.insert(mem_sgmt_, Name("t.0"),
+ &dtnode));
+
+ // "t.0" is not a subtree root
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("t.0"), &dtnode));
+ EXPECT_FALSE(dtnode->getFlag(TestDomainTreeNode::FLAG_SUBTREE_ROOT));
+
+ // fission the node "t.0"
+ EXPECT_EQ(TestDomainTree::ALREADYEXISTS,
+ dtree_expose_empty_node.insert(mem_sgmt_, Name("0"),
+ &dtnode));
+
+ // the node "0" ("0".down_ -> "t") should not be a subtree root. "t"
+ // should be a subtree root.
+ EXPECT_FALSE(dtnode->getFlag(TestDomainTreeNode::FLAG_SUBTREE_ROOT));
+
+ // "t.0" should be a subtree root now.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("t.0"), &dtnode));
+ EXPECT_TRUE(dtnode->getFlag(TestDomainTreeNode::FLAG_SUBTREE_ROOT));
+}
+
+TEST_F(DomainTreeTest, findName) {
+ // find const dtnode
+ // exact match
+ EXPECT_EQ(TestDomainTree::EXACTMATCH, dtree.find(Name("a"), &cdtnode));
+ EXPECT_EQ(Name("a"), cdtnode->getName());
+
+ // not found
+ EXPECT_EQ(TestDomainTree::NOTFOUND, dtree.find(Name("d.e.f"), &cdtnode));
+ EXPECT_EQ(TestDomainTree::NOTFOUND, dtree.find(Name("y.d.e.f"), &cdtnode));
+ EXPECT_EQ(TestDomainTree::NOTFOUND, dtree.find(Name("x"), &cdtnode));
+ EXPECT_EQ(TestDomainTree::NOTFOUND, dtree.find(Name("m.n"), &cdtnode));
+
+ // if we expose empty node, we can get the empty node created during insert
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("d.e.f"), &cdtnode));
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name("w.y.d.e.f"), &cdtnode));
+
+ // partial match
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH, dtree.find(Name("m.b"), &cdtnode));
+ EXPECT_EQ(Name("b"), cdtnode->getName());
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ dtree_expose_empty_node.find(Name("m.d.e.f"), &cdtnode));
+
+ // find dtnode
+ EXPECT_EQ(TestDomainTree::EXACTMATCH, dtree.find(Name("q.w.y.d.e.f"),
+ &dtnode));
+ EXPECT_EQ(Name("q"), dtnode->getName());
+}
+
+TEST_F(DomainTreeTest, findError) {
+ // For the version that takes a node chain, the chain must be empty.
+ TestDomainTreeNodeChain chain;
+ EXPECT_EQ(TestDomainTree::EXACTMATCH, dtree.find(Name("a"), &cdtnode,
+ chain));
+ // trying to reuse the same chain. it should result in an exception.
+ EXPECT_THROW(dtree.find(Name("a"), &cdtnode, chain),
+ BadValue);
+}
+
+TEST_F(DomainTreeTest, flags) {
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt_,
+ Name("flags.example"),
+ &dtnode));
+
+ // by default, flags are all off
+ EXPECT_FALSE(dtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+
+ // set operation, by default it enables the flag
+ dtnode->setFlag(TestDomainTreeNode::FLAG_CALLBACK);
+ EXPECT_TRUE(dtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+
+ // try disable the flag explicitly
+ dtnode->setFlag(TestDomainTreeNode::FLAG_CALLBACK, false);
+ EXPECT_FALSE(dtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+
+ // try enable the flag explicitly
+ dtnode->setFlag(TestDomainTreeNode::FLAG_CALLBACK, true);
+ EXPECT_TRUE(dtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+
+ // setting an unknown flag will trigger an exception
+ EXPECT_THROW(dtnode->setFlag(static_cast<TestDomainTreeNode::Flags>(2), true),
+ isc::InvalidParameter);
+}
+
+bool
+testCallback(const TestDomainTreeNode&, bool* callback_checker) {
+ *callback_checker = true;
+ return (false);
+}
+
+template <typename T>
+void
+performCallbackTest(TestDomainTree& dtree,
+ util::MemorySegmentLocal& mem_sgmt,
+ const T& name_called,
+ const T& name_not_called)
+{
+ TestDomainTreeNode* dtnode;
+ const TestDomainTreeNode* cdtnode;
+
+ // by default callback isn't enabled
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt,
+ Name("callback.example"),
+ &dtnode));
+ dtnode->setData(mem_sgmt, new int(1));
+ EXPECT_FALSE(dtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+
+ // enable/re-disable callback
+ dtnode->setFlag(TestDomainTreeNode::FLAG_CALLBACK);
+ EXPECT_TRUE(dtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+ dtnode->setFlag(TestDomainTreeNode::FLAG_CALLBACK, false);
+ EXPECT_FALSE(dtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+
+ // enable again for subsequent tests
+ dtnode->setFlag(TestDomainTreeNode::FLAG_CALLBACK);
+ // add more levels below and above the callback node for partial match.
+ TestDomainTreeNode* subdtnode;
+ EXPECT_EQ(TestDomainTree::SUCCESS, dtree.insert(mem_sgmt,
+ Name("sub.callback.example"),
+ &subdtnode));
+ subdtnode->setData(mem_sgmt, new int(2));
+ TestDomainTreeNode* parentdtnode;
+ EXPECT_EQ(TestDomainTree::ALREADYEXISTS, dtree.insert(mem_sgmt,
+ Name("example"),
+ &parentdtnode));
+ // the child/parent nodes shouldn't "inherit" the callback flag.
+ // "dtnode" may be invalid due to the insertion, so we need to re-find
+ // it.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH, dtree.find(Name("callback.example"),
+ &dtnode));
+ EXPECT_TRUE(dtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+ EXPECT_FALSE(subdtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+ EXPECT_FALSE(parentdtnode->getFlag(TestDomainTreeNode::FLAG_CALLBACK));
+
+ // check if the callback is called from find()
+ TestDomainTreeNodeChain node_path1;
+ bool callback_called = false;
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree.find(name_called, &cdtnode, 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.
+ TestDomainTreeNodeChain node_path2;
+ parentdtnode->setFlag(TestDomainTreeNode::FLAG_CALLBACK);
+ callback_called = false;
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree.find(name_not_called, &cdtnode, node_path2,
+ testCallback, &callback_called));
+ EXPECT_FALSE(callback_called);
+}
+
+TEST_F(DomainTreeTest, callbackName) {
+ const Name n1("sub.callback.example");
+ const Name n2("callback.example");
+
+ performCallbackTest(dtree, mem_sgmt_, n1, n2);
+}
+
+TEST_F(DomainTreeTest, callbackLabelSequence) {
+ const Name n1("sub.callback.example");
+ const Name n2("callback.example");
+ const LabelSequence ls1(n1);
+ const LabelSequence ls2(n2);
+
+ performCallbackTest(dtree, mem_sgmt_, ls1, ls2);
+}
+
+TEST_F(DomainTreeTest, chainLevel) {
+ TestDomainTreeNodeChain 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.
+ TreeHolder tree_holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_, true));
+ TestDomainTree& tree(*tree_holder.get());
+ Name node_name(Name::ROOT_NAME());
+ EXPECT_EQ(TestDomainTree::SUCCESS, tree.insert(mem_sgmt_, node_name,
+ &dtnode));
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(node_name, &cdtnode, chain));
+ EXPECT_EQ(1, chain.getLevelCount());
+
+ /*
+ * Now creating a possibly deepest tree with MAX_LABELS levels.
+ * it should look like:
+ * (.)
+ * |
+ * 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 the root name (".") solely belongs to a single level,
+ * so the levels begin with 2.
+ */
+ for (unsigned int i = 2; i <= Name::MAX_LABELS; ++i) {
+ node_name = Name("a.").concatenate(node_name);
+ EXPECT_EQ(TestDomainTree::SUCCESS, tree.insert(mem_sgmt_, node_name,
+ &dtnode));
+ TestDomainTreeNodeChain found_chain;
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(node_name, &cdtnode, found_chain));
+ EXPECT_EQ(i, found_chain.getLevelCount());
+ }
+
+ // Confirm the last inserted name has the possible maximum length with
+ // maximum label count. This confirms the dtree and chain level cannot
+ // be larger.
+ EXPECT_EQ(Name::MAX_LABELS, node_name.getLabelCount());
+ EXPECT_THROW(node_name.concatenate(Name("a.")), TooLongName);
+}
+
+TEST_F(DomainTreeTest, getAbsoluteNameError) {
+ // an empty chain isn't allowed.
+ TestDomainTreeNodeChain 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, 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) {
+ EXPECT_NE(static_cast<void*>(NULL), node);
+
+ const TestDomainTreeNode* upper_node = node->getUpperNode();
+ if (upper_node_names[i] != NULL) {
+ const TestDomainTreeNode* upper_node2 = NULL;
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree_expose_empty_node.find(Name(upper_node_names[i]),
+ &upper_node2));
+ EXPECT_NE(static_cast<void*>(NULL), upper_node2);
+ EXPECT_EQ(upper_node, upper_node2);
+ } else {
+ EXPECT_EQ(static_cast<void*>(NULL), upper_node);
+ }
+
+ node = dtree_expose_empty_node.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+}
+
+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) {
+ EXPECT_NE(static_cast<void*>(NULL), node);
+ EXPECT_EQ(Name(names[i]), node_path.getAbsoluteName());
+ node = dtree.nextNode(node_path);
+ }
+
+ // We should have reached the end of the tree.
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+}
+
+// Just walk using previousNode until the beginning of the tree and check it is
+// OK
+//
+// dtree - the tree to walk
+// node - result of previous call to find(), starting position of the walk
+// 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).
+// 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
+// match)
+void
+previousWalk(TestDomainTree& dtree, const TestDomainTreeNode* node,
+ TestDomainTreeNodeChain& node_path, size_t chain_length,
+ bool skip_first)
+{
+ if (skip_first) {
+ // If the first is not found, this is supposed to be NULL and we skip
+ // it in our checks.
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+ node = dtree.previousNode(node_path);
+ }
+ 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());
+ // Find the node at the path and check the value is the same
+ // (that it really returns the correct corresponding node)
+ //
+ // The "empty" nodes can not be found
+ if (node->getData()) {
+ const TestDomainTreeNode* node2(NULL);
+ TestDomainTreeNodeChain node_path2;
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ dtree.find(Name(names[i - 1]), &node2, node_path2));
+ EXPECT_EQ(node, node2);
+ }
+ node = dtree.previousNode(node_path);
+ }
+
+ // We should have reached the start of the tree.
+ ASSERT_NE(static_cast<void*>(NULL), node);
+ EXPECT_EQ(".", node->getLabels().toText());
+
+ // With one more call it results in NULL
+ node = dtree.previousNode(node_path);
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+
+ // Calling previousNode() yet again should still return NULL without
+ // fail.
+ node = dtree.previousNode(node_path);
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+}
+
+// Check the previousNode
+TEST_F(DomainTreeTest, previousNode) {
+ // First, iterate the whole tree from the end to the beginning.
+ TestDomainTreeNodeChain node_path;
+ EXPECT_THROW(dtree.previousNode(node_path), isc::BadValue) <<
+ "Throw before a search was done on the path";
+ const TestDomainTreeNode* node(NULL);
+ {
+ 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);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ 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));
+ previousWalk(dtree, node, node_path, 5, false);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Start at the first");
+ // 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));
+ EXPECT_NE(static_cast<void*>(NULL), node);
+ node = dtree.previousNode(node_path);
+ ASSERT_NE(static_cast<void*>(NULL), node);
+ EXPECT_EQ(".", node->getLabels().toText());
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Start before the first");
+ // If we start before the lowest (. < 0. < a.), we should not get a
+ // node. Its previous node should be the root.
+ EXPECT_EQ(TestDomainTree::NOTFOUND,
+ dtree.find<void*>(Name("0"), &node, node_path, NULL, NULL));
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+ node = dtree.previousNode(node_path);
+ ASSERT_NE(static_cast<void*>(NULL), node);
+ EXPECT_EQ(".", node->getLabels().toText());
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ 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);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Start below a leaf");
+ // We exit a leaf by going down. We should start by the one
+ // we exited - 'c' (actually, we should get it by the find, as partial
+ // match).
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ dtree.find(Name("b.c"), &node, node_path));
+ previousWalk(dtree, node, node_path, 3, false);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Start to the right of a leaf");
+ // When searching for this, we exit the 'x' node to the right side,
+ // so we should go x afterwards.
+
+ // The d.e.f is empty node, so it is hidden by find. Therefore NOTFOUND
+ // and not PARTIALMATCH.
+ EXPECT_EQ(TestDomainTree::NOTFOUND,
+ dtree.find(Name("xy.d.e.f"), &node, node_path));
+ previousWalk(dtree, node, node_path, 5, true);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Start to the left of a leaf");
+ // This is similar to the previous, but we exit the 'z' leaf to the
+ // left side, so should not visit z at all then.
+
+ // The d.e.f is empty node, so it is hidden by find. Therefore NOTFOUND
+ // and not PARTIALMATCH.
+ EXPECT_EQ(TestDomainTree::NOTFOUND,
+ dtree.find(Name("yz.d.e.f"), &node, node_path));
+ previousWalk(dtree, node, node_path, 9, true);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Start to the right of a parent");
+ // When searching for this, we exit the 'g.h' node to the right
+ // side, so we should go to g.h's children afterwards.
+
+ // 'g.h' is an empty node, so we get a NOTFOUND and not
+ // PARTIALMATCH.
+ EXPECT_EQ(TestDomainTree::NOTFOUND,
+ dtree.find(Name("x.h"), &node, node_path));
+ // 'g.h' is the COMMONANCESTOR.
+ EXPECT_EQ(node_path.getLastComparedNode()->getName(), Name("g.h"));
+ EXPECT_EQ(NameComparisonResult::COMMONANCESTOR,
+ node_path.getLastComparisonResult().getRelation());
+ // find() exits to the right of 'g.h'
+ EXPECT_GT(node_path.getLastComparisonResult().getOrder(), 0);
+ // We then descend into 'i.g.h' and walk all the nodes in the
+ // tree.
+ previousWalk(dtree, node, node_path, name_count, true);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Start inside a wrong node");
+ // The d.e.f is a single node, but we want only part of it. We
+ // should start iterating before it.
+ EXPECT_EQ(TestDomainTree::NOTFOUND,
+ dtree.find(Name("e.f"), &node, node_path));
+ previousWalk(dtree, node, node_path, 3, true);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Lookup in empty tree");
+ // Just check it doesn't crash, etc.
+ TreeHolder tree_holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_));
+ TestDomainTree& empty_tree(*tree_holder.get());
+ EXPECT_EQ(TestDomainTree::NOTFOUND,
+ empty_tree.find(Name("x"), &node, node_path));
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+ EXPECT_EQ(static_cast<void*>(NULL),
+ empty_tree.previousNode(node_path));
+ node = NULL;
+ node_path.clear();
+ }
+}
+
+TEST_F(DomainTreeTest, nextNodeError) {
+ // Empty chain for nextNode() is invalid.
+ TestDomainTreeNodeChain chain;
+ EXPECT_THROW(dtree.nextNode(chain), BadValue);
+}
+
+// A helper function for getLastComparedNode() below.
+void
+comparisonChecks(const TestDomainTreeNodeChain& chain,
+ int expected_order, int expected_common_labels,
+ NameComparisonResult::NameRelation expected_reln)
+{
+ if (expected_order > 0) {
+ EXPECT_LT(0, chain.getLastComparisonResult().getOrder());
+ } else if (expected_order < 0) {
+ EXPECT_GT(0, chain.getLastComparisonResult().getOrder());
+ } else {
+ EXPECT_EQ(0, chain.getLastComparisonResult().getOrder());
+ }
+ EXPECT_EQ(expected_common_labels,
+ chain.getLastComparisonResult().getCommonLabels());
+ EXPECT_EQ(expected_reln,
+ chain.getLastComparisonResult().getRelation());
+}
+
+TEST_F(DomainTreeTest, getLastComparedNode) {
+ TestDomainTree& tree = dtree_expose_empty_node; // use the "empty OK" mode
+ TestDomainTreeNodeChain chain;
+
+ // initially there should be no 'last compared'.
+ EXPECT_EQ(static_cast<void*>(NULL), chain.getLastComparedNode());
+
+ // A search for an empty tree should result in no 'last compared', too.
+ TreeHolder tree_holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_));
+ TestDomainTree& empty_tree(*tree_holder.get());
+ EXPECT_EQ(TestDomainTree::NOTFOUND,
+ empty_tree.find(Name("a"), &cdtnode, chain));
+ EXPECT_EQ(static_cast<void*>(NULL), chain.getLastComparedNode());
+ chain.clear();
+
+ const TestDomainTreeNode* expected_node = NULL;
+
+ // Exact match case. The returned node should be last compared.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name("x.d.e.f"), &expected_node, chain));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // 1 = # labels of "x" (note: excluding ".")
+ comparisonChecks(chain, 0, 1, NameComparisonResult::EQUAL);
+ chain.clear();
+
+ // Partial match, search stopped at the matching node, which should be
+ // the last compared node.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name("k.g.h"), &expected_node));
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ tree.find(Name("x.k.g.h"), &cdtnode, chain));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // k.g.h < x.k.g.h, 1 = # labels of "k"
+ comparisonChecks(chain, 1, 1, NameComparisonResult::SUBDOMAIN);
+ chain.clear();
+
+ // Partial match, search stopped in the subtree below the matching node
+ // after following a left branch.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name("x.d.e.f"), &expected_node));
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ tree.find(Name("a.d.e.f"), &cdtnode, chain));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // a < x, no common labels
+ comparisonChecks(chain, -1, 0, NameComparisonResult::NONE);
+ chain.clear();
+
+ // Partial match, search stopped in the subtree below the matching node
+ // after following a right branch.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name("z.d.e.f"), &expected_node));
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ tree.find(Name("zz.d.e.f"), &cdtnode, chain));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // zz > z, no common label
+ comparisonChecks(chain, 1, 0, NameComparisonResult::NONE);
+ chain.clear();
+
+ // Partial match, search stopped at a node for a super domain of the
+ // search name in the subtree below the matching node.
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ tree.find(Name("w.y.d.e.f"), &expected_node));
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ tree.find(Name("y.d.e.f"), &cdtnode, chain));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // y < w.y, 1 = # labels of "y"
+ comparisonChecks(chain, -1, 1, NameComparisonResult::SUPERDOMAIN);
+ chain.clear();
+
+ // Partial match, search stopped at a node that share a common ancestor
+ // with the search name in the subtree below the matching node.
+ // (the expected node is the same as the previous case)
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ tree.find(Name("z.y.d.e.f"), &cdtnode, chain));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // z.y > w.y, 1 = # labels of "y"
+ comparisonChecks(chain, 1, 1, NameComparisonResult::COMMONANCESTOR);
+ chain.clear();
+
+ // Search stops in the highest level (under ".") after following a left
+ // branch. (find() still returns PARTIALMATCH due to the top level ".")
+ EXPECT_EQ(TestDomainTree::EXACTMATCH, tree.find(Name("c"), &expected_node));
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ tree.find(Name("bb"), &cdtnode, chain));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // bb < c, no common label
+ comparisonChecks(chain, -1, 0, NameComparisonResult::NONE);
+ chain.clear();
+
+ // Search stops in the highest level (under ".") after following a right
+ // branch. (the expected node is the same as the previous case)
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ tree.find(Name("d"), &cdtnode, chain));
+ EXPECT_EQ(expected_node, chain.getLastComparedNode());
+ // d > c, no common label
+ comparisonChecks(chain, 1, 0, NameComparisonResult::NONE);
+ chain.clear();
+}
+
+TEST_F(DomainTreeTest, dumpTree) {
+ std::ostringstream str;
+ std::ostringstream str2;
+ dtree.dumpTree(str);
+ str2 << "tree has 15 node(s)\n"
+ ". (black) [invisible] [subtreeroot]\n"
+ " begin down from .\n"
+ " b (black) [subtreeroot]\n"
+ " a (black)\n"
+ " NULL\n"
+ " NULL\n"
+ " d.e.f (black) [invisible]\n"
+ " begin down from d.e.f\n"
+ " w.y (black) [invisible] [subtreeroot]\n"
+ " begin down from w.y\n"
+ " p (black) [subtreeroot]\n"
+ " o (red)\n"
+ " NULL\n"
+ " NULL\n"
+ " q (red)\n"
+ " NULL\n"
+ " NULL\n"
+ " end down from w.y\n"
+ " x (red)\n"
+ " NULL\n"
+ " NULL\n"
+ " z (red)\n"
+ " begin down from z\n"
+ " j (black) [subtreeroot]\n"
+ " NULL\n"
+ " NULL\n"
+ " end down from z\n"
+ " NULL\n"
+ " NULL\n"
+ " end down from d.e.f\n"
+ " c (red)\n"
+ " NULL\n"
+ " NULL\n"
+ " g.h (red)\n"
+ " begin down from g.h\n"
+ " i (black) [subtreeroot]\n"
+ " NULL\n"
+ " k (red)\n"
+ " NULL\n"
+ " NULL\n"
+ " end down from g.h\n"
+ " NULL\n"
+ " NULL\n"
+ " end down from .\n"
+ " NULL\n"
+ " NULL\n";
+ EXPECT_EQ(str2.str(), str.str());
+}
+
+TEST_F(DomainTreeTest, swap) {
+ // Store info about the first tree
+ std::ostringstream str1;
+ dtree.dumpTree(str1);
+ size_t count1(dtree.getNodeCount());
+
+ // Create second one and store state
+ TreeHolder tree_holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_));
+ TestDomainTree& tree2(*tree_holder.get());
+ TestDomainTreeNode* node;
+ tree2.insert(mem_sgmt_, Name("second"), &node);
+ std::ostringstream str2;
+ tree2.dumpTree(str2);
+
+ // Swap them
+ ASSERT_NO_THROW(tree2.swap(dtree));
+
+ // Check their sizes
+ ASSERT_EQ(1, dtree.getNodeCount());
+ ASSERT_EQ(count1, tree2.getNodeCount());
+
+ // And content
+ std::ostringstream out;
+ dtree.dumpTree(out);
+ ASSERT_EQ(str2.str(), out.str());
+ out.str("");
+ tree2.dumpTree(out);
+ ASSERT_EQ(str1.str(), out.str());
+}
+
+// Matching in the "root zone" may be special (e.g. there's no parent,
+// any domain names should be considered a subdomain of it), so it makes
+// sense to test cases with the root zone explicitly.
+TEST_F(DomainTreeTest, root) {
+ TreeHolder tree_holder(mem_sgmt_, TestDomainTree::create(mem_sgmt_));
+ TestDomainTree& root(*tree_holder.get());
+ root.insert(mem_sgmt_, Name::ROOT_NAME(), &dtnode);
+ dtnode->setData(mem_sgmt_, new int(1));
+
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ root.find(Name::ROOT_NAME(), &cdtnode));
+ EXPECT_EQ(dtnode, cdtnode);
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ root.find(Name("example.com"), &cdtnode));
+ EXPECT_EQ(dtnode, cdtnode);
+
+ // Insert a new name that better matches the query name. find() should
+ // find the better one.
+ root.insert(mem_sgmt_, Name("com"), &dtnode);
+ dtnode->setData(mem_sgmt_, new int(2));
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ root.find(Name("example.com"), &cdtnode));
+ EXPECT_EQ(dtnode, cdtnode);
+
+ // Perform the same tests for the tree that allows matching against empty
+ // nodes.
+ TreeHolder tree_holder_emptyok(mem_sgmt_,
+ TestDomainTree::create(mem_sgmt_, true));
+ TestDomainTree& root_emptyok(*tree_holder_emptyok.get());
+ root_emptyok.insert(mem_sgmt_, Name::ROOT_NAME(), &dtnode);
+ EXPECT_EQ(TestDomainTree::EXACTMATCH,
+ root_emptyok.find(Name::ROOT_NAME(), &cdtnode));
+ EXPECT_EQ(dtnode, cdtnode);
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ root_emptyok.find(Name("example.com"), &cdtnode));
+ EXPECT_EQ(dtnode, cdtnode);
+
+ root.insert(mem_sgmt_, Name("com"), &dtnode);
+ EXPECT_EQ(TestDomainTree::PARTIALMATCH,
+ root.find(Name("example.com"), &cdtnode));
+ EXPECT_EQ(dtnode, cdtnode);
+}
+}
More information about the bind10-changes
mailing list