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");