table: Name Tree Implementation

Change-Id: I27dbe50a1f484a7722b443dea6197a0f8d74aa0a
diff --git a/daemon/common.hpp b/daemon/common.hpp
index b5203c3..2e0ff22 100644
--- a/daemon/common.hpp
+++ b/daemon/common.hpp
@@ -32,6 +32,7 @@
 #include <boost/ref.hpp>
 #include <boost/asio.hpp>
 #include <boost/assert.hpp>
+#include <boost/functional/hash.hpp>
 
 #include <vector>
 #include <list>
diff --git a/daemon/table/name-tree-entry.cpp b/daemon/table/name-tree-entry.cpp
new file mode 100644
index 0000000..40e19c8
--- /dev/null
+++ b/daemon/table/name-tree-entry.cpp
@@ -0,0 +1,103 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+// Name Tree Entry (i.e., Name Prefix Entry)
+
+#include "name-tree-entry.hpp"
+
+namespace nfd {
+namespace name_tree {
+
+Node::Node() : m_prev(0), m_next(0)
+{
+}
+
+Node::~Node()
+{
+  // erase the Name Tree Nodes that were created to
+  // resolve hash collisions
+  // So before erasing a single node, make sure its m_next == 0
+  // See eraseEntryIfEmpty in name-tree.cpp
+  if (m_next)
+    delete m_next;
+}
+
+Entry::Entry(const Name& name) : m_hash(0), m_prefix(name)
+{
+}
+
+Entry::~Entry()
+{
+}
+
+void
+Entry::setHash(uint32_t hash)
+{
+  m_hash = hash;
+}
+
+void
+Entry::setParent(shared_ptr<Entry> parent)
+{
+  m_parent = parent;
+}
+
+void
+Entry::setFibEntry(shared_ptr<fib::Entry> fib)
+{
+  m_fibEntry = fib;
+}
+
+bool
+Entry::eraseFibEntry(shared_ptr<fib::Entry> fib)
+{
+  if (m_fibEntry != fib)
+    return false;
+  m_fibEntry.reset();
+  return true;
+}
+
+void
+Entry::insertPitEntry(shared_ptr<pit::Entry> pit)
+{
+  m_pitEntries.push_back(pit);
+}
+
+bool
+Entry::erasePitEntry(shared_ptr<pit::Entry> pit)
+{
+  for (size_t i = 0; i < m_pitEntries.size(); i++)
+    {
+      if (m_pitEntries[i] == pit)
+        {
+          // copy the last item to the current position
+          m_pitEntries[i] = m_pitEntries[m_pitEntries.size() - 1];
+          // then erase the last item
+          m_pitEntries.pop_back();
+          return true; // success
+        }
+    }
+  // not found this entry
+  return false; // failure
+}
+
+void
+Entry::setMeasurementsEntry(shared_ptr<measurements::Entry> measurements)
+{
+  m_measurementsEntry = measurements;
+}
+
+bool
+Entry::eraseMeasurementsEntry(shared_ptr<measurements::Entry> measurements)
+{
+  if (m_measurementsEntry != measurements)
+    return false;
+  m_measurementsEntry.reset();
+  return true;
+}
+
+} // namespace name_tree
+} // namespace nfd
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
new file mode 100644
index 0000000..b6f53db
--- /dev/null
+++ b/daemon/table/name-tree-entry.hpp
@@ -0,0 +1,164 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+// Name Tree Entry (i.e., Name Prefix Entry)
+
+#ifndef NFD_TABLE_NAME_TREE_ENTRY_HPP
+#define NFD_TABLE_NAME_TREE_ENTRY_HPP
+
+#include "common.hpp"
+#include "table/fib-entry.hpp"
+#include "table/pit-entry.hpp"
+#include "table/measurements-entry.hpp"
+
+namespace nfd {
+
+class NameTree;
+
+namespace name_tree {
+
+// Forward declaration
+class Node;
+class Entry;
+
+/**
+ * @brief Name Tree Node Class
+ */
+class Node
+{
+public:
+  Node();
+
+  ~Node();
+
+public:
+  // variables are in public as this is just a data structure
+  shared_ptr<Entry> m_entry; // Name Tree Entry (i.e., Name Prefix Entry)
+  Node* m_prev; // Previous Name Tree Node (to resolve hash collision)
+  Node* m_next; // Next Name Tree Node (to resolve hash collision)
+};
+
+/**
+ * @brief Name Tree Entry Class
+ */
+class Entry
+{
+  // Make private members accessible by Name Tree
+  friend class nfd::NameTree;
+public:
+  explicit
+  Entry(const Name& prefix);
+
+  ~Entry();
+
+  const Name&
+  getPrefix() const;
+
+  void
+  setHash(uint32_t hash);
+
+  uint32_t
+  getHash() const;
+
+  void
+  setParent(shared_ptr<Entry> parent);
+
+  shared_ptr<Entry>
+  getParent() const;
+
+  std::vector<shared_ptr<Entry> >&
+  getChildren();
+
+  void
+  setFibEntry(shared_ptr<fib::Entry> fib);
+
+  shared_ptr<fib::Entry>
+  getFibEntry() const;
+
+  bool
+  eraseFibEntry(shared_ptr<fib::Entry> fib);
+
+  void
+  insertPitEntry(shared_ptr<pit::Entry> pit);
+
+  std::vector<shared_ptr<pit::Entry> >&
+  getPitEntries();
+
+  /**
+   * @brief Erase a PIT Entry
+   * @details The address of this PIT Entry is required
+   */
+  bool
+  erasePitEntry(shared_ptr<pit::Entry> pit);
+
+  void
+  setMeasurementsEntry(shared_ptr<measurements::Entry> measurements);
+
+  shared_ptr<measurements::Entry>
+  getMeasurementsEntry() const;
+
+  bool
+  eraseMeasurementsEntry(shared_ptr<measurements::Entry> measurements);
+
+private:
+  uint32_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.
+  shared_ptr<fib::Entry> m_fibEntry;
+  std::vector<shared_ptr<pit::Entry> > m_pitEntries;
+  shared_ptr<measurements::Entry> m_measurementsEntry;
+
+  // get the Name Tree Node that is associated with this Name Tree Entry
+  Node* m_node;
+};
+
+inline const Name&
+Entry::getPrefix() const
+{
+  return m_prefix;
+}
+
+inline uint32_t
+Entry::getHash() const
+{
+  return m_hash;
+}
+
+inline shared_ptr<Entry>
+Entry::getParent() const
+{
+  return m_parent;
+}
+
+inline std::vector<shared_ptr<name_tree::Entry> >&
+Entry::getChildren()
+{
+  return m_children;
+}
+
+inline shared_ptr<fib::Entry>
+Entry::getFibEntry() const
+{
+  return m_fibEntry;
+}
+
+inline std::vector<shared_ptr<pit::Entry> >&
+Entry::getPitEntries()
+{
+  return m_pitEntries;
+}
+
+inline shared_ptr<measurements::Entry>
+Entry::getMeasurementsEntry() const
+{
+  return m_measurementsEntry;
+}
+
+} // namespace name_tree
+} // namespace nfd
+
+#endif // NFD_TABLE_NAME_TREE_ENTRY_HPP
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
new file mode 100644
index 0000000..20e09e4
--- /dev/null
+++ b/daemon/table/name-tree.cpp
@@ -0,0 +1,451 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+// Name Tree (Name Prefix Hash Table)
+
+#include "name-tree.hpp"
+#include "core/logger.hpp"
+
+namespace nfd {
+
+NFD_LOG_INIT("NameTree");
+
+namespace name_tree {
+
+// Interface of different hash functions
+uint32_t
+hashName(const Name& prefix)
+{
+  // fixed value. Used for debugging only.
+  uint32_t ret = 0;
+
+  // Boost hash
+  // requires the /boost/functional/hash.hpp header file
+  // TODO: improve hash efficiency with Name type
+  boost::hash<std::string> stringHash;
+  ret = stringHash(prefix.toUri());
+
+  return ret;
+}
+
+} // namespace name_tree
+
+NameTree::NameTree(size_t nBuckets)
+  : m_nItems(0)
+  , m_nBuckets(nBuckets)
+  , m_loadFactor(0.5)
+  , m_resizeFactor(2)
+{
+  m_resizeThreshold = static_cast<size_t>(m_loadFactor *
+                                          static_cast<double>(m_nBuckets));
+
+  // array of node pointers
+  m_buckets = new name_tree::Node*[m_nBuckets];
+  // Initialize the pointer array
+  for (size_t i = 0; i < m_nBuckets; i++)
+    m_buckets[i] = 0;
+}
+
+NameTree::~NameTree()
+{
+  for (size_t i = 0; i < m_nBuckets; i++)
+    {
+      if (m_buckets[i] != 0)
+        delete m_buckets[i];
+    }
+
+  delete [] m_buckets;
+}
+
+// insert() is a private function, and called by only lookup()
+std::pair<shared_ptr<name_tree::Entry>, bool>
+NameTree::insert(const Name& prefix)
+{
+  NFD_LOG_DEBUG("insert " << prefix);
+
+  uint32_t hashValue = name_tree::hashName(prefix);
+  uint32_t loc = hashValue % m_nBuckets;
+
+  NFD_LOG_DEBUG("Name " << prefix << " hash value = " << hashValue << "  location = " << loc);
+
+  // Check if this Name has been stored
+  name_tree::Node* node = m_buckets[loc];
+  name_tree::Node* nodePrev = node;  // initialize nodePrev to node
+
+  for (node = m_buckets[loc]; node != 0; node = node->m_next)
+    {
+      if (static_cast<bool>(node->m_entry))
+        {
+          if (prefix == node->m_entry->m_prefix)
+            {
+              return std::make_pair(node->m_entry, false); // false: old entry
+            }
+        }
+      nodePrev = node;
+    }
+
+  NFD_LOG_DEBUG("Did not find " << prefix << ", need to insert it to the table");
+
+  // If no bucket is empty occupied, we need to create a new node, and it is
+  // linked from nodePrev
+  node = new name_tree::Node();
+  node->m_prev = nodePrev;
+
+  if (nodePrev == 0)
+    {
+      m_buckets[loc] = node;
+    }
+  else
+    {
+      nodePrev->m_next = node;
+    }
+
+  // Create a new Entry
+  shared_ptr<name_tree::Entry> entry(make_shared<name_tree::Entry>(prefix));
+  entry->setHash(hashValue);
+  node->m_entry = entry; // link the Entry to its Node
+  entry->m_node = node; // link the node to Entry. Used in eraseEntryIfEmpty.
+
+  return std::make_pair(entry, true); // true: new entry
+}
+
+// Name Prefix Lookup. Create Name Tree Entry if not found
+shared_ptr<name_tree::Entry>
+NameTree::lookup(const Name& prefix)
+{
+  NFD_LOG_DEBUG("lookup " << prefix);
+
+  shared_ptr<name_tree::Entry> entry;
+  shared_ptr<name_tree::Entry> parent;
+
+  for (size_t i = 0; i <= prefix.size(); i++)
+    {
+      Name temp = prefix.getPrefix(i);
+
+      // insert() will create the entry if it does not exist.
+      std::pair<shared_ptr<name_tree::Entry>, bool> ret = insert(temp);
+      entry = ret.first;
+
+      if (ret.second == true)
+        {
+          m_nItems++; /* Increase the counter */
+          entry->m_parent = parent;
+
+          if (static_cast<bool>(parent))
+            {
+              parent->m_children.push_back(entry);
+            }
+        }
+
+      if (m_nItems > m_resizeThreshold)
+        {
+          resize(m_resizeFactor * m_nBuckets);
+        }
+
+      parent = entry;
+    }
+  return entry;
+}
+
+// Exact Match
+shared_ptr<name_tree::Entry>
+NameTree::findExactMatch(const Name& prefix) const
+{
+  NFD_LOG_DEBUG("findExactMatch " << prefix);
+
+  uint32_t hashValue = name_tree::hashName(prefix);
+  uint32_t loc = hashValue % m_nBuckets;
+
+  NFD_LOG_DEBUG("Name " << prefix << " hash value = " << hashValue <<
+                "  location = " << loc);
+
+  shared_ptr<name_tree::Entry> entry;
+  name_tree::Node* node = 0;
+
+  for (node = m_buckets[loc]; node != 0; node = node->m_next)
+    {
+      entry = node->m_entry;
+      if (static_cast<bool>(entry))
+        {
+          if (hashValue == entry->getHash() && prefix == entry->getPrefix())
+            {
+              return entry;
+            }
+        } // if entry
+    } // for node
+
+  // if not found, the default value of entry (null pointer) will be returned
+  entry.reset();
+  return entry;
+}
+
+// Longest Prefix Match
+// 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)
+{
+  NFD_LOG_DEBUG("findLongestPrefixMatch " << prefix);
+
+  shared_ptr<name_tree::Entry> entry;
+
+  for (int i = prefix.size(); i >= 0; i--)
+    {
+      entry = findExactMatch(prefix.getPrefix(i));
+      if (static_cast<bool>(entry))
+        return entry;
+    }
+
+  return entry;
+}
+
+// return {false: this entry is not empty, true: this entry is empty and erased}
+bool
+NameTree::eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry)
+{
+  BOOST_ASSERT(static_cast<bool>(entry));
+
+  NFD_LOG_DEBUG("eraseEntryIfEmpty " << entry->getPrefix());
+
+  // first check if this Entry can be erased
+  if (entry->getChildren().empty() &&
+      !(entry->getFibEntry()) &&
+      entry->getPitEntries().empty())
+    {
+      // update child-related info in the parent
+      shared_ptr<name_tree::Entry> parent = entry->getParent();
+
+      if (static_cast<bool>(parent))
+        {
+          std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList =
+            parent->getChildren();
+
+          bool isFound = false;
+          size_t size = parentChildrenList.size();
+          for (size_t i = 0; i < size; i++)
+            {
+              if (parentChildrenList[i] == entry)
+                {
+                  parentChildrenList[i] = parentChildrenList[size - 1];
+                  parentChildrenList.pop_back();
+                  isFound = true;
+                  break;
+                }
+            }
+
+          BOOST_ASSERT(isFound == true);
+        }
+
+      // remove this Entry and its Name Tree Node
+      name_tree::Node* node = entry->m_node;
+      name_tree::Node* nodePrev = node->m_prev;
+
+      // configure the previous node
+      if (nodePrev != 0)
+        {
+          // link the previous node to the next node
+          nodePrev->m_next = node->m_next;
+        }
+      else
+        {
+          m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
+        }
+
+      // link the previous node with the next node (skip the erased one)
+      if (node->m_next != 0)
+        {
+          node->m_next->m_prev = nodePrev;
+          node->m_next = 0;
+        }
+
+      BOOST_ASSERT(node->m_next == 0);
+
+      m_nItems--;
+      delete node;
+
+      if (static_cast<bool>(parent))
+        eraseEntryIfEmpty(parent);
+
+      return true;
+
+    } // if this entry is empty
+
+  return false; // if this entry is not empty
+}
+
+shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
+NameTree::fullEnumerate()
+{
+  NFD_LOG_DEBUG("fullEnumerate");
+
+  shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > ret =
+    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);
+            }
+        }
+    }
+
+  return ret;
+}
+
+// Helper function for partialEnumerate()
+void
+NameTree::partialEnumerateAddChildren(shared_ptr<name_tree::Entry> entry,
+                                      shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > ret)
+{
+  BOOST_ASSERT(static_cast<bool>(entry));
+
+  ret->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<std::vector<shared_ptr<name_tree::Entry> > >
+NameTree::partialEnumerate(const Name& prefix)
+{
+  NFD_LOG_DEBUG("partialEnumerate" << prefix);
+
+  shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > ret =
+    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);
+        }
+    }
+
+  return ret;
+}
+
+// Hash Table Resize
+void
+NameTree::resize(size_t newNBuckets)
+{
+  NFD_LOG_DEBUG("resize");
+
+  name_tree::Node** newBuckets = new name_tree::Node*[newNBuckets];
+  int 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;
+  uint32_t h;
+  uint32_t b;
+
+  for (i = 0; i < newNBuckets; i++)
+    {
+      newBuckets[i] = 0;
+    }
+
+  for (i = 0; i < m_nBuckets; i++)
+    {
+      for (p = m_buckets[i]; p != 0; p = q)
+        {
+          count++;
+          q = p->m_next;
+          BOOST_ASSERT(static_cast<bool>(p->m_entry));
+          h = p->m_entry->m_hash;
+          b = h % newNBuckets;
+          for (pp = &newBuckets[b]; *pp != 0; pp = &((*pp)->m_next))
+            {
+              pre = *pp;
+              continue;
+            }
+          p->m_prev = pre;
+          p->m_next = *pp; // Actually *pp always == 0 in this case
+          *pp = p;
+        }
+    }
+
+  BOOST_ASSERT(count == m_nItems);
+
+  name_tree::Node** oldBuckets = m_buckets;
+  m_buckets = newBuckets;
+  delete oldBuckets;
+
+  m_nBuckets = newNBuckets;
+  m_resizeThreshold = (int)(m_loadFactor * (double)m_nBuckets);
+}
+
+// For debugging
+void
+NameTree::dump(std::ostream& output)
+{
+  NFD_LOG_DEBUG("dump()");
+
+  name_tree::Node* node = 0;
+  shared_ptr<name_tree::Entry> entry;
+
+  using std::endl;
+
+  for (size_t i = 0; i < m_nBuckets; i++)
+    {
+      for (node = m_buckets[i]; node != 0; node = node->m_next)
+        {
+          entry = node->m_entry;
+
+          // if the Entry exist, dump its information
+          if (static_cast<bool>(entry))
+            {
+              output << "Bucket" << i << "\t" << entry->m_prefix.toUri() << endl;
+              output << "\t\tHash " << entry->m_hash << endl;
+
+              if (static_cast<bool>(entry->m_parent))
+                {
+                  output << "\t\tparent->" << entry->m_parent->m_prefix.toUri();
+                }
+              else
+                {
+                  output << "\t\tROOT";
+                }
+              output << endl;
+
+              if (entry->m_children.size() != 0)
+                {
+                  output << "\t\tchildren = " << entry->m_children.size() << endl;
+
+                  for (size_t j = 0; j < entry->m_children.size(); j++)
+                    {
+                      output << "\t\t\tChild " << j << " " <<
+                        entry->m_children[j]->getPrefix() << endl;
+                    }
+                }
+
+            } // if (static_cast<bool>(entry))
+
+        } // for node
+    } // for int i
+
+  output << "Bucket count = " << m_nBuckets << endl;
+  output << "Stored item = " << m_nItems << endl;
+  output << "--------------------------\n";
+}
+
+} // namespace nfd
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
new file mode 100644
index 0000000..6432583
--- /dev/null
+++ b/daemon/table/name-tree.hpp
@@ -0,0 +1,167 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+// Name Tree (Name Prefix Hash Table)
+
+#ifndef NFD_TABLE_NAME_TREE_HPP
+#define NFD_TABLE_NAME_TREE_HPP
+
+#include "common.hpp"
+#include "name-tree-entry.hpp"
+
+namespace nfd {
+namespace name_tree {
+
+/**
+ * @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.
+ */
+uint32_t
+hashName(const Name& prefix);
+
+} // namespace name_tree
+
+/**
+ * @brief Class Name Tree
+ */
+class NameTree : noncopyable
+{
+public:
+  explicit
+  NameTree(size_t nBuckets);
+
+  ~NameTree();
+
+  /**
+   * @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
+   * 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
+   * 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
+   * 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;
+   * 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
+   * 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
+   * 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
+   * by one each time, until an Entry is found.
+   */
+  shared_ptr<name_tree::Entry>
+  findLongestPrefixMatch(const Name& prefix);
+
+  /**
+   * @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.
+   */
+  void
+  resize(size_t newNBuckets);
+
+  /**
+   * @brief Enumerate all the name prefixes stored in the Name Tree.
+   */
+  shared_ptr<std::vector<shared_ptr<name_tree::Entry> > >
+  fullEnumerate();
+
+  /**
+   * @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> > >
+  partialEnumerate(const Name& prefix);
+
+  /**
+   * @brief Dump all the information stored in the Name Tree for debugging.
+   */
+  void
+  dump(std::ostream& output);
+
+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
+
+  /**
+   * @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
+   * 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,
+                              shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > ret);
+
+};
+
+inline size_t
+NameTree::size() const
+{
+  return m_nItems;
+}
+
+inline size_t
+NameTree::getNBuckets() const
+{
+  return m_nBuckets;
+}
+
+} // namespace nfd
+
+#endif // NFD_TABLE_NAME_TREE_HPP
diff --git a/tests/table/name-tree.cpp b/tests/table/name-tree.cpp
new file mode 100644
index 0000000..bc34c15
--- /dev/null
+++ b/tests/table/name-tree.cpp
@@ -0,0 +1,271 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (C) 2014 Named Data Networking Project
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "table/name-tree.hpp"
+#include <boost/test/unit_test.hpp>
+
+namespace nfd {
+
+using name_tree::Entry;
+
+BOOST_AUTO_TEST_SUITE(TableNameTree)
+
+BOOST_AUTO_TEST_CASE (Entry)
+{
+  Name prefix("ndn:/named-data/research/abc/def/ghi");
+
+  name_tree::Entry npe = name_tree::Entry(prefix);
+  BOOST_CHECK_EQUAL(npe.getPrefix(), prefix);
+
+  // examine all the get methods
+
+  uint32_t hash = npe.getHash();
+  BOOST_CHECK_EQUAL(hash, 0);
+
+  shared_ptr<name_tree::Entry> parent = npe.getParent();
+  BOOST_CHECK(!static_cast<bool>(parent));
+
+  std::vector<shared_ptr<name_tree::Entry> >& childList = npe.getChildren();
+  BOOST_CHECK_EQUAL(childList.size(), 0);
+
+  shared_ptr<fib::Entry> fib = npe.getFibEntry();
+  BOOST_CHECK(!static_cast<bool>(fib));
+
+  std::vector< shared_ptr<pit::Entry> >& pitList = npe.getPitEntries();
+  BOOST_CHECK_EQUAL(pitList.size(), 0);
+
+  // examine all the set method 
+
+  npe.setHash(12345);
+  BOOST_CHECK_EQUAL(npe.getHash(), 12345);
+
+  Name parentName("ndn:/named-data/research/abc/def");
+  parent = make_shared<name_tree::Entry>(parentName);
+  npe.setParent(parent);
+  BOOST_CHECK_EQUAL(npe.getParent(), parent);
+
+  // Insert FIB 
+
+  shared_ptr<fib::Entry> fibEntry(new fib::Entry(prefix));
+  shared_ptr<fib::Entry> fibEntryParent(new fib::Entry(parentName));
+  
+  npe.setFibEntry(fibEntry);
+  BOOST_CHECK_EQUAL(npe.getFibEntry(), fibEntry);
+
+  // Erase a FIB that does not exist 
+  BOOST_CHECK_EQUAL(npe.
+  eraseFibEntry(fibEntryParent), false);
+  BOOST_CHECK_EQUAL(npe.getFibEntry(), fibEntry);
+
+  // Erase the FIB that exists
+  BOOST_CHECK_EQUAL(npe.
+  eraseFibEntry(fibEntry), true);
+  BOOST_CHECK(!static_cast<bool>(npe.getFibEntry()));
+
+  // Insert a PIT
+
+  shared_ptr<pit::Entry> PitEntry(make_shared<pit::Entry>(prefix));
+  shared_ptr<pit::Entry> PitEntry2(make_shared<pit::Entry>(parentName)); 
+
+  Name prefix3("ndn:/named-data/research/abc/def");
+  shared_ptr<pit::Entry> PitEntry3(make_shared<pit::Entry>(prefix3));
+
+  npe.insertPitEntry(PitEntry);
+  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
+
+  npe.insertPitEntry(PitEntry2);
+  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 2);
+
+  BOOST_CHECK_EQUAL(npe.
+  erasePitEntry(PitEntry), true);
+  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
+
+  // erase a PIT Entry that does not exist
+
+  BOOST_CHECK_EQUAL(npe.
+  erasePitEntry(PitEntry3), false);
+  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
+
+  BOOST_CHECK_EQUAL(npe.
+  erasePitEntry(PitEntry2), true);
+  BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 0);
+
+  // erase a PIT Entry that does not exist any more
+
+  BOOST_CHECK_EQUAL(npe.
+  erasePitEntry(PitEntry2), false);
+}
+
+BOOST_AUTO_TEST_CASE (NameTreeBasic)
+{
+  size_t nBuckets = 16;
+  NameTree nt(nBuckets);
+
+  BOOST_CHECK_EQUAL(nt.size(), 0);
+  BOOST_CHECK_EQUAL(nt.getNBuckets(), nBuckets); 
+
+  Name nameABC = ("ndn:/a/b/c");
+  shared_ptr<name_tree::Entry> npeABC = nt.lookup(nameABC);
+  BOOST_CHECK_EQUAL(nt.size(), 4);
+  
+  Name nameABD = ("/a/b/d");
+  shared_ptr<name_tree::Entry> npeABD = nt.lookup(nameABD);
+  BOOST_CHECK_EQUAL(nt.size(), 5);
+
+  Name nameAE = ("/a/e/");
+  shared_ptr<name_tree::Entry> npeAE = nt.lookup(nameAE);
+  BOOST_CHECK_EQUAL(nt.size(), 6);
+
+  Name nameF = ("/f");
+  shared_ptr<name_tree::Entry> npeF = nt.lookup(nameF);
+  BOOST_CHECK_EQUAL(nt.size(), 7);
+
+  // validate lookup() and findExactMatch() 
+
+  Name nameAB ("/a/b");
+  BOOST_CHECK_EQUAL(npeABC->getParent(), nt.findExactMatch(nameAB));
+  BOOST_CHECK_EQUAL(npeABD->getParent(), nt.findExactMatch(nameAB));
+
+  Name nameA ("/a");
+  BOOST_CHECK_EQUAL(npeAE->getParent(), nt.findExactMatch(nameA));
+
+  Name nameRoot ("/");
+  BOOST_CHECK_EQUAL(npeF->getParent(), nt.findExactMatch(nameRoot));
+  BOOST_CHECK_EQUAL(nt.size(), 7);
+
+  Name name0 = ("/does/not/exist");
+  shared_ptr<name_tree::Entry> npe0 = nt.findExactMatch(name0);
+  BOOST_CHECK(!static_cast<bool>(npe0));
+
+
+  // Longest Prefix Matching
+
+  shared_ptr<name_tree::Entry> temp;
+  Name nameABCLPM("/a/b/c/def/asdf/nlf");
+  temp = nt.findLongestPrefixMatch(nameABCLPM);
+  BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABC));
+
+  Name nameABDLPM("/a/b/d/def/asdf/nlf");
+  temp = nt.findLongestPrefixMatch(nameABDLPM);
+  BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABD));
+
+  Name nameABLPM("/a/b/hello/world");
+  temp = nt.findLongestPrefixMatch(nameABLPM);
+  BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameAB));
+
+  Name nameAELPM("/a/e/hello/world");
+  temp = nt.findLongestPrefixMatch(nameAELPM);
+  BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameAE));
+
+  Name nameALPM("/a/hello/world");
+  temp = nt.findLongestPrefixMatch(nameALPM);
+  BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameA));
+
+  Name nameFLPM("/f/hello/world");
+  temp = nt.findLongestPrefixMatch(nameFLPM);
+  BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameF));
+
+  Name nameRootLPM("/does_not_exist");
+  temp = nt.findLongestPrefixMatch(nameRootLPM);
+  BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameRoot));
+
+  // nt.dump(std::cout);
+
+  bool eraseResult = false;
+  temp = nt.findExactMatch(nameABC);
+  if (static_cast<bool>(temp))
+    eraseResult = nt.
+  eraseEntryIfEmpty(temp);
+  BOOST_CHECK_EQUAL(nt.size(), 6);
+  BOOST_CHECK(!static_cast<bool>(nt.findExactMatch(nameABC)));
+  BOOST_CHECK_EQUAL(eraseResult, true);
+
+  eraseResult = false;
+  temp = nt.findExactMatch(nameABCLPM);
+  if (static_cast<bool>(temp)) 
+    eraseResult = nt.
+  eraseEntryIfEmpty(temp);
+  BOOST_CHECK(!static_cast<bool>(temp));
+  BOOST_CHECK_EQUAL(nt.size(), 6);
+  BOOST_CHECK_EQUAL(eraseResult, false);
+
+  // nt.dump(std::cout);
+
+  nt.lookup(nameABC);
+  BOOST_CHECK_EQUAL(nt.size(), 7);
+
+  eraseResult = false;
+  temp = nt.findExactMatch(nameABC);
+  if (static_cast<bool>(temp)) 
+    eraseResult = nt.
+  eraseEntryIfEmpty(temp);
+  BOOST_CHECK_EQUAL(nt.size(), 6);
+  BOOST_CHECK_EQUAL(eraseResult, true);
+  BOOST_CHECK(!static_cast<bool>(nt.findExactMatch(nameABC)));
+
+  // nt.dump(std::cout);
+
+  BOOST_CHECK_EQUAL(nt.getNBuckets(), 16);
+
+  // should resize now 
+  Name nameABCD("a/b/c/d");
+  nt.lookup(nameABCD);
+  Name nameABCDE("a/b/c/d/e");
+  nt.lookup(nameABCDE);
+  BOOST_CHECK_EQUAL(nt.size(), 9);
+  BOOST_CHECK_EQUAL(nt.getNBuckets(), 32);
+
+  // nt.dump(std::cout);
+
+  // try to erase /a/b/c, should return false 
+  temp = nt.findExactMatch(nameABC);
+  BOOST_CHECK_EQUAL(temp->getPrefix(), nameABC);
+  eraseResult = nt.
+  eraseEntryIfEmpty(temp);
+  BOOST_CHECK_EQUAL(eraseResult, false);
+  temp = nt.findExactMatch(nameABC);
+  BOOST_CHECK_EQUAL(temp->getPrefix(), nameABC);
+
+  temp = nt.findExactMatch(nameABD);
+  if (static_cast<bool>(temp)) 
+    nt.
+  eraseEntryIfEmpty(temp);
+  BOOST_CHECK_EQUAL(nt.size(), 8);
+  
+  // nt.dump(std::cout);
+
+  shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > fullList;
+  fullList = nt.fullEnumerate();
+  BOOST_CHECK_EQUAL(fullList->size(), 8);
+  // for (size_t j = 0; j < (*fullList).size(); j++)
+  // {
+  //  temp = (*fullList)[j];
+  //  std::cout << temp->getPrefix().toUri() << std::endl;
+  // }
+
+  shared_ptr<std::vector<shared_ptr<name_tree::Entry> > > partialList;
+  partialList = nt.partialEnumerate(nameA);
+  BOOST_CHECK_EQUAL(partialList->size(), 6);
+  // for (size_t j = 0; j < (*partialList).size(); j++)
+  // {
+  //  temp = (*partialList)[j];
+  //  std::cout << temp->getPrefix().toUri() << std::endl;
+  // }
+
+  partialList = nt.partialEnumerate(nameRoot);
+  BOOST_CHECK_EQUAL(partialList->size(), 8);
+  // for (size_t j = 0; j < (*partialList).size(); j++)
+  // {
+  //  temp = (*partialList)[j];
+  //  std::cout << temp->getPrefix().toUri() << std::endl;
+  // }
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace nfd
+
+