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

#include <daemon/table/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)

const_iterator	begin () const

const_iterator	end () const

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

Range	findAllMatches (const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
	All-prefixes match lookup. 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	fullEnumerate (const EntrySelector &entrySelector=AnyEntry()) const
	Enumerate all entries. More...

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

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

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

size_t	size () 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

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

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

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

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

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

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

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

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

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

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

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

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

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

◆ getNBuckets()

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

inline

Returns: number of hashtable buckets

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

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

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

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

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

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

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

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

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

Friends And Related Function Documentation

◆ EnumerationImpl

friend class EnumerationImpl

friend

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

NFD: Named Data Networking Forwarding Daemon 0.7.1 documentation

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ const_iterator

Constructor & Destructor Documentation

◆ NameTree()

Member Function Documentation

◆ begin()

◆ end()

◆ eraseIfEmpty()

◆ findAllMatches()

◆ findExactMatch()

◆ findLongestPrefixMatch() [1/4]

◆ findLongestPrefixMatch() [2/4]

◆ findLongestPrefixMatch() [3/4]

◆ findLongestPrefixMatch() [4/4]

◆ fullEnumerate()

◆ getEntry()

◆ getMaxDepth()

◆ getNBuckets()

◆ lookup() [1/6]

◆ lookup() [2/6]

◆ lookup() [3/6]

◆ lookup() [4/6]

◆ lookup() [5/6]

◆ lookup() [6/6]

◆ partialEnumerate()

◆ size()

Friends And Related Function Documentation

◆ EnumerationImpl