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-2019, 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 {
33 namespace fib {
34 
36 
37 const unique_ptr<Entry> Fib::s_emptyEntry = make_unique<Entry>(Name());
38 
39 static inline bool
41 {
42  return nte.getFibEntry() != nullptr;
43 }
44 
45 Fib::Fib(NameTree& nameTree)
46  : m_nameTree(nameTree)
47 {
48 }
49 
50 template<typename K>
51 const Entry&
52 Fib::findLongestPrefixMatchImpl(const K& key) const
53 {
54  name_tree::Entry* nte = m_nameTree.findLongestPrefixMatch(key, &nteHasFibEntry);
55  if (nte != nullptr) {
56  return *nte->getFibEntry();
57  }
58  return *s_emptyEntry;
59 }
60 
61 const Entry&
62 Fib::findLongestPrefixMatch(const Name& prefix) const
63 {
64  return this->findLongestPrefixMatchImpl(prefix);
65 }
66 
67 const Entry&
69 {
70  return this->findLongestPrefixMatchImpl(pitEntry);
71 }
72 
73 const Entry&
74 Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
75 {
76  return this->findLongestPrefixMatchImpl(measurementsEntry);
77 }
78 
79 Entry*
80 Fib::findExactMatch(const Name& prefix)
81 {
82  name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
83  if (nte != nullptr)
84  return nte->getFibEntry();
85 
86  return nullptr;
87 }
88 
89 std::pair<Entry*, bool>
90 Fib::insert(const Name& prefix)
91 {
92  name_tree::Entry& nte = m_nameTree.lookup(prefix);
93  Entry* entry = nte.getFibEntry();
94  if (entry != nullptr) {
95  return {entry, false};
96  }
97 
98  nte.setFibEntry(make_unique<Entry>(prefix));
99  ++m_nItems;
100  return {nte.getFibEntry(), true};
101 }
102 
103 void
104 Fib::erase(name_tree::Entry* nte, bool canDeleteNte)
105 {
106  BOOST_ASSERT(nte != nullptr);
107 
108  nte->setFibEntry(nullptr);
109  if (canDeleteNte) {
110  m_nameTree.eraseIfEmpty(nte);
111  }
112  --m_nItems;
113 }
114 
115 void
116 Fib::erase(const Name& prefix)
117 {
118  name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
119  if (nte != nullptr) {
120  this->erase(nte);
121  }
122 }
123 
124 void
125 Fib::erase(const Entry& entry)
126 {
127  name_tree::Entry* nte = m_nameTree.getEntry(entry);
128  if (nte == nullptr) { // don't try to erase s_emptyEntry
129  BOOST_ASSERT(&entry == s_emptyEntry.get());
130  return;
131  }
132  this->erase(nte);
133 }
134 
135 void
136 Fib::addOrUpdateNextHop(Entry& entry, Face& face, uint64_t cost)
137 {
138  NextHopList::iterator it;
139  bool isNew;
140  std::tie(it, isNew) = entry.addOrUpdateNextHop(face, cost);
141 
142  if (isNew)
143  this->afterNewNextHop(entry.getPrefix(), *it);
144 }
145 
147 Fib::removeNextHop(Entry& entry, const Face& face)
148 {
149  bool isRemoved = entry.removeNextHop(face);
150 
151  if (!isRemoved) {
153  }
154  else if (!entry.hasNextHops()) {
155  name_tree::Entry* nte = m_nameTree.getEntry(entry);
156  this->erase(nte, false);
158  }
159  else {
161  }
162 }
163 
165 Fib::getRange() const
166 {
167  return m_nameTree.fullEnumerate(&nteHasFibEntry) |
168  boost::adaptors::transformed(name_tree::GetTableEntry<Entry>(&name_tree::Entry::getFibEntry));
169 }
170 
171 } // namespace fib
172 } // namespace nfd
Entry * findExactMatch(const Name &prefix)
Performs an exact match lookup.
Definition: fib.cpp:80
void erase(const Name &prefix)
Definition: fib.cpp:116
Represents a Measurements entry.
Fib(NameTree &nameTree)
Definition: fib.cpp:45
represents a FIB entry
Definition: fib-entry.hpp:53
signal::Signal< Fib, Name, NextHop > afterNewNextHop
signals on Fib entry nexthop creation
Definition: fib.hpp:151
std::pair< Entry *, bool > insert(const Name &prefix)
Find or insert a FIB entry.
Definition: fib.cpp:90
NDN_CXX_ASSERT_FORWARD_ITERATOR(Fib::const_iterator)
boost::transformed_range< name_tree::GetTableEntry< Entry >, const name_tree::Range > Range
Definition: fib.hpp:125
fib::Entry * getFibEntry() const
An Interest table entry.
Definition: pit-entry.hpp:58
const Name & getPrefix() const
Definition: fib-entry.hpp:60
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
void setFibEntry(unique_ptr< fib::Entry > fibEntry)
the nexthop is removed and the fib entry is removed
An entry in the name tree.
void addOrUpdateNextHop(Entry &entry, Face &face, uint64_t cost)
Add a NextHop record.
Definition: fib.cpp:136
boost::range_iterator< Range >::type const_iterator
Definition: fib.hpp:126
RemoveNextHopResult
Definition: fib.hpp:113
const Entry & findLongestPrefixMatch(const Name &prefix) const
Performs a longest prefix match.
Definition: fib.cpp:62
RemoveNextHopResult removeNextHop(Entry &entry, const Face &face)
Remove the NextHop record for face from entry.
Definition: fib.cpp:147
a functor to get a table entry from a name tree entry
static bool nteHasFibEntry(const name_tree::Entry &nte)
Definition: fib.cpp:40
bool hasNextHops() const
Definition: fib-entry.hpp:74
the nexthop is removed and the fib entry stays