29 #include <boost/concept/assert.hpp> 30 #include <boost/concept_check.hpp> 31 #include <type_traits> 47 BOOST_ASSERT(prefixLen <= name.size());
51 const Node* node =
nullptr;
52 Entry* parent =
nullptr;
54 for (
size_t i = 0; i <= prefixLen; ++i) {
56 std::tie(node, isNew) = m_ht.
insert(name, i, hashes);
58 if (isNew && parent !=
nullptr) {
61 parent = &node->
entry;
73 BOOST_ASSERT(fibEntry.
getPrefix().empty());
77 BOOST_ASSERT(nte->getFibEntry() == &fibEntry);
84 const Name& name = pitEntry.
getName();
86 bool hasDigest = name.size() > 0 && name[-1].isImplicitSha256Digest();
92 BOOST_ASSERT(nte !=
nullptr);
94 [&pitEntry] (
const auto& pitEntry1) {
95 return pitEntry1.get() == &pitEntry;
105 BOOST_ASSERT(nte !=
nullptr);
107 BOOST_ASSERT(nte->getMeasurementsEntry() == &measurementsEntry);
116 BOOST_ASSERT(nte !=
nullptr);
118 BOOST_ASSERT(nte->getStrategyChoiceEntry() == &strategyChoiceEntry);
125 BOOST_ASSERT(entry !=
nullptr);
128 for (
Entry* parent =
nullptr; entry !=
nullptr && entry->
isEmpty(); entry = parent) {
131 if (parent !=
nullptr) {
138 if (!canEraseAncestors) {
152 prefixLen = std::min(name.size(), prefixLen);
157 const Node* node = m_ht.
find(name, prefixLen);
158 return node ==
nullptr ? nullptr : &node->
entry;
164 size_t depth = std::min(name.size(),
getMaxDepth());
167 for (ssize_t i = depth; i >= 0; --i) {
168 const Node* node = m_ht.
find(name, i, hashes);
169 if (node !=
nullptr && entrySelector(node->
entry)) {
181 while (entry !=
nullptr) {
182 if (entrySelector(*entry)) {
194 BOOST_ASSERT(nte !=
nullptr);
196 const Name& name = pitEntry.
getName();
197 size_t depth = std::min(name.size(),
getMaxDepth());
200 for (
size_t i = nte->
getName().size() + 1; i <= depth; ++i) {
202 if (exact ==
nullptr) {
212 boost::iterator_range<NameTree::const_iterator>
222 return {
Iterator(make_shared<PrefixMatchImpl>(*
this, entrySelector), entry),
end()};
225 boost::iterator_range<NameTree::const_iterator>
228 return {
Iterator(make_shared<FullEnumerationImpl>(*
this, entrySelector),
nullptr),
end()};
231 boost::iterator_range<NameTree::const_iterator>
236 return {
Iterator(make_shared<PartialEnumerationImpl>(*
this, entrySubTreeSelector), entry),
end()};
void unsetParent()
Unset parent of this entry.
Represents a Measurements entry.
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
Delete the entry if it is empty.
HashSequence computeHashes(const Name &name, size_t prefixLen)
computes hash values for each prefix of name.getPrefix(prefixLen)
const Node * find(const Name &name, size_t prefixLen) const
find node for name.getPrefix(prefixLen)
void setParent(Entry &entry)
Set parent of this entry.
static constexpr size_t getMaxDepth()
Maximum depth of the name tree.
std::vector< HashValue > HashSequence
a sequence of hash values
const std::vector< shared_ptr< pit::Entry > > & getPitEntries() const
Entry * getEntry(const EntryT &tableEntry) const
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
Enumerate all entries.
const_iterator end() const
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
Exact match lookup.
Entry & lookup(const Name &name, size_t prefixLen)
Find or insert an entry by name.
provides options for Hashtable
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
const Name & getName() const
Entry * getParent() const
std::pair< const Node *, bool > insert(const Name &name, size_t prefixLen, const HashSequence &hashes)
find or insert node for name.getPrefix(prefixLen)
Range partialEnumerate(const Name &prefix, const EntrySubTreeSelector &entrySubTreeSelector=AnyEntrySubTree()) const
Enumerate all entries under a prefix.
const Name & getPrefix() const
const Name & getName() const
const Name & getPrefix() const
Entry * findLongestPrefixMatch(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
Longest prefix matching.
Node * getNode(const Entry &entry)
An entry in the name tree.
Represents a Strategy Choice entry.
#define NFD_LOG_INIT(name)
std::function< std::pair< bool, bool >(const Entry &)> EntrySubTreeSelector
a predicate to accept or reject an Entry and its children
Range findAllMatches(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
All-prefixes match lookup.
void erase(Node *node)
delete node
std::function< bool(const Entry &)> EntrySelector
a predicate to accept or reject an Entry in find operations
const Name & getName() const
NameTree(size_t nBuckets=1024)