NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.3: NDN, CCN, CCNx, content centric networks
API Documentation
nfd::name_tree::NameTree Class Reference

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

typedef Iterator const_iterator
 

Public Member Functions

 NameTree (size_t nBuckets=1024)
 
size_t size () const
 
size_t getNBuckets () const
 
template<typename ENTRY >
EntrygetEntry (const ENTRY &tableEntry) const
 
Entrylookup (const Name &name)
 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...
 
size_t eraseIfEmpty (Entry *entry, bool canEraseAncestors=true)
 delete the entry if it is empty More...
 
EntryfindExactMatch (const Name &name) 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 ENTRY >
EntryfindLongestPrefixMatch (const ENTRY &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 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
 

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

◆ size()

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

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

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

Referenced by nfd::ForwarderStatusManager::ForwarderStatusManager().

◆ getNBuckets()

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

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

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

◆ getEntry()

template<typename ENTRY >
Entry* nfd::name_tree::NameTree::getEntry ( const ENTRY &  tableEntry) const
inline

◆ lookup() [1/5]

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

find or insert an entry with specified name

Parameters
namea name prefix
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, nfd::name_tree::Hashtable::insert(), NFD_LOG_TRACE, nfd::name_tree::Entry::setParent(), and ndn::Name::size().

Referenced by nfd::strategy_choice::StrategyChoice::findEffectiveStrategy(), nfd::measurements::Measurements::get(), getEntry(), nfd::strategy_choice::StrategyChoice::insert(), nfd::fib::Fib::insert(), lookup(), and nfd::pit::Pit::Pit().

◆ lookup() [2/5]

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 65 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
pitEntrya PIT entry attached to this name tree
Note
This overload is more efficient than .lookup(const Name&) in common cases.

Definition at line 79 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
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.

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
strategyChoiceEntrya StrategyChoice entry attached to this name tree
Note
This overload is more efficient than .lookup(const Name&) in common cases.

Definition at line 111 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
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 121 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(), nfd::measurements::Measurements::extendLifetime(), nfd::pit::Pit::findAllDataMatches(), getEntry(), and nfd::fib::Fib::insert().

◆ findExactMatch()

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

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

Referenced by nfd::fib::Fib::Fib(), findAllMatches(), nfd::strategy_choice::StrategyChoice::findEffectiveStrategyImpl(), findLongestPrefixMatch(), getEntry(), and nfd::measurements::Measurements::getParent().

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

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

◆ findLongestPrefixMatch() [3/4]

template<typename ENTRY >
Entry * nfd::name_tree::NameTree::findLongestPrefixMatch ( const ENTRY &  tableEntry,
const EntrySelector entrySelector = AnyEntry() 
) const

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

Template Parameters
ENTRYfib::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 184 of file name-tree.cpp.

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

References ndn::Name::at(), findExactMatch(), findLongestPrefixMatch(), getEntry(), nfd::name_tree::Entry::getName(), nfd::pit::Entry::getName(), ndn::Name::getPrefix(), ndn::name::Component::isImplicitSha256Digest(), 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 223 of file name-tree.cpp.

References end(), and findLongestPrefixMatch().

Referenced by nfd::pit::Pit::findAllDataMatches(), and getEntry().

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

References end().

Referenced by nfd::pit::Pit::begin(), begin(), nfd::strategy_choice::clearStrategyInfo(), and nfd::fib::Fib::removeNextHop().

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

References end(), and findExactMatch().

Referenced by nfd::strategy_choice::clearStrategyInfo().

◆ begin()

const_iterator nfd::name_tree::NameTree::begin ( ) const
inline
Returns
an iterator to the beginning
See also
fullEnumerate

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

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

Friends And Related Function Documentation

◆ EnumerationImpl

friend class EnumerationImpl
friend

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


The documentation for this class was generated from the following files: