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, bool enforceMaxDepth=false)
 find or insert an entry with specified name More...
 
Entrylookup (const fib::Entry &fibEntry)
 equivalent to .lookup(fibEntry.getPrefix()) More...
 
Entrylookup (const pit::Entry &pitEntry)
 equivalent to .lookup(pitEntry.getName()). 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 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

Constructor & Destructor Documentation

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

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

Member Function Documentation

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.

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.

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

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.

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.

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.

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.

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

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.

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.

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.

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

size_t nfd::name_tree::NameTree::getNBuckets ( ) const
inline
Returns
number of hashtable buckets

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

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

find or insert an entry with specified name

Parameters
namea name prefix
enforceMaxDepthif 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.

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

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

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

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

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

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.

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.

size_t nfd::name_tree::NameTree::size ( ) const
inline
Returns
number of name tree entries

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

Friends And Related Function Documentation

friend class EnumerationImpl
friend

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