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