name-tree.hpp
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 #ifndef NFD_DAEMON_TABLE_NAME_TREE_HPP
27 #define NFD_DAEMON_TABLE_NAME_TREE_HPP
28 
29 #include "name-tree-iterator.hpp"
30 
31 namespace nfd {
32 namespace name_tree {
33 
36 class NameTree : noncopyable
37 {
38 public:
39  explicit
40  NameTree(size_t nBuckets = 1024);
41 
42 public: // information
50  static constexpr size_t
52  {
53  return 32;
54  }
55 
58  size_t
59  size() const
60  {
61  return m_ht.size();
62  }
63 
66  size_t
67  getNBuckets() const
68  {
69  return m_ht.getNBuckets();
70  }
71 
75  template<typename EntryT>
76  Entry*
77  getEntry(const EntryT& tableEntry) const
78  {
79  return Entry::get(tableEntry);
80  }
81 
82 public: // mutation
92  Entry&
93  lookup(const Name& name, size_t prefixLen);
94 
97  Entry&
98  lookup(const Name& name)
99  {
100  return this->lookup(name, name.size());
101  }
102 
107  Entry&
108  lookup(const fib::Entry& fibEntry);
109 
114  Entry&
115  lookup(const pit::Entry& pitEntry);
116 
121  Entry&
122  lookup(const measurements::Entry& measurementsEntry);
123 
128  Entry&
129  lookup(const strategy_choice::Entry& strategyChoiceEntry);
130 
141  size_t
142  eraseIfEmpty(Entry* entry, bool canEraseAncestors = true);
143 
144 public: // matching
148  Entry*
149  findExactMatch(const Name& name, size_t prefixLen = std::numeric_limits<size_t>::max()) const;
150 
156  Entry*
157  findLongestPrefixMatch(const Name& name,
158  const EntrySelector& entrySelector = AnyEntry()) const;
159 
164  Entry*
165  findLongestPrefixMatch(const Entry& entry,
166  const EntrySelector& entrySelector = AnyEntry()) const;
167 
174  template<typename EntryT>
175  Entry*
176  findLongestPrefixMatch(const EntryT& tableEntry,
177  const EntrySelector& entrySelector = AnyEntry()) const
178  {
179  const Entry* nte = this->getEntry(tableEntry);
180  BOOST_ASSERT(nte != nullptr);
181  return this->findLongestPrefixMatch(*nte, entrySelector);
182  }
183 
189  Entry*
190  findLongestPrefixMatch(const pit::Entry& pitEntry,
191  const EntrySelector& entrySelector = AnyEntry()) const;
192 
212  Range
213  findAllMatches(const Name& name,
214  const EntrySelector& entrySelector = AnyEntry()) const;
215 
216 public: // enumeration
218 
233  Range
234  fullEnumerate(const EntrySelector& entrySelector = AnyEntry()) const;
235 
253  Range
254  partialEnumerate(const Name& prefix,
255  const EntrySubTreeSelector& entrySubTreeSelector = AnyEntrySubTree()) const;
256 
261  begin() const
262  {
263  return fullEnumerate().begin();
264  }
265 
270  end() const
271  {
272  return Iterator();
273  }
274 
275 private:
276  Hashtable m_ht;
277 
278  friend class EnumerationImpl;
279 };
280 
281 } // namespace name_tree
282 
283 using name_tree::NameTree;
284 
285 } // namespace nfd
286 
287 #endif // NFD_DAEMON_TABLE_NAME_TREE_HPP
an EntrySelector that accepts every Entry
A common index structure for FIB, PIT, StrategyChoice, and Measurements.
Definition: name-tree.hpp:36
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 * findLongestPrefixMatch(const EntryT &tableEntry, const EntrySelector &entrySelector=AnyEntry()) const
Equivalent to findLongestPrefixMatch(getEntry(tableEntry)->getName(), entrySelector) ...
Definition: name-tree.hpp:176
represents a FIB entry
Definition: fib-entry.hpp:53
static constexpr size_t getMaxDepth()
Maximum depth of the name tree.
Definition: name-tree.hpp:51
Entry & lookup(const Name &name)
Equivalent to lookup(name, name.size())
Definition: name-tree.hpp:98
Entry * getEntry(const EntryT &tableEntry) const
Definition: name-tree.hpp:77
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
Enumerate all entries.
Definition: name-tree.cpp:226
const_iterator end() const
Definition: name-tree.hpp:270
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
Exact match lookup.
Definition: name-tree.cpp:150
enumeration operation implementation
An Interest table entry.
Definition: pit-entry.hpp:58
Entry & lookup(const Name &name, size_t prefixLen)
Find or insert an entry by name.
Definition: name-tree.cpp:44
const_iterator begin() const
Definition: name-tree.hpp:261
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
Range partialEnumerate(const Name &prefix, const EntrySubTreeSelector &entrySubTreeSelector=AnyEntrySubTree()) const
Enumerate all entries under a prefix.
Definition: name-tree.cpp:232
size_t size() const
Definition: name-tree.hpp:59
size_t getNBuckets() const
Definition: name-tree.hpp:67
an EntrySubTreeSelector that accepts every Entry and its children
Entry * findLongestPrefixMatch(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
Longest prefix matching.
Definition: name-tree.cpp:162
An entry in the name tree.
Represents a Strategy Choice entry.
static Entry * get(const ENTRY &tableEntry)
boost::iterator_range< Iterator > Range
a Forward Range of name tree entries
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.
Definition: name-tree.cpp:213
std::function< bool(const Entry &)> EntrySelector
a predicate to accept or reject an Entry in find operations
NameTree(size_t nBuckets=1024)
Definition: name-tree.cpp:38
a hashtable for fast exact name lookup