table: NameTree findExactMatch, findLongestPrefixMatch return Entry*
refs #3687
Change-Id: I32752fd711b9641228fbb7f356e72144780cf9ec
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index d18ce94..388cd25 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -47,27 +47,22 @@
BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Fib::const_iterator>));
#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
+static inline bool
+nteHasFibEntry(const name_tree::Entry& nte)
+{
+ return nte.getFibEntry() != nullptr;
+}
+
Fib::Fib(NameTree& nameTree)
: m_nameTree(nameTree)
, m_nItems(0)
{
}
-Fib::~Fib()
-{
-}
-
-static inline bool
-predicate_NameTreeEntry_hasFibEntry(const name_tree::Entry& nte)
-{
- return nte.getFibEntry() != nullptr;
-}
-
const Entry&
Fib::findLongestPrefixMatch(const Name& prefix) const
{
- shared_ptr<name_tree::Entry> nte =
- m_nameTree.findLongestPrefixMatch(prefix, &predicate_NameTreeEntry_hasFibEntry);
+ name_tree::Entry* nte = m_nameTree.findLongestPrefixMatch(prefix, &nteHasFibEntry);
if (nte != nullptr) {
return *nte->getFibEntry();
}
@@ -75,13 +70,13 @@
}
const Entry&
-Fib::findLongestPrefixMatch(shared_ptr<name_tree::Entry> nte) const
+Fib::findLongestPrefixMatch(const name_tree::Entry* nte) const
{
Entry* entry = nte->getFibEntry();
if (entry != nullptr)
return *entry;
- nte = m_nameTree.findLongestPrefixMatch(nte, &predicate_NameTreeEntry_hasFibEntry);
+ nte = m_nameTree.findLongestPrefixMatch(*nte, &nteHasFibEntry);
if (nte != nullptr) {
return *nte->getFibEntry();
}
@@ -92,7 +87,7 @@
const Entry&
Fib::findLongestPrefixMatch(const pit::Entry& pitEntry) const
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.findLongestPrefixMatch(pitEntry);
+ name_tree::Entry* nte = m_nameTree.findLongestPrefixMatch(pitEntry);
BOOST_ASSERT(nte != nullptr);
return findLongestPrefixMatch(nte);
}
@@ -100,7 +95,7 @@
const Entry&
Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(measurementsEntry);
+ name_tree::Entry* nte = m_nameTree.lookup(measurementsEntry).get();
BOOST_ASSERT(nte != nullptr);
return findLongestPrefixMatch(nte);
}
@@ -108,7 +103,7 @@
Entry*
Fib::findExactMatch(const Name& prefix)
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.findExactMatch(prefix);
+ name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
if (nte != nullptr)
return nte->getFibEntry();
@@ -130,13 +125,13 @@
}
void
-Fib::erase(shared_ptr<name_tree::Entry> nte, bool canDeleteNte)
+Fib::erase(name_tree::Entry* nte, bool canDeleteNte)
{
BOOST_ASSERT(nte != nullptr);
nte->setFibEntry(nullptr);
if (canDeleteNte) {
- m_nameTree.eraseIfEmpty(nte.get());
+ m_nameTree.eraseIfEmpty(nte);
}
--m_nItems;
}
@@ -144,7 +139,7 @@
void
Fib::erase(const Name& prefix)
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.findExactMatch(prefix);
+ name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
if (nte != nullptr) {
this->erase(nte);
}
@@ -156,7 +151,7 @@
shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
if (nte != nullptr) {
// don't try to erase s_emptyEntry
- this->erase(nte);
+ this->erase(nte.get());
}
}
@@ -167,14 +162,14 @@
if (!entry.hasNextHops()) {
shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(entry);
- this->erase(nte, false);
+ this->erase(nte.get(), false);
}
}
Fib::const_iterator
Fib::begin() const
{
- return const_iterator(m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry).begin());
+ return const_iterator(m_nameTree.fullEnumerate(&nteHasFibEntry).begin());
}
} // namespace fib
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index df2bfeb..950f238 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -48,8 +48,6 @@
explicit
Fib(NameTree& nameTree);
- ~Fib();
-
size_t
size() const;
@@ -150,10 +148,10 @@
private:
const Entry&
- findLongestPrefixMatch(shared_ptr<name_tree::Entry> nte) const;
+ findLongestPrefixMatch(const name_tree::Entry* nte) const;
void
- erase(shared_ptr<name_tree::Entry> nte, bool canDeleteNte = true);
+ erase(name_tree::Entry* nte, bool canDeleteNte = true);
private:
NameTree& m_nameTree;
diff --git a/daemon/table/measurements.cpp b/daemon/table/measurements.cpp
index d93cc91..922c9cd 100644
--- a/daemon/table/measurements.cpp
+++ b/daemon/table/measurements.cpp
@@ -101,14 +101,13 @@
template<typename K>
Entry*
-Measurements::findLongestPrefixMatchImpl(const K& key,
- const EntryPredicate& pred) const
+Measurements::findLongestPrefixMatchImpl(const K& key, const EntryPredicate& pred) const
{
- shared_ptr<name_tree::Entry> match = m_nameTree.findLongestPrefixMatch(key,
- [&pred] (const name_tree::Entry& nte) -> bool {
- Entry* entry = nte.getMeasurementsEntry();
- return entry != nullptr && pred(*entry);
- });
+ name_tree::Entry* match = m_nameTree.findLongestPrefixMatch(key,
+ [&pred] (const name_tree::Entry& nte) {
+ const Entry* entry = nte.getMeasurementsEntry();
+ return entry != nullptr && pred(*entry);
+ });
if (match != nullptr) {
return match->getMeasurementsEntry();
}
@@ -116,19 +115,17 @@
}
Entry*
-Measurements::findLongestPrefixMatch(const Name& name,
- const EntryPredicate& pred) const
+Measurements::findLongestPrefixMatch(const Name& name, const EntryPredicate& pred) const
{
return this->findLongestPrefixMatchImpl(name, pred);
}
Entry*
-Measurements::findLongestPrefixMatch(const pit::Entry& pitEntry,
- const EntryPredicate& pred) const
+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(*nte, pred);
}
Entry*
diff --git a/daemon/table/measurements.hpp b/daemon/table/measurements.hpp
index cf9783d..6942124 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 shared_ptr<name_tree::Entry>
+ /** \tparam K Name or name_tree::Entry
*/
template<typename K>
Entry*
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 993a58a..9056b8a 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -125,15 +125,14 @@
return nErased;
}
-shared_ptr<Entry>
+Entry*
NameTree::findExactMatch(const Name& name) const
{
const Node* node = m_ht.find(name, name.size());
- return node == nullptr ? nullptr : node->entry;
+ return node == nullptr ? nullptr : node->entry.get();
}
-// Longest Prefix Match
-shared_ptr<Entry>
+Entry*
NameTree::findLongestPrefixMatch(const Name& name, const EntrySelector& entrySelector) const
{
HashSequence hashes = computeHashes(name);
@@ -141,40 +140,41 @@
for (ssize_t prefixLen = name.size(); prefixLen >= 0; --prefixLen) {
const Node* node = m_ht.find(name, prefixLen, hashes);
if (node != nullptr && entrySelector(*node->entry)) {
- return node->entry;
+ return node->entry.get();
}
}
return nullptr;
}
-shared_ptr<Entry>
-NameTree::findLongestPrefixMatch(shared_ptr<Entry> entry1,
- const EntrySelector& entrySelector) const
+Entry*
+NameTree::findLongestPrefixMatch(const Entry& entry1, const EntrySelector& entrySelector) const
{
- Entry* entry = entry1.get();
+ Entry* entry = const_cast<Entry*>(&entry1);
while (entry != nullptr) {
if (entrySelector(*entry)) {
- return entry->shared_from_this();
+ return entry;
}
entry = entry->getParent();
}
return nullptr;
}
-shared_ptr<Entry>
+Entry*
NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry) const
{
shared_ptr<Entry> nte = this->getEntry(pitEntry);
BOOST_ASSERT(nte != nullptr);
if (nte->getName().size() == pitEntry.getName().size()) {
- return nte;
+ return nte.get();
}
+ // 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));
- shared_ptr<Entry> exact = this->findExactMatch(pitEntry.getName());
- return exact == nullptr ? nte : exact;
+ Entry* exact = this->findExactMatch(pitEntry.getName());
+ return exact == nullptr ? nte.get() : exact;
}
boost::iterator_range<NameTree::const_iterator>
@@ -188,8 +188,8 @@
// For trie-like design, it could be more efficient by walking down the
// trie from the root node.
- shared_ptr<Entry> entry = findLongestPrefixMatch(name, entrySelector);
- return {Iterator(make_shared<PrefixMatchImpl>(*this, entrySelector), entry.get()), end()};
+ Entry* entry = findLongestPrefixMatch(name, entrySelector);
+ return {Iterator(make_shared<PrefixMatchImpl>(*this, entrySelector), entry), end()};
}
boost::iterator_range<NameTree::const_iterator>
@@ -205,8 +205,8 @@
const EntrySubTreeSelector& entrySubTreeSelector) const
{
// the first step is to process the root node
- shared_ptr<Entry> entry = findExactMatch(prefix);
- return {Iterator(make_shared<PartialEnumerationImpl>(*this, entrySubTreeSelector), entry.get()), end()};
+ Entry* entry = this->findExactMatch(prefix);
+ return {Iterator(make_shared<PartialEnumerationImpl>(*this, entrySubTreeSelector), entry), end()};
}
} // namespace name_tree
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index d630cad..c27dd24 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -117,7 +117,7 @@
/** \brief exact match lookup
* \return entry with \p name, or nullptr if it does not exist
*/
- shared_ptr<Entry>
+ Entry*
findExactMatch(const Name& name) const;
/** \brief longest prefix matching
@@ -125,23 +125,23 @@
* where no other entry with a longer name satisfies those requirements;
* or nullptr if no entry satisfying those requirements exists
*/
- shared_ptr<Entry>
+ Entry*
findLongestPrefixMatch(const Name& name,
const EntrySelector& entrySelector = AnyEntry()) const;
- /** \brief equivalent to .findLongestPrefixMatch(entry->getName(), entrySelector)
+ /** \brief equivalent to .findLongestPrefixMatch(entry.getName(), entrySelector)
* \note This overload is more efficient than .findLongestPrefixMatch(const Name&)
* in common cases.
*/
- shared_ptr<Entry>
- findLongestPrefixMatch(shared_ptr<Entry> entry,
+ 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.
*/
- shared_ptr<Entry>
+ Entry*
findLongestPrefixMatch(const pit::Entry& pitEntry) const;
/** \brief all-prefixes match lookup
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index de6c9da..06dab3e 100644
--- a/daemon/table/pit.cpp
+++ b/daemon/table/pit.cpp
@@ -66,9 +66,9 @@
const Name& nteName = isEndWithDigest ? name.getPrefix(-1) : name;
// ensure NameTree entry exists
- shared_ptr<name_tree::Entry> nte;
+ name_tree::Entry* nte = nullptr;
if (allowInsert) {
- nte = m_nameTree.lookup(nteName);
+ nte = m_nameTree.lookup(nteName).get();
BOOST_ASSERT(nte != nullptr);
}
else {
diff --git a/daemon/table/strategy-choice.cpp b/daemon/table/strategy-choice.cpp
index a8b32d7..387216c 100644
--- a/daemon/table/strategy-choice.cpp
+++ b/daemon/table/strategy-choice.cpp
@@ -36,6 +36,12 @@
NFD_LOG_INIT("StrategyChoice");
+static inline bool
+nteHasStrategyChoiceEntry(const name_tree::Entry& nte)
+{
+ return nte.getStrategyChoiceEntry() != nullptr;
+}
+
StrategyChoice::StrategyChoice(NameTree& nameTree, unique_ptr<Strategy> defaultStrategy)
: m_nameTree(nameTree)
, m_nItems(0)
@@ -129,7 +135,7 @@
{
BOOST_ASSERT(prefix.size() > 0);
- shared_ptr<name_tree::Entry> nte = m_nameTree.findExactMatch(prefix);
+ name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
if (nte == nullptr) {
return;
}
@@ -145,14 +151,14 @@
this->changeStrategy(*entry, oldStrategy, parentStrategy);
nte->setStrategyChoiceEntry(nullptr);
- m_nameTree.eraseIfEmpty(nte.get());
+ m_nameTree.eraseIfEmpty(nte);
--m_nItems;
}
std::pair<bool, Name>
StrategyChoice::get(const Name& prefix) const
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.findExactMatch(prefix);
+ name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
if (nte == nullptr) {
return {false, Name()};
}
@@ -168,23 +174,19 @@
Strategy&
StrategyChoice::findEffectiveStrategy(const Name& prefix) const
{
- shared_ptr<name_tree::Entry> nte = m_nameTree.findLongestPrefixMatch(prefix,
- [] (const name_tree::Entry& entry) { return entry.getStrategyChoiceEntry() != nullptr; });
-
+ name_tree::Entry* nte = m_nameTree.findLongestPrefixMatch(prefix, &nteHasStrategyChoiceEntry);
BOOST_ASSERT(nte != nullptr);
return nte->getStrategyChoiceEntry()->getStrategy();
}
Strategy&
-StrategyChoice::findEffectiveStrategy(shared_ptr<name_tree::Entry> nte) const
+StrategyChoice::findEffectiveStrategy(const name_tree::Entry* nte) const
{
Entry* entry = nte->getStrategyChoiceEntry();
if (entry != nullptr)
return entry->getStrategy();
- nte = m_nameTree.findLongestPrefixMatch(nte,
- [] (const name_tree::Entry& entry) { return entry.getStrategyChoiceEntry() != nullptr; });
-
+ nte = m_nameTree.findLongestPrefixMatch(*nte, &nteHasStrategyChoiceEntry);
BOOST_ASSERT(nte != nullptr);
return nte->getStrategyChoiceEntry()->getStrategy();
}
@@ -194,8 +196,7 @@
{
shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(pitEntry);
BOOST_ASSERT(nte != nullptr);
-
- return this->findEffectiveStrategy(nte);
+ return this->findEffectiveStrategy(nte.get());
}
Strategy&
@@ -203,8 +204,7 @@
{
shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(measurementsEntry);
BOOST_ASSERT(nte != nullptr);
-
- return this->findEffectiveStrategy(nte);
+ return this->findEffectiveStrategy(nte.get());
}
void
@@ -277,11 +277,7 @@
StrategyChoice::const_iterator
StrategyChoice::begin() const
{
- auto&& enumerable = m_nameTree.fullEnumerate(
- [] (const name_tree::Entry& entry) {
- return entry.getStrategyChoiceEntry() != nullptr;
- });
- return const_iterator(enumerable.begin());
+ return const_iterator(m_nameTree.fullEnumerate(&nteHasStrategyChoiceEntry).begin());
}
} // namespace strategy_choice
diff --git a/daemon/table/strategy-choice.hpp b/daemon/table/strategy-choice.hpp
index 84b1b03..a238761 100644
--- a/daemon/table/strategy-choice.hpp
+++ b/daemon/table/strategy-choice.hpp
@@ -167,7 +167,7 @@
fw::Strategy& newStrategy);
fw::Strategy&
- findEffectiveStrategy(shared_ptr<name_tree::Entry> nte) const;
+ findEffectiveStrategy(const name_tree::Entry* nte) const;
private:
NameTree& m_nameTree;
diff --git a/tests/daemon/table/name-tree.t.cpp b/tests/daemon/table/name-tree.t.cpp
index 4c030ac..b5d37d0 100644
--- a/tests/daemon/table/name-tree.t.cpp
+++ b/tests/daemon/table/name-tree.t.cpp
@@ -263,24 +263,24 @@
// validate lookup() and findExactMatch()
- Name nameAB ("/a/b");
- BOOST_CHECK_EQUAL(npeABC->getParent(), nt.findExactMatch(nameAB).get());
- BOOST_CHECK_EQUAL(npeABD->getParent(), nt.findExactMatch(nameAB).get());
+ Name nameAB("/a/b");
+ BOOST_CHECK_EQUAL(npeABC->getParent(), nt.findExactMatch(nameAB));
+ BOOST_CHECK_EQUAL(npeABD->getParent(), nt.findExactMatch(nameAB));
Name nameA ("/a");
- BOOST_CHECK_EQUAL(npeAE->getParent(), nt.findExactMatch(nameA).get());
+ BOOST_CHECK_EQUAL(npeAE->getParent(), nt.findExactMatch(nameA));
Name nameRoot ("/");
- BOOST_CHECK_EQUAL(npeF->getParent(), nt.findExactMatch(nameRoot).get());
+ BOOST_CHECK_EQUAL(npeF->getParent(), nt.findExactMatch(nameRoot));
BOOST_CHECK_EQUAL(nt.size(), 7);
Name name0("/does/not/exist");
- shared_ptr<Entry> npe0 = nt.findExactMatch(name0);
+ Entry* npe0 = nt.findExactMatch(name0);
BOOST_CHECK(npe0 == nullptr);
// Longest Prefix Matching
- shared_ptr<Entry> temp;
+ Entry* temp = nullptr;
Name nameABCLPM("/a/b/c/def/asdf/nlf");
temp = nt.findLongestPrefixMatch(nameABCLPM);
BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABC));
@@ -312,7 +312,7 @@
bool eraseResult = false;
temp = nt.findExactMatch(nameABC);
if (temp != nullptr)
- eraseResult = nt.eraseIfEmpty(temp.get());
+ eraseResult = nt.eraseIfEmpty(temp);
BOOST_CHECK_EQUAL(nt.size(), 6);
BOOST_CHECK(nt.findExactMatch(nameABC) == nullptr);
BOOST_CHECK_EQUAL(eraseResult, true);
@@ -320,7 +320,7 @@
eraseResult = false;
temp = nt.findExactMatch(nameABCLPM);
if (temp != nullptr)
- eraseResult = nt.eraseIfEmpty(temp.get());
+ eraseResult = nt.eraseIfEmpty(temp);
BOOST_CHECK(temp == nullptr);
BOOST_CHECK_EQUAL(nt.size(), 6);
BOOST_CHECK_EQUAL(eraseResult, false);
@@ -331,7 +331,7 @@
eraseResult = false;
temp = nt.findExactMatch(nameABC);
if (temp != nullptr)
- eraseResult = nt.eraseIfEmpty(temp.get());
+ eraseResult = nt.eraseIfEmpty(temp);
BOOST_CHECK_EQUAL(nt.size(), 6);
BOOST_CHECK_EQUAL(eraseResult, true);
BOOST_CHECK(nt.findExactMatch(nameABC) == nullptr);
@@ -349,14 +349,14 @@
// try to erase /a/b/c, should return false
temp = nt.findExactMatch(nameABC);
BOOST_CHECK_EQUAL(temp->getName(), nameABC);
- eraseResult = nt.eraseIfEmpty(temp.get());
+ eraseResult = nt.eraseIfEmpty(temp);
BOOST_CHECK_EQUAL(eraseResult, false);
temp = nt.findExactMatch(nameABC);
BOOST_CHECK_EQUAL(temp->getName(), nameABC);
temp = nt.findExactMatch(nameABD);
if (temp != nullptr)
- nt.eraseIfEmpty(temp.get());
+ nt.eraseIfEmpty(temp);
BOOST_CHECK_EQUAL(nt.size(), 8);
}
@@ -587,7 +587,7 @@
nt.lookup("/F");
auto&& enumerable = nt.partialEnumerate("/A",
- [] (const Entry& entry) -> std::pair<bool, bool> {
+ [] (const Entry& entry) {
bool visitEntry = false;
bool visitChildren = false;
@@ -601,7 +601,7 @@
visitChildren = true;
}
- return {visitEntry, visitChildren};
+ return std::make_pair(visitEntry, visitChildren);
});
EnumerationVerifier(enumerable)
@@ -688,7 +688,7 @@
for (NameTree::const_iterator it = nt.begin(); it != nt.end(); ++it) {
BOOST_CHECK(seenNames.insert(it->getName()).second);
if (it->getName() == nameD) {
- nt.eraseIfEmpty(nt.findExactMatch("/A/F/G").get()); // /A/F/G and /A/F are erased
+ nt.eraseIfEmpty(nt.findExactMatch("/A/F/G")); // /A/F/G and /A/F are erased
}
}