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-2017, 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 "core/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, bool enforceMaxDepth)
45 {
46  NFD_LOG_TRACE("lookup " << name);
47  size_t depth = enforceMaxDepth ? std::min(name.size(), getMaxDepth()) : name.size();
48 
49  HashSequence hashes = computeHashes(name, depth);
50  const Node* node = nullptr;
51  Entry* parent = nullptr;
52 
53  for (size_t prefixLen = 0; prefixLen <= depth; ++prefixLen) {
54  bool isNew = false;
55  std::tie(node, isNew) = m_ht.insert(name, prefixLen, 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  Entry* nte = this->getEntry(fibEntry);
69  if (nte == nullptr) {
70  // special case: Fib::s_emptyEntry is unattached
71  BOOST_ASSERT(fibEntry.getPrefix().empty());
72  return this->lookup(fibEntry.getPrefix());
73  }
74 
75  BOOST_ASSERT(nte->getFibEntry() == &fibEntry);
76  return *nte;
77 }
78 
79 Entry&
80 NameTree::lookup(const pit::Entry& pitEntry)
81 {
82  Entry* nte = this->getEntry(pitEntry);
83  BOOST_ASSERT(nte != nullptr);
84 
85  BOOST_ASSERT(std::count_if(nte->getPitEntries().begin(), nte->getPitEntries().end(),
86  [&pitEntry] (const shared_ptr<pit::Entry>& pitEntry1) {
87  return pitEntry1.get() == &pitEntry;
88  }) == 1);
89 
90  if (nte->getName().size() == pitEntry.getName().size()) {
91  return *nte;
92  }
93 
94  // special case: PIT entry whose Interest name ends with an implicit digest
95  // are attached to the name tree entry with one-shorter-prefix.
96  BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
97  BOOST_ASSERT(nte->getName() == pitEntry.getName().getPrefix(-1));
98  return this->lookup(pitEntry.getName());
99 }
100 
101 Entry&
102 NameTree::lookup(const measurements::Entry& measurementsEntry)
103 {
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  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  const Node* node = m_ht.find(name, std::min(name.size(), prefixLen));
152  return node == nullptr ? nullptr : &node->entry;
153 }
154 
155 Entry*
156 NameTree::findLongestPrefixMatch(const Name& name, const EntrySelector& entrySelector) const
157 {
158  HashSequence hashes = computeHashes(name);
159 
160  for (ssize_t prefixLen = name.size(); prefixLen >= 0; --prefixLen) {
161  const Node* node = m_ht.find(name, prefixLen, hashes);
162  if (node != nullptr && entrySelector(node->entry)) {
163  return &node->entry;
164  }
165  }
166 
167  return nullptr;
168 }
169 
170 Entry*
171 NameTree::findLongestPrefixMatch(const Entry& entry1, const EntrySelector& entrySelector) const
172 {
173  Entry* entry = const_cast<Entry*>(&entry1);
174  while (entry != nullptr) {
175  if (entrySelector(*entry)) {
176  return entry;
177  }
178  entry = entry->getParent();
179  }
180  return nullptr;
181 }
182 
183 Entry*
184 NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry, const EntrySelector& entrySelector) const
185 {
186  const Entry* nte = this->getEntry(pitEntry);
187  BOOST_ASSERT(nte != nullptr);
188 
189  // PIT entry Interest name either exceeds depth limit or ends with an implicit digest: go deeper
190  if (nte->getName().size() < pitEntry.getName().size()) {
191  for (size_t prefixLen = nte->getName().size() + 1; prefixLen <= pitEntry.getName().size(); ++prefixLen) {
192  const Entry* exact = this->findExactMatch(pitEntry.getName(), prefixLen);
193  if (exact == nullptr) {
194  break;
195  }
196  nte = exact;
197  }
198  }
199 
200  return this->findLongestPrefixMatch(*nte, entrySelector);
201 }
202 
203 boost::iterator_range<NameTree::const_iterator>
204 NameTree::findAllMatches(const Name& name, const EntrySelector& entrySelector) const
205 {
206  // As we are using Name Prefix Hash Table, and the current LPM() is
207  // implemented as starting from full name, and reduce the number of
208  // components by 1 each time, we could use it here.
209  // For trie-like design, it could be more efficient by walking down the
210  // trie from the root node.
211 
212  Entry* entry = this->findLongestPrefixMatch(name, entrySelector);
213  return {Iterator(make_shared<PrefixMatchImpl>(*this, entrySelector), entry), end()};
214 }
215 
216 boost::iterator_range<NameTree::const_iterator>
217 NameTree::fullEnumerate(const EntrySelector& entrySelector) const
218 {
219  return {Iterator(make_shared<FullEnumerationImpl>(*this, entrySelector), nullptr), end()};
220 }
221 
222 boost::iterator_range<NameTree::const_iterator>
223 NameTree::partialEnumerate(const Name& prefix,
224  const EntrySubTreeSelector& entrySubTreeSelector) const
225 {
226  Entry* entry = this->findExactMatch(prefix);
227  return {Iterator(make_shared<PartialEnumerationImpl>(*this, entrySubTreeSelector), entry), end()};
228 }
229 
230 } // namespace name_tree
231 } // namespace nfd
void unsetParent()
unset parent of this entry
bool isEmpty() const
Entry * findLongestPrefixMatch(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
longest prefix matching
Definition: name-tree.cpp:156
represents a Measurements entry
Entry & lookup(const Name &name, bool enforceMaxDepth=false)
find or insert an entry with specified name
Definition: name-tree.cpp:44
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
delete the entry if it is empty
Definition: name-tree.cpp:122
Entry * getEntry(const EntryT &tableEntry) const
Definition: name-tree.hpp:80
represents a FIB entry
Definition: fib-entry.hpp:51
HashSequence computeHashes(const Name &name, size_t prefixLen)
computes hash values for each prefix of name.getPrefix(prefixLen)
function< std::pair< bool, bool >const Entry &entry)> EntrySubTreeSelector
a predicate to accept or reject an Entry and its children
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
enumerate all entries
Definition: name-tree.cpp:217
void setParent(Entry &entry)
set parent of this entry
strategy_choice::Entry * getStrategyChoiceEntry() const
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:223
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:149
Entry * getParent() const
static size_t getMaxDepth()
Maximum depth of the name tree.
Definition: name-tree.hpp:54
fib::Entry * getFibEntry() const
an Interest table entry
Definition: pit-entry.hpp:57
const Name & getPrefix() const
Definition: fib-entry.hpp:58
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)
function< bool(const Entry &entry)> EntrySelector
a predicate to accept or reject an Entry in find operations
Range findAllMatches(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
all-prefixes match lookup
Definition: name-tree.cpp:204
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
measurements::Entry * getMeasurementsEntry() const
#define NFD_LOG_INIT(name)
Definition: logger.hpp:122
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:160
void erase(Node *node)
delete node
const Name & getName() const
const Name & getName() const
Definition: pit-entry.hpp:77
NameTree(size_t nBuckets=1024)
Definition: name-tree.cpp:38
const_iterator end() const
Definition: name-tree.hpp:263