BIND 10 master, updated. c6de8f18c1676baf8ec66ddc2c37f70d3c5b27fe [master] Merge branch 'trac2091b'
BIND 10 source code commits
bind10-changes at lists.isc.org
Sat Jul 28 23:58:45 UTC 2012
The branch, master has been updated
via c6de8f18c1676baf8ec66ddc2c37f70d3c5b27fe (commit)
via 01d1c2a889b50b24141541a10c8cf7d20c7db7dd (commit)
via fd4efa02baeae2f5ce719a8dd2db1a6da1f512b4 (commit)
via 1ee0d41198397e9772d7b833231c96dae50f944f (commit)
via 98181a847e71f8a502f5614158bf2ade6dd8fc5f (commit)
via 69fd22252b4e4850e8adc767848d997901023d39 (commit)
via a79037eb4aee4116ffe8a3b980cfad2d6a625803 (commit)
via 90e3121ad4b59d78682b9aad79da414c5fbda374 (commit)
via b4067dc72c42318a708c73f19fbfe5e3e0cc32bc (commit)
via 3093d3696dd1b882abe4fb5200903f4b4e97b2fb (commit)
via a03aed77a96c240ed71a4cfd6ab6ec7eba364f5b (commit)
via ac9299c65b0b712f1b5df429dca8ae4f254536b3 (commit)
via 6535fcf60c69445751261e593a1f740e77fbd0bb (commit)
via 78fe82d12838c8daead5477e612de9b7470c13c5 (commit)
via b805d99d2c615dc4ef49f3c1c255c490cc0bd9a6 (commit)
via 49a336ef47649db5165f047e37825dbfb2ab9b61 (commit)
via ecd6c30cc2e568d499e8fc9d97926ecef38a924c (commit)
via 5b7ac017e39647e49e3ecbaa874092b0028449e1 (commit)
via 9cc4ac55654683d19af4b55e651d486626f583e8 (commit)
via f5f665b93cb2f1b1d03a8b5de23c4672cff497d6 (commit)
via 34f0efc4296a8e142b90d862a983b2452e5c46a8 (commit)
via f554bfb2cfc6b108e253214aae99fbdd7f75593c (commit)
via 0c5ac6b64b8100e5446fd48ba8eae43b25157485 (commit)
via b8eb94ff7d736acaa5e8a1f09044617e66958a5d (commit)
via 9256f0d5a0cc43f87ebfb80588687221aca7b3fa (commit)
via d6b44e0b1af751de561e2ededf302389f3507579 (commit)
via 2e99938fc9fd5db8fe35405cecfdc591b0156600 (commit)
from 3e4bfd2ac7309a2553925e61c6464ae6d1ec0d21 (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 c6de8f18c1676baf8ec66ddc2c37f70d3c5b27fe
Merge: 3e4bfd2 01d1c2a
Author: JINMEI Tatuya <jinmei at isc.org>
Date: Sat Jul 28 16:47:33 2012 -0700
[master] Merge branch 'trac2091b'
-----------------------------------------------------------------------
Summary of changes:
src/lib/datasrc/memory/rdata_encoder.cc | 26 +-
src/lib/datasrc/memory_datasrc.cc | 103 ++++--
src/lib/datasrc/rbtree.h | 460 ++++++++++++++++++---------
src/lib/datasrc/tests/Makefile.am | 1 +
src/lib/datasrc/tests/rbtree_unittest.cc | 335 ++++++++++++-------
src/lib/datasrc/tests/zonetable_unittest.cc | 63 ++--
src/lib/datasrc/zonetable.cc | 47 ++-
src/lib/datasrc/zonetable.h | 41 ++-
src/lib/dns/labelsequence.cc | 153 ++++-----
src/lib/dns/labelsequence.h | 131 ++++----
src/lib/dns/name.h | 39 ++-
src/lib/dns/tests/labelsequence_unittest.cc | 312 ++++++++----------
12 files changed, 1018 insertions(+), 693 deletions(-)
-----------------------------------------------------------------------
diff --git a/src/lib/datasrc/memory/rdata_encoder.cc b/src/lib/datasrc/memory/rdata_encoder.cc
index 5d32cc5..973eb9a 100644
--- a/src/lib/datasrc/memory/rdata_encoder.cc
+++ b/src/lib/datasrc/memory/rdata_encoder.cc
@@ -297,18 +297,10 @@ encodeRdata(const rdata::Rdata& rdata, RRClass rrclass, RRType rrtype,
{
const Name name(ibuffer);
const LabelSequence labels(name);
- size_t nlen;
- const uint8_t* ndata = labels.getData(&nlen);
- assert(nlen < 256); // nlen should fit in 8 bits
- size_t olen;
- uint8_t offset_holder[Name::MAX_LABELS];
- labels.getOffsetData(&olen, offset_holder);
- assert(olen < 256); // olen should fit in 8 bits
- data_result.push_back(nlen);
- data_result.push_back(olen);
- data_result.insert(data_result.end(), ndata, ndata + nlen);
- data_result.insert(data_result.end(), offset_holder,
- offset_holder + olen);
+ uint8_t labels_holder[LabelSequence::MAX_SERIALIZED_LENGTH];
+ labels.serialize(labels_holder, sizeof(labels_holder));
+ data_result.insert(data_result.end(), labels_holder,
+ labels_holder + labels.getSerializedLength());
break;
}
}
@@ -348,15 +340,11 @@ foreachRdataField(RRClass rrclass, RRType rrtype,
case RdataFieldSpec::DOMAIN_NAME:
{
++name_count;
- const uint8_t nlen = encoded_data.at(off);
- const uint8_t olen = encoded_data.at(off + 1);
+ const LabelSequence labels(&encoded_data.at(off));
if (name_callback) {
- const uint8_t* ndata = &encoded_data.at(off + 2);
- const uint8_t* odata = &encoded_data.at(off + 2 + nlen);
- name_callback(LabelSequence(ndata, odata, olen),
- field_spec.name_attributes);
+ name_callback(labels, field_spec.name_attributes);
}
- off += (2 + nlen + olen);
+ off += labels.getSerializedLength();
break;
}
}
diff --git a/src/lib/datasrc/memory_datasrc.cc b/src/lib/datasrc/memory_datasrc.cc
index c5122bf..372141a 100644
--- a/src/lib/datasrc/memory_datasrc.cc
+++ b/src/lib/datasrc/memory_datasrc.cc
@@ -14,6 +14,8 @@
#include <exceptions/exceptions.h>
+#include <util/memory_segment_local.h>
+
#include <dns/name.h>
#include <dns/nsec3hash.h>
#include <dns/rdataclass.h>
@@ -120,19 +122,48 @@ typedef NSEC3Map::value_type NSEC3Pair;
// Actual zone data: Essentially a set of zone's RRs. This is defined as
// a separate structure so that it'll be replaceable on reload.
struct ZoneData {
+ // Note: this code is not entirely exception safe; domains_storage_ could
+ // leak if the constructor throws. But since it's an intermediate version
+ // toward a full revision and the actual risk of leak should be very small
+ // in practice, we leave it open for now.
ZoneData(const Name& origin) :
- domains_(true),
+ domains_storage_(DomainTree::create(local_mem_sgmt_, true)),
+ domains_(*domains_storage_),
+ aux_wild_domains_(NULL),
origin_data_(NULL),
nsec_signed_(false)
{
// We create the node for origin (it needs to exist anyway in future)
- domains_.insert(origin, &origin_data_);
+ domains_.insert(local_mem_sgmt_, origin, &origin_data_);
DomainPtr origin_domain(new Domain);
origin_data_->setData(origin_domain);
}
- // The main data (name + RRsets)
- DomainTree domains_;
+ ~ZoneData() {
+ DomainTree::destroy(local_mem_sgmt_, domains_storage_);
+ if (aux_wild_domains_ != NULL) {
+ DomainTree::destroy(local_mem_sgmt_, aux_wild_domains_);
+ }
+
+ // The assert may be too harsh, but we assume we'll discard (rewrite)
+ // this code soon enough. Until then this would be a good way to
+ // detect any memory leak. Also, at that point we shouldn't use
+ // a single separate memory segment for each zone tree; normally
+ // zone data for multiple zones will be managed in a single segment.
+ assert(local_mem_sgmt_.allMemoryDeallocated());
+ }
+
+ // Memory segment to allocate/deallocate memory for the tree and the nodes.
+ // (This will eventually have to be abstract; for now we hardcode the
+ // specific derived segment class).
+ util::MemorySegmentLocal local_mem_sgmt_;
+
+ // The main data (name + RRsets). We use domains_ as a reference to
+ // domains_storage_ so we don't have to update the rest of the code;
+ // it will eventually have to be revised substantially, at which point
+ // we should clean this up, too.
+ DomainTree* domains_storage_;
+ DomainTree& domains_;
// An auxiliary tree for wildcard expanded data used in additional data
// processing. It contains names like "ns.wild.example" in the following
@@ -150,11 +181,11 @@ struct ZoneData {
// should be even empty, and even if it has content it should be very
// small.
private:
- scoped_ptr<DomainTree> aux_wild_domains_;
+ DomainTree* aux_wild_domains_;
public:
DomainTree& getAuxWildDomains() {
- if (!aux_wild_domains_) {
- aux_wild_domains_.reset(new DomainTree);
+ if (aux_wild_domains_ == NULL) {
+ aux_wild_domains_ = DomainTree::create(local_mem_sgmt_);
}
return (*aux_wild_domains_);
}
@@ -448,15 +479,11 @@ ZoneData::findNode(const Name& name, RBTreeNodeChain<Domain>& node_path,
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) {
- // Wildcard canceled. Treat it as NXDOMAIN.
- // Note: Because the way the tree stores relative names, we
- // will have exactly one common label (the ".") in case we have
- // nothing common under the node we got, and we will get
- // more common labels otherwise (yes, this relies on the
- // internal RBTree structure, which leaks out through this
- // little bit).
+ NameComparisonResult::COMMONANCESTOR) {
+ // This means, e.g., we have *.wild.example and
+ // bar.foo.wild.example and are looking for
+ // baz.foo.wild.example. The common ancestor, foo.wild.example,
+ // should cancel wildcard. Treat it as NXDOMAIN.
LOG_DEBUG(logger, DBG_TRACE_DATA,
DATASRC_MEM_WILDCARD_CANCEL).arg(name);
return (ResultType(ZoneFinder::NXDOMAIN, NULL,
@@ -857,7 +884,9 @@ struct InMemoryZoneFinder::InMemoryZoneFinderImpl {
//
// We also perform the same trick for empty wild card names possibly
// contained in 'name' (e.g., '*.foo.example' in 'bar.*.foo.example').
- void addWildcards(DomainTree& domains, const Name& name) {
+ void addWildcards(util::MemorySegment& mem_sgmt, DomainTree& domains,
+ const Name& name)
+ {
Name wname(name);
const unsigned int labels(wname.getLabelCount());
const unsigned int origin_labels(origin_.getLabelCount());
@@ -870,7 +899,8 @@ struct InMemoryZoneFinder::InMemoryZoneFinderImpl {
// Ensure a separate level exists for the "wildcarding" name,
// and mark the node as "wild".
DomainNode* node;
- DomainTree::Result result(domains.insert(wname.split(1),
+ DomainTree::Result result(domains.insert(mem_sgmt,
+ wname.split(1),
&node));
assert(result == DomainTree::SUCCESS ||
result == DomainTree::ALREADYEXISTS);
@@ -880,7 +910,7 @@ struct InMemoryZoneFinder::InMemoryZoneFinderImpl {
// Note: for 'name' itself we do this later anyway, but the
// overhead should be marginal because wildcard names should
// be rare.
- result = domains.insert(wname, &node);
+ result = domains.insert(mem_sgmt, wname, &node);
assert(result == DomainTree::SUCCESS ||
result == DomainTree::ALREADYEXISTS);
}
@@ -1167,12 +1197,14 @@ struct InMemoryZoneFinder::InMemoryZoneFinderImpl {
// tree.
// Note: this can throw an exception, breaking strong exception
// guarantee. (see also the note for contextCheck() below).
- addWildcards(zone_data.domains_, rrset->getName());
+ addWildcards(zone_data.local_mem_sgmt_, zone_data.domains_,
+ rrset->getName());
// Get the node
DomainNode* node;
- DomainTree::Result result = zone_data.domains_.insert(rrset->getName(),
- &node);
+ DomainTree::Result result =
+ zone_data.domains_.insert(zone_data.local_mem_sgmt_,
+ rrset->getName(), &node);
// Just check it returns reasonable results
assert((result == DomainTree::SUCCESS ||
result == DomainTree::ALREADYEXISTS) && node!= NULL);
@@ -1605,7 +1637,8 @@ addAdditional(RBNodeRRset* rrset, ZoneData* zone_data,
// Wildcard and glue shouldn't coexist. Make it sure here.
assert(!node->getFlag(domain_flag::GLUE));
- if (zone_data->getAuxWildDomains().insert(name, &wildnode)
+ if (zone_data->getAuxWildDomains().insert(
+ zone_data->local_mem_sgmt_, name, &wildnode)
== DomainTree::SUCCESS) {
// If we first insert the node, copy the RRsets. If the
// original node was empty, we add empty data so
@@ -1782,9 +1815,22 @@ InMemoryZoneFinder::getFileName() const {
/// member variables later for new features.
class InMemoryClient::InMemoryClientImpl {
public:
- InMemoryClientImpl() : zone_count(0) {}
+ InMemoryClientImpl() : zone_count(0),
+ zone_table(ZoneTable::create(local_mem_sgmt))
+ {}
+ ~InMemoryClientImpl() {
+ ZoneTable::destroy(local_mem_sgmt, zone_table);
+
+ // see above for the assert().
+ assert(local_mem_sgmt.allMemoryDeallocated());
+ }
+
+ // Memory segment to allocate/deallocate memory for the zone table.
+ // (This will eventually have to be abstract; for now we hardcode the
+ // specific derived segment class).
+ util::MemorySegmentLocal local_mem_sgmt;
unsigned int zone_count;
- ZoneTable zone_table;
+ ZoneTable* zone_table;
};
InMemoryClient::InMemoryClient() : impl_(new InMemoryClientImpl)
@@ -1809,7 +1855,8 @@ InMemoryClient::addZone(ZoneFinderPtr zone_finder) {
LOG_DEBUG(logger, DBG_TRACE_BASIC, DATASRC_MEM_ADD_ZONE).
arg(zone_finder->getOrigin()).arg(zone_finder->getClass().toText());
- const result::Result result = impl_->zone_table.addZone(zone_finder);
+ const result::Result result =
+ impl_->zone_table->addZone(impl_->local_mem_sgmt, zone_finder);
if (result == result::SUCCESS) {
++impl_->zone_count;
}
@@ -1819,7 +1866,7 @@ InMemoryClient::addZone(ZoneFinderPtr zone_finder) {
InMemoryClient::FindResult
InMemoryClient::findZone(const isc::dns::Name& name) const {
LOG_DEBUG(logger, DBG_TRACE_DATA, DATASRC_MEM_FIND_ZONE).arg(name);
- ZoneTable::FindResult result(impl_->zone_table.findZone(name));
+ ZoneTable::FindResult result(impl_->zone_table->findZone(name));
return (FindResult(result.code, result.zone));
}
@@ -1925,7 +1972,7 @@ public:
ZoneIteratorPtr
InMemoryClient::getIterator(const Name& name, bool separate_rrs) const {
- ZoneTable::FindResult result(impl_->zone_table.findZone(name));
+ ZoneTable::FindResult result(impl_->zone_table->findZone(name));
if (result.code != result::SUCCESS) {
isc_throw(DataSourceError, "No such zone: " + name.toText());
}
diff --git a/src/lib/datasrc/rbtree.h b/src/lib/datasrc/rbtree.h
index e777f8f..cf61e0e 100644
--- a/src/lib/datasrc/rbtree.h
+++ b/src/lib/datasrc/rbtree.h
@@ -24,12 +24,15 @@
/// 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 <exceptions/exceptions.h>
+#include <boost/static_assert.hpp>
+
#include <ostream>
#include <algorithm>
#include <cassert>
@@ -37,27 +40,6 @@
namespace isc {
namespace datasrc {
-namespace helper {
-
-/// \brief Helper function to remove the base domain from super domain.
-///
-/// The precondition of this function is the super_name contains the
-/// sub_name so
-/// \code Name a("a.b.c");
-/// Name b("b.c");
-/// Name c = a - b;
-/// \endcode
-/// c will contain "a".
-///
-/// \note Functions in this namespace is not intended to be used outside of
-/// RBTree implementation.
-inline isc::dns::Name
-operator-(const isc::dns::Name& super_name, const isc::dns::Name& sub_name) {
- return (super_name.split(0, super_name.getLabelCount() -
- sub_name.getLabelCount()));
-}
-}
-
/// Forward declare RBTree class here is convinent for following friend
/// class declare inside RBNode and RBTreeNodeChain
template <typename T>
@@ -68,7 +50,7 @@ class RBTree;
///
/// This is meant to be used only from RBTree. It is meaningless to inherit it
/// or create instances of it from elsewhere. For that reason, the constructor
-/// is private.
+/// (and the allocator, see below) is private.
///
/// It serves three roles. One is to keep structure of the \c RBTree as a
/// red-black tree. For that purpose, it has left, right and parent pointers
@@ -83,6 +65,16 @@ class RBTree;
///
/// 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 RBTree). 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>
class RBNode : public boost::noncopyable {
private:
@@ -108,13 +100,70 @@ private:
/// "null" node.
RBNode();
- /// \brief Constructor from the node name.
- ///
- /// \param name The *relative* domain name (if this will live inside
- /// a.b.c and is called d.e.a.b.c, then you pass d.e).
- RBNode(const isc::dns::Name& name);
+ /// \brief Constructor from normal nodes.
+ RBNode(size_t labels_capacity);
+
+ /// \brief Destructor
+ ~RBNode();
//@}
+ /// \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 RBNode
+ ///
+ /// This static method allocates memory for a new \c RBNode 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 RBNode is allocated.
+ static RBNode<T>* create(util::MemorySegment& mem_sgmt,
+ const dns::LabelSequence& labels)
+ {
+ const size_t labels_len = labels.getSerializedLength();
+ void* p = mem_sgmt.allocate(sizeof(RBNode<T>) + labels_len);
+ RBNode<T>* node = new(p) RBNode<T>(labels_len);
+ labels.serialize(node->getLabelsData(), labels_len);
+ return (node);
+ }
+
+ /// \brief Destruct and deallocate \c RBNode
+ ///
+ /// \throw none
+ ///
+ /// \param mem_sgmt The \c MemorySegment that allocated memory for
+ /// \c rbnode.
+ /// \param rbnode A non NULL pointer to a valid \c RBNode 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, RBNode<T>* rbnode) {
+ const size_t labels_capacity = rbnode->labels_capacity_;
+ rbnode->~RBNode<T>();
+ mem_sgmt.deallocate(rbnode, sizeof(RBNode<T>) + 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:
/// \brief Alias for shared pointer to the data.
typedef boost::shared_ptr<T> NodeDataPtr;
@@ -132,9 +181,10 @@ public:
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 = 0x80000000U, ///< Application specific flag
- FLAG_USER2 = 0x40000000U, ///< Application specific flag
- FLAG_USER3 = 0x20000000U ///< Application specific flag
+ 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
@@ -147,17 +197,6 @@ private:
public:
- /// \brief Destructor
- ///
- /// It might seem strange that constructors are private and destructor
- /// public, but this is needed because of shared pointers need access
- /// to the destructor.
- ///
- /// You should never call anything like:
- /// \code delete pointer_to_node; \endcode
- /// The RBTree handles both creation and destructoion of nodes.
- ~RBNode();
-
/// \name Getter functions.
//@{
/// \brief Return the name of current node.
@@ -166,7 +205,26 @@ public:
///
/// To get the absolute name of one node, the node path from the top node
/// to current node has to be recorded.
- const isc::dns::Name& getName() const { return (name_); }
+ ///
+ /// \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.
///
@@ -370,11 +428,8 @@ private:
const RBNode<T>* getRight() const {
return (right_.get());
}
- RBNodeColor color_;
//@}
- /// \brief Relative name of the node.
- isc::dns::Name name_;
/// \brief Data stored here.
NodeDataPtr data_;
@@ -397,13 +452,25 @@ private:
return (down_.get());
}
- /// \brief If callback should be called when traversing this node in
- /// RBTree::find().
+ /// \brief Internal or user-configurable flags of node's properties.
///
- /// \todo It might be needed to put it into more general attributes field.
- uint32_t flags_;
-};
+ /// 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);
+};
// This is only to support NULL nodes.
template <typename T>
@@ -411,10 +478,9 @@ RBNode<T>::RBNode() :
parent_(NULL),
left_(NULL),
right_(NULL),
- // dummy name, the value doesn't matter:
- name_(isc::dns::Name::ROOT_NAME()),
down_(NULL),
- flags_(FLAG_SUBTREE_ROOT)
+ flags_(FLAG_SUBTREE_ROOT),
+ labels_capacity_(0)
{
// Some compilers object to use of "this" in initializer lists.
parent_ = this;
@@ -424,17 +490,16 @@ RBNode<T>::RBNode() :
}
template <typename T>
-RBNode<T>::RBNode(const isc::dns::Name& name) :
+RBNode<T>::RBNode(size_t labels_capacity) :
parent_(NULL_NODE()),
left_(NULL_NODE()),
right_(NULL_NODE()),
- name_(name),
down_(NULL_NODE()),
- flags_(FLAG_RED | FLAG_SUBTREE_ROOT)
+ flags_(FLAG_RED | FLAG_SUBTREE_ROOT),
+ labels_capacity_(labels_capacity)
{
}
-
template <typename T>
RBNode<T>::~RBNode() {
}
@@ -725,6 +790,8 @@ private:
*
* the tree will look like:
* \verbatim
+ .
+ |
b
/ \
a d.e.f
@@ -741,8 +808,6 @@ private:
\endverbatim
* \todo
* - add remove interface
- * - add iterator to iterate over the whole \c RBTree. This may be necessary,
- * for example, to support AXFR.
*/
template <typename T>
class RBTree : public boost::noncopyable {
@@ -759,18 +824,77 @@ public:
ALREADYEXISTS,
};
+ /// \brief Allocate and construct \c RBTree
+ ///
+ /// This static method allocates memory for a new \c RBTree 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 RBTree is allocated.
+ static RBTree* create(util::MemorySegment& mem_sgmt,
+ bool return_empty_node = false)
+ {
+ void* p = mem_sgmt.allocate(sizeof(RBTree<T>));
+ return (new(p) RBTree<T>(return_empty_node));
+ }
+
+ /// \brief Destruct and deallocate \c RBTree
+ ///
+ /// 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 rbtree and for all nodes inserted to the tree.
+ /// \param rbtree A non NULL pointer to a valid \c RBTree 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, RBTree<T>* rbtree) {
+ rbtree->deleteAllNodes(mem_sgmt);
+ rbtree->~RBTree<T>();
+ mem_sgmt.deallocate(rbtree, sizeof(RBTree<T>));
+ }
+
+private:
/// \name Constructor and Destructor
//@{
- /// The constructor.
+ /// \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 RBTree(bool returnEmptyNode = false);
- /// \b Note: RBTree is not intended to be inherited so the destructor
+ /// \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 RBTree is not intended to be inherited so the destructor
/// is not virtual
~RBTree();
//@}
+public:
+
/// \name Find methods
///
/// \brief Find the node that gives a longest match against the given name.
@@ -1045,6 +1169,9 @@ public:
/// 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.
@@ -1053,10 +1180,24 @@ public:
/// - SUCCESS The node was added.
/// - ALREADYEXISTS There was already a node of that name, so it was not
/// added.
- Result insert(const isc::dns::Name& name, RBNode<T>** inserted_node);
+ Result insert(util::MemorySegment& mem_sgmt, const isc::dns::Name& name,
+ RBNode<T>** 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(RBTree<T>& other) {
@@ -1079,7 +1220,7 @@ private:
/// \name Helper functions
//@{
/// \brief delete tree whose root is equal to node
- void deleteHelper(RBNode<T> *node);
+ void deleteHelper(util::MemorySegment& mem_sgmt, RBNode<T> *node);
/// \brief Print the information of given RBNode.
void dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
@@ -1088,11 +1229,15 @@ private:
/// \brief Indentation helper function for dumpTree
static void indent(std::ostream& os, unsigned int depth);
- /// Split one node into two nodes, keep the old node and create one new
- /// node, old node will hold the base name, new node will be the down node
- /// of old node, new node will hold the sub_name, the data
- /// of old node will be move into new node, and old node became non-terminal
- void nodeFission(RBNode<T>& node, const isc::dns::Name& sub_name);
+ /// 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 suffix labels, while the new node will hold the prefix.
+ /// The newly created node represents the labels that the original node
+ /// did, so necessary data are swapped.
+ /// (Note: as commented in the code, this behavior should be changed).
+ void nodeFission(util::MemorySegment& mem_sgmt, RBNode<T>& node,
+ const isc::dns::LabelSequence& new_prefix,
+ const isc::dns::LabelSequence& new_suffix);
//@}
RBNode<T>* NULLNODE;
@@ -1114,13 +1259,12 @@ RBTree<T>::RBTree(bool returnEmptyNode) :
template <typename T>
RBTree<T>::~RBTree() {
- deleteHelper(root_.get());
assert(node_count_ == 0);
}
template <typename T>
void
-RBTree<T>::deleteHelper(RBNode<T>* root) {
+RBTree<T>::deleteHelper(util::MemorySegment& mem_sgmt, RBNode<T>* root) {
if (root == NULLNODE) {
return;
}
@@ -1141,14 +1285,14 @@ RBTree<T>::deleteHelper(RBNode<T>* root) {
parent->right_ = NULLNODE;
}
- deleteHelper(node->getDown());
- delete node;
+ deleteHelper(mem_sgmt, node->getDown());
+ RBNode<T>::destroy(mem_sgmt, node);
--node_count_;
node = parent;
}
- deleteHelper(root->getDown());
- delete root;
+ deleteHelper(mem_sgmt, root->getDown());
+ RBNode<T>::destroy(mem_sgmt, root);
--node_count_;
}
@@ -1161,19 +1305,17 @@ RBTree<T>::find(const isc::dns::Name& target_name,
bool (*callback)(const RBNode<T>&, CBARG),
CBARG callback_arg) const
{
- using namespace helper;
-
if (!node_path.isEmpty()) {
isc_throw(isc::BadValue, "RBTree::find is given a non empty chain");
}
RBNode<T>* node = root_.get();
Result ret = NOTFOUND;
- isc::dns::Name name = target_name;
+ dns::LabelSequence target_labels(target_name);
while (node != NULLNODE) {
node_path.last_compared_ = node;
- node_path.last_comparison_ = name.compare(node->name_);
+ node_path.last_comparison_ = target_labels.compare(node->getLabels());
const isc::dns::NameComparisonResult::NameRelation relation =
node_path.last_comparison_.getRelation();
@@ -1184,22 +1326,13 @@ RBTree<T>::find(const isc::dns::Name& target_name,
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 {
- const int common_label_count =
- node_path.last_comparison_.getCommonLabels();
- // If the common label count is 1, there is no common label between
- // the two names, except the trailing "dot". In this case the two
- // sequences of labels have essentially no hierarchical
- // relationship in terms of matching, so we should continue the
- // binary search. One important exception is when the node
- // represents the root name ("."), in which case the comparison
- // result must indeed be considered subdomain matching. (We use
- // getLength() to check if the name is root, which is an equivalent
- // but cheaper way).
- if (common_label_count == 1 && node->name_.getLength() != 1) {
- node = (node_path.last_comparison_.getOrder() < 0) ?
- node->getLeft() : node->getRight();
- } else if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
+ if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
if (needsReturnEmptyNode_ || !node->isEmpty()) {
ret = PARTIALMATCH;
*target = node;
@@ -1211,7 +1344,8 @@ RBTree<T>::find(const isc::dns::Name& target_name,
}
}
node_path.push(node);
- name = name - node->name_;
+ target_labels.stripRight(
+ node_path.last_comparison_.getCommonLabels());
node = node->getDown();
} else {
break;
@@ -1283,6 +1417,7 @@ RBTree<T>::previousNode(RBTreeNodeChain<T>& node_path) const {
// 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.
@@ -1347,9 +1482,6 @@ RBTree<T>::previousNode(RBTreeNodeChain<T>& node_path) const {
// already, which located the exact node. The rest of the function
// goes one domain left and returns it for us.
break;
- default:
- // This must not happen as Name::compare() never returns NONE.
- isc_throw(isc::Unexpected, "Name::compare() returned unexpected result");
}
// So, the node_path now contains the path to a node we want previous for.
@@ -1405,17 +1537,19 @@ RBTree<T>::previousNode(RBTreeNodeChain<T>& node_path) const {
template <typename T>
typename RBTree<T>::Result
-RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
- using namespace helper;
+RBTree<T>::insert(util::MemorySegment& mem_sgmt,
+ const isc::dns::Name& target_name, RBNode<T>** new_node)
+{
RBNode<T>* parent = NULLNODE;
RBNode<T>* current = root_.get();
RBNode<T>* up_node = NULLNODE;
- isc::dns::Name name = target_name;
+ isc::dns::LabelSequence target_labels(target_name);
int order = -1;
while (current != NULLNODE) {
+ const dns::LabelSequence current_labels(current->getLabels());
const isc::dns::NameComparisonResult compare_result =
- name.compare(current->name_);
+ target_labels.compare(current_labels);
const isc::dns::NameComparisonResult::NameRelation relation =
compare_result.getRelation();
if (relation == isc::dns::NameComparisonResult::EQUAL) {
@@ -1423,90 +1557,98 @@ RBTree<T>::insert(const isc::dns::Name& target_name, RBNode<T>** new_node) {
*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 = NULLNODE;
+ up_node = current;
+ target_labels.stripRight(compare_result.getCommonLabels());
+ current = current->getDown();
} else {
- const int common_label_count = compare_result.getCommonLabels();
- // Note: see find() for the check of getLength().
- if (common_label_count == 1 && current->name_.getLength() != 1) {
- parent = current;
- order = compare_result.getOrder();
- current = order < 0 ? current->getLeft() : current->getRight();
- } else {
- // insert sub domain to sub tree
- if (relation == isc::dns::NameComparisonResult::SUBDOMAIN) {
- parent = NULLNODE;
- up_node = current;
- name = name - current->name_;
- 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.
- const isc::dns::Name common_ancestor = name.split(
- name.getLabelCount() - common_label_count,
- common_label_count);
- nodeFission(*current, common_ancestor);
- }
- }
+ // 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);
}
}
typename RBNode<T>::RBNodePtr* current_root = (up_node != NULLNODE) ?
&(up_node->down_) : &root_;
- // using auto_ptr here is avoid memory leak in case of exceptoin raised
- // after the RBNode creation, if we can make sure no exception will be
- // raised until the end of the function, we can remove it for optimization
- std::auto_ptr<RBNode<T> > node(new RBNode<T>(name));
+ // 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.
+ RBNode<T>* node = RBNode<T>::create(mem_sgmt, target_labels);
node->parent_ = parent;
if (parent == NULLNODE) {
- *current_root = node.get();
- //node is the new root of sub tree, so its init color
- // is BLACK
+ *current_root = node;
+ // node is the new root of sub tree, so its init color is BLACK
node->setColor(RBNode<T>::BLACK);
node->setSubTreeRoot(true);
} else if (order < 0) {
node->setSubTreeRoot(false);
- parent->left_ = node.get();
+ parent->left_ = node;
} else {
node->setSubTreeRoot(false);
- parent->right_ = node.get();
+ parent->right_ = node;
}
- insertRebalance(current_root, node.get());
+ insertRebalance(current_root, node);
if (new_node != NULL) {
- *new_node = node.get();
+ *new_node = node;
}
++node_count_;
- node.release();
return (SUCCESS);
}
+template <typename T>
+void
+RBTree<T>::deleteAllNodes(util::MemorySegment& mem_sgmt) {
+ deleteHelper(mem_sgmt, root_.get());
+ root_ = NULLNODE;
+}
// Note: when we redesign this (still keeping the basic concept), we should
// change this part so the newly created node will be used for the inserted
// name (and therefore the name for the existing node doesn't change).
// Otherwise, things like shortcut links between nodes won't work.
+// See Trac #2054.
template <typename T>
void
-RBTree<T>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
- using namespace helper;
- const isc::dns::Name sub_name = node.name_ - base_name;
- // using auto_ptr here is to avoid memory leak in case of exception raised
- // after the RBNode creation
- std::auto_ptr<RBNode<T> > down_node(new RBNode<T>(sub_name));
- node.name_ = base_name;
- // the rest of this function should be exception free so that it keeps
- // consistent behavior (i.e., a weak form of strong exception guarantee)
- // even if code after the call to this function throws an exception.
+RBTree<T>::nodeFission(util::MemorySegment& mem_sgmt, RBNode<T>& 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.
+ RBNode<T>* down_node = RBNode<T>::create(mem_sgmt, new_prefix);
+ node.resetLabels(new_suffix);
+
std::swap(node.data_, down_node->data_);
- std::swap(node.flags_, down_node->flags_);
- down_node->down_ = node.getDown();
+ // Swap flags bitfields; yes, this is ugly (it appears we cannot use
+ // std::swap for bitfields). The right solution is to implement
+ // the above note regarding #2054, then we won't have to swap the
+ // flags in the first place.
+ const uint32_t tmp = node.flags_;
+ node.flags_ = down_node->flags_;
+ down_node->flags_ = tmp;
- node.down_ = down_node.get();
+ down_node->down_ = node.getDown();
+ node.down_ = down_node;
- // Restore the color of the node (may have gotten changed by the flags swap)
+ // Restore the color of the node (may have gotten changed by the flags
+ // swap)
node.setColor(down_node->getColor());
// root node of sub tree, the initial color is BLACK
@@ -1516,7 +1658,6 @@ RBTree<T>::nodeFission(RBNode<T>& node, const isc::dns::Name& base_name) {
down_node->setSubTreeRoot(true);
++node_count_;
- down_node.release();
}
@@ -1660,8 +1801,9 @@ RBTree<T>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
}
indent(os, depth);
- os << node->name_.toText() << " ("
- << ((node->getColor() == RBNode<T>::BLACK) ? "black" : "red") << ")";
+ os << node->getLabels() << " ("
+ << ((node->getColor() == RBNode<T>::BLACK) ? "black" : "red")
+ << ")";
if (node->isEmpty()) {
os << " [invisible]";
}
@@ -1673,10 +1815,10 @@ RBTree<T>::dumpTreeHelper(std::ostream& os, const RBNode<T>* node,
const RBNode<T>* down = node->getDown();
if (down != NULLNODE) {
indent(os, depth + 1);
- os << "begin down from " << node->name_.toText() << "\n";
+ os << "begin down from " << node->getLabels() << "\n";
dumpTreeHelper(os, down, depth + 1);
indent(os, depth + 1);
- os << "end down from " << node->name_.toText() << "\n";
+ os << "end down from " << node->getLabels() << "\n";
}
dumpTreeHelper(os, node->getLeft(), depth + 1);
dumpTreeHelper(os, node->getRight(), depth + 1);
diff --git a/src/lib/datasrc/tests/Makefile.am b/src/lib/datasrc/tests/Makefile.am
index 0d3ce1a..5db12ea 100644
--- a/src/lib/datasrc/tests/Makefile.am
+++ b/src/lib/datasrc/tests/Makefile.am
@@ -60,6 +60,7 @@ run_unittests_SOURCES += sqlite3_unittest.cc
run_unittests_SOURCES += sqlite3_accessor_unittest.cc
run_unittests_SOURCES += memory_datasrc_unittest.cc
run_unittests_SOURCES += rbnode_rrset_unittest.cc
+run_unittests_SOURCES += zonetable_unittest.cc
run_unittests_SOURCES += zone_finder_context_unittest.cc
run_unittests_SOURCES += faked_nsec3.h faked_nsec3.cc
run_unittests_SOURCES += client_list_unittest.cc
diff --git a/src/lib/datasrc/tests/rbtree_unittest.cc b/src/lib/datasrc/tests/rbtree_unittest.cc
index 8fc5a17..cb55d81 100644
--- a/src/lib/datasrc/tests/rbtree_unittest.cc
+++ b/src/lib/datasrc/tests/rbtree_unittest.cc
@@ -16,6 +16,8 @@
#include <exceptions/exceptions.h>
+#include <util/memory_segment_local.h>
+
#include <dns/name.h>
#include <dns/rrclass.h>
#include <dns/rrset.h>
@@ -38,6 +40,8 @@ const size_t Name::MAX_LABELS;
/* The initial structure of rbtree
*
+* .
+ * |
* b
* / \
* a d.e.f
@@ -54,31 +58,61 @@ const size_t Name::MAX_LABELS;
*/
namespace {
+class TreeHolder {
+public:
+ TreeHolder(util::MemorySegment& mem_sgmt, RBTree<int>* tree) :
+ mem_sgmt_(mem_sgmt), tree_(tree)
+ {}
+ ~TreeHolder() {
+ RBTree<int>::destroy(mem_sgmt_, tree_);
+ }
+ RBTree<int>* get() { return (tree_); }
+private:
+ util::MemorySegment& mem_sgmt_;
+ RBTree<int>* tree_;
+};
+
class RBTreeTest : public::testing::Test {
protected:
- RBTreeTest() : rbtree_expose_empty_node(true), crbtnode(NULL) {
+ RBTreeTest() :
+ rbtree_holder_(mem_sgmt_, RBTree<int>::create(mem_sgmt_)),
+ rbtree_expose_empty_node_holder_(mem_sgmt_,
+ RBTree<int>::create(mem_sgmt_, true)),
+ rbtree(*rbtree_holder_.get()),
+ rbtree_expose_empty_node(*rbtree_expose_empty_node_holder_.get()),
+ crbtnode(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) {
- rbtree.insert(Name(domain_names[i]), &rbtnode);
+ rbtree.insert(mem_sgmt_, Name(domain_names[i]), &rbtnode);
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(i + 1)));
- rbtree_expose_empty_node.insert(Name(domain_names[i]), &rbtnode);
+ rbtree_expose_empty_node.insert(mem_sgmt_, Name(domain_names[i]),
+ &rbtnode);
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(i + 1)));
}
}
- RBTree<int> rbtree;
- RBTree<int> rbtree_expose_empty_node;
+ util::MemorySegmentLocal mem_sgmt_;
+ TreeHolder rbtree_holder_;
+ TreeHolder rbtree_expose_empty_node_holder_;
+ RBTree<int>& rbtree;
+ RBTree<int>& rbtree_expose_empty_node;
RBNode<int>* rbtnode;
const RBNode<int>* crbtnode;
};
-TEST_F(RBTreeTest, getNodeCount) {
- EXPECT_EQ(14, rbtree.getNodeCount());
+TEST_F(RBTreeTest, nodeCount) {
+ EXPECT_EQ(15, rbtree.getNodeCount());
+
+ // Delete all nodes, then the count should be set to 0. This also tests
+ // the behavior of deleteAllNodes().
+ rbtree.deleteAllNodes(mem_sgmt_);
+ EXPECT_EQ(0, rbtree.getNodeCount());
}
TEST_F(RBTreeTest, setGetData) {
@@ -87,64 +121,93 @@ TEST_F(RBTreeTest, setGetData) {
}
TEST_F(RBTreeTest, insertNames) {
- EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("d.e.f"),
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(mem_sgmt_,
+ Name("d.e.f"),
&rbtnode));
EXPECT_EQ(Name("d.e.f"), rbtnode->getName());
- EXPECT_EQ(14, rbtree.getNodeCount());
-
- //insert not exist node
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("."), &rbtnode));
- EXPECT_EQ(Name("."), rbtnode->getName());
EXPECT_EQ(15, rbtree.getNodeCount());
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("example.com"), &rbtnode));
+ // insert not exist node
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("0"),
+ &rbtnode));
+ EXPECT_EQ(Name("0"), rbtnode->getName());
EXPECT_EQ(16, rbtree.getNodeCount());
+
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_,
+ Name("example.com"),
+ &rbtnode));
+ EXPECT_EQ(17, rbtree.getNodeCount());
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(12)));
- // return ALREADYEXISTS, since node "example.com" already has been explicitly inserted
- EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("example.com"), &rbtnode));
- EXPECT_EQ(16, rbtree.getNodeCount());
+ // return ALREADYEXISTS, since node "example.com" already has
+ // been explicitly inserted
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(mem_sgmt_,
+ Name("example.com"),
+ &rbtnode));
+ EXPECT_EQ(17, rbtree.getNodeCount());
// split the node "d.e.f"
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("k.e.f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("k.e.f"),
+ &rbtnode));
EXPECT_EQ(Name("k"), rbtnode->getName());
- EXPECT_EQ(18, rbtree.getNodeCount());
+ EXPECT_EQ(19, rbtree.getNodeCount());
// split the node "g.h"
- EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("h"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(mem_sgmt_, Name("h"),
+ &rbtnode));
EXPECT_EQ(Name("h"), rbtnode->getName());
- EXPECT_EQ(19, rbtree.getNodeCount());
+ EXPECT_EQ(20, rbtree.getNodeCount());
// add child domain
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("m.p.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_,
+ Name("m.p.w.y.d.e.f"),
+ &rbtnode));
EXPECT_EQ(Name("m"), rbtnode->getName());
- EXPECT_EQ(20, rbtree.getNodeCount());
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("n.p.w.y.d.e.f"), &rbtnode));
- EXPECT_EQ(Name("n"), rbtnode->getName());
EXPECT_EQ(21, rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_,
+ Name("n.p.w.y.d.e.f"),
+ &rbtnode));
+ EXPECT_EQ(Name("n"), rbtnode->getName());
+ EXPECT_EQ(22, rbtree.getNodeCount());
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("l.a"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("l.a"),
+ &rbtnode));
EXPECT_EQ(Name("l"), rbtnode->getName());
- EXPECT_EQ(22, rbtree.getNodeCount());
+ EXPECT_EQ(23, rbtree.getNodeCount());
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("r.d.e.f"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("s.d.e.f"), &rbtnode));
- EXPECT_EQ(24, rbtree.getNodeCount());
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("r.d.e.f"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("s.d.e.f"),
+ &rbtnode));
+ EXPECT_EQ(25, rbtree.getNodeCount());
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("h.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_,
+ Name("h.w.y.d.e.f"),
+ &rbtnode));
// add more nodes one by one to cover leftRotate and rightRotate
- EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("f"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("m"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("nm"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("om"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("k"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("l"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("fe"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("ge"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("i"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("ae"), &rbtnode));
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("n"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(mem_sgmt_, Name("f"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("m"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("nm"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("om"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("k"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("l"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("fe"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("ge"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("i"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("ae"),
+ &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_, Name("n"),
+ &rbtnode));
}
TEST_F(RBTreeTest, findName) {
@@ -172,7 +235,8 @@ TEST_F(RBTreeTest, findName) {
rbtree_expose_empty_node.find(Name("m.d.e.f"), &crbtnode));
// find rbtnode
- EXPECT_EQ(RBTree<int>::EXACTMATCH, rbtree.find(Name("q.w.y.d.e.f"), &rbtnode));
+ EXPECT_EQ(RBTree<int>::EXACTMATCH, rbtree.find(Name("q.w.y.d.e.f"),
+ &rbtnode));
EXPECT_EQ(Name("q"), rbtnode->getName());
}
@@ -187,7 +251,8 @@ TEST_F(RBTreeTest, findError) {
}
TEST_F(RBTreeTest, flags) {
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("flags.example"),
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_,
+ Name("flags.example"),
&rbtnode));
// by default, flags are all off
@@ -218,7 +283,8 @@ testCallback(const RBNode<int>&, bool* callack_checker) {
TEST_F(RBTreeTest, callback) {
// by default callback isn't enabled
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("callback.example"),
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_,
+ Name("callback.example"),
&rbtnode));
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(1)));
EXPECT_FALSE(rbtnode->getFlag(RBNode<int>::FLAG_CALLBACK));
@@ -233,12 +299,14 @@ TEST_F(RBTreeTest, callback) {
rbtnode->setFlag(RBNode<int>::FLAG_CALLBACK);
// add more levels below and above the callback node for partial match.
RBNode<int>* subrbtnode;
- EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(Name("sub.callback.example"),
+ EXPECT_EQ(RBTree<int>::SUCCESS, rbtree.insert(mem_sgmt_,
+ Name("sub.callback.example"),
&subrbtnode));
subrbtnode->setData(RBNode<int>::NodeDataPtr(new int(2)));
RBNode<int>* parentrbtnode;
- EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(Name("example"),
- &parentrbtnode));
+ EXPECT_EQ(RBTree<int>::ALREADYEXISTS, rbtree.insert(mem_sgmt_,
+ Name("example"),
+ &parentrbtnode));
// the chilld/parent nodes shouldn't "inherit" the callback flag.
// "rbtnode" may be invalid due to the insertion, so we need to re-find
// it.
@@ -275,9 +343,11 @@ TEST_F(RBTreeTest, chainLevel) {
// insert one node to the tree and find it. there should be exactly
// one level in the chain.
- RBTree<int> tree(true);
+ TreeHolder tree_holder(mem_sgmt_, RBTree<int>::create(mem_sgmt_, true));
+ RBTree<int>& tree(*tree_holder.get());
Name node_name(Name::ROOT_NAME());
- EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(mem_sgmt_, node_name,
+ &rbtnode));
EXPECT_EQ(RBTree<int>::EXACTMATCH,
tree.find(node_name, &crbtnode, chain));
EXPECT_EQ(1, chain.getLevelCount());
@@ -299,7 +369,8 @@ TEST_F(RBTreeTest, chainLevel) {
*/
for (unsigned int i = 2; i <= Name::MAX_LABELS; ++i) {
node_name = Name("a.").concatenate(node_name);
- EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(node_name, &rbtnode));
+ EXPECT_EQ(RBTree<int>::SUCCESS, tree.insert(mem_sgmt_, node_name,
+ &rbtnode));
RBTreeNodeChain<int> found_chain;
EXPECT_EQ(RBTree<int>::EXACTMATCH,
tree.find(node_name, &crbtnode, found_chain));
@@ -321,8 +392,10 @@ TEST_F(RBTreeTest, getAbsoluteNameError) {
/*
*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
+ * ., 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
@@ -400,6 +473,11 @@ previousWalk(RBTree<int>& rbtree, const RBNode<int>* node,
}
// 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 = rbtree.previousNode(node_path);
EXPECT_EQ(static_cast<void*>(NULL), node);
// Calling previousNode() yet again should still return NULL without
@@ -441,18 +519,23 @@ TEST_F(RBTreeTest, previousNode) {
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 = rbtree.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 nor
+ // If we start before the lowest (. < 0. < a.), we should not get a
+ // node. Its previous node should be the root.
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 = rbtree.previousNode(node_path);
+ ASSERT_NE(static_cast<void*>(NULL), node);
+ EXPECT_EQ(".", node->getLabels().toText());
node = NULL;
node_path.clear();
}
@@ -542,7 +625,8 @@ TEST_F(RBTreeTest, previousNode) {
{
SCOPED_TRACE("Lookup in empty tree");
// Just check it doesn't crash, etc.
- RBTree<int> empty_tree;
+ TreeHolder tree_holder(mem_sgmt_, RBTree<int>::create(mem_sgmt_));
+ RBTree<int>& empty_tree(*tree_holder.get());
EXPECT_EQ(RBTree<int>::NOTFOUND,
empty_tree.find(Name("x"), &node, node_path));
EXPECT_EQ(static_cast<void*>(NULL), node);
@@ -586,7 +670,8 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(static_cast<void*>(NULL), chain.getLastComparedNode());
// A search for an empty tree should result in no 'last compared', too.
- RBTree<int> empty_tree;
+ TreeHolder tree_holder(mem_sgmt_, RBTree<int>::create(mem_sgmt_));
+ RBTree<int>& empty_tree(*tree_holder.get());
EXPECT_EQ(RBTree<int>::NOTFOUND,
empty_tree.find(Name("a"), &crbtnode, chain));
EXPECT_EQ(static_cast<void*>(NULL), chain.getLastComparedNode());
@@ -598,8 +683,8 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::EXACTMATCH,
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);
+ // 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
@@ -609,8 +694,8 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
tree.find(Name("x.k.g.h"), &crbtnode, chain));
EXPECT_EQ(expected_node, chain.getLastComparedNode());
- // k.g.h < x.k.g.h, 2 = # labels of "k."
- comparisonChecks(chain, 1, 2, NameComparisonResult::SUBDOMAIN);
+ // 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
@@ -620,8 +705,8 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
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);
+ // a < x, no common labels
+ comparisonChecks(chain, -1, 0, NameComparisonResult::NONE);
chain.clear();
// Partial match, search stopped in the subtree below the matching node
@@ -631,8 +716,8 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
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);
+ // 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
@@ -642,8 +727,8 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
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);
+ // 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
@@ -652,26 +737,27 @@ TEST_F(RBTreeTest, getLastComparedNode) {
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
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);
+ // z.y > w.y, 1 = # labels of "y"
+ comparisonChecks(chain, 1, 1, NameComparisonResult::COMMONANCESTOR);
chain.clear();
- // Search stops in the highest level after following a left branch.
+ // Search stops in the highest level (under ".") after following a left
+ // branch. (find() still returns PARTIALMATCH due to the top level ".")
EXPECT_EQ(RBTree<int>::EXACTMATCH, tree.find(Name("c"), &expected_node));
- EXPECT_EQ(RBTree<int>::NOTFOUND,
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
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);
+ // bb < c, no common label
+ comparisonChecks(chain, -1, 0, NameComparisonResult::NONE);
chain.clear();
- // 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,
+ // Search stops in the highest level (under ".") after following a right
+ // branch. (the expected node is the same as the previous case)
+ EXPECT_EQ(RBTree<int>::PARTIALMATCH,
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);
+ // d > c, no common label
+ comparisonChecks(chain, 1, 0, NameComparisonResult::NONE);
chain.clear();
}
@@ -679,48 +765,53 @@ TEST_F(RBTreeTest, dumpTree) {
std::ostringstream str;
std::ostringstream str2;
rbtree.dumpTree(str);
- str2 << "tree has 14 node(s)\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"
+ 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"
- " q. (red)\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 w.y.\n"
- " x. (red)\n"
+ " end down from d.e.f\n"
+ " c (red)\n"
" NULL\n"
" NULL\n"
- " z. (red)\n"
- " begin down from z.\n"
- " j. (black) [subtreeroot]\n"
+ " g.h (red)\n"
+ " begin down from g.h\n"
+ " i (black) [subtreeroot]\n"
" NULL\n"
- " NULL\n"
- " end down from z.\n"
- " NULL\n"
+ " k (red)\n"
+ " NULL\n"
+ " NULL\n"
+ " end down from g.h\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());
}
@@ -731,9 +822,10 @@ TEST_F(RBTreeTest, swap) {
size_t count1(rbtree.getNodeCount());
// Create second one and store state
- RBTree<int> tree2;
+ TreeHolder tree_holder(mem_sgmt_, RBTree<int>::create(mem_sgmt_));
+ RBTree<int>& tree2(*tree_holder.get());
RBNode<int>* node;
- tree2.insert(Name("second"), &node);
+ tree2.insert(mem_sgmt_, Name("second"), &node);
std::ostringstream str2;
tree2.dumpTree(str2);
@@ -757,8 +849,9 @@ TEST_F(RBTreeTest, swap) {
// any domain names should be considered a subdomain of it), so it makes
// sense to test cases with the root zone explicitly.
TEST_F(RBTreeTest, root) {
- RBTree<int> root;
- root.insert(Name::ROOT_NAME(), &rbtnode);
+ TreeHolder tree_holder(mem_sgmt_, RBTree<int>::create(mem_sgmt_));
+ RBTree<int>& root(*tree_holder.get());
+ root.insert(mem_sgmt_, Name::ROOT_NAME(), &rbtnode);
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(1)));
EXPECT_EQ(RBTree<int>::EXACTMATCH,
@@ -770,7 +863,7 @@ TEST_F(RBTreeTest, root) {
// Insert a new name that better matches the query name. find() should
// find the better one.
- root.insert(Name("com"), &rbtnode);
+ root.insert(mem_sgmt_, Name("com"), &rbtnode);
rbtnode->setData(RBNode<int>::NodeDataPtr(new int(2)));
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
root.find(Name("example.com"), &crbtnode));
@@ -778,8 +871,10 @@ TEST_F(RBTreeTest, root) {
// Perform the same tests for the tree that allows matching against empty
// nodes.
- RBTree<int> root_emptyok(true);
- root_emptyok.insert(Name::ROOT_NAME(), &rbtnode);
+ TreeHolder tree_holder_emptyok(mem_sgmt_,
+ RBTree<int>::create(mem_sgmt_, true));
+ RBTree<int>& root_emptyok(*tree_holder_emptyok.get());
+ root_emptyok.insert(mem_sgmt_, Name::ROOT_NAME(), &rbtnode);
EXPECT_EQ(RBTree<int>::EXACTMATCH,
root_emptyok.find(Name::ROOT_NAME(), &crbtnode));
EXPECT_EQ(rbtnode, crbtnode);
@@ -787,7 +882,7 @@ TEST_F(RBTreeTest, root) {
root_emptyok.find(Name("example.com"), &crbtnode));
EXPECT_EQ(rbtnode, crbtnode);
- root.insert(Name("com"), &rbtnode);
+ root.insert(mem_sgmt_, Name("com"), &rbtnode);
EXPECT_EQ(RBTree<int>::PARTIALMATCH,
root.find(Name("example.com"), &crbtnode));
EXPECT_EQ(rbtnode, crbtnode);
diff --git a/src/lib/datasrc/tests/zonetable_unittest.cc b/src/lib/datasrc/tests/zonetable_unittest.cc
index fa74c0e..5a29a44 100644
--- a/src/lib/datasrc/tests/zonetable_unittest.cc
+++ b/src/lib/datasrc/tests/zonetable_unittest.cc
@@ -14,6 +14,8 @@
#include <exceptions/exceptions.h>
+#include <util/memory_segment_local.h>
+
#include <dns/name.h>
#include <dns/rrclass.h>
@@ -40,7 +42,7 @@ TEST(ZoneTest, init) {
TEST(ZoneTest, find) {
InMemoryZoneFinder zone(RRClass::IN(), Name("example.com"));
EXPECT_EQ(ZoneFinder::NXDOMAIN,
- zone.find(Name("www.example.com"), RRType::A()).code);
+ zone.find(Name("www.example.com"), RRType::A())->code);
}
class ZoneTableTest : public ::testing::Test {
@@ -50,68 +52,77 @@ protected:
zone2(new InMemoryZoneFinder(RRClass::IN(),
Name("example.net"))),
zone3(new InMemoryZoneFinder(RRClass::IN(),
- Name("example")))
+ Name("example"))),
+ zone_table(ZoneTable::create(mem_sgmt_))
{}
- ZoneTable zone_table;
+
+ ~ZoneTableTest() {
+ ZoneTable::destroy(mem_sgmt_, zone_table);
+ }
ZoneFinderPtr zone1, zone2, zone3;
+ isc::util::MemorySegmentLocal mem_sgmt_;
+ ZoneTable* zone_table;
};
TEST_F(ZoneTableTest, addZone) {
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone1));
- EXPECT_EQ(result::EXIST, zone_table.addZone(zone1));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone1));
+ EXPECT_EQ(result::EXIST, zone_table->addZone(mem_sgmt_, zone1));
// names are compared in a case insensitive manner.
- EXPECT_EQ(result::EXIST, zone_table.addZone(
+ EXPECT_EQ(result::EXIST, zone_table->addZone(
+ mem_sgmt_,
ZoneFinderPtr(new InMemoryZoneFinder(RRClass::IN(),
Name("EXAMPLE.COM")))));
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone2));
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone3));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone2));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone3));
// Zone table is indexed only by name. Duplicate origin name with
// different zone class isn't allowed.
- EXPECT_EQ(result::EXIST, zone_table.addZone(
+ EXPECT_EQ(result::EXIST, zone_table->addZone(
+ mem_sgmt_,
ZoneFinderPtr(new InMemoryZoneFinder(RRClass::CH(),
Name("example.com")))));
/// Bogus zone (NULL)
- EXPECT_THROW(zone_table.addZone(ZoneFinderPtr()), isc::InvalidParameter);
+ EXPECT_THROW(zone_table->addZone(mem_sgmt_, ZoneFinderPtr()),
+ isc::InvalidParameter);
}
TEST_F(ZoneTableTest, DISABLED_removeZone) {
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone1));
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone2));
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone3));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone1));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone2));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone3));
- EXPECT_EQ(result::SUCCESS, zone_table.removeZone(Name("example.net")));
- EXPECT_EQ(result::NOTFOUND, zone_table.removeZone(Name("example.net")));
+ EXPECT_EQ(result::SUCCESS, zone_table->removeZone(Name("example.net")));
+ EXPECT_EQ(result::NOTFOUND, zone_table->removeZone(Name("example.net")));
}
TEST_F(ZoneTableTest, findZone) {
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone1));
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone2));
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone3));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone1));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone2));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone3));
- EXPECT_EQ(result::SUCCESS, zone_table.findZone(Name("example.com")).code);
+ EXPECT_EQ(result::SUCCESS, zone_table->findZone(Name("example.com")).code);
EXPECT_EQ(Name("example.com"),
- zone_table.findZone(Name("example.com")).zone->getOrigin());
+ zone_table->findZone(Name("example.com")).zone->getOrigin());
EXPECT_EQ(result::NOTFOUND,
- zone_table.findZone(Name("example.org")).code);
+ zone_table->findZone(Name("example.org")).code);
EXPECT_EQ(ConstZoneFinderPtr(),
- zone_table.findZone(Name("example.org")).zone);
+ zone_table->findZone(Name("example.org")).zone);
// there's no exact match. the result should be the longest match,
// and the code should be PARTIALMATCH.
EXPECT_EQ(result::PARTIALMATCH,
- zone_table.findZone(Name("www.example.com")).code);
+ zone_table->findZone(Name("www.example.com")).code);
EXPECT_EQ(Name("example.com"),
- zone_table.findZone(Name("www.example.com")).zone->getOrigin());
+ zone_table->findZone(Name("www.example.com")).zone->getOrigin());
// make sure the partial match is indeed the longest match by adding
// a zone with a shorter origin and query again.
ZoneFinderPtr zone_com(new InMemoryZoneFinder(RRClass::IN(), Name("com")));
- EXPECT_EQ(result::SUCCESS, zone_table.addZone(zone_com));
+ EXPECT_EQ(result::SUCCESS, zone_table->addZone(mem_sgmt_, zone_com));
EXPECT_EQ(Name("example.com"),
- zone_table.findZone(Name("www.example.com")).zone->getOrigin());
+ zone_table->findZone(Name("www.example.com")).zone->getOrigin());
}
}
diff --git a/src/lib/datasrc/zonetable.cc b/src/lib/datasrc/zonetable.cc
index 644861c..1193181 100644
--- a/src/lib/datasrc/zonetable.cc
+++ b/src/lib/datasrc/zonetable.cc
@@ -12,13 +12,15 @@
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.
-#include <cassert>
+#include <util/memory_segment.h>
#include <dns/name.h>
#include <datasrc/zonetable.h>
#include <datasrc/rbtree.h>
+#include <cassert>
+
using namespace std;
using namespace isc::dns;
@@ -30,8 +32,14 @@ struct ZoneTable::ZoneTableImpl {
// Type aliases to make it shorter
typedef RBTree<ZoneFinder> ZoneTree;
typedef RBNode<ZoneFinder> ZoneNode;
+
// The actual storage
- ZoneTree zones_;
+ ZoneTree* zones_;
+
+ // Constructor
+ ZoneTableImpl(util::MemorySegment& mem_sgmt) :
+ zones_(ZoneTree::create(mem_sgmt))
+ {}
/*
* The implementation methods are here and just wrap-called in the
@@ -40,7 +48,7 @@ struct ZoneTable::ZoneTableImpl {
*/
// Implementation of ZoneTable::addZone
- result::Result addZone(ZoneFinderPtr zone) {
+ result::Result addZone(util::MemorySegment& mem_sgmt, ZoneFinderPtr zone) {
// Sanity check
if (!zone) {
isc_throw(InvalidParameter,
@@ -49,7 +57,7 @@ struct ZoneTable::ZoneTableImpl {
// Get the node where we put the zone
ZoneNode* node(NULL);
- switch (zones_.insert(zone->getOrigin(), &node)) {
+ switch (zones_->insert(mem_sgmt, zone->getOrigin(), &node)) {
// This is OK
case ZoneTree::SUCCESS:
case ZoneTree::ALREADYEXISTS:
@@ -76,7 +84,7 @@ struct ZoneTable::ZoneTableImpl {
result::Result my_result;
// Translate the return codes
- switch (zones_.find(name, &node)) {
+ switch (zones_->find(name, &node)) {
case ZoneTree::EXACTMATCH:
my_result = result::SUCCESS;
break;
@@ -100,16 +108,39 @@ struct ZoneTable::ZoneTableImpl {
}
};
-ZoneTable::ZoneTable() : impl_(new ZoneTableImpl)
+ZoneTable::ZoneTable(util::MemorySegment& mem_sgmt) :
+ impl_(new ZoneTableImpl(mem_sgmt))
{}
ZoneTable::~ZoneTable() {
delete impl_;
}
+ZoneTable*
+ZoneTable::create(util::MemorySegment& mem_sgmt) {
+ // The ZoneTable constructor can throw, so we need to prevent memory leak.
+ // This is ugly, but for now this seems to be the only place we need
+ // this, and since we'll substantially revise this code soon, so we don't
+ // work around it by this hack at the moment.
+ void* p = mem_sgmt.allocate(sizeof(ZoneTable));
+ try {
+ return (new(p) ZoneTable(mem_sgmt));
+ } catch (...) {
+ mem_sgmt.deallocate(p, sizeof(ZoneTable));
+ throw;
+ }
+}
+
+void
+ZoneTable::destroy(util::MemorySegment& mem_sgmt, ZoneTable* ztable) {
+ ZoneTableImpl::ZoneTree::destroy(mem_sgmt, ztable->impl_->zones_);
+ ztable->~ZoneTable();
+ mem_sgmt.deallocate(ztable, sizeof(ZoneTable));
+}
+
result::Result
-ZoneTable::addZone(ZoneFinderPtr zone) {
- return (impl_->addZone(zone));
+ZoneTable::addZone(util::MemorySegment& mem_sgmt, ZoneFinderPtr zone) {
+ return (impl_->addZone(mem_sgmt, zone));
}
result::Result
diff --git a/src/lib/datasrc/zonetable.h b/src/lib/datasrc/zonetable.h
index 5a34480..93a021c 100644
--- a/src/lib/datasrc/zonetable.h
+++ b/src/lib/datasrc/zonetable.h
@@ -15,12 +15,14 @@
#ifndef __ZONETABLE_H
#define __ZONETABLE_H 1
-#include <boost/shared_ptr.hpp>
+#include <util/memory_segment.h>
#include <dns/rrset.h>
#include <datasrc/zone.h>
+#include <boost/shared_ptr.hpp>
+
namespace isc {
namespace dns {
class Name;
@@ -58,18 +60,47 @@ private:
ZoneTable(const ZoneTable& source);
ZoneTable& operator=(const ZoneTable& source);
-public:
- /// Default constructor.
+ /// Constructor.
+ ///
+ /// An object of this class is always expected to be created by the
+ /// allocator (\c create()), so the constructor is hidden as private.
///
/// This constructor internally involves resource allocation, and if
/// it fails, a corresponding standard exception will be thrown.
/// It never throws an exception otherwise.
- ZoneTable();
+ ZoneTable(util::MemorySegment& mem_sgmt);
/// The destructor.
+ ///
+ /// An object of this class is always expected to be destroyed explicitly
+ /// by \c destroy(), so the constructor is hidden as private.
~ZoneTable();
//@}
+public:
+ /// \brief Allocate and construct \c ZoneTable
+ ///
+ /// This static method allocates memory for a new \c ZoneTable 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 ZoneTable is allocated.
+ static ZoneTable* create(util::MemorySegment& mem_sgmt);
+
+ /// \brief Destruct and deallocate \c ZoneTable
+ ///
+ /// \throw none
+ ///
+ /// \param mem_sgmt The \c MemorySegment that allocated memory for
+ /// \c ztable.
+ /// \param ztable A non NULL pointer to a valid \c ZoneTable 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, ZoneTable* ztable);
+
/// Add a \c Zone to the \c ZoneTable.
///
/// \c Zone must not be associated with a NULL pointer; otherwise
@@ -83,7 +114,7 @@ public:
/// added to the zone table.
/// \return \c result::EXIST The zone table already contains
/// zone of the same origin.
- result::Result addZone(ZoneFinderPtr zone);
+ result::Result addZone(util::MemorySegment& mem_sgmt, ZoneFinderPtr zone);
/// Remove a \c Zone of the given origin name from the \c ZoneTable.
///
diff --git a/src/lib/dns/labelsequence.cc b/src/lib/dns/labelsequence.cc
index 7627571..5675e5a 100644
--- a/src/lib/dns/labelsequence.cc
+++ b/src/lib/dns/labelsequence.cc
@@ -23,62 +23,75 @@
namespace isc {
namespace dns {
-LabelSequence::LabelSequence(const uint8_t* data,
- const uint8_t* offsets,
- size_t offsets_size) : data_(data),
- offsets_(offsets),
- offsets_size_(offsets_size),
- first_label_(0),
- last_label_(offsets_size_)
-{
- if (data == NULL || offsets == NULL) {
- isc_throw(BadValue, "Null pointer passed to LabelSequence constructor");
- }
- if (offsets_size == 0) {
- isc_throw(BadValue, "Zero offsets to LabelSequence constructor");
+LabelSequence::LabelSequence(const void* buf) {
+ if (buf == NULL) {
+ isc_throw(BadValue,
+ "Null pointer passed to LabelSequence constructor");
}
- if (offsets_size > Name::MAX_LABELS) {
- isc_throw(BadValue, "MAX_LABELS exceeded");
+
+ const uint8_t* bp = reinterpret_cast<const uint8_t*>(buf);
+
+ first_label_ = 0;
+ const uint8_t offsets_len = *bp++;
+ if (offsets_len == 0 || offsets_len > Name::MAX_LABELS) {
+ isc_throw(BadValue,
+ "Bad offsets len in serialized LabelSequence data: "
+ << static_cast<unsigned int>(offsets_len));
}
- for (size_t cur_offset = 0; cur_offset < offsets_size; ++cur_offset) {
- if (offsets[cur_offset] > Name::MAX_LABELLEN) {
- isc_throw(BadValue, "MAX_LABEL_LEN exceeded");
- }
- if (cur_offset > 0 && offsets[cur_offset] <= offsets[cur_offset - 1]) {
- isc_throw(BadValue, "Offset smaller than previous offset");
+ last_label_ = offsets_len - 1;
+ offsets_ = bp;
+ data_ = bp + offsets_len;
+
+ // Check the integrity on the offsets and the name data
+ const uint8_t* dp = data_;
+ for (size_t cur_offset = 0; cur_offset < offsets_len; ++cur_offset) {
+ if (offsets_[cur_offset] > Name::MAX_LABELLEN ||
+ dp - data_ != offsets_[cur_offset]) {
+ isc_throw(BadValue,
+ "Broken offset or name data in serialized "
+ "LabelSequence data");
}
+ dp += (1 + *dp);
}
}
-
const uint8_t*
LabelSequence::getData(size_t *len) const {
*len = getDataLength();
return (&data_[offsets_[first_label_]]);
}
-void
-LabelSequence::getOffsetData(size_t* len,
- uint8_t placeholder[Name::MAX_LABELS]) const {
- *len = last_label_ - first_label_;
- for (size_t i = 0; i < *len; i++) {
- placeholder[i] = offsets_[first_label_ + i] - offsets_[first_label_];
- }
+size_t
+LabelSequence::getDataLength() const {
+ const size_t last_label_len = data_[offsets_[last_label_]] + 1;
+ return (offsets_[last_label_] - offsets_[first_label_] + last_label_len);
}
size_t
-LabelSequence::getDataLength() const {
- // If the labelsequence is absolute, the current last_label_ falls
- // out of the vector (since it points to the 'label' after the
- // root label, which doesn't exist; in that case, return
- // the length for the 'previous' label (the root label) plus
- // one (for the root label zero octet)
- if (isAbsolute()) {
- return (offsets_[last_label_ - 1] -
- offsets_[first_label_] + 1);
- } else {
- return (offsets_[last_label_] - offsets_[first_label_]);
+LabelSequence::getSerializedLength() const {
+ return (1 + getLabelCount() + getDataLength());
+}
+
+void
+LabelSequence::serialize(void* buf, size_t buf_len) const {
+ const size_t expected_size = getSerializedLength();
+ if (expected_size > buf_len) {
+ isc_throw(BadValue, "buffer too short for LabelSequence::serialize");
+ }
+
+ const size_t offsets_len = getLabelCount();
+ assert(offsets_len < 256); // should be in the 8-bit range
+
+ uint8_t* bp = reinterpret_cast<uint8_t*>(buf);
+ *bp++ = offsets_len;
+ for (size_t i = 0; i < offsets_len; ++i) {
+ *bp++ = offsets_[first_label_ + i] - offsets_[first_label_];
}
+ const size_t ndata_len = getDataLength();
+ memcpy(bp, &data_[offsets_[first_label_]], ndata_len);
+ bp += ndata_len;
+
+ assert(bp - reinterpret_cast<const uint8_t*>(buf) == expected_size);
}
bool
@@ -110,19 +123,16 @@ LabelSequence::equals(const LabelSequence& other, bool case_sensitive) const {
NameComparisonResult
LabelSequence::compare(const LabelSequence& other,
- bool case_sensitive) const {
- if (isAbsolute() ^ other.isAbsolute()) {
- return (NameComparisonResult(0, 0, NameComparisonResult::NONE));
- }
-
+ bool case_sensitive) const
+{
// Determine the relative ordering under the DNSSEC order relation of
// 'this' and 'other', and also determine the hierarchical relationship
- // of the names.
+ // of the labels.
unsigned int nlabels = 0;
- int l1 = last_label_ - first_label_;
- int l2 = other.last_label_ - other.first_label_;
- int ldiff = (int)l1 - (int)l2;
+ int l1 = getLabelCount();
+ int l2 = other.getLabelCount();
+ const int ldiff = static_cast<int>(l1) - static_cast<int>(l2);
unsigned int l = (ldiff < 0) ? l1 : l2;
while (l > 0) {
@@ -138,47 +148,38 @@ LabelSequence::compare(const LabelSequence& other,
// bitstring labels.
assert(count1 <= Name::MAX_LABELLEN && count2 <= Name::MAX_LABELLEN);
- int cdiff = (int)count1 - (int)count2;
+ const int cdiff = static_cast<int>(count1) - static_cast<int>(count2);
unsigned int count = (cdiff < 0) ? count1 : count2;
while (count > 0) {
- uint8_t label1 = data_[pos1];
- uint8_t label2 = other.data_[pos2];
+ const uint8_t label1 = data_[pos1];
+ const uint8_t label2 = other.data_[pos2];
int chdiff;
if (case_sensitive) {
- chdiff = (int)label1 - (int)label2;
+ chdiff = static_cast<int>(label1) - static_cast<int>(label2);
} else {
- chdiff = (int)isc::dns::name::internal::maptolower[label1] -
- (int)isc::dns::name::internal::maptolower[label2];
+ chdiff = static_cast<int>(
+ isc::dns::name::internal::maptolower[label1]) -
+ static_cast<int>(
+ isc::dns::name::internal::maptolower[label2]);
}
if (chdiff != 0) {
- if ((nlabels == 0) &&
- (!isAbsolute() ||
- ((last_label_ < getLabelCount()) ||
- (other.last_label_ < other.getLabelCount())))) {
- return (NameComparisonResult(0, 0,
- NameComparisonResult::NONE));
- } else {
- return (NameComparisonResult(chdiff, nlabels,
- NameComparisonResult::COMMONANCESTOR));
- }
+ return (NameComparisonResult(
+ chdiff, nlabels,
+ nlabels == 0 ? NameComparisonResult::NONE :
+ NameComparisonResult::COMMONANCESTOR));
}
--count;
++pos1;
++pos2;
}
if (cdiff != 0) {
- if ((nlabels == 0) &&
- ((last_label_ < getLabelCount()) ||
- (other.last_label_ < other.getLabelCount()))) {
- return (NameComparisonResult(0, 0,
- NameComparisonResult::NONE));
- } else {
- return (NameComparisonResult(cdiff, nlabels,
- NameComparisonResult::COMMONANCESTOR));
- }
+ return (NameComparisonResult(
+ cdiff, nlabels,
+ nlabels == 0 ? NameComparisonResult::NONE :
+ NameComparisonResult::COMMONANCESTOR));
}
++nlabels;
}
@@ -214,7 +215,7 @@ LabelSequence::stripRight(size_t i) {
bool
LabelSequence::isAbsolute() const {
- return (last_label_ == offsets_size_);
+ return (data_[offsets_[last_label_]] == 0);
}
size_t
@@ -241,7 +242,7 @@ LabelSequence::toText(bool omit_final_dot) const {
const uint8_t* np_end = np + getDataLength();
// use for integrity check
- unsigned int labels = last_label_ - first_label_;
+ unsigned int labels = getLabelCount();
// init with an impossible value to catch error cases in the end:
unsigned int count = Name::MAX_LABELLEN + 1;
diff --git a/src/lib/dns/labelsequence.h b/src/lib/dns/labelsequence.h
index d6f02c9..cd1a7c9 100644
--- a/src/lib/dns/labelsequence.h
+++ b/src/lib/dns/labelsequence.h
@@ -21,7 +21,7 @@
namespace isc {
namespace dns {
-/// \brief Light-weight Accessor to data of Name object
+/// \brief Light-weight Accessor to Name data.
///
/// The purpose of this class is to easily match Names and parts of Names,
/// without needing to copy the underlying data on each label strip.
@@ -40,7 +40,6 @@ namespace dns {
/// LabelSequences can be compared to other LabelSequences, and their
/// data can be requested (which then points to part of the original
/// data of the original Name object).
-///
class LabelSequence {
// Name calls the private toText(bool) method of LabelSequence.
friend std::string Name::toText(bool) const;
@@ -55,48 +54,29 @@ public:
///
/// \param name The Name to construct a LabelSequence for
explicit LabelSequence(const Name& name):
- data_(&name.ndata_[0]),
- offsets_(&name.offsets_[0]),
- offsets_size_(name.offsets_.size()),
- first_label_(0),
- last_label_(name.getLabelCount())
+ data_(&name.ndata_[0]),
+ offsets_(&name.offsets_[0]),
+ first_label_(0),
+ last_label_(name.getLabelCount() - 1)
{}
- /// \brief Constructs a LabelSequence for the given data
+ /// \brief Constructor from serialized image.
///
- /// \note The associated data MUST remain in scope during the lifetime
- /// of this LabelSequence, since only the pointers are copied.
+ /// This constructor restores a \c LabelSequence object from a serialized
+ /// binary image previously generated by \c serialize(). Any other input
+ /// to this constructor will result in undefined behavior.
///
- /// \note No validation is done on the given data upon construction;
- /// use with care.
+ /// The binary data passed to this constructor MUST remain in scope and
+ /// MUST NOT be modified during the lifetime of this LabelSequence.
///
- /// \exception isc::BadValue if basic checks for the input data, or
- /// offsets fails.
+ /// As long as the data were previously generated by a call to
+ /// \c serialize() on a valid \c LabelSequence object, this constructor
+ /// should succeed. While any other case is undefined, this constructor
+ /// may perform some validity checks internally for safety. Nevertheless,
+ /// applications must not rely on such checks.
///
- /// \param data The raw data for the domain name, in wire format
- /// \param offsets The offsets of the labels in the domain name data,
- /// as given by a Name object or another LabelSequence
- /// \param offsets_size The size of the offsets data
- LabelSequence(const uint8_t* data,
- const uint8_t* offsets,
- size_t offsets_size);
-
- /// \brief Copy constructor.
- ///
- /// \note The associated data MUST remain in scope during the lifetime
- /// of this LabelSequence, since only the pointers are copied.
- ///
- /// \note No validation is done on the given data upon construction;
- /// use with care.
- ///
- /// \param ls The LabelSequence to construct a LabelSequence from
- LabelSequence(const LabelSequence& ls):
- data_(ls.data_),
- offsets_(ls.offsets_),
- offsets_size_(ls.offsets_size_),
- first_label_(ls.first_label_),
- last_label_(ls.last_label_)
- {}
+ /// \param buf Pointer to the serialized image generated by \c serialize().
+ explicit LabelSequence(const void* buf);
/// \brief Return the wire-format data for this LabelSequence
///
@@ -113,16 +93,6 @@ public:
/// \return Pointer to the wire-format data of this label sequence
const uint8_t* getData(size_t* len) const;
- /// \brief Return the offset data for this LabelSequence
- ///
- /// The offsets are returned in the <code>placeholder</code> array.
- ///
- /// \param len Pointer to a size_t where the number of offsets
- /// will be stored
- /// \param placeholder Array where the offset data will be returned
- void getOffsetData(size_t* len,
- uint8_t placeholder[Name::MAX_LABELS]) const;
-
/// \brief Return the length of the wire-format data of this LabelSequence
///
/// This method returns the number of octets for the data that would
@@ -139,6 +109,52 @@ public:
/// \return The length of the data of the label sequence in octets.
size_t getDataLength() const;
+ /// \brief Max possible size of serialized image generated by \c serialize
+ ///
+ /// A fixed length buffer of this size can be always passed to
+ /// \c serialize() safely. (But the application shouldn't use the
+ /// specific size value; it must use this constant variable).
+ static const size_t MAX_SERIALIZED_LENGTH =
+ Name::MAX_WIRE + Name::MAX_LABELS + 1;
+
+ /// \brief Return the size of serialized image of the \c LabelSequence.
+ ///
+ /// This method calculates the size of necessary storage to store
+ /// serialized image of this \c LabelSequence (which would be dumped by
+ /// \c serialize()) and returns it. The size is in bytes.
+ ///
+ /// \throw none.
+ ///
+ /// \return The size of serialized image of the \c LabelSequence.
+ size_t getSerializedLength() const;
+
+ /// \brief Serialize the \c LabelSequence object in to a buffer.
+ ///
+ /// This method dumps a serialized image of this \c LabelSequence
+ /// that would be restored by the corresponding constructor into the
+ /// given buffer. The buffer size must be at least equal to
+ /// the value returned by getSerializedLength() (it can be larger than
+ /// that).
+ ///
+ /// The serialized image would be as follows:
+ /// - olen: number of offsets (1 byte)
+ /// - binary sequence of offsets (olen bytes, verbatim copy of offsets_
+ /// of this size)
+ /// - binary sequence of name data (length determined by itself, verbatim
+ /// copy of data_ of the corresponding size)
+ ///
+ /// Applications must use the resulting image opaque value and must not
+ /// use it for other purposes than input to the corresponding constructor
+ /// to restore it. Application behavior that assumes the specific
+ /// organization of the image is not guaranteed.
+ ///
+ /// \throw isc::BadValue buf_len is too short (this method never throws
+ /// otherwise)
+ ///
+ /// \param buf Pointer to the placeholder to dump the serialized image
+ /// \param buf_len The size of available region in \c buf
+ void serialize(void* buf, size_t buf_len) const;
+
/// \brief Compares two label sequences for equality.
///
/// Performs a (optionally case-insensitive) comparison between this
@@ -187,7 +203,9 @@ public:
/// \brief Returns the current number of labels for this LabelSequence
///
/// \return The number of labels
- size_t getLabelCount() const { return (last_label_ - first_label_); }
+ size_t getLabelCount() const {
+ return (last_label_ - first_label_ + 1);
+ }
/// \brief Convert the LabelSequence to a string.
///
@@ -252,11 +270,12 @@ public:
bool isAbsolute() const;
private:
- const uint8_t* data_;
- const uint8_t* offsets_;
- size_t offsets_size_;
- size_t first_label_;
- size_t last_label_;
+ const uint8_t* data_; // wire-format name data
+ const uint8_t* offsets_; // an array of offsets in data_ for the labels
+ size_t first_label_; // index of offsets_ for the first label
+ size_t last_label_; // index of offsets_ for the last label.
+ // can be equal to first_label_, but must not
+ // be smaller (the class ensures that)
};
@@ -281,3 +300,7 @@ operator<<(std::ostream& os, const LabelSequence& label_sequence);
} // end namespace isc
#endif
+
+// Local Variables:
+// mode: c++
+// End:
diff --git a/src/lib/dns/name.h b/src/lib/dns/name.h
index 27186d7..261caee 100644
--- a/src/lib/dns/name.h
+++ b/src/lib/dns/name.h
@@ -106,38 +106,45 @@ public:
};
///
-/// This is a supplemental class used only as a return value of Name::compare().
-/// It encapsulate a tuple of the comparison: ordering, number of common labels,
-/// and relationship as follows:
+/// This is a supplemental class used only as a return value of
+/// Name::compare() and LabelSequence::compare().
+/// It encapsulate a tuple of the comparison: ordering, number of common
+/// labels, and relationship as follows:
/// - ordering: relative ordering under the DNSSEC order relation
-/// - labels: the number of common significant labels of the two names being
-/// compared
+/// - labels: the number of common significant labels of the two names or
+/// two label sequences being compared
/// - relationship: see NameComparisonResult::NameRelation
///
+/// Note that the ordering is defined for two label sequences that have no
+/// hierarchical relationship (in which case the relationship will be NONE).
+/// For example, two non absolute (or "relative") sequences "example.com" and
+/// "example.org" have no hierarchical relationship, and the former should be
+/// sorted before (i.e. "smaller") than the latter.
class NameComparisonResult {
public:
/// The relation of two names under comparison.
/// Its semantics for the case of
/// <code>name1->compare(name2)</code> (where name1 and name2 are instances
- /// of the Name class) is as follows:
+ /// of the \c Name or \c LabelSequence class) is as follows:
/// - SUPERDOMAIN: name1 properly contains name2; name2 is a proper
/// subdomain of name1
/// - SUBDOMAIN: name1 is a proper subdomain of name2
/// - EQUAL: name1 and name2 are equal
/// - COMMONANCESTOR: name1 and name2 share a common ancestor
+ /// - NONE: There's no hierarchical relationship between name1 and name2
///
- /// Note that in our implementation there's always a hierarchical
- /// relationship between any two names since all names are absolute and
+ /// Note that there's always a hierarchical relationship between any two
+ /// names since all names (not generic label sequences) are absolute and
/// they at least share the trailing empty label.
/// So, for example, the relationship between "com." and "net." is
- /// "commonancestor". This may be counter intuitive and inconvenient, but
- /// we'll keep this design at the moment until we decide whether and how to
- /// handle "non absolute" names (see the description of the \c Name class).
- /// If we want to (re)introduce the notion of non absolute names, we'll
- /// want to distinguish "com" and "com.", and the current definition would
- /// be more compatible for that purpose.
- /// If, on the other hand, we finally decide we really don't need that
- /// notion, we'll probably reconsider the design here, too.
+ /// "commonancestor". The relationship of "NONE" can only happen for
+ /// comparison between two label sequences (\c LabelSequence objects);
+ /// usually only SUPERDOMAIN, SUBDOMAIN or EQUAL are important relationship
+ /// between two names.
+ ///
+ /// When two \c LabelSequence objects are compared, it's generally expected
+ /// they are either both absolute or both non absolute; if one is absolute
+ /// and the other is not, the resulting relationship will be NONE.
enum NameRelation {
SUPERDOMAIN = 0,
SUBDOMAIN = 1,
diff --git a/src/lib/dns/tests/labelsequence_unittest.cc b/src/lib/dns/tests/labelsequence_unittest.cc
index dd41d5e..b999b9d 100644
--- a/src/lib/dns/tests/labelsequence_unittest.cc
+++ b/src/lib/dns/tests/labelsequence_unittest.cc
@@ -21,11 +21,17 @@
#include <boost/functional/hash.hpp>
#include <string>
+#include <vector>
+#include <utility>
#include <set>
using namespace isc::dns;
using namespace std;
+// XXX: this is defined as class static constants, but some compilers
+// seemingly cannot find the symbols when used in the EXPECT_xxx macros.
+const size_t LabelSequence::MAX_SERIALIZED_LENGTH;
+
namespace {
class LabelSequenceTest : public ::testing::Test {
@@ -38,6 +44,13 @@ public:
n10("\\000xample.org"),
n11("\\000xample.com"),
n12("\\000xamplE.com"),
+ n_maxlabel("0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
+ "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
+ "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
+ "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
+ "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
+ "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
+ "0.1.2.3.4.5.6"),
ls1(n1), ls2(n2), ls3(n3), ls4(n4), ls5(n5),
ls6(n6), ls7(n7), ls8(n8),
ls9(n9), ls10(n10), ls11(n11), ls12(n12)
@@ -46,6 +59,7 @@ public:
// the labelsequences
Name n1, n2, n3, n4, n5, n6, n7, n8;
Name n9, n10, n11, n12;
+ const Name n_maxlabel;
LabelSequence ls1, ls2, ls3, ls4, ls5, ls6, ls7, ls8;
LabelSequence ls9, ls10, ls11, ls12;
@@ -189,12 +203,11 @@ TEST_F(LabelSequenceTest, compare) {
LabelSequence lsc(nc);
// "g.f.e.d.c.example.org." and "b.example.org" (not absolute), case
- // in-sensitive
+ // in-sensitive; the absolute one is always smaller.
lsb.stripRight(1);
result = lsc.compare(lsb);
- EXPECT_EQ(isc::dns::NameComparisonResult::NONE,
- result.getRelation());
- EXPECT_EQ(0, result.getOrder());
+ EXPECT_EQ(isc::dns::NameComparisonResult::NONE, result.getRelation());
+ EXPECT_GT(0, result.getOrder());
EXPECT_EQ(0, result.getCommonLabels());
// "g.f.e.d.c.example.org." and "example.org.", case in-sensitive
@@ -270,13 +283,13 @@ TEST_F(LabelSequenceTest, compare) {
Name ng("w.x.y.isc.EXAMPLE.org");
LabelSequence lsg(ng);
- // "a.b.c.isc.example.org." and "w.x.y.isc.EXAMPLE.org" (not
- // absolute), case in-sensitive
+ // lsf: "a.b.c.isc.example.org."
+ // lsg: "w.x.y.isc.EXAMPLE.org" (not absolute), case in-sensitive.
+ // the absolute one is always smaller.
lsg.stripRight(1);
- result = lsg.compare(lsf);
- EXPECT_EQ(isc::dns::NameComparisonResult::NONE,
- result.getRelation());
- EXPECT_EQ(0, result.getOrder());
+ result = lsg.compare(lsf); // lsg > lsf
+ EXPECT_EQ(isc::dns::NameComparisonResult::NONE, result.getRelation());
+ EXPECT_LT(0, result.getOrder());
EXPECT_EQ(0, result.getCommonLabels());
// "a.b.c.isc.example.org" (not absolute) and
@@ -298,14 +311,23 @@ TEST_F(LabelSequenceTest, compare) {
EXPECT_LT(0, result.getOrder());
EXPECT_EQ(2, result.getCommonLabels());
- // "a.b.c" (not absolute) and
- // "w.x.y" (not absolute), case in-sensitive
+ // lsf: "a.b.c" (not absolute) and
+ // lsg: "w.x.y" (not absolute), case in-sensitive; a.b.c < w.x.y;
+ // no common labels.
lsf.stripRight(2);
lsg.stripRight(2);
- result = lsg.compare(lsf);
- EXPECT_EQ(isc::dns::NameComparisonResult::NONE,
- result.getRelation());
- EXPECT_EQ(0, result.getOrder());
+ result = lsf.compare(lsg);
+ EXPECT_EQ(isc::dns::NameComparisonResult::NONE, result.getRelation());
+ EXPECT_GT(0, result.getOrder());
+ EXPECT_EQ(0, result.getCommonLabels());
+
+ // lsf2: a.b.cc (not absolute); a.b.c < a.b.cc, no common labels.
+ const Name nf2("a.b.cc");
+ LabelSequence lsf2(nf2);
+ lsf2.stripRight(1);
+ result = lsf.compare(lsf2);
+ EXPECT_EQ(isc::dns::NameComparisonResult::NONE, result.getRelation());
+ EXPECT_GT(0, result.getOrder());
EXPECT_EQ(0, result.getCommonLabels());
Name nh("aexample.org");
@@ -324,13 +346,13 @@ TEST_F(LabelSequenceTest, compare) {
EXPECT_EQ(1, result.getCommonLabels());
// "aexample" (not absolute) and
- // "bexample" (not absolute), case in-sensitive
+ // "bexample" (not absolute), case in-sensitive;
+ // aexample < bexample; no common labels.
lsh.stripRight(1);
lsi.stripRight(1);
result = lsh.compare(lsi);
- EXPECT_EQ(isc::dns::NameComparisonResult::NONE,
- result.getRelation());
- EXPECT_EQ(0, result.getOrder());
+ EXPECT_EQ(isc::dns::NameComparisonResult::NONE, result.getRelation());
+ EXPECT_GT(0, result.getOrder());
EXPECT_EQ(0, result.getCommonLabels());
Name nj("example.org");
@@ -400,93 +422,6 @@ TEST_F(LabelSequenceTest, getData) {
getDataCheck("\000", 1, ls7);
};
-TEST_F(LabelSequenceTest, getOffsetData) {
- size_t len;
- uint8_t placeholder[Name::MAX_LABELS];
-
- Name nx("x.isc.example.org");
- LabelSequence lsx(nx);
-
- // x.isc.example.org.
- lsx.getOffsetData(&len, placeholder);
- EXPECT_EQ(5, len);
- EXPECT_EQ(0, placeholder[0]);
- EXPECT_EQ(2, placeholder[1]);
- EXPECT_EQ(6, placeholder[2]);
- EXPECT_EQ(14, placeholder[3]);
- EXPECT_EQ(18, placeholder[4]);
-
- lsx.stripLeft(2);
-
- // example.org.
- lsx.getOffsetData(&len, placeholder);
- EXPECT_EQ(3, len);
- EXPECT_EQ(0, placeholder[0]);
- EXPECT_EQ(8, placeholder[1]);
- EXPECT_EQ(12, placeholder[2]);
-
- lsx.stripLeft(1);
-
- // org.
- lsx.getOffsetData(&len, placeholder);
- EXPECT_EQ(2, len);
- EXPECT_EQ(0, placeholder[0]);
- EXPECT_EQ(4, placeholder[1]);
-
- lsx.stripLeft(1);
-
- // .
- lsx.getOffsetData(&len, placeholder);
- EXPECT_EQ(1, len);
- EXPECT_EQ(0, placeholder[0]);
-
- Name ny("y.isc.example.org");
- LabelSequence lsy(ny);
-
- // y.isc.example.org.
- lsy.getOffsetData(&len, placeholder);
- EXPECT_EQ(5, len);
- EXPECT_EQ(0, placeholder[0]);
- EXPECT_EQ(2, placeholder[1]);
- EXPECT_EQ(6, placeholder[2]);
- EXPECT_EQ(14, placeholder[3]);
- EXPECT_EQ(18, placeholder[4]);
-
- lsy.stripRight(1);
-
- // y.isc.example.org
- lsy.getOffsetData(&len, placeholder);
- EXPECT_EQ(4, len);
- EXPECT_EQ(0, placeholder[0]);
- EXPECT_EQ(2, placeholder[1]);
- EXPECT_EQ(6, placeholder[2]);
- EXPECT_EQ(14, placeholder[3]);
-
- lsy.stripRight(1);
-
- // y.isc.example
- lsy.getOffsetData(&len, placeholder);
- EXPECT_EQ(3, len);
- EXPECT_EQ(0, placeholder[0]);
- EXPECT_EQ(2, placeholder[1]);
- EXPECT_EQ(6, placeholder[2]);
-
- lsy.stripLeft(1);
-
- // isc.example
- lsy.getOffsetData(&len, placeholder);
- EXPECT_EQ(2, len);
- EXPECT_EQ(0, placeholder[0]);
- EXPECT_EQ(4, placeholder[1]);
-
- lsy.stripLeft(1);
-
- // example
- lsy.getOffsetData(&len, placeholder);
- EXPECT_EQ(1, len);
- EXPECT_EQ(0, placeholder[0]);
-};
-
TEST_F(LabelSequenceTest, stripLeft) {
EXPECT_TRUE(ls1.equals(ls3));
ls1.stripLeft(0);
@@ -646,14 +581,7 @@ TEST_F(LabelSequenceTest, toText) {
"012345678901234567890123456789"
"0123456789012345678901234567890", ls_long1.toText());
- Name n_long2("0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
- "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
- "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
- "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
- "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
- "0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
- "0.1.2.3.4.5.6");
- LabelSequence ls_long2(n_long2);
+ LabelSequence ls_long2(n_maxlabel);
EXPECT_EQ("0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
"0.1.2.3.4.5.6.7.8.9.0.1.2.3.4.5.6.7.8.9."
@@ -762,78 +690,98 @@ TEST_F(LabelSequenceTest, LeftShiftOperator) {
EXPECT_EQ(ls1.toText(), oss.str());
}
-// Test different ways of construction, and see if they compare
-TEST(LabelSequence, rawConstruction) {
- Name n("example.org");
-
- uint8_t data[] = { 0x07, 'e', 'x', 'a', 'm', 'p', 'l', 'e',
- 0x03, 'o', 'r', 'g',
- 0x00 };
- uint8_t offsets[] = { 0, 8, 12 };
- size_t offsets_size = 3;
-
- LabelSequence s1(n);
- LabelSequence s2(s1);
- LabelSequence s3(data, offsets, offsets_size);
-
- // Assuming equality is transitive, so only comparing 1 to 2 and 1 to 3
- NameComparisonResult result = s1.compare(s2);
- EXPECT_EQ(isc::dns::NameComparisonResult::EQUAL,
- result.getRelation());
- EXPECT_EQ(0, result.getOrder());
- EXPECT_EQ(3, result.getCommonLabels());
-
- result = s1.compare(s3);
- EXPECT_EQ(isc::dns::NameComparisonResult::EQUAL,
- result.getRelation());
- EXPECT_EQ(0, result.getOrder());
- EXPECT_EQ(3, result.getCommonLabels());
-
- // Modify the data and make sure it's not equal anymore
- data[2] = 'f';
- result = s1.compare(s3);
- EXPECT_EQ(isc::dns::NameComparisonResult::COMMONANCESTOR,
- result.getRelation());
- EXPECT_EQ(2, result.getCommonLabels());
-
- s1.stripRight(1);
- s3.stripRight(1);
-
- result = s1.compare(s3);
- EXPECT_EQ(isc::dns::NameComparisonResult::COMMONANCESTOR,
- result.getRelation());
- EXPECT_EQ(1, result.getCommonLabels());
+TEST_F(LabelSequenceTest, serialize) {
+ // placeholder for serialized data
+ uint8_t labels_buf[LabelSequence::MAX_SERIALIZED_LENGTH];
+
+ // vector to store expected and actual data
+ vector<LabelSequence> actual_labelseqs;
+ typedef pair<size_t, const uint8_t*> DataPair;
+ vector<DataPair> expected;
+
+ // An absolute sequence directly constructed from a valid name.
+ // labels = 3, offset sequence = 0, 8, 12, data = "example.com."
+ actual_labelseqs.push_back(ls1);
+ const uint8_t expected_data1[] = {
+ 3, 0, 8, 12, 7, 'e', 'x', 'a', 'm', 'p', 'l', 'e',
+ 3, 'o', 'r', 'g', 0 };
+ expected.push_back(DataPair(sizeof(expected_data1), expected_data1));
+
+ // Strip the original one from right.
+ // labels = 2, offset sequence = 0, 8, data = "example.com" (non absolute)
+ LabelSequence ls_rstripped = ls1;
+ ls_rstripped.stripRight(1);
+ actual_labelseqs.push_back(ls_rstripped);
+ const uint8_t expected_data2[] = {
+ 2, 0, 8, 7, 'e', 'x', 'a', 'm', 'p', 'l', 'e',
+ 3, 'o', 'r', 'g'};
+ expected.push_back(DataPair(sizeof(expected_data2), expected_data2));
+
+ // Strip the original one from left.
+ // labels = 2, offset sequence = 0, 4, data = "com."
+ // Note that offsets are adjusted so that they begin with 0.
+ LabelSequence ls_lstripped = ls1;
+ ls_lstripped.stripLeft(1);
+ actual_labelseqs.push_back(ls_lstripped);
+ const uint8_t expected_data3[] = { 2, 0, 4, 3, 'o', 'r', 'g', 0 };
+ expected.push_back(DataPair(sizeof(expected_data3), expected_data3));
+
+ // Root label.
+ LabelSequence ls_root(Name::ROOT_NAME());
+ actual_labelseqs.push_back(ls_root);
+ const uint8_t expected_data4[] = { 1, 0, 0 };
+ expected.push_back(DataPair(sizeof(expected_data4), expected_data4));
+
+ // Non absolute single-label.
+ LabelSequence ls_single = ls_rstripped;
+ ls_single.stripRight(1);
+ actual_labelseqs.push_back(ls_single);
+ const uint8_t expected_data5[] = {
+ 1, 0, 7, 'e', 'x', 'a', 'm', 'p', 'l', 'e' };
+ expected.push_back(DataPair(sizeof(expected_data5), expected_data5));
+
+ // For each data set, serialize the labels and compare the data to the
+ // expected one.
+ vector<DataPair>::const_iterator it = expected.begin();
+ vector<LabelSequence>::const_iterator itl = actual_labelseqs.begin();
+ for (; it != expected.end(); ++it, ++itl) {
+ SCOPED_TRACE(itl->toText());
+
+ const size_t serialized_len = itl->getSerializedLength();
+
+ ASSERT_GE(LabelSequence::MAX_SERIALIZED_LENGTH, serialized_len);
+ itl->serialize(labels_buf, serialized_len);
+ EXPECT_EQ(it->first, serialized_len);
+ EXPECT_EQ(0, memcmp(it->second, labels_buf, serialized_len));
+
+ EXPECT_EQ(NameComparisonResult::EQUAL,
+ LabelSequence(labels_buf).compare(*itl).getRelation());
+ }
- data[9] = 'f';
- result = s1.compare(s3);
- EXPECT_EQ(isc::dns::NameComparisonResult::NONE,
- result.getRelation());
- EXPECT_EQ(0, result.getCommonLabels());
+ EXPECT_THROW(ls1.serialize(labels_buf, ls1.getSerializedLength() - 1),
+ isc::BadValue);
}
-// Test with some data that exceeds limits (MAX_LABELS and MAX_LABEL_LEN)
-TEST(LabelSequence, badRawConstruction) {
- uint8_t data[1] = { 0 };
- uint8_t offsets[1] = { 0 };
-
- EXPECT_THROW(LabelSequence(NULL, offsets, 1), isc::BadValue);
- EXPECT_THROW(LabelSequence(data, NULL, 1), isc::BadValue);
- EXPECT_THROW(LabelSequence(data, offsets, 0), isc::BadValue);
-
- // exceed MAX_LABELS
- EXPECT_THROW(LabelSequence(data, offsets, 127), isc::BadValue);
+TEST_F(LabelSequenceTest, badDeserialize) {
+ EXPECT_THROW(LabelSequence(NULL), isc::BadValue);
+ const uint8_t zero_offsets[] = { 0 };
+ EXPECT_THROW(LabelSequence ls(zero_offsets), isc::BadValue);
+ const uint8_t toomany_offsets[] = { Name::MAX_LABELS + 1 };
+ EXPECT_THROW(LabelSequence ls(toomany_offsets), isc::BadValue);
// exceed MAX_LABEL_LEN
- uint8_t offsets_toolonglabel[1] = { 64 };
- EXPECT_THROW(LabelSequence(data, offsets_toolonglabel, 1), isc::BadValue);
-
- // Add an offset that is lower than the previous offset
- uint8_t offsets_lower[3] = { 0, 8, 4 };
- EXPECT_THROW(LabelSequence(data, offsets_lower, 3), isc::BadValue);
-
- // Add an offset that is equal to the previous offset
- uint8_t offsets_noincrease[3] = { 0, 8, 8 };
- EXPECT_THROW(LabelSequence(data, offsets_noincrease, 3), isc::BadValue);
+ const uint8_t offsets_toolonglabel[] = { 2, 0, 64 };
+ EXPECT_THROW(LabelSequence ls(offsets_toolonglabel), isc::BadValue);
+
+ // Inconsistent data: an offset is lower than the previous offset
+ const uint8_t offsets_lower[] = { 3, // # of offsets
+ 0, 2, 1, // offsets
+ 1, 'a', 1, 'b', 0};
+ EXPECT_THROW(LabelSequence ls(offsets_lower), isc::BadValue);
+
+ // Inconsistent data: an offset is equal to the previous offset
+ const uint8_t offsets_noincrease[] = { 2, 0, 0, 0, 0 };
+ EXPECT_THROW(LabelSequence ls(offsets_noincrease), isc::BadValue);
}
}
More information about the bind10-changes
mailing list