NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
name-tree-iterator.cpp
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 #include "name-tree-iterator.hpp"
27 #include "name-tree.hpp"
28 #include "common/logger.hpp"
29 
30 #include <boost/range/concepts.hpp>
32 
33 namespace nfd {
34 namespace name_tree {
35 
37 BOOST_CONCEPT_ASSERT((boost::ForwardRangeConcept<Range>));
38 
40 
42  : m_entry(nullptr)
43  , m_ref(nullptr)
44  , m_state(0)
45 {
46 }
47 
48 Iterator::Iterator(shared_ptr<EnumerationImpl> impl, const Entry* ref)
49  : m_impl(std::move(impl))
50  , m_entry(nullptr)
51  , m_ref(ref)
52  , m_state(0)
53 {
54  m_impl->advance(*this);
55  NFD_LOG_TRACE("initialized " << *this);
56 }
57 
58 Iterator&
60 {
61  BOOST_ASSERT(m_impl != nullptr);
62  m_impl->advance(*this);
63  NFD_LOG_TRACE("advanced " << *this);
64  return *this;
65 }
66 
69 {
70  Iterator copy = *this;
71  this->operator++();
72  return copy;
73 }
74 
75 bool
76 Iterator::operator==(const Iterator& other) const
77 {
78  return m_entry == other.m_entry;
79 }
80 
81 std::ostream&
82 operator<<(std::ostream& os, const Iterator& i)
83 {
84  if (i.m_impl == nullptr) {
85  return os << "end";
86  }
87  if (i.m_entry == nullptr) {
88  return os << "uninitialized";
89  }
90 
91  os << "entry=" << i.m_entry->getName();
92  if (i.m_ref == nullptr) {
93  os << " ref=null";
94  }
95  else {
96  os << " ref=" << i.m_ref->getName();
97  }
98  os << " state=" << i.m_state;
99  return os;
100 }
101 
103  : nt(nt)
104  , ht(nt.m_ht)
105 {
106 }
107 
109  : EnumerationImpl(nt)
110  , m_pred(pred)
111 {
112 }
113 
114 void
116 {
117  // find first entry
118  if (i.m_entry == nullptr) {
119  for (size_t bucket = 0; bucket < ht.getNBuckets(); ++bucket) {
120  const Node* node = ht.getBucket(bucket);
121  if (node != nullptr) {
122  i.m_entry = &node->entry;
123  break;
124  }
125  }
126  if (i.m_entry == nullptr) { // empty enumerable
127  i = Iterator();
128  return;
129  }
130  if (m_pred(*i.m_entry)) { // visit first entry
131  return;
132  }
133  }
134 
135  // process entries in same bucket
136  for (const Node* node = getNode(*i.m_entry)->next; node != nullptr; node = node->next) {
137  if (m_pred(node->entry)) {
138  i.m_entry = &node->entry;
139  return;
140  }
141  }
142 
143  // process other buckets
144  size_t currentBucket = ht.computeBucketIndex(getNode(*i.m_entry)->hash);
145  for (size_t bucket = currentBucket + 1; bucket < ht.getNBuckets(); ++bucket) {
146  for (const Node* node = ht.getBucket(bucket); node != nullptr; node = node->next) {
147  if (m_pred(node->entry)) {
148  i.m_entry = &node->entry;
149  return;
150  }
151  }
152  }
153 
154  // reach the end
155  i = Iterator();
156 }
157 
159  : EnumerationImpl(nt)
160  , m_pred(pred)
161 {
162 }
163 
164 void
166 {
167  bool wantSelf = false;
168  bool wantChildren = false;
169 
170  // initialize: start from root
171  if (i.m_entry == nullptr) {
172  if (i.m_ref == nullptr) { // root does not exist
173  i = Iterator();
174  return;
175  }
176 
177  i.m_entry = i.m_ref;
178  std::tie(wantSelf, wantChildren) = m_pred(*i.m_entry);
179  if (wantSelf) { // visit root
180  i.m_state = wantChildren;
181  return;
182  }
183  }
184  else {
185  wantChildren = static_cast<bool>(i.m_state);
186  }
187  BOOST_ASSERT(i.m_ref != nullptr);
188 
189  // pre-order traversal
190  while (i.m_entry != i.m_ref || (wantChildren && i.m_entry->hasChildren())) {
191  if (wantChildren && i.m_entry->hasChildren()) { // process children of m_entry
192  i.m_entry = i.m_entry->getChildren().front();
193  std::tie(wantSelf, wantChildren) = m_pred(*i.m_entry);
194  if (wantSelf) { // visit first child
195  i.m_state = wantChildren;
196  return;
197  }
198  // first child rejected, let while loop process other children (siblings of new m_entry)
199  }
200  else { // process siblings of m_entry
201  const Entry* parent = i.m_entry->getParent();
202  const std::vector<Entry*>& siblings = parent->getChildren();
203  auto sibling = std::find(siblings.begin(), siblings.end(), i.m_entry);
204  BOOST_ASSERT(sibling != siblings.end());
205  while (++sibling != siblings.end()) {
206  i.m_entry = *sibling;
207  std::tie(wantSelf, wantChildren) = m_pred(*i.m_entry);
208  if (wantSelf) { // visit sibling
209  i.m_state = wantChildren;
210  return;
211  }
212  if (wantChildren) {
213  break; // let outer while loop process children of m_entry
214  }
215  // process next sibling
216  }
217  if (sibling == siblings.end()) { // no more sibling
218  i.m_entry = parent;
219  wantChildren = false;
220  }
221  }
222  }
223 
224  // reach the end
225  i = Iterator();
226 }
227 
229  : EnumerationImpl(nt)
230  , m_pred(pred)
231 {
232 }
233 
234 void
235 PrefixMatchImpl::advance(Iterator& i)
236 {
237  if (i.m_entry == nullptr) {
238  if (i.m_ref == nullptr) { // empty enumerable
239  i = Iterator();
240  return;
241  }
242 
243  i.m_entry = i.m_ref;
244  if (m_pred(*i.m_entry)) { // visit starting node
245  return;
246  }
247  }
248 
249  // traverse up the tree
250  while ((i.m_entry = i.m_entry->getParent()) != nullptr) {
251  if (m_pred(*i.m_entry)) {
252  return;
253  }
254  }
255 
256  // reach the end
257  i = Iterator();
258 }
259 
260 } // namespace name_tree
261 } // namespace nfd
nfd::name_tree::Entry::hasChildren
bool hasChildren() const
Check whether this entry has any children.
Definition: name-tree-entry.hpp:80
name-tree.hpp
NFD_LOG_TRACE
#define NFD_LOG_TRACE
Definition: logger.hpp:37
nfd::name_tree::Entry
An entry in the name tree.
Definition: name-tree-entry.hpp:42
nfd::name_tree::Entry::getChildren
const std::vector< Entry * > & getChildren() const
Definition: name-tree-entry.hpp:88
nonstd::optional_lite::std11::move
T & move(T &t)
Definition: optional.hpp:421
nfd::name_tree::NameTree
A common index structure for FIB, PIT, StrategyChoice, and Measurements.
Definition: name-tree.hpp:37
nfd::name_tree::Hashtable::getNBuckets
size_t getNBuckets() const
Definition: name-tree-hashtable.hpp:172
nfd::name_tree::getNode
Node * getNode(const Entry &entry)
Definition: name-tree-hashtable.cpp:107
nfd::name_tree::Iterator::operator==
bool operator==(const Iterator &other) const
Definition: name-tree-iterator.cpp:76
nfd::name_tree::Iterator::operator++
Iterator & operator++()
Definition: name-tree-iterator.cpp:59
nfd::name_tree::FullEnumerationImpl::FullEnumerationImpl
FullEnumerationImpl(const NameTree &nt, const EntrySelector &pred)
Definition: name-tree-iterator.cpp:108
nfd::name_tree::operator<<
std::ostream & operator<<(std::ostream &os, const Iterator &i)
Definition: name-tree-iterator.cpp:82
nfd::name_tree::EntrySelector
std::function< bool(const Entry &)> EntrySelector
a predicate to accept or reject an Entry in find operations
Definition: name-tree-iterator.hpp:38
nfd::name_tree::EntrySubTreeSelector
std::function< std::pair< bool, bool >(const Entry &)> EntrySubTreeSelector
a predicate to accept or reject an Entry and its children
Definition: name-tree-iterator.hpp:55
concepts.hpp
nfd::name_tree::EnumerationImpl::EnumerationImpl
EnumerationImpl(const NameTree &nt)
Definition: name-tree-iterator.cpp:102
nfd::name_tree::EnumerationImpl::ht
const Hashtable & ht
Definition: name-tree-iterator.hpp:156
nfd::name_tree::PartialEnumerationImpl::PartialEnumerationImpl
PartialEnumerationImpl(const NameTree &nt, const EntrySubTreeSelector &pred)
Definition: name-tree-iterator.cpp:158
nfd::name_tree::Iterator::Iterator
Iterator()
Definition: name-tree-iterator.cpp:41
nfd::name_tree::Entry::getName
const Name & getName() const
Definition: name-tree-entry.hpp:47
nfd
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
nfd::name_tree::PrefixMatchImpl::PrefixMatchImpl
PrefixMatchImpl(const NameTree &nt, const EntrySelector &pred)
Definition: name-tree-iterator.cpp:228
nfd::name_tree::Node
a hashtable node
Definition: name-tree-hashtable.hpp:62
nfd::name_tree::Node::next
Node * next
Definition: name-tree-hashtable.hpp:77
nfd::name_tree::NDN_CXX_ASSERT_FORWARD_ITERATOR
NDN_CXX_ASSERT_FORWARD_ITERATOR(Iterator)
nfd::name_tree::Node::hash
const HashValue hash
Definition: name-tree-hashtable.hpp:75
nfd::name_tree::Node::entry
Entry entry
Definition: name-tree-hashtable.hpp:78
nfd::name_tree::NameTreeIterator
NameTreeIterator
Definition: name-tree-iterator.cpp:39
nfd::name_tree::Hashtable::getBucket
const Node * getBucket(size_t bucket) const
Definition: name-tree-hashtable.hpp:189
name-tree-iterator.hpp
nfd::name_tree::FullEnumerationImpl::advance
void advance(Iterator &i) override
Definition: name-tree-iterator.cpp:115
nfd::name_tree::Hashtable::computeBucketIndex
size_t computeBucketIndex(HashValue h) const
Definition: name-tree-hashtable.hpp:180
nfd::name_tree::EnumerationImpl
enumeration operation implementation
Definition: name-tree-iterator.hpp:143
nfd::name_tree::Entry::getParent
Entry * getParent() const
Definition: name-tree-entry.hpp:56
nfd::name_tree::PartialEnumerationImpl::advance
void advance(Iterator &i) override
Definition: name-tree-iterator.cpp:165
NFD_LOG_INIT
#define NFD_LOG_INIT(name)
Definition: logger.hpp:31
logger.hpp
nfd::name_tree::Iterator
NameTree iterator.
Definition: name-tree-iterator.hpp:73