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-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 #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
53  static size_t
55  {
56  return 32;
57  }
58 
61  size_t
62  size() const
63  {
64  return m_ht.size();
65  }
66 
69  size_t
70  getNBuckets() const
71  {
72  return m_ht.getNBuckets();
73  }
74 
78  template<typename EntryT>
79  Entry*
80  getEntry(const EntryT& tableEntry) const
81  {
82  return Entry::get(tableEntry);
83  }
84 
85 public: // mutation
93  Entry&
94  lookup(const Name& name, bool enforceMaxDepth = false);
95 
100  Entry&
101  lookup(const fib::Entry& fibEntry);
102 
107  Entry&
108  lookup(const pit::Entry& pitEntry);
109 
114  Entry&
115  lookup(const measurements::Entry& measurementsEntry);
116 
121  Entry&
122  lookup(const strategy_choice::Entry& strategyChoiceEntry);
123 
134  size_t
135  eraseIfEmpty(Entry* entry, bool canEraseAncestors = true);
136 
137 public: // matching
141  Entry*
142  findExactMatch(const Name& name, size_t prefixLen = std::numeric_limits<size_t>::max()) const;
143 
149  Entry*
150  findLongestPrefixMatch(const Name& name,
151  const EntrySelector& entrySelector = AnyEntry()) const;
152 
157  Entry*
158  findLongestPrefixMatch(const Entry& entry,
159  const EntrySelector& entrySelector = AnyEntry()) const;
160 
167  template<typename EntryT>
168  Entry*
169  findLongestPrefixMatch(const EntryT& tableEntry,
170  const EntrySelector& entrySelector = AnyEntry()) const
171  {
172  const Entry* nte = this->getEntry(tableEntry);
173  BOOST_ASSERT(nte != nullptr);
174  return this->findLongestPrefixMatch(*nte, entrySelector);
175  }
176 
182  Entry*
183  findLongestPrefixMatch(const pit::Entry& pitEntry,
184  const EntrySelector& entrySelector = AnyEntry()) const;
185 
205  Range
206  findAllMatches(const Name& name,
207  const EntrySelector& entrySelector = AnyEntry()) const;
208 
209 public: // enumeration
211 
226  Range
227  fullEnumerate(const EntrySelector& entrySelector = AnyEntry()) const;
228 
246  Range
247  partialEnumerate(const Name& prefix,
248  const EntrySubTreeSelector& entrySubTreeSelector = AnyEntrySubTree()) const;
249 
254  begin() const
255  {
256  return fullEnumerate().begin();
257  }
258 
263  end() const
264  {
265  return Iterator();
266  }
267 
268 private:
269  Hashtable m_ht;
270 
271  friend class EnumerationImpl;
272 };
273 
274 } // namespace name_tree
275 
276 using name_tree::NameTree;
277 
278 } // namespace nfd
279 
280 #endif // NFD_DAEMON_TABLE_NAME_TREE_HPP
an EntrySelector that accepts every Entry
Entry * findLongestPrefixMatch(const EntryT &tableEntry, const EntrySelector &entrySelector=AnyEntry()) const
equivalent to .findLongestPrefixMatch(getEntry(tableEntry)->getName(), entrySelector) ...
Definition: name-tree.hpp:169
a common index structure for FIB, PIT, StrategyChoice, and Measurements
Definition: name-tree.hpp:36
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
size_t getNBuckets() const
Definition: name-tree.hpp:70
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
Range partialEnumerate(const Name &prefix, const EntrySubTreeSelector &entrySubTreeSelector=AnyEntrySubTree()) const
enumerate all entries under a prefix
Definition: name-tree.cpp:223
const_iterator begin() const
Definition: name-tree.hpp:254
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
exact match lookup
Definition: name-tree.cpp:149
static size_t getMaxDepth()
Maximum depth of the name tree.
Definition: name-tree.hpp:54
enumeration operation implementation
an Interest table entry
Definition: pit-entry.hpp:57
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
an EntrySubTreeSelector that accepts every Entry and its children
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
size_t size() const
Definition: name-tree.hpp:62
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
NameTree(size_t nBuckets=1024)
Definition: name-tree.cpp:38
a hashtable for fast exact name lookup
const_iterator end() const
Definition: name-tree.hpp:263