BIND 10 master, updated. 7b053b086b440f13275474f704c5ff7cce0d8cfa [master] Update Changelog for NSEC-merge (#1803-#1810)
BIND 10 source code commits
bind10-changes at lists.isc.org
Fri May 11 13:56:22 UTC 2012
The branch, master has been updated
via 7b053b086b440f13275474f704c5ff7cce0d8cfa (commit)
via 2f9aa4a553a05aa1d9eac06f1140d78f0c99408b (commit)
via 8efd8ed25b2bf5ac515b20e6fdd567f854365fb8 (commit)
via 4223766cd50a3465a58e8b5d655f0c34d87ddf37 (commit)
via 9ea901973b1eeb7bfe5e20768eaffb368d1dab99 (commit)
via 076510013b800546f6bb83c44fb66dcd6ad64158 (commit)
via 911f3f6bcb273fb4edf35771530ea5e4d81796d8 (commit)
via c00c53f51b120edf4d39629b303f3e2b4f6fdbb4 (commit)
via ff68e9ec714e6cffa7350f4379a813c4fab91b4e (commit)
via 03e9e74294ad900fb4f74694d8fd9d75f13536d4 (commit)
via d6e1ef18ea838bc64ee0165e0a30aa96c61a63f4 (commit)
via 077179407af119b6374302e74b90b3c79ea0682d (commit)
via 0a31990d43d949e40408fbbdcf48a074efdfe772 (commit)
via 906ba788fd5c8fb08f4cf2717e0fbccdca4850ff (commit)
via d27a40e4c0cff7e670f4d0add2a7b57db230f588 (commit)
via a584d5c1242a8b82be7eca4af4da85319d5cfbfd (commit)
via d305cc8c84239d6fce7f53188b59d1b8829c64a8 (commit)
via 773df391b037d466d8176f8682c390600215917b (commit)
via 6db9bdd58f2dae27feb07e9bb23da82aa5867e18 (commit)
via bea193a5f6c6e44144496c399a333b7bbd277d39 (commit)
via d12c2c41040c41d2070aa18884177c9090501b7b (commit)
via 8b64be78db91e57c4b9b380150d110ef1c566bcf (commit)
via 85a727dcbf99b3af919623e87b526e5eba12c300 (commit)
via fa16480fcbc6ac41cd8582af4158b0ab8112dff6 (commit)
via 9180097f88518a57f314863f9822413d325692f4 (commit)
via c40eee6618fe722031b2760d7107a8b39df9572b (commit)
via d813447bb8127d6e2a12279abf5d3c52dffee185 (commit)
via 113592770df3708dd4a5ed29d429e4b8926b4b97 (commit)
via a45f34fd77c66fa5097dbc153955094e28f36c52 (commit)
via 3896117692c2dbbbf40b7f2ca80aa61a7f20e3bf (commit)
via 47e89192baa118b32f5423b70a1b81434b7f6c3f (commit)
via 08980b117b2b64fbf767922c25e0f3625e6abf95 (commit)
via 5419a73a9e9b5f963ebd9515d049ed49a2c354d5 (commit)
via 32bb3f9e17a9c3c2bbc50b4239ee8463f9216299 (commit)
via 751e4b49ae09892db8e81f270014ad8190edca9a (commit)
via 7468970f434e5c50be3e3cf2962a74b22b266e67 (commit)
via 3b3fdd3a93aed76dd7a14f472b38b04c96c389cc (commit)
via 28d86506099a3e8cfa78855b97971427153ed85e (commit)
via 1322f10b28fb7ccbc69768c409ac36fe26ce0657 (commit)
via 86f48610df6dc6c82c92c39c8935a006c5696d13 (commit)
via 153b142c0e4dc2e96f717ac4ce9451f988ee6fe8 (commit)
via e6b2f289d677d2396eb3a29df2516cbe2d241b69 (commit)
via 3706d7583e672d807273ed9fe4dcad66d7f5774a (commit)
via 6b7e514528109978fe9b731e3690331bc5ebf10b (commit)
via 02d9aacf0a7c244a60e436237fdac09062389f48 (commit)
via 6abb27b31deb6c5bbbe18a97bb7e0a719ee9a9ce (commit)
via db211a922da7f6d72575cbb7112f6013babd4291 (commit)
via 768f28b23d6309f9916f4273222f8c187ba29faf (commit)
via 7287394dbaadfaa1c98883d18b34e6d9ca6e9328 (commit)
via e291c7f960f1a8145652ec785eb9deee6d448935 (commit)
via 4f69760cbd6bdbd9be311b404700f6fb33a37a49 (commit)
from c11a19fe6b38b10575aa8e2a9582eb1d7e12281d (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 7b053b086b440f13275474f704c5ff7cce0d8cfa
Author: Jelte Jansen <jelte at isc.org>
Date: Fri May 11 15:55:51 2012 +0200
[master] Update Changelog for NSEC-merge (#1803-#1810)
commit 2f9aa4a553a05aa1d9eac06f1140d78f0c99408b
Merge: 8efd8ed25b2bf5ac515b20e6fdd567f854365fb8 076510013b800546f6bb83c44fb66dcd6ad64158
Author: Jelte Jansen <jelte at isc.org>
Date: Fri May 11 12:52:42 2012 +0200
[nsec_merge] Merge branch 'trac1808-2' into nsec_merge
Conflicts:
src/lib/datasrc/tests/memory_datasrc_unittest.cc
commit 8efd8ed25b2bf5ac515b20e6fdd567f854365fb8
Merge: 4223766cd50a3465a58e8b5d655f0c34d87ddf37 bea193a5f6c6e44144496c399a333b7bbd277d39
Author: Jelte Jansen <jelte at isc.org>
Date: Fri May 11 12:50:54 2012 +0200
[nsec_merge] Merge branch 'trac1807' into nsec_merge
Conflicts:
src/lib/datasrc/tests/rbtree_unittest.cc
commit 4223766cd50a3465a58e8b5d655f0c34d87ddf37
Merge: 9ea901973b1eeb7bfe5e20768eaffb368d1dab99 32bb3f9e17a9c3c2bbc50b4239ee8463f9216299
Author: Jelte Jansen <jelte at isc.org>
Date: Fri May 11 12:50:07 2012 +0200
[nsec_merge] Merge branch 'trac1805' into nsec_merge
commit 9ea901973b1eeb7bfe5e20768eaffb368d1dab99
Merge: c11a19fe6b38b10575aa8e2a9582eb1d7e12281d 0a31990d43d949e40408fbbdcf48a074efdfe772
Author: Jelte Jansen <jelte at isc.org>
Date: Fri May 11 12:49:49 2012 +0200
[nsec_merge] Merge branch 'trac1803' into nsec_merge
-----------------------------------------------------------------------
Summary of changes:
ChangeLog | 4 +
src/lib/datasrc/memory_datasrc.cc | 119 +++++++--
src/lib/datasrc/memory_datasrc.h | 6 +-
src/lib/datasrc/rbtree.h | 310 +++++++++++++++++++---
src/lib/datasrc/tests/memory_datasrc_unittest.cc | 295 ++++++++++++++++++---
src/lib/datasrc/tests/rbtree_unittest.cc | 211 +++++++++++++--
6 files changed, 818 insertions(+), 127 deletions(-)
-----------------------------------------------------------------------
diff --git a/ChangeLog b/ChangeLog
index 1821340..8e02216 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,7 @@
+435. [func] team
+ The in-memory datasource now supports NSEC-signed zones.
+ (Trac #1802-#1810, git 2f9aa4a553a05aa1d9eac06f1140d78f0c99408b)
+
434. [func] tomek
libdhcp++: Linux interface detection refactored. The code is
now cleaner. Tests better support certain versions of ifconfig.
diff --git a/src/lib/datasrc/memory_datasrc.cc b/src/lib/datasrc/memory_datasrc.cc
index ea35cfa..e0af93f 100644
--- a/src/lib/datasrc/memory_datasrc.cc
+++ b/src/lib/datasrc/memory_datasrc.cc
@@ -212,11 +212,63 @@ public:
// Identify the RBTree node that best matches the given name.
// See implementation notes below.
+ //
+ // The caller should pass an empty node_path, and it will contain the
+ // search context (all ancestor nodes that the underlying RBTree search
+ // traverses, and how the search stops) for possible later use at the
+ // caller side.
template <typename ResultType>
ResultType findNode(const Name& name,
+ RBTreeNodeChain<Domain>& node_path,
ZoneFinder::FindOptions options) const;
+
+ // A helper method for NSEC-signed zones. It searches the zone for
+ // the "closest" NSEC corresponding to the search context stored in
+ // node_path (it should contain sufficient information to identify the
+ // previous name of the query name in the zone). In some cases the
+ // immediate closest name may not have NSEC (when it's under a zone cut
+ // for glue records, or even when the zone is partly broken), so this
+ // method continues the search until it finds a name that has NSEC,
+ // and returns the one found first. Due to the prerequisite (see below),
+ // it should always succeed.
+ //
+ // node_path must store valid search context (in practice, it's expected
+ // to be set by findNode()); otherwise the underlying RBTree implementation
+ // throws.
+ //
+ // If the zone is not considered NSEC-signed or DNSSEC records were not
+ // required in the original search context (specified in options), this
+ // method doesn't bother to find NSEC, and simply returns NULL. So, by
+ // definition of "NSEC-signed", when it really tries to find an NSEC it
+ // should succeed; there should be one at least at the zone origin.
+ ConstRBNodeRRsetPtr
+ getClosestNSEC(RBTreeNodeChain<Domain>& node_path,
+ ZoneFinder::FindOptions options) const;
};
+ConstRBNodeRRsetPtr
+ZoneData::getClosestNSEC(RBTreeNodeChain<Domain>& node_path,
+ ZoneFinder::FindOptions options) const
+{
+ if (!nsec_signed_ || (options & ZoneFinder::FIND_DNSSEC) == 0) {
+ return (ConstRBNodeRRsetPtr());
+ }
+
+ const DomainNode* prev_node;
+ while ((prev_node = domains_.previousNode(node_path)) != NULL) {
+ if (!prev_node->isEmpty()) {
+ const Domain::const_iterator found =
+ prev_node->getData()->find(RRType::NSEC());
+ if (found != prev_node->getData()->end()) {
+ return (found->second);
+ }
+ }
+ }
+ // This must be impossible and should be an internal bug.
+ // See the description at the method declaration.
+ assert(false);
+}
+
/// Maintain intermediate data specific to the search context used in
/// \c find().
///
@@ -359,9 +411,10 @@ bool cutCallback(const DomainNode& node, FindState* state) {
// the zone.
template <typename ResultType>
ResultType
-ZoneData::findNode(const Name& name, ZoneFinder::FindOptions options) const {
+ZoneData::findNode(const Name& name, RBTreeNodeChain<Domain>& node_path,
+ ZoneFinder::FindOptions options) const
+{
DomainNode* node = NULL;
- RBTreeNodeChain<Domain> node_path;
FindState state((options & ZoneFinder::FIND_GLUE_OK) != 0);
const DomainTree::Result result =
@@ -387,9 +440,10 @@ ZoneData::findNode(const Name& name, ZoneFinder::FindOptions options) const {
NameComparisonResult::SUPERDOMAIN) { // empty node, so NXRRSET
LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_SUPER_STOP).arg(name);
return (ResultType(ZoneFinder::NXRRSET, node,
- ConstRBNodeRRsetPtr()));
+ getClosestNSEC(node_path, options)));
}
- if (node->getFlag(domain_flag::WILD)) { // maybe a wildcard
+ if (node->getFlag(domain_flag::WILD) && // maybe a wildcard, check only
+ (options & ZoneFinder::NO_WILDCARD) == 0) { // if not disabled.
if (node_path.getLastComparisonResult().getRelation() ==
NameComparisonResult::COMMONANCESTOR &&
node_path.getLastComparisonResult().getCommonLabels() > 1) {
@@ -403,12 +457,17 @@ ZoneData::findNode(const Name& name, ZoneFinder::FindOptions options) const {
LOG_DEBUG(logger, DBG_TRACE_DATA,
DATASRC_MEM_WILDCARD_CANCEL).arg(name);
return (ResultType(ZoneFinder::NXDOMAIN, NULL,
- ConstRBNodeRRsetPtr()));
+ getClosestNSEC(node_path, options)));
}
// Now the wildcard should be the best match.
const Name wildcard(Name("*").concatenate(
node_path.getAbsoluteName()));
- DomainTree::Result result = domains_.find(wildcard, &node);
+
+ // Clear the node_path so that we don't keep incorrect (NSEC)
+ // context
+ node_path.clear();
+ DomainTree::Result result(domains_.find(wildcard, &node,
+ node_path));
// Otherwise, why would the domain_flag::WILD be there if
// there was no wildcard under it?
assert(result == DomainTree::EXACTMATCH);
@@ -418,7 +477,8 @@ ZoneData::findNode(const Name& name, ZoneFinder::FindOptions options) const {
}
// Nothing really matched.
LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_NOT_FOUND).arg(name);
- return (ResultType(ZoneFinder::NXDOMAIN, node, state.rrset_));
+ return (ResultType(ZoneFinder::NXDOMAIN, node,
+ getClosestNSEC(node_path, options)));
} else {
// If the name is neither an exact or partial match, it is
// out of bailiwick, which is considered an error.
@@ -1199,6 +1259,24 @@ struct InMemoryZoneFinder::InMemoryZoneFinderImpl {
}
}
+ // A helper function for the NXRRSET case in find(). If the zone is
+ // NSEC-signed and DNSSEC records are requested, try to find NSEC
+ // on the given node, and return it if found; return NULL for all other
+ // cases.
+ ConstRBNodeRRsetPtr getNSECForNXRRSET(FindOptions options,
+ const DomainNode& node) const
+ {
+ if (zone_data_->nsec_signed_ &&
+ (options & ZoneFinder::FIND_DNSSEC) != 0) {
+ const Domain::const_iterator found =
+ node.getData()->find(RRType::NSEC());
+ if (found != node.getData()->end()) {
+ return (found->second);
+ }
+ }
+ return (ConstRBNodeRRsetPtr());
+ }
+
// Set up FindContext object as a return value of find(), taking into
// account wildcard matches and DNSSEC information. We set the NSEC/NSEC3
// flag when applicable regardless of the find option; the caller would
@@ -1236,8 +1314,10 @@ struct InMemoryZoneFinder::InMemoryZoneFinderImpl {
// Get the node. All other cases than an exact match are handled
// in findNode(). We simply construct a result structure and return.
+ RBTreeNodeChain<Domain> node_path; // findNode will fill in this
const ZoneData::FindNodeResult node_result =
- zone_data_->findNode<ZoneData::FindNodeResult>(name, options);
+ zone_data_->findNode<ZoneData::FindNodeResult>(name, node_path,
+ options);
if (node_result.code != SUCCESS) {
return (createFindResult(node_result.code, node_result.rrset));
}
@@ -1253,7 +1333,10 @@ struct InMemoryZoneFinder::InMemoryZoneFinderImpl {
if (node->isEmpty()) {
LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_DOMAIN_EMPTY).
arg(name);
- return (createFindResult(NXRRSET, ConstRBNodeRRsetPtr(), rename));
+ return (createFindResult(NXRRSET,
+ zone_data_->getClosestNSEC(node_path,
+ options),
+ rename));
}
Domain::const_iterator found;
@@ -1309,10 +1392,9 @@ struct InMemoryZoneFinder::InMemoryZoneFinderImpl {
rename));
}
}
- // No exact match or CNAME. Return NXRRSET.
- LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_NXRRSET).arg(type).
- arg(name);
- return (createFindResult(NXRRSET, ConstRBNodeRRsetPtr(), rename));
+ // No exact match or CNAME. Get NSEC if necessary and return NXRRSET.
+ return (createFindResult(NXRRSET, getNSECForNXRRSET(options, *node),
+ rename));
}
};
@@ -1474,6 +1556,7 @@ addAdditional(RBNodeRRset* rrset, ZoneData* zone_data,
{
RdataIteratorPtr rdata_iterator = rrset->getRdataIterator();
bool match_wild = false; // will be true if wildcard match is found
+ RBTreeNodeChain<Domain> node_path; // placeholder for findNode()
for (; !rdata_iterator->isLast(); rdata_iterator->next()) {
// For each domain name that requires additional section processing
// in each RDATA, search the tree for the name and remember it if
@@ -1486,13 +1569,14 @@ addAdditional(RBNodeRRset* rrset, ZoneData* zone_data,
// if the name is not in or below this zone, skip it
const NameComparisonResult::NameRelation reln =
name.compare(zone_data->origin_data_->getName()).getRelation();
- if (reln != NameComparisonResult::SUBDOMAIN &&
- reln != NameComparisonResult::EQUAL) {
+ if (reln != NameComparisonResult::SUBDOMAIN &&
+ reln != NameComparisonResult::EQUAL) {
continue;
}
+ node_path.clear();
const ZoneData::FindMutableNodeResult result =
zone_data->findNode<ZoneData::FindMutableNodeResult>(
- name, ZoneFinder::FIND_GLUE_OK);
+ name, node_path, ZoneFinder::FIND_GLUE_OK);
if (result.code != ZoneFinder::SUCCESS) {
// We are not interested in anything but a successful match.
continue;
@@ -1762,8 +1846,7 @@ public:
{
// Find the first node (origin) and preserve the node chain for future
// searches
- DomainTree::Result result(tree_.find<void*>(origin, &node_, chain_,
- NULL, NULL));
+ DomainTree::Result result(tree_.find(origin, &node_, chain_));
// It can't happen that the origin is not in there
if (result != DomainTree::EXACTMATCH) {
isc_throw(Unexpected,
diff --git a/src/lib/datasrc/memory_datasrc.h b/src/lib/datasrc/memory_datasrc.h
index c687d1b..f4e99a8 100644
--- a/src/lib/datasrc/memory_datasrc.h
+++ b/src/lib/datasrc/memory_datasrc.h
@@ -65,11 +65,7 @@ public:
/// \brief Returns the class of the zone.
virtual isc::dns::RRClass getClass() const;
- /// \brief Looks up an RRset in the zone.
- ///
- /// See documentation in \c Zone.
- ///
- /// It returns NULL pointer in case of NXDOMAIN and NXRRSET.
+ /// \brief Find an RRset in the datasource
virtual ZoneFinderContextPtr find(const isc::dns::Name& name,
const isc::dns::RRType& type,
const FindOptions options =
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index dbf0591..39646ac 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -237,7 +237,7 @@ private:
/// Return if callback is enabled at the node.
//@}
-private:
+
/// \brief Define rbnode color
enum RBNodeColor {BLACK, RED};
/// This is a factory class method of a special singleton null node.
@@ -263,6 +263,37 @@ private:
/// This method never throws an exception.
const RBNode<T>* 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 RBTree;
+ /// RBTree is a tree in tree, and the real next node may reside in
+ /// an upper or lower subtree of the subtree where this node belongs.
+ /// For example, if 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_NODE().
+ ///
+ /// This method never throws an exception.
+ const RBNode<T>* 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 RBNode<T>* abstractSuccessor(RBNode<T>* RBNode<T>::*left,
+ RBNode<T>* RBNode<T>::*right) const;
+
/// \name Data to maintain the rbtree structure.
//@{
RBNode<T>* parent_;
@@ -283,7 +314,7 @@ private:
/// \par Adding down pointer to \c RBNode 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 useage as it allows storing only relative names,
+ /// \li It saves memory usage as it allows storing only relative names,
/// avoiding storage of the same domain labels multiple times.
RBNode<T>* down_;
@@ -333,30 +364,48 @@ RBNode<T>::~RBNode() {
template <typename T>
const RBNode<T>*
-RBNode<T>::successor() const {
+RBNode<T>::abstractSuccessor(RBNode<T>* RBNode<T>::*left, RBNode<T>*
+ RBNode<T>::*right) const
+{
+ // This function is written as a successor. It becomes predecessor if
+ // the left and right pointers are swapped. So in case of predecessor,
+ // the left pointer points to right and vice versa. Don't get confused
+ // by the idea, just imagine the pointers look into a mirror.
+
const RBNode<T>* current = this;
// If it has right node, the successor is the left-most node of the right
// subtree.
- if (right_ != NULL_NODE()) {
- current = right_;
- while (current->left_ != NULL_NODE()) {
- current = current->left_;
+ if (current->*right != RBNode<T>::NULL_NODE()) {
+ current = current->*right;
+ while (current->*left != RBNode<T>::NULL_NODE()) {
+ current = current->*left;
}
return (current);
}
-
// Otherwise go up until we find the first left branch on our path to
// root. If found, the parent of the branch is the successor.
// Otherwise, we return the null node
const RBNode<T>* parent = current->parent_;
- while (parent != NULL_NODE() && current == parent->right_) {
+ while (parent != RBNode<T>::NULL_NODE() && current == parent->*right) {
current = parent;
parent = parent->parent_;
}
return (parent);
}
+template <typename T>
+const RBNode<T>*
+RBNode<T>::successor() const {
+ return (abstractSuccessor(&RBNode<T>::left_, &RBNode<T>::right_));
+}
+
+template <typename T>
+const RBNode<T>*
+RBNode<T>::predecessor() const {
+ // Swap the left and right pointers for the abstractSuccessor
+ return (abstractSuccessor(&RBNode<T>::right_, &RBNode<T>::left_));
+}
/// \brief RBTreeNodeChain stores detailed information of \c RBTree::find()
/// result.
@@ -364,8 +413,7 @@ RBNode<T>::successor() const {
/// - The \c RBNode 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 (which is
-/// not yet implemented).
+/// - 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.
@@ -396,7 +444,7 @@ RBNode<T>::successor() const {
template <typename T>
class RBTreeNodeChain {
/// RBTreeNodeChain is initialized by RBTree, only RBTree has
- /// knowledge to manipuate it.
+ /// knowledge to manipulate it.
friend class RBTree<T>;
public:
/// \name Constructors and Assignment Operator.
@@ -498,10 +546,10 @@ public:
private:
// the following private functions check invariants about the internal
// state using assert() instead of exception. The state of a chain
- // can only be modified operations within this file, so if any of the
+ // can only be modified by operations within this file, so if any of the
// assumptions fails it means an internal bug.
- /// \brief return whther node chain has node in it.
+ /// \brief return whether node chain has node in it.
///
/// \exception None
bool isEmpty() const { return (node_count_ == 0); }
@@ -655,7 +703,7 @@ public:
/// By default, nodes that don't have data (see RBNode::isEmpty) are
/// ignored and the result can be NOTFOUND even if there's a node whose
/// name matches. If the \c RBTree is constructed with its
- /// \c returnEmptyNode parameter being \c true, an empty node will also
+ /// \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
@@ -673,7 +721,7 @@ public:
/// 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 and PARTIALMATCH, it is set
+ /// is output-only, and in case of EXACTMATCH or PARTIALMATCH, it is set
/// to a pointer to the found node.
///
/// They return:
@@ -710,6 +758,30 @@ public:
return (ret);
}
+ /// \brief Simple find, with node_path tracking
+ ///
+ /// Acts as described in the \ref find section.
+ Result find(const isc::dns::Name& name, RBNode<T>** node,
+ RBTreeNodeChain<T>& node_path) const
+ {
+ return (find<void*>(name, 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 RBNode<T>** node,
+ RBTreeNodeChain<T>& node_path) const
+ {
+ RBNode<T> *target_node = NULL;
+ Result ret = (find<void*>(name, &target_node, node_path, NULL, NULL));
+ if (ret != NOTFOUND) {
+ *node = target_node;
+ }
+ return (ret);
+ }
+
/// \brief Find with callback and node chain.
/// \anchor callback
///
@@ -720,13 +792,16 @@ public:
///
/// 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 RBNode::enableCallback and related
- /// functions).
+ /// the domain namespace (see \c RBNode::FLAG_CALLBACK).
///
/// 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
@@ -741,38 +816,36 @@ public:
/// which is an object of class \c RBTreeNodeChain.
/// The passed parameter must be empty.
///
- /// \note The rest of the description isn't yet implemented. It will be
- /// handled in Trac ticket #517.
- ///
- /// On success, the node sequence stoed in \c node_path will contain all
+ /// 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.f and d.e.f will be stored below it.
+ /// 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 names. With the current implementation
/// it's not possible without a node chain, because there is a no pointer
/// from the root of a subtree to the parent subtree (this may change
- /// in a future version). A node chain can also be used to find the next
- /// node of a given node in the entire RBTree; the \c nextNode() method
- /// takes a node chain as a parameter.
+ /// in a future version). A node chain can also be used to find the
+ /// next and previous nodes of a given node in the entire RBTree;
+ /// the \c nextNode() and \c previousNode() methods take a node
+ /// chain as a parameter.
///
- /// \exception isc::BadValue node_path is not empty (not yet implemented).
+ /// \exception isc::BadValue node_path is not empty.
///
/// \param name Target to be found
/// \param node On success (either \c EXACTMATCH or \c PARTIALMATCH)
/// it will store a pointer to the matching node
/// \param node_path 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 above).
+ /// \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 described above, but in case of callback returning true,
- /// it returns immediately with the current node.
+ /// \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::Name& name,
RBNode<T>** node,
@@ -826,6 +899,30 @@ public:
/// the largest, \c NULL will be returned.
const RBNode<T>* nextNode(RBTreeNodeChain<T>& node_path) const;
+ /// \brief return the next smaller node in DNSSEC order from a node
+ /// searched by RBTree::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 RBTree
+ /// 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 RBNode that is next smaller than \c node; if \c node is
+ /// the smallest, \c NULL will be returned.
+ const RBNode<T>* previousNode(RBTreeNodeChain<T>& 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
@@ -848,8 +945,8 @@ public:
//@{
/// \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 inserted_node parameter
+ /// 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.
@@ -1059,15 +1156,7 @@ RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const {
return (left_most);
}
- // node_path go to up level
- node_path.pop();
- // otherwise found the successor node in current level
- const RBNode<T>* successor = node->successor();
- if (successor != NULLNODE) {
- node_path.push(successor);
- return (successor);
- }
-
+ // 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
@@ -1084,6 +1173,143 @@ RBTree<T>::nextNode(RBTreeNodeChain<T>& node_path) const {
return (NULL);
}
+template <typename T>
+const RBNode<T>*
+RBTree<T>::previousNode(RBTreeNodeChain<T>& 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,
+ "RBTree::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:
+ // 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 RBNode<T>* current(node_path.last_compared_);
+ while (current != NULLNODE) {
+ node_path.push(current);
+ // Go a level down and as much right there as possible
+ current = current->down_;
+ while (current->right_ != NULLNODE) {
+ // A small trick. The current may be NULLNODE, but
+ // such node has the right_ pointer and it is equal
+ // to NULLNODE.
+ current = 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 RBNode<T>* node(node_path.top());
+
+ // Try going left in this tree
+ node = node->predecessor();
+ if (node == NULLNODE) {
+ // 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
+ while (node->down_ != NULLNODE) {
+ // Move to the tree below
+ node = node->down_;
+ // And get as much to the right of the tree as possible
+ while (node->right_ != NULLNODE) {
+ node = 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 RBTree<T>::Result
diff --git a/src/lib/datasrc/tests/memory_datasrc_unittest.cc b/src/lib/datasrc/tests/memory_datasrc_unittest.cc
index 07d1fb9..b3e7601 100644
--- a/src/lib/datasrc/tests/memory_datasrc_unittest.cc
+++ b/src/lib/datasrc/tests/memory_datasrc_unittest.cc
@@ -373,18 +373,30 @@ protected:
// expected_flags is set to either RESULT_NSEC_SIGNED or
// RESULT_NSEC3_SIGNED when it's NSEC/NSEC3 signed respectively and
// find() is expected to set the corresponding flags.
+ // find_options should be set to FIND_DNSSEC for NSEC-signed case when
+ // NSEC is expected to be returned.
void findCheck(ZoneFinder::FindResultFlags expected_flags =
- ZoneFinder::RESULT_DEFAULT);
+ ZoneFinder::RESULT_DEFAULT,
+ ZoneFinder::FindOptions find_options =
+ ZoneFinder::FIND_DEFAULT);
void emptyNodeCheck(ZoneFinder::FindResultFlags expected_flags =
ZoneFinder::RESULT_DEFAULT);
void wildcardCheck(ZoneFinder::FindResultFlags expected_flags =
- ZoneFinder::RESULT_DEFAULT);
+ ZoneFinder::RESULT_DEFAULT,
+ ZoneFinder::FindOptions find_options =
+ ZoneFinder::FIND_DEFAULT);
void doCancelWildcardCheck(ZoneFinder::FindResultFlags expected_flags =
- ZoneFinder::RESULT_DEFAULT);
+ ZoneFinder::RESULT_DEFAULT,
+ ZoneFinder::FindOptions find_options =
+ ZoneFinder::FIND_DEFAULT);
void anyWildcardCheck(ZoneFinder::FindResultFlags expected_flags =
ZoneFinder::RESULT_DEFAULT);
void emptyWildcardCheck(ZoneFinder::FindResultFlags expected_flags =
ZoneFinder::RESULT_DEFAULT);
+ void findNSECENTCheck(const Name& ent_name,
+ ConstRRsetPtr expected_nsec,
+ ZoneFinder::FindResultFlags expected_flags =
+ ZoneFinder::RESULT_DEFAULT);
public:
InMemoryZoneFinderTest() :
@@ -441,8 +453,23 @@ public:
{"0P9MHAVEQVM6T7VBL5LOP2U3T2RP3TOM.example.org. 300 IN "
"NSEC3 1 1 12 aabbccdd 2T7B4G4VSA5SMI47K61MV5BV1A22BOJR A RRSIG",
&rr_nsec3_},
- {"example.org. 300 IN NSEC cname.example.org. A NS NSEC",
- &rr_nsec_},
+ {"example.org. 300 IN NSEC wild.*.foo.example.org. "
+ "NS SOA RRSIG NSEC DNSKEY", &rr_nsec_},
+ // Together with the apex NSEC, these next NSECs make a complete
+ // chain in the case of the zone for the emptyNonterminal tests
+ // (We may want to clean up this generator code and/or masterLoad
+ // so that we can prepare conflicting datasets better)
+ {"wild.*.foo.example.org. 3600 IN NSEC ns.example.org. "
+ "A RRSIG NSEC", &rr_ent_nsec2_},
+ {"ns.example.org. 3600 IN NSEC foo.wild.example.org. A RRSIG NSEC",
+ &rr_ent_nsec3_},
+ {"foo.wild.example.org. 3600 IN NSEC example.org. A RRSIG NSEC",
+ &rr_ent_nsec4_},
+ // And these are NSECs used in different tests
+ {"ns.example.org. 300 IN NSEC *.nswild.example.org. A AAAA NSEC",
+ &rr_ns_nsec_},
+ {"*.wild.example.org. 300 IN NSEC foo.wild.example.org. A NSEC",
+ &rr_wild_nsec_},
{NULL, NULL}
};
@@ -508,6 +535,11 @@ public:
RRsetPtr rr_not_wild_another_;
RRsetPtr rr_nsec3_;
RRsetPtr rr_nsec_;
+ RRsetPtr rr_ent_nsec2_;
+ RRsetPtr rr_ent_nsec3_;
+ RRsetPtr rr_ent_nsec4_;
+ RRsetPtr rr_ns_nsec_;
+ RRsetPtr rr_wild_nsec_;
// A faked NSEC3 hash calculator for convenience.
// Tests that need to use the faked hashed values should call
@@ -977,7 +1009,9 @@ TEST_F(InMemoryZoneFinderTest, glue) {
* directly there, it just tells it doesn't exist.
*/
void
-InMemoryZoneFinderTest::findCheck(ZoneFinder::FindResultFlags expected_flags) {
+InMemoryZoneFinderTest::findCheck(ZoneFinder::FindResultFlags expected_flags,
+ ZoneFinder::FindOptions find_options)
+{
// Fill some data inside
// Now put all the data we have there. It should throw nothing
EXPECT_NO_THROW(EXPECT_EQ(SUCCESS, zone_finder_.add(rr_ns_)));
@@ -996,31 +1030,122 @@ InMemoryZoneFinderTest::findCheck(ZoneFinder::FindResultFlags expected_flags) {
findTest(rr_ns_a_->getName(), RRType::A(), ZoneFinder::SUCCESS, true,
rr_ns_a_);
- // These domain exist but don't have the provided RRType
- findTest(origin_, RRType::AAAA(), ZoneFinder::NXRRSET, true,
- ConstRRsetPtr(), expected_flags);
- findTest(rr_ns_a_->getName(), RRType::NS(), ZoneFinder::NXRRSET, true,
- ConstRRsetPtr(), expected_flags);
+ // These domains don't exist. (and one is out of the zone). In an
+ // NSEC-signed zone with DNSSEC records requested, it should return the
+ // covering NSEC for the query name (the actual NSEC in the test data may
+ // not really "cover" it, but for the purpose of this test it's okay).
+ ConstRRsetPtr expected_nsec; // by default it's NULL
+ if ((expected_flags & ZoneFinder::RESULT_NSEC_SIGNED) != 0 &&
+ (find_options & ZoneFinder::FIND_DNSSEC) != 0) {
+ expected_nsec = rr_nsec_;
+ }
- // These domains don't exist (and one is out of the zone)
- findTest(Name("nothere.example.org"), RRType::A(), ZoneFinder::NXDOMAIN,
- true, ConstRRsetPtr(), expected_flags);
+ // There's no other name between this one and the origin, so when NSEC
+ // is to be returned it should be the origin NSEC.
+ findTest(Name("nothere.example.org"), RRType::A(),
+ ZoneFinder::NXDOMAIN, true, expected_nsec, expected_flags,
+ NULL, find_options);
+
+ // The previous name in the zone is "ns.example.org", but it doesn't
+ // have an NSEC. It should be skipped and the origin NSEC will be
+ // returned as the "closest NSEC".
+ findTest(Name("nxdomain.example.org"), RRType::A(),
+ ZoneFinder::NXDOMAIN, true, expected_nsec, expected_flags,
+ NULL, find_options);
EXPECT_THROW(zone_finder_.find(Name("example.net"), RRType::A()),
OutOfZone);
+
+ // These domain exist but don't have the provided RRType. For the latter
+ // one we now add its NSEC (which was delayed so that it wouldn't break
+ // other cases above).
+ findTest(origin_, RRType::AAAA(), ZoneFinder::NXRRSET, true,
+ expected_nsec, expected_flags, NULL, find_options);
+ if ((expected_flags & ZoneFinder::RESULT_NSEC_SIGNED) != 0) {
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_ns_nsec_));
+ if ((find_options & ZoneFinder::FIND_DNSSEC) != 0) {
+ expected_nsec = rr_ns_nsec_;
+ }
+ }
+ findTest(rr_ns_a_->getName(), RRType::NS(), ZoneFinder::NXRRSET, true,
+ expected_nsec, expected_flags, NULL, find_options);
}
TEST_F(InMemoryZoneFinderTest, find) {
findCheck();
}
-TEST_F(InMemoryZoneFinderTest, findNSEC3Signed) {
+TEST_F(InMemoryZoneFinderTest, findNSEC3Signe) {
findCheck(ZoneFinder::RESULT_NSEC3_SIGNED);
}
+TEST_F(InMemoryZoneFinderTest, findNSEC3SignedWithDNSSEC) {
+ // For NSEC3-signed zones, specifying the DNSSEC option shouldn't change
+ // anything (the NSEC3_SIGNED flag is always set, and no records are
+ // returned for negative cases regardless).
+ findCheck(ZoneFinder::RESULT_NSEC3_SIGNED, ZoneFinder::FIND_DNSSEC);
+}
+
TEST_F(InMemoryZoneFinderTest, findNSECSigned) {
+ // NSEC-signed zone, without requesting DNSSEC (no NSEC should be provided)
findCheck(ZoneFinder::RESULT_NSEC_SIGNED);
}
+// Generalized test for Empty Nonterminal (ENT) cases with NSEC
+void
+InMemoryZoneFinderTest::findNSECENTCheck(const Name& ent_name,
+ ConstRRsetPtr expected_nsec,
+ ZoneFinder::FindResultFlags expected_flags)
+{
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_emptywild_));
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_under_wild_));
+
+ // Sanity check: Should result in NXRRSET
+ findTest(ent_name, RRType::A(), ZoneFinder::NXRRSET, true,
+ ConstRRsetPtr(), expected_flags);
+ // Sanity check: No NSEC added yet
+ findTest(ent_name, RRType::A(), ZoneFinder::NXRRSET, true,
+ ConstRRsetPtr(), expected_flags,
+ NULL, ZoneFinder::FIND_DNSSEC);
+
+ // Now add the NSEC rrs making it a 'complete' zone (in terms of NSEC,
+ // there are no sigs)
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_nsec_));
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_ent_nsec2_));
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_ent_nsec3_));
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_ent_nsec4_));
+
+ // Should result in NXRRSET, and RESULT_NSEC_SIGNED
+ findTest(ent_name, RRType::A(), ZoneFinder::NXRRSET, true,
+ ConstRRsetPtr(),
+ expected_flags | ZoneFinder::RESULT_NSEC_SIGNED);
+
+ // And check for the NSEC if DNSSEC_OK
+ findTest(ent_name, RRType::A(), ZoneFinder::NXRRSET, true,
+ expected_nsec, expected_flags | ZoneFinder::RESULT_NSEC_SIGNED,
+ NULL, ZoneFinder::FIND_DNSSEC);
+}
+
+TEST_F(InMemoryZoneFinderTest,findNSECEmptyNonterminal) {
+ // Non-wildcard case
+ findNSECENTCheck(Name("wild.example.org"), rr_ent_nsec3_);
+}
+
+TEST_F(InMemoryZoneFinderTest,findNSECEmptyNonterminalWildcard) {
+ // Wildcard case, above actual wildcard
+ findNSECENTCheck(Name("foo.example.org"), rr_nsec_);
+}
+
+TEST_F(InMemoryZoneFinderTest,findNSECEmptyNonterminalAtWildcard) {
+ // Wildcard case, at actual wildcard
+ findNSECENTCheck(Name("bar.foo.example.org"), rr_nsec_,
+ ZoneFinder::RESULT_WILDCARD);
+}
+
+TEST_F(InMemoryZoneFinderTest, findNSECSignedWithDNSSEC) {
+ // NSEC-signed zone, requesting DNSSEC (NSEC should be provided)
+ findCheck(ZoneFinder::RESULT_NSEC_SIGNED, ZoneFinder::FIND_DNSSEC);
+}
+
void
InMemoryZoneFinderTest::emptyNodeCheck(
ZoneFinder::FindResultFlags expected_flags)
@@ -1183,7 +1308,8 @@ TEST_F(InMemoryZoneFinderTest, loadFromIterator) {
*/
void
InMemoryZoneFinderTest::wildcardCheck(
- ZoneFinder::FindResultFlags expected_flags)
+ ZoneFinder::FindResultFlags expected_flags,
+ ZoneFinder::FindOptions find_options)
{
/*
* example.org.
@@ -1195,7 +1321,6 @@ InMemoryZoneFinderTest::wildcardCheck(
// If the zone is "signed" (detecting it by the NSEC/NSEC3 signed flags),
// add RRSIGs to the records.
- ZoneFinder::FindOptions find_options = ZoneFinder::FIND_DEFAULT;
if ((expected_flags & ZoneFinder::RESULT_NSEC_SIGNED) != 0 ||
(expected_flags & ZoneFinder::RESULT_NSEC3_SIGNED) != 0) {
// Convenience shortcut. The RDATA is not really validatable, but
@@ -1225,8 +1350,25 @@ InMemoryZoneFinderTest::wildcardCheck(
// be in the wildcard (so check the wildcard isn't matched at the parent)
{
SCOPED_TRACE("Search at parent");
- findTest(Name("wild.example.org"), RRType::A(), ZoneFinder::NXRRSET,
- true, ConstRRsetPtr(), expected_flags, NULL, find_options);
+ if ((expected_flags & ZoneFinder::RESULT_NSEC_SIGNED) != 0) {
+ findTest(Name("wild.example.org"), RRType::A(),
+ ZoneFinder::NXRRSET, true, rr_nsec_, expected_flags,
+ NULL, find_options);
+ } else {
+ findTest(Name("wild.example.org"), RRType::A(),
+ ZoneFinder::NXRRSET, true, ConstRRsetPtr(),
+ expected_flags, NULL, find_options);
+ }
+ }
+
+ // For the test setup of "NSEC-signed" zone, we might expect it will
+ // be returned with a negative result, either because wildcard match is
+ // disabled by the search option or because wildcard match is canceled
+ // per protocol.
+ ConstRRsetPtr expected_nsec; // by default it's NULL
+ if ((expected_flags & ZoneFinder::RESULT_NSEC_SIGNED) != 0 &&
+ (find_options & ZoneFinder::FIND_DNSSEC) != 0) {
+ expected_nsec = rr_nsec_;
}
// Search the original name of wildcard
@@ -1236,45 +1378,70 @@ InMemoryZoneFinderTest::wildcardCheck(
true, rr_wild_, ZoneFinder::RESULT_DEFAULT, NULL,
find_options);
}
+
+ // Below some of the test cases will normally result in a wildcard match;
+ // if NO_WILDCARD is specified, it should result in NXDOMAIN instead,
+ // and, when available and requested, the covering NSEC will be returned.
+ // The following are shortcut parameters to unify these cases.
+ const bool wild_ok = ((find_options & ZoneFinder::NO_WILDCARD) == 0);
+ const ZoneFinder::FindResultFlags wild_expected_flags =
+ wild_ok ? (ZoneFinder::RESULT_WILDCARD | expected_flags) :
+ expected_flags;
+
// Search "created" name.
{
SCOPED_TRACE("Search at created child");
- findTest(Name("a.wild.example.org"), RRType::A(), ZoneFinder::SUCCESS,
- false, rr_wild_,
- ZoneFinder::RESULT_WILDCARD | expected_flags, NULL,
- find_options, true);
- // Wildcard match, but no data
- findTest(Name("a.wild.example.org"), RRType::AAAA(),
- ZoneFinder::NXRRSET, true, ConstRRsetPtr(),
- ZoneFinder::RESULT_WILDCARD | expected_flags, NULL,
- find_options);
+ findTest(Name("a.wild.example.org"), RRType::A(),
+ wild_ok ? ZoneFinder::SUCCESS : ZoneFinder::NXDOMAIN, false,
+ wild_ok ? rr_wild_ : expected_nsec,
+ wild_expected_flags, NULL, find_options, wild_ok);
}
// Search name that has CNAME.
{
SCOPED_TRACE("Matching CNAME");
findTest(Name("a.cnamewild.example.org"), RRType::A(),
- ZoneFinder::CNAME, false, rr_cnamewild_,
- ZoneFinder::RESULT_WILDCARD | expected_flags, NULL,
- find_options, true);
+ wild_ok ? ZoneFinder::CNAME : ZoneFinder::NXDOMAIN, false,
+ wild_ok ? rr_cnamewild_ : expected_nsec,
+ wild_expected_flags, NULL, find_options, wild_ok);
}
// Search another created name, this time little bit lower
{
SCOPED_TRACE("Search at created grand-child");
findTest(Name("a.b.wild.example.org"), RRType::A(),
- ZoneFinder::SUCCESS, false, rr_wild_,
- ZoneFinder::RESULT_WILDCARD | expected_flags, NULL,
- find_options, true);
+ wild_ok ? ZoneFinder::SUCCESS : ZoneFinder::NXDOMAIN, false,
+ wild_ok ? rr_wild_ : expected_nsec,
+ wild_expected_flags, NULL, find_options, wild_ok);
}
EXPECT_EQ(SUCCESS, zone_finder_.add(rr_under_wild_));
{
SCOPED_TRACE("Search under non-wildcard");
findTest(Name("bar.foo.wild.example.org"), RRType::A(),
- ZoneFinder::NXDOMAIN, true, ConstRRsetPtr(), expected_flags,
+ ZoneFinder::NXDOMAIN, true, expected_nsec, expected_flags,
NULL, find_options);
}
+
+ // Wildcard match, but no data. We add the additional NSEC at the wildcard
+ // at this point so that it wouldn't break other tests above. Note also
+ // that in the NO_WILDCARD case the resulting NSEC is the same. Ideally
+ // we could use a more tricky setup so we can distinguish these cases,
+ // but for this purpose it's not bad; what we'd like to test here is that
+ // wildcard substitution doesn't happen for either case, and the
+ // NO_WILDCARD effect itself can be checked by the result code (NXDOMAIN).
+ ConstRRsetPtr expected_wild_nsec; // by default it's NULL
+ if ((expected_flags & ZoneFinder::RESULT_NSEC_SIGNED) != 0) {
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_wild_nsec_));
+ expected_wild_nsec = rr_wild_nsec_;
+ }
+ {
+ SCOPED_TRACE("Search at wildcard, no data");
+ findTest(Name("a.wild.example.org"), RRType::AAAA(),
+ wild_ok ? ZoneFinder::NXRRSET : ZoneFinder::NXDOMAIN, true,
+ wild_ok ? expected_wild_nsec : expected_wild_nsec,
+ wild_expected_flags, NULL, find_options);
+ }
}
TEST_F(InMemoryZoneFinderTest, wildcard) {
@@ -1288,10 +1455,22 @@ TEST_F(InMemoryZoneFinderTest, wildcardNSEC3) {
}
TEST_F(InMemoryZoneFinderTest, wildcardNSEC) {
- // Similar to the previous one, but the zone signed with NSEC
+ // Similar to the previous one, but the zone is signed with NSEC
wildcardCheck(ZoneFinder::RESULT_NSEC_SIGNED);
}
+TEST_F(InMemoryZoneFinderTest, wildcardDisabledWithNSEC) {
+ // Wildcard is disabled. In practice, this is used as part of query
+ // processing for an NSEC-signed zone, so we test that case specifically.
+ wildcardCheck(ZoneFinder::RESULT_NSEC_SIGNED, ZoneFinder::NO_WILDCARD);
+}
+
+TEST_F(InMemoryZoneFinderTest, wildcardDisabledWithoutNSEC) {
+ // Similar to the previous once, but check the behavior for a non signed
+ // zone just in case.
+ wildcardCheck(ZoneFinder::RESULT_DEFAULT, ZoneFinder::NO_WILDCARD);
+}
+
/*
* Test that we don't match a wildcard if we get under delegation.
* By 4.3.3 of RFC1034:
@@ -1495,15 +1674,29 @@ TEST_F(InMemoryZoneFinderTest, nestedEmptyWildcard) {
// situations
void
InMemoryZoneFinderTest::doCancelWildcardCheck(
- ZoneFinder::FindResultFlags expected_flags)
+ ZoneFinder::FindResultFlags expected_flags,
+ ZoneFinder::FindOptions find_options)
{
// These should be canceled
{
SCOPED_TRACE("Canceled under foo.wild.example.org");
+
+ // For an NSEC-signed zone with DNSSEC requested, the covering NSEC
+ // should be returned. The expected NSEC is actually just the only
+ // NSEC in the test data, but in this context it doesn't matter;
+ // it's sufficient just to check any NSEC is returned (or not).
+ ConstRRsetPtr expected_nsec; // by default it's NULL
+ if ((expected_flags & ZoneFinder::RESULT_NSEC_SIGNED) != 0 &&
+ (find_options & ZoneFinder::FIND_DNSSEC)) {
+ expected_nsec = rr_nsec_;
+ }
+
findTest(Name("aaa.foo.wild.example.org"), RRType::A(),
- ZoneFinder::NXDOMAIN, true, ConstRRsetPtr(), expected_flags);
+ ZoneFinder::NXDOMAIN, true, expected_nsec, expected_flags,
+ NULL, find_options);
findTest(Name("zzz.foo.wild.example.org"), RRType::A(),
- ZoneFinder::NXDOMAIN, true, ConstRRsetPtr(), expected_flags);
+ ZoneFinder::NXDOMAIN, true, expected_nsec, expected_flags,
+ NULL, find_options);
}
// This is existing, non-wildcard domain, shouldn't wildcard at all
@@ -1571,6 +1764,7 @@ TEST_F(InMemoryZoneFinderTest, cancelWildcard) {
}
}
+// Same tests as cancelWildcard for NSEC3-signed zone
TEST_F(InMemoryZoneFinderTest, cancelWildcardNSEC3) {
EXPECT_EQ(SUCCESS, zone_finder_.add(rr_wild_));
EXPECT_EQ(SUCCESS, zone_finder_.add(rr_not_wild_));
@@ -1587,6 +1781,29 @@ TEST_F(InMemoryZoneFinderTest, cancelWildcardNSEC3) {
}
}
+// Same tests as cancelWildcard for NSEC-signed zone. Check both cases with
+// or without FIND_DNSSEC option. NSEC should be returned only when the option
+// is given.
+TEST_F(InMemoryZoneFinderTest, cancelWildcardNSEC) {
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_wild_));
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_not_wild_));
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_nsec_));
+
+ {
+ SCOPED_TRACE("Runnig with single entry under foo.wild.example.org");
+ doCancelWildcardCheck(ZoneFinder::RESULT_NSEC_SIGNED,
+ ZoneFinder::FIND_DNSSEC);
+ doCancelWildcardCheck(ZoneFinder::RESULT_NSEC_SIGNED);
+ }
+ EXPECT_EQ(SUCCESS, zone_finder_.add(rr_not_wild_another_));
+ {
+ SCOPED_TRACE("Runnig with two entries under foo.wild.example.org");
+ doCancelWildcardCheck(ZoneFinder::RESULT_NSEC_SIGNED,
+ ZoneFinder::FIND_DNSSEC);
+ doCancelWildcardCheck(ZoneFinder::RESULT_NSEC_SIGNED);
+ }
+}
+
TEST_F(InMemoryZoneFinderTest, loadBadWildcard) {
// We reject loading the zone if it contains a wildcard name for
// NS or DNAME.
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index b26a22b..25eafb4 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -180,10 +180,10 @@ TEST_F(RBTreeTest, findName) {
TEST_F(RBTreeTest, findError) {
// For the version that takes a node chain, the chain must be empty.
RBTreeNodeChain<int> chain;
- EXPECT_EQ(RBTree<int>::EXACTMATCH, rbtree.find<void*>(Name("a"), &crbtnode,
- chain, NULL, NULL));
+ EXPECT_EQ(RBTree<int>::EXACTMATCH, rbtree.find(Name("a"), &crbtnode,
+ chain));
// trying to reuse the same chain. it should result in an exception.
- EXPECT_THROW(rbtree.find<void*>(Name("a"), &crbtnode, chain, NULL, NULL),
+ EXPECT_THROW(rbtree.find(Name("a"), &crbtnode, chain),
BadValue);
}
@@ -280,7 +280,7 @@ TEST_F(RBTreeTest, chainLevel) {
Name node_name(Name::ROOT_NAME());
EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- tree.find<void*>(node_name, &crbtnode, chain, NULL, NULL));
+ tree.find(node_name, &crbtnode, chain));
EXPECT_EQ(1, chain.getLevelCount());
/*
@@ -303,8 +303,7 @@ TEST_F(RBTreeTest, chainLevel) {
EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
RBTreeNodeChain<int> found_chain;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- tree.find<void*>(node_name, &crbtnode, found_chain,
- NULL, NULL));
+ tree.find(node_name, &crbtnode, found_chain));
EXPECT_EQ(i, found_chain.getLevelCount());
}
@@ -339,6 +338,11 @@ TEST_F(RBTreeTest, getAbsoluteNameError) {
* / \
* 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"};
+const size_t name_count(sizeof(names) / sizeof(*names));
+
TEST_F(RBTreeTest, nextNode) {
const char* const names[] = {
"a", "b", "c", "d.e.f", "x.d.e.f", "w.y.d.e.f", "o.w.y.d.e.f",
@@ -347,8 +351,7 @@ TEST_F(RBTreeTest, nextNode) {
RBTreeNodeChain<int> node_path;
const RBNode<int>* node = NULL;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- rbtree.find<void*>(Name(names[0]), &node, node_path, NULL,
- NULL));
+ rbtree.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());
@@ -359,6 +362,174 @@ TEST_F(RBTreeTest, nextNode) {
EXPECT_EQ(static_cast<void*>(NULL), node);
}
+// Just walk using previousNode until the beginning of the tree and check it is
+// OK
+//
+// rbtree - 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(RBTree<int>& rbtree, const RBNode<int>* node,
+ RBTreeNodeChain<int>& 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 = rbtree.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 RBNode<int>* node2(NULL);
+ RBTreeNodeChain<int> node_path2;
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree.find(Name(names[i - 1]), &node2, node_path2));
+ EXPECT_EQ(node, node2);
+ }
+ node = rbtree.previousNode(node_path);
+ }
+
+ // We should have reached the start of the tree.
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+}
+
+// Check the previousNode
+TEST_F(RBTreeTest, previousNode) {
+ // First, iterate the whole tree from the end to the beginning.
+ RBTreeNodeChain<int> node_path;
+ EXPECT_THROW(rbtree.previousNode(node_path), isc::BadValue) <<
+ "Throw before a search was done on the path";
+ const RBNode<int>* node(NULL);
+ {
+ SCOPED_TRACE("Iterate through");
+ EXPECT_EQ(RBTree<int>::EXACTMATCH,
+ rbtree.find(Name(names[name_count - 1]), &node, node_path));
+ previousWalk(rbtree, 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(RBTree<int>::EXACTMATCH,
+ rbtree.find(Name(names[4]), &node, node_path));
+ previousWalk(rbtree, 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(RBTree<int>::EXACTMATCH,
+ rbtree.find(Name(names[0]), &node, node_path));
+ EXPECT_NE(static_cast<void*>(NULL), node);
+ EXPECT_EQ(static_cast<void*>(NULL), rbtree.previousNode(node_path));
+ 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 nor
+ EXPECT_EQ(RBTree<int>::NOTFOUND,
+ rbtree.find<void*>(Name("0"), &node, node_path, NULL, NULL));
+ EXPECT_EQ(static_cast<void*>(NULL), node);
+ EXPECT_EQ(static_cast<void*>(NULL), rbtree.previousNode(node_path));
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Start after the last");
+ EXPECT_EQ(RBTree<int>::NOTFOUND,
+ rbtree.find(Name("z"), &node, node_path));
+ previousWalk(rbtree, 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(RBTree<int>::PARTIALMATCH,
+ rbtree.find(Name("b.c"), &node, node_path));
+ previousWalk(rbtree, 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(RBTree<int>::NOTFOUND,
+ rbtree.find(Name("xy.d.e.f"), &node, node_path));
+ previousWalk(rbtree, 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(RBTree<int>::NOTFOUND,
+ rbtree.find(Name("yz.d.e.f"), &node, node_path));
+ previousWalk(rbtree, node, node_path, 9, 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(RBTree<int>::NOTFOUND,
+ rbtree.find(Name("e.f"), &node, node_path));
+ previousWalk(rbtree, node, node_path, 3, true);
+ node = NULL;
+ node_path.clear();
+ }
+
+ {
+ SCOPED_TRACE("Lookup in empty tree");
+ // Just check it doesn't crash, etc.
+ RBTree<int> empty_tree;
+ EXPECT_EQ(RBTree<int>::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(RBTreeTest, nextNodeError) {
// Empty chain for nextNode() is invalid.
RBTreeNodeChain<int> chain;
@@ -394,7 +565,7 @@ TEST_F(RBTreeTest, getLastComparedNode) {
// A search for an empty tree should result in no 'last compared', too.
RBTree<int> empty_tree;
EXPECT_EQ(RBTree<int>::NOTFOUND,
- empty_tree.find<void*>(Name("a"), &crbtnode, chain, NULL, NULL));
+ empty_tree.find(Name("a"), &crbtnode, chain));
EXPECT_EQ(static_cast<void*>(NULL), chain.getLastComparedNode());
chain.clear();
@@ -402,8 +573,7 @@ TEST_F(RBTreeTest, getLastComparedNode) {
// Exact match case. The returned node should be last compared.
EXPECT_EQ(RBTree<int>::EXACTMATCH,
- tree.find<void*>(Name("x.d.e.f"), &expected_node, chain,
- NULL, NULL));
+ tree.find(Name("x.d.e.f"), &expected_node, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
// 2 = # labels of "x."
comparisonChecks(chain, 0, 2, NameComparisonResult::EQUAL);
@@ -414,8 +584,7 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::EXACTMATCH,
tree.find(Name("i.g.h"), &expected_node));
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
- tree.find<void*>(Name("x.i.g.h"), &crbtnode, chain,
- NULL, NULL));
+ tree.find(Name("x.i.g.h"), &crbtnode, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
// i.g.h < x.i.g.h, 2 = # labels of "i."
comparisonChecks(chain, 1, 2, NameComparisonResult::SUBDOMAIN);
@@ -426,8 +595,7 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::EXACTMATCH,
tree.find(Name("x.d.e.f"), &expected_node));
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
- tree.find<void*>(Name("a.d.e.f"), &crbtnode, chain,
- NULL, NULL));
+ tree.find(Name("a.d.e.f"), &crbtnode, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
// a < x, 1 = # labels of "." (trailing dot)
comparisonChecks(chain, -1, 1, NameComparisonResult::COMMONANCESTOR);
@@ -438,8 +606,7 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::EXACTMATCH,
tree.find(Name("z.d.e.f"), &expected_node));
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
- tree.find<void*>(Name("zz.d.e.f"), &crbtnode, chain,
- NULL, NULL));
+ tree.find(Name("zz.d.e.f"), &crbtnode, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
// zz > z, 1 = # labels of "." (trailing dot)
comparisonChecks(chain, 1, 1, NameComparisonResult::COMMONANCESTOR);
@@ -450,8 +617,7 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::EXACTMATCH,
tree.find(Name("w.y.d.e.f"), &expected_node));
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
- tree.find<void*>(Name("y.d.e.f"), &crbtnode, chain,
- NULL, NULL));
+ tree.find(Name("y.d.e.f"), &crbtnode, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
// y < w.y, 2 = # labels of "y."
comparisonChecks(chain, -1, 2, NameComparisonResult::SUPERDOMAIN);
@@ -461,8 +627,7 @@ TEST_F(RBTreeTest, getLastComparedNode) {
// with the search name in the subtree below the matching node.
// (the expected node is the same as the previous case)
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
- tree.find<void*>(Name("z.y.d.e.f"), &crbtnode, chain,
- NULL, NULL));
+ tree.find(Name("z.y.d.e.f"), &crbtnode, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
// z.y > w.y, 2 = # labels of "y."
comparisonChecks(chain, 1, 2, NameComparisonResult::COMMONANCESTOR);
@@ -471,7 +636,7 @@ TEST_F(RBTreeTest, getLastComparedNode) {
// Search stops in the highest level after following a left branch.
EXPECT_EQ(RBTree<int>::EXACTMATCH, tree.find(Name("c"), &expected_node));
EXPECT_EQ(RBTree<int>::NOTFOUND,
- tree.find<void*>(Name("bb"), &crbtnode, chain, NULL, NULL));
+ tree.find(Name("bb"), &crbtnode, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
// bb < c, 1 = # labels of "." (trailing dot)
comparisonChecks(chain, -1, 1, NameComparisonResult::COMMONANCESTOR);
@@ -480,7 +645,7 @@ TEST_F(RBTreeTest, getLastComparedNode) {
// Search stops in the highest level after following a right branch.
// (the expected node is the same as the previous case)
EXPECT_EQ(RBTree<int>::NOTFOUND,
- tree.find<void*>(Name("d"), &crbtnode, chain, NULL, NULL));
+ tree.find(Name("d"), &crbtnode, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
// d > c, 1 = # labels of "." (trailing dot)
comparisonChecks(chain, 1, 1, NameComparisonResult::COMMONANCESTOR);
More information about the bind10-changes
mailing list