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