a common index structure for FIB, PIT, StrategyChoice, and Measurements More...

#include <name-tree.hpp>

Inheritance diagram for nfd::name_tree::NameTree:

Collaboration diagram for nfd::name_tree::NameTree:

Public Types
typedef Iterator	const_iterator

Public Member Functions
	NameTree (size_t nBuckets=1024)

size_t	size () const

size_t	getNBuckets () const

template<typename ENTRY >
Entry *	getEntry (const ENTRY &tableEntry) const

Entry &	lookup (const Name &name)
	find or insert an entry with specified name More...

Entry &	lookup (const fib::Entry &fibEntry)
	equivalent to .lookup(fibEntry.getPrefix()) More...

Entry &	lookup (const pit::Entry &pitEntry)
	equivalent to .lookup(pitEntry.getName()). More...

Entry &	lookup (const measurements::Entry &measurementsEntry)
	equivalent to .lookup(measurementsEntry.getName()) More...

Entry &	lookup (const strategy_choice::Entry &strategyChoiceEntry)
	equivalent to .lookup(strategyChoiceEntry.getPrefix()) More...

size_t	eraseIfEmpty (Entry *entry, bool canEraseAncestors=true)
	delete the entry if it is empty More...

Entry *	findExactMatch (const Name &name) const
	exact match lookup More...

Entry *	findLongestPrefixMatch (const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
	longest prefix matching More...

Entry *	findLongestPrefixMatch (const Entry &entry, const EntrySelector &entrySelector=AnyEntry()) const
	equivalent to .findLongestPrefixMatch(entry.getName(), entrySelector) More...

template<typename ENTRY >
Entry *	findLongestPrefixMatch (const ENTRY &tableEntry, const EntrySelector &entrySelector=AnyEntry()) const
	equivalent to .findLongestPrefixMatch(getEntry(tableEntry)->getName(), entrySelector) More...

Entry *	findLongestPrefixMatch (const pit::Entry &pitEntry, const EntrySelector &entrySelector=AnyEntry()) const
	equivalent to .findLongestPrefixMatch(pitEntry.getName(), entrySelector) More...

Range	findAllMatches (const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
	all-prefixes match lookup More...

Range	fullEnumerate (const EntrySelector &entrySelector=AnyEntry()) const
	enumerate all entries More...

Range	partialEnumerate (const Name &prefix, const EntrySubTreeSelector &entrySubTreeSelector=AnyEntrySubTree()) const
	enumerate all entries under a prefix More...

const_iterator	begin () const

const_iterator	end () const

Friends
class	EnumerationImpl

Detailed Description

a common index structure for FIB, PIT, StrategyChoice, and Measurements

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

Member Typedef Documentation

◆ const_iterator

typedef Iterator nfd::name_tree::NameTree::const_iterator

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

Constructor & Destructor Documentation

◆ NameTree()

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

explicit

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

Member Function Documentation

◆ size()

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

inline

Returns: number of name tree entries

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

References nfd::name_tree::Hashtable::size().

Referenced by nfd::ForwarderStatusManager::ForwarderStatusManager().

◆ getNBuckets()

size_t nfd::name_tree::NameTree::getNBuckets ( ) const

inline

Returns: number of hashtable buckets

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

References nfd::name_tree::Hashtable::getNBuckets().

◆ getEntry()

template<typename ENTRY >

Entry* nfd::name_tree::NameTree::getEntry ( const ENTRY & tableEntry ) const

inline

Returns: name tree entry on which a table entry is attached, or nullptr if the table entry is detached

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

References eraseIfEmpty(), findAllMatches(), findExactMatch(), findLongestPrefixMatch(), nfd::name_tree::Entry::get(), and lookup().

Referenced by nfd::strategy_choice::clearStrategyInfo(), nfd::fib::Fib::erase(), nfd::measurements::Measurements::extendLifetime(), nfd::pit::Pit::findAllDataMatches(), findLongestPrefixMatch(), nfd::measurements::Measurements::getParent(), lookup(), and nfd::fib::Fib::removeNextHop().

◆ lookup() [1/5]

Entry & nfd::name_tree::NameTree::lookup ( const Name & name )

find or insert an entry with specified name

Parameters

name	a name prefix

Returns: an entry with name

Postcondition: an entry with name and all ancestors are created

Note: Existing iterators are unaffected.

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

References nfd::name_tree::computeHashes(), nfd::name_tree::Node::entry, nfd::name_tree::Hashtable::insert(), NFD_LOG_TRACE, nfd::name_tree::Entry::setParent(), and ndn::Name::size().

Referenced by nfd::strategy_choice::StrategyChoice::findEffectiveStrategy(), nfd::measurements::Measurements::get(), getEntry(), nfd::strategy_choice::StrategyChoice::insert(), nfd::fib::Fib::insert(), lookup(), and nfd::pit::Pit::Pit().

◆ lookup() [2/5]

Entry & nfd::name_tree::NameTree::lookup ( const fib::Entry & fibEntry )

equivalent to .lookup(fibEntry.getPrefix())

Parameters

fibEntry a FIB entry attached to this name tree, or Fib::s_emptyEntry

Note: This overload is more efficient than .lookup(const Name&) in common cases.

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

References ndn::Name::empty(), getEntry(), nfd::name_tree::Entry::getFibEntry(), nfd::fib::Entry::getPrefix(), and lookup().

◆ lookup() [3/5]

Entry & nfd::name_tree::NameTree::lookup ( const pit::Entry & pitEntry )

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

Parameters

pitEntry a PIT entry attached to this name tree

Note: This overload is more efficient than .lookup(const Name&) in common cases.

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

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

◆ lookup() [4/5]

Entry & nfd::name_tree::NameTree::lookup ( const measurements::Entry & measurementsEntry )

equivalent to .lookup(measurementsEntry.getName())

Parameters

measurementsEntry a Measurements entry attached to this name tree

Note: This overload is more efficient than .lookup(const Name&) in common cases.

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

References getEntry(), and nfd::name_tree::Entry::getMeasurementsEntry().

◆ lookup() [5/5]

Entry & nfd::name_tree::NameTree::lookup ( const strategy_choice::Entry & strategyChoiceEntry )

equivalent to .lookup(strategyChoiceEntry.getPrefix())

Parameters

strategyChoiceEntry a StrategyChoice entry attached to this name tree

Note: This overload is more efficient than .lookup(const Name&) in common cases.

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

References getEntry(), and nfd::name_tree::Entry::getStrategyChoiceEntry().

◆ eraseIfEmpty()

size_t nfd::name_tree::NameTree::eraseIfEmpty	(	Entry *	entry,
		bool	canEraseAncestors = `true`
	)

delete the entry if it is empty

Parameters

entry	a valid entry
canEraseAncestors	whether ancestors should be deleted if they become empty

Returns: number of deleted entries

See also: Entry::isEmpty()

Postcondition: If the entry is empty, it's deleted. If canEraseAncestors is true, ancestors of the entry are also deleted if they become empty.

Note: This function must be called after detaching a table entry from a name tree entry,; Existing iterators, except those pointing to deleted entries, are unaffected.

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

References nfd::name_tree::Hashtable::erase(), nfd::name_tree::Entry::getName(), nfd::name_tree::getNode(), nfd::name_tree::Entry::getParent(), nfd::name_tree::Entry::isEmpty(), NFD_LOG_TRACE, and nfd::name_tree::Entry::unsetParent().

Referenced by nfd::strategy_choice::StrategyChoice::erase(), nfd::measurements::Measurements::extendLifetime(), nfd::pit::Pit::findAllDataMatches(), getEntry(), and nfd::fib::Fib::insert().

◆ findExactMatch()

Entry * nfd::name_tree::NameTree::findExactMatch ( const Name & name ) const

exact match lookup

Returns: entry with name, or nullptr if it does not exist

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

References nfd::name_tree::Node::entry, nfd::name_tree::Hashtable::find(), and ndn::Name::size().

Referenced by nfd::fib::Fib::erase(), nfd::strategy_choice::StrategyChoice::erase(), nfd::fib::Fib::findExactMatch(), nfd::measurements::Measurements::findExactMatch(), findLongestPrefixMatch(), nfd::strategy_choice::StrategyChoice::get(), getEntry(), partialEnumerate(), and nfd::pit::Pit::Pit().

◆ findLongestPrefixMatch() [1/4]

Entry * nfd::name_tree::NameTree::findLongestPrefixMatch	(	const Name &	name,
		const EntrySelector &	entrySelector = `AnyEntry()`
	)		const

longest prefix matching

Returns: entry whose name is a prefix of name and passes entrySelector, where no other entry with a longer name satisfies those requirements; or nullptr if no entry satisfying those requirements exists

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

References nfd::name_tree::computeHashes(), nfd::name_tree::Node::entry, nfd::name_tree::Hashtable::find(), and ndn::Name::size().

Referenced by nfd::fib::Fib::Fib(), findAllMatches(), nfd::strategy_choice::StrategyChoice::findEffectiveStrategyImpl(), findLongestPrefixMatch(), getEntry(), and nfd::measurements::Measurements::getParent().

◆ findLongestPrefixMatch() [2/4]

Entry * nfd::name_tree::NameTree::findLongestPrefixMatch	(	const Entry &	entry,
		const EntrySelector &	entrySelector = `AnyEntry()`
	)		const

equivalent to .findLongestPrefixMatch(entry.getName(), entrySelector)

Note: This overload is more efficient than .findLongestPrefixMatch(const Name&, const EntrySelector&) in common cases.

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

References nfd::name_tree::Entry::getParent().

◆ findLongestPrefixMatch() [3/4]

template<typename ENTRY >

Entry * nfd::name_tree::NameTree::findLongestPrefixMatch	(	const ENTRY &	tableEntry,
		const EntrySelector &	entrySelector = `AnyEntry()`
	)		const

equivalent to .findLongestPrefixMatch(getEntry(tableEntry)->getName(), entrySelector)

Template Parameters

ENTRY fib::Entry or measurements::Entry or strategy_choice::Entry

Note: This overload is more efficient than .findLongestPrefixMatch(const Name&, const EntrySelector&) in common cases.

Warning: Undefined behavior may occur if tableEntry is not attached to this name tree.

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

References findLongestPrefixMatch(), and getEntry().

◆ findLongestPrefixMatch() [4/4]

Entry * nfd::name_tree::NameTree::findLongestPrefixMatch	(	const pit::Entry &	pitEntry,
		const EntrySelector &	entrySelector = `AnyEntry()`
	)		const

equivalent to .findLongestPrefixMatch(pitEntry.getName(), entrySelector)

Note: This overload is more efficient than .findLongestPrefixMatch(const Name&, const EntrySelector&) in common cases.

Warning: Undefined behavior may occur if pitEntry is not attached to this name tree.

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

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

◆ findAllMatches()

boost::iterator_range< NameTree::const_iterator > nfd::name_tree::NameTree::findAllMatches	(	const Name &	name,
		const EntrySelector &	entrySelector = `AnyEntry()`
	)		const

all-prefixes match lookup

Returns: a range where every entry has a name that is a prefix of name , and matches entrySelector.

Example:

Name name("/A/B/C");
auto&& allMatches = nt.findAllMatches(name);
for (const Entry& nte : allMatches) {
  BOOST_ASSERT(nte.getName().isPrefixOf(name));
  ...
}

Note: Iteration order is implementation-defined.

Warning: If a name tree entry whose name is a prefix of name is inserted during the enumeration, it may or may not be visited. If a name tree entry whose name is a prefix of name is deleted during the enumeration, undefined behavior may occur.

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

References end(), and findLongestPrefixMatch().

Referenced by nfd::pit::Pit::findAllDataMatches(), and getEntry().

◆ fullEnumerate()

boost::iterator_range< NameTree::const_iterator > nfd::name_tree::NameTree::fullEnumerate ( const EntrySelector & entrySelector = AnyEntry() ) const

enumerate all entries

Returns: a range where every entry matches entrySelector

Example:

auto&& enumerable = nt.fullEnumerate();
for (const Entry& nte : enumerable) {
  ...
}

Note: Iteration order is implementation-defined.

Warning: If a name tree entry is inserted or deleted during the enumeration, it may cause the enumeration to skip entries or visit some entries twice.

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

References end().

Referenced by nfd::pit::Pit::begin(), begin(), nfd::strategy_choice::clearStrategyInfo(), and nfd::fib::Fib::removeNextHop().

◆ partialEnumerate()

boost::iterator_range< NameTree::const_iterator > nfd::name_tree::NameTree::partialEnumerate	(	const Name &	prefix,
		const EntrySubTreeSelector &	entrySubTreeSelector = `AnyEntrySubTree()`
	)		const

enumerate all entries under a prefix

Returns: a range where every entry has a name that starts with prefix, and matches entrySubTreeSelector.

Example:

Name name("/A/B/C");
auto&& enumerable = nt.partialEnumerate(name);
for (const Entry& nte : enumerable) {
  BOOST_ASSERT(name.isPrefixOf(nte.getName()));
  ...
}

Note: Iteration order is implementation-defined.

Warning: If a name tree entry under prefix is inserted or deleted during the enumeration, it may cause the enumeration to skip entries or visit some entries twice.

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

References end(), and findExactMatch().

Referenced by nfd::strategy_choice::clearStrategyInfo().

◆ begin()

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

inline

Returns: an iterator to the beginning

See also: fullEnumerate

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

References fullEnumerate().

◆ end()

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

inline

Returns: an iterator to the end

See also: begin()

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

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

Friends And Related Function Documentation

◆ EnumerationImpl

friend class EnumerationImpl

friend

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

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

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ const_iterator

Constructor & Destructor Documentation

◆ NameTree()

Member Function Documentation

◆ size()

◆ getNBuckets()

◆ getEntry()

◆ lookup() [1/5]

◆ lookup() [2/5]

◆ lookup() [3/5]

◆ lookup() [4/5]

◆ lookup() [5/5]

◆ eraseIfEmpty()

◆ findExactMatch()

◆ findLongestPrefixMatch() [1/4]

◆ findLongestPrefixMatch() [2/4]

◆ findLongestPrefixMatch() [3/4]

◆ findLongestPrefixMatch() [4/4]

◆ findAllMatches()

◆ fullEnumerate()

◆ partialEnumerate()

◆ begin()

◆ end()

Friends And Related Function Documentation

◆ EnumerationImpl