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

Detailed Description

Class Name Tree.

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

Member Enumeration Documentation

enum nfd::NameTree::IteratorType

Enumerator
FULL_ENUMERATE_TYPE
PARTIAL_ENUMERATE_TYPE
FIND_ALL_MATCHES_TYPE

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

Constructor & Destructor Documentation

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

explicit

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

nfd::NameTree::~NameTree ( )

Definition at line 139 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_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(), and nfd::StatusServer::StatusServer().

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.

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.

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

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

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

inline

get NameTree entry from attached FIB entry

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

Referenced by nfd::clearStrategyInfo(), 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().

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.

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.

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.

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

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.

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(), nfd::name_tree::Node::m_entry, nfd::name_tree::Node::m_next, nfd::name_tree::Node::m_prev, 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.

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_next, and NFD_LOG_TRACE.

Referenced by nfd::Pit::begin(), nfd::Fib::begin(), nfd::StrategyChoice::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.

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.

Referenced by nfd::clearStrategyInfo().

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.

Referenced by findAllMatches().

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

Constructor & Destructor Documentation

Member Function Documentation