table: fix PIT not matching full name
refs #3363
Change-Id: I4ff3d02aaf43c3aaba843cfcf6221c218c1cea99
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index aaa89c6..7d60dfa 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -90,11 +90,9 @@
shared_ptr<fib::Entry>
Fib::findLongestPrefixMatch(const pit::Entry& pitEntry) const
{
- shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(pitEntry);
-
- BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
-
- return findLongestPrefixMatch(nameTreeEntry);
+ shared_ptr<name_tree::Entry> nte = m_nameTree.findLongestPrefixMatch(pitEntry);
+ BOOST_ASSERT(nte != nullptr);
+ return findLongestPrefixMatch(nte);
}
shared_ptr<fib::Entry>
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 0f730d1..8e699c5 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -240,6 +240,99 @@
return entry;
}
+// return {false: this entry is not empty, true: this entry is empty and erased}
+bool
+NameTree::eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry)
+{
+ BOOST_ASSERT(static_cast<bool>(entry));
+
+ NFD_LOG_TRACE("eraseEntryIfEmpty " << entry->getPrefix());
+
+ // first check if this Entry can be erased
+ if (entry->isEmpty())
+ {
+ // update child-related info in the parent
+ shared_ptr<name_tree::Entry> parent = entry->getParent();
+
+ if (static_cast<bool>(parent))
+ {
+ std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList =
+ parent->getChildren();
+
+ bool isFound = false;
+ size_t size = parentChildrenList.size();
+ for (size_t i = 0; i < size; i++)
+ {
+ if (parentChildrenList[i] == entry)
+ {
+ parentChildrenList[i] = parentChildrenList[size - 1];
+ parentChildrenList.pop_back();
+ isFound = true;
+ break;
+ }
+ }
+
+ BOOST_VERIFY(isFound == true);
+ }
+
+ // remove this Entry and its Name Tree Node
+ name_tree::Node* node = entry->m_node;
+ name_tree::Node* nodePrev = node->m_prev;
+
+ // configure the previous node
+ if (nodePrev != 0)
+ {
+ // link the previous node to the next node
+ nodePrev->m_next = node->m_next;
+ }
+ else
+ {
+ m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
+ }
+
+ // link the previous node with the next node (skip the erased one)
+ if (node->m_next != 0)
+ {
+ node->m_next->m_prev = nodePrev;
+ node->m_next = 0;
+ }
+
+ BOOST_ASSERT(node->m_next == 0);
+
+ m_nItems--;
+ delete node;
+
+ if (static_cast<bool>(parent))
+ eraseEntryIfEmpty(parent);
+
+ size_t newNBuckets = static_cast<size_t>(m_shrinkFactor *
+ static_cast<double>(m_nBuckets));
+
+ if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold)
+ {
+ resize(newNBuckets);
+ }
+
+ return true;
+
+ } // if this entry is empty
+
+ return false; // if this entry is not empty
+}
+
+shared_ptr<name_tree::Entry>
+NameTree::get(const pit::Entry& pitEntry)
+{
+ shared_ptr<name_tree::Entry> nte = pitEntry.m_nameTreeEntry;
+ if (nte->getPrefix().size() == pitEntry.getName().size()) {
+ return nte;
+ }
+
+ BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
+ BOOST_ASSERT(nte->getPrefix() == pitEntry.getName().getPrefix(-1));
+ return this->lookup(pitEntry.getName());
+}
+
// Exact Match
shared_ptr<name_tree::Entry>
NameTree::findExactMatch(const Name& prefix) const
@@ -324,84 +417,40 @@
return shared_ptr<name_tree::Entry>();
}
-// return {false: this entry is not empty, true: this entry is empty and erased}
-bool
-NameTree::eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry)
+shared_ptr<name_tree::Entry>
+NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry) const
{
- BOOST_ASSERT(static_cast<bool>(entry));
+ shared_ptr<name_tree::Entry> nte = pitEntry.m_nameTreeEntry;
+ if (nte->getPrefix().size() == pitEntry.getName().size()) {
+ return nte;
+ }
- NFD_LOG_TRACE("eraseEntryIfEmpty " << entry->getPrefix());
+ BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
+ BOOST_ASSERT(nte->getPrefix() == pitEntry.getName().getPrefix(-1));
+ shared_ptr<name_tree::Entry> exact = this->findExactMatch(pitEntry.getName());
+ return exact == nullptr ? nte : exact;
+}
- // first check if this Entry can be erased
- if (entry->isEmpty())
- {
- // update child-related info in the parent
- shared_ptr<name_tree::Entry> parent = entry->getParent();
+boost::iterator_range<NameTree::const_iterator>
+NameTree::findAllMatches(const Name& prefix,
+ const name_tree::EntrySelector& entrySelector) const
+{
+ NFD_LOG_TRACE("NameTree::findAllMatches" << prefix);
- if (static_cast<bool>(parent))
- {
- std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList =
- parent->getChildren();
+ // As we are using Name Prefix Hash Table, and the current LPM() is
+ // implemented as starting from full name, and reduce the number of
+ // components by 1 each time, we could use it here.
+ // For trie-like design, it could be more efficient by walking down the
+ // trie from the root node.
- bool isFound = false;
- size_t size = parentChildrenList.size();
- for (size_t i = 0; i < size; i++)
- {
- if (parentChildrenList[i] == entry)
- {
- parentChildrenList[i] = parentChildrenList[size - 1];
- parentChildrenList.pop_back();
- isFound = true;
- break;
- }
- }
+ shared_ptr<name_tree::Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
- BOOST_VERIFY(isFound == true);
- }
-
- // remove this Entry and its Name Tree Node
- name_tree::Node* node = entry->m_node;
- name_tree::Node* nodePrev = node->m_prev;
-
- // configure the previous node
- if (nodePrev != 0)
- {
- // link the previous node to the next node
- nodePrev->m_next = node->m_next;
- }
- else
- {
- m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
- }
-
- // link the previous node with the next node (skip the erased one)
- if (node->m_next != 0)
- {
- node->m_next->m_prev = nodePrev;
- node->m_next = 0;
- }
-
- BOOST_ASSERT(node->m_next == 0);
-
- m_nItems--;
- delete node;
-
- if (static_cast<bool>(parent))
- eraseEntryIfEmpty(parent);
-
- size_t newNBuckets = static_cast<size_t>(m_shrinkFactor *
- static_cast<double>(m_nBuckets));
-
- if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold)
- {
- resize(newNBuckets);
- }
-
- return true;
-
- } // if this entry is empty
-
- return false; // if this entry is not empty
+ if (static_cast<bool>(entry)) {
+ const_iterator begin(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
+ return {begin, end()};
+ }
+ // If none of the entry satisfies the requirements, then return the end() iterator.
+ return {end(), end()};
}
boost::iterator_range<NameTree::const_iterator>
@@ -452,28 +501,6 @@
return {it, end()};
}
-boost::iterator_range<NameTree::const_iterator>
-NameTree::findAllMatches(const Name& prefix,
- const name_tree::EntrySelector& entrySelector) const
-{
- NFD_LOG_TRACE("NameTree::findAllMatches" << prefix);
-
- // As we are using Name Prefix Hash Table, and the current LPM() is
- // implemented as starting from full name, and reduce the number of
- // components by 1 each time, we could use it here.
- // For trie-like design, it could be more efficient by walking down the
- // trie from the root node.
-
- shared_ptr<name_tree::Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
-
- if (static_cast<bool>(entry)) {
- const_iterator begin(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
- return {begin, end()};
- }
- // If none of the entry satisfies the requirements, then return the end() iterator.
- return {end(), end()};
-}
-
// Hash Table Resize
void
NameTree::resize(size_t newNBuckets)
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 465299a..15a717b 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -133,19 +133,31 @@
eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry);
public: // shortcut access
- /// get NameTree entry from attached FIB entry
+ /** \brief get NameTree entry from FIB entry
+ *
+ * This is equivalent to .lookup(fibEntry.getPrefix())
+ */
shared_ptr<name_tree::Entry>
get(const fib::Entry& fibEntry) const;
- /// get NameTree entry from attached PIT entry
+ /** \brief get NameTree entry from PIT entry
+ *
+ * This is equivalent to .lookup(pitEntry.getName()).
+ */
shared_ptr<name_tree::Entry>
- get(const pit::Entry& pitEntry) const;
+ get(const pit::Entry& pitEntry);
- /// get NameTree entry from attached Measurements entry
+ /** \brief get NameTree entry from Measurements entry
+ *
+ * This is equivalent to .lookup(measurementsEntry.getName())
+ */
shared_ptr<name_tree::Entry>
get(const measurements::Entry& measurementsEntry) const;
- /// get NameTree entry from attached StrategyChoice entry
+ /** \brief get NameTree entry from StrategyChoice entry
+ *
+ * This is equivalent to .lookup(strategyChoiceEntry.getName())
+ */
shared_ptr<name_tree::Entry>
get(const strategy_choice::Entry& strategyChoiceEntry) const;
@@ -173,6 +185,13 @@
const name_tree::EntrySelector& entrySelector =
name_tree::AnyEntry()) const;
+ /** \brief longest prefix matching for Interest name of the PIT entry
+ *
+ * This is equivalent to .findLongestPrefixMatch(pitEntry.getName(), AnyEntry()).
+ */
+ shared_ptr<name_tree::Entry>
+ findLongestPrefixMatch(const pit::Entry& pitEntry) const;
+
/** \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
* \return an unspecified type that have .begin() and .end() methods
* and is usable with range-based for
@@ -351,12 +370,6 @@
}
inline shared_ptr<name_tree::Entry>
-NameTree::get(const pit::Entry& pitEntry) const
-{
- return pitEntry.m_nameTreeEntry;
-}
-
-inline shared_ptr<name_tree::Entry>
NameTree::get(const measurements::Entry& measurementsEntry) const
{
return measurementsEntry.m_nameTreeEntry;
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index 959593f..12a21bd 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-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -57,26 +57,28 @@
{
}
-Pit::~Pit()
-{
-}
-
std::pair<shared_ptr<pit::Entry>, bool>
Pit::findOrInsert(const Interest& interest, bool allowInsert)
{
- // first lookup() the Interest Name in the NameTree, which will creates all
- // the intermedia nodes, starting from the shortest prefix.
- shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(interest.getName());
- BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
+ // ensure NameTree entry exists
+ const Name& name = interest.getName();
+ bool isEndWithDigest = name.size() > 0 && name[-1].isImplicitSha256Digest();
+ shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(isEndWithDigest ? name.getPrefix(-1) : name);
+ BOOST_ASSERT(nte != nullptr);
+ size_t nteNameLen = nte->getPrefix().size();
- const std::vector<shared_ptr<pit::Entry>>& pitEntries = nameTreeEntry->getPitEntries();
-
- // then check if this Interest is already in the PIT entries
+ // check if PIT entry already exists
+ const std::vector<shared_ptr<pit::Entry>>& pitEntries = nte->getPitEntries();
auto it = std::find_if(pitEntries.begin(), pitEntries.end(),
- [&interest] (const shared_ptr<pit::Entry>& entry) {
- return entry->getInterest().getName() == interest.getName() &&
- entry->getInterest().getSelectors() == interest.getSelectors();
- });
+ [&interest, nteNameLen] (const shared_ptr<pit::Entry>& entry) -> bool {
+ // initial part of the name is guaranteed to be the same
+ BOOST_ASSERT(entry->getInterest().getName().compare(0, nteNameLen,
+ interest.getName(), 0, nteNameLen) == 0);
+ // compare implicit digest (or its absence) only
+ return entry->getInterest().getName().compare(nteNameLen, Name::npos,
+ interest.getName(), nteNameLen) == 0 &&
+ entry->getInterest().getSelectors() == interest.getSelectors();
+ });
if (it != pitEntries.end()) {
return {*it, false};
}
@@ -85,8 +87,8 @@
return {nullptr, true};
}
- shared_ptr<pit::Entry> entry = make_shared<pit::Entry>(interest);
- nameTreeEntry->insertPitEntry(entry);
+ auto entry = make_shared<pit::Entry>(interest);
+ nte->insertPitEntry(entry);
m_nItems++;
return {entry, true};
}
diff --git a/daemon/table/pit.hpp b/daemon/table/pit.hpp
index adab085..cea528f 100644
--- a/daemon/table/pit.hpp
+++ b/daemon/table/pit.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014-2015, Regents of the University of California,
+ * Copyright (c) 2014-2016, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -51,8 +51,6 @@
explicit
Pit(NameTree& nameTree);
- ~Pit();
-
/** \return number of entries
*/
size_t