name-tree.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2022, Regents of the University of California,
4  * Arizona Board of Regents,
5  * Colorado State University,
6  * University Pierre & Marie Curie, Sorbonne University,
7  * Washington University in St. Louis,
8  * Beijing Institute of Technology,
9  * The University of Memphis.
10  *
11  * This file is part of NFD (Named Data Networking Forwarding Daemon).
12  * See AUTHORS.md for complete list of NFD authors and contributors.
13  *
14  * NFD is free software: you can redistribute it and/or modify it under the terms
15  * of the GNU General Public License as published by the Free Software Foundation,
16  * either version 3 of the License, or (at your option) any later version.
17  *
18  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20  * PURPOSE. See the GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License along with
23  * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24  */
25 
26 #include "name-tree.hpp"
27 #include "common/logger.hpp"
28 
29 #include <boost/concept/assert.hpp>
30 #include <boost/concept_check.hpp>
31 #include <type_traits>
32 
33 namespace nfd::name_tree {
34 
35 NFD_LOG_INIT(NameTree);
36 
37 NameTree::NameTree(size_t nBuckets)
38  : m_ht(HashtableOptions(nBuckets))
39 {
40 }
41 
42 Entry&
43 NameTree::lookup(const Name& name, size_t prefixLen)
44 {
45  NFD_LOG_TRACE("lookup(" << name << ", " << prefixLen << ')');
46  BOOST_ASSERT(prefixLen <= name.size());
47  BOOST_ASSERT(prefixLen <= getMaxDepth());
48 
49  HashSequence hashes = computeHashes(name, prefixLen);
50  const Node* node = nullptr;
51  Entry* parent = nullptr;
52 
53  for (size_t i = 0; i <= prefixLen; ++i) {
54  bool isNew = false;
55  std::tie(node, isNew) = m_ht.insert(name, i, hashes);
56 
57  if (isNew && parent != nullptr) {
58  node->entry.setParent(*parent);
59  }
60  parent = &node->entry;
61  }
62  return node->entry;
63 }
64 
65 Entry&
66 NameTree::lookup(const fib::Entry& fibEntry)
67 {
68  NFD_LOG_TRACE("lookup(FIB " << fibEntry.getPrefix() << ')');
69  Entry* nte = this->getEntry(fibEntry);
70  if (nte == nullptr) {
71  // special case: Fib::s_emptyEntry is unattached
72  BOOST_ASSERT(fibEntry.getPrefix().empty());
73  return this->lookup(fibEntry.getPrefix());
74  }
75 
76  BOOST_ASSERT(nte->getFibEntry() == &fibEntry);
77  return *nte;
78 }
79 
80 Entry&
81 NameTree::lookup(const pit::Entry& pitEntry)
82 {
83  const Name& name = pitEntry.getName();
84  NFD_LOG_TRACE("lookup(PIT " << name << ')');
85  bool hasDigest = name.size() > 0 && name[-1].isImplicitSha256Digest();
86  if (hasDigest && name.size() <= getMaxDepth()) {
87  return this->lookup(name);
88  }
89 
90  Entry* nte = this->getEntry(pitEntry);
91  BOOST_ASSERT(nte != nullptr);
92  BOOST_ASSERT(std::count_if(nte->getPitEntries().begin(), nte->getPitEntries().end(),
93  [&pitEntry] (const auto& pitEntry1) {
94  return pitEntry1.get() == &pitEntry;
95  }) == 1);
96  return *nte;
97 }
98 
99 Entry&
100 NameTree::lookup(const measurements::Entry& measurementsEntry)
101 {
102  NFD_LOG_TRACE("lookup(M " << measurementsEntry.getName() << ')');
103  Entry* nte = this->getEntry(measurementsEntry);
104  BOOST_ASSERT(nte != nullptr);
105 
106  BOOST_ASSERT(nte->getMeasurementsEntry() == &measurementsEntry);
107  return *nte;
108 }
109 
110 Entry&
111 NameTree::lookup(const strategy_choice::Entry& strategyChoiceEntry)
112 {
113  NFD_LOG_TRACE("lookup(SC " << strategyChoiceEntry.getPrefix() << ')');
114  Entry* nte = this->getEntry(strategyChoiceEntry);
115  BOOST_ASSERT(nte != nullptr);
116 
117  BOOST_ASSERT(nte->getStrategyChoiceEntry() == &strategyChoiceEntry);
118  return *nte;
119 }
120 
121 size_t
122 NameTree::eraseIfEmpty(Entry* entry, bool canEraseAncestors)
123 {
124  BOOST_ASSERT(entry != nullptr);
125 
126  size_t nErased = 0;
127  for (Entry* parent = nullptr; entry != nullptr && entry->isEmpty(); entry = parent) {
128  parent = entry->getParent();
129 
130  if (parent != nullptr) {
131  entry->unsetParent();
132  }
133 
134  m_ht.erase(getNode(*entry));
135  ++nErased;
136 
137  if (!canEraseAncestors) {
138  break;
139  }
140  }
141 
142  if (nErased == 0) {
143  NFD_LOG_TRACE("not-erase " << entry->getName());
144  }
145  return nErased;
146 }
147 
148 Entry*
149 NameTree::findExactMatch(const Name& name, size_t prefixLen) const
150 {
151  prefixLen = std::min(name.size(), prefixLen);
152  if (prefixLen > getMaxDepth()) {
153  return nullptr;
154  }
155 
156  const Node* node = m_ht.find(name, prefixLen);
157  return node == nullptr ? nullptr : &node->entry;
158 }
159 
160 Entry*
161 NameTree::findLongestPrefixMatch(const Name& name, const EntrySelector& entrySelector) const
162 {
163  size_t depth = std::min(name.size(), getMaxDepth());
164  HashSequence hashes = computeHashes(name, depth);
165 
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)) {
169  return &node->entry;
170  }
171  }
172 
173  return nullptr;
174 }
175 
176 Entry*
177 NameTree::findLongestPrefixMatch(const Entry& entry1, const EntrySelector& entrySelector) const
178 {
179  Entry* entry = const_cast<Entry*>(&entry1);
180  while (entry != nullptr) {
181  if (entrySelector(*entry)) {
182  return entry;
183  }
184  entry = entry->getParent();
185  }
186  return nullptr;
187 }
188 
189 Entry*
190 NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry, const EntrySelector& entrySelector) const
191 {
192  const Entry* nte = this->getEntry(pitEntry);
193  BOOST_ASSERT(nte != nullptr);
194 
195  const Name& name = pitEntry.getName();
196  size_t depth = std::min(name.size(), getMaxDepth());
197  if (nte->getName().size() < pitEntry.getName().size()) {
198  // PIT entry name either exceeds depth limit or ends with an implicit digest: go deeper
199  for (size_t i = nte->getName().size() + 1; i <= depth; ++i) {
200  const Entry* exact = this->findExactMatch(name, i);
201  if (exact == nullptr) {
202  break;
203  }
204  nte = exact;
205  }
206  }
207 
208  return this->findLongestPrefixMatch(*nte, entrySelector);
209 }
210 
211 boost::iterator_range<NameTree::const_iterator>
212 NameTree::findAllMatches(const Name& name, const EntrySelector& entrySelector) const
213 {
214  // As we are using Name Prefix Hash Table, and the current LPM() is
215  // implemented as starting from full name, and reduce the number of
216  // components by 1 each time, we could use it here.
217  // For trie-like design, it could be more efficient by walking down the
218  // trie from the root node.
219 
220  Entry* entry = this->findLongestPrefixMatch(name, entrySelector);
221  return {Iterator(make_shared<PrefixMatchImpl>(*this, entrySelector), entry), end()};
222 }
223 
224 boost::iterator_range<NameTree::const_iterator>
225 NameTree::fullEnumerate(const EntrySelector& entrySelector) const
226 {
227  return {Iterator(make_shared<FullEnumerationImpl>(*this, entrySelector), nullptr), end()};
228 }
229 
230 boost::iterator_range<NameTree::const_iterator>
231 NameTree::partialEnumerate(const Name& prefix,
232  const EntrySubTreeSelector& entrySubTreeSelector) const
233 {
234  Entry* entry = this->findExactMatch(prefix);
235  return {Iterator(make_shared<PartialEnumerationImpl>(*this, entrySubTreeSelector), entry), end()};
236 }
237 
238 } // namespace nfd::name_tree
Represents an entry in the FIB.
Definition: fib-entry.hpp:91
const Name & getPrefix() const noexcept
Definition: fib-entry.hpp:97
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
bool isEmpty() const
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)
Definition: name-tree.cpp:37
Range partialEnumerate(const Name &prefix, const EntrySubTreeSelector &entrySubTreeSelector=AnyEntrySubTree()) const
Enumerate all entries under a prefix.
Definition: name-tree.cpp:231
Range findAllMatches(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
All-prefixes match lookup.
Definition: name-tree.cpp:212
const_iterator end() const
Definition: name-tree.hpp:270
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
Delete the entry if it is empty.
Definition: name-tree.cpp:122
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
Enumerate all entries.
Definition: name-tree.cpp:225
static constexpr size_t getMaxDepth()
Maximum depth of the name tree.
Definition: name-tree.hpp:51
Entry & lookup(const Name &name, size_t prefixLen)
Find or insert an entry by name.
Definition: name-tree.cpp:43
Entry * getEntry(const EntryT &tableEntry) const
Definition: name-tree.hpp:77
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
Exact match lookup.
Definition: name-tree.cpp:149
Entry * findLongestPrefixMatch(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
Longest prefix matching.
Definition: name-tree.cpp:161
Represents an entry in the Interest table (PIT).
Definition: pit-entry.hpp:197
const Name & getName() const
Definition: pit-entry.hpp:216
Represents an entry in the Strategy Choice table.
const Name & getPrefix() const
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
#define NFD_LOG_TRACE
Definition: logger.hpp:37
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.