table: Allow iteration over CS entries
Change-Id: I23bf0da9a853de70187c9e72a0f7a5cb98107fbd
Refs: #2340
diff --git a/daemon/table/cs-entry.cpp b/daemon/table/cs-entry.cpp
index 1262065..0bcdefc 100644
--- a/daemon/table/cs-entry.cpp
+++ b/daemon/table/cs-entry.cpp
@@ -35,12 +35,9 @@
NFD_LOG_INIT("CsEntry");
-void
-Entry::release()
+Entry::Entry()
+ : m_isUnsolicited(false)
{
- BOOST_ASSERT(m_layerIterators.empty());
-
- m_dataPacket.reset();
}
void
@@ -58,27 +55,18 @@
m_staleAt = time::steady_clock::now() + m_dataPacket->getFreshnessPeriod();
}
-void
-Entry::setIterator(int layer, const Entry::LayerIterators::mapped_type& layerIterator)
+bool
+Entry::isStale() const
{
- m_layerIterators[layer] = layerIterator;
+ return m_staleAt < time::steady_clock::now();
}
void
-Entry::removeIterator(int layer)
+Entry::reset()
{
- m_layerIterators.erase(layer);
-}
-
-void
-Entry::printIterators() const
-{
- for (LayerIterators::const_iterator it = m_layerIterators.begin();
- it != m_layerIterators.end();
- ++it)
- {
- NFD_LOG_TRACE("[" << it->first << "]" << " " << &(*it->second));
- }
+ m_staleAt = time::steady_clock::TimePoint();
+ m_dataPacket.reset();
+ m_isUnsolicited = false;
}
} // namespace cs
diff --git a/daemon/table/cs-entry.hpp b/daemon/table/cs-entry.hpp
index 0373e60..e922ffd 100644
--- a/daemon/table/cs-entry.hpp
+++ b/daemon/table/cs-entry.hpp
@@ -37,20 +37,13 @@
class Entry;
-/** \brief represents a CS entry
+/** \brief represents a base class for CS entry
*/
class Entry : noncopyable
{
public:
- typedef std::map<int, std::list<Entry*>::iterator > LayerIterators;
-
Entry();
- /** \brief releases reference counts on shared objects
- */
- void
- release();
-
/** \brief returns the name of the Data packet stored in the CS entry
* \return{ NDN name }
*/
@@ -71,12 +64,6 @@
bool
isUnsolicited() const;
- /** \brief returns the absolute time when Data becomes expired
- * \return{ Time (resolution up to time::milliseconds) }
- */
- const time::steady_clock::TimePoint&
- getStaleTime() const;
-
/** \brief returns the Data packet stored in the CS entry
*/
const Data&
@@ -87,62 +74,54 @@
void
setData(const Data& data, bool isUnsolicited);
+ /** \brief returns the absolute time when Data becomes expired
+ * \return{ Time (resolution up to time::milliseconds) }
+ */
+ const time::steady_clock::TimePoint&
+ getStaleTime() const;
+
/** \brief refreshes the time when Data becomes expired
* according to the current absolute time.
*/
void
updateStaleTime();
- /** \brief saves the iterator pointing to the CS entry on a specific layer of skip list
+ /** \brief checks if the stored Data is stale
+ */
+ bool
+ isStale() const;
+
+ /** \brief clears CS entry
+ * After reset, *this == Entry()
*/
void
- setIterator(int layer, const LayerIterators::mapped_type& layerIterator);
-
- /** \brief removes the iterator pointing to the CS entry on a specific layer of skip list
- */
- void
- removeIterator(int layer);
-
- /** \brief returns the table containing <layer, iterator> pairs.
- */
- const LayerIterators&
- getIterators() const;
-
-private:
- /** \brief prints <layer, iterator> pairs.
- */
- void
- printIterators() const;
+ reset();
private:
time::steady_clock::TimePoint m_staleAt;
shared_ptr<const Data> m_dataPacket;
bool m_isUnsolicited;
-
- LayerIterators m_layerIterators;
};
-inline
-Entry::Entry()
-{
-}
-
inline const Name&
Entry::getName() const
{
+ BOOST_ASSERT(m_dataPacket != nullptr);
return m_dataPacket->getName();
}
inline const Name&
Entry::getFullName() const
{
+ BOOST_ASSERT(m_dataPacket != nullptr);
return m_dataPacket->getFullName();
}
inline const Data&
Entry::getData() const
{
+ BOOST_ASSERT(m_dataPacket != nullptr);
return *m_dataPacket;
}
@@ -158,12 +137,6 @@
return m_staleAt;
}
-inline const Entry::LayerIterators&
-Entry::getIterators() const
-{
- return m_layerIterators;
-}
-
} // namespace cs
} // namespace nfd
diff --git a/daemon/table/cs-skip-list-entry.cpp b/daemon/table/cs-skip-list-entry.cpp
new file mode 100644
index 0000000..a05f0d1
--- /dev/null
+++ b/daemon/table/cs-skip-list-entry.cpp
@@ -0,0 +1,72 @@
+/* -*- 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
+ *
+ * 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/>.
+ *
+ * \author Ilya Moiseenko <http://ilyamoiseenko.com/>
+ * \author Junxiao Shi <http://www.cs.arizona.edu/people/shijunxiao/>
+ * \author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html>
+ */
+
+#include "cs-skip-list-entry.hpp"
+#include "core/logger.hpp"
+
+namespace nfd {
+namespace cs {
+namespace skip_list {
+
+NFD_LOG_INIT("CsSkipListEntry");
+
+void
+Entry::release()
+{
+ BOOST_ASSERT(m_layerIterators.empty());
+
+ reset();
+}
+
+void
+Entry::setIterator(int layer, const Entry::LayerIterators::mapped_type& layerIterator)
+{
+ m_layerIterators[layer] = layerIterator;
+}
+
+void
+Entry::removeIterator(int layer)
+{
+ m_layerIterators.erase(layer);
+}
+
+void
+Entry::printIterators() const
+{
+ for (LayerIterators::const_iterator it = m_layerIterators.begin();
+ it != m_layerIterators.end();
+ ++it)
+ {
+ NFD_LOG_TRACE("[" << it->first << "]" << " " << &(*it->second));
+ }
+}
+
+} // namespace skip_list
+} // namespace cs
+} // namespace nfd
diff --git a/daemon/table/cs-skip-list-entry.hpp b/daemon/table/cs-skip-list-entry.hpp
new file mode 100644
index 0000000..1328cc0
--- /dev/null
+++ b/daemon/table/cs-skip-list-entry.hpp
@@ -0,0 +1,89 @@
+/* -*- 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
+ *
+ * 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/>.
+ *
+ * \author Ilya Moiseenko <http://ilyamoiseenko.com/>
+ * \author Junxiao Shi <http://www.cs.arizona.edu/people/shijunxiao/>
+ * \author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html>
+ */
+
+#ifndef NFD_DAEMON_TABLE_CS_SKIP_LIST_ENTRY_HPP
+#define NFD_DAEMON_TABLE_CS_SKIP_LIST_ENTRY_HPP
+
+#include "common.hpp"
+#include "cs-entry.hpp"
+
+namespace nfd {
+namespace cs {
+namespace skip_list {
+
+/** \brief represents an entry in a CS with skip list implementation
+ */
+class Entry : public cs::Entry
+{
+public:
+ typedef std::map<int, std::list<Entry*>::iterator > LayerIterators;
+
+ Entry() = default;
+
+ /** \brief releases reference counts on shared objects
+ */
+ void
+ release();
+
+ /** \brief saves the iterator pointing to the CS entry on a specific layer of skip list
+ */
+ void
+ setIterator(int layer, const LayerIterators::mapped_type& layerIterator);
+
+ /** \brief removes the iterator pointing to the CS entry on a specific layer of skip list
+ */
+ void
+ removeIterator(int layer);
+
+ /** \brief returns the table containing <layer, iterator> pairs.
+ */
+ const LayerIterators&
+ getIterators() const;
+
+private:
+ /** \brief prints <layer, iterator> pairs.
+ */
+ void
+ printIterators() const;
+
+private:
+ LayerIterators m_layerIterators;
+};
+
+inline const Entry::LayerIterators&
+Entry::getIterators() const
+{
+ return m_layerIterators;
+}
+
+} // namespace skip_list
+} // namespace cs
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_CS_SKIP_LIST_ENTRY_HPP
diff --git a/daemon/table/cs.cpp b/daemon/table/cs.cpp
index 1654bb2..d976def 100644
--- a/daemon/table/cs.cpp
+++ b/daemon/table/cs.cpp
@@ -35,6 +35,9 @@
#include <ndn-cxx/security/signature-sha256-with-rsa.hpp>
#include <boost/random/bernoulli_distribution.hpp>
+#include <boost/concept/assert.hpp>
+#include <boost/concept_check.hpp>
+#include <type_traits>
/// max skip list layers
static const size_t SKIPLIST_MAX_LAYERS = 32;
@@ -45,6 +48,17 @@
namespace nfd {
+// 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_nMaxPackets(nMaxPackets)
, m_nPackets(0)
@@ -53,7 +67,7 @@
m_skipList.push_back(zeroLayer);
for (size_t i = 0; i < m_nMaxPackets; i++)
- m_freeCsEntries.push(new cs::Entry());
+ m_freeCsEntries.push(new cs::skip_list::Entry());
}
Cs::~Cs()
@@ -89,7 +103,7 @@
if (m_nMaxPackets >= oldNMaxPackets) {
for (size_t i = oldNMaxPackets; i < m_nMaxPackets; i++) {
- m_freeCsEntries.push(new cs::Entry());
+ m_freeCsEntries.push(new cs::skip_list::Entry());
}
}
else {
@@ -107,7 +121,7 @@
}
//Reference: "Skip Lists: A Probabilistic Alternative to Balanced Trees" by W.Pugh
-std::pair<cs::Entry*, bool>
+std::pair<cs::skip_list::Entry*, bool>
Cs::insertToSkipList(const Data& data, bool isUnsolicited)
{
NFD_LOG_TRACE("insertToSkipList() " << data.getFullName() << ", "
@@ -117,7 +131,7 @@
BOOST_ASSERT(m_freeCsEntries.size() > 0);
// take entry for the memory pool
- cs::Entry* entry = m_freeCsEntries.front();
+ cs::skip_list::Entry* entry = m_freeCsEntries.front();
m_freeCsEntries.pop();
m_nPackets++;
entry->setData(data, isUnsolicited);
@@ -258,7 +272,7 @@
}
//pointer and insertion status
- std::pair<cs::Entry*, bool> entry = insertToSkipList(data, isUnsolicited);
+ std::pair<cs::skip_list::Entry*, bool> entry = insertToSkipList(data, isUnsolicited);
//new entry
if (static_cast<bool>(entry.first) && (entry.second == true))
@@ -294,14 +308,14 @@
}
bool
-Cs::eraseFromSkipList(cs::Entry* entry)
+Cs::eraseFromSkipList(cs::skip_list::Entry* entry)
{
NFD_LOG_TRACE("eraseFromSkipList() " << entry->getFullName());
NFD_LOG_TRACE("SkipList size " << size());
bool isErased = false;
- const std::map<int, std::list<cs::Entry*>::iterator>& iterators = entry->getIterators();
+ const std::map<int, std::list<cs::skip_list::Entry*>::iterator>& iterators = entry->getIterators();
if (!iterators.empty())
{
@@ -309,7 +323,7 @@
for (SkipList::iterator it = m_skipList.begin(); it != m_skipList.end(); )
{
- std::map<int, std::list<cs::Entry*>::iterator>::const_iterator i = iterators.find(layer);
+ std::map<int, std::list<cs::skip_list::Entry*>::iterator>::const_iterator i = iterators.find(layer);
if (i != iterators.end())
{
@@ -605,7 +619,7 @@
bool
Cs::doesComplyWithSelectors(const Interest& interest,
- cs::Entry* entry,
+ cs::skip_list::Entry* entry,
bool doesInterestContainDigest) const
{
NFD_LOG_TRACE("doesComplyWithSelectors()");
@@ -711,7 +725,7 @@
}
bool
-Cs::recognizeInterestWithDigest(const Interest& interest, cs::Entry* entry) const
+Cs::recognizeInterestWithDigest(const Interest& interest, cs::skip_list::Entry* entry) const
{
// only when min selector is not specified or specified with value of 0
// and Interest's name length is exactly the length of the name of CS entry
@@ -757,7 +771,7 @@
// it can happen when begin() contains the element we want to remove
if (!isIterated && ((*head)->getFullName() == exactName))
{
- cs::Entry* entryToDelete = *head;
+ cs::skip_list::Entry* entryToDelete = *head;
NFD_LOG_TRACE("Found target " << entryToDelete->getFullName());
eraseFromSkipList(entryToDelete);
// head can become invalid after eraseFromSkipList
@@ -806,7 +820,7 @@
if (isNameIdentical)
{
- cs::Entry* entryToDelete = *head;
+ cs::skip_list::Entry* entryToDelete = *head;
NFD_LOG_TRACE("Found target " << entryToDelete->getFullName());
eraseFromSkipList(entryToDelete);
// head can become invalid after eraseFromSkipList
diff --git a/daemon/table/cs.hpp b/daemon/table/cs.hpp
index f683a20..0d989cd 100644
--- a/daemon/table/cs.hpp
+++ b/daemon/table/cs.hpp
@@ -31,7 +31,7 @@
#define NFD_DAEMON_TABLE_CS_HPP
#include "common.hpp"
-#include "cs-entry.hpp"
+#include "cs-skip-list-entry.hpp"
#include <boost/multi_index/member.hpp>
#include <boost/multi_index_container.hpp>
@@ -43,14 +43,14 @@
namespace nfd {
-typedef std::list<cs::Entry*> SkipListLayer;
+typedef std::list<cs::skip_list::Entry*> SkipListLayer;
typedef std::list<SkipListLayer*> SkipList;
class StalenessComparator
{
public:
bool
- operator()(const cs::Entry* entry1, const cs::Entry* entry2) const
+ operator()(const cs::skip_list::Entry* entry1, const cs::skip_list::Entry* entry2) const
{
return entry1->getStaleTime() < entry2->getStaleTime();
}
@@ -60,13 +60,13 @@
{
public:
bool
- operator()(const cs::Entry* entry1, const cs::Entry* entry2) const
+ operator()(const cs::skip_list::Entry* entry1, const cs::skip_list::Entry* entry2) const
{
return entry1->isUnsolicited();
}
bool
- operator()(bool isUnsolicited, const cs::Entry* entry) const
+ operator()(bool isUnsolicited, const cs::skip_list::Entry* entry) const
{
if (isUnsolicited)
return true;
@@ -81,7 +81,7 @@
class byArrival;
typedef boost::multi_index_container<
- cs::Entry*,
+ cs::skip_list::Entry*,
boost::multi_index::indexed_by<
// by arrival (FIFO)
@@ -92,14 +92,14 @@
// index by staleness time
boost::multi_index::ordered_non_unique<
boost::multi_index::tag<byStaleness>,
- boost::multi_index::identity<cs::Entry*>,
+ boost::multi_index::identity<cs::skip_list::Entry*>,
StalenessComparator
>,
// unsolicited Data is in the front
boost::multi_index::ordered_non_unique<
boost::multi_index::tag<unsolicited>,
- boost::multi_index::identity<cs::Entry*>,
+ boost::multi_index::identity<cs::skip_list::Entry*>,
UnsolicitedComparator
>
@@ -155,6 +155,53 @@
size_t
size() const;
+public: // enumeration
+ class const_iterator;
+
+ /** \brief returns an iterator pointing to the first CS entry
+ * \note Iteration order is implementation-specific and is undefined
+ * \note The returned iterator may get invalidated if CS is modified
+ */
+ const_iterator
+ begin() const;
+
+ /** \brief returns an iterator referring to the past-the-end CS entry
+ * \note The returned iterator may get invalidated if CS is modified
+ */
+ const_iterator
+ end() const;
+
+ class const_iterator : public std::iterator<std::forward_iterator_tag, const cs::Entry>
+ {
+ public:
+ const_iterator() = default;
+
+ const_iterator(SkipListLayer::const_iterator it);
+
+ ~const_iterator();
+
+ reference
+ operator*() const;
+
+ pointer
+ operator->() const;
+
+ const_iterator&
+ operator++();
+
+ const_iterator
+ operator++(int);
+
+ bool
+ operator==(const const_iterator& other) const;
+
+ bool
+ operator!=(const const_iterator& other) const;
+
+ private:
+ SkipListLayer::const_iterator m_skipListIterator;
+ };
+
protected:
/** \brief removes one Data packet from Content Store based on replacement policy
* \return{ whether the Data was removed }
@@ -181,14 +228,14 @@
* \return{ returns a pair containing a pointer to the CS Entry,
* and a flag indicating if the entry was newly created (True) or refreshed (False) }
*/
- std::pair<cs::Entry*, bool>
+ std::pair<cs::skip_list::Entry*, bool>
insertToSkipList(const Data& data, bool isUnsolicited = false);
/** \brief Removes a specific CS Entry from all layers of a skip list
* \return{ returns True if CS Entry was succesfully removed and False if CS Entry was not found}
*/
bool
- eraseFromSkipList(cs::Entry* entry);
+ eraseFromSkipList(cs::skip_list::Entry* entry);
/** \brief Prints contents of the skip list, starting from the top layer
*/
@@ -216,7 +263,7 @@
*/
bool
doesComplyWithSelectors(const Interest& interest,
- cs::Entry* entry,
+ cs::skip_list::Entry* entry,
bool doesInterestContainDigest) const;
/** \brief interprets minSuffixComponent and name lengths to understand if Interest contains
@@ -224,16 +271,78 @@
* \return{ True if Interest name contains digest; False otherwise }
*/
bool
- recognizeInterestWithDigest(const Interest& interest, cs::Entry* entry) const;
+ recognizeInterestWithDigest(const Interest& interest, cs::skip_list::Entry* entry) const;
private:
SkipList m_skipList;
CleanupIndex m_cleanupIndex;
size_t m_nMaxPackets; // user defined maximum size of the Content Store in packets
size_t m_nPackets; // current number of packets in Content Store
- std::queue<cs::Entry*> m_freeCsEntries; // memory pool
+ std::queue<cs::skip_list::Entry*> m_freeCsEntries; // memory pool
};
+inline Cs::const_iterator
+Cs::begin() const
+{
+ return const_iterator(m_skipList.front()->begin());
+}
+
+inline Cs::const_iterator
+Cs::end() const
+{
+ return const_iterator(m_skipList.front()->end());
+}
+
+inline
+Cs::const_iterator::const_iterator(SkipListLayer::const_iterator it)
+ : m_skipListIterator(it)
+{
+}
+
+inline
+Cs::const_iterator::~const_iterator()
+{
+}
+
+inline Cs::const_iterator&
+Cs::const_iterator::operator++()
+{
+ ++m_skipListIterator;
+ return *this;
+}
+
+inline Cs::const_iterator
+Cs::const_iterator::operator++(int)
+{
+ Cs::const_iterator temp(*this);
+ ++(*this);
+ return temp;
+}
+
+inline Cs::const_iterator::reference
+Cs::const_iterator::operator*() const
+{
+ return *(this->operator->());
+}
+
+inline Cs::const_iterator::pointer
+Cs::const_iterator::operator->() const
+{
+ return *m_skipListIterator;
+}
+
+inline bool
+Cs::const_iterator::operator==(const Cs::const_iterator& other) const
+{
+ return m_skipListIterator == other.m_skipListIterator;
+}
+
+inline bool
+Cs::const_iterator::operator!=(const Cs::const_iterator& other) const
+{
+ return !(*this == other);
+}
+
} // namespace nfd
#endif // NFD_DAEMON_TABLE_CS_HPP
diff --git a/tests/daemon/table/cs.cpp b/tests/daemon/table/cs.cpp
index d38538e..4032ff4 100644
--- a/tests/daemon/table/cs.cpp
+++ b/tests/daemon/table/cs.cpp
@@ -986,6 +986,42 @@
BOOST_AUTO_TEST_SUITE_END() // Find
+BOOST_AUTO_TEST_CASE(Iterator)
+{
+ Cs cs;
+
+ Name nameA("/A");
+ Name nameAB("/A/B");
+ Name nameABC("/A/B/C");
+ Name nameD("/D");
+
+ BOOST_CHECK_EQUAL(cs.size(), 0);
+ BOOST_CHECK(cs.begin() == cs.end());
+
+ cs.insert(*makeData(nameABC));
+ BOOST_CHECK_EQUAL(cs.size(), 1);
+ BOOST_CHECK(cs.begin() != cs.end());
+ BOOST_CHECK(cs.begin()->getName() == nameABC);
+ BOOST_CHECK((*cs.begin()).getName() == nameABC);
+
+ auto i = cs.begin();
+ auto j = cs.begin();
+ BOOST_CHECK(++i == cs.end());
+ BOOST_CHECK(j++ == cs.begin());
+ BOOST_CHECK(j == cs.end());
+
+ cs.insert(*makeData(nameA));
+ cs.insert(*makeData(nameAB));
+ cs.insert(*makeData(nameD));
+
+ std::set<Name> expected = {nameA, nameAB, nameABC, nameD};
+ std::set<Name> actual;
+ for (const auto& csEntry : cs) {
+ actual.insert(csEntry.getName());
+ }
+ BOOST_CHECK_EQUAL_COLLECTIONS(actual.begin(), actual.end(), expected.begin(), expected.end());
+}
+
BOOST_AUTO_TEST_SUITE_END() // TableCs
} // namespace tests