NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: NDN, CCN, CCNx, content centric networks
API Documentation
name-tree.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "name-tree.hpp"
27 #include "core/logger.hpp"
28 #include "core/city-hash.hpp"
29 
30 #include <boost/concept/assert.hpp>
31 #include <boost/concept_check.hpp>
32 #include <type_traits>
33 
34 namespace nfd {
35 
36 NFD_LOG_INIT("NameTree");
37 
38 // http://en.cppreference.com/w/cpp/concept/ForwardIterator
39 BOOST_CONCEPT_ASSERT((boost::ForwardIterator<NameTree::const_iterator>));
40 // boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
41 // which doesn't require DefaultConstructible
42 #ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
43 static_assert(std::is_default_constructible<NameTree::const_iterator>::value,
44  "NameTree::const_iterator must be default-constructible");
45 #else
46 BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<NameTree::const_iterator>));
47 #endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
48 
49 namespace name_tree {
50 
51 class Hash32
52 {
53 public:
54  static size_t
55  compute(const char* buffer, size_t length)
56  {
57  return static_cast<size_t>(CityHash32(buffer, length));
58  }
59 };
60 
61 class Hash64
62 {
63 public:
64  static size_t
65  compute(const char* buffer, size_t length)
66  {
67  return static_cast<size_t>(CityHash64(buffer, length));
68  }
69 };
70 
71 typedef boost::mpl::if_c<sizeof(size_t) >= 8, Hash64, Hash32>::type CityHash;
72 
73 // Interface of different hash functions
74 size_t
75 computeHash(const Name& prefix)
76 {
77  prefix.wireEncode(); // guarantees prefix's wire buffer is not empty
78 
79  size_t hashValue = 0;
80  size_t hashUpdate = 0;
81 
82  for (Name::const_iterator it = prefix.begin(); it != prefix.end(); it++)
83  {
84  const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
85  hashUpdate = CityHash::compute(wireFormat, it->size());
86  hashValue ^= hashUpdate;
87  }
88 
89  return hashValue;
90 }
91 
92 std::vector<size_t>
93 computeHashSet(const Name& prefix)
94 {
95  prefix.wireEncode(); // guarantees prefix's wire buffer is not empty
96 
97  size_t hashValue = 0;
98  size_t hashUpdate = 0;
99 
100  std::vector<size_t> hashValueSet;
101  hashValueSet.push_back(hashValue);
102 
103  for (Name::const_iterator it = prefix.begin(); it != prefix.end(); it++)
104  {
105  const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
106  hashUpdate = CityHash::compute(wireFormat, it->size());
107  hashValue ^= hashUpdate;
108  hashValueSet.push_back(hashValue);
109  }
110 
111  return hashValueSet;
112 }
113 
114 } // namespace name_tree
115 
116 NameTree::NameTree(size_t nBuckets)
117  : m_nItems(0)
118  , m_nBuckets(nBuckets)
119  , m_minNBuckets(nBuckets)
120  , m_enlargeLoadFactor(0.5) // more than 50% buckets loaded
121  , m_enlargeFactor(2) // double the hash table size
122  , m_shrinkLoadFactor(0.1) // less than 10% buckets loaded
123  , m_shrinkFactor(0.5) // reduce the number of buckets by half
124  , m_endIterator(FULL_ENUMERATE_TYPE, *this, m_end)
125 {
126  m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor *
127  static_cast<double>(m_nBuckets));
128 
129  m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor *
130  static_cast<double>(m_nBuckets));
131 
132  // array of node pointers
133  m_buckets = new name_tree::Node*[m_nBuckets];
134  // Initialize the pointer array
135  for (size_t i = 0; i < m_nBuckets; i++)
136  m_buckets[i] = 0;
137 }
138 
140 {
141  for (size_t i = 0; i < m_nBuckets; i++)
142  {
143  if (m_buckets[i] != 0) {
144  delete m_buckets[i];
145  }
146  }
147 
148  delete [] m_buckets;
149 }
150 
151 // insert() is a private function, and called by only lookup()
152 std::pair<shared_ptr<name_tree::Entry>, bool>
153 NameTree::insert(const Name& prefix)
154 {
155  NFD_LOG_TRACE("insert " << prefix);
156 
157  size_t hashValue = name_tree::computeHash(prefix);
158  size_t loc = hashValue % m_nBuckets;
159 
160  NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue << " location = " << loc);
161 
162  // Check if this Name has been stored
163  name_tree::Node* node = m_buckets[loc];
164  name_tree::Node* nodePrev = node; // initialize nodePrev to node
165 
166  for (node = m_buckets[loc]; node != 0; node = node->m_next)
167  {
168  if (static_cast<bool>(node->m_entry))
169  {
170  if (prefix == node->m_entry->m_prefix)
171  {
172  return std::make_pair(node->m_entry, false); // false: old entry
173  }
174  }
175  nodePrev = node;
176  }
177 
178  NFD_LOG_TRACE("Did not find " << prefix << ", need to insert it to the table");
179 
180  // If no bucket is empty occupied, we need to create a new node, and it is
181  // linked from nodePrev
182  node = new name_tree::Node();
183  node->m_prev = nodePrev;
184 
185  if (nodePrev == 0)
186  {
187  m_buckets[loc] = node;
188  }
189  else
190  {
191  nodePrev->m_next = node;
192  }
193 
194  // Create a new Entry
195  shared_ptr<name_tree::Entry> entry(make_shared<name_tree::Entry>(prefix));
196  entry->setHash(hashValue);
197  node->m_entry = entry; // link the Entry to its Node
198  entry->m_node = node; // link the node to Entry. Used in eraseEntryIfEmpty.
199 
200  return std::make_pair(entry, true); // true: new entry
201 }
202 
203 // Name Prefix Lookup. Create Name Tree Entry if not found
204 shared_ptr<name_tree::Entry>
205 NameTree::lookup(const Name& prefix)
206 {
207  NFD_LOG_TRACE("lookup " << prefix);
208 
209  shared_ptr<name_tree::Entry> entry;
210  shared_ptr<name_tree::Entry> parent;
211 
212  for (size_t i = 0; i <= prefix.size(); i++)
213  {
214  Name temp = prefix.getPrefix(i);
215 
216  // insert() will create the entry if it does not exist.
217  std::pair<shared_ptr<name_tree::Entry>, bool> ret = insert(temp);
218  entry = ret.first;
219 
220  if (ret.second == true)
221  {
222  m_nItems++; // Increase the counter
223  entry->m_parent = parent;
224 
225  if (static_cast<bool>(parent))
226  {
227  parent->m_children.push_back(entry);
228  }
229  }
230 
231  if (m_nItems > m_enlargeThreshold)
232  {
233  resize(m_enlargeFactor * m_nBuckets);
234  }
235 
236  parent = entry;
237  }
238  return entry;
239 }
240 
241 // Exact Match
242 shared_ptr<name_tree::Entry>
243 NameTree::findExactMatch(const Name& prefix) const
244 {
245  NFD_LOG_TRACE("findExactMatch " << prefix);
246 
247  size_t hashValue = name_tree::computeHash(prefix);
248  size_t loc = hashValue % m_nBuckets;
249 
250  NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue <<
251  " location = " << loc);
252 
253  shared_ptr<name_tree::Entry> entry;
254  name_tree::Node* node = 0;
255 
256  for (node = m_buckets[loc]; node != 0; node = node->m_next)
257  {
258  entry = node->m_entry;
259  if (static_cast<bool>(entry))
260  {
261  if (hashValue == entry->getHash() && prefix == entry->getPrefix())
262  {
263  return entry;
264  }
265  } // if entry
266  } // for node
267 
268  // if not found, the default value of entry (null pointer) will be returned
269  entry.reset();
270  return entry;
271 }
272 
273 // Longest Prefix Match
274 shared_ptr<name_tree::Entry>
275 NameTree::findLongestPrefixMatch(const Name& prefix, const name_tree::EntrySelector& entrySelector) const
276 {
277  NFD_LOG_TRACE("findLongestPrefixMatch " << prefix);
278 
279  shared_ptr<name_tree::Entry> entry;
280  std::vector<size_t> hashValueSet = name_tree::computeHashSet(prefix);
281 
282  size_t hashValue = 0;
283  size_t loc = 0;
284 
285  for (int i = static_cast<int>(prefix.size()); i >= 0; i--)
286  {
287  hashValue = hashValueSet[i];
288  loc = hashValue % m_nBuckets;
289 
290  name_tree::Node* node = 0;
291  for (node = m_buckets[loc]; node != 0; node = node->m_next)
292  {
293  entry = node->m_entry;
294  if (static_cast<bool>(entry))
295  {
296  // isPrefixOf() is used to avoid making a copy of the name
297  if (hashValue == entry->getHash() &&
298  entry->getPrefix().isPrefixOf(prefix) &&
299  entrySelector(*entry))
300  {
301  return entry;
302  }
303  } // if entry
304  } // for node
305  }
306 
307  // if not found, the default value of entry (null pointer) will be returned
308  entry.reset();
309  return entry;
310 }
311 
312 shared_ptr<name_tree::Entry>
313 NameTree::findLongestPrefixMatch(shared_ptr<name_tree::Entry> entry,
314  const name_tree::EntrySelector& entrySelector) const
315 {
316  while (static_cast<bool>(entry))
317  {
318  if (entrySelector(*entry))
319  return entry;
320  entry = entry->getParent();
321  }
322  return shared_ptr<name_tree::Entry>();
323 }
324 
325 // return {false: this entry is not empty, true: this entry is empty and erased}
326 bool
327 NameTree::eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry)
328 {
329  BOOST_ASSERT(static_cast<bool>(entry));
330 
331  NFD_LOG_TRACE("eraseEntryIfEmpty " << entry->getPrefix());
332 
333  // first check if this Entry can be erased
334  if (entry->isEmpty())
335  {
336  // update child-related info in the parent
337  shared_ptr<name_tree::Entry> parent = entry->getParent();
338 
339  if (static_cast<bool>(parent))
340  {
341  std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList =
342  parent->getChildren();
343 
344  bool isFound = false;
345  size_t size = parentChildrenList.size();
346  for (size_t i = 0; i < size; i++)
347  {
348  if (parentChildrenList[i] == entry)
349  {
350  parentChildrenList[i] = parentChildrenList[size - 1];
351  parentChildrenList.pop_back();
352  isFound = true;
353  break;
354  }
355  }
356 
357  BOOST_VERIFY(isFound == true);
358  }
359 
360  // remove this Entry and its Name Tree Node
361  name_tree::Node* node = entry->m_node;
362  name_tree::Node* nodePrev = node->m_prev;
363 
364  // configure the previous node
365  if (nodePrev != 0)
366  {
367  // link the previous node to the next node
368  nodePrev->m_next = node->m_next;
369  }
370  else
371  {
372  m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
373  }
374 
375  // link the previous node with the next node (skip the erased one)
376  if (node->m_next != 0)
377  {
378  node->m_next->m_prev = nodePrev;
379  node->m_next = 0;
380  }
381 
382  BOOST_ASSERT(node->m_next == 0);
383 
384  m_nItems--;
385  delete node;
386 
387  if (static_cast<bool>(parent))
388  eraseEntryIfEmpty(parent);
389 
390  size_t newNBuckets = static_cast<size_t>(m_shrinkFactor *
391  static_cast<double>(m_nBuckets));
392 
393  if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold)
394  {
395  resize(newNBuckets);
396  }
397 
398  return true;
399 
400  } // if this entry is empty
401 
402  return false; // if this entry is not empty
403 }
404 
405 boost::iterator_range<NameTree::const_iterator>
407 {
408  NFD_LOG_TRACE("fullEnumerate");
409 
410  // find the first eligible entry
411  for (size_t i = 0; i < m_nBuckets; i++) {
412  for (name_tree::Node* node = m_buckets[i]; node != 0; node = node->m_next) {
413  if (static_cast<bool>(node->m_entry) && entrySelector(*node->m_entry)) {
414  const_iterator it(FULL_ENUMERATE_TYPE, *this, node->m_entry, entrySelector);
415  return {it, end()};
416  }
417  }
418  }
419 
420  // If none of the entry satisfies the requirements, then return the end() iterator.
421  return {end(), end()};
422 }
423 
424 boost::iterator_range<NameTree::const_iterator>
426  const name_tree::EntrySubTreeSelector& entrySubTreeSelector) const
427 {
428  // the first step is to process the root node
429  shared_ptr<name_tree::Entry> entry = findExactMatch(prefix);
430  if (!static_cast<bool>(entry)) {
431  return {end(), end()};
432  }
433 
434  std::pair<bool, bool>result = entrySubTreeSelector(*entry);
436  *this,
437  entry,
439  entrySubTreeSelector);
440 
441  it.m_shouldVisitChildren = (result.second && entry->hasChildren());
442 
443  if (result.first) {
444  // root node is acceptable
445  }
446  else {
447  // let the ++ operator handle it
448  ++it;
449  }
450  return {it, end()};
451 }
452 
453 boost::iterator_range<NameTree::const_iterator>
455  const name_tree::EntrySelector& entrySelector) const
456 {
457  NFD_LOG_TRACE("NameTree::findAllMatches" << prefix);
458 
459  // As we are using Name Prefix Hash Table, and the current LPM() is
460  // implemented as starting from full name, and reduce the number of
461  // components by 1 each time, we could use it here.
462  // For trie-like design, it could be more efficient by walking down the
463  // trie from the root node.
464 
465  shared_ptr<name_tree::Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
466 
467  if (static_cast<bool>(entry)) {
468  const_iterator begin(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
469  return {begin, end()};
470  }
471  // If none of the entry satisfies the requirements, then return the end() iterator.
472  return {end(), end()};
473 }
474 
475 // Hash Table Resize
476 void
477 NameTree::resize(size_t newNBuckets)
478 {
479  NFD_LOG_TRACE("resize");
480 
481  name_tree::Node** newBuckets = new name_tree::Node*[newNBuckets];
482  size_t count = 0;
483 
484  // referenced ccnx hashtb.c hashtb_rehash()
485  name_tree::Node** pp = 0;
486  name_tree::Node* p = 0;
487  name_tree::Node* pre = 0;
488  name_tree::Node* q = 0; // record p->m_next
489  size_t i;
490  uint32_t h;
491  uint32_t b;
492 
493  for (i = 0; i < newNBuckets; i++)
494  {
495  newBuckets[i] = 0;
496  }
497 
498  for (i = 0; i < m_nBuckets; i++)
499  {
500  for (p = m_buckets[i]; p != 0; p = q)
501  {
502  count++;
503  q = p->m_next;
504  BOOST_ASSERT(static_cast<bool>(p->m_entry));
505  h = p->m_entry->m_hash;
506  b = h % newNBuckets;
507  pre = 0;
508  for (pp = &newBuckets[b]; *pp != 0; pp = &((*pp)->m_next))
509  {
510  pre = *pp;
511  continue;
512  }
513  p->m_prev = pre;
514  p->m_next = *pp; // Actually *pp always == 0 in this case
515  *pp = p;
516  }
517  }
518 
519  BOOST_ASSERT(count == m_nItems);
520 
521  name_tree::Node** oldBuckets = m_buckets;
522  m_buckets = newBuckets;
523  delete [] oldBuckets;
524 
525  m_nBuckets = newNBuckets;
526 
527  m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor *
528  static_cast<double>(m_nBuckets));
529  m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor *
530  static_cast<double>(m_nBuckets));
531 }
532 
533 // For debugging
534 void
535 NameTree::dump(std::ostream& output) const
536 {
537  NFD_LOG_TRACE("dump()");
538 
539  name_tree::Node* node = 0;
540  shared_ptr<name_tree::Entry> entry;
541 
542  using std::endl;
543 
544  for (size_t i = 0; i < m_nBuckets; i++)
545  {
546  for (node = m_buckets[i]; node != 0; node = node->m_next)
547  {
548  entry = node->m_entry;
549 
550  // if the Entry exist, dump its information
551  if (static_cast<bool>(entry))
552  {
553  output << "Bucket" << i << "\t" << entry->m_prefix.toUri() << endl;
554  output << "\t\tHash " << entry->m_hash << endl;
555 
556  if (static_cast<bool>(entry->m_parent))
557  {
558  output << "\t\tparent->" << entry->m_parent->m_prefix.toUri();
559  }
560  else
561  {
562  output << "\t\tROOT";
563  }
564  output << endl;
565 
566  if (entry->m_children.size() != 0)
567  {
568  output << "\t\tchildren = " << entry->m_children.size() << endl;
569 
570  for (size_t j = 0; j < entry->m_children.size(); j++)
571  {
572  output << "\t\t\tChild " << j << " " <<
573  entry->m_children[j]->getPrefix() << endl;
574  }
575  }
576 
577  } // if (static_cast<bool>(entry))
578 
579  } // for node
580  } // for int i
581 
582  output << "Bucket count = " << m_nBuckets << endl;
583  output << "Stored item = " << m_nItems << endl;
584  output << "--------------------------\n";
585 }
586 
588  : m_nameTree(nullptr)
589 {
590 }
591 
593  const NameTree& nameTree,
594  shared_ptr<name_tree::Entry> entry,
595  const name_tree::EntrySelector& entrySelector,
596  const name_tree::EntrySubTreeSelector& entrySubTreeSelector)
597  : m_nameTree(&nameTree)
598  , m_entry(entry)
599  , m_subTreeRoot(entry)
600  , m_entrySelector(make_shared<name_tree::EntrySelector>(entrySelector))
601  , m_entrySubTreeSelector(make_shared<name_tree::EntrySubTreeSelector>(entrySubTreeSelector))
602  , m_type(type)
603  , m_shouldVisitChildren(true)
604 {
605 }
606 
607 // operator++()
610 {
611  NFD_LOG_TRACE("const_iterator::operator++()");
612 
613  BOOST_ASSERT(m_entry != m_nameTree->m_end);
614 
615  if (m_type == FULL_ENUMERATE_TYPE) // fullEnumerate
616  {
617  // process the entries in the same bucket first
618  while (m_entry->m_node->m_next != 0)
619  {
620  m_entry = m_entry->m_node->m_next->m_entry;
621  if ((*m_entrySelector)(*m_entry))
622  {
623  return *this;
624  }
625  }
626 
627  // process other buckets
628 
629  for (int newLocation = m_entry->m_hash % m_nameTree->m_nBuckets + 1;
630  newLocation < static_cast<int>(m_nameTree->m_nBuckets);
631  ++newLocation)
632  {
633  // process each bucket
634  name_tree::Node* node = m_nameTree->m_buckets[newLocation];
635  while (node != 0)
636  {
637  m_entry = node->m_entry;
638  if ((*m_entrySelector)(*m_entry))
639  {
640  return *this;
641  }
642  node = node->m_next;
643  }
644  }
645 
646  // Reach the end()
647  m_entry = m_nameTree->m_end;
648  return *this;
649  }
650 
651  if (m_type == PARTIAL_ENUMERATE_TYPE) // partialEnumerate
652  {
653  // We use pre-order traversal.
654  // if at the root, it could have already been accepted, or this
655  // iterator was just declared, and root doesn't satisfy the
656  // requirement
657  // The if() section handles this special case
658  // Essentially, we need to check root's fist child, and the rest will
659  // be the same as normal process
660  if (m_entry == m_subTreeRoot)
661  {
662  if (m_shouldVisitChildren)
663  {
664  m_entry = m_entry->getChildren()[0];
665  std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
666  m_shouldVisitChildren = (result.second && m_entry->hasChildren());
667  if(result.first)
668  {
669  return *this;
670  }
671  else
672  {
673  // the first child did not meet the requirement
674  // the rest of the process can just fall through the while loop
675  // as normal
676  }
677  }
678  else
679  {
680  // no children, should return end();
681  // just fall through
682  }
683  }
684 
685  // The first thing to do is to visit its child, or go to find its possible
686  // siblings
687  while (m_entry != m_subTreeRoot)
688  {
689  if (m_shouldVisitChildren)
690  {
691  // If this subtree should be visited
692  m_entry = m_entry->getChildren()[0];
693  std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
694  m_shouldVisitChildren = (result.second && m_entry->hasChildren());
695  if (result.first) // if this node is acceptable
696  {
697  return *this;
698  }
699  else
700  {
701  // do nothing, as this node is essentially ignored
702  // send this node to the while loop.
703  }
704  }
705  else
706  {
707  // Should try to find its sibling
708  shared_ptr<name_tree::Entry> parent = m_entry->getParent();
709 
710  std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList = parent->getChildren();
711  bool isFound = false;
712  size_t i = 0;
713  for (i = 0; i < parentChildrenList.size(); i++)
714  {
715  if (parentChildrenList[i] == m_entry)
716  {
717  isFound = true;
718  break;
719  }
720  }
721 
722  BOOST_VERIFY(isFound == true);
723  if (i < parentChildrenList.size() - 1) // m_entry not the last child
724  {
725  m_entry = parentChildrenList[i + 1];
726  std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
727  m_shouldVisitChildren = (result.second && m_entry->hasChildren());
728  if (result.first) // if this node is acceptable
729  {
730  return *this;
731  }
732  else
733  {
734  // do nothing, as this node is essentially ignored
735  // send this node to the while loop.
736  }
737  }
738  else
739  {
740  // m_entry is the last child, no more sibling, should try to find parent's sibling
741  m_shouldVisitChildren = false;
742  m_entry = parent;
743  }
744  }
745  }
746 
747  m_entry = m_nameTree->m_end;
748  return *this;
749  }
750 
751  if (m_type == FIND_ALL_MATCHES_TYPE) // findAllMatches
752  {
753  // Assumption: at the beginning, m_entry was initialized with the first
754  // eligible Name Tree entry (i.e., has a PIT entry that can be satisfied
755  // by the Data packet)
756 
757  while (static_cast<bool>(m_entry->getParent()))
758  {
759  m_entry = m_entry->getParent();
760  if ((*m_entrySelector)(*m_entry))
761  return *this;
762  }
763 
764  // Reach to the end (Root)
765  m_entry = m_nameTree->m_end;
766  return *this;
767  }
768 
769  BOOST_ASSERT(false); // unknown type
770  return *this;
771 }
772 
773 } // namespace nfd
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&#39;s WIRE FORMAT.
Definition: name-tree.cpp:75
NameTree(size_t nBuckets=1024)
Definition: name-tree.cpp:116
const_iterator begin() const
Begin iterator (const).
Definition: name.hpp:576
static size_t compute(const char *buffer, size_t length)
Definition: name-tree.cpp:65
Name Tree Node Class.
const_iterator begin() const
Get an iterator pointing to the first NameTree entry.
Definition: name-tree.hpp:372
shared_ptr< Entry > m_entry
Hash32::type CityHash
Definition: name-tree.cpp:71
bool eraseEntryIfEmpty(shared_ptr< name_tree::Entry > entry)
Delete a Name Tree Entry if this entry is empty.
Definition: name-tree.cpp:327
uint32 CityHash32(const char *s, size_t len)
Definition: city-hash.cpp:182
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
size_t wireEncode(EncodingImpl< TAG > &encoder) const
Fast encoding or block size estimation.
Definition: name.cpp:69
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
typedef Hash64
Definition: name-tree.cpp:71
std::vector< size_t > computeHashSet(const Name &prefix)
Incrementally compute hash values.
Definition: name-tree.cpp:93
size_t size() const
Get the number of occupied entries in the Name Tree.
Definition: name-tree.hpp:336
uint64 CityHash64(const char *s, size_t len)
Definition: city-hash.cpp:359
const_iterator end() const
End iterator (const).
Definition: name.hpp:587
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:38
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
size_t size() const
Get the number of components.
Definition: name.hpp:408
Name abstraction to represent an absolute name.
Definition: name.hpp:46
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
Component holds a read-only name component value.
static size_t compute(const char *buffer, size_t length)
Definition: name-tree.cpp:55
#define NFD_LOG_INIT(name)
Definition: logger.hpp:33
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:35
function< bool(const Entry &entry)> EntrySelector
a predicate to accept or reject an Entry in find operations
Definition: name-tree.hpp:49
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix (PartialName) of the name, containing first nComponents components.
Definition: name.hpp:249
shared_ptr< name_tree::Entry > findExactMatch(const Name &prefix) const
Exact match lookup for the given name prefix.
Definition: name-tree.cpp:243
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