table: simplify FIB with C++11 features
refs #2100
Change-Id: I293044ae321b9a1d7c07a34f631c49c791c7856d
diff --git a/daemon/table/fib-entry.cpp b/daemon/table/fib-entry.cpp
index 79111e2..b2ea76c 100644
--- a/daemon/table/fib-entry.cpp
+++ b/daemon/table/fib-entry.cpp
@@ -1,11 +1,12 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014 Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -20,7 +21,7 @@
*
* You should have received a copy of the GNU General Public License along with
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- **/
+ */
#include "fib-entry.hpp"
@@ -32,28 +33,29 @@
{
}
-static inline bool
-predicate_NextHop_eq_Face(const NextHop& nexthop, shared_ptr<Face> face)
+NextHopList::iterator
+Entry::findNextHop(Face& face)
{
- return nexthop.getFace() == face;
+ return std::find_if(m_nextHops.begin(), m_nextHops.end(),
+ [&face] (const NextHop& nexthop) {
+ return nexthop.getFace().get() == &face;
+ });
}
bool
Entry::hasNextHop(shared_ptr<Face> face) const
{
- NextHopList::const_iterator it = std::find_if(m_nextHops.begin(), m_nextHops.end(),
- bind(&predicate_NextHop_eq_Face, _1, face));
- return it != m_nextHops.end();
+ return const_cast<Entry*>(this)->findNextHop(*face) != m_nextHops.end();
}
void
Entry::addNextHop(shared_ptr<Face> face, uint64_t cost)
{
- NextHopList::iterator it = std::find_if(m_nextHops.begin(), m_nextHops.end(),
- bind(&predicate_NextHop_eq_Face, _1, face));
+ auto it = this->findNextHop(*face);
if (it == m_nextHops.end()) {
m_nextHops.push_back(fib::NextHop(face));
- it = m_nextHops.end() - 1;
+ it = m_nextHops.end();
+ --it;
}
// now it refers to the NextHop for face
@@ -65,25 +67,17 @@
void
Entry::removeNextHop(shared_ptr<Face> face)
{
- NextHopList::iterator it = std::find_if(m_nextHops.begin(), m_nextHops.end(),
- bind(&predicate_NextHop_eq_Face, _1, face));
- if (it == m_nextHops.end()) {
- return;
+ auto it = this->findNextHop(*face);
+ if (it != m_nextHops.end()) {
+ m_nextHops.erase(it);
}
-
- m_nextHops.erase(it);
-}
-
-static inline bool
-compare_NextHop_cost(const NextHop& a, const NextHop& b)
-{
- return a.getCost() < b.getCost();
}
void
Entry::sortNextHops()
{
- std::sort(m_nextHops.begin(), m_nextHops.end(), &compare_NextHop_cost);
+ std::sort(m_nextHops.begin(), m_nextHops.end(),
+ [] (const NextHop& a, const NextHop& b) { return a.getCost() < b.getCost(); });
}
diff --git a/daemon/table/fib-entry.hpp b/daemon/table/fib-entry.hpp
index 1d03426..4a6116e 100644
--- a/daemon/table/fib-entry.hpp
+++ b/daemon/table/fib-entry.hpp
@@ -1,11 +1,12 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014 Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -20,7 +21,7 @@
*
* You should have received a copy of the GNU General Public License along with
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- **/
+ */
#ifndef NFD_DAEMON_TABLE_FIB_ENTRY_HPP
#define NFD_DAEMON_TABLE_FIB_ENTRY_HPP
@@ -38,7 +39,8 @@
/** \class NextHopList
* \brief represents a collection of nexthops
- * This type has these methods:
+ *
+ * This type has these methods as public API:
* iterator<NextHop> begin()
* iterator<NextHop> end()
* size_t size()
@@ -60,22 +62,41 @@
const NextHopList&
getNextHops() const;
- /// whether this Entry has any nexthop
+ /** \return whether this Entry has any NextHop record
+ */
bool
hasNextHops() const;
+ /** \return whether there is a NextHop record for face
+ *
+ * \todo change parameter type to Face&
+ */
bool
hasNextHop(shared_ptr<Face> face) const;
- /// adds a nexthop
+ /** \brief adds a NextHop record
+ *
+ * If a NextHop record for face already exists, its cost is updated.
+ * \note shared_ptr is passed by value because this function will take shared ownership
+ */
void
addNextHop(shared_ptr<Face> face, uint64_t cost);
- /// removes a nexthop
+ /** \brief removes a NextHop record
+ *
+ * If no NextHop record for face exists, do nothing.
+ *
+ * \todo change parameter type to Face&
+ */
void
removeNextHop(shared_ptr<Face> face);
private:
+ /** @note This method is non-const because normal iterator is needed by callers.
+ */
+ NextHopList::iterator
+ findNextHop(Face& face);
+
/// sorts the nexthop list
void
sortNextHops();
diff --git a/daemon/table/fib-nexthop.cpp b/daemon/table/fib-nexthop.cpp
index 7f480a8..235fc79 100644
--- a/daemon/table/fib-nexthop.cpp
+++ b/daemon/table/fib-nexthop.cpp
@@ -1,11 +1,12 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014 Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -20,7 +21,7 @@
*
* You should have received a copy of the GNU General Public License along with
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- **/
+ */
#include "fib-nexthop.hpp"
@@ -28,16 +29,12 @@
namespace fib {
NextHop::NextHop(shared_ptr<Face> face)
- : m_face(face), m_cost(0)
+ : m_face(face)
+ , m_cost(0)
{
}
-NextHop::NextHop(const NextHop& other)
- : m_face(other.m_face), m_cost(other.m_cost)
-{
-}
-
-shared_ptr<Face>
+const shared_ptr<Face>&
NextHop::getFace() const
{
return m_face;
diff --git a/daemon/table/fib-nexthop.hpp b/daemon/table/fib-nexthop.hpp
index 691cf6b..9f7ed93 100644
--- a/daemon/table/fib-nexthop.hpp
+++ b/daemon/table/fib-nexthop.hpp
@@ -1,11 +1,12 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/**
- * Copyright (c) 2014 Regents of the University of California,
- * Arizona Board of Regents,
- * Colorado State University,
- * University Pierre & Marie Curie, Sorbonne University,
- * Washington University in St. Louis,
- * Beijing Institute of Technology
+ * Copyright (c) 2014, Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -20,7 +21,7 @@
*
* You should have received a copy of the GNU General Public License along with
* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- **/
+ */
#ifndef NFD_DAEMON_TABLE_FIB_NEXTHOP_HPP
#define NFD_DAEMON_TABLE_FIB_NEXTHOP_HPP
@@ -40,9 +41,7 @@
explicit
NextHop(shared_ptr<Face> face);
- NextHop(const NextHop& other);
-
- shared_ptr<Face>
+ const shared_ptr<Face>&
getFace() const;
void
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 660ae72..a3b836e 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -47,19 +47,6 @@
return static_cast<bool>(entry.getFibEntry());
}
-std::pair<shared_ptr<fib::Entry>, bool>
-Fib::insert(const Name& prefix)
-{
- 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);
-}
-
shared_ptr<fib::Entry>
Fib::findLongestPrefixMatch(const Name& prefix) const
{
@@ -114,6 +101,19 @@
return shared_ptr<fib::Entry>();
}
+std::pair<shared_ptr<fib::Entry>, bool>
+Fib::insert(const Name& prefix)
+{
+ 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);
+}
+
void
Fib::erase(shared_ptr<name_tree::Entry> nameTreeEntry)
{
@@ -147,7 +147,7 @@
&predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end();) {
shared_ptr<fib::Entry> entry = it->getFibEntry();
- ++it; // need to be advance before `erase`, otherwise the iterator can be invalidated
+ ++it; // advance the iterator before `erase` invalidates it
entry->removeNextHop(face);
if (!entry->hasNextHops()) {
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 615462f..3a19949 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -44,20 +44,15 @@
class Fib : noncopyable
{
public:
- class const_iterator;
-
explicit
Fib(NameTree& nameTree);
~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);
+ size_t
+ size() const;
+public: // lookup
/// performs a longest prefix match
shared_ptr<fib::Entry>
findLongestPrefixMatch(const Name& prefix) const;
@@ -73,6 +68,14 @@
shared_ptr<fib::Entry>
findExactMatch(const Name& prefix) const;
+public: // mutation
+ /** \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);
+
void
erase(const Name& prefix);
@@ -80,14 +83,17 @@
erase(const fib::Entry& entry);
/** \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.
+ * Removing the last NextHop in a FIB entry will erase the FIB entry.
+ *
+ * \todo change parameter type to Face&
*/
void
removeNextHopFromAllEntries(shared_ptr<Face> face);
- size_t
- size() const;
+public: // enumeration
+ class const_iterator;
const_iterator
begin() const;
@@ -140,8 +146,8 @@
*
* This entry has no nexthops.
* It is returned by findLongestPrefixMatch if nothing is matched.
+ * Returning empty entry instead of nullptr makes forwarding and strategy implementation easier.
*/
- // Returning empty entry instead of nullptr makes forwarding and strategy implementation easier.
static const shared_ptr<fib::Entry> s_emptyEntry;
};