NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: NDN, CCN, CCNx, content centric networks
API Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
name-tree.hpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #ifndef NFD_DAEMON_TABLE_NAME_TREE_HPP
27 #define NFD_DAEMON_TABLE_NAME_TREE_HPP
28 
29 #include "common.hpp"
30 #include "name-tree-entry.hpp"
31 
32 namespace nfd {
33 namespace name_tree {
34 
38 size_t
39 computeHash(const Name& prefix);
40 
45 std::vector<size_t>
46 computeHashSet(const Name& prefix);
47 
49 typedef function<bool (const Entry& entry)> EntrySelector;
50 
56 typedef function<std::pair<bool,bool> (const Entry& entry)> EntrySubTreeSelector;
57 
58 struct AnyEntry {
59  bool
60  operator()(const Entry& entry)
61  {
62  return true;
63  }
64 };
65 
67  std::pair<bool, bool>
68  operator()(const Entry& entry)
69  {
70  return std::make_pair(true, true);
71  }
72 };
73 
74 } // namespace name_tree
75 
79 class NameTree : noncopyable
80 {
81 public:
82  class const_iterator;
83 
84  explicit
85  NameTree(size_t nBuckets = 1024);
86 
87  ~NameTree();
88 
89 public: // information
93  size_t
94  size() const;
95 
101  size_t
102  getNBuckets() const;
103 
107  void
108  dump(std::ostream& output) const;
109 
110 public: // mutation
121  shared_ptr<name_tree::Entry>
122  lookup(const Name& prefix);
123 
132  bool
133  eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry);
134 
135 public: // shortcut access
137  shared_ptr<name_tree::Entry>
138  get(const fib::Entry& fibEntry) const;
139 
141  shared_ptr<name_tree::Entry>
142  get(const pit::Entry& pitEntry) const;
143 
145  shared_ptr<name_tree::Entry>
146  get(const measurements::Entry& measurementsEntry) const;
147 
149  shared_ptr<name_tree::Entry>
150  get(const strategy_choice::Entry& strategyChoiceEntry) const;
151 
152 public: // matching
158  shared_ptr<name_tree::Entry>
159  findExactMatch(const Name& prefix) const;
160 
166  shared_ptr<name_tree::Entry>
167  findLongestPrefixMatch(const Name& prefix,
168  const name_tree::EntrySelector& entrySelector =
169  name_tree::AnyEntry()) const;
170 
171  shared_ptr<name_tree::Entry>
172  findLongestPrefixMatch(shared_ptr<name_tree::Entry> entry,
173  const name_tree::EntrySelector& entrySelector =
174  name_tree::AnyEntry()) const;
175 
190  boost::iterator_range<const_iterator>
191  findAllMatches(const Name& prefix,
192  const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
193 
194 public: // enumeration
209  boost::iterator_range<const_iterator>
210  fullEnumerate(const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
211 
226  boost::iterator_range<const_iterator>
227  partialEnumerate(const Name& prefix,
228  const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
230 
236  begin() const;
237 
243  end() const;
244 
249  };
250 
251  class const_iterator : public std::iterator<std::forward_iterator_tag, const name_tree::Entry>
252  {
253  public:
254  friend class NameTree;
255 
256  const_iterator();
257 
259  const NameTree& nameTree,
260  shared_ptr<name_tree::Entry> entry,
261  const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry(),
262  const name_tree::EntrySubTreeSelector& entrySubTreeSelector = name_tree::AnyEntrySubTree());
263 
264  ~const_iterator();
265 
266  const name_tree::Entry&
267  operator*() const;
268 
269  shared_ptr<name_tree::Entry>
270  operator->() const;
271 
273  operator++();
274 
276  operator++(int);
277 
278  bool
279  operator==(const const_iterator& other) const;
280 
281  bool
282  operator!=(const const_iterator& other) const;
283 
284  private:
285  const NameTree* m_nameTree;
286  shared_ptr<name_tree::Entry> m_entry;
287  shared_ptr<name_tree::Entry> m_subTreeRoot;
288  shared_ptr<name_tree::EntrySelector> m_entrySelector;
289  shared_ptr<name_tree::EntrySubTreeSelector> m_entrySubTreeSelector;
290  NameTree::IteratorType m_type;
291  bool m_shouldVisitChildren;
292  };
293 
294 private:
302  void
303  resize(size_t newNBuckets);
304 
305 private:
306  size_t m_nItems; // Number of items being stored
307  size_t m_nBuckets; // Number of hash buckets
308  size_t m_minNBuckets; // Minimum number of hash buckets
309  double m_enlargeLoadFactor;
310  size_t m_enlargeThreshold;
311  int m_enlargeFactor;
312  double m_shrinkLoadFactor;
313  size_t m_shrinkThreshold;
314  double m_shrinkFactor;
315  name_tree::Node** m_buckets; // Name Tree Buckets in the NPHT
316  shared_ptr<name_tree::Entry> m_end;
317  const_iterator m_endIterator;
318 
327  std::pair<shared_ptr<name_tree::Entry>, bool>
328  insert(const Name& prefix);
329 };
330 
332 {
333 }
334 
335 inline size_t
337 {
338  return m_nItems;
339 }
340 
341 inline size_t
343 {
344  return m_nBuckets;
345 }
346 
347 inline shared_ptr<name_tree::Entry>
348 NameTree::get(const fib::Entry& fibEntry) const
349 {
350  return fibEntry.m_nameTreeEntry;
351 }
352 
353 inline shared_ptr<name_tree::Entry>
354 NameTree::get(const pit::Entry& pitEntry) const
355 {
356  return pitEntry.m_nameTreeEntry;
357 }
358 
359 inline shared_ptr<name_tree::Entry>
360 NameTree::get(const measurements::Entry& measurementsEntry) const
361 {
362  return measurementsEntry.m_nameTreeEntry;
363 }
364 
365 inline shared_ptr<name_tree::Entry>
366 NameTree::get(const strategy_choice::Entry& strategyChoiceEntry) const
367 {
368  return strategyChoiceEntry.m_nameTreeEntry;
369 }
370 
373 {
374  return fullEnumerate().begin();
375 }
376 
379 {
380  return m_endIterator;
381 }
382 
383 inline const name_tree::Entry&
385 {
386  return *m_entry;
387 }
388 
389 inline shared_ptr<name_tree::Entry>
391 {
392  return m_entry;
393 }
394 
397 {
398  NameTree::const_iterator temp(*this);
399  ++(*this);
400  return temp;
401 }
402 
403 inline bool
405 {
406  return m_entry == other.m_entry;
407 }
408 
409 inline bool
411 {
412  return m_entry != other.m_entry;
413 }
414 
415 } // namespace nfd
416 
417 #endif // NFD_DAEMON_TABLE_NAME_TREE_HPP
bool operator==(const const_iterator &other) const
Definition: name-tree.hpp:404
boost::iterator_range< const_iterator > partialEnumerate(const Name &prefix, const name_tree::EntrySubTreeSelector &entrySubTreeSelector=name_tree::AnyEntrySubTree()) const
Enumerate all entries under a prefix, optionally filtered by an EntrySubTreeSelector.
Definition: name-tree.cpp:425
size_t computeHash(const Name &prefix)
Compute the hash value of the given name prefix's WIRE FORMAT.
Definition: name-tree.cpp:75
NameTree(size_t nBuckets=1024)
Definition: name-tree.cpp:116
Name Tree Node Class.
const_iterator begin() const
Get an iterator pointing to the first NameTree entry.
Definition: name-tree.hpp:372
represents a FIB entry
Definition: fib-entry.hpp:53
bool eraseEntryIfEmpty(shared_ptr< name_tree::Entry > entry)
Delete a Name Tree Entry if this entry is empty.
Definition: name-tree.cpp:327
shared_ptr< name_tree::Entry > get(const fib::Entry &fibEntry) const
get NameTree entry from attached FIB entry
Definition: name-tree.hpp:348
boost::iterator_range< const_iterator > findAllMatches(const Name &prefix, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
Enumerate all the name prefixes that satisfy the prefix and entrySelector.
Definition: name-tree.cpp:454
function< std::pair< bool, bool >const Entry &entry)> EntrySubTreeSelector
a predicate to accept or reject an Entry and its children
Definition: name-tree.hpp:56
const_iterator end() const
Get an iterator referring to the past-the-end FIB entry.
Definition: name-tree.hpp:378
const name_tree::Entry & operator*() const
Definition: name-tree.hpp:384
shared_ptr< name_tree::Entry > findLongestPrefixMatch(const Name &prefix, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
Longest prefix matching for the given name.
Definition: name-tree.cpp:275
std::vector< size_t > computeHashSet(const Name &prefix)
Incrementally compute hash values.
Definition: name-tree.cpp:93
size_t getNBuckets() const
Get the number of buckets in the Name Tree (NPHT)
Definition: name-tree.hpp:342
represents a Measurements entry
size_t size() const
Get the number of occupied entries in the Name Tree.
Definition: name-tree.hpp:336
std::pair< bool, bool > operator()(const Entry &entry)
Definition: name-tree.hpp:68
represents a PIT entry
Definition: pit-entry.hpp:67
bool operator!=(const const_iterator &other) const
Definition: name-tree.hpp:410
Class Name Tree.
Definition: name-tree.hpp:79
void dump(std::ostream &output) const
Dump all the information stored in the Name Tree for debugging.
Definition: name-tree.cpp:535
represents a Strategy Choice entry
shared_ptr< name_tree::Entry > lookup(const Name &prefix)
Look for the Name Tree Entry that contains this name prefix.
Definition: name-tree.cpp:205
const_iterator operator++()
Definition: name-tree.cpp:609
function< bool(const Entry &entry)> EntrySelector
a predicate to accept or reject an Entry in find operations
Definition: name-tree.hpp:49
shared_ptr< name_tree::Entry > findExactMatch(const Name &prefix) const
Exact match lookup for the given name prefix.
Definition: name-tree.cpp:243
shared_ptr< name_tree::Entry > operator->() const
Definition: name-tree.hpp:390
boost::iterator_range< const_iterator > fullEnumerate(const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
Enumerate all entries, optionally filtered by an EntrySelector.
Definition: name-tree.cpp:406
bool operator()(const Entry &entry)
Definition: name-tree.hpp:60
Name Tree Entry Class.