table: ContentStore enumeration
refs #2254
Change-Id: Ic440afea2197f12f7720adb559b836d08e864bed
diff --git a/daemon/table/cs-entry-impl.cpp b/daemon/table/cs-entry-impl.cpp
new file mode 100644
index 0000000..c97d692
--- /dev/null
+++ b/daemon/table/cs-entry-impl.cpp
@@ -0,0 +1,86 @@
+/* -*- 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 "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)
+ : queueType(QUEUE_NONE)
+{
+ this->setData(data, isUnsolicited);
+ BOOST_ASSERT(!this->isQuery());
+}
+
+bool
+EntryImpl::isQuery() const
+{
+ return !this->hasData();
+}
+
+bool
+EntryImpl::canStale() const
+{
+ BOOST_ASSERT(!this->isQuery());
+ return this->getStaleTime() < time::steady_clock::TimePoint::max();
+}
+
+void
+EntryImpl::unsetUnsolicited()
+{
+ BOOST_ASSERT(!this->isQuery());
+ this->setData(this->getData(), false);
+}
+
+bool
+EntryImpl::operator<(const EntryImpl& other) const
+{
+ if (this->isQuery()) {
+ if (other.isQuery()) {
+ return m_queryName < other.m_queryName;
+ }
+ else {
+ return m_queryName < other.m_queryName;
+ }
+ }
+ else {
+ if (other.isQuery()) {
+ return this->getFullName() < other.m_queryName;
+ }
+ else {
+ return this->getFullName() < other.getFullName();
+ }
+ }
+}
+
+} // namespace cs
+} // namespace nfd
diff --git a/daemon/table/cs-entry-impl.hpp b/daemon/table/cs-entry-impl.hpp
new file mode 100644
index 0000000..0732047
--- /dev/null
+++ b/daemon/table/cs-entry-impl.hpp
@@ -0,0 +1,84 @@
+/* -*- 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_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
+#define NFD_DAEMON_TABLE_CS_ENTRY_IMPL_HPP
+
+#include "cs-internal.hpp"
+#include "cs-entry.hpp"
+#include "core/scheduler.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);
+
+ /** \return true if entry can become stale, false if entry is never stale
+ */
+ bool
+ canStale() const;
+
+ void
+ unsetUnsolicited();
+
+ bool
+ operator<(const EntryImpl& other) const;
+
+private:
+ bool
+ isQuery() const;
+
+public:
+ QueueType queueType;
+ QueueIt queueIt;
+ scheduler::EventId moveStaleEvent;
+
+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 584dda3..d4f3921 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -28,91 +28,38 @@
namespace nfd {
namespace cs {
-Entry::Entry(const Name& name)
- : m_queryName(name)
+void
+Entry::setData(shared_ptr<const Data> data, bool isUnsolicited)
{
- BOOST_ASSERT(this->isQuery());
-}
+ m_data = data;
+ m_isUnsolicited = isUnsolicited;
-Entry::Entry(shared_ptr<const Data> data, bool isUnsolicited)
- : queueType(Cs::QUEUE_NONE)
- , m_data(data)
- , m_isUnsolicited(isUnsolicited)
-{
- BOOST_ASSERT(!this->isQuery());
-}
-
-bool
-Entry::isQuery() const
-{
- return m_data == nullptr;
-}
-
-shared_ptr<const Data>
-Entry::getData() const
-{
- BOOST_ASSERT(!this->isQuery());
- return m_data;
-}
-
-const Name&
-Entry::getName() const
-{
- BOOST_ASSERT(!this->isQuery());
- return m_data->getName();
-}
-
-const Name&
-Entry::getFullName() const
-{
- BOOST_ASSERT(!this->isQuery());
- return m_data->getFullName();
-}
-
-bool
-Entry::canStale() const
-{
- BOOST_ASSERT(!this->isQuery());
- return m_data->getFreshnessPeriod() >= time::milliseconds::zero();
+ updateStaleTime();
}
bool
Entry::isStale() const
{
- BOOST_ASSERT(!this->isQuery());
- return time::steady_clock::now() > m_staleAt;
+ BOOST_ASSERT(this->hasData());
+ return m_staleTime < time::steady_clock::now();
}
void
-Entry::refresh()
+Entry::updateStaleTime()
{
- BOOST_ASSERT(!this->isQuery());
- if (this->canStale()) {
- m_staleAt = time::steady_clock::now() + time::milliseconds(m_data->getFreshnessPeriod());
+ BOOST_ASSERT(this->hasData());
+ if (m_data->getFreshnessPeriod() >= time::milliseconds::zero()) {
+ m_staleTime = time::steady_clock::now() + time::milliseconds(m_data->getFreshnessPeriod());
}
else {
- m_staleAt = time::steady_clock::TimePoint::max();
+ m_staleTime = time::steady_clock::TimePoint::max();
}
}
bool
-Entry::isUnsolicited() const
-{
- BOOST_ASSERT(!this->isQuery());
- return m_isUnsolicited;
-}
-
-void
-Entry::unsetUnsolicited()
-{
- BOOST_ASSERT(!this->isQuery());
- m_isUnsolicited = false;
-}
-
-bool
Entry::canSatisfy(const Interest& interest) const
{
- BOOST_ASSERT(!this->isQuery());
+ BOOST_ASSERT(this->hasData());
if (!interest.matchesData(*m_data)) {
return false;
}
@@ -124,25 +71,12 @@
return true;
}
-bool
-Entry::operator<(const Entry& other) const
+void
+Entry::reset()
{
- if (this->isQuery()) {
- if (other.isQuery()) {
- return m_queryName < other.m_queryName;
- }
- else {
- return m_queryName < other.m_queryName;
- }
- }
- else {
- if (other.isQuery()) {
- return this->getFullName() < other.m_queryName;
- }
- else {
- return this->getFullName() < other.getFullName();
- }
- }
+ m_data.reset();
+ m_isUnsolicited = false;
+ m_staleTime = time::steady_clock::TimePoint();
}
} // namespace cs
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index a35d9e9..fe7846c 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -26,81 +26,117 @@
#ifndef NFD_DAEMON_TABLE_CS_ENTRY_HPP
#define NFD_DAEMON_TABLE_CS_ENTRY_HPP
-#include "cs.hpp"
-#include "core/scheduler.hpp"
+#include "common.hpp"
namespace nfd {
namespace cs {
-/** \brief an Entry in ContentStore
- * \note This type is internal to ContentStore.
- *
- * 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.
+/** \brief represents a base class for CS entry
*/
class 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
+public: // exposed through ContentStore enumeration
+ /** \return the stored Data
+ * \pre hasData()
*/
- Entry(const Name& name);
+ const Data&
+ getData() const
+ {
+ BOOST_ASSERT(this->hasData());
+ return *m_data;
+ }
- /** \brief construct Entry for storage
+ /** \return Name of the stored Data
+ * \pre hasData()
*/
- Entry(shared_ptr<const Data> data, bool isUnsolicited);
-
- shared_ptr<const Data>
- getData() const;
-
const Name&
- getName() const;
+ getName() const
+ {
+ BOOST_ASSERT(this->hasData());
+ return m_data->getName();
+ }
+ /** \return full name (including implicit digest) of the stored Data
+ * \pre hasData()
+ */
const Name&
- getFullName() const;
+ getFullName() const
+ {
+ BOOST_ASSERT(this->hasData());
+ return m_data->getFullName();
+ }
- /** \return true if entry can become stale, false if entry is never stale
+ /** \return whether the stored Data is unsolicited
+ * \pre hasData()
*/
bool
- canStale() const;
+ isUnsolicited() const
+ {
+ BOOST_ASSERT(this->hasData());
+ return m_isUnsolicited;
+ }
+ /** \return the absolute time when the stored Data becomes expired
+ * \retval time::steady_clock::TimePoint::max() if the stored Data never expires
+ * \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()
+ */
bool
isStale() const;
- void
- refresh();
-
- bool
- isUnsolicited() const;
-
- void
- unsetUnsolicited();
-
- /** \brief determines whether Interest can be satisified by this cached Data
+ /** \brief determines whether Interest can be satisified by the stored Data
* \note ChildSelector is not considered
+ * \pre hasData()
*/
bool
canSatisfy(const Interest& interest) const;
+public: // used by generic ContentStore implementation
+ /** \return true if a Data packet is stored
+ */
bool
- operator<(const Entry& other) const;
+ hasData() const
+ {
+ return m_data != nullptr;
+ }
+
+ /** \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:
- bool
- isQuery() const;
-
-public:
- Cs::QueueType queueType;
- Cs::QueueIt queueIt;
- scheduler::EventId moveStaleEvent;
-
-private:
- Name m_queryName;
shared_ptr<const Data> m_data;
- time::steady_clock::TimePoint m_staleAt;
bool m_isUnsolicited;
+ time::steady_clock::TimePoint m_staleTime;
};
} // namespace cs
diff --git a/daemon/table/cs-internal.hpp b/daemon/table/cs-internal.hpp
new file mode 100644
index 0000000..7df3d06
--- /dev/null
+++ b/daemon/table/cs-internal.hpp
@@ -0,0 +1,57 @@
+/* -*- 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/>.
+ */
+
+/** \file
+ * \brief declares ContentStore internal types
+ */
+
+#ifndef NFD_DAEMON_TABLE_CS_INTERNAL_HPP
+#define NFD_DAEMON_TABLE_CS_INTERNAL_HPP
+
+#include "common.hpp"
+
+namespace nfd {
+namespace cs {
+
+class EntryImpl;
+
+typedef std::set<EntryImpl> Table;
+typedef Table::const_iterator TableIt;
+
+typedef std::list<TableIt> Queue;
+typedef Queue::iterator QueueIt;
+
+enum QueueType {
+ QUEUE_UNSOLICITED,
+ QUEUE_STALE,
+ QUEUE_FIFO,
+ QUEUE_MAX,
+ QUEUE_NONE = QUEUE_MAX
+};
+
+} // namespace cs
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CS_INTERNAL_HPP
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index 3bc816a..e1e8e73 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -24,7 +24,6 @@
*/
#include "cs.hpp"
-#include "cs-entry.hpp"
#include "core/logger.hpp"
#include "core/algorithm.hpp"
#include <numeric>
@@ -34,18 +33,23 @@
namespace nfd {
namespace cs {
+// http://en.cppreference.com/w/cpp/concept/ForwardIterator
+BOOST_CONCEPT_ASSERT((boost::ForwardIterator<Cs::const_iterator>));
+// boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
+// which doesn't require DefaultConstructible
+#ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
+static_assert(std::is_default_constructible<Cs::const_iterator>::value,
+ "Cs::const_iterator must be default-constructible");
+#else
+BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Cs::const_iterator>));
+#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
+
Cs::Cs(size_t nMaxPackets)
: m_limit(nMaxPackets)
{
BOOST_ASSERT(nMaxPackets > 0);
}
-Cs::~Cs()
-{
- // It's necessary to put this empty destructor in cs.cpp,
- // because cs::Entry has incomplete type in cs.hpp.
-}
-
void
Cs::setLimit(size_t nMaxPackets)
{
@@ -54,12 +58,6 @@
this->evict();
}
-size_t
-Cs::size() const
-{
- return m_table.size();
-}
-
bool
Cs::insert(const Data& data, bool isUnsolicited)
{
@@ -67,8 +65,8 @@
bool isNewEntry = false; TableIt it;
// use .insert because gcc46 does not support .emplace
- std::tie(it, isNewEntry) = m_table.insert(Entry(data.shared_from_this(), isUnsolicited));
- Entry& entry = const_cast<Entry&>(*it);
+ std::tie(it, isNewEntry) = m_table.insert(EntryImpl(data.shared_from_this(), isUnsolicited));
+ EntryImpl& entry = const_cast<EntryImpl&>(*it);
if (!isNewEntry) { // existing entry
this->detachQueue(it);
@@ -77,11 +75,11 @@
entry.unsetUnsolicited();
}
}
- entry.refresh();
+ entry.updateStaleTime();
this->attachQueue(it);
// check there are same amount of entries in the table and in queues
- BOOST_ASSERT(m_table.size() == std::accumulate(m_queues, m_queues + QUEUE_UBOUND, 0U,
+ BOOST_ASSERT(m_table.size() == std::accumulate(m_queues, m_queues + QUEUE_MAX, 0U,
[] (size_t sum, const Queue queue) { return sum + queue.size(); }));
this->evict(); // XXX The new entry could be evicted, but it shouldn't matter.
@@ -115,16 +113,16 @@
return nullptr;
}
NFD_LOG_DEBUG(" matching " << match->getName());
- return match->getData().get();
+ return &match->getData();
}
-Cs::TableIt
+TableIt
Cs::findLeftmost(const Interest& interest, TableIt first, TableIt last) const
{
- return std::find_if(first, last, bind(&cs::Entry::canSatisfy, _1, interest));
+ return std::find_if(first, last, bind(&cs::EntryImpl::canSatisfy, _1, interest));
}
-Cs::TableIt
+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.
@@ -156,16 +154,16 @@
return last;
}
-Cs::TableIt
+TableIt
Cs::findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const
{
- return find_last_if(first, last, bind(&Entry::canSatisfy, _1, interest));
+ return find_last_if(first, last, bind(&EntryImpl::canSatisfy, _1, interest));
}
void
Cs::attachQueue(TableIt it)
{
- Entry& entry = const_cast<Entry&>(*it);
+ EntryImpl& entry = const_cast<EntryImpl&>(*it);
if (entry.queueType != QUEUE_NONE) {
this->detachQueue(it);
@@ -181,7 +179,7 @@
entry.queueType = QUEUE_FIFO;
if (entry.canStale()) {
- entry.moveStaleEvent = scheduler::schedule(entry.getData()->getFreshnessPeriod(),
+ entry.moveStaleEvent = scheduler::schedule(entry.getData().getFreshnessPeriod(),
bind(&Cs::moveToStaleQueue, this, it));
}
}
@@ -193,7 +191,7 @@
void
Cs::detachQueue(TableIt it)
{
- Entry& entry = const_cast<Entry&>(*it);
+ EntryImpl& entry = const_cast<EntryImpl&>(*it);
BOOST_ASSERT(entry.queueType != QUEUE_NONE);
@@ -208,7 +206,7 @@
void
Cs::moveToStaleQueue(TableIt it)
{
- Entry& entry = const_cast<Entry&>(*it);
+ EntryImpl& entry = const_cast<EntryImpl&>(*it);
BOOST_ASSERT(entry.queueType == QUEUE_FIFO);
m_queues[QUEUE_FIFO].erase(entry.queueIt);
@@ -218,7 +216,7 @@
entry.queueIt = queue.insert(queue.end(), it);
}
-std::tuple<Cs::TableIt, std::string>
+std::tuple<TableIt, std::string>
Cs::evictPick()
{
if (!m_queues[QUEUE_UNSOLICITED].empty()) {
@@ -253,7 +251,7 @@
Cs::dump()
{
NFD_LOG_DEBUG("dump table");
- for (const Entry& entry : m_table) {
+ for (const EntryImpl& entry : m_table) {
NFD_LOG_TRACE(entry.getFullName());
}
}
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index 5bab097..77a4474 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -48,13 +48,12 @@
#ifndef NFD_DAEMON_TABLE_CS_HPP
#define NFD_DAEMON_TABLE_CS_HPP
-#include "common.hpp"
+#include "cs-entry-impl.hpp"
+#include <boost/iterator/transform_iterator.hpp>
namespace nfd {
namespace cs {
-class Entry;
-
/** \brief represents the ContentStore
*/
class Cs : noncopyable
@@ -63,8 +62,6 @@
explicit
Cs(size_t nMaxPackets = 10);
- ~Cs();
-
/** \brief inserts a Data packet
* \return true
*/
@@ -98,26 +95,44 @@
/** \return number of stored packets
*/
size_t
- size() const;
+ size() const
+ {
+ return m_table.size();
+ }
PUBLIC_WITH_TESTS_ELSE_PRIVATE:
void
dump();
-public:
- typedef std::set<Entry> Table;
- typedef Table::const_iterator TableIt;
- typedef std::list<TableIt> Queue;
- typedef Queue::iterator QueueIt;
- enum QueueType {
- QUEUE_UNSOLICITED,
- QUEUE_STALE,
- QUEUE_FIFO,
- QUEUE_UBOUND,
- QUEUE_NONE = QUEUE_UBOUND
+public: // enumeration
+ struct EntryFromEntryImpl
+ {
+ typedef const Entry& result_type;
+
+ const Entry&
+ operator()(const EntryImpl& entry) const
+ {
+ return entry;
+ }
};
-private:
+ /** \brief ContentStore iterator (public API)
+ */
+ typedef boost::transform_iterator<EntryFromEntryImpl, TableIt, const Entry&> const_iterator;
+
+ const_iterator
+ begin() const
+ {
+ return boost::make_transform_iterator(m_table.begin(), EntryFromEntryImpl());
+ }
+
+ const_iterator
+ end() const
+ {
+ 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
*/
@@ -136,6 +151,7 @@
TableIt
findRightmostAmongExact(const Interest& interest, TableIt first, TableIt last) const;
+private: // cleanup
/** \brief attaches an entry to a suitable cleanup queue
* \note if the entry is already attached to a queue, it's automatically detached
*/
@@ -167,7 +183,7 @@
private:
size_t m_limit;
Table m_table;
- Queue m_queues[QUEUE_UBOUND];
+ Queue m_queues[QUEUE_MAX];
};
} // namespace cs