table: Ensure Fib::const_iterator is default and copy constructible
This functionality is necessary for ndnSIM python bindings and is
technically required by ForwardIterator C++ concept
(http://en.cppreference.com/w/cpp/concept/ForwardIterator)
Change-Id: Ibe0812c3a2cf05840cd3e83b941cc52affe2ac65
Refs: #2338
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index c28a695..ee9e733 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -27,10 +27,25 @@
#include "pit-entry.hpp"
#include "measurements-entry.hpp"
+#include <boost/concept/assert.hpp>
+#include <boost/concept_check.hpp>
+#include <type_traits>
+
namespace nfd {
const shared_ptr<fib::Entry> Fib::s_emptyEntry = make_shared<fib::Entry>(Name());
+// http://en.cppreference.com/w/cpp/concept/ForwardIterator
+BOOST_CONCEPT_ASSERT((boost::ForwardIterator<Fib::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<Fib::const_iterator>::value,
+ "Fib::const_iterator must be default-constructible");
+#else
+BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Fib::const_iterator>));
+#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
+
Fib::Fib(NameTree& nameTree)
: m_nameTree(nameTree)
, m_nItems(0)
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 3a19949..34a2009 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -95,15 +95,26 @@
public: // enumeration
class const_iterator;
+ /** \brief returns an iterator pointing to the first FIB entry
+ * \note Iteration order is implementation-specific and is undefined
+ * \note The returned iterator may get invalidated if FIB or another NameTree-based
+ * table is modified
+ */
const_iterator
begin() const;
+ /** \brief returns an iterator referring to the past-the-end FIB entry
+ * \note The returned iterator may get invalidated if FIB or another NameTree-based
+ * table is modified
+ */
const_iterator
end() const;
- class const_iterator : public std::iterator<std::forward_iterator_tag, fib::Entry>
+ class const_iterator : public std::iterator<std::forward_iterator_tag, const fib::Entry>
{
public:
+ const_iterator() = default;
+
explicit
const_iterator(const NameTree::const_iterator& it);
@@ -193,7 +204,7 @@
inline const fib::Entry&
Fib::const_iterator::operator*() const
{
- return *(m_nameTreeIterator->getFibEntry());
+ return *this->operator->();
}
inline shared_ptr<fib::Entry>
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index d7cb544..3ac469d 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -27,10 +27,25 @@
#include "core/logger.hpp"
#include "core/city-hash.hpp"
+#include <boost/concept/assert.hpp>
+#include <boost/concept_check.hpp>
+#include <type_traits>
+
namespace nfd {
NFD_LOG_INIT("NameTree");
+// http://en.cppreference.com/w/cpp/concept/ForwardIterator
+BOOST_CONCEPT_ASSERT((boost::ForwardIterator<NameTree::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<NameTree::const_iterator>::value,
+ "NameTree::const_iterator must be default-constructible");
+#else
+BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<NameTree::const_iterator>));
+#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
+
namespace name_tree {
class Hash32
@@ -569,12 +584,17 @@
output << "--------------------------\n";
}
+NameTree::const_iterator::const_iterator()
+ : m_nameTree(nullptr)
+{
+}
+
NameTree::const_iterator::const_iterator(NameTree::IteratorType type,
const NameTree& nameTree,
shared_ptr<name_tree::Entry> entry,
const name_tree::EntrySelector& entrySelector,
const name_tree::EntrySubTreeSelector& entrySubTreeSelector)
- : m_nameTree(nameTree)
+ : m_nameTree(&nameTree)
, m_entry(entry)
, m_subTreeRoot(entry)
, m_entrySelector(make_shared<name_tree::EntrySelector>(entrySelector))
@@ -590,7 +610,7 @@
{
NFD_LOG_TRACE("const_iterator::operator++()");
- BOOST_ASSERT(m_entry != m_nameTree.m_end);
+ BOOST_ASSERT(m_entry != m_nameTree->m_end);
if (m_type == FULL_ENUMERATE_TYPE) // fullEnumerate
{
@@ -608,12 +628,12 @@
// process other buckets
- for (int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
- newLocation < static_cast<int>(m_nameTree.m_nBuckets);
+ for (int newLocation = m_entry->m_hash % m_nameTree->m_nBuckets + 1;
+ newLocation < static_cast<int>(m_nameTree->m_nBuckets);
++newLocation)
{
// process each bucket
- name_tree::Node* node = m_nameTree.m_buckets[newLocation];
+ name_tree::Node* node = m_nameTree->m_buckets[newLocation];
while (node != 0)
{
m_entry = node->m_entry;
@@ -627,7 +647,7 @@
}
BOOST_VERIFY(isFound == false);
// Reach to the end()
- m_entry = m_nameTree.m_end;
+ m_entry = m_nameTree->m_end;
return *this;
}
@@ -727,7 +747,7 @@
}
}
- m_entry = m_nameTree.m_end;
+ m_entry = m_nameTree->m_end;
return *this;
}
@@ -745,7 +765,7 @@
}
// Reach to the end (Root)
- m_entry = m_nameTree.m_end;
+ m_entry = m_nameTree->m_end;
return *this;
}
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 6e936d0..8d4e437 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -184,6 +184,8 @@
* ...
* }
* \endcode
+ * \note Iteration order is implementation-specific and is undefined
+ * \note The returned iterator may get invalidated when NameTree is modified
*/
boost::iterator_range<const_iterator>
findAllMatches(const Name& prefix,
@@ -201,6 +203,8 @@
* ...
* }
* \endcode
+ * \note Iteration order is implementation-specific and is undefined
+ * \note The returned iterator may get invalidated when NameTree is modified
*/
boost::iterator_range<const_iterator>
fullEnumerate(const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
@@ -216,15 +220,25 @@
* ...
* }
* \endcode
+ * \note Iteration order is implementation-specific and is undefined
+ * \note The returned iterator may get invalidated when NameTree is modified
*/
boost::iterator_range<const_iterator>
partialEnumerate(const Name& prefix,
const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
name_tree::AnyEntrySubTree()) const;
+ /** \brief Get an iterator pointing to the first NameTree entry
+ * \note Iteration order is implementation-specific and is undefined
+ * \note The returned iterator may get invalidated when NameTree is modified
+ */
const_iterator
begin() const;
+ /** \brief Get an iterator referring to the past-the-end FIB entry
+ * \note Iteration order is implementation-specific and is undefined
+ * \note The returned iterator may get invalidated when NameTree is modified
+ */
const_iterator
end() const;
@@ -234,11 +248,13 @@
FIND_ALL_MATCHES_TYPE
};
- class const_iterator : public std::iterator<std::forward_iterator_tag, name_tree::Entry>
+ class const_iterator : public std::iterator<std::forward_iterator_tag, const name_tree::Entry>
{
public:
friend class NameTree;
+ const_iterator();
+
const_iterator(NameTree::IteratorType type,
const NameTree& nameTree,
shared_ptr<name_tree::Entry> entry,
@@ -266,7 +282,7 @@
operator!=(const const_iterator& other) const;
private:
- const NameTree& m_nameTree;
+ const NameTree* m_nameTree;
shared_ptr<name_tree::Entry> m_entry;
shared_ptr<name_tree::Entry> m_subTreeRoot;
shared_ptr<name_tree::EntrySelector> m_entrySelector;