table: ensure NameTree::lookup(tableEntry) does not return nullptr
NameTree::lookup(tableEntry) is always equivalent to NameTree::lookup(Name).
NameTree::getEntry(tableEntry) should be used when inserting new name tree entry is undesired.
refs #3687
Change-Id: I0b17cd07dde83341976cfe66c85855dfb2fa6e89
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 388cd25..7cbcad8 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -70,15 +70,15 @@
}
const Entry&
-Fib::findLongestPrefixMatch(const name_tree::Entry* nte) const
+Fib::findLongestPrefixMatch(const name_tree::Entry& nte) const
{
- Entry* entry = nte->getFibEntry();
+ Entry* entry = nte.getFibEntry();
if (entry != nullptr)
return *entry;
- nte = m_nameTree.findLongestPrefixMatch(*nte, &nteHasFibEntry);
- if (nte != nullptr) {
- return *nte->getFibEntry();
+ const name_tree::Entry* nte2 = m_nameTree.findLongestPrefixMatch(nte, &nteHasFibEntry);
+ if (nte2 != nullptr) {
+ return *nte2->getFibEntry();
}
return *s_emptyEntry;
@@ -89,15 +89,15 @@
{
name_tree::Entry* nte = m_nameTree.findLongestPrefixMatch(pitEntry);
BOOST_ASSERT(nte != nullptr);
- return findLongestPrefixMatch(nte);
+ return findLongestPrefixMatch(*nte);
}
const Entry&
Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
{
- name_tree::Entry* nte = m_nameTree.lookup(measurementsEntry).get();
+ name_tree::Entry* nte = m_nameTree.getEntry(measurementsEntry).get();
BOOST_ASSERT(nte != nullptr);
- return findLongestPrefixMatch(nte);
+ return findLongestPrefixMatch(*nte);
}
Entry*
@@ -148,7 +148,7 @@
void
Fib::erase(const Entry& entry)
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
+ shared_ptr<name_tree::Entry> nte = m_nameTree.getEntry(entry);
if (nte != nullptr) {
// don't try to erase s_emptyEntry
this->erase(nte.get());
@@ -161,7 +161,7 @@
entry.removeNextHop(face);
if (!entry.hasNextHops()) {
- shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
+ shared_ptr<name_tree::Entry> nte = m_nameTree.getEntry(entry);
this->erase(nte.get(), false);
}
}
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 950f238..0a44166 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -148,7 +148,7 @@
private:
const Entry&
- findLongestPrefixMatch(const name_tree::Entry* nte) const;
+ findLongestPrefixMatch(const name_tree::Entry& nte) const;
void
erase(name_tree::Entry* nte, bool canDeleteNte = true);
diff --git a/daemon/table/measurements.cpp b/daemon/table/measurements.cpp
index 922c9cd..b2e8637 100644
--- a/daemon/table/measurements.cpp
+++ b/daemon/table/measurements.cpp
@@ -68,12 +68,6 @@
Measurements::get(const fib::Entry& fibEntry)
{
shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(fibEntry);
- if (nte == nullptr) {
- // must be Fib::s_emptyEntry that is unattached
- BOOST_ASSERT(fibEntry.getPrefix().empty());
- nte = m_nameTree.lookup(fibEntry.getPrefix());
- }
-
BOOST_ASSERT(nte != nullptr);
return this->get(*nte);
}
@@ -93,7 +87,7 @@
return nullptr;
}
- shared_ptr<name_tree::Entry> nteChild = m_nameTree.lookup(child);
+ shared_ptr<name_tree::Entry> nteChild = m_nameTree.getEntry(child);
name_tree::Entry* nte = nteChild->getParent();
BOOST_ASSERT(nte != nullptr);
return &this->get(*nte);
@@ -123,25 +117,20 @@
Entry*
Measurements::findLongestPrefixMatch(const pit::Entry& pitEntry, const EntryPredicate& pred) const
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(pitEntry);
- BOOST_ASSERT(nte != nullptr);
- return this->findLongestPrefixMatchImpl(*nte, pred);
+ return this->findLongestPrefixMatchImpl(pitEntry, pred);
}
Entry*
Measurements::findExactMatch(const Name& name) const
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(name);
- if (nte != nullptr) {
- return nte->getMeasurementsEntry();
- }
- return nullptr;
+ const name_tree::Entry* nte = m_nameTree.findExactMatch(name);
+ return nte == nullptr ? nullptr : nte->getMeasurementsEntry();
}
void
Measurements::extendLifetime(Entry& entry, const time::nanoseconds& lifetime)
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
+ shared_ptr<name_tree::Entry> nte = m_nameTree.getEntry(entry);
BOOST_ASSERT(nte != nullptr);
time::steady_clock::TimePoint expiry = time::steady_clock::now() + lifetime;
@@ -158,7 +147,7 @@
void
Measurements::cleanup(Entry& entry)
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
+ shared_ptr<name_tree::Entry> nte = m_nameTree.getEntry(entry);
BOOST_ASSERT(nte != nullptr);
nte->setMeasurementsEntry(nullptr);
diff --git a/daemon/table/measurements.hpp b/daemon/table/measurements.hpp
index 6942124..dd593f6 100644
--- a/daemon/table/measurements.hpp
+++ b/daemon/table/measurements.hpp
@@ -136,7 +136,7 @@
Entry&
get(name_tree::Entry& nte);
- /** \tparam K Name or name_tree::Entry
+ /** \tparam K a parameter acceptable by NameTree::findLongestPrefixMatch
*/
template<typename K>
Entry*
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 9056b8a..fa3b558 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -62,10 +62,16 @@
}
shared_ptr<Entry>
-NameTree::lookup(const fib::Entry& fibEntry) const
+NameTree::lookup(const fib::Entry& fibEntry)
{
shared_ptr<Entry> nte = this->getEntry(fibEntry);
- BOOST_ASSERT(nte == nullptr || nte->getFibEntry() == &fibEntry);
+ if (nte == nullptr) {
+ // special case: Fib::s_emptyEntry is unattached
+ BOOST_ASSERT(fibEntry.getPrefix().empty());
+ return this->lookup(fibEntry.getPrefix());
+ }
+
+ BOOST_ASSERT(nte->getFibEntry() == &fibEntry);
return nte;
}
@@ -73,32 +79,41 @@
NameTree::lookup(const pit::Entry& pitEntry)
{
shared_ptr<Entry> nte = this->getEntry(pitEntry);
- if (nte == nullptr) {
- return nullptr;
- }
+ BOOST_ASSERT(nte != nullptr);
+
+ BOOST_ASSERT(std::count_if(nte->getPitEntries().begin(), nte->getPitEntries().end(),
+ [&pitEntry] (const shared_ptr<pit::Entry>& pitEntry1) {
+ return pitEntry1.get() == &pitEntry;
+ }) == 1);
if (nte->getName().size() == pitEntry.getName().size()) {
return nte;
}
+ // 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));
return this->lookup(pitEntry.getName());
}
shared_ptr<Entry>
-NameTree::lookup(const measurements::Entry& measurementsEntry) const
+NameTree::lookup(const measurements::Entry& measurementsEntry)
{
shared_ptr<Entry> nte = this->getEntry(measurementsEntry);
- BOOST_ASSERT(nte == nullptr || nte->getMeasurementsEntry() == &measurementsEntry);
+ BOOST_ASSERT(nte != nullptr);
+
+ BOOST_ASSERT(nte->getMeasurementsEntry() == &measurementsEntry);
return nte;
}
shared_ptr<Entry>
-NameTree::lookup(const strategy_choice::Entry& strategyChoiceEntry) const
+NameTree::lookup(const strategy_choice::Entry& strategyChoiceEntry)
{
shared_ptr<Entry> nte = this->getEntry(strategyChoiceEntry);
- BOOST_ASSERT(nte == nullptr || nte->getStrategyChoiceEntry() == &strategyChoiceEntry);
+ BOOST_ASSERT(nte != nullptr);
+
+ BOOST_ASSERT(nte->getStrategyChoiceEntry() == &strategyChoiceEntry);
return nte;
}
@@ -161,27 +176,28 @@
}
Entry*
-NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry) const
+NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry, const EntrySelector& entrySelector) const
{
- shared_ptr<Entry> nte = this->getEntry(pitEntry);
+ const Entry* nte = this->getEntry(pitEntry).get();
BOOST_ASSERT(nte != nullptr);
- if (nte->getName().size() == pitEntry.getName().size()) {
- return nte.get();
+
+ 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) {
+ nte = exact;
+ }
}
- // 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));
- Entry* exact = this->findExactMatch(pitEntry.getName());
- return exact == nullptr ? nte.get() : exact;
+ return this->findLongestPrefixMatch(*nte, entrySelector);
}
boost::iterator_range<NameTree::const_iterator>
NameTree::findAllMatches(const Name& name, const EntrySelector& entrySelector) const
{
- NFD_LOG_TRACE("NameTree::findAllMatches" << name);
-
// 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.
@@ -195,8 +211,6 @@
boost::iterator_range<NameTree::const_iterator>
NameTree::fullEnumerate(const EntrySelector& entrySelector) const
{
- NFD_LOG_TRACE("fullEnumerate");
-
return {Iterator(make_shared<FullEnumerationImpl>(*this, entrySelector), nullptr), end()};
}
@@ -204,7 +218,6 @@
NameTree::partialEnumerate(const Name& prefix,
const EntrySubTreeSelector& entrySubTreeSelector) const
{
- // the first step is to process the root node
Entry* entry = this->findExactMatch(prefix);
return {Iterator(make_shared<PartialEnumerationImpl>(*this, entrySubTreeSelector), entry), end()};
}
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index c27dd24..b534212 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -58,7 +58,8 @@
return m_ht.getNBuckets();
}
- /** \return entry on which a table entry is attached
+ /** \return name tree entry on which a table entry is attached,
+ * or nullptr if the table entry is detached
*/
template<typename ENTRY>
shared_ptr<Entry>
@@ -78,28 +79,32 @@
lookup(const Name& name);
/** \brief equivalent to .lookup(fibEntry.getPrefix())
+ * \param fibEntry a FIB entry attached to this name tree, or Fib::s_emptyEntry
* \note This overload is more efficient than .lookup(const Name&) in common cases.
*/
shared_ptr<Entry>
- lookup(const fib::Entry& fibEntry) const;
+ lookup(const fib::Entry& fibEntry);
/** \brief equivalent to .lookup(pitEntry.getName()).
+ * \param pitEntry a PIT entry attached to this name tree
* \note This overload is more efficient than .lookup(const Name&) in common cases.
*/
shared_ptr<Entry>
lookup(const pit::Entry& pitEntry);
/** \brief equivalent to .lookup(measurementsEntry.getName())
+ * \param measurementsEntry a Measurements entry attached to this name tree
* \note This overload is more efficient than .lookup(const Name&) in common cases.
*/
shared_ptr<Entry>
- lookup(const measurements::Entry& measurementsEntry) const;
+ lookup(const measurements::Entry& measurementsEntry);
/** \brief equivalent to .lookup(strategyChoiceEntry.getName())
+ * \param strategyChoiceEntry a StrategyChoice entry attached to this name tree
* \note This overload is more efficient than .lookup(const Name&) in common cases.
*/
shared_ptr<Entry>
- lookup(const strategy_choice::Entry& strategyChoiceEntry) const;
+ lookup(const strategy_choice::Entry& strategyChoiceEntry);
/** \brief delete the entry if it is empty
* \param entry a valid entry
@@ -130,19 +135,20 @@
const EntrySelector& entrySelector = AnyEntry()) const;
/** \brief equivalent to .findLongestPrefixMatch(entry.getName(), entrySelector)
- * \note This overload is more efficient than .findLongestPrefixMatch(const Name&)
- * in common cases.
+ * \note This overload is more efficient than
+ * .findLongestPrefixMatch(const Name&, const EntrySelector&) in common cases.
*/
Entry*
findLongestPrefixMatch(const Entry& entry,
const EntrySelector& entrySelector = AnyEntry()) const;
/** \brief equivalent to .findLongestPrefixMatch(pitEntry.getName(), AnyEntry())
- * \note This overload is more efficient than .findLongestPrefixMatch(const Name&)
- * in common cases.
+ * \note This overload is more efficient than
+ * .findLongestPrefixMatch(const Name&, const EntrySelector&) in common cases.
*/
Entry*
- findLongestPrefixMatch(const pit::Entry& pitEntry) const;
+ findLongestPrefixMatch(const pit::Entry& pitEntry,
+ const EntrySelector& entrySelector = AnyEntry()) const;
/** \brief all-prefixes match lookup
* \return an unspecified type that have .begin() and .end() methods
diff --git a/daemon/table/strategy-choice.cpp b/daemon/table/strategy-choice.cpp
index 387216c..59ac463 100644
--- a/daemon/table/strategy-choice.cpp
+++ b/daemon/table/strategy-choice.cpp
@@ -180,31 +180,31 @@
}
Strategy&
-StrategyChoice::findEffectiveStrategy(const name_tree::Entry* nte) const
+StrategyChoice::findEffectiveStrategy(const name_tree::Entry& nte) const
{
- Entry* entry = nte->getStrategyChoiceEntry();
+ Entry* entry = nte.getStrategyChoiceEntry();
if (entry != nullptr)
return entry->getStrategy();
- nte = m_nameTree.findLongestPrefixMatch(*nte, &nteHasStrategyChoiceEntry);
- BOOST_ASSERT(nte != nullptr);
- return nte->getStrategyChoiceEntry()->getStrategy();
+ const name_tree::Entry* nte2 = m_nameTree.findLongestPrefixMatch(nte, &nteHasStrategyChoiceEntry);
+ BOOST_ASSERT(nte2 != nullptr);
+ return nte2->getStrategyChoiceEntry()->getStrategy();
}
Strategy&
StrategyChoice::findEffectiveStrategy(const pit::Entry& pitEntry) const
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(pitEntry);
+ const name_tree::Entry* nte = m_nameTree.findLongestPrefixMatch(pitEntry);
BOOST_ASSERT(nte != nullptr);
- return this->findEffectiveStrategy(nte.get());
+ return this->findEffectiveStrategy(*nte);
}
Strategy&
StrategyChoice::findEffectiveStrategy(const measurements::Entry& measurementsEntry) const
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(measurementsEntry);
+ shared_ptr<name_tree::Entry> nte = m_nameTree.getEntry(measurementsEntry);
BOOST_ASSERT(nte != nullptr);
- return this->findEffectiveStrategy(nte.get());
+ return this->findEffectiveStrategy(*nte);
}
void
@@ -258,7 +258,8 @@
// reset StrategyInfo on a portion of NameTree,
// where entry's effective strategy is covered by the changing StrategyChoice entry
- const name_tree::Entry* rootNte = m_nameTree.lookup(entry).get();
+ const name_tree::Entry* rootNte = m_nameTree.getEntry(entry).get();
+ BOOST_ASSERT(rootNte != nullptr);
auto&& ntChanged = m_nameTree.partialEnumerate(entry.getPrefix(),
[&rootNte] (const name_tree::Entry& nte) -> std::pair<bool, bool> {
if (&nte == rootNte) {
diff --git a/daemon/table/strategy-choice.hpp b/daemon/table/strategy-choice.hpp
index a238761..1388cbb 100644
--- a/daemon/table/strategy-choice.hpp
+++ b/daemon/table/strategy-choice.hpp
@@ -167,7 +167,7 @@
fw::Strategy& newStrategy);
fw::Strategy&
- findEffectiveStrategy(const name_tree::Entry* nte) const;
+ findEffectiveStrategy(const name_tree::Entry& nte) const;
private:
NameTree& m_nameTree;