cs: avoid Entry construction during query
Using C++14's transparent comparators, CS lookup logic can
compare stored Entry objects with the queried Name without
constructing an Entry object. This in turn eliminates the need
for a special "query entry", so EntryImpl class is deleted.
refs #4914
Change-Id: I5b05a1ab9ad696e79f7ebd6045be8de11cd58ee6
diff --git a/daemon/table/cs-entry-impl.cpp b/daemon/table/cs-entry-impl.cpp
deleted file mode 100644
index f3ce820..0000000
--- a/daemon/table/cs-entry-impl.cpp
+++ /dev/null
@@ -1,110 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2014-2019, 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 "cs-entry-impl.hpp"
-
-namespace nfd {
-namespace cs {
-
-EntryImpl::EntryImpl(const Name& name)
- : m_queryName(name)
-{
- BOOST_ASSERT(this->isQuery());
-}
-
-EntryImpl::EntryImpl(shared_ptr<const Data> data, bool isUnsolicited)
-{
- this->setData(data, isUnsolicited);
- BOOST_ASSERT(!this->isQuery());
-}
-
-bool
-EntryImpl::isQuery() const
-{
- return !this->hasData();
-}
-
-void
-EntryImpl::unsetUnsolicited()
-{
- BOOST_ASSERT(!this->isQuery());
- this->setData(this->getData(), false);
-}
-
-static int
-compareQueryWithData(const Name& queryName, const Data& data)
-{
- bool queryIsFullName = !queryName.empty() && queryName[-1].isImplicitSha256Digest();
-
- int cmp = queryIsFullName ?
- queryName.compare(0, queryName.size() - 1, data.getName()) :
- queryName.compare(data.getName());
-
- if (cmp != 0) { // Name without digest differs
- return cmp;
- }
-
- if (queryIsFullName) { // Name without digest equals, compare digest
- return queryName[-1].compare(data.getFullName()[-1]);
- }
- else { // queryName is a proper prefix of Data fullName
- return -1;
- }
-}
-
-static int
-compareDataWithData(const Data& lhs, const Data& rhs)
-{
- int cmp = lhs.getName().compare(rhs.getName());
- if (cmp != 0) {
- return cmp;
- }
-
- return lhs.getFullName()[-1].compare(rhs.getFullName()[-1]);
-}
-
-bool
-EntryImpl::operator<(const EntryImpl& other) const
-{
- if (this->isQuery()) {
- if (other.isQuery()) {
- return m_queryName < other.m_queryName;
- }
- else {
- return compareQueryWithData(m_queryName, other.getData()) < 0;
- }
- }
- else {
- if (other.isQuery()) {
- return compareQueryWithData(other.m_queryName, this->getData()) > 0;
- }
- else {
- return compareDataWithData(this->getData(), other.getData()) < 0;
- }
- }
-}
-
-} // namespace cs
-} // namespace nfd
diff --git a/daemon/table/cs-entry-impl.hpp b/daemon/table/cs-entry-impl.hpp
deleted file mode 100644
index 262fcd1..0000000
--- a/daemon/table/cs-entry-impl.hpp
+++ /dev/null
@@ -1,72 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2017, 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_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
-#define NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
-
-#include "cs-entry.hpp"
-
-namespace nfd {
-namespace cs {
-
-/** \brief an Entry in ContentStore implementation
- *
- * An Entry is either a stored Entry which contains a Data packet and related attributes,
- * or a query Entry which contains a Name that is LessComparable to other stored/query Entry
- * and is used to lookup a container of entries.
- *
- * \note This type is internal to this specific ContentStore implementation.
- */
-class EntryImpl : public Entry
-{
-public:
- /** \brief construct Entry for query
- * \note Name is implicitly convertible to Entry, so that Name can be passed to
- * lookup functions on a container of Entry
- */
- EntryImpl(const Name& name);
-
- /** \brief construct Entry for storage
- */
- EntryImpl(shared_ptr<const Data> data, bool isUnsolicited);
-
- void
- unsetUnsolicited();
-
- bool
- operator<(const EntryImpl& other) const;
-
-private:
- bool
- isQuery() const;
-
-private:
- Name m_queryName;
-};
-
-} // namespace cs
-} // namespace nfd
-
-#endif // NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
diff --git a/daemon/table/cs-entry.cpp b/daemon/table/cs-entry.cpp
index 15b5a6f..470e850 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -28,50 +28,87 @@
namespace nfd {
namespace cs {
-void
-Entry::setData(shared_ptr<const Data> data, bool isUnsolicited)
+Entry::Entry(shared_ptr<const Data> data, bool isUnsolicited)
+ : m_data(std::move(data))
+ , m_isUnsolicited(isUnsolicited)
{
- m_data = std::move(data);
- m_isUnsolicited = isUnsolicited;
-
- updateStaleTime();
+ updateFreshUntil();
}
bool
-Entry::isStale() const
+Entry::isFresh() const
{
- BOOST_ASSERT(this->hasData());
- return m_staleTime < time::steady_clock::now();
+ return m_freshUntil >= time::steady_clock::now();
}
void
-Entry::updateStaleTime()
+Entry::updateFreshUntil()
{
- BOOST_ASSERT(this->hasData());
- m_staleTime = time::steady_clock::now() + time::milliseconds(m_data->getFreshnessPeriod());
+ m_freshUntil = time::steady_clock::now() + m_data->getFreshnessPeriod();
}
bool
Entry::canSatisfy(const Interest& interest) const
{
- BOOST_ASSERT(this->hasData());
if (!interest.matchesData(*m_data)) {
return false;
}
- if (interest.getMustBeFresh() == static_cast<int>(true) && this->isStale()) {
+ if (interest.getMustBeFresh() && !this->isFresh()) {
return false;
}
return true;
}
-void
-Entry::reset()
+static int
+compareQueryWithData(const Name& queryName, const Data& data)
{
- m_data.reset();
- m_isUnsolicited = false;
- m_staleTime = time::steady_clock::TimePoint();
+ bool queryIsFullName = !queryName.empty() && queryName[-1].isImplicitSha256Digest();
+
+ int cmp = queryIsFullName ?
+ queryName.compare(0, queryName.size() - 1, data.getName()) :
+ queryName.compare(data.getName());
+
+ if (cmp != 0) { // Name without digest differs
+ return cmp;
+ }
+
+ if (queryIsFullName) { // Name without digest equals, compare digest
+ return queryName[-1].compare(data.getFullName()[-1]);
+ }
+ else { // queryName is a proper prefix of Data fullName
+ return -1;
+ }
+}
+
+static int
+compareDataWithData(const Data& lhs, const Data& rhs)
+{
+ int cmp = lhs.getName().compare(rhs.getName());
+ if (cmp != 0) {
+ return cmp;
+ }
+
+ return lhs.getFullName()[-1].compare(rhs.getFullName()[-1]);
+}
+
+bool
+operator<(const Entry& entry, const Name& queryName)
+{
+ return compareQueryWithData(queryName, entry.getData()) > 0;
+}
+
+bool
+operator<(const Name& queryName, const Entry& entry)
+{
+ return compareQueryWithData(queryName, entry.getData()) < 0;
+}
+
+bool
+operator<(const Entry& lhs, const Entry& rhs)
+{
+ return compareDataWithData(lhs.getData(), rhs.getData()) < 0;
}
} // namespace cs
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index eb30d58..eadb9f6 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -31,113 +31,92 @@
namespace nfd {
namespace cs {
-/** \brief represents a base class for CS entry
+/** \brief a ContentStore entry
*/
class Entry
{
public: // exposed through ContentStore enumeration
- /** \return the stored Data
- * \pre hasData()
+ /** \brief return the stored Data
*/
const Data&
getData() const
{
- BOOST_ASSERT(this->hasData());
return *m_data;
}
- /** \return Name of the stored Data
- * \pre hasData()
+ /** \brief return stored Data name
*/
const Name&
getName() const
{
- BOOST_ASSERT(this->hasData());
return m_data->getName();
}
- /** \return full name (including implicit digest) of the stored Data
- * \pre hasData()
+ /** \brief return full name (including implicit digest) of the stored Data
*/
const Name&
getFullName() const
{
- BOOST_ASSERT(this->hasData());
return m_data->getFullName();
}
- /** \return whether the stored Data is unsolicited
- * \pre hasData()
+ /** \brief return whether the stored Data is unsolicited
*/
bool
isUnsolicited() const
{
- BOOST_ASSERT(this->hasData());
return m_isUnsolicited;
}
- /** \return the absolute time when the stored Data becomes stale
- * \note if the returned TimePoint is in the past, the Data is stale
- * \pre hasData()
- */
- const time::steady_clock::TimePoint&
- getStaleTime() const
- {
- BOOST_ASSERT(this->hasData());
- return m_staleTime;
- }
-
- /** \brief checks if the stored Data is stale now
- * \pre hasData()
+ /** \brief check if the stored Data is fresh now
*/
bool
- isStale() const;
+ isFresh() const;
- /** \brief determines whether Interest can be satisified by the stored Data
- * \pre hasData()
+ /** \brief determine whether Interest can be satisified by the stored Data
*/
bool
canSatisfy(const Interest& interest) const;
-public: // used by generic ContentStore implementation
- /** \return true if a Data packet is stored
+public: // used by ContentStore implementation
+ Entry(shared_ptr<const Data> data, bool isUnsolicited);
+
+ /** \brief recalculate when the entry would become non-fresh, relative to current time
*/
- bool
- hasData() const
+ void
+ updateFreshUntil();
+
+ /** \brief clear 'unsolicited' flag
+ */
+ void
+ clearUnsolicited()
{
- return m_data != nullptr;
+ m_isUnsolicited = false;
}
- /** \brief replaces the stored Data
- */
- void
- setData(shared_ptr<const Data> data, bool isUnsolicited);
-
- /** \brief replaces the stored Data
- */
- void
- setData(const Data& data, bool isUnsolicited)
- {
- this->setData(data.shared_from_this(), isUnsolicited);
- }
-
- /** \brief refreshes stale time relative to current time
- */
- void
- updateStaleTime();
-
- /** \brief clears the entry
- * \post !hasData()
- */
- void
- reset();
-
private:
shared_ptr<const Data> m_data;
bool m_isUnsolicited;
- time::steady_clock::TimePoint m_staleTime;
+ time::steady_clock::TimePoint m_freshUntil;
};
+bool
+operator<(const Entry& entry, const Name& queryName);
+
+bool
+operator<(const Name& queryName, const Entry& entry);
+
+bool
+operator<(const Entry& lhs, const Entry& rhs);
+
+/** \brief an ordered container of ContentStore entries
+ *
+ * This container uses std::less<> comparator to enable lookup with queryName.
+ */
+using Table = std::set<Entry, std::less<>>;
+
+using iterator = Table::const_iterator;
+
} // namespace cs
} // namespace nfd
diff --git a/daemon/table/cs-internal.hpp b/daemon/table/cs-internal.hpp
deleted file mode 100644
index d240801..0000000
--- a/daemon/table/cs-internal.hpp
+++ /dev/null
@@ -1,46 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2014-2019, 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/>.
- */
-
-/** \file
- * \brief declares ContentStore internal types
- */
-
-#ifndef NFD_DAEMON_TABLE_CS_INTERNAL_HPP
-#define NFD_DAEMON_TABLE_CS_INTERNAL_HPP
-
-#include "core/common.hpp"
-
-namespace nfd {
-namespace cs {
-
-class EntryImpl;
-
-using Table = std::set<EntryImpl>;
-using iterator = Table::const_iterator;
-
-} // namespace cs
-} // namespace nfd
-
-#endif // NFD_DAEMON_TABLE_CS_INTERNAL_HPP
diff --git a/daemon/table/cs-policy-priority-fifo.cpp b/daemon/table/cs-policy-priority-fifo.cpp
index db13013..3c604ce 100644
--- a/daemon/table/cs-policy-priority-fifo.cpp
+++ b/daemon/table/cs-policy-priority-fifo.cpp
@@ -113,7 +113,7 @@
if (i->isUnsolicited()) {
entryInfo->queueType = QUEUE_UNSOLICITED;
}
- else if (i->isStale()) {
+ else if (!i->isFresh()) {
entryInfo->queueType = QUEUE_STALE;
}
else {
diff --git a/daemon/table/cs-policy.hpp b/daemon/table/cs-policy.hpp
index 93e028e..f50f854 100644
--- a/daemon/table/cs-policy.hpp
+++ b/daemon/table/cs-policy.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016, 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,
@@ -26,8 +26,7 @@
#ifndef NFD_DAEMON_TABLE_CS_POLICY_HPP
#define NFD_DAEMON_TABLE_CS_POLICY_HPP
-#include "cs-internal.hpp"
-#include "cs-entry-impl.hpp"
+#include "cs-entry.hpp"
namespace nfd {
namespace cs {
@@ -67,23 +66,36 @@
~Policy() = default;
const std::string&
- getName() const;
+ getName() const
+ {
+ return m_policyName;
+ }
+
public:
/** \brief gets cs
*/
Cs*
- getCs() const;
+ getCs() const
+ {
+ return m_cs;
+ }
/** \brief sets cs
*/
void
- setCs(Cs *cs);
+ setCs(Cs* cs)
+ {
+ m_cs = cs;
+ }
/** \brief gets hard limit (in number of entries)
*/
size_t
- getLimit() const;
+ getLimit() const
+ {
+ return m_limit;
+ }
/** \brief sets hard limit (in number of entries)
* \post getLimit() == nMaxEntries
@@ -189,30 +201,6 @@
Cs* m_cs;
};
-inline const std::string&
-Policy::getName() const
-{
- return m_policyName;
-}
-
-inline Cs*
-Policy::getCs() const
-{
- return m_cs;
-}
-
-inline void
-Policy::setCs(Cs *cs)
-{
- m_cs = cs;
-}
-
-inline size_t
-Policy::getLimit() const
-{
- return m_limit;
-}
-
} // namespace cs
} // namespace nfd
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index a086cac..a73303f 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -69,14 +69,14 @@
iterator it;
bool isNewEntry = false;
std::tie(it, isNewEntry) = m_table.emplace(data.shared_from_this(), isUnsolicited);
- EntryImpl& entry = const_cast<EntryImpl&>(*it);
+ Entry& entry = const_cast<Entry&>(*it);
- entry.updateStaleTime();
+ entry.updateFreshUntil();
if (!isNewEntry) { // existing entry
// XXX This doesn't forbid unsolicited Data from refreshing a solicited entry.
if (entry.isUnsolicited() && !isUnsolicited) {
- entry.unsetUnsolicited();
+ entry.clearUnsolicited();
}
m_policy->afterRefresh(it);
@@ -137,7 +137,7 @@
Cs::dump()
{
NFD_LOG_DEBUG("dump table");
- for (const EntryImpl& entry : m_table) {
+ for (const Entry& entry : m_table) {
NFD_LOG_TRACE(entry.getFullName());
}
}
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index df6c88b..1d15294 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -27,10 +27,6 @@
#define NFD_DAEMON_TABLE_CS_HPP
#include "cs-policy.hpp"
-#include "cs-internal.hpp"
-#include "cs-entry-impl.hpp"
-
-#include <boost/iterator/transform_iterator.hpp>
namespace nfd {
namespace cs {
@@ -162,32 +158,20 @@
enableServe(bool shouldServe);
public: // enumeration
- class EntryFromEntryImpl
- {
- public:
- typedef const Entry& result_type;
-
- const Entry&
- operator()(const EntryImpl& entry) const
- {
- return entry;
- }
- };
-
/** \brief ContentStore iterator (public API)
*/
- using const_iterator = boost::transform_iterator<EntryFromEntryImpl, iterator, const Entry&>;
+ using const_iterator = iterator;
const_iterator
begin() const
{
- return boost::make_transform_iterator(m_table.begin(), EntryFromEntryImpl());
+ return m_table.begin();
}
const_iterator
end() const
{
- return boost::make_transform_iterator(m_table.end(), EntryFromEntryImpl());
+ return m_table.end();
}
private: