table: added findExactMatch and remove methods to Fib
Added methods required to implement remaining FIB
management commands.
refs: #1223
Change-Id: Idf27a60a19286ab1d5712bbc00cca7f41092807b
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 532ad97..7a3295a 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -35,7 +35,7 @@
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);
return std::make_pair(entry, true);
@@ -54,12 +54,32 @@
shared_ptr<fib::Entry>
Fib::findLongestPrefixMatch(const Name& prefix) const
{
- shared_ptr<fib::Entry> bestMatch =
+ 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<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;
+ }
+ return shared_ptr<fib::Entry>();
+}
+
+void
+Fib::remove(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)
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 53a34c7..22d5222 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -17,20 +17,26 @@
{
public:
Fib();
-
+
~Fib();
-
+
/** \brief inserts a FIB entry for prefix
* If an entry for exact same prefix exists, that entry is returned.
* \return{ the entry, and true for new entry, false for existing entry }
*/
std::pair<shared_ptr<fib::Entry>, bool>
insert(const Name& prefix);
-
+
/// performs a longest prefix match
shared_ptr<fib::Entry>
findLongestPrefixMatch(const Name& prefix) const;
-
+
+ shared_ptr<fib::Entry>
+ findExactMatch(const Name& prefix) const;
+
+ void
+ remove(const Name& prefix);
+
/** \brief removes the NextHop record for face in all entrites
* This is usually invoked when face goes away.
* Removing all NextHops in a FIB entry will not remove the FIB entry.
diff --git a/tests/table/fib.cpp b/tests/table/fib.cpp
index d4dc463..d1fe068 100644
--- a/tests/table/fib.cpp
+++ b/tests/table/fib.cpp
@@ -201,6 +201,105 @@
BOOST_CHECK_EQUAL(nexthopsB.size(), 0);
}
+void
+validateFindExactMatch(const Fib& fib, const Name& target)
+{
+ shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
+ if (static_cast<bool>(entry))
+ {
+ BOOST_CHECK_EQUAL(entry->getPrefix(), target);
+ }
+ else
+ {
+ BOOST_FAIL("No entry found for " << target);
+ }
+}
+
+void
+validateNoExactMatch(const Fib& fib, const Name& target)
+{
+ shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
+ if (static_cast<bool>(entry))
+ {
+ BOOST_FAIL("Found unexpected entry for " << target);
+ }
+}
+
+BOOST_AUTO_TEST_CASE(FindExactMatch)
+{
+ Fib fib;
+ fib.insert("/A");
+ fib.insert("/A/B");
+ fib.insert("/A/B/C");
+
+ validateFindExactMatch(fib, "/A");
+ validateFindExactMatch(fib, "/A/B");
+ validateFindExactMatch(fib, "/A/B/C");
+ validateFindExactMatch(fib, "/");
+
+ validateNoExactMatch(fib, "/does/not/exist");
+
+ Fib gapFib;
+ fib.insert("/X");
+ fib.insert("/X/Y/Z");
+
+ validateNoExactMatch(gapFib, "/X/Y");
+
+ Fib emptyFib;
+ validateNoExactMatch(emptyFib, "/nothing/here");
+}
+
+void
+validateRemove(Fib& fib, const Name& target)
+{
+ fib.remove(target);
+
+ shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
+ if (static_cast<bool>(entry))
+ {
+ BOOST_FAIL("Found \"removed\" entry for " << target);
+ }
+}
+
+BOOST_AUTO_TEST_CASE(Remove)
+{
+ Fib emptyFib;
+
+ emptyFib.remove("/does/not/exist"); // crash test
+
+ validateRemove(emptyFib, "/");
+
+ emptyFib.remove("/still/does/not/exist"); // crash test
+
+ Fib fib;
+ fib.insert("/A");
+ fib.insert("/A/B");
+ fib.insert("/A/B/C");
+
+ // check if we remove the right thing and leave
+ // everything else alone
+
+ validateRemove(fib, "/A/B");
+ validateFindExactMatch(fib, "/A");
+ validateFindExactMatch(fib, "/A/B/C");
+ validateFindExactMatch(fib, "/");
+
+ validateRemove(fib, "/A/B/C");
+ validateFindExactMatch(fib, "/A");
+ validateFindExactMatch(fib, "/");
+
+ validateRemove(fib, "/A");
+ validateFindExactMatch(fib, "/");
+
+ Fib gapFib;
+ gapFib.insert("/X");
+ gapFib.insert("/X/Y/Z");
+
+ gapFib.remove("/X/Y"); //should do nothing
+ validateFindExactMatch(gapFib, "/X");
+ validateFindExactMatch(gapFib, "/X/Y/Z");
+}
+
BOOST_AUTO_TEST_SUITE_END()
} // namespace nfd