table: NameTree::findLongestPrefixMatch predicate
refs #1313
Change-Id: I759c8ddf9bc0fe5b970c979f69131a98b1ef32e4
diff --git a/daemon/fw/forwarder.cpp b/daemon/fw/forwarder.cpp
index 417a4cb..a812198 100644
--- a/daemon/fw/forwarder.cpp
+++ b/daemon/fw/forwarder.cpp
@@ -90,9 +90,7 @@
}
// PIT insert
- std::pair<shared_ptr<pit::Entry>, bool>
- pitInsertResult = m_pit.insert(interest);
- shared_ptr<pit::Entry> pitEntry = pitInsertResult.first;
+ shared_ptr<pit::Entry> pitEntry = m_pit.insert(interest).first;
// detect loop and record Nonce
bool isLoop = ! pitEntry->addNonce(interest.getNonce());
@@ -131,9 +129,7 @@
}
// FIB lookup
- shared_ptr<fib::Entry> fibEntry
- = m_fib.findLongestPrefixMatch(interest.getName());
- // TODO use Fib::findParent(pitEntry)
+ shared_ptr<fib::Entry> fibEntry = m_fib.findLongestPrefixMatch(*pitEntry);
// dispatch to strategy
this->dispatchToStrategy(inFace, interest, fibEntry, pitEntry);
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 9c7a611..32aabbf 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -9,17 +9,25 @@
#include "measurements-entry.hpp"
namespace nfd {
+
+const shared_ptr<fib::Entry> Fib::m_emptyEntry = make_shared<fib::Entry>(Name());
+
Fib::Fib(NameTree& nameTree)
: m_nameTree(nameTree)
, m_nItems(0)
{
- m_rootEntry = (this->insert(Name())).first;
}
Fib::~Fib()
{
}
+static inline bool
+predicate_NameTreeEntry_hasFibEntry(const name_tree::Entry& entry)
+{
+ return static_cast<bool>(entry.getFibEntry());
+}
+
std::pair<shared_ptr<fib::Entry>, bool>
Fib::insert(const Name& prefix)
{
@@ -36,15 +44,12 @@
shared_ptr<fib::Entry>
Fib::findLongestPrefixMatch(const Name& prefix) const
{
- shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findLongestPrefixMatch(prefix);
- while (static_cast<bool>(nameTreeEntry))
- {
- if (static_cast<bool>(nameTreeEntry->getFibEntry()))
- return nameTreeEntry->getFibEntry();
- else
- nameTreeEntry = nameTreeEntry->getParent();
+ shared_ptr<name_tree::Entry> nameTreeEntry =
+ m_nameTree.findLongestPrefixMatch(prefix, &predicate_NameTreeEntry_hasFibEntry);
+ if (static_cast<bool>(nameTreeEntry)) {
+ return nameTreeEntry->getFibEntry();
}
- return m_rootEntry;
+ return m_emptyEntry;
}
shared_ptr<fib::Entry>
@@ -82,13 +87,11 @@
void
Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
{
- shared_ptr<fib::Entry> entry;
- shared_ptr<std::vector<shared_ptr<name_tree::Entry > > > res = m_nameTree.fullEnumerate();
- for (int i = 0; i < res->size(); i++)
- {
- entry = (*res)[i]->getFibEntry();
- if (static_cast<bool>(entry))
- entry->removeNextHop(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();
+ entry->removeNextHop(face);
}
}
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 166eb1b..0399833 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -66,9 +66,16 @@
size() const;
private:
- shared_ptr<fib::Entry> m_rootEntry;
NameTree& m_nameTree;
- size_t m_nItems; // Number of items being stored
+ size_t m_nItems;
+
+ /** \brief The empty FIB entry.
+ *
+ * This entry has no nexthops.
+ * It is returned by findLongestPrefixMatch if nothing is matched.
+ */
+ // Returning empty entry instead of nullptr makes forwarding and strategy implementation easier.
+ static const shared_ptr<fib::Entry> m_emptyEntry;
};
inline size_t
diff --git a/daemon/table/measurements.cpp b/daemon/table/measurements.cpp
index e361aba..a5b107e 100644
--- a/daemon/table/measurements.cpp
+++ b/daemon/table/measurements.cpp
@@ -23,6 +23,12 @@
{
}
+static inline bool
+predicate_NameTreeEntry_hasMeasurementsEntry(const name_tree::Entry& entry)
+{
+ return static_cast<bool>(entry.getMeasurementsEntry());
+}
+
shared_ptr<measurements::Entry>
Measurements::get(const Name& name)
{
@@ -63,12 +69,10 @@
shared_ptr<measurements::Entry>
Measurements::findLongestPrefixMatch(const Name& name) const
{
- shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findLongestPrefixMatch(name);
- while (static_cast<bool>(nameTreeEntry))
- {
- if (static_cast<bool>(nameTreeEntry->getMeasurementsEntry()))
- return nameTreeEntry->getMeasurementsEntry();
- nameTreeEntry = nameTreeEntry->getParent();
+ shared_ptr<name_tree::Entry> nameTreeEntry =
+ m_nameTree.findLongestPrefixMatch(name, &predicate_NameTreeEntry_hasMeasurementsEntry);
+ if (static_cast<bool>(nameTreeEntry)) {
+ return nameTreeEntry->getMeasurementsEntry();
}
return shared_ptr<measurements::Entry>();
}
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index b6f53db..cef42ff 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -71,6 +71,9 @@
std::vector<shared_ptr<Entry> >&
getChildren();
+
+ bool
+ isEmpty() const;
void
setFibEntry(shared_ptr<fib::Entry> fib);
@@ -140,6 +143,15 @@
return m_children;
}
+inline bool
+Entry::isEmpty() const
+{
+ return m_children.empty() &&
+ !static_cast<bool>(m_fibEntry) &&
+ m_pitEntries.empty() &&
+ !static_cast<bool>(m_measurementsEntry);
+}
+
inline shared_ptr<fib::Entry>
Entry::getFibEntry() const
{
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 20e09e4..964730e 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -186,7 +186,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)
+NameTree::findLongestPrefixMatch(const Name& prefix, const name_tree::EntrySelector& entrySelector)
{
NFD_LOG_DEBUG("findLongestPrefixMatch " << prefix);
@@ -195,11 +195,11 @@
for (int i = prefix.size(); i >= 0; i--)
{
entry = findExactMatch(prefix.getPrefix(i));
- if (static_cast<bool>(entry))
+ if (static_cast<bool>(entry) && entrySelector(*entry))
return entry;
}
- return entry;
+ return shared_ptr<name_tree::Entry>();
}
// return {false: this entry is not empty, true: this entry is empty and erased}
@@ -211,9 +211,7 @@
NFD_LOG_DEBUG("eraseEntryIfEmpty " << entry->getPrefix());
// first check if this Entry can be erased
- if (entry->getChildren().empty() &&
- !(entry->getFibEntry()) &&
- entry->getPitEntries().empty())
+ if (entry->isEmpty())
{
// update child-related info in the parent
shared_ptr<name_tree::Entry> parent = entry->getParent();
@@ -277,68 +275,62 @@
}
shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
-NameTree::fullEnumerate()
+NameTree::fullEnumerate(const name_tree::EntrySelector& entrySelector)
{
NFD_LOG_DEBUG("fullEnumerate");
- shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > ret =
+ shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > results =
make_shared<std::vector<shared_ptr<name_tree::Entry> > >();
- for (int 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))
- {
- ret->push_back(node->m_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 ret;
+ return results;
}
// Helper function for partialEnumerate()
void
NameTree::partialEnumerateAddChildren(shared_ptr<name_tree::Entry> entry,
- shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > ret)
+ const name_tree::EntrySelector& entrySelector,
+ std::vector<shared_ptr<name_tree::Entry> >& results)
{
BOOST_ASSERT(static_cast<bool>(entry));
+
+ if (!entrySelector(*entry)) {
+ return;
+ }
- ret->push_back(entry);
+ results.push_back(entry);
for (size_t i = 0; i < entry->m_children.size(); i++)
{
- shared_ptr<name_tree::Entry> temp = entry->m_children[i];
- partialEnumerateAddChildren(temp, ret);
+ shared_ptr<name_tree::Entry> child = entry->m_children[i];
+ partialEnumerateAddChildren(child, entrySelector, results);
}
}
shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
-NameTree::partialEnumerate(const Name& prefix)
+NameTree::partialEnumerate(const Name& prefix,
+ const name_tree::EntrySelector& entrySelector)
{
NFD_LOG_DEBUG("partialEnumerate" << prefix);
- shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > ret =
+ shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > results =
make_shared<std::vector<shared_ptr<name_tree::Entry> > >();
// find the hash bucket corresponding to that prefix
shared_ptr<name_tree::Entry> entry = findExactMatch(prefix);
- if (!static_cast<bool>(entry))
- {
- return ret;
- }
- else
- {
- // go through its children list via depth-first-search
- ret->push_back(entry);
- for (size_t i = 0; i < entry->m_children.size(); i++)
- {
- partialEnumerateAddChildren(entry->m_children[i], ret);
- }
- }
+ if (static_cast<bool>(entry)) {
+ // go through its children list via depth-first-search
+ partialEnumerateAddChildren(entry, entrySelector, *results);
+ }
- return ret;
+ return results;
}
// Hash Table Resize
@@ -348,14 +340,14 @@
NFD_LOG_DEBUG("resize");
name_tree::Node** newBuckets = new name_tree::Node*[newNBuckets];
- int count = 0;
+ size_t count = 0;
// referenced ccnx hashtb.c hashtb_rehash()
name_tree::Node** pp = 0;
name_tree::Node* p = 0;
name_tree::Node* pre = 0;
name_tree::Node* q = 0; // record p->m_next
- int i;
+ size_t i;
uint32_t h;
uint32_t b;
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 6432583..812c916 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -25,6 +25,17 @@
uint32_t
hashName(const Name& prefix);
+/// a predicate to accept or reject an Entry in find operations
+typedef function<bool (const Entry& entry)> EntrySelector;
+
+struct AnyEntry {
+ bool
+ operator()(const Entry& entry)
+ {
+ return true;
+ }
+};
+
} // namespace name_tree
/**
@@ -90,7 +101,8 @@
* by one each time, until an Entry is found.
*/
shared_ptr<name_tree::Entry>
- findLongestPrefixMatch(const Name& prefix);
+ findLongestPrefixMatch(const Name& prefix,
+ const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry());
/**
* @brief Resize the hash table size when its load factor reaches a threshold.
@@ -106,7 +118,7 @@
* @brief Enumerate all the name prefixes stored in the Name Tree.
*/
shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
- fullEnumerate();
+ fullEnumerate(const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry());
/**
* @brief Enumerate all the name prefixes under a specific name prefix
@@ -114,7 +126,8 @@
* number of entries stored in the vector.
*/
shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
- partialEnumerate(const Name& prefix);
+ partialEnumerate(const Name& prefix,
+ const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry());
/**
* @brief Dump all the information stored in the Name Tree for debugging.
@@ -146,7 +159,8 @@
*/
void
partialEnumerateAddChildren(shared_ptr<name_tree::Entry> entry,
- shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > ret);
+ const name_tree::EntrySelector& entrySelector,
+ std::vector<shared_ptr<name_tree::Entry> >& results);
};
diff --git a/tests/table/fib.cpp b/tests/table/fib.cpp
index 0be6492..4d9d05f 100644
--- a/tests/table/fib.cpp
+++ b/tests/table/fib.cpp
@@ -120,50 +120,58 @@
NameTree nameTree(1024);
Fib fib(nameTree);
+ // []
+
+ entry = fib.findLongestPrefixMatch(nameA);
+ BOOST_REQUIRE(static_cast<bool>(entry)); // the empty entry
+
+ insertRes = fib.insert(nameEmpty);
+ BOOST_CHECK_EQUAL(insertRes.second, true);
+ BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameEmpty);
// ['/']
entry = fib.findLongestPrefixMatch(nameA);
- BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
- BOOST_CHECK(entry->getPrefix().equals(nameEmpty));
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
insertRes = fib.insert(nameA);
BOOST_CHECK_EQUAL(insertRes.second, true);
- BOOST_CHECK(insertRes.first->getPrefix().equals(nameA));
+ BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
// ['/', '/A']
insertRes = fib.insert(nameA);
BOOST_CHECK_EQUAL(insertRes.second, false);
- BOOST_CHECK(insertRes.first->getPrefix().equals(nameA));
+ BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
// ['/', '/A']
entry = fib.findLongestPrefixMatch(nameA);
- BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
- BOOST_CHECK(entry->getPrefix().equals(nameA));
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
entry = fib.findLongestPrefixMatch(nameABCD);
- BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
- BOOST_CHECK(entry->getPrefix().equals(nameA));
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
insertRes = fib.insert(nameABC);
BOOST_CHECK_EQUAL(insertRes.second, true);
- BOOST_CHECK(insertRes.first->getPrefix().equals(nameABC));
+ BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameABC);
// ['/', '/A', '/A/B/C']
entry = fib.findLongestPrefixMatch(nameA);
- BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
- BOOST_CHECK(entry->getPrefix().equals(nameA));
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
entry = fib.findLongestPrefixMatch(nameAB);
- BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
- BOOST_CHECK(entry->getPrefix().equals(nameA));
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
entry = fib.findLongestPrefixMatch(nameABCD);
- BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
- BOOST_CHECK(entry->getPrefix().equals(nameABC));
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameABC);
entry = fib.findLongestPrefixMatch(nameE);
- BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
- BOOST_CHECK(entry->getPrefix().equals(nameEmpty));
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
}
BOOST_AUTO_TEST_CASE(RemoveNextHopFromAllEntries)
@@ -193,13 +201,13 @@
// {'/':[], '/A':[2], '/B':[]}
entry = fib.findLongestPrefixMatch(nameA);
- BOOST_CHECK(entry->getPrefix().equals(nameA));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
const fib::NextHopList& nexthopsA = entry->getNextHops();
BOOST_CHECK_EQUAL(nexthopsA.size(), 1);
BOOST_CHECK_EQUAL(nexthopsA.begin()->getFace(), face2);
entry = fib.findLongestPrefixMatch(nameB);
- BOOST_CHECK(entry->getPrefix().equals(nameB));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameB);
const fib::NextHopList& nexthopsB = entry->getNextHops();
BOOST_CHECK_EQUAL(nexthopsB.size(), 0);
}
@@ -239,7 +247,7 @@
validateFindExactMatch(fib, "/A");
validateFindExactMatch(fib, "/A/B");
validateFindExactMatch(fib, "/A/B/C");
- validateFindExactMatch(fib, "/");
+ validateNoExactMatch(fib, "/");
validateNoExactMatch(fib, "/does/not/exist");
@@ -280,6 +288,7 @@
NameTree nameTree(1024);
Fib fib(nameTree);
+ fib.insert("/");
fib.insert("/A");
fib.insert("/A/B");
fib.insert("/A/B/C");
@@ -299,6 +308,9 @@
validateRemove(fib, "/A");
validateFindExactMatch(fib, "/");
+ validateRemove(fib, "/");
+ validateNoExactMatch(fib, "/");
+
NameTree gapNameTree(1024);
Fib gapFib(gapNameTree);
gapFib.insert("/X");