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
using	const_iterator = Iterator

Public Member Functions
	NameTree (size_t nBuckets=1024)

size_t	size () const

size_t	getNBuckets () const

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

Entry &	lookup (const Name &name, bool enforceMaxDepth=false)
	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, size_t prefixLen=std::numeric_limits< size_t >::max()) 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 EntryT >
Entry *	findLongestPrefixMatch (const EntryT &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

Static Public Member Functions
static constexpr size_t	getMaxDepth ()
	Maximum depth of the name tree. More...

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

using nfd::name_tree::NameTree::const_iterator = Iterator

Definition at line 210 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

◆ getMaxDepth()

static constexpr size_t nfd::name_tree::NameTree::getMaxDepth ( )

inlinestatic

Maximum depth of the name tree.

Calling NameTree::lookup with a name with many components would cause the creation of many NameTree entries, which could take very long time. This constant limits the maximum number of name components in the name of a NameTree entry. Thus, it limits the number of NameTree entries created from a long name, bounding the processing complexity.

This constant is currently advisory. It is enforced in NameTree::lookup only if enforceMaxDepth is set to true. This will become mandatory later.

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

Referenced by nfd::measurements::Measurements::findLongestPrefixMatch(), nfd::fib::Fib::getMaxDepth(), nfd::strategy_choice::StrategyChoice::insert(), lookup(), and nfd::strategy_choice::operator<<().

◆ size()

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

inline

Returns: number of name tree entries

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

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

◆ getNBuckets()

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

inline

Returns: number of hashtable buckets

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

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

◆ getEntry()

template<typename EntryT >

Entry* nfd::name_tree::NameTree::getEntry ( const EntryT & 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 80 of file name-tree.hpp.

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

Referenced by nfd::fib::Fib::erase(), nfd::measurements::Measurements::extendLifetime(), findLongestPrefixMatch(), nfd::measurements::Measurements::getParent(), lookup(), and nfd::fib::Fib::removeNextHop().

◆ lookup() [1/5]

Entry & nfd::name_tree::NameTree::lookup	(	const Name &	name,
		bool	enforceMaxDepth = `false`
	)

find or insert an entry with specified name

Parameters

name	a name prefix
enforceMaxDepth	if true, use `name.getPrefix(getMaxDepth())` in place of `name`

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, getMaxDepth(), nfd::name_tree::Hashtable::insert(), NFD_LOG_TRACE, and nfd::name_tree::Entry::setParent().

Referenced by nfd::measurements::Measurements::get(), nfd::fib::Fib::insert(), nfd::strategy_choice::StrategyChoice::insert(), lookup(), and nfd::strategy_choice::StrategyChoice::setDefaultStrategy().

◆ 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 66 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 80 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 102 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 112 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 122 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().

◆ findExactMatch()

Entry * nfd::name_tree::NameTree::findExactMatch	(	const Name &	name,
		size_t	prefixLen = `std::numeric_limits<size_t>::max()`
	)		const

exact match lookup

Returns: entry with name.getPrefix(prefixLen), or nullptr if it does not exist

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

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

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

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

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

Referenced by findAllMatches(), nfd::strategy_choice::StrategyChoice::findEffectiveStrategyImpl(), and findLongestPrefixMatch().

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

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

◆ findLongestPrefixMatch() [3/4]

template<typename EntryT >

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

inline

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

Template Parameters

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

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

References findExactMatch(), findLongestPrefixMatch(), getEntry(), nfd::name_tree::Entry::getName(), nfd::pit::Entry::getName(), 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 204 of file name-tree.cpp.

References end(), and findLongestPrefixMatch().

Referenced by nfd::pit::Pit::findAllDataMatches().

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

References end().

Referenced by nfd::pit::Pit::begin(), and begin().

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

References end(), and findExactMatch().

◆ begin()

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

inline

Returns: an iterator to the beginning

See also: fullEnumerate

Definition at line 254 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 263 of file name-tree.hpp.

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

Friends And Related Function Documentation

◆ EnumerationImpl

friend class EnumerationImpl

friend

Definition at line 271 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

Static Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ const_iterator

Constructor & Destructor Documentation

◆ NameTree()

Member Function Documentation

◆ getMaxDepth()

◆ 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