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
diff --git a/tests/daemon/table/name-tree.cpp b/tests/daemon/table/name-tree.cpp
index ebb8550..9790596 100644
--- a/tests/daemon/table/name-tree.cpp
+++ b/tests/daemon/table/name-tree.cpp
@@ -24,6 +24,8 @@
*/
#include "table/name-tree.hpp"
+#include <unordered_set>
+
#include "tests/test-common.hpp"
namespace nfd {
@@ -239,382 +241,215 @@
BOOST_CHECK_EQUAL(nt.size(), 8);
}
-BOOST_AUTO_TEST_CASE(IteratorFullEnumerate)
+/** \brief verify a NameTree enumeration contains expected entries
+ *
+ * Example:
+ * \code{.cpp}
+ * auto& enumerable = ...;
+ * EnumerationVerifier(enumerable)
+ * .expect("/A")
+ * .expect("/B")
+ * .end();
+ * // enumerable must have /A /B and nothing else to pass the test.
+ * \endcode
+ */
+class EnumerationVerifier : noncopyable
{
- size_t nBuckets = 1024;
- NameTree nt(nBuckets);
+public:
+ template<typename Enumerable>
+ EnumerationVerifier(Enumerable&& enumerable)
+ {
+ for (const name_tree::Entry& entry : enumerable) {
+ const Name& name = entry.getPrefix();
+ BOOST_CHECK_MESSAGE(m_names.insert(name).second, "duplicate Name " << name);
+ }
+ }
- BOOST_CHECK_EQUAL(nt.size(), 0);
- BOOST_CHECK_EQUAL(nt.getNBuckets(), nBuckets);
+ EnumerationVerifier&
+ expect(const Name& name)
+ {
+ BOOST_CHECK_MESSAGE(m_names.erase(name) == 1, "missing Name " << name);
+ return *this;
+ }
- Name nameABC("ndn:/a/b/c");
- shared_ptr<name_tree::Entry> npeABC = nt.lookup(nameABC);
+ void
+ end()
+ {
+ BOOST_CHECK_MESSAGE(m_names.empty(), "excess Names including " << *m_names.begin());
+ }
+
+private:
+ std::unordered_set<Name> m_names;
+};
+
+class EnumerationFixture : public BaseFixture
+{
+protected:
+ EnumerationFixture()
+ : nt(N_BUCKETS)
+ {
+ BOOST_CHECK_EQUAL(nt.size(), 0);
+ BOOST_CHECK_EQUAL(nt.getNBuckets(), N_BUCKETS);
+ }
+
+ void
+ insertAbAc()
+ {
+ nt.lookup("/a/b");
+ nt.lookup("/a/c");
+ BOOST_CHECK_EQUAL(nt.size(), 4);
+ // /, /a, /a/b, /a/c
+ }
+
+ void
+ insertAb1Ab2Ac1Ac2()
+ {
+ nt.lookup("/a/b/1");
+ nt.lookup("/a/b/2");
+ nt.lookup("/a/c/1");
+ nt.lookup("/a/c/2");
+ BOOST_CHECK_EQUAL(nt.size(), 8);
+ // /, /a, /a/b, /a/b/1, /a/b/2, /a/c, /a/c/1, /a/c/2
+ }
+
+protected:
+ static const size_t N_BUCKETS = 16;
+ NameTree nt;
+};
+const size_t EnumerationFixture::N_BUCKETS;
+
+BOOST_FIXTURE_TEST_CASE(IteratorFullEnumerate, EnumerationFixture)
+{
+ nt.lookup("/a/b/c");
BOOST_CHECK_EQUAL(nt.size(), 4);
- Name nameABD("/a/b/d");
- shared_ptr<name_tree::Entry> npeABD = nt.lookup(nameABD);
+ nt.lookup("/a/b/d");
BOOST_CHECK_EQUAL(nt.size(), 5);
- Name nameAE("/a/e/");
- shared_ptr<name_tree::Entry> npeAE = nt.lookup(nameAE);
+ nt.lookup("/a/e");
BOOST_CHECK_EQUAL(nt.size(), 6);
- Name nameF("/f");
- shared_ptr<name_tree::Entry> npeF = nt.lookup(nameF);
+ nt.lookup("/f");
BOOST_CHECK_EQUAL(nt.size(), 7);
- Name nameRoot("/");
- shared_ptr<name_tree::Entry> npeRoot = nt.lookup(nameRoot);
+ nt.lookup("/");
BOOST_CHECK_EQUAL(nt.size(), 7);
- Name nameA("/a");
- Name nameAB("/a/b");
-
- bool hasRoot = false;
- bool hasA = false;
- bool hasAB = false;
- bool hasABC = false;
- bool hasABD = false;
- bool hasAE = false;
- bool hasF = false;
-
- int counter = 0;
- NameTree::const_iterator it = nt.fullEnumerate();
-
- for(; it != nt.end(); it++)
- {
- counter++;
-
- if (it->getPrefix() == nameRoot)
- hasRoot = true;
- if (it->getPrefix() == nameA)
- hasA = true;
- if (it->getPrefix() == nameAB)
- hasAB = true;
- if (it->getPrefix() == nameABC)
- hasABC = true;
- if (it->getPrefix() == nameABD)
- hasABD = true;
- if (it->getPrefix() == nameAE)
- hasAE = true;
- if (it->getPrefix() == nameF)
- hasF = true;
- }
-
- BOOST_CHECK_EQUAL(hasRoot , true);
- BOOST_CHECK_EQUAL(hasA , true);
- BOOST_CHECK_EQUAL(hasAB , true);
- BOOST_CHECK_EQUAL(hasABC , true);
- BOOST_CHECK_EQUAL(hasABD , true);
- BOOST_CHECK_EQUAL(hasAE , true);
- BOOST_CHECK_EQUAL(hasF , true);
-
- BOOST_CHECK_EQUAL(counter , 7);
+ auto&& enumerable = nt.fullEnumerate();
+ EnumerationVerifier(enumerable)
+ .expect("/")
+ .expect("/a")
+ .expect("/a/b")
+ .expect("/a/b/c")
+ .expect("/a/b/d")
+ .expect("/a/e")
+ .expect("/f")
+ .end();
}
-// Predicates for testing the partial enumerate function
+BOOST_FIXTURE_TEST_SUITE(IteratorPartialEnumerate, EnumerationFixture)
-static inline std::pair<bool, bool>
-predicate_NameTreeEntry_NameA_Only(const name_tree::Entry& entry)
+BOOST_AUTO_TEST_CASE(Empty)
{
- Name nameA("/a");
- bool first = nameA.equals(entry.getPrefix());
- return std::make_pair(first, true);
+ auto&& enumerable = nt.partialEnumerate("/a");
+
+ EnumerationVerifier(enumerable)
+ .end();
}
-static inline std::pair<bool, bool>
-predicate_NameTreeEntry_Except_NameA(const name_tree::Entry& entry)
+BOOST_AUTO_TEST_CASE(NotIn)
{
- Name nameA("/a");
- bool first = !(nameA.equals(entry.getPrefix()));
- return std::make_pair(first, true);
-}
-
-static inline std::pair<bool, bool>
-predicate_NameTreeEntry_NoSubNameA(const name_tree::Entry& entry)
-{
- Name nameA("/a");
- bool second = !(nameA.equals(entry.getPrefix()));
- return std::make_pair(true, second);
-}
-
-static inline std::pair<bool, bool>
-predicate_NameTreeEntry_NoNameA_NoSubNameAB(const name_tree::Entry& entry)
-{
- Name nameA("/a");
- Name nameAB("/a/b");
- bool first = !(nameA.equals(entry.getPrefix()));
- bool second = !(nameAB.equals(entry.getPrefix()));
- return std::make_pair(first, second);
-}
-
-static inline std::pair<bool, bool>
-predicate_NameTreeEntry_NoNameA_NoSubNameAC(const name_tree::Entry& entry)
-{
- Name nameA("/a");
- Name nameAC("/a/c");
- bool first = !(nameA.equals(entry.getPrefix()));
- bool second = !(nameAC.equals(entry.getPrefix()));
- return std::make_pair(first, second);
-}
-
-static inline std::pair<bool, bool>
-predicate_NameTreeEntry_Example(const name_tree::Entry& entry)
-{
- Name nameRoot("/");
- Name nameA("/a");
- Name nameAB("/a/b");
- Name nameABC("/a/b/c");
- Name nameAD("/a/d");
- Name nameE("/e");
- Name nameF("/f");
-
- bool first = false;
- bool second = false;
-
- Name name = entry.getPrefix();
-
- if (name == nameRoot || name == nameAB || name == nameABC || name == nameAD)
- {
- first = true;
- }
-
- if(name == nameRoot || name == nameA || name == nameF)
- {
- second = true;
- }
-
- return std::make_pair(first, second);
-}
-
-BOOST_AUTO_TEST_CASE(IteratorPartialEnumerate)
-{
- typedef NameTree::const_iterator const_iterator;
-
- size_t nBuckets = 16;
- NameTree nameTree(nBuckets);
- int counter = 0;
-
- // empty nameTree, should return end();
- Name nameA("/a");
- bool hasA = false;
- const_iterator itA = nameTree.partialEnumerate(nameA);
- BOOST_CHECK(itA == nameTree.end());
-
- // We have "/", "/a", "/a/b", "a/c" now.
- Name nameAB("/a/b");
- bool hasAB = false;
- nameTree.lookup(nameAB);
-
- Name nameAC("/a/c");
- bool hasAC = false;
- nameTree.lookup(nameAC);
- BOOST_CHECK_EQUAL(nameTree.size(), 4);
+ this->insertAbAc();
// Enumerate on some name that is not in nameTree
- Name name0="/0";
- const_iterator it0 = nameTree.partialEnumerate(name0);
- BOOST_CHECK(it0 == nameTree.end());
+ Name name0("/0");
+ auto&& enumerable = nt.partialEnumerate("/0");
+
+ EnumerationVerifier(enumerable)
+ .end();
+}
+
+BOOST_AUTO_TEST_CASE(OnlyA)
+{
+ this->insertAbAc();
// Accept "root" nameA only
- const_iterator itAOnly = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NameA_Only);
- BOOST_CHECK_EQUAL(itAOnly->getPrefix(), nameA);
- BOOST_CHECK(++itAOnly == nameTree.end());
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ return std::make_pair(entry.getPrefix() == "/a", true);
+ });
+
+ EnumerationVerifier(enumerable)
+ .expect("/a")
+ .end();
+}
+
+BOOST_AUTO_TEST_CASE(ExceptA)
+{
+ this->insertAbAc();
// Accept anything except "root" nameA
- const_iterator itExceptA = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_Except_NameA);
- hasA = false;
- hasAB = false;
- hasAC = false;
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ return std::make_pair(entry.getPrefix() != "/a", true);
+ });
- counter = 0;
- for (; itExceptA != nameTree.end(); itExceptA++)
- {
- counter++;
+ EnumerationVerifier(enumerable)
+ .expect("/a/b")
+ .expect("/a/c")
+ .end();
+}
- if (itExceptA->getPrefix() == nameA)
- hasA = true;
-
- if (itExceptA->getPrefix() == nameAB)
- hasAB = true;
-
- if (itExceptA->getPrefix() == nameAC)
- hasAC = true;
- }
- BOOST_CHECK_EQUAL(hasA, false);
- BOOST_CHECK_EQUAL(hasAB, true);
- BOOST_CHECK_EQUAL(hasAC, true);
-
- BOOST_CHECK_EQUAL(counter, 2);
-
- Name nameAB1("a/b/1");
- bool hasAB1 = false;
- nameTree.lookup(nameAB1);
-
- Name nameAB2("a/b/2");
- bool hasAB2 = false;
- nameTree.lookup(nameAB2);
-
- Name nameAC1("a/c/1");
- bool hasAC1 = false;
- nameTree.lookup(nameAC1);
-
- Name nameAC2("a/c/2");
- bool hasAC2 = false;
- nameTree.lookup(nameAC2);
-
- BOOST_CHECK_EQUAL(nameTree.size(), 8);
+BOOST_AUTO_TEST_CASE(NoNameANoSubTreeAB)
+{
+ this->insertAb1Ab2Ac1Ac2();
// No NameA
// No SubTree from NameAB
- const_iterator itNoNameANoSubNameAB = nameTree.partialEnumerate(nameA,
- &predicate_NameTreeEntry_NoNameA_NoSubNameAB);
- hasA = false;
- hasAB = false;
- hasAB1 = false;
- hasAB2 = false;
- hasAC = false;
- hasAC1 = false;
- hasAC2 = false;
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ return std::make_pair(entry.getPrefix() != "/a", entry.getPrefix() != "/a/b");
+ });
- counter = 0;
+ EnumerationVerifier(enumerable)
+ .expect("/a/b")
+ .expect("/a/c")
+ .expect("/a/c/1")
+ .expect("/a/c/2")
+ .end();
+}
- for (; itNoNameANoSubNameAB != nameTree.end(); itNoNameANoSubNameAB++)
- {
- counter++;
-
- if (itNoNameANoSubNameAB->getPrefix() == nameA)
- hasA = true;
-
- if (itNoNameANoSubNameAB->getPrefix() == nameAB)
- hasAB = true;
-
- if (itNoNameANoSubNameAB->getPrefix() == nameAB1)
- hasAB1 = true;
-
- if (itNoNameANoSubNameAB->getPrefix() == nameAB2)
- hasAB2 = true;
-
- if (itNoNameANoSubNameAB->getPrefix() == nameAC)
- hasAC = true;
-
- if (itNoNameANoSubNameAB->getPrefix() == nameAC1)
- hasAC1 = true;
-
- if (itNoNameANoSubNameAB->getPrefix() == nameAC2)
- hasAC2 = true;
- }
-
- BOOST_CHECK_EQUAL(hasA, false);
- BOOST_CHECK_EQUAL(hasAB, true);
- BOOST_CHECK_EQUAL(hasAB1, false);
- BOOST_CHECK_EQUAL(hasAB2, false);
- BOOST_CHECK_EQUAL(hasAC, true);
- BOOST_CHECK_EQUAL(hasAC1, true);
- BOOST_CHECK_EQUAL(hasAC2, true);
-
- BOOST_CHECK_EQUAL(counter, 4);
+BOOST_AUTO_TEST_CASE(NoNameANoSubTreeAC)
+{
+ this->insertAb1Ab2Ac1Ac2();
// No NameA
// No SubTree from NameAC
- const_iterator itNoNameANoSubNameAC = nameTree.partialEnumerate(nameA,
- &predicate_NameTreeEntry_NoNameA_NoSubNameAC);
- hasA = false;
- hasAB = false;
- hasAB1 = false;
- hasAB2 = false;
- hasAC = false;
- hasAC1 = false;
- hasAC2 = false;
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ return std::make_pair(entry.getPrefix() != "/a", entry.getPrefix() != "/a/c");
+ });
- counter = 0;
+ EnumerationVerifier(enumerable)
+ .expect("/a/b")
+ .expect("/a/b/1")
+ .expect("/a/b/2")
+ .expect("/a/c")
+ .end();
+}
- for (; itNoNameANoSubNameAC != nameTree.end(); itNoNameANoSubNameAC++)
- {
- counter++;
-
- if (itNoNameANoSubNameAC->getPrefix() == nameA)
- hasA = true;
-
- if (itNoNameANoSubNameAC->getPrefix() == nameAB)
- hasAB = true;
-
- if (itNoNameANoSubNameAC->getPrefix() == nameAB1)
- hasAB1 = true;
-
- if (itNoNameANoSubNameAC->getPrefix() == nameAB2)
- hasAB2 = true;
-
- if (itNoNameANoSubNameAC->getPrefix() == nameAC)
- hasAC = true;
-
- if (itNoNameANoSubNameAC->getPrefix() == nameAC1)
- hasAC1 = true;
-
- if (itNoNameANoSubNameAC->getPrefix() == nameAC2)
- hasAC2 = true;
- }
-
- BOOST_CHECK_EQUAL(hasA, false);
- BOOST_CHECK_EQUAL(hasAB, true);
- BOOST_CHECK_EQUAL(hasAB1, true);
- BOOST_CHECK_EQUAL(hasAB2, true);
- BOOST_CHECK_EQUAL(hasAC, true);
- BOOST_CHECK_EQUAL(hasAC1, false);
- BOOST_CHECK_EQUAL(hasAC2, false);
-
- BOOST_CHECK_EQUAL(counter, 4);
+BOOST_AUTO_TEST_CASE(NoSubTreeA)
+{
+ this->insertAb1Ab2Ac1Ac2();
// No Subtree from NameA
- const_iterator itNoANoSubNameA = nameTree.partialEnumerate(nameA,
- &predicate_NameTreeEntry_NoSubNameA);
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ return std::make_pair(true, entry.getPrefix() != "/a");
+ });
- hasA = false;
- hasAB = false;
- hasAB1 = false;
- hasAB2 = false;
- hasAC = false;
- hasAC1 = false;
- hasAC2 = false;
+ EnumerationVerifier(enumerable)
+ .expect("/a")
+ .end();
+}
- counter = 0;
-
- for (; itNoANoSubNameA != nameTree.end(); itNoANoSubNameA++)
- {
- counter++;
-
- if (itNoANoSubNameA->getPrefix() == nameA)
- hasA = true;
-
- if (itNoANoSubNameA->getPrefix() == nameAB)
- hasAB = true;
-
- if (itNoANoSubNameA->getPrefix() == nameAB1)
- hasAB1 = true;
-
- if (itNoANoSubNameA->getPrefix() == nameAB2)
- hasAB2 = true;
-
- if (itNoANoSubNameA->getPrefix() == nameAC)
- hasAC = true;
-
- if (itNoANoSubNameA->getPrefix() == nameAC1)
- hasAC1 = true;
-
- if (itNoANoSubNameA->getPrefix() == nameAC2)
- hasAC2 = true;
- }
-
- BOOST_CHECK_EQUAL(hasA, true);
- BOOST_CHECK_EQUAL(hasAB, false);
- BOOST_CHECK_EQUAL(hasAB1, false);
- BOOST_CHECK_EQUAL(hasAB2, false);
- BOOST_CHECK_EQUAL(hasAC, false);
- BOOST_CHECK_EQUAL(hasAC1, false);
- BOOST_CHECK_EQUAL(hasAC2, false);
-
- BOOST_CHECK_EQUAL(counter, 1);
-
+BOOST_AUTO_TEST_CASE(Example)
+{
// Example
// /
// /A
@@ -624,163 +459,57 @@
// /E
// /F
- NameTree nameTreeExample(nBuckets);
+ nt.lookup("/A");
+ nt.lookup("/A/B");
+ nt.lookup("/A/B/C");
+ nt.lookup("/A/D");
+ nt.lookup("/E");
+ nt.lookup("/F");
- Name nameRoot("/");
- bool hasRoot = false;
+ auto&& enumerable = nt.partialEnumerate("/A",
+ [] (const name_tree::Entry& entry) -> std::pair<bool, bool> {
+ bool visitEntry = false;
+ bool visitChildren = false;
- nameTreeExample.lookup(nameA);
- hasA = false;
- nameTreeExample.lookup(nameAB);
- hasAB = false;
+ Name name = entry.getPrefix();
- Name nameABC("a/b/c");
- bool hasABC = false;
- nameTreeExample.lookup(nameABC);
+ if (name == "/" || name == "/A/B" || name == "/A/B/C" || name == "/A/D") {
+ visitEntry = true;
+ }
- Name nameAD("/a/d");
- nameTreeExample.lookup(nameAD);
- bool hasAD = false;
+ if (name == "/" || name == "/A" || name == "/F") {
+ visitChildren = true;
+ }
- Name nameE("/e");
- nameTreeExample.lookup(nameE);
- bool hasE = false;
+ return {visitEntry, visitChildren};
+ });
- Name nameF("/f");
- nameTreeExample.lookup(nameF);
- bool hasF = false;
-
- counter = 0;
- const_iterator itExample = nameTreeExample.partialEnumerate(nameA,
- &predicate_NameTreeEntry_Example);
-
- for (; itExample != nameTreeExample.end(); itExample++)
- {
- counter++;
-
- if (itExample->getPrefix() == nameRoot)
- hasRoot = true;
-
- if (itExample->getPrefix() == nameA)
- hasA = true;
-
- if (itExample->getPrefix() == nameAB)
- hasAB = true;
-
- if (itExample->getPrefix() == nameABC)
- hasABC = true;
-
- if (itExample->getPrefix() == nameAD)
- hasAD = true;
-
- if (itExample->getPrefix() == nameE)
- hasE = true;
-
- if (itExample->getPrefix() == nameF)
- hasF = true;
- }
-
- BOOST_CHECK_EQUAL(hasRoot, false);
- BOOST_CHECK_EQUAL(hasA, false);
- BOOST_CHECK_EQUAL(hasAB, true);
- BOOST_CHECK_EQUAL(hasABC, false);
- BOOST_CHECK_EQUAL(hasAD, true);
- BOOST_CHECK_EQUAL(hasE, false);
- BOOST_CHECK_EQUAL(hasF, false);
-
- BOOST_CHECK_EQUAL(counter, 2);
+ EnumerationVerifier(enumerable)
+ .expect("/A/B")
+ .expect("/A/D")
+ .end();
}
+BOOST_AUTO_TEST_SUITE_END()
-BOOST_AUTO_TEST_CASE(IteratorFindAllMatches)
+BOOST_FIXTURE_TEST_CASE(IteratorFindAllMatches, EnumerationFixture)
{
- size_t nBuckets = 16;
- NameTree nt(nBuckets);
- int counter = 0;
-
- Name nameABCDEF("a/b/c/d/e/f");
- shared_ptr<name_tree::Entry> npeABCDEF = nt.lookup(nameABCDEF);
-
- Name nameAAC("a/a/c");
- shared_ptr<name_tree::Entry> npeAAC = nt.lookup(nameAAC);
-
- Name nameAAD1("a/a/d/1");
- shared_ptr<name_tree::Entry> npeAAD1 = nt.lookup(nameAAD1);
-
- Name nameAAD2("a/a/d/2");
- shared_ptr<name_tree::Entry> npeAAD2 = nt.lookup(nameAAD2);
-
-
+ nt.lookup("/a/b/c/d/e/f");
+ nt.lookup("/a/a/c");
+ nt.lookup("/a/a/d/1");
+ nt.lookup("/a/a/d/2");
BOOST_CHECK_EQUAL(nt.size(), 12);
- Name nameRoot ("/");
- Name nameA ("/a");
- Name nameAB ("/a/b");
- Name nameABC ("/a/b/c");
- Name nameABCD ("/a/b/c/d");
- Name nameABCDE("/a/b/c/d/e");
- Name nameAA ("/a/a");
- Name nameAAD ("/a/a/d");
+ auto&& allMatches = nt.findAllMatches("/a/b/c/d/e");
- bool hasRoot = false;
- bool hasA = false;
- bool hasAB = false;
- bool hasABC = false;
- bool hasABCD = false;
- bool hasABCDE = false;
- bool hasABCDEF = false;
- bool hasAA = false;
- bool hasAAC = false;
- bool hasAAD = false;
- bool hasAAD1 = false;
- bool hasAAD2 = false;
-
- counter = 0;
-
- auto&& allMatches = nt.findAllMatches(nameABCDEF);
- for (const name_tree::Entry& entry : allMatches) {
- counter++;
-
- if (entry.getPrefix() == nameRoot)
- hasRoot = true;
- if (entry.getPrefix() == nameA)
- hasA = true;
- if (entry.getPrefix() == nameAB)
- hasAB = true;
- if (entry.getPrefix() == nameABC)
- hasABC = true;
- if (entry.getPrefix() == nameABCD)
- hasABCD = true;
- if (entry.getPrefix() == nameABCDE)
- hasABCDE = true;
- if (entry.getPrefix() == nameABCDEF)
- hasABCDEF = true;
- if (entry.getPrefix() == nameAA)
- hasAA = true;
- if (entry.getPrefix() == nameAAC)
- hasAAC = true;
- if (entry.getPrefix() == nameAAD)
- hasAAD = true;
- if (entry.getPrefix() == nameAAD1)
- hasAAD1 = true;
- if (entry.getPrefix() == nameAAD2)
- hasAAD2 = true;
- }
-
- BOOST_CHECK_EQUAL(hasRoot , true);
- BOOST_CHECK_EQUAL(hasA , true);
- BOOST_CHECK_EQUAL(hasAB , true);
- BOOST_CHECK_EQUAL(hasABC , true);
- BOOST_CHECK_EQUAL(hasABCD , true);
- BOOST_CHECK_EQUAL(hasABCDE , true);
- BOOST_CHECK_EQUAL(hasABCDEF , true);
- BOOST_CHECK_EQUAL(hasAA , false);
- BOOST_CHECK_EQUAL(hasAAC , false);
- BOOST_CHECK_EQUAL(hasAAD , false);
- BOOST_CHECK_EQUAL(hasAAD1 , false);
- BOOST_CHECK_EQUAL(hasAAD2 , false);
-
- BOOST_CHECK_EQUAL(counter, 7);
+ EnumerationVerifier(allMatches)
+ .expect("/")
+ .expect("/a")
+ .expect("/a/b")
+ .expect("/a/b/c")
+ .expect("/a/b/c/d")
+ .expect("/a/b/c/d/e")
+ .end();
}
BOOST_AUTO_TEST_CASE(HashTableResizeShrink)