table: attach PIT entry to NameTree node within depth limit
refs #4262
Change-Id: I64d76a337c3b491efa2f93c803046cea70c87000
diff --git a/daemon/table/name-tree-hashtable.cpp b/daemon/table/name-tree-hashtable.cpp
index 421f298..e6b3c33 100644
--- a/daemon/table/name-tree-hashtable.cpp
+++ b/daemon/table/name-tree-hashtable.cpp
@@ -57,12 +57,12 @@
using HashFunc = std::conditional<(sizeof(HashValue) > 4), Hash64, Hash32>::type;
HashValue
-computeHash(const Name& name, ssize_t prefixLen)
+computeHash(const Name& name, size_t prefixLen)
{
name.wireEncode(); // ensure wire buffer exists
HashValue h = 0;
- for (size_t i = 0, last = prefixLen < 0 ? name.size() : prefixLen; i < last; ++i) {
+ for (size_t i = 0, last = std::min(prefixLen, name.size()); i < last; ++i) {
const name::Component& comp = name[i];
h ^= HashFunc::compute(comp.wire(), comp.size());
}
@@ -70,11 +70,11 @@
}
HashSequence
-computeHashes(const Name& name, ssize_t prefixLen)
+computeHashes(const Name& name, size_t prefixLen)
{
name.wireEncode(); // ensure wire buffer exists
- size_t last = prefixLen < 0 ? name.size() : std::min(static_cast<size_t>(prefixLen), name.size());
+ size_t last = std::min(prefixLen, name.size());
HashSequence seq;
seq.reserve(last + 1);
diff --git a/daemon/table/name-tree-hashtable.hpp b/daemon/table/name-tree-hashtable.hpp
index d7ca6a6..ec5caa0 100644
--- a/daemon/table/name-tree-hashtable.hpp
+++ b/daemon/table/name-tree-hashtable.hpp
@@ -42,22 +42,16 @@
*/
using HashSequence = std::vector<HashValue>;
-/** \brief computes a single hash value
- * \param name base name
- * \param prefixLen if non-negative, compute hash value for name.getPrefix(prefixLen);
- * if negative, compute hash value for complete name
+/** \brief computes hash value of \p name.getPrefix(prefixLen)
*/
HashValue
-computeHash(const Name& name, ssize_t prefixLen = -1);
+computeHash(const Name& name, size_t prefixLen = std::numeric_limits<size_t>::max());
-/** \brief computes hash values for each prefix of name
- * \param name base name
- * \param prefixLen if non-negative, compute up to the first \p prefixLen name components;
- * if negative, compute all hash values
+/** \brief computes hash values for each prefix of \p name.getPrefix(prefixLen)
* \return a hash sequence, where the i-th hash value equals computeHash(name, i)
*/
HashSequence
-computeHashes(const Name& name, ssize_t prefixLen = -1);
+computeHashes(const Name& name, size_t prefixLen = std::numeric_limits<size_t>::max());
/** \brief a hashtable node
*
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 65cafd7..1fa54af 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -44,7 +44,7 @@
NameTree::lookup(const Name& name, bool enforceMaxDepth)
{
NFD_LOG_TRACE("lookup " << name);
- size_t depth = enforceMaxDepth ? getMaxDepth() : name.size();
+ size_t depth = enforceMaxDepth ? std::min(name.size(), getMaxDepth()) : name.size();
HashSequence hashes = computeHashes(name, depth);
const Node* node = nullptr;
@@ -146,9 +146,9 @@
}
Entry*
-NameTree::findExactMatch(const Name& name) const
+NameTree::findExactMatch(const Name& name, size_t prefixLen) const
{
- const Node* node = m_ht.find(name, name.size());
+ const Node* node = m_ht.find(name, std::min(name.size(), prefixLen));
return node == nullptr ? nullptr : &node->entry;
}
@@ -186,13 +186,13 @@
const Entry* nte = this->getEntry(pitEntry);
BOOST_ASSERT(nte != nullptr);
+ // PIT entry Interest name either exceeds depth limit or ends with an implicit digest: go deeper
if (nte->getName().size() < pitEntry.getName().size()) {
- // special case: PIT entry whose Interest name ends with an implicit digest
- // are attached to the name tree entry with one-shorter-prefix.
- BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
- BOOST_ASSERT(nte->getName() == pitEntry.getName().getPrefix(-1));
- const Entry* exact = this->findExactMatch(pitEntry.getName());
- if (exact != nullptr) {
+ for (size_t prefixLen = nte->getName().size() + 1; prefixLen <= pitEntry.getName().size(); ++prefixLen) {
+ const Entry* exact = this->findExactMatch(pitEntry.getName(), prefixLen);
+ if (exact == nullptr) {
+ break;
+ }
nte = exact;
}
}
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 6d04821..04e504e 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -136,10 +136,10 @@
public: // matching
/** \brief exact match lookup
- * \return entry with \p name, or nullptr if it does not exist
+ * \return entry with \p name.getPrefix(prefixLen), or nullptr if it does not exist
*/
Entry*
- findExactMatch(const Name& name) const;
+ findExactMatch(const Name& name, size_t prefixLen = std::numeric_limits<size_t>::max()) const;
/** \brief longest prefix matching
* \return entry whose name is a prefix of \p name and passes \p entrySelector,
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index 3256b89..2050417 100644
--- a/daemon/table/pit.cpp
+++ b/daemon/table/pit.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -51,7 +51,7 @@
// ensure NameTree entry exists
name_tree::Entry* nte = nullptr;
if (allowInsert) {
- nte = &m_nameTree.lookup(nteName);
+ nte = &m_nameTree.lookup(nteName, true);
}
else {
nte = m_nameTree.findExactMatch(nteName);
@@ -61,7 +61,7 @@
}
// check if PIT entry already exists
- size_t nteNameLen = nteName.size();
+ size_t nteNameLen = nte->getName().size();
const std::vector<shared_ptr<Entry>>& pitEntries = nte->getPitEntries();
auto it = std::find_if(pitEntries.begin(), pitEntries.end(),
[&interest, nteNameLen] (const shared_ptr<Entry>& entry) {
diff --git a/tests/daemon/table/pit.t.cpp b/tests/daemon/table/pit.t.cpp
index a468ed0..c883ff4 100644
--- a/tests/daemon/table/pit.t.cpp
+++ b/tests/daemon/table/pit.t.cpp
@@ -1,5 +1,5 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
+/*
* Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
@@ -308,6 +308,44 @@
BOOST_CHECK_EQUAL(found->getName(), fullName);
}
+BOOST_AUTO_TEST_CASE(InsertMatchLongName)
+{
+ NameTree nameTree(16);
+ Pit pit(nameTree);
+
+ Name n1;
+ while (n1.size() < NameTree::getMaxDepth()) {
+ n1.append("A");
+ }
+ Name n2 = n1;
+ while (n2.size() < NameTree::getMaxDepth() * 2) {
+ n2.append("B");
+ }
+ Name n3 = n1;
+ while (n3.size() < NameTree::getMaxDepth() * 2) {
+ n3.append("C");
+ }
+ auto d2 = makeData(n2);
+ auto i2 = makeInterest(n2);
+ auto d3 = makeData(n3);
+ auto i3 = makeInterest(d3->getFullName());
+
+ shared_ptr<Entry> entry2 = pit.insert(*i2).first;
+ shared_ptr<Entry> entry3 = pit.insert(*i3).first;
+
+ BOOST_CHECK_EQUAL(pit.size(), 2);
+ BOOST_CHECK_EQUAL(nameTree.size(), 1 + NameTree::getMaxDepth()); // root node + max depth
+ BOOST_CHECK(entry2->getInterest().matchesInterest(*i2));
+ BOOST_CHECK(entry3->getInterest().matchesInterest(*i3));
+
+ DataMatchResult matches2 = pit.findAllDataMatches(*d2);
+ BOOST_REQUIRE_EQUAL(std::distance(matches2.begin(), matches2.end()), 1);
+ BOOST_CHECK(*matches2.begin() == entry2);
+ DataMatchResult matches3 = pit.findAllDataMatches(*d3);
+ BOOST_REQUIRE_EQUAL(std::distance(matches3.begin(), matches3.end()), 1);
+ BOOST_CHECK(*matches3.begin() == entry3);
+}
+
BOOST_AUTO_TEST_CASE(Iterator)
{
NameTree nameTree(16);