name-prefix-list: compare names only in operator==
NamePrefixList type is now a sorted container. The sort() method is
deleted.
The remove() method is renamed to erase(), in accordance with ndn-cxx
code style recommendations.
refs #4094
Change-Id: I2d3f2fa768a8dd9a51108f6f4064243b21fd6df8
diff --git a/src/lsa/name-lsa.cpp b/src/lsa/name-lsa.cpp
index 90f946f..50e4cb7 100644
--- a/src/lsa/name-lsa.cpp
+++ b/src/lsa/name-lsa.cpp
@@ -138,9 +138,6 @@
auto nlsa = std::static_pointer_cast<NameLsa>(lsa);
bool updated = false;
- m_npl.sort();
- nlsa->getNpl().sort();
-
// Obtain the set difference of the current and the incoming
// name prefix sets, and add those.
std::list<ndn::Name> newNames = nlsa->getNpl().getNames();
@@ -153,8 +150,6 @@
updated = true;
}
- m_npl.sort();
-
// Also remove any names that are no longer being advertised.
std::list<ndn::Name> namesToRemove;
std::set_difference(oldNames.begin(), oldNames.end(), newNames.begin(), newNames.end(),
diff --git a/src/lsa/name-lsa.hpp b/src/lsa/name-lsa.hpp
index 1705abc..5e4cfa6 100644
--- a/src/lsa/name-lsa.hpp
+++ b/src/lsa/name-lsa.hpp
@@ -78,7 +78,7 @@
removeName(const ndn::Name& name)
{
m_wire.reset();
- m_npl.remove(name);
+ m_npl.erase(name);
}
bool
diff --git a/src/name-prefix-list.cpp b/src/name-prefix-list.cpp
index c858c96..5af7062 100644
--- a/src/name-prefix-list.cpp
+++ b/src/name-prefix-list.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2022, The University of Memphis,
+ * Copyright (c) 2014-2023, The University of Memphis,
* Regents of the University of California,
* Arizona Board of Regents.
*
@@ -28,85 +28,39 @@
NamePrefixList::NamePrefixList(ndn::span<const ndn::Name> names)
{
- std::transform(names.begin(), names.end(), std::back_inserter(m_names),
- [] (const auto& name) { return NamePair{name, {""}}; });
-}
-
-std::vector<NamePrefixList::NamePair>::iterator
-NamePrefixList::get(const ndn::Name& name)
-{
- return std::find_if(m_names.begin(), m_names.end(),
- [&] (const NamePrefixList::NamePair& pair) {
- return name == std::get<NamePrefixList::NamePairIndex::NAME>(pair);
- });
-}
-
-std::vector<std::string>::iterator
-NamePrefixList::getSource(const std::string& source, std::vector<NamePair>::iterator& entry)
-{
- return std::find_if(std::get<NamePairIndex::SOURCES>(*entry).begin(),
- std::get<NamePairIndex::SOURCES>(*entry).end(),
- [&] (const std::string& containerSource) {
- return source == containerSource;
- });
+ for (const auto& name : names) {
+ insert(name);
+ }
}
bool
NamePrefixList::insert(const ndn::Name& name, const std::string& source)
{
- auto pairItr = get(name);
- if (pairItr == m_names.end()) {
- std::vector<std::string> sources{source};
- m_names.emplace_back(name, sources);
- return true;
- }
- else {
- auto& sources = std::get<NamePrefixList::NamePairIndex::SOURCES>(*pairItr);
- auto sourceItr = getSource(source, pairItr);
- if (sourceItr == sources.end()) {
- sources.push_back(source);
- return true;
- }
- }
- return false;
+ auto& sources = m_namesSources[name];
+ return sources.insert(source).second;
}
bool
-NamePrefixList::remove(const ndn::Name& name, const std::string& source)
+NamePrefixList::erase(const ndn::Name& name, const std::string& source)
{
- auto pairItr = get(name);
- if (pairItr != m_names.end()) {
- auto& sources = std::get<NamePrefixList::NamePairIndex::SOURCES>(*pairItr);
- auto sourceItr = getSource(source, pairItr);
- if (sourceItr != sources.end()) {
- sources.erase(sourceItr);
- if (sources.empty()) {
- m_names.erase(pairItr);
- }
- return true;
- }
+ auto it = m_namesSources.find(name);
+ if (it == m_namesSources.end()) {
+ return false;
}
- return false;
-}
-bool
-NamePrefixList::operator==(const NamePrefixList& other) const
-{
- return m_names == other.m_names;
-}
-
-void
-NamePrefixList::sort()
-{
- std::sort(m_names.begin(), m_names.end());
+ bool isRemoved = it->second.erase(source);
+ if (it->second.empty()) {
+ m_namesSources.erase(it);
+ }
+ return isRemoved;
}
std::list<ndn::Name>
NamePrefixList::getNames() const
{
std::list<ndn::Name> names;
- for (const auto& namePair : m_names) {
- names.push_back(std::get<NamePrefixList::NamePairIndex::NAME>(namePair));
+ for (const auto& [name, sources] : m_namesSources) {
+ names.push_back(name);
}
return names;
}
@@ -120,16 +74,16 @@
const std::vector<std::string>
NamePrefixList::getSources(const ndn::Name& name) const
{
- auto it = std::find_if(m_names.begin(), m_names.end(),
- [&] (const NamePrefixList::NamePair& pair) {
- return name == std::get<NamePrefixList::NamePairIndex::NAME>(pair);
- });
- if (it != m_names.end()) {
- return std::get<NamePrefixList::NamePairIndex::SOURCES>(*it);
- }
- else {
+ auto it = m_namesSources.find(name);
+ if (it == m_namesSources.end()) {
return {};
}
+
+ std::vector<std::string> result;
+ for (const auto& source : it->second) {
+ result.push_back(source);
+ }
+ return result;
}
std::ostream&
diff --git a/src/name-prefix-list.hpp b/src/name-prefix-list.hpp
index 46eb0d0..68e6b81 100644
--- a/src/name-prefix-list.hpp
+++ b/src/name-prefix-list.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2022, The University of Memphis,
+ * Copyright (c) 2014-2023, The University of Memphis,
* Regents of the University of California,
* Arizona Board of Regents.
*
@@ -24,17 +24,20 @@
#include "test-access-control.hpp"
+#include <ndn-cxx/name.hpp>
+
+#include <boost/operators.hpp>
+
#include <initializer_list>
#include <list>
+#include <map>
+#include <set>
#include <string>
-#include <tuple>
#include <vector>
-#include <ndn-cxx/name.hpp>
-
namespace nlsr {
-class NamePrefixList
+class NamePrefixList : private boost::equality_comparable<NamePrefixList>
{
public:
using NamePair = std::tuple<ndn::Name, std::vector<std::string>>;
@@ -56,8 +59,12 @@
}
NamePrefixList(std::initializer_list<NamePair> namesAndSources)
- : m_names(namesAndSources)
{
+ for (const auto& np : namesAndSources) {
+ for (const auto& source : std::get<NamePrefixList::NamePairIndex::SOURCES>(np)) {
+ insert(std::get<NamePrefixList::NamePairIndex::NAME>(np), source);
+ }
+ }
}
#endif
@@ -73,23 +80,17 @@
\retval false If the name failed to be removed.
*/
bool
- remove(const ndn::Name& name, const std::string& source = "");
-
- void
- sort();
+ erase(const ndn::Name& name, const std::string& source = "");
size_t
size() const
{
- return m_names.size();
+ return m_namesSources.size();
}
std::list<ndn::Name>
getNames() const;
- bool
- operator==(const NamePrefixList& other) const;
-
/*! Returns how many unique sources this name has.
\retval 0 if the name is not in the list, else the number of sources.
@@ -108,24 +109,22 @@
void
clear()
{
- m_names.clear();
+ m_namesSources.clear();
+ }
+
+private: // non-member operators
+ // NOTE: the following "hidden friend" operators are available via
+ // argument-dependent lookup only and must be defined inline.
+ // boost::equality_comparable provides != operators.
+
+ friend bool
+ operator==(const NamePrefixList& lhs, const NamePrefixList& rhs)
+ {
+ return lhs.getNames() == rhs.getNames();
}
private:
- /*! Obtain an iterator to the entry matching name.
-
- \note We could do this quite easily inline with a lambda, but this
- is slightly more efficient.
- */
- std::vector<NamePair>::iterator
- get(const ndn::Name& name);
-
- /*! Obtain an iterator to a specific source in an entry
- */
- std::vector<std::string>::iterator
- getSource(const std::string& source, std::vector<NamePair>::iterator& entry);
-
- std::vector<NamePair> m_names;
+ std::map<ndn::Name, std::set<std::string>> m_namesSources;
};
std::ostream&
diff --git a/src/update/manager-base.cpp b/src/update/manager-base.cpp
index 238a88f..3e0b612 100644
--- a/src/update/manager-base.cpp
+++ b/src/update/manager-base.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2022, The University of Memphis,
+ * Copyright (c) 2014-2023, The University of Memphis,
* Regents of the University of California,
* Arizona Board of Regents.
*
@@ -102,7 +102,7 @@
static_cast<const ndn::nfd::ControlParameters&>(parameters);
// Only build a Name LSA if the added name is new
- if (m_namePrefixList.remove(castParams.getName())) {
+ if (m_namePrefixList.erase(castParams.getName())) {
NLSR_LOG_INFO("Withdrawing/Removing name: " << castParams.getName() << "\n");
m_lsdb.buildAndInstallOwnNameLsa();
if (castParams.hasFlags() && castParams.getFlags() == PREFIX_FLAG) {
diff --git a/tests/test-lsdb.cpp b/tests/test-lsdb.cpp
index f6e078b..526da8a 100644
--- a/tests/test-lsdb.cpp
+++ b/tests/test-lsdb.cpp
@@ -357,7 +357,7 @@
BOOST_CHECK_EQUAL(nameList, prefixes);
// Remove a prefix: name2
- prefixes.remove(name2);
+ prefixes.erase(name2);
NameLsa removeLsa(otherRouter, 3, MAX_TIME, prefixes);
lsdb.installLsa(std::make_shared<NameLsa>(removeLsa));
@@ -367,7 +367,7 @@
// Add and remove a prefix: add name2, remove name3
prefixes.insert(name2);
- prefixes.remove(name3);
+ prefixes.erase(name3);
NameLsa addAndRemoveLsa(otherRouter, 4, MAX_TIME, prefixes);
lsdb.installLsa(std::make_shared<NameLsa>(addAndRemoveLsa));
diff --git a/tests/test-name-prefix-list.cpp b/tests/test-name-prefix-list.cpp
index b62ab31..6fdfd17 100644
--- a/tests/test-name-prefix-list.cpp
+++ b/tests/test-name-prefix-list.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2022, The University of Memphis,
+ * Copyright (c) 2014-2023, The University of Memphis,
* Regents of the University of California
*
* This file is part of NLSR (Named-data Link State Routing).
@@ -38,7 +38,7 @@
BOOST_CHECK_EQUAL(npl1.size(), 2);
- npl1.remove(b);
+ npl1.erase(b);
BOOST_CHECK_EQUAL(npl1.size(), 1);
}
@@ -53,9 +53,19 @@
ndn::Name name2("/ndn/test/name2");
ndn::Name name3("/ndn/some/other/name1");
NamePrefixList list1{name1, name2, name3};
- NamePrefixList list2{name1, name2, name3};
+ NamePrefixList list2;
+ BOOST_CHECK_NE(list1, list2);
+
+ list2.insert(name1);
+ list2.insert(name1, "A1");
+ list2.insert(name2, "B0");
+ list2.insert(name2, "B1");
+ list2.insert(name3, "C0");
BOOST_CHECK_EQUAL(list1, list2);
+
+ list2.erase(name3, "C0");
+ BOOST_CHECK_NE(list1, list2);
}
/*
@@ -141,7 +151,7 @@
list.insert(name1, "readvertise");
list.insert(name1, "prefix-update");
- list.remove(name1, "prefix-update");
+ list.erase(name1, "prefix-update");
std::vector<std::string> referenceSources{"nlsr.conf", "readvertise", "prefix-update"};
const std::vector<std::string> sources = list.getSources(name1);
@@ -162,8 +172,8 @@
const ndn::Name name3{"/ndn/test/prefix3"};
std::list<ndn::Name> testList{name1, name2, name3};
- const std::vector<std::string> sources1{"static", "readvertise"};
- const std::vector<std::string> sources2{"static", "nlsrc"};
+ const std::vector<std::string> sources1{"readvertise", "static"};
+ const std::vector<std::string> sources2{"nlsrc", "static"};
const std::vector<std::string> sources3{"static"};
NamePrefixList list1{name1, name2, name3};