29 #include <boost/concept/assert.hpp>
30 #include <boost/concept_check.hpp>
31 #include <type_traits>
46 BOOST_ASSERT(prefixLen <= name.size());
50 const Node* node =
nullptr;
51 Entry* parent =
nullptr;
53 for (
size_t i = 0; i <= prefixLen; ++i) {
55 std::tie(node, isNew) = m_ht.
insert(name, i, hashes);
57 if (isNew && parent !=
nullptr) {
60 parent = &node->
entry;
72 BOOST_ASSERT(fibEntry.
getPrefix().empty());
83 const Name& name = pitEntry.
getName();
85 bool hasDigest = name.size() > 0 && name[-1].isImplicitSha256Digest();
91 BOOST_ASSERT(nte !=
nullptr);
93 [&pitEntry] (
const auto& pitEntry1) {
94 return pitEntry1.get() == &pitEntry;
104 BOOST_ASSERT(nte !=
nullptr);
115 BOOST_ASSERT(nte !=
nullptr);
124 BOOST_ASSERT(entry !=
nullptr);
127 for (
Entry* parent =
nullptr; entry !=
nullptr && entry->
isEmpty(); entry = parent) {
130 if (parent !=
nullptr) {
137 if (!canEraseAncestors) {
151 prefixLen = std::min(name.size(), prefixLen);
156 const Node* node = m_ht.
find(name, prefixLen);
157 return node ==
nullptr ? nullptr : &node->
entry;
163 size_t depth = std::min(name.size(),
getMaxDepth());
166 for (ssize_t i = depth; i >= 0; --i) {
167 const Node* node = m_ht.
find(name, i, hashes);
168 if (node !=
nullptr && entrySelector(node->
entry)) {
180 while (entry !=
nullptr) {
181 if (entrySelector(*entry)) {
193 BOOST_ASSERT(nte !=
nullptr);
195 const Name& name = pitEntry.
getName();
196 size_t depth = std::min(name.size(),
getMaxDepth());
199 for (
size_t i = nte->
getName().size() + 1; i <= depth; ++i) {
201 if (exact ==
nullptr) {
211 boost::iterator_range<NameTree::const_iterator>
221 return {
Iterator(make_shared<PrefixMatchImpl>(*
this, entrySelector), entry),
end()};
224 boost::iterator_range<NameTree::const_iterator>
227 return {
Iterator(make_shared<FullEnumerationImpl>(*
this, entrySelector),
nullptr),
end()};
230 boost::iterator_range<NameTree::const_iterator>
235 return {
Iterator(make_shared<PartialEnumerationImpl>(*
this, entrySubTreeSelector), entry),
end()};
Represents an entry in the FIB.
const Name & getPrefix() const noexcept
Represents an entry in the Measurements table.
const Name & getName() const noexcept
An entry in the name tree.
void unsetParent()
Unset parent of this entry.
fib::Entry * getFibEntry() const
measurements::Entry * getMeasurementsEntry() const
void setParent(Entry &entry)
Set parent of this entry.
const std::vector< shared_ptr< pit::Entry > > & getPitEntries() const
Entry * getParent() const noexcept
const Name & getName() const noexcept
strategy_choice::Entry * getStrategyChoiceEntry() const
void erase(Node *node)
Delete node.
std::pair< const Node *, bool > insert(const Name &name, size_t prefixLen, const HashSequence &hashes)
Find or insert node for name.getPrefix(prefixLen).
const Node * find(const Name &name, size_t prefixLen) const
Find node for name.getPrefix(prefixLen).
NameTree(size_t nBuckets=1024)
Range partialEnumerate(const Name &prefix, const EntrySubTreeSelector &entrySubTreeSelector=AnyEntrySubTree()) const
Enumerate all entries under a prefix.
Range findAllMatches(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
All-prefixes match lookup.
const_iterator end() const
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
Delete the entry if it is empty.
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
Enumerate all entries.
static constexpr size_t getMaxDepth()
Maximum depth of the name tree.
Entry & lookup(const Name &name, size_t prefixLen)
Find or insert an entry by name.
Entry * getEntry(const EntryT &tableEntry) const
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
Exact match lookup.
Entry * findLongestPrefixMatch(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
Longest prefix matching.
Represents an entry in the Interest table (PIT).
const Name & getName() const
Represents an entry in the Strategy Choice table.
const Name & getPrefix() const
#define NFD_LOG_INIT(name)
std::vector< HashValue > HashSequence
A sequence of hash values.
std::function< bool(const Entry &)> EntrySelector
A predicate to accept or reject an Entry in find operations.
Node * getNode(const Entry &entry)
std::function< std::pair< bool, bool >(const Entry &)> EntrySubTreeSelector
A predicate to accept or reject an Entry and its children.
HashSequence computeHashes(const Name &name, size_t prefixLen)
Computes hash values for each prefix of name.getPrefix(prefixLen).
Provides options for Hashtable.