Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 1 | /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
| 2 | /** |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 3 | * 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 | * The University of Memphis |
Alexander Afanasyev | 9bcbc7c | 2014-04-06 19:37:37 -0700 | [diff] [blame] | 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/>. |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 24 | */ |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 25 | |
Alexander Afanasyev | 613e2a9 | 2014-04-15 13:36:58 -0700 | [diff] [blame] | 26 | #ifndef NFD_DAEMON_TABLE_FIB_HPP |
| 27 | #define NFD_DAEMON_TABLE_FIB_HPP |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 28 | |
| 29 | #include "fib-entry.hpp" |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 30 | #include "name-tree.hpp" |
Junxiao Shi | dbe7173 | 2014-02-21 22:23:28 -0700 | [diff] [blame] | 31 | |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 32 | namespace nfd { |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 33 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 34 | namespace measurements { |
| 35 | class Entry; |
| 36 | } |
| 37 | namespace pit { |
| 38 | class Entry; |
| 39 | } |
| 40 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 41 | /** \class Fib |
| 42 | * \brief represents the FIB |
| 43 | */ |
| 44 | class Fib : noncopyable |
| 45 | { |
| 46 | public: |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 47 | explicit |
| 48 | Fib(NameTree& nameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 49 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 50 | ~Fib(); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 51 | |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 52 | size_t |
| 53 | size() const; |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 54 | |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 55 | public: // lookup |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 56 | /// performs a longest prefix match |
| 57 | shared_ptr<fib::Entry> |
| 58 | findLongestPrefixMatch(const Name& prefix) const; |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 59 | |
Junxiao Shi | dbe7173 | 2014-02-21 22:23:28 -0700 | [diff] [blame] | 60 | /// performs a longest prefix match |
| 61 | shared_ptr<fib::Entry> |
| 62 | findLongestPrefixMatch(const pit::Entry& pitEntry) const; |
| 63 | |
| 64 | /// performs a longest prefix match |
| 65 | shared_ptr<fib::Entry> |
| 66 | findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const; |
| 67 | |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 68 | shared_ptr<fib::Entry> |
| 69 | findExactMatch(const Name& prefix) const; |
| 70 | |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 71 | public: // mutation |
| 72 | /** \brief inserts a FIB entry for prefix |
| 73 | * If an entry for exact same prefix exists, that entry is returned. |
| 74 | * \return{ the entry, and true for new entry, false for existing entry } |
| 75 | */ |
| 76 | std::pair<shared_ptr<fib::Entry>, bool> |
| 77 | insert(const Name& prefix); |
| 78 | |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 79 | void |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 80 | erase(const Name& prefix); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 81 | |
Steve DiBenedetto | d030cfc | 2014-03-10 20:04:47 -0600 | [diff] [blame] | 82 | void |
| 83 | erase(const fib::Entry& entry); |
| 84 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 85 | /** \brief removes the NextHop record for face in all entrites |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 86 | * |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 87 | * This is usually invoked when face goes away. |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 88 | * Removing the last NextHop in a FIB entry will erase the FIB entry. |
| 89 | * |
| 90 | * \todo change parameter type to Face& |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 91 | */ |
| 92 | void |
| 93 | removeNextHopFromAllEntries(shared_ptr<Face> face); |
| 94 | |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 95 | public: // enumeration |
| 96 | class const_iterator; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 97 | |
Alexander Afanasyev | 09fc3d9 | 2015-01-03 02:02:37 -0800 | [diff] [blame^] | 98 | /** \brief returns an iterator pointing to the first FIB entry |
| 99 | * \note Iteration order is implementation-specific and is undefined |
| 100 | * \note The returned iterator may get invalidated if FIB or another NameTree-based |
| 101 | * table is modified |
| 102 | */ |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 103 | const_iterator |
| 104 | begin() const; |
| 105 | |
Alexander Afanasyev | 09fc3d9 | 2015-01-03 02:02:37 -0800 | [diff] [blame^] | 106 | /** \brief returns an iterator referring to the past-the-end FIB entry |
| 107 | * \note The returned iterator may get invalidated if FIB or another NameTree-based |
| 108 | * table is modified |
| 109 | */ |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 110 | const_iterator |
| 111 | end() const; |
| 112 | |
Alexander Afanasyev | 09fc3d9 | 2015-01-03 02:02:37 -0800 | [diff] [blame^] | 113 | class const_iterator : public std::iterator<std::forward_iterator_tag, const fib::Entry> |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 114 | { |
| 115 | public: |
Alexander Afanasyev | 09fc3d9 | 2015-01-03 02:02:37 -0800 | [diff] [blame^] | 116 | const_iterator() = default; |
| 117 | |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 118 | explicit |
| 119 | const_iterator(const NameTree::const_iterator& it); |
| 120 | |
| 121 | ~const_iterator(); |
| 122 | |
| 123 | const fib::Entry& |
| 124 | operator*() const; |
| 125 | |
| 126 | shared_ptr<fib::Entry> |
| 127 | operator->() const; |
| 128 | |
| 129 | const_iterator& |
| 130 | operator++(); |
| 131 | |
| 132 | const_iterator |
| 133 | operator++(int); |
| 134 | |
| 135 | bool |
| 136 | operator==(const const_iterator& other) const; |
| 137 | |
| 138 | bool |
| 139 | operator!=(const const_iterator& other) const; |
| 140 | |
| 141 | private: |
| 142 | NameTree::const_iterator m_nameTreeIterator; |
| 143 | }; |
| 144 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 145 | private: |
HangZhang | cb4fc83 | 2014-03-11 16:57:11 +0800 | [diff] [blame] | 146 | shared_ptr<fib::Entry> |
| 147 | findLongestPrefixMatch(shared_ptr<name_tree::Entry> nameTreeEntry) const; |
| 148 | |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 149 | void |
| 150 | erase(shared_ptr<name_tree::Entry> nameTreeEntry); |
| 151 | |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 152 | private: |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 153 | NameTree& m_nameTree; |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 154 | size_t m_nItems; |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 155 | |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 156 | /** \brief The empty FIB entry. |
| 157 | * |
| 158 | * This entry has no nexthops. |
| 159 | * It is returned by findLongestPrefixMatch if nothing is matched. |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 160 | * Returning empty entry instead of nullptr makes forwarding and strategy implementation easier. |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 161 | */ |
HangZhang | cb4fc83 | 2014-03-11 16:57:11 +0800 | [diff] [blame] | 162 | static const shared_ptr<fib::Entry> s_emptyEntry; |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 163 | }; |
| 164 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 165 | inline size_t |
| 166 | Fib::size() const |
| 167 | { |
| 168 | return m_nItems; |
| 169 | } |
| 170 | |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 171 | inline Fib::const_iterator |
| 172 | Fib::end() const |
| 173 | { |
| 174 | return const_iterator(m_nameTree.end()); |
| 175 | } |
| 176 | |
| 177 | inline |
| 178 | Fib::const_iterator::const_iterator(const NameTree::const_iterator& it) |
| 179 | : m_nameTreeIterator(it) |
| 180 | { |
| 181 | } |
| 182 | |
| 183 | inline |
| 184 | Fib::const_iterator::~const_iterator() |
| 185 | { |
| 186 | } |
| 187 | |
| 188 | inline |
| 189 | Fib::const_iterator |
| 190 | Fib::const_iterator::operator++(int) |
| 191 | { |
| 192 | Fib::const_iterator temp(*this); |
| 193 | ++(*this); |
| 194 | return temp; |
| 195 | } |
| 196 | |
| 197 | inline Fib::const_iterator& |
| 198 | Fib::const_iterator::operator++() |
| 199 | { |
| 200 | ++m_nameTreeIterator; |
| 201 | return *this; |
| 202 | } |
| 203 | |
| 204 | inline const fib::Entry& |
| 205 | Fib::const_iterator::operator*() const |
| 206 | { |
Alexander Afanasyev | 09fc3d9 | 2015-01-03 02:02:37 -0800 | [diff] [blame^] | 207 | return *this->operator->(); |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 208 | } |
| 209 | |
| 210 | inline shared_ptr<fib::Entry> |
| 211 | Fib::const_iterator::operator->() const |
| 212 | { |
| 213 | return m_nameTreeIterator->getFibEntry(); |
| 214 | } |
| 215 | |
| 216 | inline bool |
| 217 | Fib::const_iterator::operator==(const Fib::const_iterator& other) const |
| 218 | { |
| 219 | return m_nameTreeIterator == other.m_nameTreeIterator; |
| 220 | } |
| 221 | |
| 222 | inline bool |
| 223 | Fib::const_iterator::operator!=(const Fib::const_iterator& other) const |
| 224 | { |
| 225 | return m_nameTreeIterator != other.m_nameTreeIterator; |
| 226 | } |
| 227 | |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 228 | } // namespace nfd |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 229 | |
Alexander Afanasyev | 613e2a9 | 2014-04-15 13:36:58 -0700 | [diff] [blame] | 230 | #endif // NFD_DAEMON_TABLE_FIB_HPP |