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-2017, 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 typedef function<bool(const Entry& entry)> EntrySelector;
39 
42 struct AnyEntry
43 {
44  bool
45  operator()(const Entry& entry) const
46  {
47  return true;
48  }
49 };
50 
55 typedef function<std::pair<bool,bool>(const Entry& entry)> EntrySubTreeSelector;
56 
60 {
61  std::pair<bool, bool>
62  operator()(const Entry& entry) const
63  {
64  return {true, true};
65  }
66 };
67 
68 class EnumerationImpl;
69 
72 class Iterator : public std::iterator<std::forward_iterator_tag, const Entry>
73 {
74 public:
75  Iterator();
76 
77  Iterator(shared_ptr<EnumerationImpl> impl, const Entry* ref);
78 
79  const Entry&
80  operator*() const
81  {
82  BOOST_ASSERT(m_impl != nullptr);
83  return *m_entry;
84  }
85 
86  const Entry*
87  operator->() const
88  {
89  BOOST_ASSERT(m_impl != nullptr);
90  return m_entry;
91  }
92 
93  Iterator&
94  operator++();
95 
96  Iterator
97  operator++(int);
98 
99  bool
100  operator==(const Iterator& other) const;
101 
102  bool
103  operator!=(const Iterator& other) const
104  {
105  return !this->operator==(other);
106  }
107 
108 private:
111  shared_ptr<EnumerationImpl> m_impl;
112 
115  const Entry* m_entry;
116 
119  const Entry* m_ref;
120 
123  int m_state;
124 
125  friend std::ostream& operator<<(std::ostream&, const Iterator&);
126  friend class FullEnumerationImpl;
128  friend class PrefixMatchImpl;
129 };
130 
131 std::ostream&
132 operator<<(std::ostream& os, const Iterator& i);
133 
137 {
138 public:
139  explicit
140  EnumerationImpl(const NameTree& nt);
141 
142  virtual
143  ~EnumerationImpl() = default;
144 
145  virtual void
146  advance(Iterator& i) = 0;
147 
148 protected:
149  const NameTree& nt;
150  const Hashtable& ht;
151 };
152 
156 {
157 public:
158  FullEnumerationImpl(const NameTree& nt, const EntrySelector& pred);
159 
160  void
161  advance(Iterator& i) override;
162 
163 private:
164  EntrySelector m_pred;
165 };
166 
173 {
174 public:
175  PartialEnumerationImpl(const NameTree& nt, const EntrySubTreeSelector& pred);
176 
177  void
178  advance(Iterator& i) override;
179 
180 private:
181  EntrySubTreeSelector m_pred;
182 };
183 
189 {
190 public:
191  PrefixMatchImpl(const NameTree& nt, const EntrySelector& pred);
192 
193 private:
194  void
195  advance(Iterator& i) override;
196 
197 private:
198  EntrySelector m_pred;
199 };
200 
206 typedef boost::iterator_range<Iterator> Range;
207 
208 } // namespace name_tree
209 } // namespace nfd
210 
211 #endif // NFD_DAEMON_TABLE_NAME_TREE_ITERATOR_HPP
bool operator()(const Entry &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:41
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
std::ostream & operator<<(std::ostream &os, const Iterator &i)
const Entry * operator->() const
Table::const_iterator iterator
Definition: cs-internal.hpp:41
enumeration operation implementation
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
partial enumeration implementation
std::pair< bool, bool > operator()(const Entry &entry) const
an EntrySubTreeSelector that accepts every Entry and its children
function< bool(const Entry &entry)> EntrySelector
a predicate to accept or reject an Entry in find operations
an entry in the name tree
partial enumeration implementation
boost::iterator_range< Iterator > Range
a Forward Range of name tree entries
const Entry & operator*() const
full enumeration implementation
a hashtable for fast exact name lookup