blob: f7ae4d5acc1caffd575d664d1ea24fa47bb7c9e8 [file] [log] [blame]
Junxiao Shic1e12362014-01-24 20:03:26 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -07003 * Copyright (c) 2014 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 *
10 * This file is part of NFD (Named Data Networking Forwarding Daemon).
11 * See AUTHORS.md for complete list of NFD authors and contributors.
12 *
13 * NFD is free software: you can redistribute it and/or modify it under the terms
14 * of the GNU General Public License as published by the Free Software Foundation,
15 * either version 3 of the License, or (at your option) any later version.
16 *
17 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
18 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
19 * PURPOSE. See the GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License along with
22 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
23 **/
Junxiao Shic1e12362014-01-24 20:03:26 -070024
25#ifndef NFD_TABLE_FIB_HPP
26#define NFD_TABLE_FIB_HPP
27
28#include "fib-entry.hpp"
HangZhangad4afd12014-03-01 11:03:08 +080029#include "name-tree.hpp"
Junxiao Shidbe71732014-02-21 22:23:28 -070030
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080031namespace nfd {
Junxiao Shic1e12362014-01-24 20:03:26 -070032
HangZhangad4afd12014-03-01 11:03:08 +080033namespace measurements {
34class Entry;
35}
36namespace pit {
37class Entry;
38}
39
Junxiao Shic1e12362014-01-24 20:03:26 -070040/** \class Fib
41 * \brief represents the FIB
42 */
43class Fib : noncopyable
44{
45public:
HangZhang5d469422014-03-12 09:26:26 +080046 class const_iterator;
47
HangZhangad4afd12014-03-01 11:03:08 +080048 explicit
49 Fib(NameTree& nameTree);
Steve DiBenedettod5f87932014-02-05 15:11:39 -070050
Junxiao Shic1e12362014-01-24 20:03:26 -070051 ~Fib();
Steve DiBenedettod5f87932014-02-05 15:11:39 -070052
Junxiao Shic1e12362014-01-24 20:03:26 -070053 /** \brief inserts a FIB entry for prefix
54 * If an entry for exact same prefix exists, that entry is returned.
55 * \return{ the entry, and true for new entry, false for existing entry }
56 */
57 std::pair<shared_ptr<fib::Entry>, bool>
58 insert(const Name& prefix);
Steve DiBenedettod5f87932014-02-05 15:11:39 -070059
Junxiao Shic1e12362014-01-24 20:03:26 -070060 /// performs a longest prefix match
61 shared_ptr<fib::Entry>
62 findLongestPrefixMatch(const Name& prefix) const;
Steve DiBenedettod5f87932014-02-05 15:11:39 -070063
Junxiao Shidbe71732014-02-21 22:23:28 -070064 /// performs a longest prefix match
65 shared_ptr<fib::Entry>
66 findLongestPrefixMatch(const pit::Entry& pitEntry) const;
67
68 /// performs a longest prefix match
69 shared_ptr<fib::Entry>
70 findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const;
71
Steve DiBenedettod5f87932014-02-05 15:11:39 -070072 shared_ptr<fib::Entry>
73 findExactMatch(const Name& prefix) const;
74
75 void
HangZhangad4afd12014-03-01 11:03:08 +080076 erase(const Name& prefix);
Steve DiBenedettod5f87932014-02-05 15:11:39 -070077
Steve DiBenedettod030cfc2014-03-10 20:04:47 -060078 void
79 erase(const fib::Entry& entry);
80
Junxiao Shic1e12362014-01-24 20:03:26 -070081 /** \brief removes the NextHop record for face in all entrites
82 * This is usually invoked when face goes away.
83 * Removing all NextHops in a FIB entry will not remove the FIB entry.
84 */
85 void
86 removeNextHopFromAllEntries(shared_ptr<Face> face);
87
HangZhangad4afd12014-03-01 11:03:08 +080088 size_t
89 size() const;
90
HangZhang5d469422014-03-12 09:26:26 +080091 const_iterator
92 begin() const;
93
94 const_iterator
95 end() const;
96
97 class const_iterator : public std::iterator<std::forward_iterator_tag, fib::Entry>
98 {
99 public:
100 explicit
101 const_iterator(const NameTree::const_iterator& it);
102
103 ~const_iterator();
104
105 const fib::Entry&
106 operator*() const;
107
108 shared_ptr<fib::Entry>
109 operator->() const;
110
111 const_iterator&
112 operator++();
113
114 const_iterator
115 operator++(int);
116
117 bool
118 operator==(const const_iterator& other) const;
119
120 bool
121 operator!=(const const_iterator& other) const;
122
123 private:
124 NameTree::const_iterator m_nameTreeIterator;
125 };
126
Junxiao Shic1e12362014-01-24 20:03:26 -0700127private:
HangZhangcb4fc832014-03-11 16:57:11 +0800128 shared_ptr<fib::Entry>
129 findLongestPrefixMatch(shared_ptr<name_tree::Entry> nameTreeEntry) const;
130
Junxiao Shiefceadc2014-03-09 18:52:57 -0700131private:
HangZhangad4afd12014-03-01 11:03:08 +0800132 NameTree& m_nameTree;
Junxiao Shi40631842014-03-01 13:52:37 -0700133 size_t m_nItems;
Junxiao Shiefceadc2014-03-09 18:52:57 -0700134
Junxiao Shi40631842014-03-01 13:52:37 -0700135 /** \brief The empty FIB entry.
136 *
137 * This entry has no nexthops.
138 * It is returned by findLongestPrefixMatch if nothing is matched.
139 */
140 // Returning empty entry instead of nullptr makes forwarding and strategy implementation easier.
HangZhangcb4fc832014-03-11 16:57:11 +0800141 static const shared_ptr<fib::Entry> s_emptyEntry;
Junxiao Shic1e12362014-01-24 20:03:26 -0700142};
143
HangZhangad4afd12014-03-01 11:03:08 +0800144inline size_t
145Fib::size() const
146{
147 return m_nItems;
148}
149
HangZhang5d469422014-03-12 09:26:26 +0800150inline Fib::const_iterator
151Fib::end() const
152{
153 return const_iterator(m_nameTree.end());
154}
155
156inline
157Fib::const_iterator::const_iterator(const NameTree::const_iterator& it)
158 : m_nameTreeIterator(it)
159{
160}
161
162inline
163Fib::const_iterator::~const_iterator()
164{
165}
166
167inline
168Fib::const_iterator
169Fib::const_iterator::operator++(int)
170{
171 Fib::const_iterator temp(*this);
172 ++(*this);
173 return temp;
174}
175
176inline Fib::const_iterator&
177Fib::const_iterator::operator++()
178{
179 ++m_nameTreeIterator;
180 return *this;
181}
182
183inline const fib::Entry&
184Fib::const_iterator::operator*() const
185{
186 return *(m_nameTreeIterator->getFibEntry());
187}
188
189inline shared_ptr<fib::Entry>
190Fib::const_iterator::operator->() const
191{
192 return m_nameTreeIterator->getFibEntry();
193}
194
195inline bool
196Fib::const_iterator::operator==(const Fib::const_iterator& other) const
197{
198 return m_nameTreeIterator == other.m_nameTreeIterator;
199}
200
201inline bool
202Fib::const_iterator::operator!=(const Fib::const_iterator& other) const
203{
204 return m_nameTreeIterator != other.m_nameTreeIterator;
205}
206
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800207} // namespace nfd
Junxiao Shic1e12362014-01-24 20:03:26 -0700208
209#endif // NFD_TABLE_FIB_HPP