fib.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2022, 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 #include "fib.hpp"
27 #include "pit-entry.hpp"
28 #include "measurements-entry.hpp"
29 
30 #include <ndn-cxx/util/concepts.hpp>
31 
32 namespace nfd::fib {
33 
35 
36 const unique_ptr<Entry> Fib::s_emptyEntry = make_unique<Entry>(Name());
37 
38 static inline bool
40 {
41  return nte.getFibEntry() != nullptr;
42 }
43 
44 Fib::Fib(NameTree& nameTree)
45  : m_nameTree(nameTree)
46 {
47 }
48 
49 template<typename K>
50 const Entry&
51 Fib::findLongestPrefixMatchImpl(const K& key) const
52 {
54  if (nte != nullptr) {
55  return *nte->getFibEntry();
56  }
57  return *s_emptyEntry;
58 }
59 
60 const Entry&
61 Fib::findLongestPrefixMatch(const Name& prefix) const
62 {
63  return this->findLongestPrefixMatchImpl(prefix);
64 }
65 
66 const Entry&
68 {
69  return this->findLongestPrefixMatchImpl(pitEntry);
70 }
71 
72 const Entry&
73 Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
74 {
75  return this->findLongestPrefixMatchImpl(measurementsEntry);
76 }
77 
78 Entry*
79 Fib::findExactMatch(const Name& prefix)
80 {
81  name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
82  if (nte != nullptr)
83  return nte->getFibEntry();
84 
85  return nullptr;
86 }
87 
88 std::pair<Entry*, bool>
89 Fib::insert(const Name& prefix)
90 {
91  name_tree::Entry& nte = m_nameTree.lookup(prefix);
92  Entry* entry = nte.getFibEntry();
93  if (entry != nullptr) {
94  return {entry, false};
95  }
96 
97  nte.setFibEntry(make_unique<Entry>(prefix));
98  ++m_nItems;
99  return {nte.getFibEntry(), true};
100 }
101 
102 void
103 Fib::erase(name_tree::Entry* nte, bool canDeleteNte)
104 {
105  BOOST_ASSERT(nte != nullptr);
106 
107  nte->setFibEntry(nullptr);
108  if (canDeleteNte) {
109  m_nameTree.eraseIfEmpty(nte);
110  }
111  --m_nItems;
112 }
113 
114 void
115 Fib::erase(const Name& prefix)
116 {
117  name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
118  if (nte != nullptr) {
119  this->erase(nte);
120  }
121 }
122 
123 void
124 Fib::erase(const Entry& entry)
125 {
126  name_tree::Entry* nte = m_nameTree.getEntry(entry);
127  if (nte == nullptr) { // don't try to erase s_emptyEntry
128  BOOST_ASSERT(&entry == s_emptyEntry.get());
129  return;
130  }
131  this->erase(nte);
132 }
133 
134 void
135 Fib::addOrUpdateNextHop(Entry& entry, Face& face, uint64_t cost)
136 {
137  auto [it, isNew] = entry.addOrUpdateNextHop(face, cost);
138  if (isNew)
139  this->afterNewNextHop(entry.getPrefix(), *it);
140 }
141 
143 Fib::removeNextHop(Entry& entry, const Face& face)
144 {
145  bool isRemoved = entry.removeNextHop(face);
146 
147  if (!isRemoved) {
149  }
150  else if (!entry.hasNextHops()) {
151  name_tree::Entry* nte = m_nameTree.getEntry(entry);
152  this->erase(nte, false);
154  }
155  else {
157  }
158 }
159 
161 Fib::getRange() const
162 {
163  return m_nameTree.fullEnumerate(&nteHasFibEntry) |
164  boost::adaptors::transformed(name_tree::GetTableEntry<Entry>(&name_tree::Entry::getFibEntry));
165 }
166 
167 } // namespace nfd::fib
Generalization of a network interface.
Definition: face.hpp:56
Represents an entry in the FIB.
Definition: fib-entry.hpp:54
bool hasNextHops() const
Definition: fib-entry.hpp:74
const Name & getPrefix() const
Definition: fib-entry.hpp:60
RemoveNextHopResult
Definition: fib.hpp:116
@ NEXTHOP_REMOVED
the nexthop is removed and the fib entry stays
@ FIB_ENTRY_REMOVED
the nexthop is removed and the fib entry is removed
@ NO_SUCH_NEXTHOP
the nexthop is not found
std::pair< Entry *, bool > insert(const Name &prefix)
Find or insert a FIB entry.
Definition: fib.cpp:89
Entry * findExactMatch(const Name &prefix)
Performs an exact match lookup.
Definition: fib.cpp:79
boost::range_iterator< Range >::type const_iterator
Definition: fib.hpp:129
RemoveNextHopResult removeNextHop(Entry &entry, const Face &face)
Remove the NextHop record for face from entry.
Definition: fib.cpp:143
boost::transformed_range< name_tree::GetTableEntry< Entry >, const name_tree::Range > Range
Definition: fib.hpp:128
signal::Signal< Fib, Name, NextHop > afterNewNextHop
Signals on Fib entry nexthop creation.
Definition: fib.hpp:154
void erase(const Name &prefix)
Definition: fib.cpp:115
Fib(NameTree &nameTree)
Definition: fib.cpp:44
const Entry & findLongestPrefixMatch(const Name &prefix) const
Performs a longest prefix match.
Definition: fib.cpp:61
void addOrUpdateNextHop(Entry &entry, Face &face, uint64_t cost)
Add a NextHop record.
Definition: fib.cpp:135
Represents an entry in the Measurements table.
An entry in the name tree.
fib::Entry * getFibEntry() const
void setFibEntry(unique_ptr< fib::Entry > fibEntry)
A functor to get a table entry from a name tree entry.
A common index structure for FIB, PIT, StrategyChoice, and Measurements.
Definition: name-tree.hpp:37
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
Delete the entry if it is empty.
Definition: name-tree.cpp:122
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
Enumerate all entries.
Definition: name-tree.cpp:225
Entry & lookup(const Name &name, size_t prefixLen)
Find or insert an entry by name.
Definition: name-tree.cpp:43
Entry * getEntry(const EntryT &tableEntry) const
Definition: name-tree.hpp:77
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
Exact match lookup.
Definition: name-tree.cpp:149
Entry * findLongestPrefixMatch(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
Longest prefix matching.
Definition: name-tree.cpp:161
Represents an entry in the Interest table (PIT).
Definition: pit-entry.hpp:62
NDN_CXX_ASSERT_FORWARD_ITERATOR(Fib::const_iterator)
static bool nteHasFibEntry(const name_tree::Entry &nte)
Definition: fib.cpp:39