table: drop ChildSelector processing in CS
refs #4805
Change-Id: I994d1955091421e6a4ab682f40898999875736fe
diff --git a/daemon/table/cs-entry-impl.cpp b/daemon/table/cs-entry-impl.cpp
index 255cfff..f3ce820 100644
--- a/daemon/table/cs-entry-impl.cpp
+++ b/daemon/table/cs-entry-impl.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2017, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2019, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -53,7 +53,7 @@
this->setData(this->getData(), false);
}
-int
+static int
compareQueryWithData(const Name& queryName, const Data& data)
{
bool queryIsFullName = !queryName.empty() && queryName[-1].isImplicitSha256Digest();
@@ -74,7 +74,7 @@
}
}
-int
+static int
compareDataWithData(const Data& lhs, const Data& rhs)
{
int cmp = lhs.getName().compare(rhs.getName());
diff --git a/daemon/table/cs-entry.cpp b/daemon/table/cs-entry.cpp
index 4bf84d5..15b5a6f 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2017, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2019, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -31,7 +31,7 @@
void
Entry::setData(shared_ptr<const Data> data, bool isUnsolicited)
{
- m_data = data;
+ m_data = std::move(data);
m_isUnsolicited = isUnsolicited;
updateStaleTime();
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index 48895b1..eb30d58 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2017, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2019, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -94,7 +94,6 @@
isStale() const;
/** \brief determines whether Interest can be satisified by the stored Data
- * \note ChildSelector is not considered
* \pre hasData()
*/
bool
diff --git a/daemon/table/cs-internal.hpp b/daemon/table/cs-internal.hpp
index ae9d593..d240801 100644
--- a/daemon/table/cs-internal.hpp
+++ b/daemon/table/cs-internal.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
- * Copyright (c) 2014-2017, Regents of the University of California,
+ * Copyright (c) 2014-2019, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -37,8 +37,8 @@
class EntryImpl;
-typedef std::set<EntryImpl> Table;
-typedef Table::const_iterator iterator;
+using Table = std::set<EntryImpl>;
+using iterator = Table::const_iterator;
} // namespace cs
} // namespace nfd
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index 3a06c7d..a086cac 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -86,111 +86,51 @@
}
}
-void
-Cs::erase(const Name& prefix, size_t limit, const AfterEraseCallback& cb)
+std::pair<iterator, iterator>
+Cs::findPrefixRange(const Name& prefix) const
{
- BOOST_ASSERT(static_cast<bool>(cb));
-
iterator first = m_table.lower_bound(prefix);
iterator last = m_table.end();
if (prefix.size() > 0) {
last = m_table.lower_bound(prefix.getSuccessor());
}
+ return {first, last};
+}
+
+size_t
+Cs::eraseImpl(const Name& prefix, size_t limit)
+{
+ iterator i, last;
+ std::tie(i, last) = findPrefixRange(prefix);
size_t nErased = 0;
- while (first != last && nErased < limit) {
- m_policy->beforeErase(first);
- first = m_table.erase(first);
+ while (i != last && nErased < limit) {
+ m_policy->beforeErase(i);
+ i = m_table.erase(i);
++nErased;
}
-
- if (cb) {
- cb(nErased);
- }
+ return nErased;
}
-void
-Cs::find(const Interest& interest,
- const HitCallback& hitCallback,
- const MissCallback& missCallback) const
+iterator
+Cs::findImpl(const Interest& interest) const
{
- BOOST_ASSERT(static_cast<bool>(hitCallback));
- BOOST_ASSERT(static_cast<bool>(missCallback));
-
if (!m_shouldServe || m_policy->getLimit() == 0) {
- missCallback(interest);
- return;
+ return m_table.end();
}
+
const Name& prefix = interest.getName();
- bool isRightmost = interest.getChildSelector() == 1;
- NFD_LOG_DEBUG("find " << prefix << (isRightmost ? " R" : " L"));
+ auto range = findPrefixRange(prefix);
+ auto match = std::find_if(range.first, range.second,
+ [&interest] (const auto& entry) { return entry.canSatisfy(interest); });
- iterator first = m_table.lower_bound(prefix);
- iterator last = m_table.end();
- if (prefix.size() > 0) {
- last = m_table.lower_bound(prefix.getSuccessor());
+ if (match == range.second) {
+ NFD_LOG_DEBUG("find " << prefix << " no-match");
+ return m_table.end();
}
-
- iterator 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");
- missCallback(interest);
- return;
- }
- NFD_LOG_DEBUG(" matching " << match->getName());
+ NFD_LOG_DEBUG("find " << prefix << " matching " << match->getName());
m_policy->beforeUse(match);
- hitCallback(interest, match->getData());
-}
-
-iterator
-Cs::findLeftmost(const Interest& interest, iterator first, iterator last) const
-{
- return std::find_if(first, last, [&interest] (const auto& entry) { return entry.canSatisfy(interest); });
-}
-
-iterator
-Cs::findRightmost(const Interest& interest, iterator first, iterator 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 (iterator right = last; right != first;) {
- iterator prev = std::prev(right);
-
- // special case: [first,prev] have exact Names
- if (prev->getName().size() == interestNameLength) {
- NFD_LOG_TRACE(" find-among-exact " << prev->getName());
- iterator matchExact = this->findRightmostAmongExact(interest, first, right);
- return matchExact == right ? last : matchExact;
- }
-
- Name prefix = prev->getName().getPrefix(interestNameLength + 1);
- iterator left = m_table.lower_bound(prefix);
-
- // normal case: [left,right) are under one-component-longer prefix
- NFD_LOG_TRACE(" find-under-prefix " << prefix);
- iterator match = this->findLeftmost(interest, left, right);
- if (match != right) {
- return match;
- }
- right = left;
- }
- return last;
-}
-
-iterator
-Cs::findRightmostAmongExact(const Interest& interest, iterator first, iterator last) const
-{
- return find_last_if(first, last, [&interest] (const auto& entry) { return entry.canSatisfy(interest); });
+ return match;
}
void
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 16e28a5..df6c88b 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -56,31 +56,41 @@
void
insert(const Data& data, bool isUnsolicited = false);
- using AfterEraseCallback = std::function<void(size_t nErased)>;
-
/** \brief asynchronously erases entries under \p prefix
+ * \tparam AfterEraseCallback `void f(size_t nErased)`
* \param prefix name prefix of entries
* \param limit max number of entries to erase
- * \param cb callback to receive the actual number of erased entries; it may be empty;
+ * \param cb callback to receive the actual number of erased entries; must not be empty;
* it may be invoked either before or after erase() returns
*/
+ template<typename AfterEraseCallback>
void
- erase(const Name& prefix, size_t limit, const AfterEraseCallback& cb);
-
- using HitCallback = std::function<void(const Interest&, const Data&)>;
- using MissCallback = std::function<void(const Interest&)>;
+ erase(const Name& prefix, size_t limit, AfterEraseCallback&& cb)
+ {
+ size_t nErased = eraseImpl(prefix, limit);
+ cb(nErased);
+ }
/** \brief finds the best matching Data packet
+ * \tparam HitCallback `void f(const Interest&, const Data&)`
+ * \tparam MissCallback `void f(const Interest&)`
* \param interest the Interest for lookup
- * \param hitCallback a callback if a match is found; must not be empty
- * \param missCallback a callback if there's no match; must not be empty
+ * \param hit a callback if a match is found; must not be empty
+ * \param miss a callback if there's no match; must not be empty
* \note A lookup invokes either callback exactly once.
* The callback may be invoked either before or after find() returns
*/
+ template<typename HitCallback, typename MissCallback>
void
- find(const Interest& interest,
- const HitCallback& hitCallback,
- const MissCallback& missCallback) const;
+ find(const Interest& interest, HitCallback&& hit, MissCallback&& miss) const
+ {
+ iterator match = findImpl(interest);
+ if (match == m_table.end()) {
+ miss(interest);
+ return;
+ }
+ hit(interest, match->getData());
+ }
/** \brief get number of stored packets
*/
@@ -152,8 +162,9 @@
enableServe(bool shouldServe);
public: // enumeration
- struct EntryFromEntryImpl
+ class EntryFromEntryImpl
{
+ public:
typedef const Entry& result_type;
const Entry&
@@ -165,7 +176,7 @@
/** \brief ContentStore iterator (public API)
*/
- typedef boost::transform_iterator<EntryFromEntryImpl, iterator, const Entry&> const_iterator;
+ using const_iterator = boost::transform_iterator<EntryFromEntryImpl, iterator, const Entry&>;
const_iterator
begin() const
@@ -179,24 +190,15 @@
return boost::make_transform_iterator(m_table.end(), EntryFromEntryImpl());
}
-private: // find
- /** \brief find leftmost match in [first,last)
- * \return the leftmost match, or last if not found
- */
- iterator
- findLeftmost(const Interest& interest, iterator left, iterator right) const;
+private:
+ std::pair<iterator, iterator>
+ findPrefixRange(const Name& prefix) const;
- /** \brief find rightmost match in [first,last)
- * \return the rightmost match, or last if not found
- */
- iterator
- findRightmost(const Interest& interest, iterator first, iterator last) const;
+ size_t
+ eraseImpl(const Name& prefix, size_t limit);
- /** \brief find rightmost match among entries with exact Names in [first,last)
- * \return the rightmost match, or last if not found
- */
iterator
- findRightmostAmongExact(const Interest& interest, iterator first, iterator last) const;
+ findImpl(const Interest& interest) const;
void
setPolicyImpl(unique_ptr<Policy> policy);