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, size_t prefixLen)
	Find or insert an entry by name. More...

Entry &	lookup (const Name &name)
	Equivalent to `lookup(name, name.size())` More...

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

Entry &	lookup (const pit::Entry &pitEntry)
	Equivalent to `lookup(pitEntry.getName(), std::min(pitEntry.getName().size(), getMaxDepth()))` 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 217 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 ( )

inlinestaticconstexpr

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.

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

Referenced by nfd::name_tree::Entry::Entry(), findExactMatch(), nfd::measurements::Measurements::findLongestPrefixMatch(), findLongestPrefixMatch(), nfd::fib::Fib::getMaxDepth(), nfd::measurements::Measurements::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 59 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 67 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 77 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/6]

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

Find or insert an entry by name.

This method seeks a name tree entry of name name.getPrefix(prefixLen). If the entry does not exist, it is created along with all ancestors. Existing iterators are unaffected during this operation.

Warning: prefixLen must not exceed name.size().; prefixLen must not exceed getMaxDepth().

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/6]

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

inline

Equivalent to lookup(name, name.size())

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

References lookup().

◆ lookup() [3/6]

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

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

◆ lookup() [4/6]

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

Equivalent to lookup(pitEntry.getName(), std::min(pitEntry.getName().size(), getMaxDepth()))

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

References getEntry(), getMaxDepth(), nfd::pit::Entry::getName(), nfd::name_tree::Entry::getPitEntries(), lookup(), and NFD_LOG_TRACE.

◆ lookup() [5/6]

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(), nfd::name_tree::Entry::getMeasurementsEntry(), nfd::measurements::Entry::getName(), and NFD_LOG_TRACE.

◆ lookup() [6/6]

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(), nfd::strategy_choice::Entry::getPrefix(), nfd::name_tree::Entry::getStrategyChoiceEntry(), and NFD_LOG_TRACE.

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

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

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

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

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 178 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 176 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 191 of file name-tree.cpp.

References findExactMatch(), findLongestPrefixMatch(), getEntry(), getMaxDepth(), 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 213 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 226 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 232 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 261 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 270 of file name-tree.hpp.

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

Friends And Related Function Documentation

◆ EnumerationImpl

friend class EnumerationImpl

friend

Definition at line 278 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/6]

◆ lookup() [2/6]

◆ lookup() [3/6]

◆ lookup() [4/6]

◆ lookup() [5/6]

◆ lookup() [6/6]

◆ 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