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