table: NameTree optimization

This commit adds platform-specific hash function selection and hash
table shrink function.

Change-Id: Iaaa0e5b86842d4e0582d3523f0a6b6836e152239
Refs: #1305
diff --git a/tests/table/fib.cpp b/tests/table/fib.cpp
index 368067d..629a10f 100644
--- a/tests/table/fib.cpp
+++ b/tests/table/fib.cpp
@@ -136,7 +136,7 @@
   std::pair<shared_ptr<fib::Entry>, bool> insertRes;
   shared_ptr<fib::Entry> entry;
 
-  NameTree nameTree(1024);
+  NameTree nameTree;
   Fib fib(nameTree);
   // []
   BOOST_CHECK_EQUAL(fib.size(), 0);
@@ -208,7 +208,7 @@
   std::pair<shared_ptr<fib::Entry>, bool> insertRes;
   shared_ptr<fib::Entry> entry;
 
-  NameTree nameTree(1024);
+  NameTree nameTree;
   Fib fib(nameTree);
   // {}
 
@@ -262,7 +262,7 @@
 
 BOOST_AUTO_TEST_CASE(FindExactMatch)
 {
-  NameTree nameTree(1024);
+  NameTree nameTree;
   Fib fib(nameTree);
   fib.insert("/A");
   fib.insert("/A/B");
@@ -275,14 +275,14 @@
 
   validateNoExactMatch(fib, "/does/not/exist");
 
-  NameTree gapNameTree(1024);
+  NameTree gapNameTree;
   Fib gapFib(nameTree);
   fib.insert("/X");
   fib.insert("/X/Y/Z");
 
   validateNoExactMatch(gapFib, "/X/Y");
 
-  NameTree emptyNameTree(1024);
+  NameTree emptyNameTree;
   Fib emptyFib(emptyNameTree);
   validateNoExactMatch(emptyFib, "/nothing/here");
 }
@@ -301,7 +301,7 @@
 
 BOOST_AUTO_TEST_CASE(Remove)
 {
-  NameTree emptyNameTree(1024);
+  NameTree emptyNameTree;
   Fib emptyFib(emptyNameTree);
 
   emptyFib.erase("/does/not/exist"); // crash test
@@ -310,7 +310,7 @@
 
   emptyFib.erase("/still/does/not/exist"); // crash test
 
-  NameTree nameTree(1024);
+  NameTree nameTree;
   Fib fib(nameTree);
   fib.insert("/");
   fib.insert("/A");
@@ -335,7 +335,7 @@
   validateRemove(fib, "/");
   validateNoExactMatch(fib, "/");
 
-  NameTree gapNameTree(1024);
+  NameTree gapNameTree;
   Fib gapFib(gapNameTree);
   gapFib.insert("/X");
   gapFib.insert("/X/Y/Z");
@@ -347,7 +347,7 @@
 
 BOOST_AUTO_TEST_CASE(Iterator)
 {
-  NameTree nameTree(1024);
+  NameTree nameTree;
   Fib fib(nameTree);
   Name nameA("/A");
   Name nameAB("/A/B");
diff --git a/tests/table/measurements.cpp b/tests/table/measurements.cpp
index 3de39ca..98676b5 100644
--- a/tests/table/measurements.cpp
+++ b/tests/table/measurements.cpp
@@ -33,7 +33,7 @@
 
 BOOST_AUTO_TEST_CASE(Get_Parent)
 {
-  NameTree nameTree(1024);
+  NameTree nameTree;
   Measurements measurements(nameTree);
 
   Name name0;
diff --git a/tests/table/name-tree.cpp b/tests/table/name-tree.cpp
index a652558..e5e9089 100644
--- a/tests/table/name-tree.cpp
+++ b/tests/table/name-tree.cpp
@@ -32,6 +32,19 @@
 
 BOOST_FIXTURE_TEST_SUITE(TableNameTree, BaseFixture)
 
+BOOST_AUTO_TEST_CASE(Hash)
+{
+  Name root("/");
+  root.wireEncode();
+  size_t hashValue = name_tree::computeHash(root);
+  BOOST_CHECK_EQUAL(hashValue, static_cast<size_t>(0));
+
+  Name prefix("/nohello/world/ndn/research");
+  prefix.wireEncode();
+  std::vector<size_t> hashSet = name_tree::computeHashSet(prefix);
+  BOOST_CHECK_EQUAL(hashSet.size(), prefix.size() + 1);
+}
+
 BOOST_AUTO_TEST_CASE(Entry)
 {
   Name prefix("ndn:/named-data/research/abc/def/ghi");
@@ -41,25 +54,25 @@
 
   // examine all the get methods
 
-  uint32_t hash = npe->getHash();
-  BOOST_CHECK_EQUAL(hash, 0);
+  size_t hash = npe->getHash();
+  BOOST_CHECK_EQUAL(hash, static_cast<size_t>(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);
+  BOOST_CHECK_EQUAL(childList.size(), static_cast<size_t>(0));
 
   shared_ptr<fib::Entry> fib = npe->getFibEntry();
   BOOST_CHECK(!static_cast<bool>(fib));
 
   const std::vector< shared_ptr<pit::Entry> >& pitList = npe->getPitEntries();
-  BOOST_CHECK_EQUAL(pitList.size(), 0);
+  BOOST_CHECK_EQUAL(pitList.size(), static_cast<size_t>(0));
 
   // examine all the set method
 
-  npe->setHash(12345);
-  BOOST_CHECK_EQUAL(npe->getHash(), 12345);
+  npe->setHash(static_cast<size_t>(12345));
+  BOOST_CHECK_EQUAL(npe->getHash(), static_cast<size_t>(12345));
 
   Name parentName("ndn:/named-data/research/abc/def");
   parent = make_shared<name_tree::Entry>(parentName);
@@ -138,7 +151,6 @@
 
 
   // Longest Prefix Matching
-
   shared_ptr<name_tree::Entry> temp;
   Name nameABCLPM("/a/b/c/def/asdf/nlf");
   temp = nt.findLongestPrefixMatch(nameABCLPM);
@@ -228,8 +240,6 @@
 
 BOOST_AUTO_TEST_CASE(NameTreeIteratorFullEnumerate)
 {
-  using namespace std;
-
   size_t nBuckets = 1024;
   NameTree nt(nBuckets);
 
@@ -378,7 +388,6 @@
 
 BOOST_AUTO_TEST_CASE(NameTreeIteratorPartialEnumerate)
 {
-  using namespace std;
   typedef NameTree::const_iterator const_iterator;
 
   size_t nBuckets = 16;
@@ -680,8 +689,6 @@
 
 BOOST_AUTO_TEST_CASE(NameTreeIteratorFindAllMatches)
 {
-  using namespace std;
-
   size_t nBuckets = 16;
   NameTree nt(nBuckets);
   int counter = 0;
@@ -772,6 +779,22 @@
   BOOST_CHECK_EQUAL(counter, 7);
 }
 
+BOOST_AUTO_TEST_CASE(NameTreeHashTableResizeShrink)
+{
+  size_t nBuckets = 16;
+  NameTree nameTree(nBuckets);
+
+  Name prefix("/a/b/c/d/e/f/g/h"); // requires 9 buckets
+
+  shared_ptr<name_tree::Entry> entry = nameTree.lookup(prefix);
+  BOOST_CHECK_EQUAL(nameTree.size(), 9);
+  BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 32);
+
+  nameTree.eraseEntryIfEmpty(entry);
+  BOOST_CHECK_EQUAL(nameTree.size(), 0);
+  BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 16);
+}
+
 BOOST_AUTO_TEST_SUITE_END()
 
 } // namespace tests