src: Sort NextHops on NexthopList insertion
refs: #2721
Change-Id: I39893c5fb6b5fac93220901ab3190090f0d2cc57
diff --git a/src/route/fib.cpp b/src/route/fib.cpp
index f61f6f4..4a82661 100644
--- a/src/route/fib.cpp
+++ b/src/route/fib.cpp
@@ -16,9 +16,6 @@
*
* You should have received a copy of the GNU General Public License along with
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
**/
#include <list>
#include <cmath>
@@ -72,7 +69,7 @@
m_table.end(),
bind(&fibEntryNameCompare, _1, name));
if (it != m_table.end()) {
- for (std::list<NextHop>::iterator nhit =
+ for (std::set<NextHop, NextHopComparator>::iterator nhit =
(*it).getNexthopList().getNextHops().begin();
nhit != (*it).getNexthopList().getNextHops().end(); nhit++) {
//remove entry from NDN-FIB
@@ -110,8 +107,6 @@
ndn::nfd::ROUTE_FLAG_CAPTURE, 0);
}
}
-
- entry.getNexthopList().sort();
}
void
@@ -156,9 +151,6 @@
{
_LOG_DEBUG("Fib::update called");
- // Sort all of the next hops so lower cost hops are prioritized
- allHops.sort();
-
// Get the max possible faces which is the minumum of the configuration setting and
// the length of the list of all next hops.
unsigned int maxFaces = getNumberOfFacesForName(allHops);
@@ -239,7 +231,7 @@
++it) {
_LOG_DEBUG("Cancelling Scheduled event. Name: " << it->getName());
cancelScheduledExpiringEvent((*it).getExpiringEventId());
- for (std::list<NextHop>::iterator nhit =
+ for (std::set<NextHop, NextHopComparator>::iterator nhit =
(*it).getNexthopList().getNextHops().begin();
nhit != (*it).getNexthopList().getNextHops().end(); nhit++) {
//Remove entry from NDN-FIB
@@ -279,7 +271,7 @@
Fib::removeHop(NexthopList& nl, const std::string& doNotRemoveHopFaceUri,
const ndn::Name& name)
{
- for (std::list<NextHop>::iterator it = nl.getNextHops().begin();
+ for (std::set<NextHop, NextHopComparator>::iterator it = nl.getNextHops().begin();
it != nl.getNextHops().end(); ++it) {
if (it->getConnectingFaceUri() != doNotRemoveHopFaceUri) {
//Remove FIB Entry from NDN-FIB
diff --git a/src/route/name-prefix-table-entry.cpp b/src/route/name-prefix-table-entry.cpp
index a9682ef..0306911 100644
--- a/src/route/name-prefix-table-entry.cpp
+++ b/src/route/name-prefix-table-entry.cpp
@@ -38,7 +38,7 @@
it != m_rteList.end(); ++it)
{
// Add every next hop from each routing table entry to this entry's NHL.
- for (std::list<NextHop>::iterator nhit =
+ for (std::set<NextHop, NextHopComparator>::iterator nhit =
(*it).getNexthopList().getNextHops().begin();
nhit != (*it).getNexthopList().getNextHops().end(); ++nhit)
{
@@ -80,7 +80,7 @@
else
{
(*it).getNexthopList().reset(); // reseting existing routing table's next hop
- for (std::list<NextHop>::iterator nhit =
+ for (std::set<NextHop, NextHopComparator>::iterator nhit =
rte.getNexthopList().getNextHops().begin();
nhit != rte.getNexthopList().getNextHops().end(); ++nhit) {
(*it).getNexthopList().addNextHop((*nhit));
diff --git a/src/route/name-prefix-table.cpp b/src/route/name-prefix-table.cpp
index e5199b0..5c18b77 100644
--- a/src/route/name-prefix-table.cpp
+++ b/src/route/name-prefix-table.cpp
@@ -53,7 +53,6 @@
NamePrefixTableEntry entry(name);
entry.addRoutingTableEntry(rte); // Add this RTE to this new NPT entry.
entry.generateNhlfromRteList(); // Generate a list of next-hops from the RTE.
- entry.getNexthopList().sort(); // Sort it.
m_table.push_back(entry); // Add the new, completed entry into the main table.
@@ -68,8 +67,7 @@
// Update the existing entry with the new RTE.
it->addRoutingTableEntry(rte);
- it->generateNhlfromRteList(); // Rebuild the list of next-hops
- it->getNexthopList().sort(); // Sort it.
+ it->generateNhlfromRteList();
// As above, inform the FIB of this fact.
// We may possibly have a new best next-hop for this name prefix
@@ -122,7 +120,6 @@
else {
_LOG_TRACE(*it << " has other routing table entries; updating FIB with next hops");
it->generateNhlfromRteList();
- it->getNexthopList().sort();
m_nlsr.getFib().update(name, it->getNexthopList());
}
diff --git a/src/route/nexthop-list.cpp b/src/route/nexthop-list.cpp
index ed46b55..22046fd 100644
--- a/src/route/nexthop-list.cpp
+++ b/src/route/nexthop-list.cpp
@@ -19,8 +19,6 @@
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
**/
-#include <iostream>
-
#include "common.hpp"
#include "nexthop-list.hpp"
#include "nexthop.hpp"
@@ -33,64 +31,37 @@
using namespace std;
static bool
-nexthopCompare(NextHop& nh1, NextHop& nh2)
+nexthopAddCompare(const NextHop& nh1, const NextHop& nh2)
{
return nh1.getConnectingFaceUri() == nh2.getConnectingFaceUri();
}
static bool
-nexthopRemoveCompare(NextHop& nh1, NextHop& nh2)
+nexthopRemoveCompare(const NextHop& nh1, const NextHop& nh2)
{
return (nh1.getConnectingFaceUri() == nh2.getConnectingFaceUri() &&
nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) ;
}
-static bool
-nextHopSortingComparator(const NextHop& nh1, const NextHop& nh2)
-{
- if (nh1.getRouteCostAsAdjustedInteger() < nh2.getRouteCostAsAdjustedInteger()) {
- return true;
- }
- else if (nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) {
- return nh1.getConnectingFaceUri() < nh2.getConnectingFaceUri();
- }
- else {
- return false;
- }
-}
-
-/*!
-Add next hop to the Next Hop list
-If next hop is new it is added
-If next hop already exists in next
-hop list then updates the route
-cost with new next hop's route cost
-*/
-
void
-NexthopList::addNextHop(NextHop& nh)
+NexthopList::addNextHop(const NextHop& nh)
{
- std::list<NextHop>::iterator it = std::find_if(m_nexthopList.begin(),
+ std::set<NextHop, NextHopComparator>::iterator it = std::find_if(m_nexthopList.begin(),
m_nexthopList.end(),
- ndn::bind(&nexthopCompare, _1, nh));
+ ndn::bind(&nexthopAddCompare, _1, nh));
if (it == m_nexthopList.end()) {
- m_nexthopList.push_back(nh);
- return;
+ m_nexthopList.insert(nh);
}
- if ((*it).getRouteCost() > nh.getRouteCost()) {
- (*it).setRouteCost(nh.getRouteCost());
+ else if (it->getRouteCost() > nh.getRouteCost()) {
+ removeNextHop(*it);
+ m_nexthopList.insert(nh);
}
}
-/*!
-Remove a next hop only if both next hop face and route cost are same
-
-*/
-
void
-NexthopList::removeNextHop(NextHop& nh)
+NexthopList::removeNextHop(const NextHop& nh)
{
- std::list<NextHop>::iterator it = std::find_if(m_nexthopList.begin(),
+ std::set<NextHop, NextHopComparator>::iterator it = std::find_if(m_nexthopList.begin(),
m_nexthopList.end(),
ndn::bind(&nexthopRemoveCompare, _1, nh));
if (it != m_nexthopList.end()) {
@@ -99,17 +70,11 @@
}
void
-NexthopList::sort()
-{
- m_nexthopList.sort(nextHopSortingComparator);
-}
-
-void
NexthopList::writeLog()
{
int i = 1;
- sort();
- for (std::list<NextHop>::iterator it = m_nexthopList.begin();
+
+ for (std::set<NextHop, NextHopComparator>::iterator it = m_nexthopList.begin();
it != m_nexthopList.end() ; it++, i++) {
_LOG_DEBUG("Nexthop " << i << ": " << (*it).getConnectingFaceUri()
<< " Route Cost: " << (*it).getRouteCost());
diff --git a/src/route/nexthop-list.hpp b/src/route/nexthop-list.hpp
index 0c57ba3..77bd4e7 100644
--- a/src/route/nexthop-list.hpp
+++ b/src/route/nexthop-list.hpp
@@ -16,14 +16,11 @@
*
* You should have received a copy of the GNU General Public License along with
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
**/
#ifndef NLSR_NEXTHOP_LIST_HPP
#define NLSR_NEXTHOP_LIST_HPP
-#include <list>
+#include <set>
#include <iostream>
#include <boost/cstdint.hpp>
@@ -34,6 +31,21 @@
namespace nlsr {
+struct NextHopComparator {
+ bool
+ operator() (const NextHop& nh1, const NextHop& nh2) const {
+ if (nh1.getRouteCostAsAdjustedInteger() < nh2.getRouteCostAsAdjustedInteger()) {
+ return true;
+ }
+ else if (nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) {
+ return nh1.getConnectingFaceUri() < nh2.getConnectingFaceUri();
+ }
+ else {
+ return false;
+ }
+ }
+};
+
class NexthopList
{
public:
@@ -45,7 +57,6 @@
{
}
-
/*! \brief Adds a next hop to the list.
\param nh The next hop.
@@ -54,18 +65,16 @@
cost with new next hop's route cost
*/
void
- addNextHop(NextHop& nh);
+ addNextHop(const NextHop& nh);
- /*! \brief Removes a next hop.
- \param nh The next hop.
+ /*! \brief Remove a next hop from the Next Hop list
+ \param nh The NextHop we want to remove.
- Remove a next hop only if both next hop face and route cost are same.
+ The next hop gets removed only if both next hop face and route cost are same.
*/
- void
- removeNextHop(NextHop& nh);
void
- sort();
+ removeNextHop(const NextHop& nh);
size_t
getSize()
@@ -79,14 +88,14 @@
m_nexthopList.clear();
}
- std::list<NextHop>&
+ std::set<NextHop, NextHopComparator>&
getNextHops()
{
return m_nexthopList;
}
- typedef std::list<NextHop>::iterator iterator;
- typedef std::list<NextHop>::const_iterator const_iterator;
+ typedef std::set<NextHop, NextHopComparator>::iterator iterator;
+ typedef std::set<NextHop, NextHopComparator>::const_iterator const_iterator;
iterator
begin()
@@ -116,7 +125,7 @@
writeLog();
private:
- std::list<NextHop> m_nexthopList;
+ std::set<NextHop, NextHopComparator> m_nexthopList;
};
} // namespace nlsr
diff --git a/src/route/nexthop.hpp b/src/route/nexthop.hpp
index 8c5ffd1..0aa5640 100644
--- a/src/route/nexthop.hpp
+++ b/src/route/nexthop.hpp
@@ -16,9 +16,6 @@
*
* You should have received a copy of the GNU General Public License along with
* NLSR, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
**/
#ifndef NLSR_NEXTHOP_HPP
#define NLSR_NEXTHOP_HPP
@@ -80,7 +77,7 @@
}
void
- setRouteCost(double rc)
+ setRouteCost(const double rc)
{
m_routeCost = rc;
}