Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 1 | /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
Junxiao Shi | 7530635 | 2018-02-01 21:59:44 +0000 | [diff] [blame] | 2 | /* |
Davide Pesavento | b7bfcb9 | 2022-05-22 23:55:23 -0400 | [diff] [blame^] | 3 | * Copyright (c) 2014-2022, Regents of the University of California, |
Alexander Afanasyev | 319f2c8 | 2015-01-07 14:56:53 -0800 | [diff] [blame] | 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 | |
Junxiao Shi | 13ad4b7 | 2016-08-15 04:51:21 +0000 | [diff] [blame] | 32 | #include <boost/range/adaptor/transformed.hpp> |
| 33 | |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 34 | namespace nfd { |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 35 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 36 | namespace measurements { |
| 37 | class Entry; |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 38 | } // namespace measurements |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 39 | namespace pit { |
| 40 | class Entry; |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 41 | } // namespace pit |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 42 | |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 43 | namespace fib { |
| 44 | |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 45 | /** \brief Represents the Forwarding Information Base (FIB) |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 46 | */ |
| 47 | class Fib : noncopyable |
| 48 | { |
| 49 | public: |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 50 | explicit |
| 51 | Fib(NameTree& nameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 52 | |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 53 | size_t |
Junxiao Shi | 13ad4b7 | 2016-08-15 04:51:21 +0000 | [diff] [blame] | 54 | size() const |
| 55 | { |
| 56 | return m_nItems; |
| 57 | } |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 58 | |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 59 | public: // lookup |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 60 | /** \brief Performs a longest prefix match |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 61 | */ |
| 62 | const Entry& |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 63 | findLongestPrefixMatch(const Name& prefix) const; |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 64 | |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 65 | /** \brief Performs a longest prefix match |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 66 | * |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 67 | * This is equivalent to `findLongestPrefixMatch(pitEntry.getName())` |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 68 | */ |
| 69 | const Entry& |
Junxiao Shi | dbe7173 | 2014-02-21 22:23:28 -0700 | [diff] [blame] | 70 | findLongestPrefixMatch(const pit::Entry& pitEntry) const; |
| 71 | |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 72 | /** \brief Performs a longest prefix match |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 73 | * |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 74 | * This is equivalent to `findLongestPrefixMatch(measurementsEntry.getName())` |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 75 | */ |
| 76 | const Entry& |
Junxiao Shi | dbe7173 | 2014-02-21 22:23:28 -0700 | [diff] [blame] | 77 | findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const; |
| 78 | |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 79 | /** \brief Performs an exact match lookup |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 80 | */ |
| 81 | Entry* |
| 82 | findExactMatch(const Name& prefix); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 83 | |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 84 | public: // mutation |
Junxiao Shi | 7530635 | 2018-02-01 21:59:44 +0000 | [diff] [blame] | 85 | /** \brief Maximum number of components in a FIB entry prefix. |
Junxiao Shi | 7530635 | 2018-02-01 21:59:44 +0000 | [diff] [blame] | 86 | */ |
| 87 | static constexpr size_t |
| 88 | getMaxDepth() |
| 89 | { |
Davide Pesavento | 2cae8ca | 2019-04-18 20:48:05 -0400 | [diff] [blame] | 90 | return NameTree::getMaxDepth(); |
Junxiao Shi | 7530635 | 2018-02-01 21:59:44 +0000 | [diff] [blame] | 91 | } |
| 92 | |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 93 | /** \brief Find or insert a FIB entry |
| 94 | * \param prefix FIB entry name; it must not have more than \c getMaxDepth() components. |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 95 | * \return the entry, and true for new entry or false for existing entry |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 96 | */ |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 97 | std::pair<Entry*, bool> |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 98 | insert(const Name& prefix); |
| 99 | |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 100 | void |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 101 | erase(const Name& prefix); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 102 | |
Steve DiBenedetto | d030cfc | 2014-03-10 20:04:47 -0600 | [diff] [blame] | 103 | void |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 104 | erase(const Entry& entry); |
Steve DiBenedetto | d030cfc | 2014-03-10 20:04:47 -0600 | [diff] [blame] | 105 | |
Ju Pan | d8315bf | 2019-07-31 06:59:07 +0000 | [diff] [blame] | 106 | /** \brief Add a NextHop record |
| 107 | * |
| 108 | * If a NextHop record for \p face already exists in \p entry, its cost is set to \p cost. |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 109 | */ |
| 110 | void |
Ju Pan | d8315bf | 2019-07-31 06:59:07 +0000 | [diff] [blame] | 111 | addOrUpdateNextHop(Entry& entry, Face& face, uint64_t cost); |
| 112 | |
| 113 | enum class RemoveNextHopResult { |
| 114 | NO_SUCH_NEXTHOP, ///< the nexthop is not found |
| 115 | NEXTHOP_REMOVED, ///< the nexthop is removed and the fib entry stays |
| 116 | FIB_ENTRY_REMOVED ///< the nexthop is removed and the fib entry is removed |
| 117 | }; |
| 118 | |
| 119 | /** \brief Remove the NextHop record for \p face from \p entry |
| 120 | */ |
| 121 | RemoveNextHopResult |
Md Ashiqur Rahman | 6be9387 | 2019-08-07 01:25:31 +0000 | [diff] [blame] | 122 | removeNextHop(Entry& entry, const Face& face); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 123 | |
Junxiao Shi | 56a21bf | 2014-11-02 21:11:50 -0700 | [diff] [blame] | 124 | public: // enumeration |
Davide Pesavento | b7bfcb9 | 2022-05-22 23:55:23 -0400 | [diff] [blame^] | 125 | using Range = boost::transformed_range<name_tree::GetTableEntry<Entry>, const name_tree::Range>; |
| 126 | using const_iterator = boost::range_iterator<Range>::type; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 127 | |
Junxiao Shi | b30863e | 2016-08-15 21:32:01 +0000 | [diff] [blame] | 128 | /** \return an iterator to the beginning |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 129 | * \note The iteration order is implementation-defined. |
Junxiao Shi | b30863e | 2016-08-15 21:32:01 +0000 | [diff] [blame] | 130 | * \warning Undefined behavior may occur if a FIB/PIT/Measurements/StrategyChoice entry |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 131 | * is inserted or erased during iteration. |
Alexander Afanasyev | 09fc3d9 | 2015-01-03 02:02:37 -0800 | [diff] [blame] | 132 | */ |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 133 | const_iterator |
Junxiao Shi | 13ad4b7 | 2016-08-15 04:51:21 +0000 | [diff] [blame] | 134 | begin() const |
| 135 | { |
| 136 | return this->getRange().begin(); |
| 137 | } |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 138 | |
Junxiao Shi | b30863e | 2016-08-15 21:32:01 +0000 | [diff] [blame] | 139 | /** \return an iterator to the end |
| 140 | * \sa begin() |
Alexander Afanasyev | 09fc3d9 | 2015-01-03 02:02:37 -0800 | [diff] [blame] | 141 | */ |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 142 | const_iterator |
Junxiao Shi | 13ad4b7 | 2016-08-15 04:51:21 +0000 | [diff] [blame] | 143 | end() const |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 144 | { |
Junxiao Shi | 13ad4b7 | 2016-08-15 04:51:21 +0000 | [diff] [blame] | 145 | return this->getRange().end(); |
| 146 | } |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 147 | |
Ju Pan | d8315bf | 2019-07-31 06:59:07 +0000 | [diff] [blame] | 148 | public: // signal |
| 149 | /** \brief signals on Fib entry nexthop creation |
| 150 | */ |
| 151 | signal::Signal<Fib, Name, NextHop> afterNewNextHop; |
| 152 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 153 | private: |
Junxiao Shi | dd8f661 | 2016-08-12 15:42:52 +0000 | [diff] [blame] | 154 | /** \tparam K a parameter acceptable to NameTree::findLongestPrefixMatch |
| 155 | */ |
| 156 | template<typename K> |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 157 | const Entry& |
Junxiao Shi | dd8f661 | 2016-08-12 15:42:52 +0000 | [diff] [blame] | 158 | findLongestPrefixMatchImpl(const K& key) const; |
HangZhang | cb4fc83 | 2014-03-11 16:57:11 +0800 | [diff] [blame] | 159 | |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 160 | void |
Junxiao Shi | 811c010 | 2016-08-10 04:12:45 +0000 | [diff] [blame] | 161 | erase(name_tree::Entry* nte, bool canDeleteNte = true); |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 162 | |
Junxiao Shi | 13ad4b7 | 2016-08-15 04:51:21 +0000 | [diff] [blame] | 163 | Range |
| 164 | getRange() const; |
| 165 | |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 166 | private: |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 167 | NameTree& m_nameTree; |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 168 | size_t m_nItems = 0; |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 169 | |
Davide Pesavento | 50a6af3 | 2019-02-21 00:04:40 -0500 | [diff] [blame] | 170 | /** \brief The empty FIB entry. |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 171 | * |
| 172 | * This entry has no nexthops. |
| 173 | * It is returned by findLongestPrefixMatch if nothing is matched. |
| 174 | */ |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 175 | static const unique_ptr<Entry> s_emptyEntry; |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 176 | }; |
| 177 | |
Junxiao Shi | a6de429 | 2016-07-12 02:08:10 +0000 | [diff] [blame] | 178 | } // namespace fib |
| 179 | |
| 180 | using fib::Fib; |
| 181 | |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 182 | } // namespace nfd |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 183 | |
Alexander Afanasyev | 613e2a9 | 2014-04-15 13:36:58 -0700 | [diff] [blame] | 184 | #endif // NFD_DAEMON_TABLE_FIB_HPP |