blob: 87a93f770fe174292f284ca9e970eeff82d372c6 [file] [log] [blame]
Junxiao Shi029401f2016-08-05 12:55:14 +00001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Alexander Afanasyev847de402017-09-21 18:57:30 -04002/*
Davide Pesavento87fc0f82018-04-11 23:43:51 -04003 * Copyright (c) 2014-2018, Regents of the University of California,
Junxiao Shi029401f2016-08-05 12:55:14 +00004 * 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
Junxiao Shi340d5532016-08-13 04:00:35 +000029#include "name-tree-hashtable.hpp"
Junxiao Shi029401f2016-08-05 12:55:14 +000030
31namespace nfd {
32namespace name_tree {
33
Junxiao Shi340d5532016-08-13 04:00:35 +000034class NameTree;
35
Junxiao Shi029401f2016-08-05 12:55:14 +000036/** \brief a predicate to accept or reject an Entry in find operations
37 */
Davide Pesavento87fc0f82018-04-11 23:43:51 -040038using EntrySelector = std::function<bool(const Entry&)>;
Junxiao Shi029401f2016-08-05 12:55:14 +000039
40/** \brief an EntrySelector that accepts every Entry
41 */
42struct AnyEntry
43{
44 bool
Davide Pesavento87fc0f82018-04-11 23:43:51 -040045 operator()(const Entry&) const
Junxiao Shi029401f2016-08-05 12:55:14 +000046 {
47 return true;
48 }
49};
50
51/** \brief a predicate to accept or reject an Entry and its children
Davide Pesavento87fc0f82018-04-11 23:43:51 -040052 * \return `.first` indicates whether entry should be accepted;
53 * `.second` indicates whether entry's children should be visited
Junxiao Shi029401f2016-08-05 12:55:14 +000054 */
Davide Pesavento87fc0f82018-04-11 23:43:51 -040055using EntrySubTreeSelector = std::function<std::pair<bool, bool>(const Entry&)>;
Junxiao Shi029401f2016-08-05 12:55:14 +000056
57/** \brief an EntrySubTreeSelector that accepts every Entry and its children
58 */
59struct AnyEntrySubTree
60{
61 std::pair<bool, bool>
Davide Pesavento87fc0f82018-04-11 23:43:51 -040062 operator()(const Entry&) const
Junxiao Shi029401f2016-08-05 12:55:14 +000063 {
64 return {true, true};
65 }
66};
67
68class EnumerationImpl;
69
70/** \brief NameTree iterator
71 */
72class Iterator : public std::iterator<std::forward_iterator_tag, const Entry>
73{
74public:
75 Iterator();
76
Junxiao Shib660b4c2016-08-06 20:47:44 +000077 Iterator(shared_ptr<EnumerationImpl> impl, const Entry* ref);
Junxiao Shi029401f2016-08-05 12:55:14 +000078
Junxiao Shi029401f2016-08-05 12:55:14 +000079 const Entry&
80 operator*() const
81 {
82 BOOST_ASSERT(m_impl != nullptr);
83 return *m_entry;
84 }
85
Junxiao Shib660b4c2016-08-06 20:47:44 +000086 const Entry*
Junxiao Shi029401f2016-08-05 12:55:14 +000087 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
108private:
109 /** \brief enumeration implementation; nullptr for end iterator
110 */
111 shared_ptr<EnumerationImpl> m_impl;
112
113 /** \brief current entry; nullptr for uninitialized iterator
114 */
Junxiao Shib660b4c2016-08-06 20:47:44 +0000115 const Entry* m_entry;
Junxiao Shi029401f2016-08-05 12:55:14 +0000116
117 /** \brief reference entry used by enumeration implementation
118 */
Junxiao Shib660b4c2016-08-06 20:47:44 +0000119 const Entry* m_ref;
Junxiao Shi029401f2016-08-05 12:55:14 +0000120
121 /** \brief state used by enumeration implementation
122 */
123 int m_state;
124
125 friend std::ostream& operator<<(std::ostream&, const Iterator&);
126 friend class FullEnumerationImpl;
127 friend class PartialEnumerationImpl;
128 friend class PrefixMatchImpl;
129};
130
131std::ostream&
132operator<<(std::ostream& os, const Iterator& i);
133
134/** \brief enumeration operation implementation
135 */
136class EnumerationImpl
137{
138public:
139 explicit
140 EnumerationImpl(const NameTree& nt);
141
Alexander Afanasyev847de402017-09-21 18:57:30 -0400142 virtual
143 ~EnumerationImpl() = default;
144
Junxiao Shi029401f2016-08-05 12:55:14 +0000145 virtual void
146 advance(Iterator& i) = 0;
147
148protected:
149 const NameTree& nt;
Junxiao Shib660b4c2016-08-06 20:47:44 +0000150 const Hashtable& ht;
Junxiao Shi029401f2016-08-05 12:55:14 +0000151};
152
153/** \brief full enumeration implementation
154 */
155class FullEnumerationImpl : public EnumerationImpl
156{
157public:
158 FullEnumerationImpl(const NameTree& nt, const EntrySelector& pred);
159
Alexander Afanasyev847de402017-09-21 18:57:30 -0400160 void
Junxiao Shi029401f2016-08-05 12:55:14 +0000161 advance(Iterator& i) override;
162
163private:
164 EntrySelector m_pred;
165};
166
167/** \brief partial enumeration implementation
168 *
169 * Iterator::m_ref should be initialized to subtree root.
170 * Iterator::m_state LSB indicates whether to visit children of m_entry.
171 */
172class PartialEnumerationImpl : public EnumerationImpl
173{
174public:
175 PartialEnumerationImpl(const NameTree& nt, const EntrySubTreeSelector& pred);
176
Alexander Afanasyev847de402017-09-21 18:57:30 -0400177 void
Junxiao Shi029401f2016-08-05 12:55:14 +0000178 advance(Iterator& i) override;
179
180private:
181 EntrySubTreeSelector m_pred;
182};
183
184/** \brief partial enumeration implementation
185 *
186 * Iterator::m_ref should be initialized to longest prefix matched entry.
187 */
188class PrefixMatchImpl : public EnumerationImpl
189{
190public:
191 PrefixMatchImpl(const NameTree& nt, const EntrySelector& pred);
192
193private:
Alexander Afanasyev847de402017-09-21 18:57:30 -0400194 void
Junxiao Shi029401f2016-08-05 12:55:14 +0000195 advance(Iterator& i) override;
196
197private:
198 EntrySelector m_pred;
199};
200
Junxiao Shi9f6ca602016-08-15 04:50:29 +0000201/** \brief a Forward Range of name tree entries
202 *
203 * This type has .begin() and .end() methods which return Iterator.
204 * This type is usable with range-based for.
205 */
Davide Pesavento87fc0f82018-04-11 23:43:51 -0400206using Range = boost::iterator_range<Iterator>;
Junxiao Shi9f6ca602016-08-15 04:50:29 +0000207
Junxiao Shi029401f2016-08-05 12:55:14 +0000208} // namespace name_tree
209} // namespace nfd
210
211#endif // NFD_DAEMON_TABLE_NAME_TREE_ITERATOR_HPP