blob: 2f404bf5cde784eb31f41707d919bdc68fbabd1b [file] [log] [blame]
HYuana9b85752014-02-26 02:32:30 -06001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -07003 * Copyright (c) 2014 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 *
10 * This file is part of NFD (Named Data Networking Forwarding Daemon).
11 * See AUTHORS.md for complete list of NFD authors and contributors.
12 *
13 * NFD is free software: you can redistribute it and/or modify it under the terms
14 * of the GNU General Public License as published by the Free Software Foundation,
15 * either version 3 of the License, or (at your option) any later version.
16 *
17 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
18 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
19 * PURPOSE. See the GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License along with
22 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
23 **/
HYuana9b85752014-02-26 02:32:30 -060024
25// Name Tree (Name Prefix Hash Table)
26
Alexander Afanasyev613e2a92014-04-15 13:36:58 -070027#ifndef NFD_DAEMON_TABLE_NAME_TREE_HPP
28#define NFD_DAEMON_TABLE_NAME_TREE_HPP
HYuana9b85752014-02-26 02:32:30 -060029
30#include "common.hpp"
31#include "name-tree-entry.hpp"
32
33namespace nfd {
34namespace name_tree {
35
36/**
Haowei Yuanf52dac72014-03-24 23:35:03 -050037 * \brief Compute the hash value of the given name prefix's WIRE FORMAT
HYuana9b85752014-02-26 02:32:30 -060038 */
Haowei Yuanf52dac72014-03-24 23:35:03 -050039size_t
40computeHash(const Name& prefix);
41
42/**
43 * \brief Incrementally compute hash values
44 * \return Return a vector of hash values, starting from the root prefix
45 */
46std::vector<size_t>
47computeHashSet(const Name& prefix);
HYuana9b85752014-02-26 02:32:30 -060048
Junxiao Shi40631842014-03-01 13:52:37 -070049/// a predicate to accept or reject an Entry in find operations
50typedef function<bool (const Entry& entry)> EntrySelector;
51
Haowei Yuane1079fc2014-03-08 14:41:25 -060052/**
53 * \brief a predicate to accept or reject an Entry and its children
54 * \return .first indicates whether entry should be accepted;
55 * .second indicates whether entry's children should be visited
56 */
57typedef function<std::pair<bool,bool> (const Entry& entry)> EntrySubTreeSelector;
58
Junxiao Shi40631842014-03-01 13:52:37 -070059struct AnyEntry {
60 bool
61 operator()(const Entry& entry)
62 {
63 return true;
64 }
65};
66
Haowei Yuane1079fc2014-03-08 14:41:25 -060067struct AnyEntrySubTree {
68 std::pair<bool, bool>
69 operator()(const Entry& entry)
70 {
71 return std::make_pair(true, true);
72 }
73};
74
HYuana9b85752014-02-26 02:32:30 -060075} // namespace name_tree
76
77/**
Haowei Yuane1079fc2014-03-08 14:41:25 -060078 * \brief Class Name Tree
HYuana9b85752014-02-26 02:32:30 -060079 */
80class NameTree : noncopyable
81{
82public:
Haowei Yuane1079fc2014-03-08 14:41:25 -060083 class const_iterator;
84
HYuana9b85752014-02-26 02:32:30 -060085 explicit
Haowei Yuanf52dac72014-03-24 23:35:03 -050086 NameTree(size_t nBuckets = 1024);
HYuana9b85752014-02-26 02:32:30 -060087
88 ~NameTree();
89
90 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -060091 * \brief Get the number of occupied entries in the Name Tree
HYuana9b85752014-02-26 02:32:30 -060092 */
93 size_t
94 size() const;
95
96 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -060097 * \brief Get the number of buckets in the Name Tree (NPHT)
98 * \details The number of buckets is the one that used to create the hash
HYuana9b85752014-02-26 02:32:30 -060099 * table, i.e., m_nBuckets.
100 */
101 size_t
102 getNBuckets() const;
103
104 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -0600105 * \brief Look for the Name Tree Entry that contains this name prefix.
106 * \details Starts from the shortest name prefix, and then increase the
HYuana9b85752014-02-26 02:32:30 -0600107 * number of name components by one each time. All non-existing Name Tree
108 * Entries will be created.
Haowei Yuane1079fc2014-03-08 14:41:25 -0600109 * \param prefix The querying name prefix.
110 * \return The pointer to the Name Tree Entry that contains this full name
HYuana9b85752014-02-26 02:32:30 -0600111 * prefix.
112 */
113 shared_ptr<name_tree::Entry>
114 lookup(const Name& prefix);
115
116 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -0600117 * \brief Exact match lookup for the given name prefix.
118 * \return a null shared_ptr if this prefix is not found;
HYuana9b85752014-02-26 02:32:30 -0600119 * otherwise return the Name Tree Entry address
120 */
121 shared_ptr<name_tree::Entry>
122 findExactMatch(const Name& prefix) const;
123
Junxiao Shiefceadc2014-03-09 18:52:57 -0700124 shared_ptr<name_tree::Entry>
125 findExactMatch(const fib::Entry& fibEntry) const;
126
HYuana9b85752014-02-26 02:32:30 -0600127 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -0600128 * \brief Erase a Name Tree Entry if this entry is empty.
129 * \details If a Name Tree Entry contains no Children, no FIB, no PIT, and
HYuana9b85752014-02-26 02:32:30 -0600130 * no Measurements entries, then it can be erased. In addition, its parent entry
131 * will also be examined by following the parent pointer until all empty entries
132 * are erased.
Haowei Yuane1079fc2014-03-08 14:41:25 -0600133 * \param entry The pointer to the entry to be erased. The entry pointer should
HYuana9b85752014-02-26 02:32:30 -0600134 * returned by the findExactMatch(), lookup(), or findLongestPrefixMatch() functions.
135 */
136 bool
137 eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry);
138
139 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -0600140 * \brief Longest prefix matching for the given name
141 * \details Starts from the full name string, reduce the number of name component
HYuana9b85752014-02-26 02:32:30 -0600142 * by one each time, until an Entry is found.
143 */
144 shared_ptr<name_tree::Entry>
Junxiao Shi40631842014-03-01 13:52:37 -0700145 findLongestPrefixMatch(const Name& prefix,
Haowei Yuane1079fc2014-03-08 14:41:25 -0600146 const name_tree::EntrySelector& entrySelector =
147 name_tree::AnyEntry()) const;
HYuana9b85752014-02-26 02:32:30 -0600148
HangZhangcb4fc832014-03-11 16:57:11 +0800149 shared_ptr<name_tree::Entry>
150 findLongestPrefixMatch(shared_ptr<name_tree::Entry> entry,
151 const name_tree::EntrySelector& entrySelector =
152 name_tree::AnyEntry()) const;
153
HYuana9b85752014-02-26 02:32:30 -0600154 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -0600155 * \brief Resize the hash table size when its load factor reaches a threshold.
156 * \details As we are currently using a hand-written hash table implementation
HYuana9b85752014-02-26 02:32:30 -0600157 * for the Name Tree, the hash table resize() function should be kept in the
158 * name-tree.hpp file.
Haowei Yuane1079fc2014-03-08 14:41:25 -0600159 * \param newNBuckets The number of buckets for the new hash table.
HYuana9b85752014-02-26 02:32:30 -0600160 */
161 void
162 resize(size_t newNBuckets);
163
164 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -0600165 * \brief Enumerate all the name prefixes stored in the Name Tree.
HYuana9b85752014-02-26 02:32:30 -0600166 */
Haowei Yuane1079fc2014-03-08 14:41:25 -0600167 const_iterator
168 fullEnumerate(const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
HYuana9b85752014-02-26 02:32:30 -0600169
170 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -0600171 * \brief Enumerate all the name prefixes that satisfies the EntrySubTreeSelector.
172 */
173 const_iterator
Junxiao Shi40631842014-03-01 13:52:37 -0700174 partialEnumerate(const Name& prefix,
Junxiao Shiefceadc2014-03-09 18:52:57 -0700175 const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
176 name_tree::AnyEntrySubTree()) const;
HYuana9b85752014-02-26 02:32:30 -0600177
178 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -0600179 * \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
180 */
181 const_iterator
182 findAllMatches(const Name& prefix,
183 const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
184
185 /**
186 * \brief Dump all the information stored in the Name Tree for debugging.
HYuana9b85752014-02-26 02:32:30 -0600187 */
188 void
Haowei Yuane1079fc2014-03-08 14:41:25 -0600189 dump(std::ostream& output) const;
190
HangZhangcb4fc832014-03-11 16:57:11 +0800191 shared_ptr<name_tree::Entry>
192 get(const fib::Entry& fibEntry) const;
193
194 shared_ptr<name_tree::Entry>
195 get(const pit::Entry& pitEntry) const;
196
197 shared_ptr<name_tree::Entry>
198 get(const measurements::Entry& measurementsEntry) const;
199
200 shared_ptr<name_tree::Entry>
201 get(const strategy_choice::Entry& strategeChoiceEntry) const;
202
Haowei Yuane1079fc2014-03-08 14:41:25 -0600203 const_iterator
204 begin() const;
205
206 const_iterator
207 end() const;
208
209 enum IteratorType
210 {
211 FULL_ENUMERATE_TYPE,
212 PARTIAL_ENUMERATE_TYPE,
213 FIND_ALL_MATCHES_TYPE
214 };
215
216 class const_iterator : public std::iterator<std::forward_iterator_tag, name_tree::Entry>
217 {
218 public:
219 friend class NameTree;
220
221 const_iterator(NameTree::IteratorType type,
222 const NameTree& nameTree,
223 shared_ptr<name_tree::Entry> entry,
224 const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry(),
225 const name_tree::EntrySubTreeSelector& entrySubTreeSelector = name_tree::AnyEntrySubTree());
226
227 ~const_iterator();
228
229 const name_tree::Entry&
230 operator*() const;
231
232 shared_ptr<name_tree::Entry>
233 operator->() const;
234
235 const_iterator
236 operator++();
237
238 const_iterator
239 operator++(int);
240
241 bool
242 operator==(const const_iterator& other) const;
243
244 bool
245 operator!=(const const_iterator& other) const;
246
247 private:
Haowei Yuane1079fc2014-03-08 14:41:25 -0600248 const NameTree& m_nameTree;
249 shared_ptr<name_tree::Entry> m_entry;
250 shared_ptr<name_tree::Entry> m_subTreeRoot;
251 shared_ptr<name_tree::EntrySelector> m_entrySelector;
252 shared_ptr<name_tree::EntrySubTreeSelector> m_entrySubTreeSelector;
253 NameTree::IteratorType m_type;
Junxiao Shiefceadc2014-03-09 18:52:57 -0700254 bool m_shouldVisitChildren;
Haowei Yuane1079fc2014-03-08 14:41:25 -0600255 };
HYuana9b85752014-02-26 02:32:30 -0600256
257private:
Haowei Yuane1079fc2014-03-08 14:41:25 -0600258 size_t m_nItems; // Number of items being stored
259 size_t m_nBuckets; // Number of hash buckets
Haowei Yuanf52dac72014-03-24 23:35:03 -0500260 size_t m_minNBuckets; // Minimum number of hash buckets
261 double m_enlargeLoadFactor;
262 size_t m_enlargeThreshold;
263 int m_enlargeFactor;
264 double m_shrinkLoadFactor;
265 size_t m_shrinkThreshold;
266 double m_shrinkFactor;
Haowei Yuane1079fc2014-03-08 14:41:25 -0600267 name_tree::Node** m_buckets; // Name Tree Buckets in the NPHT
268 shared_ptr<name_tree::Entry> m_end;
269 const_iterator m_endIterator;
HYuana9b85752014-02-26 02:32:30 -0600270
271 /**
Haowei Yuane1079fc2014-03-08 14:41:25 -0600272 * \brief Create a Name Tree Entry if it does not exist, or return the existing
HYuana9b85752014-02-26 02:32:30 -0600273 * Name Tree Entry address.
Haowei Yuane1079fc2014-03-08 14:41:25 -0600274 * \details Called by lookup() only.
275 * \return The first item is the Name Tree Entry address, the second item is
HYuana9b85752014-02-26 02:32:30 -0600276 * a bool value indicates whether this is an old entry (false) or a new
277 * entry (true).
278 */
279 std::pair<shared_ptr<name_tree::Entry>, bool>
280 insert(const Name& prefix);
HYuana9b85752014-02-26 02:32:30 -0600281};
282
Haowei Yuane1079fc2014-03-08 14:41:25 -0600283inline NameTree::const_iterator::~const_iterator()
284{
285}
286
HYuana9b85752014-02-26 02:32:30 -0600287inline size_t
288NameTree::size() const
289{
290 return m_nItems;
291}
292
293inline size_t
294NameTree::getNBuckets() const
295{
296 return m_nBuckets;
297}
298
Junxiao Shiefceadc2014-03-09 18:52:57 -0700299inline shared_ptr<name_tree::Entry>
300NameTree::findExactMatch(const fib::Entry& fibEntry) const
301{
302 return fibEntry.m_nameTreeEntry;
303}
304
HangZhangcb4fc832014-03-11 16:57:11 +0800305inline shared_ptr<name_tree::Entry>
306NameTree::get(const fib::Entry& fibEntry) const
307{
308 return fibEntry.m_nameTreeEntry;
309}
310
311inline shared_ptr<name_tree::Entry>
312NameTree::get(const pit::Entry& pitEntry) const
313{
314 return pitEntry.m_nameTreeEntry;
315}
316
317inline shared_ptr<name_tree::Entry>
318NameTree::get(const measurements::Entry& measurementsEntry) const
319{
320 return measurementsEntry.m_nameTreeEntry;
321}
322
323inline shared_ptr<name_tree::Entry>
324NameTree::get(const strategy_choice::Entry& strategeChoiceEntry) const
325{
326 return strategeChoiceEntry.m_nameTreeEntry;
327}
328
Haowei Yuane1079fc2014-03-08 14:41:25 -0600329inline NameTree::const_iterator
330NameTree::begin() const
331{
332 return fullEnumerate();
333}
334
335inline NameTree::const_iterator
336NameTree::end() const
337{
338 return m_endIterator;
339}
340
341inline const name_tree::Entry&
342NameTree::const_iterator::operator*() const
343{
344 return *m_entry;
345}
346
347inline shared_ptr<name_tree::Entry>
348NameTree::const_iterator::operator->() const
349{
350 return m_entry;
351}
352
353inline NameTree::const_iterator
354NameTree::const_iterator::operator++(int)
355{
356 NameTree::const_iterator temp(*this);
357 ++(*this);
358 return temp;
359}
360
361inline bool
362NameTree::const_iterator::operator==(const NameTree::const_iterator& other) const
363{
364 return m_entry == other.m_entry;
365}
366
367inline bool
368NameTree::const_iterator::operator!=(const NameTree::const_iterator& other) const
369{
370 return m_entry != other.m_entry;
371}
372
HYuana9b85752014-02-26 02:32:30 -0600373} // namespace nfd
374
Alexander Afanasyev613e2a92014-04-15 13:36:58 -0700375#endif // NFD_DAEMON_TABLE_NAME_TREE_HPP