nfd::name_tree::NameTree Class Reference

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...
 
EntryfindExactMatch (const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
 Exact match lookup. More...
 
EntryfindLongestPrefixMatch (const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
 Longest prefix matching. More...
 
EntryfindLongestPrefixMatch (const Entry &entry, const EntrySelector &entrySelector=AnyEntry()) const
 Equivalent to findLongestPrefixMatch(entry.getName(), entrySelector) More...
 
template<typename EntryT >
EntryfindLongestPrefixMatch (const EntryT &tableEntry, const EntrySelector &entrySelector=AnyEntry()) const
 Equivalent to findLongestPrefixMatch(getEntry(tableEntry)->getName(), entrySelector) More...
 
EntryfindLongestPrefixMatch (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 >
EntrygetEntry (const EntryT &tableEntry) const
 
size_t getNBuckets () const
 
Entrylookup (const Name &name, size_t prefixLen)
 Find or insert an entry by name. More...
 
Entrylookup (const Name &name)
 Equivalent to lookup(name, name.size()) More...
 
Entrylookup (const fib::Entry &fibEntry)
 Equivalent to lookup(fibEntry.getPrefix()) More...
 
Entrylookup (const pit::Entry &pitEntry)
 Equivalent to lookup(pitEntry.getName(), std::min(pitEntry.getName().size(), getMaxDepth())) More...
 
Entrylookup (const measurements::Entry &measurementsEntry)
 Equivalent to lookup(measurementsEntry.getName()) More...
 
Entrylookup (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

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
entrya valid entry
canEraseAncestorswhether 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
EntryTfib::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
fibEntrya 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
pitEntrya 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
measurementsEntrya 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
strategyChoiceEntrya 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.