NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: NDN, CCN, CCNx, content centric networks
API Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
fib.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "fib.hpp"
27 #include "pit-entry.hpp"
28 #include "measurements-entry.hpp"
29 
30 #include <boost/concept/assert.hpp>
31 #include <boost/concept_check.hpp>
32 #include <type_traits>
33 
34 namespace nfd {
35 
36 const shared_ptr<fib::Entry> Fib::s_emptyEntry = make_shared<fib::Entry>(Name());
37 
38 // http://en.cppreference.com/w/cpp/concept/ForwardIterator
39 BOOST_CONCEPT_ASSERT((boost::ForwardIterator<Fib::const_iterator>));
40 // boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
41 // which doesn't require DefaultConstructible
42 #ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
43 static_assert(std::is_default_constructible<Fib::const_iterator>::value,
44  "Fib::const_iterator must be default-constructible");
45 #else
46 BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Fib::const_iterator>));
47 #endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
48 
49 Fib::Fib(NameTree& nameTree)
50  : m_nameTree(nameTree)
51  , m_nItems(0)
52 {
53 }
54 
56 {
57 }
58 
59 static inline bool
61 {
62  return static_cast<bool>(entry.getFibEntry());
63 }
64 
65 shared_ptr<fib::Entry>
66 Fib::findLongestPrefixMatch(const Name& prefix) const
67 {
68  shared_ptr<name_tree::Entry> nameTreeEntry =
70  if (static_cast<bool>(nameTreeEntry)) {
71  return nameTreeEntry->getFibEntry();
72  }
73  return s_emptyEntry;
74 }
75 
76 shared_ptr<fib::Entry>
77 Fib::findLongestPrefixMatch(shared_ptr<name_tree::Entry> nameTreeEntry) const
78 {
79  shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
80  if (static_cast<bool>(entry))
81  return entry;
82  nameTreeEntry = m_nameTree.findLongestPrefixMatch(nameTreeEntry,
84  if (static_cast<bool>(nameTreeEntry)) {
85  return nameTreeEntry->getFibEntry();
86  }
87  return s_emptyEntry;
88 }
89 
90 shared_ptr<fib::Entry>
92 {
93  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(pitEntry);
94 
95  BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
96 
97  return findLongestPrefixMatch(nameTreeEntry);
98 }
99 
100 shared_ptr<fib::Entry>
101 Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
102 {
103  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(measurementsEntry);
104 
105  BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
106 
107  return findLongestPrefixMatch(nameTreeEntry);
108 }
109 
110 shared_ptr<fib::Entry>
111 Fib::findExactMatch(const Name& prefix) const
112 {
113  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
114  if (static_cast<bool>(nameTreeEntry))
115  return nameTreeEntry->getFibEntry();
116  return shared_ptr<fib::Entry>();
117 }
118 
119 std::pair<shared_ptr<fib::Entry>, bool>
120 Fib::insert(const Name& prefix)
121 {
122  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(prefix);
123  shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
124  if (static_cast<bool>(entry))
125  return std::make_pair(entry, false);
126  entry = make_shared<fib::Entry>(prefix);
127  nameTreeEntry->setFibEntry(entry);
128  ++m_nItems;
129  return std::make_pair(entry, true);
130 }
131 
132 void
133 Fib::erase(shared_ptr<name_tree::Entry> nameTreeEntry)
134 {
135  nameTreeEntry->setFibEntry(shared_ptr<fib::Entry>());
136  m_nameTree.eraseEntryIfEmpty(nameTreeEntry);
137  --m_nItems;
138 }
139 
140 void
141 Fib::erase(const Name& prefix)
142 {
143  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
144  if (static_cast<bool>(nameTreeEntry)) {
145  this->erase(nameTreeEntry);
146  }
147 }
148 
149 void
150 Fib::erase(const fib::Entry& entry)
151 {
152  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(entry);
153  if (static_cast<bool>(nameTreeEntry)) {
154  this->erase(nameTreeEntry);
155  }
156 }
157 
158 void
159 Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
160 {
161  std::list<fib::Entry*> toErase;
162 
163  auto&& enumerable = m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry);
164  for (const name_tree::Entry& nte : enumerable) {
165  shared_ptr<fib::Entry> entry = nte.getFibEntry();
166  entry->removeNextHop(face);
167  if (!entry->hasNextHops()) {
168  toErase.push_back(entry.get());
169  // entry needs to be erased, but we must wait until the enumeration ends,
170  // because otherwise NameTree iterator would be invalidated
171  }
172  }
173 
174  for (fib::Entry* entry : toErase) {
175  this->erase(*entry);
176  }
177 }
178 
180 Fib::begin() const
181 {
183 }
184 
185 } // namespace nfd
static bool predicate_NameTreeEntry_hasFibEntry(const name_tree::Entry &entry)
Definition: fib.cpp:60
shared_ptr< fib::Entry > findLongestPrefixMatch(const Name &prefix) const
performs a longest prefix match
Definition: fib.cpp:66
std::pair< shared_ptr< fib::Entry >, bool > insert(const Name &prefix)
inserts a FIB entry for prefix If an entry for exact same prefix exists, that entry is returned...
Definition: fib.cpp:120
represents a FIB entry
Definition: fib-entry.hpp:53
bool eraseEntryIfEmpty(shared_ptr< name_tree::Entry > entry)
Delete a Name Tree Entry if this entry is empty.
Definition: name-tree.cpp:327
shared_ptr< name_tree::Entry > get(const fib::Entry &fibEntry) const
get NameTree entry from attached FIB entry
Definition: name-tree.hpp:348
const_iterator begin() const
returns an iterator pointing to the first FIB entry
Definition: fib.cpp:180
shared_ptr< name_tree::Entry > findLongestPrefixMatch(const Name &prefix, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
Longest prefix matching for the given name.
Definition: name-tree.cpp:275
represents a Measurements entry
void removeNextHopFromAllEntries(shared_ptr< Face > face)
removes the NextHop record for face in all entrites
Definition: fib.cpp:159
void erase(const Name &prefix)
Definition: fib.cpp:141
represents a PIT entry
Definition: pit-entry.hpp:67
shared_ptr< fib::Entry > findExactMatch(const Name &prefix) const
Definition: fib.cpp:111
Class Name Tree.
Definition: name-tree.hpp:79
~Fib()
Definition: fib.cpp:55
shared_ptr< name_tree::Entry > lookup(const Name &prefix)
Look for the Name Tree Entry that contains this name prefix.
Definition: name-tree.cpp:205
shared_ptr< name_tree::Entry > findExactMatch(const Name &prefix) const
Exact match lookup for the given name prefix.
Definition: name-tree.cpp:243
Fib(NameTree &nameTree)
Definition: fib.cpp:49
boost::iterator_range< const_iterator > fullEnumerate(const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
Enumerate all entries, optionally filtered by an EntrySelector.
Definition: name-tree.cpp:406
Name Tree Entry Class.
shared_ptr< fib::Entry > getFibEntry() const