Class Name Tree. More...
#include <name-tree.hpp>
Classes | |
class | const_iterator |
Public Types | |
enum | IteratorType { FULL_ENUMERATE_TYPE, PARTIAL_ENUMERATE_TYPE, FIND_ALL_MATCHES_TYPE } |
Public Member Functions | |
NameTree (size_t nBuckets=1024) | |
~NameTree () | |
size_t | size () const |
Get the number of occupied entries in the Name Tree. More... | |
size_t | getNBuckets () const |
Get the number of buckets in the Name Tree (NPHT) More... | |
void | dump (std::ostream &output) const |
Dump all the information stored in the Name Tree for debugging. More... | |
shared_ptr< name_tree::Entry > | lookup (const Name &prefix) |
Look for the Name Tree Entry that contains this name prefix. More... | |
bool | eraseEntryIfEmpty (shared_ptr< name_tree::Entry > entry) |
Delete a Name Tree Entry if this entry is empty. More... | |
shared_ptr< name_tree::Entry > | get (const fib::Entry &fibEntry) const |
get NameTree entry from attached FIB entry More... | |
shared_ptr< name_tree::Entry > | get (const pit::Entry &pitEntry) const |
get NameTree entry from attached PIT entry More... | |
shared_ptr< name_tree::Entry > | get (const measurements::Entry &measurementsEntry) const |
get NameTree entry from attached Measurements entry More... | |
shared_ptr< name_tree::Entry > | get (const strategy_choice::Entry &strategyChoiceEntry) const |
get NameTree entry from attached StrategyChoice entry More... | |
shared_ptr< name_tree::Entry > | findExactMatch (const Name &prefix) const |
Exact match lookup for the given name prefix. More... | |
shared_ptr< name_tree::Entry > | findLongestPrefixMatch (const Name &prefix, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const |
Longest prefix matching for the given name. More... | |
shared_ptr< name_tree::Entry > | findLongestPrefixMatch (shared_ptr< name_tree::Entry > entry, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const |
boost::iterator_range< const_iterator > | findAllMatches (const Name &prefix, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const |
Enumerate all the name prefixes that satisfy the prefix and entrySelector. More... | |
boost::iterator_range< const_iterator > | fullEnumerate (const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const |
Enumerate all entries, optionally filtered by an EntrySelector. More... | |
boost::iterator_range< const_iterator > | partialEnumerate (const Name &prefix, const name_tree::EntrySubTreeSelector &entrySubTreeSelector=name_tree::AnyEntrySubTree()) const |
Enumerate all entries under a prefix, optionally filtered by an EntrySubTreeSelector. More... | |
const_iterator | begin () const |
Get an iterator pointing to the first NameTree entry. More... | |
const_iterator | end () const |
Get an iterator referring to the past-the-end FIB entry. More... | |
Class Name Tree.
Definition at line 79 of file name-tree.hpp.
Enumerator | |
---|---|
FULL_ENUMERATE_TYPE | |
PARTIAL_ENUMERATE_TYPE | |
FIND_ALL_MATCHES_TYPE |
Definition at line 245 of file name-tree.hpp.
|
explicit |
Definition at line 116 of file name-tree.cpp.
nfd::NameTree::~NameTree | ( | ) |
Definition at line 139 of file name-tree.cpp.
|
inline |
Get the number of occupied entries in the Name Tree.
Definition at line 336 of file name-tree.hpp.
Referenced by eraseEntryIfEmpty().
|
inline |
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.
Definition at line 342 of file name-tree.hpp.
void nfd::NameTree::dump | ( | std::ostream & | output | ) | const |
Dump all the information stored in the Name Tree for debugging.
Definition at line 535 of file name-tree.cpp.
References nfd::name_tree::Node::m_entry, nfd::name_tree::Node::m_next, and NFD_LOG_TRACE.
shared_ptr< name_tree::Entry > nfd::NameTree::lookup | ( | const Name & | prefix | ) |
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.
prefix | The querying name prefix. |
Definition at line 205 of file name-tree.cpp.
References ndn::Name::getPrefix(), NFD_LOG_TRACE, and ndn::Name::size().
Referenced by nfd::Measurements::findExactMatch(), nfd::Measurements::get(), nfd::Pit::insert(), nfd::StrategyChoice::insert(), and nfd::Fib::insert().
bool nfd::NameTree::eraseEntryIfEmpty | ( | shared_ptr< name_tree::Entry > | entry | ) |
Delete a Name Tree Entry if this entry is empty.
entry | The entry to be deleted if empty. |
Definition at line 327 of file name-tree.cpp.
References nfd::name_tree::Node::m_next, nfd::name_tree::Node::m_prev, NFD_LOG_TRACE, and size().
Referenced by nfd::Pit::erase(), and nfd::StrategyChoice::erase().
|
inline |
get NameTree entry from attached FIB entry
Definition at line 348 of file name-tree.hpp.
Referenced by nfd::Pit::erase(), nfd::Fib::erase(), nfd::Measurements::extendLifetime(), nfd::StrategyChoice::findEffectiveStrategy(), nfd::Fib::findLongestPrefixMatch(), nfd::Measurements::findLongestPrefixMatch(), nfd::Measurements::get(), and nfd::Measurements::getParent().
|
inline |
get NameTree entry from attached PIT entry
Definition at line 354 of file name-tree.hpp.
|
inline |
get NameTree entry from attached Measurements entry
Definition at line 360 of file name-tree.hpp.
|
inline |
get NameTree entry from attached StrategyChoice entry
Definition at line 366 of file name-tree.hpp.
shared_ptr< name_tree::Entry > nfd::NameTree::findExactMatch | ( | const Name & | prefix | ) | const |
Exact match lookup for the given name prefix.
Definition at line 243 of file name-tree.cpp.
References nfd::name_tree::computeHash(), ndn::Name::getPrefix(), nfd::name_tree::Node::m_entry, nfd::name_tree::Node::m_next, and NFD_LOG_TRACE.
Referenced by nfd::Fib::erase(), nfd::StrategyChoice::erase(), nfd::Fib::findExactMatch(), nfd::StrategyChoice::get(), and partialEnumerate().
shared_ptr< name_tree::Entry > nfd::NameTree::findLongestPrefixMatch | ( | const Name & | prefix, |
const name_tree::EntrySelector & | entrySelector = name_tree::AnyEntry() |
||
) | const |
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.
Definition at line 275 of file name-tree.cpp.
References nfd::name_tree::computeHashSet(), nfd::name_tree::Node::m_entry, nfd::name_tree::Node::m_next, NFD_LOG_TRACE, and ndn::Name::size().
Referenced by findAllMatches(), nfd::StrategyChoice::findEffectiveStrategy(), nfd::Fib::findLongestPrefixMatch(), and nfd::Measurements::findLongestPrefixMatchImpl().
shared_ptr< name_tree::Entry > nfd::NameTree::findLongestPrefixMatch | ( | shared_ptr< name_tree::Entry > | entry, |
const name_tree::EntrySelector & | entrySelector = name_tree::AnyEntry() |
||
) | const |
Definition at line 313 of file name-tree.cpp.
boost::iterator_range< NameTree::const_iterator > nfd::NameTree::findAllMatches | ( | const Name & | prefix, |
const name_tree::EntrySelector & | entrySelector = name_tree::AnyEntry() |
||
) | const |
Enumerate all the name prefixes that satisfy the prefix and entrySelector.
Example:
Definition at line 454 of file name-tree.cpp.
References begin(), end(), FIND_ALL_MATCHES_TYPE, findLongestPrefixMatch(), and NFD_LOG_TRACE.
Referenced by nfd::Pit::findAllDataMatches().
boost::iterator_range< NameTree::const_iterator > nfd::NameTree::fullEnumerate | ( | const name_tree::EntrySelector & | entrySelector = name_tree::AnyEntry() | ) | const |
Enumerate all entries, optionally filtered by an EntrySelector.
Example:
Definition at line 406 of file name-tree.cpp.
References end(), FULL_ENUMERATE_TYPE, nfd::name_tree::Node::m_entry, nfd::name_tree::Node::m_next, and NFD_LOG_TRACE.
Referenced by nfd::Pit::begin(), nfd::Fib::begin(), nfd::StrategyChoice::begin(), begin(), and nfd::Fib::removeNextHopFromAllEntries().
boost::iterator_range< NameTree::const_iterator > nfd::NameTree::partialEnumerate | ( | const Name & | prefix, |
const name_tree::EntrySubTreeSelector & | entrySubTreeSelector = name_tree::AnyEntrySubTree() |
||
) | const |
Enumerate all entries under a prefix, optionally filtered by an EntrySubTreeSelector.
Example:
Definition at line 425 of file name-tree.cpp.
References end(), findExactMatch(), and PARTIAL_ENUMERATE_TYPE.
|
inline |
Get an iterator pointing to the first NameTree entry.
Definition at line 372 of file name-tree.hpp.
References fullEnumerate().
Referenced by findAllMatches().
|
inline |
Get an iterator referring to the past-the-end FIB entry.
Definition at line 378 of file name-tree.hpp.
Referenced by nfd::Pit::end(), nfd::Fib::end(), nfd::StrategyChoice::end(), findAllMatches(), fullEnumerate(), and partialEnumerate().