table: PIT on NameTree
ref# 1194
Change-Id: I32f103374885445725fc5deeebda60b1b1e54c2f
diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index a605ef0..cc40f24 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -16,6 +16,8 @@
Forwarder::Forwarder()
: m_lastFaceId(0)
+ , m_nameTree(1024) // "1024" could be made as one configurable parameter of the forwarder.
+ , m_pit(m_nameTree)
{
m_strategy = make_shared<fw::BestRouteStrategy>(boost::ref(*this));
}
@@ -189,8 +191,8 @@
// invoke PIT unsatisfied callback
// TODO
- // PIT delete
- m_pit.remove(pitEntry);
+ // PIT erase
+ m_pit.erase(pitEntry);
}
void
@@ -322,7 +324,7 @@
time::Duration stragglerTime = time::milliseconds(100);
pitEntry->m_stragglerTimer = scheduler::schedule(stragglerTime,
- bind(&Pit::remove, &m_pit, pitEntry));
+ bind(&Pit::erase, &m_pit, pitEntry));
}
void
diff --git a/daemon/fw/forwarder.hpp b/daemon/fw/forwarder.hpp
index 6622999..3df2d41 100644
--- a/daemon/fw/forwarder.hpp
+++ b/daemon/fw/forwarder.hpp
@@ -117,7 +117,8 @@
private:
FaceId m_lastFaceId;
std::map<FaceId, shared_ptr<Face> > m_faces;
-
+
+ NameTree m_nameTree;
Fib m_fib;
Pit m_pit;
Cs m_cs;
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index 168a64e..6f5acf3 100644
--- a/daemon/table/pit.cpp
+++ b/daemon/table/pit.cpp
@@ -4,12 +4,24 @@
* 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"
-#include <algorithm>
namespace nfd {
-Pit::Pit()
+Pit::Pit(NameTree& nameTree) : m_nameTree(nameTree), m_nItems(0)
{
}
@@ -43,34 +55,83 @@
std::pair<shared_ptr<pit::Entry>, bool>
Pit::insert(const Interest& interest)
{
- std::list<shared_ptr<pit::Entry> >::iterator it = std::find_if(
- m_table.begin(), m_table.end(),
- bind(&predicate_PitEntry_similar_Interest, _1, interest));
- if (it != m_table.end()) return std::make_pair(*it, false);
-
- shared_ptr<pit::Entry> entry = make_shared<pit::Entry>(interest);
- m_table.push_back(entry);
- return std::make_pair(entry, true);
+ // - 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
+ // could use findExactMatch() instead.
+ // - 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));
+
+ std::vector<shared_ptr<pit::Entry> >& pitEntries = nameTreeEntry->getPitEntries();
+
+ // then check if this Interest is already in the PIT entries
+ std::vector<shared_ptr<pit::Entry> >::iterator it = std::find_if(pitEntries.begin(), pitEntries.end(), bind(&predicate_PitEntry_similar_Interest, _1, interest));
+
+ if (it != pitEntries.end())
+ {
+ return std::make_pair(*it, false);
+ }
+ else
+ {
+ shared_ptr<pit::Entry> entry = make_shared<pit::Entry>(interest);
+ nameTreeEntry->insertPitEntry(entry);
+
+ // Increase m_nItmes only if we create a new PIT Entry
+ m_nItems++;
+
+ return std::make_pair(entry, true);
+ }
}
shared_ptr<pit::DataMatchResult>
Pit::findAllDataMatches(const Data& data) const
{
shared_ptr<pit::DataMatchResult> result = make_shared<pit::DataMatchResult>();
- for (std::list<shared_ptr<pit::Entry> >::const_iterator it = m_table.begin();
- it != m_table.end(); ++it) {
- shared_ptr<pit::Entry> entry = *it;
- if (entry->getInterest().matchesName(data.getName())) {
- result->push_back(entry);
+
+ 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())
+ {
+ std::vector<shared_ptr<pit::Entry> >& pitEntries = nameTreeEntry->getPitEntries();
+ for (size_t i = 0; i < pitEntries.size(); i++)
+ {
+ if (pitEntries[i]->getInterest().matchesName(data.getName()))
+ result->push_back(pitEntries[i]);
+ }
}
- }
+
return result;
}
void
-Pit::remove(shared_ptr<pit::Entry> pitEntry)
+Pit::erase(shared_ptr<pit::Entry> pitEntry)
{
- m_table.remove(pitEntry);
+ // first get the NPE
+ // If pit-entry.hpp stores a NameTree Entry for each PIT, we could also use the get() method
+ // directly, saving one hash computation.
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(pitEntry->getName());
+
+ BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
+
+ // erase this PIT entry
+ if (static_cast<bool>(nameTreeEntry))
+ {
+ nameTreeEntry->erasePitEntry(pitEntry);
+ m_nameTree.eraseEntryIfEmpty(nameTreeEntry);
+
+ m_nItems--;
+ }
}
} // namespace nfd
diff --git a/daemon/table/pit.hpp b/daemon/table/pit.hpp
index 9dd2e1e..9ea5aac 100644
--- a/daemon/table/pit.hpp
+++ b/daemon/table/pit.hpp
@@ -7,7 +7,9 @@
#ifndef NFD_TABLE_PIT_HPP
#define NFD_TABLE_PIT_HPP
+#include "name-tree.hpp"
#include "pit-entry.hpp"
+
namespace nfd {
namespace pit {
@@ -27,9 +29,16 @@
class Pit : noncopyable
{
public:
- Pit();
-
+ explicit
+ Pit(NameTree& nameTree);
+
~Pit();
+
+ /**
+ * \brief Get the number of items stored in the PIT.
+ */
+ size_t
+ size() const;
/** \brief inserts a FIB entry for prefix
* If an entry for exact same prefix exists, that entry is returned.
@@ -43,15 +52,24 @@
*/
shared_ptr<pit::DataMatchResult>
findAllDataMatches(const Data& data) const;
-
- /// removes a PIT entry
+
+ /**
+ * \brief Erase a PIT Entry
+ */
void
- remove(shared_ptr<pit::Entry> pitEntry);
+ erase(shared_ptr<pit::Entry> pitEntry);
private:
- std::list<shared_ptr<pit::Entry> > m_table;
+ NameTree& m_nameTree;
+ size_t m_nItems;
};
+inline size_t
+Pit::size() const
+{
+ return m_nItems;
+}
+
} // namespace nfd
#endif // NFD_TABLE_PIT_HPP