table: better ContentStore findRightmost algorithm
refs #2254
Change-Id: Ib8f473f0cce1a1636b600a98494292499d71972e
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