table: NameTree enumeration
refs #1318
Change-Id: I26f25cefe8f2939ca884103f1b081c0c02325207
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 32aabbf..eea7641 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -87,13 +87,12 @@
void
Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
{
- shared_ptr<std::vector<shared_ptr<name_tree::Entry > > > nameTreeEntries =
- m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry);
- for (size_t i = 0; i < nameTreeEntries->size(); ++i) {
- shared_ptr<fib::Entry> entry = nameTreeEntries->at(i)->getFibEntry();
+ for (NameTree::const_iterator it =
+ m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end(); it++)
+ {
+ shared_ptr<fib::Entry> entry = it->getFibEntry();
entry->removeNextHop(face);
}
}
-
} // namespace nfd
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index 1708dbf..cca1908 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -21,12 +21,12 @@
namespace name_tree {
-// Forward declaration
+// Forward declarations
class Node;
class Entry;
/**
- * @brief Name Tree Node Class
+ * \brief Name Tree Node Class
*/
class Node
{
@@ -43,9 +43,9 @@
};
/**
- * @brief Name Tree Entry Class
+ * \brief Name Tree Entry Class
*/
-class Entry
+class Entry : noncopyable
{
// Make private members accessible by Name Tree
friend class nfd::NameTree;
@@ -72,7 +72,10 @@
std::vector<shared_ptr<Entry> >&
getChildren();
-
+
+ bool
+ hasChildren() const;
+
bool
isEmpty() const;
@@ -88,12 +91,15 @@
void
insertPitEntry(shared_ptr<pit::Entry> pit);
+ bool
+ hasPitEntries() const;
+
std::vector<shared_ptr<pit::Entry> >&
getPitEntries();
/**
- * @brief Erase a PIT Entry
- * @details The address of this PIT Entry is required
+ * \brief Erase a PIT Entry
+ * \details The address of this PIT Entry is required
*/
bool
erasePitEntry(shared_ptr<pit::Entry> pit);
@@ -152,6 +158,12 @@
}
inline bool
+Entry::hasChildren() const
+{
+ return !m_children.empty();
+}
+
+inline bool
Entry::isEmpty() const
{
return m_children.empty() &&
@@ -166,6 +178,12 @@
return m_fibEntry;
}
+inline bool
+Entry::hasPitEntries() const
+{
+ return !m_pitEntries.empty();
+}
+
inline std::vector<shared_ptr<pit::Entry> >&
Entry::getPitEntries()
{
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 964730e..5d11c27 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -38,6 +38,7 @@
, m_nBuckets(nBuckets)
, m_loadFactor(0.5)
, m_resizeFactor(2)
+ , m_endIterator(FULL_ENUMERATE_TYPE, *this, m_end)
{
m_resizeThreshold = static_cast<size_t>(m_loadFactor *
static_cast<double>(m_nBuckets));
@@ -186,7 +187,7 @@
// Return the longest matching Entry address
// start from the full name, and then remove 1 name comp each time
shared_ptr<name_tree::Entry>
-NameTree::findLongestPrefixMatch(const Name& prefix, const name_tree::EntrySelector& entrySelector)
+NameTree::findLongestPrefixMatch(const Name& prefix, const name_tree::EntrySelector& entrySelector) const
{
NFD_LOG_DEBUG("findLongestPrefixMatch " << prefix);
@@ -274,63 +275,82 @@
return false; // if this entry is not empty
}
-shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
-NameTree::fullEnumerate(const name_tree::EntrySelector& entrySelector)
+NameTree::const_iterator
+NameTree::fullEnumerate(const name_tree::EntrySelector& entrySelector) const
{
NFD_LOG_DEBUG("fullEnumerate");
- shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > results =
- make_shared<std::vector<shared_ptr<name_tree::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)) {
- results->push_back(node->m_entry);
- }
- }
- }
-
- return results;
-}
-
-// Helper function for partialEnumerate()
-void
-NameTree::partialEnumerateAddChildren(shared_ptr<name_tree::Entry> entry,
- const name_tree::EntrySelector& entrySelector,
- std::vector<shared_ptr<name_tree::Entry> >& results)
-{
- BOOST_ASSERT(static_cast<bool>(entry));
-
- if (!entrySelector(*entry)) {
- return;
- }
-
- results.push_back(entry);
- for (size_t i = 0; i < entry->m_children.size(); i++)
+ // find the first eligible entry
+ for (size_t i = 0; i < m_nBuckets; i++)
{
- shared_ptr<name_tree::Entry> child = entry->m_children[i];
- partialEnumerateAddChildren(child, entrySelector, results);
+ 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;
+ }
+ }
+ }
+
+ // If none of the entry satisfies the requirements, then return the end() iterator.
+ return end();
+}
+
+NameTree::const_iterator
+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();
+ }
+
+ std::pair<bool, bool>result = entrySubTreeSelector(*entry);
+ const_iterator it(PARTIAL_ENUMERATE_TYPE,
+ *this,
+ entry,
+ name_tree::AnyEntry(),
+ entrySubTreeSelector);
+
+ 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;
}
}
-shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
-NameTree::partialEnumerate(const Name& prefix,
- const name_tree::EntrySelector& entrySelector)
+NameTree::const_iterator
+NameTree::findAllMatches(const Name& prefix,
+ const name_tree::EntrySelector& entrySelector) const
{
- NFD_LOG_DEBUG("partialEnumerate" << prefix);
+ NFD_LOG_DEBUG("NameTree::findAllMatches" << prefix);
- shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > results =
- make_shared<std::vector<shared_ptr<name_tree::Entry> > >();
+ // As we are using Name Prefix Hash Table, and the current LPM() is
+ // implemented as starting from full name, and reduce the number of
+ // components by 1 each time, we could use it here.
+ // For trie-like design, it could be more efficient by walking down the
+ // trie from the root node.
- // find the hash bucket corresponding to that prefix
- shared_ptr<name_tree::Entry> entry = findExactMatch(prefix);
+ shared_ptr<name_tree::Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
- if (static_cast<bool>(entry)) {
- // go through its children list via depth-first-search
- partialEnumerateAddChildren(entry, entrySelector, *results);
- }
-
- return results;
+ if (static_cast<bool>(entry))
+ {
+ const_iterator it(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
+ return it;
+ }
+ // If none of the entry satisfies the requirements, then return the end() iterator.
+ return end();
}
// Hash Table Resize
@@ -388,7 +408,7 @@
// For debugging
void
-NameTree::dump(std::ostream& output)
+NameTree::dump(std::ostream& output) const
{
NFD_LOG_DEBUG("dump()");
@@ -440,4 +460,183 @@
output << "--------------------------\n";
}
+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_entry(entry)
+ , m_subTreeRoot(entry)
+ , m_entrySelector(make_shared<name_tree::EntrySelector>(entrySelector))
+ , m_entrySubTreeSelector(make_shared<name_tree::EntrySubTreeSelector>(entrySubTreeSelector))
+ , m_type(type)
+ , m_shouldVisitChildren(true)
+{
+}
+
+// operator++()
+NameTree::const_iterator
+NameTree::const_iterator::operator++()
+{
+ NFD_LOG_DEBUG("const_iterator::operator++()");
+
+ BOOST_ASSERT(m_entry != m_nameTree.m_end);
+
+ if (m_type == FULL_ENUMERATE_TYPE) // fullEnumerate
+ {
+ bool isFound = false;
+ // process the entries in the same bucket first
+ while (m_entry->m_node->m_next != 0)
+ {
+ m_entry = m_entry->m_node->m_next->m_entry;
+ if ((*m_entrySelector)(*m_entry))
+ {
+ isFound = true;
+ return *this;
+ }
+ }
+
+ // process other buckets
+ int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
+ for (newLocation = newLocation; newLocation < m_nameTree.m_nBuckets; newLocation++)
+ {
+ // process each bucket
+ name_tree::Node* node = m_nameTree.m_buckets[newLocation];
+ while (node != 0)
+ {
+ m_entry = node->m_entry;
+ if ((*m_entrySelector)(*m_entry))
+ {
+ isFound = true;
+ return *this;
+ }
+ node = node->m_next;
+ }
+ }
+ BOOST_ASSERT(isFound == false);
+ // Reach to the end()
+ m_entry = m_nameTree.m_end;
+ return *this;
+ }
+
+ if (m_type == PARTIAL_ENUMERATE_TYPE) // partialEnumerate
+ {
+ // 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<name_tree::Entry> parent = m_entry->getParent();
+
+ std::vector<shared_ptr<name_tree::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_ASSERT(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) // findAllMatches
+ {
+ // 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 (static_cast<bool>(m_entry->getParent()))
+ {
+ 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;
+ }
+}
+
} // namespace nfd
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 812c916..1a30b2b 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -16,8 +16,8 @@
namespace name_tree {
/**
- * @brief Compute the hash value of the given name prefix.
- * @todo 1) have another parameter that specifies the number of components
+ * \brief Compute the hash value of the given name prefix.
+ * \todo 1) have another parameter that specifies the number of components
* 2) optimize the hash function to return a list of have values for all
* the (or a certain number of, like a batch operation) prefixes. 3) move
* the hash-related code to a separate file in /core or ndn-cpp-dev lib.
@@ -28,6 +28,13 @@
/// 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)
@@ -36,134 +43,201 @@
}
};
+struct AnyEntrySubTree {
+ std::pair<bool, bool>
+ operator()(const Entry& entry)
+ {
+ return std::make_pair(true, true);
+ }
+};
+
} // namespace name_tree
/**
- * @brief Class Name Tree
+ * \brief Class Name Tree
*/
class NameTree : noncopyable
{
public:
+ class const_iterator;
+
explicit
NameTree(size_t nBuckets);
~NameTree();
/**
- * @brief Get the number of occupied entries in the Name Tree
+ * \brief Get the number of occupied entries in the Name Tree
*/
size_t
size() const;
/**
- * @brief Get the number of buckets in the Name Tree (NPHT)
- * @details The number of buckets is the one that used to create the hash
+ * \brief Get the number of buckets in the Name Tree (NPHT)
+ * \details The number of buckets is the one that used to create the hash
* table, i.e., m_nBuckets.
*/
size_t
getNBuckets() const;
/**
- * @brief Look for the Name Tree Entry that contains this name prefix.
- * @details Starts from the shortest name prefix, and then increase the
+ * \brief Look for the Name Tree Entry that contains this name prefix.
+ * \details Starts from the shortest name prefix, and then increase the
* number of name components by one each time. All non-existing Name Tree
* Entries will be created.
- * @param prefix The querying name prefix.
- * @return The pointer to the Name Tree Entry that contains this full name
+ * \param prefix The querying name prefix.
+ * \return The pointer to the Name Tree Entry that contains this full name
* prefix.
*/
shared_ptr<name_tree::Entry>
lookup(const Name& prefix);
/**
- * @brief Exact match lookup for the given name prefix.
- * @return a null shared_ptr if this prefix is not found;
+ * \brief Exact match lookup for the given name prefix.
+ * \return a null shared_ptr if this prefix is not found;
* otherwise return the Name Tree Entry address
*/
shared_ptr<name_tree::Entry>
findExactMatch(const Name& prefix) const;
/**
- * @brief Erase a Name Tree Entry if this entry is empty.
- * @details If a Name Tree Entry contains no Children, no FIB, no PIT, and
+ * \brief Erase a Name Tree Entry if this entry is empty.
+ * \details If a Name Tree Entry contains no Children, no FIB, no PIT, and
* no Measurements entries, then it can be erased. In addition, its parent entry
* will also be examined by following the parent pointer until all empty entries
* are erased.
- * @param entry The pointer to the entry to be erased. The entry pointer should
+ * \param entry The pointer to the entry to be erased. The entry pointer should
* returned by the findExactMatch(), lookup(), or findLongestPrefixMatch() functions.
*/
bool
eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry);
/**
- * @brief Longest prefix matching for the given name
- * @details Starts from the full name string, reduce the number of name component
+ * \brief Longest prefix matching for the given name
+ * \details Starts from the full name string, reduce the number of name component
* by one each time, until an Entry is found.
*/
shared_ptr<name_tree::Entry>
findLongestPrefixMatch(const Name& prefix,
- const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry());
+ const name_tree::EntrySelector& entrySelector =
+ name_tree::AnyEntry()) const;
/**
- * @brief Resize the hash table size when its load factor reaches a threshold.
- * @details As we are currently using a hand-written hash table implementation
+ * \brief Resize the hash table size when its load factor reaches a threshold.
+ * \details As we are currently using a hand-written hash table implementation
* for the Name Tree, the hash table resize() function should be kept in the
* name-tree.hpp file.
- * @param newNBuckets The number of buckets for the new hash table.
+ * \param newNBuckets The number of buckets for the new hash table.
*/
void
resize(size_t newNBuckets);
/**
- * @brief Enumerate all the name prefixes stored in the Name Tree.
+ * \brief Enumerate all the name prefixes stored in the Name Tree.
*/
- shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
- fullEnumerate(const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry());
+ const_iterator
+ fullEnumerate(const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
/**
- * @brief Enumerate all the name prefixes under a specific name prefix
- * @todo It might be better to have functions like fullEnemerateFib() to reduce the
- * number of entries stored in the vector.
- */
- shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
+ * \brief Enumerate all the name prefixes that satisfies the EntrySubTreeSelector.
+ */
+ const_iterator
partialEnumerate(const Name& prefix,
- const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry());
+ const name_tree::EntrySubTreeSelector& entrySubTreeSelector = name_tree::AnyEntrySubTree()) const;
/**
- * @brief Dump all the information stored in the Name Tree for debugging.
+ * \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
+ */
+ const_iterator
+ findAllMatches(const Name& prefix,
+ const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
+
+ /**
+ * \brief Dump all the information stored in the Name Tree for debugging.
*/
void
- dump(std::ostream& output);
+ dump(std::ostream& output) const;
+
+ const_iterator
+ begin() const;
+
+ 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, name_tree::Entry>
+ {
+ public:
+ friend class NameTree;
+
+ const_iterator(NameTree::IteratorType type,
+ const NameTree& nameTree,
+ shared_ptr<name_tree::Entry> entry,
+ const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry(),
+ const name_tree::EntrySubTreeSelector& entrySubTreeSelector = name_tree::AnyEntrySubTree());
+
+ ~const_iterator();
+
+ const name_tree::Entry&
+ operator*() const;
+
+ shared_ptr<name_tree::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:
+ bool m_shouldVisitChildren;
+ 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;
+ shared_ptr<name_tree::EntrySubTreeSelector> m_entrySubTreeSelector;
+ NameTree::IteratorType m_type;
+ };
private:
- size_t m_nItems; // Number of items being stored
- size_t m_nBuckets; // Number of hash buckets
- double m_loadFactor;
- size_t m_resizeThreshold;
- int m_resizeFactor;
- name_tree::Node** m_buckets; // Name Tree Buckets in the NPHT
+ size_t m_nItems; // Number of items being stored
+ size_t m_nBuckets; // Number of hash buckets
+ double m_loadFactor;
+ size_t m_resizeThreshold;
+ int m_resizeFactor;
+ name_tree::Node** m_buckets; // Name Tree Buckets in the NPHT
+ shared_ptr<name_tree::Entry> m_end;
+ const_iterator m_endIterator;
/**
- * @brief Create a Name Tree Entry if it does not exist, or return the existing
+ * \brief Create a Name Tree Entry if it does not exist, or return the existing
* Name Tree Entry address.
- * @details Called by lookup() only.
- * @return The first item is the Name Tree Entry address, the second item is
+ * \details Called by lookup() only.
+ * \return The first item is the Name Tree Entry address, the second item is
* a bool value indicates whether this is an old entry (false) or a new
* entry (true).
*/
std::pair<shared_ptr<name_tree::Entry>, bool>
insert(const Name& prefix);
-
- /**
- * @brief Helper function for partialEnumerate()
- */
- void
- partialEnumerateAddChildren(shared_ptr<name_tree::Entry> entry,
- const name_tree::EntrySelector& entrySelector,
- std::vector<shared_ptr<name_tree::Entry> >& results);
-
};
+inline NameTree::const_iterator::~const_iterator()
+{
+}
+
inline size_t
NameTree::size() const
{
@@ -176,6 +250,50 @@
return m_nBuckets;
}
+inline NameTree::const_iterator
+NameTree::begin() const
+{
+ return fullEnumerate();
+}
+
+inline NameTree::const_iterator
+NameTree::end() const
+{
+ return m_endIterator;
+}
+
+inline const name_tree::Entry&
+NameTree::const_iterator::operator*() const
+{
+ return *m_entry;
+}
+
+inline shared_ptr<name_tree::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;
+}
+
} // namespace nfd
#endif // NFD_TABLE_NAME_TREE_HPP
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index 6f5acf3..dafec47 100644
--- a/daemon/table/pit.cpp
+++ b/daemon/table/pit.cpp
@@ -4,19 +4,6 @@
* See COPYING for copyright and distribution information.
*/
-/**
- * KNOWN ISSUES
- *
- * - To remove a PIT entry, we need to first perform a lookup on NameTree
- * to locate its NameTree Entry, and then call NameTreeEntry->deletePitEntry()
- * function. Alternatively, we could store a pointer at each PIT-Entry, which
- * would speed up this procedure with the cost of additional memory space. Maybe
- * this could also be part of the PIT/FIB/Measurement shortcut, where all of these
- * entries have pointers to their NameTreeEntry. Which could be part of task
- * #1202, shortcuts between FIB, PIT, Measurements.
- *
- */
-
#include "pit.hpp"
namespace nfd {
@@ -30,6 +17,12 @@
}
static inline bool
+predicate_NameTreeEntry_hasPitEntry(const name_tree::Entry& entry)
+{
+ return entry.hasPitEntries();
+}
+
+static inline bool
operator==(const Exclude& a, const Exclude& b)
{
const Block& aBlock = a.wireEncode();
@@ -57,10 +50,10 @@
{
// - first lookup() the Interest Name in the NameTree, which will creates all
// the intermedia nodes, starting from the shortest prefix.
- // - if it is guaranteed that this Interest already has a NameTree Entry, we
+ // - if it is guaranteed that this Interest already has a NameTree Entry, we
// could use findExactMatch() instead.
- // - Alternatively, we could try to do findExactMatch() first, if not found, then
- // do lookup().
+ // - Alternatively, we could try to do findExactMatch() first, if not found,
+ // then do lookup().
shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(interest.getName());
BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
@@ -91,19 +84,11 @@
{
shared_ptr<pit::DataMatchResult> result = make_shared<pit::DataMatchResult>();
- shared_ptr<name_tree::Entry> nameTreeEntry;
-
- // NOTE: We are using findLongestPrefixMatch() here.
- // The reason is that findLongestPrefixMatch() starts with the full name
- // and then remove one component each time, which is the type of behavior we would like
- // to use here.
- // If it could be guranteed that the quering Data packet always has a Name Tree
- // Entry, we could also use findExactMatch().
- for (nameTreeEntry = m_nameTree.findLongestPrefixMatch(data.getName());
- static_cast<bool>(nameTreeEntry);
- nameTreeEntry = nameTreeEntry->getParent())
+ for (NameTree::const_iterator it =
+ m_nameTree.findAllMatches(data.getName(), &predicate_NameTreeEntry_hasPitEntry);
+ it != m_nameTree.end(); it++)
{
- std::vector<shared_ptr<pit::Entry> >& pitEntries = nameTreeEntry->getPitEntries();
+ std::vector<shared_ptr<pit::Entry> >& pitEntries = it->getPitEntries();
for (size_t i = 0; i < pitEntries.size(); i++)
{
if (pitEntries[i]->getInterest().matchesName(data.getName()))
@@ -125,7 +110,7 @@
BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
// erase this PIT entry
- if (static_cast<bool>(nameTreeEntry))
+ if (static_cast<bool>(nameTreeEntry))
{
nameTreeEntry->erasePitEntry(pitEntry);
m_nameTree.eraseEntryIfEmpty(nameTreeEntry);
diff --git a/daemon/table/pit.hpp b/daemon/table/pit.hpp
index 9ea5aac..e0b5ba2 100644
--- a/daemon/table/pit.hpp
+++ b/daemon/table/pit.hpp
@@ -31,31 +31,31 @@
public:
explicit
Pit(NameTree& nameTree);
-
+
~Pit();
- /**
+ /**
* \brief Get the number of items stored in the PIT.
*/
- size_t
+ size_t
size() const;
-
+
/** \brief inserts a FIB entry for prefix
* If an entry for exact same prefix exists, that entry is returned.
* \return{ the entry, and true for new entry, false for existing entry }
*/
std::pair<shared_ptr<pit::Entry>, bool>
insert(const Interest& interest);
-
+
/** \brief performs a Data match
* \return{ an iterable of all PIT entries matching data }
*/
shared_ptr<pit::DataMatchResult>
findAllDataMatches(const Data& data) const;
-
+
/**
* \brief Erase a PIT Entry
- */
+ */
void
erase(shared_ptr<pit::Entry> pitEntry);