table: FIB on NameTree
Change-Id:Ie949ad2209ed841af498f45e2d0f365ac905c45d
Refs: #1190
diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index cc40f24..ce22c22 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -17,6 +17,7 @@
Forwarder::Forwarder()
: m_lastFaceId(0)
, m_nameTree(1024) // "1024" could be made as one configurable parameter of the forwarder.
+ , m_fib(m_nameTree)
, m_pit(m_nameTree)
{
m_strategy = make_shared<fw::BestRouteStrategy>(boost::ref(*this));
diff --git a/daemon/fw/forwarder.hpp b/daemon/fw/forwarder.hpp
index 3df2d41..5130c76 100644
--- a/daemon/fw/forwarder.hpp
+++ b/daemon/fw/forwarder.hpp
@@ -117,7 +117,7 @@
private:
FaceId m_lastFaceId;
std::map<FaceId, shared_ptr<Face> > m_faces;
-
+
NameTree m_nameTree;
Fib m_fib;
Pit m_pit;
diff --git a/daemon/mgmt/fib-manager.cpp b/daemon/mgmt/fib-manager.cpp
index 0b20c02..27707d7 100644
--- a/daemon/mgmt/fib-manager.cpp
+++ b/daemon/mgmt/fib-manager.cpp
@@ -179,7 +179,7 @@
NFD_LOG_INFO("delete result: OK"
<< " prefix: " << options.getName());
- m_managedFib.remove(options.getName());
+ m_managedFib.erase(options.getName());
setResponse(response, 200, "Success", options.wireEncode());
}
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 481df77..9c7a611 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -9,55 +9,42 @@
#include "measurements-entry.hpp"
namespace nfd {
-
-Fib::Fib()
+Fib::Fib(NameTree& nameTree)
+ : m_nameTree(nameTree)
+ , m_nItems(0)
{
- std::pair<shared_ptr<fib::Entry>, bool> pair_rootEntry_dummy =
- this->insert(Name());
- m_rootEntry = pair_rootEntry_dummy.first;
+ m_rootEntry = (this->insert(Name())).first;
}
Fib::~Fib()
{
}
-static inline bool
-predicate_FibEntry_eq_Name(const shared_ptr<fib::Entry>& entry,
- const Name& name)
-{
- return entry->getPrefix().equals(name);
-}
-
std::pair<shared_ptr<fib::Entry>, bool>
Fib::insert(const Name& prefix)
{
- std::list<shared_ptr<fib::Entry> >::iterator it = std::find_if(
- m_table.begin(), m_table.end(),
- bind(&predicate_FibEntry_eq_Name, _1, prefix));
- if (it != m_table.end()) return std::make_pair(*it, false);
-
- shared_ptr<fib::Entry> entry = make_shared<fib::Entry>(prefix);
- m_table.push_back(entry);
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(prefix);
+ shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
+ if (static_cast<bool>(entry))
+ return std::make_pair(entry, false);
+ entry = make_shared<fib::Entry>(prefix);
+ nameTreeEntry->setFibEntry(entry);
+ m_nItems++;
return std::make_pair(entry, true);
}
-static inline const shared_ptr<fib::Entry>&
-accumulate_FibEntry_longestPrefixMatch(
- const shared_ptr<fib::Entry>& bestMatch,
- const shared_ptr<fib::Entry>& entry, const Name& name)
-{
- if (!entry->getPrefix().isPrefixOf(name)) return bestMatch;
- if (bestMatch->getPrefix().size() < entry->getPrefix().size()) return entry;
- return bestMatch;
-}
-
shared_ptr<fib::Entry>
Fib::findLongestPrefixMatch(const Name& prefix) const
{
- shared_ptr<fib::Entry> bestMatch =
- std::accumulate(m_table.begin(), m_table.end(), m_rootEntry,
- bind(&accumulate_FibEntry_longestPrefixMatch, _1, _2, prefix));
- return bestMatch;
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findLongestPrefixMatch(prefix);
+ while (static_cast<bool>(nameTreeEntry))
+ {
+ if (static_cast<bool>(nameTreeEntry->getFibEntry()))
+ return nameTreeEntry->getFibEntry();
+ else
+ nameTreeEntry = nameTreeEntry->getParent();
+ }
+ return m_rootEntry;
}
shared_ptr<fib::Entry>
@@ -75,35 +62,34 @@
shared_ptr<fib::Entry>
Fib::findExactMatch(const Name& prefix) const
{
- std::list<shared_ptr<fib::Entry> >::const_iterator it =
- std::find_if(m_table.begin(), m_table.end(),
- bind(&predicate_FibEntry_eq_Name, _1, prefix));
-
- if (it != m_table.end())
- {
- return *it;
- }
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
+ if (static_cast<bool>(nameTreeEntry))
+ return nameTreeEntry->getFibEntry();
return shared_ptr<fib::Entry>();
}
void
-Fib::remove(const Name& prefix)
+Fib::erase(const Name& prefix)
{
- m_table.remove_if(bind(&predicate_FibEntry_eq_Name, _1, prefix));
-}
-
-static inline void
-FibEntry_removeNextHop(shared_ptr<fib::Entry> entry,
- shared_ptr<Face> face)
-{
- entry->removeNextHop(face);
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
+ if (static_cast<bool>(nameTreeEntry))
+ {
+ nameTreeEntry->eraseFibEntry(nameTreeEntry->getFibEntry());
+ m_nItems--;
+ }
}
void
Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
{
- std::for_each(m_table.begin(), m_table.end(),
- bind(&FibEntry_removeNextHop, _1, face));
+ shared_ptr<fib::Entry> entry;
+ shared_ptr<std::vector<shared_ptr<name_tree::Entry > > > res = m_nameTree.fullEnumerate();
+ for (int i = 0; i < res->size(); i++)
+ {
+ entry = (*res)[i]->getFibEntry();
+ if (static_cast<bool>(entry))
+ entry->removeNextHop(face);
+ }
}
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 2661911..166eb1b 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -8,18 +8,25 @@
#define NFD_TABLE_FIB_HPP
#include "fib-entry.hpp"
-#include "pit-entry.hpp"
-#include "measurements-entry.hpp"
+#include "name-tree.hpp"
namespace nfd {
+namespace measurements {
+class Entry;
+}
+namespace pit {
+class Entry;
+}
+
/** \class Fib
* \brief represents the FIB
*/
class Fib : noncopyable
{
public:
- Fib();
+ explicit
+ Fib(NameTree& nameTree);
~Fib();
@@ -46,7 +53,7 @@
findExactMatch(const Name& prefix) const;
void
- remove(const Name& prefix);
+ erase(const Name& prefix);
/** \brief removes the NextHop record for face in all entrites
* This is usually invoked when face goes away.
@@ -55,11 +62,21 @@
void
removeNextHopFromAllEntries(shared_ptr<Face> face);
+ size_t
+ size() const;
+
private:
shared_ptr<fib::Entry> m_rootEntry;
- std::list<shared_ptr<fib::Entry> > m_table;
+ NameTree& m_nameTree;
+ size_t m_nItems; // Number of items being stored
};
+inline size_t
+Fib::size() const
+{
+ return m_nItems;
+}
+
} // namespace nfd
#endif // NFD_TABLE_FIB_HPP
diff --git a/tests/mgmt/fib-manager.cpp b/tests/mgmt/fib-manager.cpp
index 00043d2..9905f8a 100644
--- a/tests/mgmt/fib-manager.cpp
+++ b/tests/mgmt/fib-manager.cpp
@@ -166,7 +166,8 @@
BOOST_AUTO_TEST_CASE(TestFireInterestFilter)
{
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -185,7 +186,8 @@
BOOST_AUTO_TEST_CASE(MalformedCommmand)
{
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -206,7 +208,8 @@
BOOST_AUTO_TEST_CASE(UnsupportedVerb)
{
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -237,7 +240,8 @@
addFace(make_shared<DummyFace>());
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -271,7 +275,8 @@
addFace(make_shared<DummyFace>());
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -305,7 +310,8 @@
addFace(make_shared<DummyFace>());
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -329,7 +335,8 @@
addFace(make_shared<DummyFace>());
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -361,7 +368,8 @@
addFace(make_shared<DummyFace>());
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -403,7 +411,8 @@
addFace(make_shared<DummyFace>());
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -437,7 +446,8 @@
addFace(make_shared<DummyFace>());
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -491,7 +501,8 @@
addFace(make_shared<DummyFace>());
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace,
this, _1),
@@ -566,7 +577,8 @@
BOOST_AUTO_TEST_CASE(Insert)
{
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -664,7 +676,8 @@
BOOST_AUTO_TEST_CASE(Delete)
{
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -758,7 +771,8 @@
addFace(face3);
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -788,7 +802,8 @@
BOOST_AUTO_TEST_CASE(RemoveNoFace)
{
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
@@ -818,7 +833,8 @@
addFace(make_shared<DummyFace>());
shared_ptr<InternalFace> face(make_shared<InternalFace>());
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
FibManager manager(fib,
bind(&FibManagerFixture::getFace, this, _1),
face);
diff --git a/tests/table/fib.cpp b/tests/table/fib.cpp
index 1615876..0be6492 100644
--- a/tests/table/fib.cpp
+++ b/tests/table/fib.cpp
@@ -118,7 +118,8 @@
std::pair<shared_ptr<fib::Entry>, bool> insertRes;
shared_ptr<fib::Entry> entry;
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
// ['/']
entry = fib.findLongestPrefixMatch(nameA);
@@ -175,7 +176,8 @@
std::pair<shared_ptr<fib::Entry>, bool> insertRes;
shared_ptr<fib::Entry> entry;
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
// {'/':[]}
insertRes = fib.insert(nameA);
@@ -228,7 +230,8 @@
BOOST_AUTO_TEST_CASE(FindExactMatch)
{
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
fib.insert("/A");
fib.insert("/A/B");
fib.insert("/A/B/C");
@@ -240,20 +243,22 @@
validateNoExactMatch(fib, "/does/not/exist");
- Fib gapFib;
+ NameTree gapNameTree(1024);
+ Fib gapFib(nameTree);
fib.insert("/X");
fib.insert("/X/Y/Z");
validateNoExactMatch(gapFib, "/X/Y");
- Fib emptyFib;
+ NameTree emptyNameTree(1024);
+ Fib emptyFib(emptyNameTree);
validateNoExactMatch(emptyFib, "/nothing/here");
}
void
validateRemove(Fib& fib, const Name& target)
{
- fib.remove(target);
+ fib.erase(target);
shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
if (static_cast<bool>(entry))
@@ -264,15 +269,17 @@
BOOST_AUTO_TEST_CASE(Remove)
{
- Fib emptyFib;
+ NameTree emptyNameTree(1024);
+ Fib emptyFib(emptyNameTree);
- emptyFib.remove("/does/not/exist"); // crash test
+ emptyFib.erase("/does/not/exist"); // crash test
validateRemove(emptyFib, "/");
- emptyFib.remove("/still/does/not/exist"); // crash test
+ emptyFib.erase("/still/does/not/exist"); // crash test
- Fib fib;
+ NameTree nameTree(1024);
+ Fib fib(nameTree);
fib.insert("/A");
fib.insert("/A/B");
fib.insert("/A/B/C");
@@ -292,11 +299,12 @@
validateRemove(fib, "/A");
validateFindExactMatch(fib, "/");
- Fib gapFib;
+ NameTree gapNameTree(1024);
+ Fib gapFib(gapNameTree);
gapFib.insert("/X");
gapFib.insert("/X/Y/Z");
- gapFib.remove("/X/Y"); //should do nothing
+ gapFib.erase("/X/Y"); //should do nothing
validateFindExactMatch(gapFib, "/X");
validateFindExactMatch(gapFib, "/X/Y/Z");
}