table: better ContentStore findRightmost algorithm
refs #2254
Change-Id: Ib8f473f0cce1a1636b600a98494292499d71972e
diff --git a/core/algorithm.hpp b/core/algorithm.hpp
new file mode 100644
index 0000000..5dc9dbb
--- /dev/null
+++ b/core/algorithm.hpp
@@ -0,0 +1,58 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * 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_CORE_ALGORITHM_HPP
+#define NFD_CORE_ALGORITHM_HPP
+
+#include "common.hpp"
+#include <boost/concept/requires.hpp>
+
+namespace nfd {
+
+/** \brief finds the last element satisfying a predicate
+ * \tparam It BidirectionalIterator
+ * \tparam Pred UnaryPredicate
+ *
+ * \return Iterator to the last element satisfying the condition,
+ * or \p last if no such element is found.
+ *
+ * Complexity: at most \p last-first invocations of \p p
+ */
+template<typename It, typename Pred>
+BOOST_CONCEPT_REQUIRES(
+ ((boost::BidirectionalIterator<It>))
+ ((boost::UnaryPredicate<Pred, typename std::iterator_traits<It>::value_type>)),
+ (It)
+)
+find_last_if(It first, It last, Pred p)
+{
+ std::reverse_iterator<It> firstR(first), lastR(last);
+ auto found = std::find_if(lastR, firstR, p);
+ return found == firstR ? last : std::prev(found.base());
+}
+
+} // namespace nfd
+
+#endif // NFD_CORE_ALGORITHM_HPP
diff --git a/daemon/table/cs-entry.cpp b/daemon/table/cs-entry.cpp
index be6202c..584dda3 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -1,12 +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,
- * The University of Memphis
+ * Copyright (c) 2014-2015, 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.
@@ -56,6 +56,13 @@
}
const Name&
+Entry::getName() const
+{
+ BOOST_ASSERT(!this->isQuery());
+ return m_data->getName();
+}
+
+const Name&
Entry::getFullName() const
{
BOOST_ASSERT(!this->isQuery());
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index 12a65b0..a35d9e9 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -1,12 +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,
- * The University of Memphis
+ * Copyright (c) 2014-2015, 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.
@@ -56,6 +56,9 @@
getData() const;
const Name&
+ getName() const;
+
+ const Name&
getFullName() const;
/** \return true if entry can become stale, false if entry is never stale
@@ -75,6 +78,9 @@
void
unsetUnsolicited();
+ /** \brief determines whether Interest can be satisified by this cached Data
+ * \note ChildSelector is not considered
+ */
bool
canSatisfy(const Interest& interest) const;
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index 822cb84..3bc816a 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -1,12 +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,
- * The University of Memphis
+ * Copyright (c) 2014-2015, 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.
@@ -26,6 +26,7 @@
#include "cs.hpp"
#include "cs-entry.hpp"
#include "core/logger.hpp"
+#include "core/algorithm.hpp"
#include <numeric>
NFD_LOG_INIT("ContentStore");
@@ -62,7 +63,7 @@
bool
Cs::insert(const Data& data, bool isUnsolicited)
{
- NFD_LOG_DEBUG("insert " << data.getFullName());
+ NFD_LOG_DEBUG("insert " << data.getName());
bool isNewEntry = false; TableIt it;
// use .insert because gcc46 does not support .emplace
@@ -88,50 +89,77 @@
return true;
}
-bool
-Cs::isNewRightmostCandidate(const Name& prefix, TableIt a, TableIt b)
-{
- if (a->getFullName().size() == prefix.size()) {
- return true;
- }
- return b->getFullName().at(prefix.size()) > a->getFullName().at(prefix.size());
-}
-
const Data*
Cs::find(const Interest& interest) const
{
const Name& prefix = interest.getName();
bool isRightmost = interest.getChildSelector() == 1;
NFD_LOG_DEBUG("find " << prefix << (isRightmost ? " R" : " L"));
- TableIt rightmostCandidate = m_table.end();
- TableIt left = m_table.lower_bound(prefix);
- TableIt right = m_table.end();
+ TableIt first = m_table.lower_bound(prefix);
+ TableIt last = m_table.end();
if (prefix.size() > 0) {
- right = m_table.lower_bound(prefix.getSuccessor());
+ last = m_table.lower_bound(prefix.getSuccessor());
}
- for (TableIt it = left; it != right; ++it) {
- const Entry& entry = *it;
- if (!entry.canSatisfy(interest)) {
- NFD_LOG_TRACE("cannotSatisfy " << entry.getFullName());
- continue;
- }
- NFD_LOG_TRACE("canSatisfy " << entry.getFullName());
- if (!isRightmost) {
- return entry.getData().get();
+
+ TableIt match = last;
+ if (isRightmost) {
+ match = this->findRightmost(interest, first, last);
+ }
+ else {
+ match = this->findLeftmost(interest, first, last);
+ }
+
+ if (match == last) {
+ NFD_LOG_DEBUG(" no-match");
+ return nullptr;
+ }
+ NFD_LOG_DEBUG(" matching " << match->getName());
+ return match->getData().get();
+}
+
+Cs::TableIt
+Cs::findLeftmost(const Interest& interest, TableIt first, TableIt last) const
+{
+ return std::find_if(first, last, bind(&cs::Entry::canSatisfy, _1, interest));
+}
+
+Cs::TableIt
+Cs::findRightmost(const Interest& interest, TableIt first, TableIt last) const
+{
+ // Each loop visits a sub-namespace under a prefix one component longer than Interest Name.
+ // If there is a match in that sub-namespace, the leftmost match is returned;
+ // otherwise, loop continues.
+
+ size_t interestNameLength = interest.getName().size();
+ for (TableIt right = last; right != first;) {
+ TableIt prev = std::prev(right);
+
+ // special case: [first,prev] have exact Names
+ if (prev->getName().size() == interestNameLength) {
+ NFD_LOG_TRACE(" find-among-exact " << prev->getName());
+ TableIt matchExact = this->findRightmostAmongExact(interest, first, right);
+ return matchExact == right ? last : matchExact;
}
- if (rightmostCandidate == m_table.end() ||
- isNewRightmostCandidate(prefix, rightmostCandidate, it)) {
- NFD_LOG_TRACE("rightmostCandidate=" << entry.getFullName());
- rightmostCandidate = it;
+ Name prefix = prev->getName().getPrefix(interestNameLength + 1);
+ TableIt left = m_table.lower_bound(prefix);
+
+ // normal case: [left,right) are under one-component-longer prefix
+ NFD_LOG_TRACE(" find-under-prefix " << prefix);
+ TableIt match = this->findLeftmost(interest, left, right);
+ if (match != right) {
+ return match;
}
+ right = left;
}
- if (isRightmost) {
- return rightmostCandidate == m_table.end() ? nullptr :
- rightmostCandidate->getData().get();
- }
- return nullptr;
+ return last;
+}
+
+Cs::TableIt
+Cs::findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const
+{
+ return find_last_if(first, last, bind(&Entry::canSatisfy, _1, interest));
}
void
@@ -215,7 +243,7 @@
TableIt it; std::string reason;
std::tie(it, reason) = this->evictPick();
- NFD_LOG_DEBUG("evict " << it->getFullName() << " " << reason);
+ NFD_LOG_DEBUG("evict " << it->getName() << " " << reason);
this->detachQueue(it);
m_table.erase(it);
}
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 4eadd40..5bab097 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -1,12 +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,
- * The University of Memphis
+ * Copyright (c) 2014-2015, 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.
@@ -118,10 +118,23 @@
};
private:
- /** \brief determines whether b should be the rightmost candidate instead of a
+ /** \brief find leftmost match in [first,last)
+ * \return the leftmost match, or last if not found
*/
- static bool
- isNewRightmostCandidate(const Name& prefix, TableIt a, TableIt b);
+ TableIt
+ findLeftmost(const Interest& interest, TableIt left, TableIt right) const;
+
+ /** \brief find rightmost match in [first,last)
+ * \return the rightmost match, or last if not found
+ */
+ TableIt
+ findRightmost(const Interest& interest, TableIt first, TableIt last) const;
+
+ /** \brief find rightmost match among entries with exact Names in [first,last)
+ * \return the rightmost match, or last if not found
+ */
+ TableIt
+ findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const;
/** \brief attaches an entry to a suitable cleanup queue
* \note if the entry is already attached to a queue, it's automatically detached
diff --git a/tests/core/algorithm.cpp b/tests/core/algorithm.cpp
new file mode 100644
index 0000000..941166d
--- /dev/null
+++ b/tests/core/algorithm.cpp
@@ -0,0 +1,62 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2015, 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.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * 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 "core/algorithm.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(CoreAlgorithm, BaseFixture)
+
+BOOST_AUTO_TEST_CASE(FindLastIf)
+{
+ std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9};
+
+ int hit1 = 0;
+ std::vector<int>::const_iterator found1 = find_last_if(vec.begin(), vec.end(),
+ [&hit1] (int n) -> bool {
+ ++hit1;
+ return n % 2 == 0;
+ });
+ BOOST_REQUIRE(found1 != vec.end());
+ BOOST_CHECK_EQUAL(*found1, 8);
+ BOOST_CHECK_LE(hit1, vec.size());
+
+ int hit2 = 0;
+ std::vector<int>::const_iterator found2 = find_last_if(vec.begin(), vec.end(),
+ [&hit2] (int n) -> bool {
+ ++hit2;
+ return n < 0;
+ });
+ BOOST_CHECK(found2 == vec.end());
+ BOOST_CHECK_LE(hit2, vec.size());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd