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