NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
nfd::NameTree Class Reference

Class Name Tree. More...

#include <name-tree.hpp>

Inheritance diagram for nfd::NameTree:
Collaboration diagram for nfd::NameTree:

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::Entrylookup (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::Entryget (const fib::Entry &fibEntry) const
 get NameTree entry from attached FIB entry More...
 
shared_ptr< name_tree::Entryget (const pit::Entry &pitEntry) const
 get NameTree entry from attached PIT entry More...
 
shared_ptr< name_tree::Entryget (const measurements::Entry &measurementsEntry) const
 get NameTree entry from attached Measurements entry More...
 
shared_ptr< name_tree::Entryget (const strategy_choice::Entry &strategyChoiceEntry) const
 get NameTree entry from attached StrategyChoice entry More...
 
shared_ptr< name_tree::EntryfindExactMatch (const Name &prefix) const
 Exact match lookup for the given name prefix. More...
 
shared_ptr< name_tree::EntryfindLongestPrefixMatch (const Name &prefix, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
 Longest prefix matching for the given name. More...
 
shared_ptr< name_tree::EntryfindLongestPrefixMatch (shared_ptr< name_tree::Entry > entry, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
 
boost::iterator_range< const_iteratorfindAllMatches (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_iteratorfullEnumerate (const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
 Enumerate all entries, optionally filtered by an EntrySelector. More...
 
boost::iterator_range< const_iteratorpartialEnumerate (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...
 

Detailed Description

Class Name Tree.

Definition at line 79 of file name-tree.hpp.

Member Enumeration Documentation

◆ IteratorType

Enumerator
FULL_ENUMERATE_TYPE 
PARTIAL_ENUMERATE_TYPE 
FIND_ALL_MATCHES_TYPE 

Definition at line 245 of file name-tree.hpp.

Constructor & Destructor Documentation

◆ NameTree()

nfd::NameTree::NameTree ( size_t  nBuckets = 1024)
explicit

Definition at line 116 of file name-tree.cpp.

◆ ~NameTree()

nfd::NameTree::~NameTree ( )

Definition at line 139 of file name-tree.cpp.

Member Function Documentation

◆ size()

size_t nfd::NameTree::size ( ) const
inline

Get the number of occupied entries in the Name Tree.

Definition at line 336 of file name-tree.hpp.

Referenced by eraseEntryIfEmpty().

◆ getNBuckets()

size_t nfd::NameTree::getNBuckets ( ) const
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.

◆ dump()

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.

◆ lookup()

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.

Parameters
prefixThe querying name prefix.
Returns
The pointer to the Name Tree Entry that contains this full name prefix.
Note
Existing iterators are unaffected.

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().

◆ eraseEntryIfEmpty()

bool nfd::NameTree::eraseEntryIfEmpty ( shared_ptr< name_tree::Entry entry)

Delete a Name Tree Entry if this entry is empty.

Parameters
entryThe 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.
Existing iterators, except those pointing to deleted entries, are unaffected.

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().

◆ get() [1/4]

◆ get() [2/4]

shared_ptr< name_tree::Entry > nfd::NameTree::get ( const pit::Entry pitEntry) const
inline

get NameTree entry from attached PIT entry

Definition at line 354 of file name-tree.hpp.

◆ get() [3/4]

shared_ptr< name_tree::Entry > nfd::NameTree::get ( const measurements::Entry measurementsEntry) const
inline

get NameTree entry from attached Measurements entry

Definition at line 360 of file name-tree.hpp.

◆ get() [4/4]

shared_ptr< name_tree::Entry > nfd::NameTree::get ( const strategy_choice::Entry strategyChoiceEntry) const
inline

get NameTree entry from attached StrategyChoice entry

Definition at line 366 of file name-tree.hpp.

◆ findExactMatch()

shared_ptr< name_tree::Entry > nfd::NameTree::findExactMatch ( const Name prefix) const

Exact match lookup for the given name prefix.

Returns
a null shared_ptr if this prefix is not found; otherwise return the Name Tree Entry address

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().

◆ findLongestPrefixMatch() [1/2]

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().

◆ findLongestPrefixMatch() [2/2]

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.

◆ findAllMatches()

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.

Returns
an unspecified type that have .begin() and .end() methods and is usable with range-based for

Example:

auto&& allMatches = nt.findAllMatches(Name("/A/B/C"));
for (const name_tree::Entry& nte : allMatches) {
...
}
Note
Iteration order is implementation-specific and is undefined
The returned iterator may get invalidated when NameTree is modified

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().

◆ fullEnumerate()

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.

Returns
an unspecified type that have .begin() and .end() methods and is usable with range-based for

Example:

auto&& enumerable = nt.fullEnumerate();
for (const name_tree::Entry& nte : enumerable) {
...
}
Note
Iteration order is implementation-specific and is undefined
The returned iterator may get invalidated when NameTree is modified

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().

◆ partialEnumerate()

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.

Returns
an unspecified type that have .begin() and .end() methods and is usable with range-based for

Example:

auto&& enumerable = nt.partialEnumerate(Name("/A/B/C"));
for (const name_tree::Entry& nte : enumerable) {
...
}
Note
Iteration order is implementation-specific and is undefined
The returned iterator may get invalidated when NameTree is modified

Definition at line 425 of file name-tree.cpp.

References end(), findExactMatch(), and PARTIAL_ENUMERATE_TYPE.

◆ begin()

NameTree::const_iterator nfd::NameTree::begin ( ) const
inline

Get an iterator pointing to the first NameTree entry.

Note
Iteration order is implementation-specific and is undefined
The returned iterator may get invalidated when NameTree is modified

Definition at line 372 of file name-tree.hpp.

References fullEnumerate().

Referenced by findAllMatches().

◆ end()

NameTree::const_iterator nfd::NameTree::end ( ) const
inline

Get an iterator referring to the past-the-end FIB entry.

Note
Iteration order is implementation-specific and is undefined
The returned iterator may get invalidated when NameTree is modified

Definition at line 378 of file name-tree.hpp.

Referenced by nfd::Pit::end(), nfd::Fib::end(), nfd::StrategyChoice::end(), findAllMatches(), fullEnumerate(), and partialEnumerate().


The documentation for this class was generated from the following files: