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::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 FIB entry More...

shared_ptr< name_tree::Entry >	get (const pit::Entry &pitEntry)
	get NameTree entry from PIT entry More...

shared_ptr< name_tree::Entry >	get (const measurements::Entry &measurementsEntry) const
	get NameTree entry from Measurements entry More...

shared_ptr< name_tree::Entry >	get (const strategy_choice::Entry &strategyChoiceEntry) const
	get NameTree entry from 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

shared_ptr< name_tree::Entry >	findLongestPrefixMatch (const pit::Entry &pitEntry) const
	longest prefix matching for Interest name of the PIT entry More...

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

Detailed Description

Class Name Tree.

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

Member Enumeration Documentation

§ IteratorType

enum nfd::NameTree::IteratorType

Enumerator
FULL_ENUMERATE_TYPE
PARTIAL_ENUMERATE_TYPE
FIND_ALL_MATCHES_TYPE

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

Constructor & Destructor Documentation

§ NameTree()

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

explicit

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

§ ~NameTree()

nfd::NameTree::~NameTree ( )

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

References nfd::name_tree::computeHash(), nfd::name_tree::Node::m_entry, nfd::name_tree::Node::m_next, nfd::name_tree::Node::m_prev, and NFD_LOG_TRACE.

Member Function Documentation

§ size()

size_t nfd::NameTree::size ( ) const

inline

Get the number of occupied entries in the Name Tree.

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

Referenced by eraseEntryIfEmpty(), and nfd::ForwarderStatusManager::ForwarderStatusManager().

§ 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 361 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 568 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

prefix The 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 207 of file name-tree.cpp.

References ndn::Name::getPrefix(), NFD_LOG_TRACE, and ndn::Name::size().

Referenced by nfd::StrategyChoice::findEffectiveStrategy(), nfd::Measurements::findExactMatch(), nfd::Measurements::get(), get(), nfd::Fib::insert(), nfd::StrategyChoice::insert(), and nfd::Pit::Pit().

§ eraseEntryIfEmpty()

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

Delete a Name Tree Entry if this entry is empty.

Parameters

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

Definition at line 245 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(), nfd::StrategyChoice::erase(), nfd::Measurements::extendLifetime(), and nfd::Fib::insert().

§ get() [1/4]

shared_ptr< name_tree::Entry > nfd::NameTree::get ( const fib::Entry & fibEntry ) const

inline

get NameTree entry from FIB entry

This is equivalent to .lookup(fibEntry.getPrefix())

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

Referenced by nfd::clearStrategyInfo(), nfd::Fib::erase(), nfd::Measurements::extendLifetime(), nfd::StrategyChoice::findEffectiveStrategy(), nfd::Fib::findLongestPrefixMatch(), nfd::Measurements::findLongestPrefixMatch(), nfd::Measurements::get(), and nfd::Measurements::getParent().

§ get() [2/4]

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

get NameTree entry from PIT entry

This is equivalent to .lookup(pitEntry.getName()).

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

References ndn::Name::at(), nfd::pit::Entry::getName(), ndn::Name::getPrefix(), ndn::name::Component::isImplicitSha256Digest(), lookup(), and ndn::Name::size().

§ get() [3/4]

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

inline

get NameTree entry from Measurements entry

This is equivalent to .lookup(measurementsEntry.getName())

Definition at line 373 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 StrategyChoice entry

This is equivalent to .lookup(strategyChoiceEntry.getName())

Definition at line 379 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 342 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(), findLongestPrefixMatch(), nfd::StrategyChoice::get(), and partialEnumerate().

§ findLongestPrefixMatch() [1/3]

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 374 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/3]

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 412 of file name-tree.cpp.

§ findLongestPrefixMatch() [3/3]

shared_ptr< name_tree::Entry > nfd::NameTree::findLongestPrefixMatch ( const pit::Entry & pitEntry ) const

longest prefix matching for Interest name of the PIT entry

This is equivalent to .findLongestPrefixMatch(pitEntry.getName(), AnyEntry()).

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

References ndn::Name::at(), findExactMatch(), nfd::pit::Entry::getName(), ndn::Name::getPrefix(), ndn::name::Component::isImplicitSha256Digest(), and ndn::Name::size().

§ 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 439 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 461 of file name-tree.cpp.

References end(), FULL_ENUMERATE_TYPE, nfd::name_tree::Node::m_next, and NFD_LOG_TRACE.

Referenced by nfd::Pit::begin(), nfd::Fib::begin(), nfd::StrategyChoice::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 480 of file name-tree.cpp.

References end(), findExactMatch(), nfd::name_tree::Node::m_entry, nfd::name_tree::Node::m_next, nfd::name_tree::Node::m_prev, NFD_LOG_TRACE, and PARTIAL_ENUMERATE_TYPE.

Referenced by nfd::clearStrategyInfo().

§ 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 385 of file name-tree.hpp.

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 391 of file name-tree.hpp.

Referenced by findAllMatches(), fullEnumerate(), and partialEnumerate().

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

ndnSIM/NFD/daemon/table/name-tree.hpp
ndnSIM/NFD/daemon/table/name-tree.cpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

§ IteratorType

Constructor & Destructor Documentation

§ NameTree()

§ ~NameTree()

Member Function Documentation

§ size()

§ getNBuckets()

§ dump()

§ lookup()

§ eraseEntryIfEmpty()

§ get() [1/4]

§ get() [2/4]

§ get() [3/4]

§ get() [4/4]

§ findExactMatch()

§ findLongestPrefixMatch() [1/3]

§ findLongestPrefixMatch() [2/3]

§ findLongestPrefixMatch() [3/3]

§ findAllMatches()

§ fullEnumerate()

§ partialEnumerate()

§ begin()

§ end()