table: NameTree code style corrections
refs #3687
Change-Id: I25cfac1d8b11236c251c2ab717facb82b62dcb10
diff --git a/daemon/table/fib-entry.hpp b/daemon/table/fib-entry.hpp
index 8f83266..94f2331 100644
--- a/daemon/table/fib-entry.hpp
+++ b/daemon/table/fib-entry.hpp
@@ -30,10 +30,11 @@
namespace nfd {
-class NameTree;
namespace name_tree {
+class NameTree;
class Entry;
} // namespace name_tree
+using name_tree::NameTree;
namespace fib {
diff --git a/daemon/table/measurements-entry.hpp b/daemon/table/measurements-entry.hpp
index 8eb40ff..933baef 100644
--- a/daemon/table/measurements-entry.hpp
+++ b/daemon/table/measurements-entry.hpp
@@ -32,11 +32,11 @@
namespace nfd {
-class NameTree;
-
namespace name_tree {
+class NameTree;
class Entry;
} // namespace name_tree
+using name_tree::NameTree;
namespace measurements {
diff --git a/daemon/table/name-tree-entry.cpp b/daemon/table/name-tree-entry.cpp
index b094e38..c0bc932 100644
--- a/daemon/table/name-tree-entry.cpp
+++ b/daemon/table/name-tree-entry.cpp
@@ -29,8 +29,8 @@
namespace name_tree {
Node::Node()
- : m_prev(0)
- , m_next(0)
+ : m_prev(nullptr)
+ , m_next(nullptr)
{
}
@@ -38,9 +38,9 @@
{
// erase the Name Tree Nodes that were created to
// resolve hash collisions
- // So before erasing a single node, make sure its m_next == 0
+ // So before erasing a single node, make sure its m_next == nullptr
// See eraseEntryIfEmpty in name-tree.cpp
- if (m_next != 0)
+ if (m_next != nullptr)
delete m_next;
}
@@ -50,10 +50,6 @@
{
}
-Entry::~Entry()
-{
-}
-
bool
Entry::isEmpty() const
{
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index 2827926..23acdd0 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -34,13 +34,11 @@
namespace nfd {
-class NameTree;
-
namespace name_tree {
-// Forward declarations
class Node;
class Entry;
+class NameTree;
/**
* \brief Name Tree Node Class
@@ -68,8 +66,6 @@
explicit
Entry(const Name& prefix);
- ~Entry();
-
const Name&
getPrefix() const;
@@ -85,7 +81,7 @@
shared_ptr<Entry>
getParent() const;
- std::vector<shared_ptr<Entry> >&
+ std::vector<shared_ptr<Entry>>&
getChildren();
bool
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index bcf888e..abc5672 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -32,6 +32,7 @@
#include <type_traits>
namespace nfd {
+namespace name_tree {
NFD_LOG_INIT("NameTree");
@@ -46,8 +47,6 @@
BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<NameTree::const_iterator>));
#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
-namespace name_tree {
-
class Hash32
{
public:
@@ -81,12 +80,11 @@
size_t hashValue = 0;
size_t hashUpdate = 0;
- for (Name::const_iterator it = prefix.begin(); it != prefix.end(); it++)
- {
- const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
- hashUpdate = CityHash::compute(wireFormat, it->size());
- hashValue ^= hashUpdate;
- }
+ for (Name::const_iterator it = prefix.begin(); it != prefix.end(); ++it) {
+ const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
+ hashUpdate = CityHash::compute(wireFormat, it->size());
+ hashValue ^= hashUpdate;
+ }
return hashValue;
}
@@ -94,7 +92,7 @@
std::vector<size_t>
computeHashSet(const Name& prefix)
{
- prefix.wireEncode(); // guarantees prefix's wire buffer is not empty
+ prefix.wireEncode(); // guarantees prefix's wire buffer is not empty
size_t hashValue = 0;
size_t hashUpdate = 0;
@@ -102,156 +100,141 @@
std::vector<size_t> hashValueSet;
hashValueSet.push_back(hashValue);
- for (Name::const_iterator it = prefix.begin(); it != prefix.end(); it++)
- {
- const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
- hashUpdate = CityHash::compute(wireFormat, it->size());
- hashValue ^= hashUpdate;
- hashValueSet.push_back(hashValue);
- }
+ for (Name::const_iterator it = prefix.begin(); it != prefix.end(); ++it) {
+ const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
+ hashUpdate = CityHash::compute(wireFormat, it->size());
+ hashValue ^= hashUpdate;
+ hashValueSet.push_back(hashValue);
+ }
return hashValueSet;
}
-} // namespace name_tree
-
NameTree::NameTree(size_t nBuckets)
: m_nItems(0)
, m_nBuckets(nBuckets)
, m_minNBuckets(nBuckets)
- , m_enlargeLoadFactor(0.5) // more than 50% buckets loaded
+ , m_enlargeLoadFactor(0.5) // more than 50% buckets loaded
, m_enlargeFactor(2) // double the hash table size
- , m_shrinkLoadFactor(0.1) // less than 10% buckets loaded
- , m_shrinkFactor(0.5) // reduce the number of buckets by half
+ , m_shrinkLoadFactor(0.1) // less than 10% buckets loaded
+ , m_shrinkFactor(0.5) // reduce the number of buckets by half
, m_endIterator(FULL_ENUMERATE_TYPE, *this, m_end)
{
- m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor *
- static_cast<double>(m_nBuckets));
-
- m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor *
- static_cast<double>(m_nBuckets));
+ m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor * static_cast<double>(m_nBuckets));
+ m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor * static_cast<double>(m_nBuckets));
// array of node pointers
- m_buckets = new name_tree::Node*[m_nBuckets];
+ m_buckets = new Node*[m_nBuckets];
// Initialize the pointer array
- for (size_t i = 0; i < m_nBuckets; i++)
- m_buckets[i] = 0;
+ for (size_t i = 0; i < m_nBuckets; ++i) {
+ m_buckets[i] = nullptr;
+ }
}
NameTree::~NameTree()
{
- for (size_t i = 0; i < m_nBuckets; i++)
- {
- if (m_buckets[i] != 0) {
- delete m_buckets[i];
- }
+ for (size_t i = 0; i < m_nBuckets; ++i) {
+ if (m_buckets[i] != nullptr) {
+ delete m_buckets[i];
}
+ }
- delete [] m_buckets;
+ delete[] m_buckets;
}
// insert() is a private function, and called by only lookup()
-std::pair<shared_ptr<name_tree::Entry>, bool>
+std::pair<shared_ptr<Entry>, bool>
NameTree::insert(const Name& prefix)
{
NFD_LOG_TRACE("insert " << prefix);
- size_t hashValue = name_tree::computeHash(prefix);
+ size_t hashValue = computeHash(prefix);
size_t loc = hashValue % m_nBuckets;
NFD_LOG_TRACE("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
+ Node* node = m_buckets[loc];
+ Node* nodePrev = 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;
+ for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
+ if (node->m_entry != nullptr) {
+ if (prefix == node->m_entry->m_prefix) {
+ return {node->m_entry, false}; // false: old entry
+ }
}
+ nodePrev = node;
+ }
NFD_LOG_TRACE("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 = new Node();
node->m_prev = nodePrev;
- if (nodePrev == 0)
- {
- m_buckets[loc] = node;
- }
- else
- {
- nodePrev->m_next = node;
- }
+ if (nodePrev == nullptr) {
+ 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));
+ auto entry = make_shared<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
+ return {entry, true}; // true: new entry
}
// Name Prefix Lookup. Create Name Tree Entry if not found
-shared_ptr<name_tree::Entry>
+shared_ptr<Entry>
NameTree::lookup(const Name& prefix)
{
NFD_LOG_TRACE("lookup " << prefix);
- shared_ptr<name_tree::Entry> entry;
- shared_ptr<name_tree::Entry> parent;
+ shared_ptr<Entry> entry;
+ shared_ptr<Entry> parent;
- for (size_t i = 0; i <= prefix.size(); i++)
- {
- Name temp = prefix.getPrefix(i);
+ 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;
+ // insert() will create the entry if it does not exist.
+ bool isNew = false;
+ std::tie(entry, isNew) = insert(temp);
- if (ret.second == true)
- {
- m_nItems++; // Increase the counter
- entry->m_parent = parent;
+ if (isNew) {
+ ++m_nItems; // Increase the counter
+ entry->m_parent = parent;
- if (static_cast<bool>(parent))
- {
- parent->m_children.push_back(entry);
- }
- }
-
- if (m_nItems > m_enlargeThreshold)
- {
- resize(m_enlargeFactor * m_nBuckets);
- }
-
- parent = entry;
+ if (parent != nullptr) {
+ parent->m_children.push_back(entry);
+ }
}
+
+ if (m_nItems > m_enlargeThreshold) {
+ resize(m_enlargeFactor * m_nBuckets);
+ }
+
+ parent = entry;
+ }
return entry;
}
-shared_ptr<name_tree::Entry>
+shared_ptr<Entry>
NameTree::lookup(const fib::Entry& fibEntry) const
{
- shared_ptr<name_tree::Entry> nte = this->getEntry(fibEntry);
+ shared_ptr<Entry> nte = this->getEntry(fibEntry);
BOOST_ASSERT(nte == nullptr || nte->getFibEntry() == &fibEntry);
return nte;
}
-shared_ptr<name_tree::Entry>
+shared_ptr<Entry>
NameTree::lookup(const pit::Entry& pitEntry)
{
- shared_ptr<name_tree::Entry> nte = this->getEntry(pitEntry);
+ shared_ptr<Entry> nte = this->getEntry(pitEntry);
if (nte == nullptr) {
return nullptr;
}
@@ -265,128 +248,115 @@
return this->lookup(pitEntry.getName());
}
-shared_ptr<name_tree::Entry>
+shared_ptr<Entry>
NameTree::lookup(const measurements::Entry& measurementsEntry) const
{
- shared_ptr<name_tree::Entry> nte = this->getEntry(measurementsEntry);
+ shared_ptr<Entry> nte = this->getEntry(measurementsEntry);
BOOST_ASSERT(nte == nullptr || nte->getMeasurementsEntry() == &measurementsEntry);
return nte;
}
-shared_ptr<name_tree::Entry>
+shared_ptr<Entry>
NameTree::lookup(const strategy_choice::Entry& strategyChoiceEntry) const
{
- shared_ptr<name_tree::Entry> nte = this->getEntry(strategyChoiceEntry);
+ shared_ptr<Entry> nte = this->getEntry(strategyChoiceEntry);
BOOST_ASSERT(nte == nullptr || nte->getStrategyChoiceEntry() == &strategyChoiceEntry);
return nte;
}
// return {false: this entry is not empty, true: this entry is empty and erased}
bool
-NameTree::eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry)
+NameTree::eraseEntryIfEmpty(shared_ptr<Entry> entry)
{
- BOOST_ASSERT(static_cast<bool>(entry));
+ BOOST_ASSERT(entry != nullptr);
NFD_LOG_TRACE("eraseEntryIfEmpty " << entry->getPrefix());
// first check if this Entry can be erased
- if (entry->isEmpty())
- {
- // update child-related info in the parent
- shared_ptr<name_tree::Entry> parent = entry->getParent();
+ if (entry->isEmpty()) {
+ // update child-related info in the parent
+ shared_ptr<Entry> parent = entry->getParent();
- if (static_cast<bool>(parent))
- {
- std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList =
- parent->getChildren();
+ if (parent != nullptr) {
+ std::vector<shared_ptr<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_VERIFY(isFound == true);
+ 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;
}
+ }
- // remove this Entry and its Name Tree Node
- name_tree::Node* node = entry->m_node;
- name_tree::Node* nodePrev = node->m_prev;
+ BOOST_VERIFY(isFound == true);
+ }
- // 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;
- }
+ // remove this Entry and its Name Tree Node
+ Node* node = entry->m_node;
+ Node* nodePrev = node->m_prev;
- // 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;
- }
+ // configure the previous node
+ if (nodePrev != nullptr) {
+ // link the previous node to the next node
+ nodePrev->m_next = node->m_next;
+ }
+ else {
+ m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
+ }
- BOOST_ASSERT(node->m_next == 0);
+ // link the previous node with the next node (skip the erased one)
+ if (node->m_next != nullptr) {
+ node->m_next->m_prev = nodePrev;
+ node->m_next = 0;
+ }
- m_nItems--;
- delete node;
+ BOOST_ASSERT(node->m_next == nullptr);
- if (static_cast<bool>(parent))
- eraseEntryIfEmpty(parent);
+ --m_nItems;
+ delete node;
- size_t newNBuckets = static_cast<size_t>(m_shrinkFactor *
- static_cast<double>(m_nBuckets));
+ if (parent != nullptr) {
+ eraseEntryIfEmpty(parent);
+ }
- if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold)
- {
- resize(newNBuckets);
- }
+ size_t newNBuckets = static_cast<size_t>(m_shrinkFactor * static_cast<double>(m_nBuckets));
- return true;
+ if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold) {
+ resize(newNBuckets);
+ }
- } // if this entry is empty
+ return true;
- return false; // if this entry is not empty
+ }
+
+ return false;
}
// Exact Match
-shared_ptr<name_tree::Entry>
+shared_ptr<Entry>
NameTree::findExactMatch(const Name& prefix) const
{
NFD_LOG_TRACE("findExactMatch " << prefix);
- size_t hashValue = name_tree::computeHash(prefix);
+ size_t hashValue = computeHash(prefix);
size_t loc = hashValue % m_nBuckets;
- NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue <<
- " location = " << loc);
+ NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue << " location = " << loc);
- shared_ptr<name_tree::Entry> entry;
- name_tree::Node* node = 0;
+ shared_ptr<Entry> entry;
+ Node* node = nullptr;
- 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
+ for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
+ entry = node->m_entry;
+ if (entry != nullptr) {
+ if (hashValue == entry->getHash() && prefix == entry->getPrefix()) {
+ return entry;
+ }
+ }
+ }
// if not found, the default value of entry (null pointer) will be returned
entry.reset();
@@ -394,61 +364,55 @@
}
// Longest Prefix Match
-shared_ptr<name_tree::Entry>
-NameTree::findLongestPrefixMatch(const Name& prefix, const name_tree::EntrySelector& entrySelector) const
+shared_ptr<Entry>
+NameTree::findLongestPrefixMatch(const Name& prefix, const EntrySelector& entrySelector) const
{
NFD_LOG_TRACE("findLongestPrefixMatch " << prefix);
- shared_ptr<name_tree::Entry> entry;
- std::vector<size_t> hashValueSet = name_tree::computeHashSet(prefix);
+ shared_ptr<Entry> entry;
+ std::vector<size_t> hashValueSet = computeHashSet(prefix);
size_t hashValue = 0;
size_t loc = 0;
- for (int i = static_cast<int>(prefix.size()); i >= 0; i--)
- {
- hashValue = hashValueSet[i];
- loc = hashValue % m_nBuckets;
+ for (int i = static_cast<int>(prefix.size()); i >= 0; --i) {
+ hashValue = hashValueSet[i];
+ loc = hashValue % m_nBuckets;
- 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))
- {
- // isPrefixOf() is used to avoid making a copy of the name
- if (hashValue == entry->getHash() &&
- entry->getPrefix().isPrefixOf(prefix) &&
- entrySelector(*entry))
- {
- return entry;
- }
- } // if entry
- } // for node
+ Node* node = nullptr;
+ for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
+ entry = node->m_entry;
+ if (entry != nullptr) {
+ // isPrefixOf() is used to avoid making a copy of the name
+ if (hashValue == entry->getHash() &&
+ entry->getPrefix().isPrefixOf(prefix) &&
+ entrySelector(*entry)) {
+ return entry;
+ }
+ }
}
+ }
- // if not found, the default value of entry (null pointer) will be returned
- entry.reset();
- return entry;
+ return nullptr;
}
-shared_ptr<name_tree::Entry>
-NameTree::findLongestPrefixMatch(shared_ptr<name_tree::Entry> entry,
- const name_tree::EntrySelector& entrySelector) const
+shared_ptr<Entry>
+NameTree::findLongestPrefixMatch(shared_ptr<Entry> entry,
+ const EntrySelector& entrySelector) const
{
- while (static_cast<bool>(entry))
- {
- if (entrySelector(*entry))
- return entry;
- entry = entry->getParent();
+ while (entry != nullptr) {
+ if (entrySelector(*entry)) {
+ return entry;
}
- return shared_ptr<name_tree::Entry>();
+ entry = entry->getParent();
+ }
+ return nullptr;
}
-shared_ptr<name_tree::Entry>
+shared_ptr<Entry>
NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry) const
{
- shared_ptr<name_tree::Entry> nte = this->getEntry(pitEntry);
+ shared_ptr<Entry> nte = this->getEntry(pitEntry);
BOOST_ASSERT(nte != nullptr);
if (nte->getPrefix().size() == pitEntry.getName().size()) {
return nte;
@@ -456,13 +420,13 @@
BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
BOOST_ASSERT(nte->getPrefix() == pitEntry.getName().getPrefix(-1));
- shared_ptr<name_tree::Entry> exact = this->findExactMatch(pitEntry.getName());
+ shared_ptr<Entry> exact = this->findExactMatch(pitEntry.getName());
return exact == nullptr ? nte : exact;
}
boost::iterator_range<NameTree::const_iterator>
NameTree::findAllMatches(const Name& prefix,
- const name_tree::EntrySelector& entrySelector) const
+ const EntrySelector& entrySelector) const
{
NFD_LOG_TRACE("NameTree::findAllMatches" << prefix);
@@ -472,9 +436,9 @@
// For trie-like design, it could be more efficient by walking down the
// trie from the root node.
- shared_ptr<name_tree::Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
+ shared_ptr<Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
- if (static_cast<bool>(entry)) {
+ if (entry != nullptr) {
const_iterator begin(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
return {begin, end()};
}
@@ -483,14 +447,14 @@
}
boost::iterator_range<NameTree::const_iterator>
-NameTree::fullEnumerate(const name_tree::EntrySelector& entrySelector) const
+NameTree::fullEnumerate(const EntrySelector& entrySelector) const
{
NFD_LOG_TRACE("fullEnumerate");
// find the first eligible 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)) {
+ for (size_t i = 0; i < m_nBuckets; ++i) {
+ for (Node* node = m_buckets[i]; node != nullptr; node = node->m_next) {
+ if (node->m_entry != nullptr && entrySelector(*node->m_entry)) {
const_iterator it(FULL_ENUMERATE_TYPE, *this, node->m_entry, entrySelector);
return {it, end()};
}
@@ -503,19 +467,19 @@
boost::iterator_range<NameTree::const_iterator>
NameTree::partialEnumerate(const Name& prefix,
- const name_tree::EntrySubTreeSelector& entrySubTreeSelector) const
+ const EntrySubTreeSelector& entrySubTreeSelector) const
{
// the first step is to process the root node
- shared_ptr<name_tree::Entry> entry = findExactMatch(prefix);
- if (!static_cast<bool>(entry)) {
+ shared_ptr<Entry> entry = findExactMatch(prefix);
+ if (entry == nullptr) {
return {end(), end()};
}
- std::pair<bool, bool>result = entrySubTreeSelector(*entry);
+ std::pair<bool, bool> result = entrySubTreeSelector(*entry);
const_iterator it(PARTIAL_ENUMERATE_TYPE,
*this,
entry,
- name_tree::AnyEntry(),
+ AnyEntry(),
entrySubTreeSelector);
it.m_shouldVisitChildren = (result.second && entry->hasChildren());
@@ -536,56 +500,45 @@
{
NFD_LOG_TRACE("resize");
- name_tree::Node** newBuckets = new name_tree::Node*[newNBuckets];
+ Node** newBuckets = new Node*[newNBuckets];
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
- size_t i;
- uint32_t h;
- uint32_t b;
+ Node** pp = nullptr;
+ Node* p = nullptr;
+ Node* pre = nullptr;
+ Node* q = nullptr; // record p->m_next
- for (i = 0; i < newNBuckets; i++)
- {
- newBuckets[i] = 0;
- }
+ for (size_t i = 0; i < newNBuckets; ++i) {
+ newBuckets[i] = nullptr;
+ }
- 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;
- pre = 0;
- 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;
- }
+ for (size_t i = 0; i < m_nBuckets; ++i) {
+ for (p = m_buckets[i]; p != nullptr; p = q) {
+ ++count;
+ q = p->m_next;
+ BOOST_ASSERT(p->m_entry != nullptr);
+ uint32_t h = p->m_entry->m_hash;
+ uint32_t b = h % newNBuckets;
+ pre = nullptr;
+ for (pp = &newBuckets[b]; *pp != nullptr; pp = &((*pp)->m_next)) {
+ pre = *pp;
+ }
+ p->m_prev = pre;
+ p->m_next = *pp; // Actually *pp always == nullptr in this case
+ *pp = p;
}
+ }
BOOST_ASSERT(count == m_nItems);
- name_tree::Node** oldBuckets = m_buckets;
+ Node** oldBuckets = m_buckets;
m_buckets = newBuckets;
- delete [] oldBuckets;
+ delete[] oldBuckets;
m_nBuckets = newNBuckets;
-
- m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor *
- static_cast<double>(m_nBuckets));
- m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor *
- static_cast<double>(m_nBuckets));
+ m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor * static_cast<double>(m_nBuckets));
+ m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor * static_cast<double>(m_nBuckets));
}
// For debugging
@@ -594,51 +547,41 @@
{
NFD_LOG_TRACE("dump()");
- name_tree::Node* node = 0;
- shared_ptr<name_tree::Entry> entry;
+ Node* node = nullptr;
+ shared_ptr<Entry> entry;
- using std::endl;
+ for (size_t i = 0; i < m_nBuckets; ++i) {
+ for (node = m_buckets[i]; node != nullptr; node = node->m_next) {
+ entry = node->m_entry;
- 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 (entry != nullptr) {
+ output << "Bucket" << i << '\t' << entry->m_prefix.toUri() << '\n';
+ output << "\t\tHash " << entry->m_hash << '\n';
- // 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 (entry->m_parent != nullptr) {
+ output << "\t\tparent->" << entry->m_parent->m_prefix.toUri();
+ }
+ else {
+ output << "\t\tROOT";
+ }
+ output << '\n';
- 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.empty()) {
+ output << "\t\tchildren = " << entry->m_children.size() << '\n';
- 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() << '\n';
+ }
+ }
- 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 << "Bucket count = " << m_nBuckets << '\n';
+ output << "Stored item = " << m_nItems << '\n';
output << "--------------------------\n";
}
@@ -648,15 +591,15 @@
}
NameTree::const_iterator::const_iterator(NameTree::IteratorType type,
- const NameTree& nameTree,
- shared_ptr<name_tree::Entry> entry,
- const name_tree::EntrySelector& entrySelector,
- const name_tree::EntrySubTreeSelector& entrySubTreeSelector)
+ const NameTree& nameTree,
+ shared_ptr<Entry> entry,
+ const EntrySelector& entrySelector,
+ const EntrySubTreeSelector& entrySubTreeSelector)
: m_nameTree(&nameTree)
, m_entry(entry)
, m_subTreeRoot(entry)
- , m_entrySelector(make_shared<name_tree::EntrySelector>(entrySelector))
- , m_entrySubTreeSelector(make_shared<name_tree::EntrySubTreeSelector>(entrySubTreeSelector))
+ , m_entrySelector(make_shared<EntrySelector>(entrySelector))
+ , m_entrySubTreeSelector(make_shared<EntrySubTreeSelector>(entrySubTreeSelector))
, m_type(type)
, m_shouldVisitChildren(true)
{
@@ -670,162 +613,137 @@
BOOST_ASSERT(m_entry != m_nameTree->m_end);
- if (m_type == FULL_ENUMERATE_TYPE) // fullEnumerate
- {
- // process the entries in the same bucket first
- while (m_entry->m_node->m_next != 0)
- {
- m_entry = m_entry->m_node->m_next->m_entry;
- if ((*m_entrySelector)(*m_entry))
- {
- return *this;
- }
- }
-
- // process other buckets
-
- for (int newLocation = m_entry->m_hash % m_nameTree->m_nBuckets + 1;
- newLocation < static_cast<int>(m_nameTree->m_nBuckets);
- ++newLocation)
- {
- // process each bucket
- name_tree::Node* node = m_nameTree->m_buckets[newLocation];
- while (node != 0)
- {
- m_entry = node->m_entry;
- if ((*m_entrySelector)(*m_entry))
- {
- return *this;
- }
- node = node->m_next;
- }
- }
-
- // Reach the end()
- m_entry = m_nameTree->m_end;
- return *this;
+ if (m_type == FULL_ENUMERATE_TYPE) {
+ // process the entries in the same bucket first
+ while (m_entry->m_node->m_next != nullptr) {
+ m_entry = m_entry->m_node->m_next->m_entry;
+ if ((*m_entrySelector)(*m_entry)) {
+ return *this;
+ }
}
- if (m_type == PARTIAL_ENUMERATE_TYPE) // partialEnumerate
- {
- // We use pre-order traversal.
- // if at the root, it could have already been accepted, or this
- // iterator was just declared, and root doesn't satisfy the
- // requirement
- // The if() section handles this special case
- // Essentially, we need to check root's fist child, and the rest will
- // be the same as normal process
- if (m_entry == m_subTreeRoot)
- {
- if (m_shouldVisitChildren)
- {
- m_entry = m_entry->getChildren()[0];
- std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
- m_shouldVisitChildren = (result.second && m_entry->hasChildren());
- if(result.first)
- {
- return *this;
- }
- else
- {
- // the first child did not meet the requirement
- // the rest of the process can just fall through the while loop
- // as normal
- }
- }
- else
- {
- // no children, should return end();
- // just fall through
- }
+ // process other buckets
+
+ for (int newLocation = m_entry->m_hash % m_nameTree->m_nBuckets + 1;
+ newLocation < static_cast<int>(m_nameTree->m_nBuckets);
+ ++newLocation) {
+ // process each bucket
+ Node* node = m_nameTree->m_buckets[newLocation];
+ while (node != nullptr) {
+ m_entry = node->m_entry;
+ if ((*m_entrySelector)(*m_entry)) {
+ return *this;
}
-
- // The first thing to do is to visit its child, or go to find its possible
- // siblings
- while (m_entry != m_subTreeRoot)
- {
- if (m_shouldVisitChildren)
- {
- // If this subtree should be visited
- m_entry = m_entry->getChildren()[0];
- std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
- m_shouldVisitChildren = (result.second && m_entry->hasChildren());
- if (result.first) // if this node is acceptable
- {
- return *this;
- }
- else
- {
- // do nothing, as this node is essentially ignored
- // send this node to the while loop.
- }
- }
- else
- {
- // Should try to find its sibling
- shared_ptr<name_tree::Entry> parent = m_entry->getParent();
-
- std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList = parent->getChildren();
- bool isFound = false;
- size_t i = 0;
- for (i = 0; i < parentChildrenList.size(); i++)
- {
- if (parentChildrenList[i] == m_entry)
- {
- isFound = true;
- break;
- }
- }
-
- BOOST_VERIFY(isFound == true);
- if (i < parentChildrenList.size() - 1) // m_entry not the last child
- {
- m_entry = parentChildrenList[i + 1];
- std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
- m_shouldVisitChildren = (result.second && m_entry->hasChildren());
- if (result.first) // if this node is acceptable
- {
- return *this;
- }
- else
- {
- // do nothing, as this node is essentially ignored
- // send this node to the while loop.
- }
- }
- else
- {
- // m_entry is the last child, no more sibling, should try to find parent's sibling
- m_shouldVisitChildren = false;
- m_entry = parent;
- }
- }
- }
-
- m_entry = m_nameTree->m_end;
- return *this;
+ node = node->m_next;
+ }
}
- if (m_type == FIND_ALL_MATCHES_TYPE) // findAllMatches
- {
- // Assumption: at the beginning, m_entry was initialized with the first
- // eligible Name Tree entry (i.e., has a PIT entry that can be satisfied
- // by the Data packet)
+ // Reach the end()
+ m_entry = m_nameTree->m_end;
+ return *this;
+ }
- while (static_cast<bool>(m_entry->getParent()))
- {
- m_entry = m_entry->getParent();
- if ((*m_entrySelector)(*m_entry))
+ if (m_type == PARTIAL_ENUMERATE_TYPE) {
+ // We use pre-order traversal.
+ // if at the root, it could have already been accepted, or this
+ // iterator was just declared, and root doesn't satisfy the
+ // requirement
+ // The if() section handles this special case
+ // Essentially, we need to check root's fist child, and the rest will
+ // be the same as normal process
+ if (m_entry == m_subTreeRoot) {
+ if (m_shouldVisitChildren) {
+ m_entry = m_entry->getChildren()[0];
+ std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
+ m_shouldVisitChildren = (result.second && m_entry->hasChildren());
+ if (result.first) {
+ return *this;
+ }
+ else {
+ // the first child did not meet the requirement
+ // the rest of the process can just fall through the while loop as normal
+ }
+ }
+ else {
+ // no children, should return end();
+ // just fall through
+ }
+ }
+
+ // The first thing to do is to visit its child, or go to find its possible siblings
+ while (m_entry != m_subTreeRoot) {
+ if (m_shouldVisitChildren) {
+ // If this subtree should be visited
+ m_entry = m_entry->getChildren()[0];
+ std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
+ m_shouldVisitChildren = (result.second && m_entry->hasChildren());
+ if (result.first) { // if this node is acceptable
+ return *this;
+ }
+ else {
+ // do nothing, as this node is essentially ignored
+ // send this node to the while loop.
+ }
+ }
+ else {
+ // Should try to find its sibling
+ shared_ptr<Entry> parent = m_entry->getParent();
+
+ std::vector<shared_ptr<Entry>>& parentChildrenList = parent->getChildren();
+ bool isFound = false;
+ size_t i = 0;
+ for (i = 0; i < parentChildrenList.size(); ++i) {
+ if (parentChildrenList[i] == m_entry) {
+ isFound = true;
+ break;
+ }
+ }
+
+ BOOST_VERIFY(isFound == true);
+ if (i < parentChildrenList.size() - 1) { // m_entry not the last child
+ m_entry = parentChildrenList[i + 1];
+ std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
+ m_shouldVisitChildren = (result.second && m_entry->hasChildren());
+ if (result.first) { // if this node is acceptable
return *this;
+ }
+ else {
+ // do nothing, as this node is essentially ignored
+ // send this node to the while loop.
+ }
}
-
- // Reach to the end (Root)
- m_entry = m_nameTree->m_end;
- return *this;
+ else {
+ // m_entry is the last child, no more sibling, should try to find parent's sibling
+ m_shouldVisitChildren = false;
+ m_entry = parent;
+ }
+ }
}
+ m_entry = m_nameTree->m_end;
+ return *this;
+ }
+
+ if (m_type == FIND_ALL_MATCHES_TYPE) {
+ // Assumption: at the beginning, m_entry was initialized with the first
+ // eligible Name Tree entry (i.e., has a PIT entry that can be satisfied
+ // by the Data packet)
+
+ while (m_entry->getParent() != nullptr) {
+ m_entry = m_entry->getParent();
+ if ((*m_entrySelector)(*m_entry)) {
+ return *this;
+ }
+ }
+
+ // Reach to the end (Root)
+ m_entry = m_nameTree->m_end;
+ return *this;
+ }
+
BOOST_ASSERT(false); // unknown type
return *this;
}
+} // namespace name_tree
} // namespace nfd
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index b047696..460e497 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -32,49 +32,46 @@
namespace nfd {
namespace name_tree {
-/**
- * \brief Compute the hash value of the given name prefix's WIRE FORMAT
+/** \brief Compute the hash value of the given name prefix's WIRE FORMAT
*/
size_t
computeHash(const Name& prefix);
-/**
- * \brief Incrementally compute hash values
- * \return Return a vector of hash values, starting from the root prefix
+/** \brief Incrementally compute hash values
+ * \return Return a vector of hash values, starting from the root prefix
*/
std::vector<size_t>
computeHashSet(const Name& prefix);
-/// a predicate to accept or reject an Entry in find operations
-typedef function<bool (const Entry& entry)> EntrySelector;
-
-/**
- * \brief a predicate to accept or reject an Entry and its children
- * \return .first indicates whether entry should be accepted;
- * .second indicates whether entry's children should be visited
+/** \brief a predicate to accept or reject an Entry in find operations
*/
-typedef function<std::pair<bool,bool> (const Entry& entry)> EntrySubTreeSelector;
+typedef function<bool(const Entry& entry)> EntrySelector;
-struct AnyEntry {
+/** \brief a predicate to accept or reject an Entry and its children
+ * \return .first indicates whether entry should be accepted;
+ * .second indicates whether entry's children should be visited
+ */
+typedef function<std::pair<bool,bool>(const Entry& entry)> EntrySubTreeSelector;
+
+struct AnyEntry
+{
bool
- operator()(const Entry& entry)
+ operator()(const Entry& entry) const
{
return true;
}
};
-struct AnyEntrySubTree {
+struct AnyEntrySubTree
+{
std::pair<bool, bool>
- operator()(const Entry& entry)
+ operator()(const Entry& entry) const
{
- return std::make_pair(true, true);
+ return {true, true};
}
};
-} // namespace name_tree
-
-/**
- * \brief Class Name Tree
+/** \brief shared name-based index for FIB, PIT, Measurements, and StrategyChoice
*/
class NameTree : noncopyable
{
@@ -87,16 +84,15 @@
~NameTree();
public: // information
- /**
- * \brief Get the number of occupied entries in the Name Tree
+ /** \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.
+ /** \brief Get the number of buckets in the Name Tree (NPHT)
+ *
+ * The number of buckets is the one that used to create the hash
+ * table, i.e., m_nBuckets.
*/
size_t
getNBuckets() const;
@@ -104,97 +100,91 @@
/** \return Name Tree Entry on which a table entry is attached
*/
template<typename ENTRY>
- shared_ptr<name_tree::Entry>
+ shared_ptr<Entry>
getEntry(const ENTRY& tableEntry) const;
- /**
- * \brief Dump all the information stored in the Name Tree for debugging.
+ /** \brief Dump all the information stored in the Name Tree for debugging.
*/
void
dump(std::ostream& output) const;
public: // mutation
- /**
- * \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.
- * \note Existing iterators are unaffected.
+ /** \brief Look for the Name Tree Entry that contains this name prefix.
+ *
+ * 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.
+ * \note Existing iterators are unaffected.
*/
- shared_ptr<name_tree::Entry>
+ shared_ptr<Entry>
lookup(const Name& prefix);
/** \brief get NameTree entry from FIB entry
*
* This is equivalent to .lookup(fibEntry.getPrefix())
*/
- shared_ptr<name_tree::Entry>
+ shared_ptr<Entry>
lookup(const fib::Entry& fibEntry) const;
/** \brief get NameTree entry from PIT entry
*
* This is equivalent to .lookup(pitEntry.getName()).
*/
- shared_ptr<name_tree::Entry>
+ shared_ptr<Entry>
lookup(const pit::Entry& pitEntry);
/** \brief get NameTree entry from Measurements entry
*
* This is equivalent to .lookup(measurementsEntry.getName())
*/
- shared_ptr<name_tree::Entry>
+ shared_ptr<Entry>
lookup(const measurements::Entry& measurementsEntry) const;
/** \brief get NameTree entry from StrategyChoice entry
*
* This is equivalent to .lookup(strategyChoiceEntry.getName())
*/
- shared_ptr<name_tree::Entry>
+ shared_ptr<Entry>
lookup(const strategy_choice::Entry& strategyChoiceEntry) const;
- /**
- * \brief Delete a Name Tree Entry if this entry is empty.
- * \param entry The entry to be deleted if empty.
- * \note This function must be called after a table entry is detached from Name Tree
- * entry. The function deletes a Name Tree entry if nothing is attached to it and
- * it has no children, then repeats the same process on its ancestors.
- * \note Existing iterators, except those pointing to deleted entries, are unaffected.
+ /** \brief Delete a Name Tree Entry if this entry is empty.
+ * \param entry The entry to be deleted if empty.
+ * \note This function must be called after a table entry is detached from Name Tree
+ * entry. The function deletes a Name Tree entry if nothing is attached to it and
+ * it has no children, then repeats the same process on its ancestors.
+ * \note Existing iterators, except those pointing to deleted entries, are unaffected.
*/
bool
- eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry);
+ eraseEntryIfEmpty(shared_ptr<Entry> entry);
public: // matching
- /**
- * \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
+ /** \brief Exact match lookup for the given name prefix.
+ * \return nullptr if this prefix is not found; otherwise return the Name Tree Entry address
*/
- shared_ptr<name_tree::Entry>
+ shared_ptr<Entry>
findExactMatch(const Name& prefix) const;
- /**
- * \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.
+ /** \brief Longest prefix matching for the given name
+ *
+ * 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>
+ shared_ptr<Entry>
findLongestPrefixMatch(const Name& prefix,
- const name_tree::EntrySelector& entrySelector =
- name_tree::AnyEntry()) const;
+ const EntrySelector& entrySelector = AnyEntry()) const;
- shared_ptr<name_tree::Entry>
- findLongestPrefixMatch(shared_ptr<name_tree::Entry> entry,
- const name_tree::EntrySelector& entrySelector =
- name_tree::AnyEntry()) const;
+ shared_ptr<Entry>
+ findLongestPrefixMatch(shared_ptr<Entry> entry,
+ const EntrySelector& entrySelector = AnyEntry()) const;
/** \brief longest prefix matching for Interest name of the PIT entry
*
* This is equivalent to .findLongestPrefixMatch(pitEntry.getName(), AnyEntry()).
*/
- shared_ptr<name_tree::Entry>
+ shared_ptr<Entry>
findLongestPrefixMatch(const pit::Entry& pitEntry) const;
/** \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
@@ -204,7 +194,7 @@
* Example:
* \code{.cpp}
* auto&& allMatches = nt.findAllMatches(Name("/A/B/C"));
- * for (const name_tree::Entry& nte : allMatches) {
+ * for (const Entry& nte : allMatches) {
* ...
* }
* \endcode
@@ -213,7 +203,7 @@
*/
boost::iterator_range<const_iterator>
findAllMatches(const Name& prefix,
- const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
+ const EntrySelector& entrySelector = AnyEntry()) const;
public: // enumeration
/** \brief Enumerate all entries, optionally filtered by an EntrySelector.
@@ -223,7 +213,7 @@
* Example:
* \code{.cpp}
* auto&& enumerable = nt.fullEnumerate();
- * for (const name_tree::Entry& nte : enumerable) {
+ * for (const Entry& nte : enumerable) {
* ...
* }
* \endcode
@@ -231,7 +221,7 @@
* \note The returned iterator may get invalidated when NameTree is modified
*/
boost::iterator_range<const_iterator>
- fullEnumerate(const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
+ fullEnumerate(const EntrySelector& entrySelector = AnyEntry()) const;
/** \brief Enumerate all entries under a prefix, optionally filtered by an EntrySubTreeSelector.
* \return an unspecified type that have .begin() and .end() methods
@@ -240,7 +230,7 @@
* Example:
* \code{.cpp}
* auto&& enumerable = nt.partialEnumerate(Name("/A/B/C"));
- * for (const name_tree::Entry& nte : enumerable) {
+ * for (const Entry& nte : enumerable) {
* ...
* }
* \endcode
@@ -249,8 +239,7 @@
*/
boost::iterator_range<const_iterator>
partialEnumerate(const Name& prefix,
- const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
- name_tree::AnyEntrySubTree()) const;
+ const EntrySubTreeSelector& entrySubTreeSelector = AnyEntrySubTree()) const;
/** \brief Get an iterator pointing to the first NameTree entry
* \note Iteration order is implementation-specific and is undefined
@@ -272,7 +261,7 @@
FIND_ALL_MATCHES_TYPE
};
- class const_iterator : public std::iterator<std::forward_iterator_tag, const name_tree::Entry>
+ class const_iterator : public std::iterator<std::forward_iterator_tag, const Entry>
{
public:
friend class NameTree;
@@ -280,17 +269,15 @@
const_iterator();
const_iterator(NameTree::IteratorType type,
- const NameTree& nameTree,
- shared_ptr<name_tree::Entry> entry,
- const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry(),
- const name_tree::EntrySubTreeSelector& entrySubTreeSelector = name_tree::AnyEntrySubTree());
+ const NameTree& nameTree,
+ shared_ptr<Entry> entry,
+ const EntrySelector& entrySelector = AnyEntry(),
+ const EntrySubTreeSelector& entrySubTreeSelector = AnyEntrySubTree());
- ~const_iterator();
-
- const name_tree::Entry&
+ const Entry&
operator*() const;
- shared_ptr<name_tree::Entry>
+ shared_ptr<Entry>
operator->() const;
const_iterator
@@ -306,56 +293,53 @@
operator!=(const const_iterator& other) const;
private:
- const NameTree* m_nameTree;
- shared_ptr<name_tree::Entry> m_entry;
- shared_ptr<name_tree::Entry> m_subTreeRoot;
- shared_ptr<name_tree::EntrySelector> m_entrySelector;
- shared_ptr<name_tree::EntrySubTreeSelector> m_entrySubTreeSelector;
- NameTree::IteratorType m_type;
- bool m_shouldVisitChildren;
+ const NameTree* m_nameTree;
+ shared_ptr<Entry> m_entry;
+ shared_ptr<Entry> m_subTreeRoot;
+ shared_ptr<EntrySelector> m_entrySelector;
+ shared_ptr<EntrySubTreeSelector> m_entrySubTreeSelector;
+ NameTree::IteratorType m_type;
+ bool m_shouldVisitChildren;
};
private:
- /**
- * \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).
+ /** \brief Create a Name Tree Entry if it does not exist, or return the existing
+ * Name Tree Entry address.
+ *
+ * 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>
+ std::pair<shared_ptr<Entry>, bool>
insert(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.
+ /** \brief Resize the hash table size when its load factor reaches a threshold.
+ *
+ * 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);
private:
- size_t m_nItems; // Number of items being stored
- size_t m_nBuckets; // Number of hash buckets
- size_t m_minNBuckets; // Minimum number of hash buckets
- double m_enlargeLoadFactor;
- size_t m_enlargeThreshold;
- int m_enlargeFactor;
- double m_shrinkLoadFactor;
- size_t m_shrinkThreshold;
- double m_shrinkFactor;
- name_tree::Node** m_buckets; // Name Tree Buckets in the NPHT
- shared_ptr<name_tree::Entry> m_end;
- const_iterator m_endIterator;
+ size_t m_nItems; ///< Number of items being stored
+ size_t m_nBuckets; ///< Number of hash buckets
+ size_t m_minNBuckets; ///< Minimum number of hash buckets
+ double m_enlargeLoadFactor;
+ size_t m_enlargeThreshold;
+ int m_enlargeFactor;
+ double m_shrinkLoadFactor;
+ size_t m_shrinkThreshold;
+ double m_shrinkFactor;
+ Node** m_buckets; ///< Name Tree Buckets in the NPHT
+ shared_ptr<Entry> m_end;
+ const_iterator m_endIterator;
};
-inline NameTree::const_iterator::~const_iterator()
-{
-}
-
inline size_t
NameTree::size() const
{
@@ -369,7 +353,7 @@
}
template<typename ENTRY>
-inline shared_ptr<name_tree::Entry>
+inline shared_ptr<Entry>
NameTree::getEntry(const ENTRY& tableEntry) const
{
return tableEntry.m_nameTreeEntry.lock();
@@ -387,13 +371,13 @@
return m_endIterator;
}
-inline const name_tree::Entry&
+inline const Entry&
NameTree::const_iterator::operator*() const
{
return *m_entry;
}
-inline shared_ptr<name_tree::Entry>
+inline shared_ptr<Entry>
NameTree::const_iterator::operator->() const
{
return m_entry;
@@ -419,6 +403,10 @@
return m_entry != other.m_entry;
}
+} // namespace name_tree
+
+using name_tree::NameTree;
+
} // namespace nfd
#endif // NFD_DAEMON_TABLE_NAME_TREE_HPP
diff --git a/daemon/table/pit-entry.hpp b/daemon/table/pit-entry.hpp
index 282d1df..5f77a4d 100644
--- a/daemon/table/pit-entry.hpp
+++ b/daemon/table/pit-entry.hpp
@@ -32,11 +32,11 @@
namespace nfd {
-class NameTree;
-
namespace name_tree {
+class NameTree;
class Entry;
} // namespace name_tree
+using name_tree::NameTree;
namespace pit {
diff --git a/daemon/table/strategy-choice-entry.hpp b/daemon/table/strategy-choice-entry.hpp
index 9261039..e02a5ab 100644
--- a/daemon/table/strategy-choice-entry.hpp
+++ b/daemon/table/strategy-choice-entry.hpp
@@ -30,13 +30,14 @@
namespace nfd {
-class NameTree;
-namespace name_tree {
-class Entry;
-} // namespace name_tree
namespace fw {
class Strategy;
} // namespace fw
+namespace name_tree {
+class NameTree;
+class Entry;
+} // namespace name_tree
+using name_tree::NameTree;
namespace strategy_choice {
diff --git a/tests/daemon/table/name-tree.t.cpp b/tests/daemon/table/name-tree.t.cpp
index a79e2d5..394f4d1 100644
--- a/tests/daemon/table/name-tree.t.cpp
+++ b/tests/daemon/table/name-tree.t.cpp
@@ -24,61 +24,62 @@
*/
#include "table/name-tree.hpp"
-#include <unordered_set>
#include "tests/test-common.hpp"
namespace nfd {
+namespace name_tree {
namespace tests {
-using name_tree::Entry;
+using namespace nfd::tests;
-BOOST_FIXTURE_TEST_SUITE(TableNameTree, BaseFixture)
+BOOST_AUTO_TEST_SUITE(Table)
+BOOST_FIXTURE_TEST_SUITE(TestNameTree, 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));
+ size_t hashValue = computeHash(root);
+ BOOST_CHECK_EQUAL(hashValue, 0);
Name prefix("/nohello/world/ndn/research");
prefix.wireEncode();
- std::vector<size_t> hashSet = name_tree::computeHashSet(prefix);
+ std::vector<size_t> hashSet = computeHashSet(prefix);
BOOST_CHECK_EQUAL(hashSet.size(), prefix.size() + 1);
}
-BOOST_AUTO_TEST_CASE(Entry)
+BOOST_AUTO_TEST_CASE(NameTreeEntry)
{
Name prefix("ndn:/named-data/research/abc/def/ghi");
- shared_ptr<name_tree::Entry> npe = make_shared<name_tree::Entry>(prefix);
+ auto npe = make_shared<Entry>(prefix);
BOOST_CHECK_EQUAL(npe->getPrefix(), prefix);
// examine all the get methods
size_t hash = npe->getHash();
- BOOST_CHECK_EQUAL(hash, static_cast<size_t>(0));
+ BOOST_CHECK_EQUAL(hash, 0);
- shared_ptr<name_tree::Entry> parent = npe->getParent();
- BOOST_CHECK(!static_cast<bool>(parent));
+ shared_ptr<Entry> parent = npe->getParent();
+ BOOST_CHECK(parent == nullptr);
- std::vector<shared_ptr<name_tree::Entry> >& childList = npe->getChildren();
- BOOST_CHECK_EQUAL(childList.size(), static_cast<size_t>(0));
+ std::vector<shared_ptr<Entry>>& childList = npe->getChildren();
+ BOOST_CHECK_EQUAL(childList.size(), 0);
fib::Entry* fib = npe->getFibEntry();
BOOST_CHECK(fib == nullptr);
- const std::vector< shared_ptr<pit::Entry> >& pitList = npe->getPitEntries();
- BOOST_CHECK_EQUAL(pitList.size(), static_cast<size_t>(0));
+ const std::vector<shared_ptr<pit::Entry>>& pitList = npe->getPitEntries();
+ BOOST_CHECK_EQUAL(pitList.size(), 0);
// examine all the set method
- npe->setHash(static_cast<size_t>(12345));
- BOOST_CHECK_EQUAL(npe->getHash(), static_cast<size_t>(12345));
+ npe->setHash(12345);
+ BOOST_CHECK_EQUAL(npe->getHash(), 12345);
Name parentName("ndn:/named-data/research/abc/def");
- parent = make_shared<name_tree::Entry>(parentName);
+ parent = make_shared<Entry>(parentName);
npe->setParent(parent);
BOOST_CHECK_EQUAL(npe->getParent(), parent);
@@ -93,8 +94,8 @@
// Insert a PIT
- shared_ptr<pit::Entry> pitEntry(make_shared<pit::Entry>(*makeInterest(prefix)));
- shared_ptr<pit::Entry> pitEntry2(make_shared<pit::Entry>(*makeInterest(parentName)));
+ auto pitEntry = make_shared<pit::Entry>(*makeInterest(prefix));
+ auto pitEntry2 = make_shared<pit::Entry>(*makeInterest(parentName));
npe->insertPitEntry(pitEntry);
BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
@@ -118,19 +119,19 @@
BOOST_CHECK_EQUAL(nt.getNBuckets(), nBuckets);
Name nameABC("ndn:/a/b/c");
- shared_ptr<name_tree::Entry> npeABC = nt.lookup(nameABC);
+ shared_ptr<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);
+ shared_ptr<Entry> npeABD = nt.lookup(nameABD);
BOOST_CHECK_EQUAL(nt.size(), 5);
Name nameAE("/a/e/");
- shared_ptr<name_tree::Entry> npeAE = nt.lookup(nameAE);
+ shared_ptr<Entry> npeAE = nt.lookup(nameAE);
BOOST_CHECK_EQUAL(nt.size(), 6);
Name nameF("/f");
- shared_ptr<name_tree::Entry> npeF = nt.lookup(nameF);
+ shared_ptr<Entry> npeF = nt.lookup(nameF);
BOOST_CHECK_EQUAL(nt.size(), 7);
// validate lookup() and findExactMatch()
@@ -147,12 +148,12 @@
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));
+ shared_ptr<Entry> npe0 = nt.findExactMatch(name0);
+ BOOST_CHECK(npe0 == nullptr);
// Longest Prefix Matching
- shared_ptr<name_tree::Entry> temp;
+ shared_ptr<Entry> temp;
Name nameABCLPM("/a/b/c/def/asdf/nlf");
temp = nt.findLongestPrefixMatch(nameABCLPM);
BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABC));
@@ -183,19 +184,17 @@
bool eraseResult = false;
temp = nt.findExactMatch(nameABC);
- if (static_cast<bool>(temp))
- eraseResult = nt.
- eraseEntryIfEmpty(temp);
+ if (temp != nullptr)
+ eraseResult = nt.eraseEntryIfEmpty(temp);
BOOST_CHECK_EQUAL(nt.size(), 6);
- BOOST_CHECK(!static_cast<bool>(nt.findExactMatch(nameABC)));
+ BOOST_CHECK(nt.findExactMatch(nameABC) == nullptr);
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));
+ if (temp != nullptr)
+ eraseResult = nt.eraseEntryIfEmpty(temp);
+ BOOST_CHECK(temp == nullptr);
BOOST_CHECK_EQUAL(nt.size(), 6);
BOOST_CHECK_EQUAL(eraseResult, false);
@@ -206,12 +205,11 @@
eraseResult = false;
temp = nt.findExactMatch(nameABC);
- if (static_cast<bool>(temp))
- eraseResult = nt.
- eraseEntryIfEmpty(temp);
+ if (temp != nullptr)
+ eraseResult = nt.eraseEntryIfEmpty(temp);
BOOST_CHECK_EQUAL(nt.size(), 6);
BOOST_CHECK_EQUAL(eraseResult, true);
- BOOST_CHECK(!static_cast<bool>(nt.findExactMatch(nameABC)));
+ BOOST_CHECK(nt.findExactMatch(nameABC) == nullptr);
BOOST_CHECK_EQUAL(nt.getNBuckets(), 16);
@@ -226,16 +224,14 @@
// try to erase /a/b/c, should return false
temp = nt.findExactMatch(nameABC);
BOOST_CHECK_EQUAL(temp->getPrefix(), nameABC);
- eraseResult = nt.
- eraseEntryIfEmpty(temp);
+ 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);
+ if (temp != nullptr)
+ nt.eraseEntryIfEmpty(temp);
BOOST_CHECK_EQUAL(nt.size(), 8);
}
@@ -257,7 +253,7 @@
template<typename Enumerable>
EnumerationVerifier(Enumerable&& enumerable)
{
- for (const name_tree::Entry& entry : enumerable) {
+ for (const Entry& entry : enumerable) {
const Name& name = entry.getPrefix();
BOOST_CHECK_MESSAGE(m_names.insert(name).second, "duplicate Name " << name);
}
@@ -314,6 +310,7 @@
static const size_t N_BUCKETS = 16;
NameTree nt;
};
+
const size_t EnumerationFixture::N_BUCKETS;
BOOST_FIXTURE_TEST_CASE(IteratorFullEnumerate, EnumerationFixture)
@@ -372,7 +369,7 @@
this->insertAbAc();
// Accept "root" nameA only
- auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
return std::make_pair(entry.getPrefix() == "/a", true);
});
@@ -386,7 +383,7 @@
this->insertAbAc();
// Accept anything except "root" nameA
- auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
return std::make_pair(entry.getPrefix() != "/a", true);
});
@@ -402,7 +399,7 @@
// No NameA
// No SubTree from NameAB
- auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
return std::make_pair(entry.getPrefix() != "/a", entry.getPrefix() != "/a/b");
});
@@ -420,7 +417,7 @@
// No NameA
// No SubTree from NameAC
- auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
return std::make_pair(entry.getPrefix() != "/a", entry.getPrefix() != "/a/c");
});
@@ -437,7 +434,7 @@
this->insertAb1Ab2Ac1Ac2();
// No Subtree from NameA
- auto&& enumerable = nt.partialEnumerate("/a", [] (const name_tree::Entry& entry) {
+ auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
return std::make_pair(true, entry.getPrefix() != "/a");
});
@@ -465,7 +462,7 @@
nt.lookup("/F");
auto&& enumerable = nt.partialEnumerate("/A",
- [] (const name_tree::Entry& entry) -> std::pair<bool, bool> {
+ [] (const Entry& entry) -> std::pair<bool, bool> {
bool visitEntry = false;
bool visitChildren = false;
@@ -517,7 +514,7 @@
Name prefix("/a/b/c/d/e/f/g/h"); // requires 9 buckets
- shared_ptr<name_tree::Entry> entry = nameTree.lookup(prefix);
+ shared_ptr<Entry> entry = nameTree.lookup(prefix);
BOOST_CHECK_EQUAL(nameTree.size(), 9);
BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 32);
@@ -583,7 +580,9 @@
BOOST_CHECK(seenNames.size() == 7);
}
-BOOST_AUTO_TEST_SUITE_END()
+BOOST_AUTO_TEST_SUITE_END() // TestNameTree
+BOOST_AUTO_TEST_SUITE_END() // Table
} // namespace tests
+} // namespace name_tree
} // namespace nfd