NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
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 
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  , m_nItems(0)
48 {
49 }
50 
51 template<typename K>
52 const Entry&
53 Fib::findLongestPrefixMatchImpl(const K& key) const
54 {
56  if (nte != nullptr) {
57  return *nte->getFibEntry();
58  }
59  return *s_emptyEntry;
60 }
61 
62 const Entry&
63 Fib::findLongestPrefixMatch(const Name& prefix) const
64 {
65  return this->findLongestPrefixMatchImpl(prefix);
66 }
67 
68 const Entry&
70 {
71  return this->findLongestPrefixMatchImpl(pitEntry);
72 }
73 
74 const Entry&
75 Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
76 {
77  return this->findLongestPrefixMatchImpl(measurementsEntry);
78 }
79 
80 Entry*
81 Fib::findExactMatch(const Name& prefix)
82 {
83  name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
84  if (nte != nullptr)
85  return nte->getFibEntry();
86 
87  return nullptr;
88 }
89 
90 std::pair<Entry*, bool>
91 Fib::insert(const Name& prefix)
92 {
93  name_tree::Entry& nte = m_nameTree.lookup(prefix);
94  Entry* entry = nte.getFibEntry();
95  if (entry != nullptr) {
96  return {entry, false};
97  }
98 
99  nte.setFibEntry(make_unique<Entry>(prefix));
100  ++m_nItems;
101  return {nte.getFibEntry(), true};
102 }
103 
104 void
105 Fib::erase(name_tree::Entry* nte, bool canDeleteNte)
106 {
107  BOOST_ASSERT(nte != nullptr);
108 
109  nte->setFibEntry(nullptr);
110  if (canDeleteNte) {
111  m_nameTree.eraseIfEmpty(nte);
112  }
113  --m_nItems;
114 }
115 
116 void
117 Fib::erase(const Name& prefix)
118 {
119  name_tree::Entry* nte = m_nameTree.findExactMatch(prefix);
120  if (nte != nullptr) {
121  this->erase(nte);
122  }
123 }
124 
125 void
126 Fib::erase(const Entry& entry)
127 {
128  name_tree::Entry* nte = m_nameTree.getEntry(entry);
129  if (nte == nullptr) { // don't try to erase s_emptyEntry
130  BOOST_ASSERT(&entry == s_emptyEntry.get());
131  return;
132  }
133  this->erase(nte);
134 }
135 
136 void
137 Fib::eraseIfEmpty(Entry& entry)
138 {
139  if (!entry.hasNextHops()) {
140  name_tree::Entry* nte = m_nameTree.getEntry(entry);
141  this->erase(nte, false);
142  }
143 }
144 
145 void
146 Fib::removeNextHop(Entry& entry, const Face& face, uint64_t endpointId)
147 {
148  entry.removeNextHop(face, endpointId);
149  this->eraseIfEmpty(entry);
150 }
151 
152 void
153 Fib::removeNextHopByFace(Entry& entry, const Face& face)
154 {
155  entry.removeNextHopByFace(face);
156  this->eraseIfEmpty(entry);
157 }
158 
160 Fib::getRange() const
161 {
162  return m_nameTree.fullEnumerate(&nteHasFibEntry) |
163  boost::adaptors::transformed(name_tree::GetTableEntry<Entry>(&name_tree::Entry::getFibEntry));
164 }
165 
166 } // namespace fib
167 } // namespace nfd
void removeNextHopByFace(Entry &entry, const Face &face)
removes the NextHop record for face for any endpointId
Definition: fib.cpp:153
std::pair< Entry *, bool > insert(const Name &prefix)
find or insert a FIB entry
Definition: fib.cpp:91
Fib(NameTree &nameTree)
Definition: fib.cpp:45
Entry * findExactMatch(const Name &prefix)
performs an exact match lookup
Definition: fib.cpp:81
void erase(const Name &prefix)
Definition: fib.cpp:117
generalization of a network interface
Definition: face.hpp:67
represents a FIB entry
Definition: fib-entry.hpp:51
fib::Entry * getFibEntry() const
const Entry & findLongestPrefixMatch(const Name &prefix) const
performs a longest prefix match
Definition: fib.cpp:63
Entry & lookup(const Name &name, size_t prefixLen)
find or insert an entry by name
Definition: name-tree.cpp:44
Entry * findLongestPrefixMatch(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
longest prefix matching
Definition: name-tree.cpp:162
represents a Measurements entry
NDN_CXX_ASSERT_FORWARD_ITERATOR(Fib::const_iterator)
void removeNextHop(Entry &entry, const Face &face, uint64_t endpointId)
removes the NextHop record for face with a given endpointId
Definition: fib.cpp:146
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
an Interest table entry
Definition: pit-entry.hpp:59
void removeNextHop(const Face &face, uint64_t endpointId)
removes the NextHop record for face with the given endpointId
Definition: fib-entry.cpp:65
Entry * getEntry(const EntryT &tableEntry) const
Definition: name-tree.hpp:79
Represents an absolute name.
Definition: name.hpp:43
boost::range_iterator< Range >::type const_iterator
Definition: fib.hpp:120
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
enumerate all entries
Definition: name-tree.cpp:226
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
delete the entry if it is empty
Definition: name-tree.cpp:123
a common index structure for FIB, PIT, StrategyChoice, and Measurements
Definition: name-tree.hpp:38
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
exact match lookup
Definition: name-tree.cpp:150
void removeNextHopByFace(const Face &face)
removes all NextHop records on face for any endpointId
Definition: fib-entry.cpp:74
a functor to get a table entry from a name tree entry
static bool nteHasFibEntry(const name_tree::Entry &nte)
Definition: fib.cpp:40
boost::transformed_range< name_tree::GetTableEntry< Entry >, const name_tree::Range > Range
Definition: fib.hpp:119
bool hasNextHops() const
Definition: fib-entry.hpp:72
void setFibEntry(unique_ptr< fib::Entry > fibEntry)
an entry in the name tree