table: make NameTree enumeration usable with range-based for
NameTree::fullEnumerate and NameTree::partialEnumerate are changed
to return a type usable with range-based for.
NameTree enumeration test cases are also simplified.
refs #2155
Change-Id: I315d9502d2194670aa7054ab956ededefb0c7ca0
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index a3b836e..99a1bf9 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -143,23 +143,33 @@
void
Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
{
- for (NameTree::const_iterator it = m_nameTree.fullEnumerate(
- &predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end();) {
- shared_ptr<fib::Entry> entry = it->getFibEntry();
+ shared_ptr<fib::Entry> toErase;
- ++it; // advance the iterator before `erase` invalidates it
+ auto&& enumerable = m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry);
+ for (const name_tree::Entry& nte : enumerable) {
+ if (toErase != nullptr) {
+ this->erase(*toErase);
+ toErase.reset();
+ }
+ shared_ptr<fib::Entry> entry = nte.getFibEntry();
entry->removeNextHop(face);
if (!entry->hasNextHops()) {
- this->erase(*entry);
+ toErase = entry;
+ // entry needs to be erased, but we must wait until next iteration
+ // to erase it because otherwise it would invalidate the iterator
}
}
+
+ if (toErase != nullptr) {
+ this->erase(*toErase);
+ }
}
Fib::const_iterator
Fib::begin() const
{
- return const_iterator(m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry));
+ return const_iterator(m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry).begin());
}
} // namespace nfd
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 31bde14..3dfd2ae 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -387,38 +387,34 @@
return false; // if this entry is not empty
}
-NameTree::const_iterator
+NameTree::Range
NameTree::fullEnumerate(const name_tree::EntrySelector& entrySelector) const
{
NFD_LOG_TRACE("fullEnumerate");
// find the first eligible entry
- for (size_t i = 0; i < m_nBuckets; i++)
- {
- for (name_tree::Node* node = m_buckets[i]; node != 0; node = node->m_next)
- {
- if (static_cast<bool>(node->m_entry) && entrySelector(*node->m_entry))
- {
- const_iterator it(FULL_ENUMERATE_TYPE, *this, node->m_entry, entrySelector);
- return it;
- }
- }
+ for (size_t i = 0; i < m_nBuckets; i++) {
+ for (name_tree::Node* node = m_buckets[i]; node != 0; node = node->m_next) {
+ if (static_cast<bool>(node->m_entry) && entrySelector(*node->m_entry)) {
+ const_iterator it(FULL_ENUMERATE_TYPE, *this, node->m_entry, entrySelector);
+ return {it, end()};
+ }
}
+ }
// If none of the entry satisfies the requirements, then return the end() iterator.
- return end();
+ return {end(), end()};
}
-NameTree::const_iterator
+NameTree::Range
NameTree::partialEnumerate(const Name& prefix,
const name_tree::EntrySubTreeSelector& entrySubTreeSelector) const
{
// the first step is to process the root node
shared_ptr<name_tree::Entry> entry = findExactMatch(prefix);
- if (!static_cast<bool>(entry))
- {
- return end();
- }
+ if (!static_cast<bool>(entry)) {
+ return {end(), end()};
+ }
std::pair<bool, bool>result = entrySubTreeSelector(*entry);
const_iterator it(PARTIAL_ENUMERATE_TYPE,
@@ -429,17 +425,14 @@
it.m_shouldVisitChildren = (result.second && entry->hasChildren());
- if (result.first)
- {
- // root node is acceptable
- return it;
- }
- else
- {
- // let the ++ operator handle it
- ++it;
- return it;
- }
+ if (result.first) {
+ // root node is acceptable
+ }
+ else {
+ // let the ++ operator handle it
+ ++it;
+ }
+ return {it, end()};
}
NameTree::Range
@@ -458,10 +451,10 @@
if (static_cast<bool>(entry)) {
const_iterator begin(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
- return { begin, end() };
+ return {begin, end()};
}
// If none of the entry satisfies the requirements, then return the end() iterator.
- return { end(), end() };
+ return {end(), end()};
}
// Hash Table Resize
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 2ef032e..b4e12ed 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -191,16 +191,34 @@
const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
public: // enumeration
- /**
- * \brief Enumerate all the name prefixes stored in the Name Tree.
+ /** \brief Enumerate all entries, optionally filtered by an EntrySelector.
+ * \return an unspecified type that have .begin() and .end() methods
+ * and is usable with range-based for
+ *
+ * Example:
+ * \code{.cpp}
+ * auto&& enumerable = nt.fullEnumerate();
+ * for (const name_tree::Entry& nte : enumerable) {
+ * ...
+ * }
+ * \endcode
*/
- const_iterator
+ Range
fullEnumerate(const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
- /**
- * \brief Enumerate all the name prefixes that satisfies the EntrySubTreeSelector.
- */
- const_iterator
+ /** \brief Enumerate all entries under a prefix, optionally filtered by an EntrySubTreeSelector.
+ * \return an unspecified type that have .begin() and .end() methods
+ * and is usable with range-based for
+ *
+ * Example:
+ * \code{.cpp}
+ * auto&& enumerable = nt.partialEnumerate(Name("/A/B/C"));
+ * for (const name_tree::Entry& nte : enumerable) {
+ * ...
+ * }
+ * \endcode
+ */
+ Range
partialEnumerate(const Name& prefix,
const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
name_tree::AnyEntrySubTree()) const;
@@ -364,7 +382,7 @@
inline NameTree::const_iterator
NameTree::begin() const
{
- return fullEnumerate();
+ return fullEnumerate().begin();
}
inline NameTree::const_iterator
diff --git a/daemon/table/strategy-choice.cpp b/daemon/table/strategy-choice.cpp
index f39df1c..85aade6 100644
--- a/daemon/table/strategy-choice.cpp
+++ b/daemon/table/strategy-choice.cpp
@@ -259,26 +259,29 @@
// reset StrategyInfo on a portion of NameTree,
// where entry's effective strategy is covered by the changing StrategyChoice entry
const name_tree::Entry* rootNte = m_nameTree.get(entry).get();
- auto ntChanged = m_nameTree.partialEnumerate(entry.getPrefix(),
+ auto&& ntChanged = m_nameTree.partialEnumerate(entry.getPrefix(),
[&rootNte] (const name_tree::Entry& nte) -> std::pair<bool, bool> {
if (&nte == rootNte) {
- return { true, true };
+ return {true, true};
}
if (static_cast<bool>(nte.getStrategyChoiceEntry())) {
- return { false, false };
+ return {false, false};
}
- return { true, true };
+ return {true, true};
});
- std::for_each(ntChanged, m_nameTree.end(), &clearStrategyInfo);
+ for (const name_tree::Entry& nte : ntChanged) {
+ clearStrategyInfo(nte);
+ }
}
StrategyChoice::const_iterator
StrategyChoice::begin() const
{
- return const_iterator(m_nameTree.fullEnumerate(
+ auto&& enumerable = m_nameTree.fullEnumerate(
[] (const name_tree::Entry& entry) {
return static_cast<bool>(entry.getStrategyChoiceEntry());
- }));
+ });
+ return const_iterator(enumerable.begin());
}
} // namespace nfd