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-2019, 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 {
34 namespace name_tree {
35 
36 NFD_LOG_INIT(NameTree);
37 
38 NameTree::NameTree(size_t nBuckets)
39  : m_ht(HashtableOptions(nBuckets))
40 {
41 }
42 
43 Entry&
44 NameTree::lookup(const Name& name, size_t prefixLen)
45 {
46  NFD_LOG_TRACE("lookup(" << name << ", " << prefixLen << ')');
47  BOOST_ASSERT(prefixLen <= name.size());
48  BOOST_ASSERT(prefixLen <= getMaxDepth());
49 
50  HashSequence hashes = computeHashes(name, prefixLen);
51  const Node* node = nullptr;
52  Entry* parent = nullptr;
53 
54  for (size_t i = 0; i <= prefixLen; ++i) {
55  bool isNew = false;
56  std::tie(node, isNew) = m_ht.insert(name, i, hashes);
57 
58  if (isNew && parent != nullptr) {
59  node->entry.setParent(*parent);
60  }
61  parent = &node->entry;
62  }
63  return node->entry;
64 }
65 
66 Entry&
67 NameTree::lookup(const fib::Entry& fibEntry)
68 {
69  NFD_LOG_TRACE("lookup(FIB " << fibEntry.getPrefix() << ')');
70  Entry* nte = this->getEntry(fibEntry);
71  if (nte == nullptr) {
72  // special case: Fib::s_emptyEntry is unattached
73  BOOST_ASSERT(fibEntry.getPrefix().empty());
74  return this->lookup(fibEntry.getPrefix());
75  }
76 
77  BOOST_ASSERT(nte->getFibEntry() == &fibEntry);
78  return *nte;
79 }
80 
81 Entry&
82 NameTree::lookup(const pit::Entry& pitEntry)
83 {
84  const Name& name = pitEntry.getName();
85  NFD_LOG_TRACE("lookup(PIT " << name << ')');
86  bool hasDigest = name.size() > 0 && name[-1].isImplicitSha256Digest();
87  if (hasDigest && name.size() <= getMaxDepth()) {
88  return this->lookup(name);
89  }
90 
91  Entry* nte = this->getEntry(pitEntry);
92  BOOST_ASSERT(nte != nullptr);
93  BOOST_ASSERT(std::count_if(nte->getPitEntries().begin(), nte->getPitEntries().end(),
94  [&pitEntry] (const auto& pitEntry1) {
95  return pitEntry1.get() == &pitEntry;
96  }) == 1);
97  return *nte;
98 }
99 
100 Entry&
101 NameTree::lookup(const measurements::Entry& measurementsEntry)
102 {
103  NFD_LOG_TRACE("lookup(M " << measurementsEntry.getName() << ')');
104  Entry* nte = this->getEntry(measurementsEntry);
105  BOOST_ASSERT(nte != nullptr);
106 
107  BOOST_ASSERT(nte->getMeasurementsEntry() == &measurementsEntry);
108  return *nte;
109 }
110 
111 Entry&
112 NameTree::lookup(const strategy_choice::Entry& strategyChoiceEntry)
113 {
114  NFD_LOG_TRACE("lookup(SC " << strategyChoiceEntry.getPrefix() << ')');
115  Entry* nte = this->getEntry(strategyChoiceEntry);
116  BOOST_ASSERT(nte != nullptr);
117 
118  BOOST_ASSERT(nte->getStrategyChoiceEntry() == &strategyChoiceEntry);
119  return *nte;
120 }
121 
122 size_t
123 NameTree::eraseIfEmpty(Entry* entry, bool canEraseAncestors)
124 {
125  BOOST_ASSERT(entry != nullptr);
126 
127  size_t nErased = 0;
128  for (Entry* parent = nullptr; entry != nullptr && entry->isEmpty(); entry = parent) {
129  parent = entry->getParent();
130 
131  if (parent != nullptr) {
132  entry->unsetParent();
133  }
134 
135  m_ht.erase(getNode(*entry));
136  ++nErased;
137 
138  if (!canEraseAncestors) {
139  break;
140  }
141  }
142 
143  if (nErased == 0) {
144  NFD_LOG_TRACE("not-erase " << entry->getName());
145  }
146  return nErased;
147 }
148 
149 Entry*
150 NameTree::findExactMatch(const Name& name, size_t prefixLen) const
151 {
152  prefixLen = std::min(name.size(), prefixLen);
153  if (prefixLen > getMaxDepth()) {
154  return nullptr;
155  }
156 
157  const Node* node = m_ht.find(name, prefixLen);
158  return node == nullptr ? nullptr : &node->entry;
159 }
160 
161 Entry*
162 NameTree::findLongestPrefixMatch(const Name& name, const EntrySelector& entrySelector) const
163 {
164  size_t depth = std::min(name.size(), getMaxDepth());
165  HashSequence hashes = computeHashes(name, depth);
166 
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)) {
170  return &node->entry;
171  }
172  }
173 
174  return nullptr;
175 }
176 
177 Entry*
178 NameTree::findLongestPrefixMatch(const Entry& entry1, const EntrySelector& entrySelector) const
179 {
180  Entry* entry = const_cast<Entry*>(&entry1);
181  while (entry != nullptr) {
182  if (entrySelector(*entry)) {
183  return entry;
184  }
185  entry = entry->getParent();
186  }
187  return nullptr;
188 }
189 
190 Entry*
191 NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry, const EntrySelector& entrySelector) const
192 {
193  const Entry* nte = this->getEntry(pitEntry);
194  BOOST_ASSERT(nte != nullptr);
195 
196  const Name& name = pitEntry.getName();
197  size_t depth = std::min(name.size(), getMaxDepth());
198  if (nte->getName().size() < pitEntry.getName().size()) {
199  // PIT entry name either exceeds depth limit or ends with an implicit digest: go deeper
200  for (size_t i = nte->getName().size() + 1; i <= depth; ++i) {
201  const Entry* exact = this->findExactMatch(name, i);
202  if (exact == nullptr) {
203  break;
204  }
205  nte = exact;
206  }
207  }
208 
209  return this->findLongestPrefixMatch(*nte, entrySelector);
210 }
211 
212 boost::iterator_range<NameTree::const_iterator>
213 NameTree::findAllMatches(const Name& name, const EntrySelector& entrySelector) const
214 {
215  // As we are using Name Prefix Hash Table, and the current LPM() is
216  // implemented as starting from full name, and reduce the number of
217  // components by 1 each time, we could use it here.
218  // For trie-like design, it could be more efficient by walking down the
219  // trie from the root node.
220 
221  Entry* entry = this->findLongestPrefixMatch(name, entrySelector);
222  return {Iterator(make_shared<PrefixMatchImpl>(*this, entrySelector), entry), end()};
223 }
224 
225 boost::iterator_range<NameTree::const_iterator>
226 NameTree::fullEnumerate(const EntrySelector& entrySelector) const
227 {
228  return {Iterator(make_shared<FullEnumerationImpl>(*this, entrySelector), nullptr), end()};
229 }
230 
231 boost::iterator_range<NameTree::const_iterator>
232 NameTree::partialEnumerate(const Name& prefix,
233  const EntrySubTreeSelector& entrySubTreeSelector) const
234 {
235  Entry* entry = this->findExactMatch(prefix);
236  return {Iterator(make_shared<PartialEnumerationImpl>(*this, entrySubTreeSelector), entry), end()};
237 }
238 
239 } // namespace name_tree
240 } // namespace nfd
void unsetParent()
Unset parent of this entry.
const Name & getName() const
bool isEmpty() const
Entry * findLongestPrefixMatch(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
Longest prefix matching.
Definition: name-tree.cpp:162
Represents a Measurements entry.
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
Delete the entry if it is empty.
Definition: name-tree.cpp:123
Entry * getEntry(const EntryT &tableEntry) const
Definition: name-tree.hpp:77
represents a FIB entry
Definition: fib-entry.hpp:53
HashSequence computeHashes(const Name &name, size_t prefixLen)
computes hash values for each prefix of name.getPrefix(prefixLen)
#define NFD_LOG_TRACE
Definition: logger.hpp:37
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
Enumerate all entries.
Definition: name-tree.cpp:226
void setParent(Entry &entry)
Set parent of this entry.
static constexpr size_t getMaxDepth()
Maximum depth of the name tree.
Definition: name-tree.hpp:51
std::vector< HashValue > HashSequence
a sequence of hash values
Range partialEnumerate(const Name &prefix, const EntrySubTreeSelector &entrySubTreeSelector=AnyEntrySubTree()) const
Enumerate all entries under a prefix.
Definition: name-tree.cpp:232
const std::vector< shared_ptr< pit::Entry > > & getPitEntries() const
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
Exact match lookup.
Definition: name-tree.cpp:150
Entry * getParent() const
An Interest table entry.
Definition: pit-entry.hpp:58
const Name & getPrefix() const
Definition: fib-entry.hpp:60
Entry & lookup(const Name &name, size_t prefixLen)
Find or insert an entry by name.
Definition: name-tree.cpp:44
provides options for Hashtable
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
std::pair< const Node *, bool > insert(const Name &name, size_t prefixLen, const HashSequence &hashes)
find or insert node for name.getPrefix(prefixLen)
Range findAllMatches(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
All-prefixes match lookup.
Definition: name-tree.cpp:213
const Node * find(const Name &name, size_t prefixLen) const
find node for name.getPrefix(prefixLen)
Node * getNode(const Entry &entry)
An entry in the name tree.
Represents a Strategy Choice entry.
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
std::function< std::pair< bool, bool >(const Entry &)> EntrySubTreeSelector
a predicate to accept or reject an Entry and its children
const Name & getPrefix() const
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
const Name & getName() const
Definition: pit-entry.hpp:78
NameTree(size_t nBuckets=1024)
Definition: name-tree.cpp:38
const_iterator end() const
Definition: name-tree.hpp:270