fib: implicitly delete empty Entry
Fib::removeNextHopFromAllEntries automatically deletes fib::Entry
if the last nexthop record is being removed.
refs #1341
Change-Id: I36d42fe8f9fc8f03d194f845020aff408cd70488
diff --git a/daemon/table/fib-entry.cpp b/daemon/table/fib-entry.cpp
index 6a9b686..1628d96 100644
--- a/daemon/table/fib-entry.cpp
+++ b/daemon/table/fib-entry.cpp
@@ -42,7 +42,6 @@
it->setCost(cost);
this->sortNextHops();
-
}
void
diff --git a/daemon/table/fib-entry.hpp b/daemon/table/fib-entry.hpp
index aac8fc5..48b09d6 100644
--- a/daemon/table/fib-entry.hpp
+++ b/daemon/table/fib-entry.hpp
@@ -11,6 +11,11 @@
namespace nfd {
+class NameTree;
+namespace name_tree {
+class Entry;
+}
+
namespace fib {
/** \class NextHopList
@@ -37,6 +42,10 @@
const NextHopList&
getNextHops() const;
+ /// whether this Entry has any nexthop
+ bool
+ hasNextHops() const;
+
bool
hasNextHop(shared_ptr<Face> face) const;
@@ -56,6 +65,10 @@
private:
Name m_prefix;
NextHopList m_nextHops;
+
+ shared_ptr<name_tree::Entry> m_nameTreeEntry;
+ friend class nfd::NameTree;
+ friend class nfd::name_tree::Entry;
};
@@ -71,6 +84,12 @@
return m_nextHops;
}
+inline bool
+Entry::hasNextHops() const
+{
+ return !m_nextHops.empty();
+}
+
} // namespace fib
} // namespace nfd
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index eea7641..7397c60 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -37,7 +37,7 @@
return std::make_pair(entry, false);
entry = make_shared<fib::Entry>(prefix);
nameTreeEntry->setFibEntry(entry);
- m_nItems++;
+ ++m_nItems;
return std::make_pair(entry, true);
}
@@ -79,19 +79,32 @@
shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
if (static_cast<bool>(nameTreeEntry))
{
- nameTreeEntry->eraseFibEntry(nameTreeEntry->getFibEntry());
- m_nItems--;
+ nameTreeEntry->setFibEntry(shared_ptr<fib::Entry>());
+ --m_nItems;
+ }
+}
+
+void
+Fib::erase(const fib::Entry& entry)
+{
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(entry);
+ if (static_cast<bool>(nameTreeEntry))
+ {
+ nameTreeEntry->setFibEntry(shared_ptr<fib::Entry>());
+ --m_nItems;
}
}
void
Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
{
- for (NameTree::const_iterator it =
- m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end(); it++)
- {
+ for (NameTree::const_iterator it = m_nameTree.fullEnumerate(
+ &predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end(); ++it) {
shared_ptr<fib::Entry> entry = it->getFibEntry();
entry->removeNextHop(face);
+ if (!entry->hasNextHops()) {
+ this->erase(*entry);
+ }
}
}
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 0399833..5e2e03d 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -66,9 +66,13 @@
size() const;
private:
+ void
+ erase(const fib::Entry& entry);
+
+private:
NameTree& m_nameTree;
size_t m_nItems;
-
+
/** \brief The empty FIB entry.
*
* This entry has no nexthops.
diff --git a/daemon/table/name-tree-entry.cpp b/daemon/table/name-tree-entry.cpp
index 673be47..dd7bf4b 100644
--- a/daemon/table/name-tree-entry.cpp
+++ b/daemon/table/name-tree-entry.cpp
@@ -46,18 +46,15 @@
}
void
-Entry::setFibEntry(shared_ptr<fib::Entry> fib)
+Entry::setFibEntry(shared_ptr<fib::Entry> fibEntry)
{
- m_fibEntry = fib;
-}
-
-bool
-Entry::eraseFibEntry(shared_ptr<fib::Entry> fib)
-{
- if (m_fibEntry != fib)
- return false;
- m_fibEntry.reset();
- return true;
+ if (static_cast<bool>(m_fibEntry)) {
+ m_fibEntry->m_nameTreeEntry.reset();
+ }
+ m_fibEntry = fibEntry;
+ if (static_cast<bool>(m_fibEntry)) {
+ m_fibEntry->m_nameTreeEntry = this->shared_from_this();
+ }
}
void
@@ -102,7 +99,13 @@
void
Entry::setStrategyChoiceEntry(shared_ptr<strategy_choice::Entry> strategyChoiceEntry)
{
+ if (static_cast<bool>(m_strategyChoiceEntry)) {
+ m_strategyChoiceEntry->m_nameTreeEntry.reset();
+ }
m_strategyChoiceEntry = strategyChoiceEntry;
+ if (static_cast<bool>(m_strategyChoiceEntry)) {
+ m_strategyChoiceEntry->m_nameTreeEntry = this->shared_from_this();
+ }
}
} // namespace name_tree
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index cca1908..e3c72f2 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -45,7 +45,7 @@
/**
* \brief Name Tree Entry Class
*/
-class Entry : noncopyable
+class Entry : public enable_shared_from_this<Entry>, noncopyable
{
// Make private members accessible by Name Tree
friend class nfd::NameTree;
@@ -80,14 +80,11 @@
isEmpty() const;
void
- setFibEntry(shared_ptr<fib::Entry> fib);
+ setFibEntry(shared_ptr<fib::Entry> fibEntry);
shared_ptr<fib::Entry>
getFibEntry() const;
- bool
- eraseFibEntry(shared_ptr<fib::Entry> fib);
-
void
insertPitEntry(shared_ptr<pit::Entry> pit);
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 5d11c27..430ed3c 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -498,8 +498,10 @@
}
// process other buckets
- int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
- for (newLocation = newLocation; newLocation < m_nameTree.m_nBuckets; newLocation++)
+
+ for (int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
+ newLocation < static_cast<int>(m_nameTree.m_nBuckets);
+ ++newLocation)
{
// process each bucket
name_tree::Node* node = m_nameTree.m_buckets[newLocation];
@@ -637,6 +639,9 @@
m_entry = m_nameTree.m_end;
return *this;
}
+
+ BOOST_ASSERT(false); // unknown type
+ return *this;
}
} // namespace nfd
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 1a30b2b..3d0de70 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -100,6 +100,9 @@
shared_ptr<name_tree::Entry>
findExactMatch(const Name& prefix) const;
+ shared_ptr<name_tree::Entry>
+ findExactMatch(const fib::Entry& fibEntry) const;
+
/**
* \brief Erase a Name Tree Entry if this entry is empty.
* \details If a Name Tree Entry contains no Children, no FIB, no PIT, and
@@ -143,7 +146,8 @@
*/
const_iterator
partialEnumerate(const Name& prefix,
- const name_tree::EntrySubTreeSelector& entrySubTreeSelector = name_tree::AnyEntrySubTree()) const;
+ const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
+ name_tree::AnyEntrySubTree()) const;
/**
* \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
@@ -203,13 +207,13 @@
operator!=(const const_iterator& other) const;
private:
- bool m_shouldVisitChildren;
const NameTree& m_nameTree;
shared_ptr<name_tree::Entry> m_entry;
shared_ptr<name_tree::Entry> m_subTreeRoot;
shared_ptr<name_tree::EntrySelector> m_entrySelector;
shared_ptr<name_tree::EntrySubTreeSelector> m_entrySubTreeSelector;
NameTree::IteratorType m_type;
+ bool m_shouldVisitChildren;
};
private:
@@ -250,6 +254,12 @@
return m_nBuckets;
}
+inline shared_ptr<name_tree::Entry>
+NameTree::findExactMatch(const fib::Entry& fibEntry) const
+{
+ return fibEntry.m_nameTreeEntry;
+}
+
inline NameTree::const_iterator
NameTree::begin() const
{
diff --git a/tests/table/fib.cpp b/tests/table/fib.cpp
index 4d9d05f..cc80bba 100644
--- a/tests/table/fib.cpp
+++ b/tests/table/fib.cpp
@@ -19,21 +19,21 @@
Name prefix("ndn:/pxWhfFza");
shared_ptr<Face> face1 = make_shared<DummyFace>();
shared_ptr<Face> face2 = make_shared<DummyFace>();
-
+
fib::Entry entry(prefix);
- BOOST_CHECK(entry.getPrefix().equals(prefix));
-
+ BOOST_CHECK_EQUAL(entry.getPrefix(), prefix);
+
const fib::NextHopList& nexthops1 = entry.getNextHops();
// []
BOOST_CHECK_EQUAL(nexthops1.size(), 0);
-
+
entry.addNextHop(face1, 20);
const fib::NextHopList& nexthops2 = entry.getNextHops();
// [(face1,20)]
BOOST_CHECK_EQUAL(nexthops2.size(), 1);
BOOST_CHECK_EQUAL(nexthops2.begin()->getFace(), face1);
BOOST_CHECK_EQUAL(nexthops2.begin()->getCost(), 20);
-
+
entry.addNextHop(face1, 30);
const fib::NextHopList& nexthops3 = entry.getNextHops();
// [(face1,30)]
@@ -80,26 +80,26 @@
break;
}
}
-
+
entry.removeNextHop(face1);
const fib::NextHopList& nexthops6 = entry.getNextHops();
// [(face2,10)]
BOOST_CHECK_EQUAL(nexthops6.size(), 1);
BOOST_CHECK_EQUAL(nexthops6.begin()->getFace(), face2);
BOOST_CHECK_EQUAL(nexthops6.begin()->getCost(), 10);
-
+
entry.removeNextHop(face1);
const fib::NextHopList& nexthops7 = entry.getNextHops();
// [(face2,10)]
BOOST_CHECK_EQUAL(nexthops7.size(), 1);
BOOST_CHECK_EQUAL(nexthops7.begin()->getFace(), face2);
BOOST_CHECK_EQUAL(nexthops7.begin()->getCost(), 10);
-
+
entry.removeNextHop(face2);
const fib::NextHopList& nexthops8 = entry.getNextHops();
// []
BOOST_CHECK_EQUAL(nexthops8.size(), 0);
-
+
entry.removeNextHop(face2);
const fib::NextHopList& nexthops9 = entry.getNextHops();
// []
@@ -114,61 +114,66 @@
Name nameABC ("ndn:/A/B/C");
Name nameABCD("ndn:/A/B/C/D");
Name nameE ("ndn:/E");
-
+
std::pair<shared_ptr<fib::Entry>, bool> insertRes;
shared_ptr<fib::Entry> entry;
NameTree nameTree(1024);
Fib fib(nameTree);
// []
+ BOOST_CHECK_EQUAL(fib.size(), 0);
entry = fib.findLongestPrefixMatch(nameA);
BOOST_REQUIRE(static_cast<bool>(entry)); // the empty entry
-
+
insertRes = fib.insert(nameEmpty);
BOOST_CHECK_EQUAL(insertRes.second, true);
BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameEmpty);
// ['/']
-
+ BOOST_CHECK_EQUAL(fib.size(), 1);
+
entry = fib.findLongestPrefixMatch(nameA);
BOOST_REQUIRE(static_cast<bool>(entry));
BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
-
+
insertRes = fib.insert(nameA);
BOOST_CHECK_EQUAL(insertRes.second, true);
BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
// ['/', '/A']
-
+ BOOST_CHECK_EQUAL(fib.size(), 2);
+
insertRes = fib.insert(nameA);
BOOST_CHECK_EQUAL(insertRes.second, false);
BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
// ['/', '/A']
+ BOOST_CHECK_EQUAL(fib.size(), 2);
entry = fib.findLongestPrefixMatch(nameA);
BOOST_REQUIRE(static_cast<bool>(entry));
BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
-
+
entry = fib.findLongestPrefixMatch(nameABCD);
BOOST_REQUIRE(static_cast<bool>(entry));
BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
-
+
insertRes = fib.insert(nameABC);
BOOST_CHECK_EQUAL(insertRes.second, true);
BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameABC);
// ['/', '/A', '/A/B/C']
+ BOOST_CHECK_EQUAL(fib.size(), 3);
entry = fib.findLongestPrefixMatch(nameA);
BOOST_REQUIRE(static_cast<bool>(entry));
BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
-
+
entry = fib.findLongestPrefixMatch(nameAB);
BOOST_REQUIRE(static_cast<bool>(entry));
BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
-
+
entry = fib.findLongestPrefixMatch(nameABCD);
BOOST_REQUIRE(static_cast<bool>(entry));
BOOST_CHECK_EQUAL(entry->getPrefix(), nameABC);
-
+
entry = fib.findLongestPrefixMatch(nameE);
BOOST_REQUIRE(static_cast<bool>(entry));
BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
@@ -178,38 +183,39 @@
{
shared_ptr<Face> face1 = make_shared<DummyFace>();
shared_ptr<Face> face2 = make_shared<DummyFace>();
+ Name nameEmpty("ndn:/");
Name nameA("ndn:/A");
Name nameB("ndn:/B");
-
+
std::pair<shared_ptr<fib::Entry>, bool> insertRes;
shared_ptr<fib::Entry> entry;
-
+
NameTree nameTree(1024);
Fib fib(nameTree);
- // {'/':[]}
-
+ // {}
+
insertRes = fib.insert(nameA);
insertRes.first->addNextHop(face1, 0);
insertRes.first->addNextHop(face2, 0);
- // {'/':[], '/A':[1,2]}
+ // {'/A':[1,2]}
insertRes = fib.insert(nameB);
insertRes.first->addNextHop(face1, 0);
- // {'/':[], '/A':[1,2], '/B':[1]}
-
+ // {'/A':[1,2], '/B':[1]}
+ BOOST_CHECK_EQUAL(fib.size(), 2);
+
fib.removeNextHopFromAllEntries(face1);
- // {'/':[], '/A':[2], '/B':[]}
-
+ // {'/A':[2]}
+ BOOST_CHECK_EQUAL(fib.size(), 1);
+
entry = fib.findLongestPrefixMatch(nameA);
BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
const fib::NextHopList& nexthopsA = entry->getNextHops();
BOOST_CHECK_EQUAL(nexthopsA.size(), 1);
BOOST_CHECK_EQUAL(nexthopsA.begin()->getFace(), face2);
-
+
entry = fib.findLongestPrefixMatch(nameB);
- BOOST_CHECK_EQUAL(entry->getPrefix(), nameB);
- const fib::NextHopList& nexthopsB = entry->getNextHops();
- BOOST_CHECK_EQUAL(nexthopsB.size(), 0);
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
}
void
diff --git a/tests/table/name-tree.cpp b/tests/table/name-tree.cpp
index e44c401..d03f4af 100644
--- a/tests/table/name-tree.cpp
+++ b/tests/table/name-tree.cpp
@@ -18,53 +18,46 @@
{
Name prefix("ndn:/named-data/research/abc/def/ghi");
- name_tree::Entry npe(prefix);
- BOOST_CHECK_EQUAL(npe.getPrefix(), prefix);
+ shared_ptr<name_tree::Entry> npe = make_shared<name_tree::Entry>(prefix);
+ BOOST_CHECK_EQUAL(npe->getPrefix(), prefix);
// examine all the get methods
- uint32_t hash = npe.getHash();
+ uint32_t hash = npe->getHash();
BOOST_CHECK_EQUAL(hash, 0);
- shared_ptr<name_tree::Entry> parent = npe.getParent();
+ shared_ptr<name_tree::Entry> parent = npe->getParent();
BOOST_CHECK(!static_cast<bool>(parent));
- std::vector<shared_ptr<name_tree::Entry> >& childList = npe.getChildren();
+ std::vector<shared_ptr<name_tree::Entry> >& childList = npe->getChildren();
BOOST_CHECK_EQUAL(childList.size(), 0);
- shared_ptr<fib::Entry> fib = npe.getFibEntry();
+ shared_ptr<fib::Entry> fib = npe->getFibEntry();
BOOST_CHECK(!static_cast<bool>(fib));
- std::vector< shared_ptr<pit::Entry> >& pitList = npe.getPitEntries();
+ std::vector< shared_ptr<pit::Entry> >& pitList = npe->getPitEntries();
BOOST_CHECK_EQUAL(pitList.size(), 0);
// examine all the set method
- npe.setHash(12345);
- BOOST_CHECK_EQUAL(npe.getHash(), 12345);
+ npe->setHash(12345);
+ BOOST_CHECK_EQUAL(npe->getHash(), 12345);
Name parentName("ndn:/named-data/research/abc/def");
parent = make_shared<name_tree::Entry>(parentName);
- npe.setParent(parent);
- BOOST_CHECK_EQUAL(npe.getParent(), parent);
+ npe->setParent(parent);
+ BOOST_CHECK_EQUAL(npe->getParent(), parent);
// Insert FIB
shared_ptr<fib::Entry> fibEntry(new fib::Entry(prefix));
shared_ptr<fib::Entry> fibEntryParent(new fib::Entry(parentName));
- npe.setFibEntry(fibEntry);
- BOOST_CHECK_EQUAL(npe.getFibEntry(), fibEntry);
+ npe->setFibEntry(fibEntry);
+ BOOST_CHECK_EQUAL(npe->getFibEntry(), fibEntry);
- // Erase a FIB that does not exist
- BOOST_CHECK_EQUAL(npe.
- eraseFibEntry(fibEntryParent), false);
- BOOST_CHECK_EQUAL(npe.getFibEntry(), fibEntry);
-
- // Erase the FIB that exists
- BOOST_CHECK_EQUAL(npe.
- eraseFibEntry(fibEntry), true);
- BOOST_CHECK(!static_cast<bool>(npe.getFibEntry()));
+ npe->setFibEntry(shared_ptr<fib::Entry>());
+ BOOST_CHECK(!static_cast<bool>(npe->getFibEntry()));
// Insert a PIT
@@ -74,29 +67,29 @@
Name prefix3("ndn:/named-data/research/abc/def");
shared_ptr<pit::Entry> PitEntry3(make_shared<pit::Entry>(prefix3));
- npe.insertPitEntry(PitEntry);
- BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
+ npe->insertPitEntry(PitEntry);
+ BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
- npe.insertPitEntry(PitEntry2);
- BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 2);
+ npe->insertPitEntry(PitEntry2);
+ BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 2);
- BOOST_CHECK_EQUAL(npe.
+ BOOST_CHECK_EQUAL(npe->
erasePitEntry(PitEntry), true);
- BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
+ BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
// erase a PIT Entry that does not exist
- BOOST_CHECK_EQUAL(npe.
+ BOOST_CHECK_EQUAL(npe->
erasePitEntry(PitEntry3), false);
- BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
+ BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
- BOOST_CHECK_EQUAL(npe.
+ BOOST_CHECK_EQUAL(npe->
erasePitEntry(PitEntry2), true);
- BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 0);
+ BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 0);
// erase a PIT Entry that does not exist any more
- BOOST_CHECK_EQUAL(npe.
+ BOOST_CHECK_EQUAL(npe->
erasePitEntry(PitEntry2), false);
}