name-tree-iterator.hpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2018, 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 #ifndef NFD_DAEMON_TABLE_NAME_TREE_ITERATOR_HPP
27 #define NFD_DAEMON_TABLE_NAME_TREE_ITERATOR_HPP
28 
29 #include "name-tree-hashtable.hpp"
30 
31 namespace nfd {
32 namespace name_tree {
33 
34 class NameTree;
35 
38 using EntrySelector = std::function<bool(const Entry&)>;
39 
42 struct AnyEntry
43 {
44  bool
45  operator()(const Entry&) const
46  {
47  return true;
48  }
49 };
50 
55 using EntrySubTreeSelector = std::function<std::pair<bool, bool>(const Entry&)>;
56 
60 {
61  std::pair<bool, bool>
62  operator()(const Entry&) const
63  {
64  return {true, true};
65  }
66 };
67 
68 class EnumerationImpl;
69 
72 class Iterator
73 {
74 public:
75  using iterator_category = std::forward_iterator_tag;
76  using value_type = const Entry;
77  using difference_type = std::ptrdiff_t;
78  using pointer = value_type*;
80 
81  Iterator();
82 
83  Iterator(shared_ptr<EnumerationImpl> impl, const Entry* ref);
84 
85  const Entry&
86  operator*() const
87  {
88  BOOST_ASSERT(m_impl != nullptr);
89  return *m_entry;
90  }
91 
92  const Entry*
93  operator->() const
94  {
95  BOOST_ASSERT(m_impl != nullptr);
96  return m_entry;
97  }
98 
99  Iterator&
100  operator++();
101 
102  Iterator
103  operator++(int);
104 
105  bool
106  operator==(const Iterator& other) const;
107 
108  bool
109  operator!=(const Iterator& other) const
110  {
111  return !this->operator==(other);
112  }
113 
114 private:
117  shared_ptr<EnumerationImpl> m_impl;
118 
121  const Entry* m_entry;
122 
125  const Entry* m_ref;
126 
129  int m_state;
130 
131  friend std::ostream& operator<<(std::ostream&, const Iterator&);
132  friend class FullEnumerationImpl;
134  friend class PrefixMatchImpl;
135 };
136 
137 std::ostream&
138 operator<<(std::ostream& os, const Iterator& i);
139 
143 {
144 public:
145  explicit
146  EnumerationImpl(const NameTree& nt);
147 
148  virtual
149  ~EnumerationImpl() = default;
150 
151  virtual void
152  advance(Iterator& i) = 0;
153 
154 protected:
155  const NameTree& nt;
156  const Hashtable& ht;
157 };
158 
162 {
163 public:
164  FullEnumerationImpl(const NameTree& nt, const EntrySelector& pred);
165 
166  void
167  advance(Iterator& i) override;
168 
169 private:
170  EntrySelector m_pred;
171 };
172 
179 {
180 public:
181  PartialEnumerationImpl(const NameTree& nt, const EntrySubTreeSelector& pred);
182 
183  void
184  advance(Iterator& i) override;
185 
186 private:
187  EntrySubTreeSelector m_pred;
188 };
189 
195 {
196 public:
197  PrefixMatchImpl(const NameTree& nt, const EntrySelector& pred);
198 
199 private:
200  void
201  advance(Iterator& i) override;
202 
203 private:
204  EntrySelector m_pred;
205 };
206 
212 using Range = boost::iterator_range<Iterator>;
213 
214 } // namespace name_tree
215 } // namespace nfd
216 
217 #endif // NFD_DAEMON_TABLE_NAME_TREE_ITERATOR_HPP
bool operator()(const Entry &) const
an EntrySelector that accepts every Entry
A common index structure for FIB, PIT, StrategyChoice, and Measurements.
Definition: name-tree.hpp:36
bool operator==(const Route &lhs, const Route &rhs)
Definition: route.cpp:63
bool operator!=(const Iterator &other) const
std::pair< bool, bool > operator()(const Entry &) const
std::ostream & operator<<(std::ostream &os, const Iterator &i)
enumeration operation implementation
const Entry * operator->() const
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
partial enumeration implementation
an EntrySubTreeSelector that accepts every Entry and its children
An entry in the name tree.
partial enumeration implementation
boost::iterator_range< Iterator > Range
a Forward Range of name tree entries
std::function< std::pair< bool, bool >(const Entry &)> EntrySubTreeSelector
a predicate to accept or reject an Entry and its children
std::forward_iterator_tag iterator_category
full enumeration implementation
std::function< bool(const Entry &)> EntrySelector
a predicate to accept or reject an Entry in find operations
a hashtable for fast exact name lookup
const Entry & operator*() const