table: refactor NameTree iterator
refs #3687
Change-Id: Icf5be98d79cfaa27597f62832fcd0189df2731d1
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index 4d7ad0c..b0641d0 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -33,7 +33,6 @@
#include "table/strategy-choice-entry.hpp"
namespace nfd {
-
namespace name_tree {
class Node;
@@ -128,17 +127,19 @@
size_t m_hash;
Name m_prefix;
shared_ptr<Entry> m_parent; // Pointing to the parent entry.
- std::vector<shared_ptr<Entry> > m_children; // Children pointers.
+ std::vector<shared_ptr<Entry>> m_children; // Children pointers.
unique_ptr<fib::Entry> m_fibEntry;
- std::vector<shared_ptr<pit::Entry> > m_pitEntries;
+ std::vector<shared_ptr<pit::Entry>> m_pitEntries;
unique_ptr<measurements::Entry> m_measurementsEntry;
unique_ptr<strategy_choice::Entry> m_strategyChoiceEntry;
// get the Name Tree Node that is associated with this Name Tree Entry
Node* m_node;
- // Make private members accessible by Name Tree
- friend class nfd::NameTree;
+ friend class NameTree;
+ friend class FullEnumerationImpl;
+ friend class PartialEnumerationImpl;
+ friend class PrefixMatchImpl;
};
inline const Name&
@@ -171,7 +172,7 @@
m_parent = parent;
}
-inline std::vector<shared_ptr<name_tree::Entry> >&
+inline std::vector<shared_ptr<name_tree::Entry>>&
Entry::getChildren()
{
return m_children;
diff --git a/daemon/table/name-tree-iterator.cpp b/daemon/table/name-tree-iterator.cpp
new file mode 100644
index 0000000..31077be
--- /dev/null
+++ b/daemon/table/name-tree-iterator.cpp
@@ -0,0 +1,258 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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/>.
+ */
+
+#include "name-tree-iterator.hpp"
+#include "name-tree.hpp"
+#include "core/logger.hpp"
+
+#include <boost/concept/assert.hpp>
+#include <boost/concept_check.hpp>
+#include <type_traits>
+
+namespace nfd {
+namespace name_tree {
+
+NFD_LOG_INIT("NameTreeIterator");
+
+BOOST_CONCEPT_ASSERT((boost::ForwardIterator<Iterator>));
+static_assert(std::is_default_constructible<Iterator>::value,
+ "Iterator must be default-constructible");
+
+Iterator::Iterator()
+ : m_state(0)
+{
+}
+
+Iterator::Iterator(shared_ptr<EnumerationImpl> impl, shared_ptr<Entry> ref)
+ : m_impl(impl)
+ , m_ref(ref)
+ , m_state(0)
+{
+ m_impl->advance(*this);
+ NFD_LOG_TRACE("initialized " << *this);
+}
+
+Iterator&
+Iterator::operator++()
+{
+ BOOST_ASSERT(m_impl != nullptr);
+ m_impl->advance(*this);
+ NFD_LOG_TRACE("advanced " << *this);
+ return *this;
+}
+
+Iterator
+Iterator::operator++(int)
+{
+ Iterator copy = *this;
+ this->operator++();
+ return copy;
+}
+
+bool
+Iterator::operator==(const Iterator& other) const
+{
+ return m_entry == other.m_entry;
+}
+
+std::ostream&
+operator<<(std::ostream& os, const Iterator& i)
+{
+ if (i.m_impl == nullptr) {
+ return os << "end";
+ }
+ if (i.m_entry == nullptr) {
+ return os << "uninitialized";
+ }
+
+ os << "entry=" << i.m_entry->getPrefix();
+ if (i.m_ref == nullptr) {
+ os << " ref=null";
+ }
+ else {
+ os << " ref=" << i.m_ref->getPrefix();
+ }
+ os << " state=" << i.m_state;
+ return os;
+}
+
+EnumerationImpl::EnumerationImpl(const NameTree& nt1)
+ : nt(nt1)
+{
+}
+
+FullEnumerationImpl::FullEnumerationImpl(const NameTree& nt, const EntrySelector& pred)
+ : EnumerationImpl(nt)
+ , m_pred(pred)
+{
+}
+
+void
+FullEnumerationImpl::advance(Iterator& i)
+{
+ // find initial entry
+ if (i.m_entry == nullptr) {
+ for (size_t bucket = 0; bucket < nt.m_nBuckets; ++bucket) {
+ Node* node = nt.m_buckets[bucket];
+ if (node != nullptr) {
+ i.m_entry = node->m_entry;
+ break;
+ }
+ }
+ if (i.m_entry == nullptr) { // empty enumeration
+ i = Iterator();
+ return;
+ }
+ if (m_pred(*i.m_entry)) { // visit initial entry
+ return;
+ }
+ }
+
+ // process entries in same bucket
+ for (Node* node = i.m_entry->m_node->m_next; node != nullptr; node = node->m_next) {
+ if (m_pred(*node->m_entry)) {
+ i.m_entry = node->m_entry;
+ return;
+ }
+ }
+
+ // process other buckets
+ for (size_t bucket = i.m_entry->m_hash % nt.m_nBuckets + 1; bucket < nt.m_nBuckets; ++bucket) {
+ for (Node* node = nt.m_buckets[bucket]; node != nullptr; node = node->m_next) {
+ if (m_pred(*node->m_entry)) {
+ i.m_entry = node->m_entry;
+ return;
+ }
+ }
+ }
+
+ // reach the end
+ i = Iterator();
+}
+
+PartialEnumerationImpl::PartialEnumerationImpl(const NameTree& nt, const EntrySubTreeSelector& pred)
+ : EnumerationImpl(nt)
+ , m_pred(pred)
+{
+}
+
+void
+PartialEnumerationImpl::advance(Iterator& i)
+{
+ bool wantSelf = false;
+ bool wantChildren = false;
+
+ // initialize: start from root
+ if (i.m_entry == nullptr) {
+ if (i.m_ref == nullptr) { // empty enumeration
+ i = Iterator();
+ return;
+ }
+
+ i.m_entry = i.m_ref;
+ std::tie(wantSelf, wantChildren) = m_pred(*i.m_entry);
+ if (wantSelf) { // visit root
+ i.m_state = wantChildren;
+ return;
+ }
+ }
+ else {
+ wantChildren = static_cast<bool>(i.m_state);
+ }
+ BOOST_ASSERT(i.m_ref != nullptr);
+
+ // pre-order traversal
+ while (i.m_entry != i.m_ref || (wantChildren && i.m_entry->hasChildren())) {
+ if (wantChildren && i.m_entry->hasChildren()) { // process children of m_entry
+ i.m_entry = i.m_entry->getChildren().front();
+ std::tie(wantSelf, wantChildren) = m_pred(*i.m_entry);
+ if (wantSelf) { // visit first child
+ i.m_state = wantChildren;
+ return;
+ }
+ // first child rejected, let while loop process other children (siblings of new m_entry)
+ }
+ else { // process siblings of m_entry
+ shared_ptr<Entry> parent = i.m_entry->getParent();
+ const std::vector<shared_ptr<Entry>>& siblings = parent->getChildren();
+ auto sibling = std::find(siblings.begin(), siblings.end(), i.m_entry);
+ BOOST_ASSERT(sibling != siblings.end());
+ while (++sibling != siblings.end()) {
+ i.m_entry = *sibling;
+ std::tie(wantSelf, wantChildren) = m_pred(*i.m_entry);
+ if (wantSelf) { // visit sibling
+ i.m_state = wantChildren;
+ return;
+ }
+ if (wantChildren) {
+ break; // let outer while loop process children of m_entry
+ }
+ // process next sibling
+ }
+ if (sibling == siblings.end()) { // no more sibling
+ i.m_entry = parent;
+ wantChildren = false;
+ }
+ }
+ }
+
+ // reach the end
+ i = Iterator();
+}
+
+PrefixMatchImpl::PrefixMatchImpl(const NameTree& nt, const EntrySelector& pred)
+ : EnumerationImpl(nt)
+ , m_pred(pred)
+{
+}
+
+void
+PrefixMatchImpl::advance(Iterator& i)
+{
+ if (i.m_entry == nullptr) {
+ if (i.m_ref == nullptr) { // empty enumeration
+ i = Iterator();
+ return;
+ }
+
+ i.m_entry = i.m_ref;
+ if (m_pred(*i.m_entry)) { // visit starting node
+ return;
+ }
+ }
+
+ // traverse up the tree
+ while ((i.m_entry = i.m_entry->getParent()) != nullptr) {
+ if (m_pred(*i.m_entry)) {
+ return;
+ }
+ }
+
+ // reach the end
+ i = Iterator();
+}
+
+} // namespace name_tree
+} // namespace nfd
diff --git a/daemon/table/name-tree-iterator.hpp b/daemon/table/name-tree-iterator.hpp
new file mode 100644
index 0000000..a764677
--- /dev/null
+++ b/daemon/table/name-tree-iterator.hpp
@@ -0,0 +1,201 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014-2016, 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/>.
+ */
+
+#ifndef NFD_DAEMON_TABLE_NAME_TREE_ITERATOR_HPP
+#define NFD_DAEMON_TABLE_NAME_TREE_ITERATOR_HPP
+
+#include "name-tree-entry.hpp"
+
+namespace nfd {
+namespace name_tree {
+
+/** \brief a predicate to accept or reject an Entry in find operations
+ */
+typedef function<bool(const Entry& entry)> EntrySelector;
+
+/** \brief an EntrySelector that accepts every Entry
+ */
+struct AnyEntry
+{
+ bool
+ operator()(const Entry& entry) const
+ {
+ return true;
+ }
+};
+
+/** \brief a predicate to accept or reject an Entry and its children
+ * \return .first indicates whether entry should be accepted;
+ * .second indicates whether entry's children should be visited
+ */
+typedef function<std::pair<bool,bool>(const Entry& entry)> EntrySubTreeSelector;
+
+/** \brief an EntrySubTreeSelector that accepts every Entry and its children
+ */
+struct AnyEntrySubTree
+{
+ std::pair<bool, bool>
+ operator()(const Entry& entry) const
+ {
+ return {true, true};
+ }
+};
+
+class EnumerationImpl;
+
+/** \brief NameTree iterator
+ */
+class Iterator : public std::iterator<std::forward_iterator_tag, const Entry>
+{
+public:
+ Iterator();
+
+ Iterator(shared_ptr<EnumerationImpl> impl, shared_ptr<Entry> ref);
+
+ virtual
+ ~Iterator() = default;
+
+ const Entry&
+ operator*() const
+ {
+ BOOST_ASSERT(m_impl != nullptr);
+ return *m_entry;
+ }
+
+ shared_ptr<Entry>
+ operator->() const
+ {
+ BOOST_ASSERT(m_impl != nullptr);
+ return m_entry;
+ }
+
+ Iterator&
+ operator++();
+
+ Iterator
+ operator++(int);
+
+ bool
+ operator==(const Iterator& other) const;
+
+ bool
+ operator!=(const Iterator& other) const
+ {
+ return !this->operator==(other);
+ }
+
+private:
+ /** \brief enumeration implementation; nullptr for end iterator
+ */
+ shared_ptr<EnumerationImpl> m_impl;
+
+ /** \brief current entry; nullptr for uninitialized iterator
+ */
+ shared_ptr<Entry> m_entry;
+
+ /** \brief reference entry used by enumeration implementation
+ */
+ shared_ptr<Entry> m_ref;
+
+ /** \brief state used by enumeration implementation
+ */
+ int m_state;
+
+ friend std::ostream& operator<<(std::ostream&, const Iterator&);
+ friend class FullEnumerationImpl;
+ friend class PartialEnumerationImpl;
+ friend class PrefixMatchImpl;
+};
+
+std::ostream&
+operator<<(std::ostream& os, const Iterator& i);
+
+/** \brief enumeration operation implementation
+ */
+class EnumerationImpl
+{
+public:
+ explicit
+ EnumerationImpl(const NameTree& nt);
+
+ virtual void
+ advance(Iterator& i) = 0;
+
+protected:
+ const NameTree& nt;
+};
+
+/** \brief full enumeration implementation
+ */
+class FullEnumerationImpl : public EnumerationImpl
+{
+public:
+ FullEnumerationImpl(const NameTree& nt, const EntrySelector& pred);
+
+ virtual void
+ advance(Iterator& i) override;
+
+private:
+ EntrySelector m_pred;
+};
+
+/** \brief partial enumeration implementation
+ *
+ * Iterator::m_ref should be initialized to subtree root.
+ * Iterator::m_state LSB indicates whether to visit children of m_entry.
+ */
+class PartialEnumerationImpl : public EnumerationImpl
+{
+public:
+ PartialEnumerationImpl(const NameTree& nt, const EntrySubTreeSelector& pred);
+
+ virtual void
+ advance(Iterator& i) override;
+
+private:
+ EntrySubTreeSelector m_pred;
+};
+
+/** \brief partial enumeration implementation
+ *
+ * Iterator::m_ref should be initialized to longest prefix matched entry.
+ */
+class PrefixMatchImpl : public EnumerationImpl
+{
+public:
+ PrefixMatchImpl(const NameTree& nt, const EntrySelector& pred);
+
+private:
+ virtual void
+ advance(Iterator& i) override;
+
+private:
+ EntrySelector m_pred;
+};
+
+} // namespace name_tree
+} // namespace nfd
+
+#endif // NFD_DAEMON_TABLE_NAME_TREE_ITERATOR_HPP
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index abc5672..09b57f7 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -118,7 +118,6 @@
, m_enlargeFactor(2) // double the hash table size
, m_shrinkLoadFactor(0.1) // less than 10% buckets loaded
, m_shrinkFactor(0.5) // reduce the number of buckets by half
- , m_endIterator(FULL_ENUMERATE_TYPE, *this, m_end)
{
m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor * static_cast<double>(m_nBuckets));
m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor * static_cast<double>(m_nBuckets));
@@ -437,13 +436,7 @@
// trie from the root node.
shared_ptr<Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
-
- if (entry != nullptr) {
- const_iterator begin(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
- return {begin, end()};
- }
- // If none of the entry satisfies the requirements, then return the end() iterator.
- return {end(), end()};
+ return {Iterator(make_shared<PrefixMatchImpl>(*this, entrySelector), entry), end()};
}
boost::iterator_range<NameTree::const_iterator>
@@ -451,18 +444,7 @@
{
NFD_LOG_TRACE("fullEnumerate");
- // find the first eligible entry
- for (size_t i = 0; i < m_nBuckets; ++i) {
- for (Node* node = m_buckets[i]; node != nullptr; node = node->m_next) {
- if (node->m_entry != nullptr && 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(), end()};
+ return {Iterator(make_shared<FullEnumerationImpl>(*this, entrySelector), nullptr), end()};
}
boost::iterator_range<NameTree::const_iterator>
@@ -471,27 +453,7 @@
{
// the first step is to process the root node
shared_ptr<Entry> entry = findExactMatch(prefix);
- if (entry == nullptr) {
- return {end(), end()};
- }
-
- std::pair<bool, bool> result = entrySubTreeSelector(*entry);
- const_iterator it(PARTIAL_ENUMERATE_TYPE,
- *this,
- entry,
- AnyEntry(),
- entrySubTreeSelector);
-
- it.m_shouldVisitChildren = (result.second && entry->hasChildren());
-
- if (result.first) {
- // root node is acceptable
- }
- else {
- // let the ++ operator handle it
- ++it;
- }
- return {it, end()};
+ return {Iterator(make_shared<PartialEnumerationImpl>(*this, entrySubTreeSelector), entry), end()};
}
// Hash Table Resize
@@ -585,165 +547,5 @@
output << "--------------------------\n";
}
-NameTree::const_iterator::const_iterator()
- : m_nameTree(nullptr)
-{
-}
-
-NameTree::const_iterator::const_iterator(NameTree::IteratorType type,
- const NameTree& nameTree,
- shared_ptr<Entry> entry,
- const EntrySelector& entrySelector,
- const EntrySubTreeSelector& entrySubTreeSelector)
- : m_nameTree(&nameTree)
- , m_entry(entry)
- , m_subTreeRoot(entry)
- , m_entrySelector(make_shared<EntrySelector>(entrySelector))
- , m_entrySubTreeSelector(make_shared<EntrySubTreeSelector>(entrySubTreeSelector))
- , m_type(type)
- , m_shouldVisitChildren(true)
-{
-}
-
-// operator++()
-NameTree::const_iterator
-NameTree::const_iterator::operator++()
-{
- NFD_LOG_TRACE("const_iterator::operator++()");
-
- BOOST_ASSERT(m_entry != m_nameTree->m_end);
-
- if (m_type == FULL_ENUMERATE_TYPE) {
- // process the entries in the same bucket first
- while (m_entry->m_node->m_next != nullptr) {
- m_entry = m_entry->m_node->m_next->m_entry;
- if ((*m_entrySelector)(*m_entry)) {
- return *this;
- }
- }
-
- // process other buckets
-
- for (int newLocation = m_entry->m_hash % m_nameTree->m_nBuckets + 1;
- newLocation < static_cast<int>(m_nameTree->m_nBuckets);
- ++newLocation) {
- // process each bucket
- Node* node = m_nameTree->m_buckets[newLocation];
- while (node != nullptr) {
- m_entry = node->m_entry;
- if ((*m_entrySelector)(*m_entry)) {
- return *this;
- }
- node = node->m_next;
- }
- }
-
- // Reach the end()
- m_entry = m_nameTree->m_end;
- return *this;
- }
-
- if (m_type == PARTIAL_ENUMERATE_TYPE) {
- // We use pre-order traversal.
- // if at the root, it could have already been accepted, or this
- // iterator was just declared, and root doesn't satisfy the
- // requirement
- // The if() section handles this special case
- // Essentially, we need to check root's fist child, and the rest will
- // be the same as normal process
- if (m_entry == m_subTreeRoot) {
- if (m_shouldVisitChildren) {
- m_entry = m_entry->getChildren()[0];
- std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
- m_shouldVisitChildren = (result.second && m_entry->hasChildren());
- if (result.first) {
- return *this;
- }
- else {
- // the first child did not meet the requirement
- // the rest of the process can just fall through the while loop as normal
- }
- }
- else {
- // no children, should return end();
- // just fall through
- }
- }
-
- // The first thing to do is to visit its child, or go to find its possible siblings
- while (m_entry != m_subTreeRoot) {
- if (m_shouldVisitChildren) {
- // If this subtree should be visited
- m_entry = m_entry->getChildren()[0];
- std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
- m_shouldVisitChildren = (result.second && m_entry->hasChildren());
- if (result.first) { // if this node is acceptable
- return *this;
- }
- else {
- // do nothing, as this node is essentially ignored
- // send this node to the while loop.
- }
- }
- else {
- // Should try to find its sibling
- shared_ptr<Entry> parent = m_entry->getParent();
-
- std::vector<shared_ptr<Entry>>& parentChildrenList = parent->getChildren();
- bool isFound = false;
- size_t i = 0;
- for (i = 0; i < parentChildrenList.size(); ++i) {
- if (parentChildrenList[i] == m_entry) {
- isFound = true;
- break;
- }
- }
-
- BOOST_VERIFY(isFound == true);
- if (i < parentChildrenList.size() - 1) { // m_entry not the last child
- m_entry = parentChildrenList[i + 1];
- std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
- m_shouldVisitChildren = (result.second && m_entry->hasChildren());
- if (result.first) { // if this node is acceptable
- return *this;
- }
- else {
- // do nothing, as this node is essentially ignored
- // send this node to the while loop.
- }
- }
- else {
- // m_entry is the last child, no more sibling, should try to find parent's sibling
- m_shouldVisitChildren = false;
- m_entry = parent;
- }
- }
- }
-
- m_entry = m_nameTree->m_end;
- return *this;
- }
-
- if (m_type == FIND_ALL_MATCHES_TYPE) {
- // Assumption: at the beginning, m_entry was initialized with the first
- // eligible Name Tree entry (i.e., has a PIT entry that can be satisfied
- // by the Data packet)
-
- while (m_entry->getParent() != nullptr) {
- m_entry = m_entry->getParent();
- if ((*m_entrySelector)(*m_entry)) {
- return *this;
- }
- }
-
- // Reach to the end (Root)
- m_entry = m_nameTree->m_end;
- return *this;
- }
-
- BOOST_ASSERT(false); // unknown type
- return *this;
-}
-
} // namespace name_tree
} // namespace nfd
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index fa20034..91ec3fa 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -26,8 +26,7 @@
#ifndef NFD_DAEMON_TABLE_NAME_TREE_HPP
#define NFD_DAEMON_TABLE_NAME_TREE_HPP
-#include "core/common.hpp"
-#include "name-tree-entry.hpp"
+#include "name-tree-iterator.hpp"
namespace nfd {
namespace name_tree {
@@ -43,40 +42,12 @@
std::vector<size_t>
computeHashSet(const Name& prefix);
-/** \brief a predicate to accept or reject an Entry in find operations
- */
-typedef function<bool(const Entry& entry)> EntrySelector;
-
-/** \brief a predicate to accept or reject an Entry and its children
- * \return .first indicates whether entry should be accepted;
- * .second indicates whether entry's children should be visited
- */
-typedef function<std::pair<bool,bool>(const Entry& entry)> EntrySubTreeSelector;
-
-struct AnyEntry
-{
- bool
- operator()(const Entry& entry) const
- {
- return true;
- }
-};
-
-struct AnyEntrySubTree
-{
- std::pair<bool, bool>
- operator()(const Entry& entry) const
- {
- return {true, true};
- }
-};
-
/** \brief shared name-based index for FIB, PIT, Measurements, and StrategyChoice
*/
class NameTree : noncopyable
{
public:
- class const_iterator;
+ typedef Iterator const_iterator;
explicit
NameTree(size_t nBuckets = 1024);
@@ -255,53 +226,6 @@
const_iterator
end() const;
- enum IteratorType {
- FULL_ENUMERATE_TYPE,
- PARTIAL_ENUMERATE_TYPE,
- FIND_ALL_MATCHES_TYPE
- };
-
- class const_iterator : public std::iterator<std::forward_iterator_tag, const Entry>
- {
- public:
- friend class NameTree;
-
- const_iterator();
-
- const_iterator(NameTree::IteratorType type,
- const NameTree& nameTree,
- shared_ptr<Entry> entry,
- const EntrySelector& entrySelector = AnyEntry(),
- const EntrySubTreeSelector& entrySubTreeSelector = AnyEntrySubTree());
-
- const Entry&
- operator*() const;
-
- shared_ptr<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:
- const NameTree* m_nameTree;
- shared_ptr<Entry> m_entry;
- shared_ptr<Entry> m_subTreeRoot;
- shared_ptr<EntrySelector> m_entrySelector;
- shared_ptr<EntrySubTreeSelector> m_entrySubTreeSelector;
- NameTree::IteratorType m_type;
- bool m_shouldVisitChildren;
- };
-
private:
/** \brief Create a Name Tree Entry if it does not exist, or return the existing
* Name Tree Entry address.
@@ -336,8 +260,10 @@
size_t m_shrinkThreshold;
double m_shrinkFactor;
Node** m_buckets; ///< Name Tree Buckets in the NPHT
- shared_ptr<Entry> m_end;
- const_iterator m_endIterator;
+
+ friend class FullEnumerationImpl;
+ friend class PartialEnumerationImpl;
+ friend class PrefixMatchImpl;
};
inline size_t
@@ -368,39 +294,7 @@
inline NameTree::const_iterator
NameTree::end() const
{
- return m_endIterator;
-}
-
-inline const Entry&
-NameTree::const_iterator::operator*() const
-{
- return *m_entry;
-}
-
-inline shared_ptr<Entry>
-NameTree::const_iterator::operator->() const
-{
- return m_entry;
-}
-
-inline NameTree::const_iterator
-NameTree::const_iterator::operator++(int)
-{
- NameTree::const_iterator temp(*this);
- ++(*this);
- return temp;
-}
-
-inline bool
-NameTree::const_iterator::operator==(const NameTree::const_iterator& other) const
-{
- return m_entry == other.m_entry;
-}
-
-inline bool
-NameTree::const_iterator::operator!=(const NameTree::const_iterator& other) const
-{
- return m_entry != other.m_entry;
+ return Iterator();
}
} // namespace name_tree