table: Allow iteration over PIT entries
Change-Id: If48d7f827ccb5df0480cfa27bd2f3db4e3f796fa
Refs: #2339
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index e4199e8..5e333aa 100644
--- a/daemon/table/pit.cpp
+++ b/daemon/table/pit.cpp
@@ -26,6 +26,10 @@
#include "pit.hpp"
#include <type_traits>
+#include <boost/concept/assert.hpp>
+#include <boost/concept_check.hpp>
+#include <type_traits>
+
namespace nfd {
namespace pit {
@@ -36,6 +40,17 @@
} // namespace pit
+// http://en.cppreference.com/w/cpp/concept/ForwardIterator
+BOOST_CONCEPT_ASSERT((boost::ForwardIterator<Pit::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<Pit::const_iterator>::value,
+ "Pit::const_iterator must be default-constructible");
+#else
+BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Pit::const_iterator>));
+#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
+
Pit::Pit(NameTree& nameTree)
: m_nameTree(nameTree)
, m_nItems(0)
@@ -101,4 +116,11 @@
--m_nItems;
}
+Pit::const_iterator
+Pit::begin() const
+{
+ return const_iterator(m_nameTree.fullEnumerate(
+ [] (const name_tree::Entry& entry) { return entry.hasPitEntries(); }).begin());
+}
+
} // namespace nfd
diff --git a/daemon/table/pit.hpp b/daemon/table/pit.hpp
index 00d90ca..3bdf44f 100644
--- a/daemon/table/pit.hpp
+++ b/daemon/table/pit.hpp
@@ -78,6 +78,62 @@
void
erase(shared_ptr<pit::Entry> pitEntry);
+public: // enumeration
+ class const_iterator;
+
+ /** \brief returns an iterator pointing to the first PIT entry
+ * \note Iteration order is implementation-specific and is undefined
+ * \note The returned iterator may get invalidated if PIT or another NameTree-based
+ * table is modified
+ */
+ const_iterator
+ begin() const;
+
+ /** \brief returns an iterator referring to the past-the-end PIT entry
+ * \note The returned iterator may get invalidated if PIT or another NameTree-based
+ * table is modified
+ */
+ const_iterator
+ end() const;
+
+ class const_iterator : public std::iterator<std::forward_iterator_tag, const pit::Entry>
+ {
+ public:
+ const_iterator();
+
+ explicit
+ const_iterator(const NameTree::const_iterator& it);
+
+ ~const_iterator();
+
+ const pit::Entry&
+ operator*() const;
+
+ shared_ptr<pit::Entry>
+ operator->() const;
+
+ const_iterator&
+ operator++();
+
+ const_iterator
+ operator++(int);
+
+ bool
+ operator==(const const_iterator& other) const;
+
+ bool
+ operator!=(const const_iterator& other) const;
+
+ private:
+ NameTree::const_iterator m_nameTreeIterator;
+ /** \brief Index of the current visiting PIT entry in NameTree node
+ *
+ * Index is used to ensure that dereferencing of m_nameTreeIterator happens only when
+ * const_iterator is dereferenced or advanced.
+ */
+ size_t m_iPitEntry;
+ };
+
private:
NameTree& m_nameTree;
size_t m_nItems;
@@ -89,6 +145,76 @@
return m_nItems;
}
+inline Pit::const_iterator
+Pit::end() const
+{
+ return const_iterator(m_nameTree.end());
+}
+
+inline
+Pit::const_iterator::const_iterator()
+ : m_iPitEntry(0)
+{
+}
+
+inline
+Pit::const_iterator::const_iterator(const NameTree::const_iterator& it)
+ : m_nameTreeIterator(it)
+ , m_iPitEntry(0)
+{
+}
+
+inline
+Pit::const_iterator::~const_iterator()
+{
+}
+
+inline Pit::const_iterator
+Pit::const_iterator::operator++(int)
+{
+ Pit::const_iterator temp(*this);
+ ++(*this);
+ return temp;
+}
+
+inline Pit::const_iterator&
+Pit::const_iterator::operator++()
+{
+ ++m_iPitEntry;
+ if (m_iPitEntry < m_nameTreeIterator->getPitEntries().size()) {
+ return *this;
+ }
+
+ ++m_nameTreeIterator;
+ m_iPitEntry = 0;
+ return *this;
+}
+
+inline const pit::Entry&
+Pit::const_iterator::operator*() const
+{
+ return *(this->operator->());
+}
+
+inline shared_ptr<pit::Entry>
+Pit::const_iterator::operator->() const
+{
+ return m_nameTreeIterator->getPitEntries().at(m_iPitEntry);
+}
+
+inline bool
+Pit::const_iterator::operator==(const Pit::const_iterator& other) const
+{
+ return m_nameTreeIterator == other.m_nameTreeIterator &&
+ m_iPitEntry == other.m_iPitEntry;
+}
+
+inline bool
+Pit::const_iterator::operator!=(const Pit::const_iterator& other) const
+{
+ return !(*this == other);
+}
+
} // namespace nfd
#endif // NFD_DAEMON_TABLE_PIT_HPP
diff --git a/tests/daemon/table/pit.cpp b/tests/daemon/table/pit.cpp
index dcf5053..cabbab9 100644
--- a/tests/daemon/table/pit.cpp
+++ b/tests/daemon/table/pit.cpp
@@ -450,6 +450,48 @@
}
+BOOST_AUTO_TEST_CASE(Iterator)
+{
+ NameTree nameTree(16);
+ Pit pit(nameTree);
+
+ shared_ptr<Interest> interestA = makeInterest("/A");
+ shared_ptr<Interest> interestABC1 = makeInterest("/A/B/C");
+ shared_ptr<Interest> interestABC2 = makeInterest("/A/B/C");
+ interestABC2->setSelectors(ndn::Selectors().setMinSuffixComponents(10));
+ shared_ptr<Interest> interestD = makeInterest("/D");
+
+ BOOST_CHECK_EQUAL(pit.size(), 0);
+ BOOST_CHECK(pit.begin() == pit.end());
+
+ pit.insert(*interestABC1);
+ BOOST_CHECK_EQUAL(pit.size(), 1);
+ BOOST_CHECK(pit.begin() != pit.end());
+ BOOST_CHECK(pit.begin()->getInterest() == *interestABC1);
+ BOOST_CHECK((*pit.begin()).getInterest() == *interestABC1);
+
+ auto i = pit.begin();
+ auto j = pit.begin();
+ BOOST_CHECK(++i == pit.end());
+ BOOST_CHECK(j++ == pit.begin());
+ BOOST_CHECK(j == pit.end());
+
+ pit.insert(*interestA);
+ pit.insert(*interestABC2);
+ pit.insert(*interestD);
+
+ std::set<const Interest*> expected = {&*interestA, &*interestABC1, &*interestABC2, &*interestD};
+ std::set<const Interest*> actual;
+ for (const auto& pitEntry : pit) {
+ actual.insert(&pitEntry.getInterest());
+ }
+ BOOST_CHECK(actual == expected);
+ for (auto actualIt = actual.begin(), expectedIt = expected.begin();
+ actualIt != actual.end() && expectedIt != expected.end(); ++actualIt, ++expectedIt) {
+ BOOST_CHECK_EQUAL(**actualIt, **expectedIt);
+ }
+}
+
BOOST_AUTO_TEST_SUITE_END()
} // namespace tests