NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: 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; -*- */
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> nte = m_nameTree.findLongestPrefixMatch(pitEntry);
94  BOOST_ASSERT(nte != nullptr);
95  return findLongestPrefixMatch(nte);
96 }
97 
98 shared_ptr<fib::Entry>
99 Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
100 {
101  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(measurementsEntry);
102 
103  BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
104 
105  return findLongestPrefixMatch(nameTreeEntry);
106 }
107 
108 shared_ptr<fib::Entry>
109 Fib::findExactMatch(const Name& prefix) const
110 {
111  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
112  if (static_cast<bool>(nameTreeEntry))
113  return nameTreeEntry->getFibEntry();
114  return shared_ptr<fib::Entry>();
115 }
116 
117 std::pair<shared_ptr<fib::Entry>, bool>
118 Fib::insert(const Name& prefix)
119 {
120  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(prefix);
121  shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
122  if (static_cast<bool>(entry))
123  return std::make_pair(entry, false);
124  entry = make_shared<fib::Entry>(prefix);
125  nameTreeEntry->setFibEntry(entry);
126  ++m_nItems;
127  return std::make_pair(entry, true);
128 }
129 
130 void
131 Fib::erase(shared_ptr<name_tree::Entry> nameTreeEntry)
132 {
133  nameTreeEntry->setFibEntry(shared_ptr<fib::Entry>());
134  m_nameTree.eraseEntryIfEmpty(nameTreeEntry);
135  --m_nItems;
136 }
137 
138 void
139 Fib::erase(const Name& prefix)
140 {
141  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
142  if (static_cast<bool>(nameTreeEntry)) {
143  this->erase(nameTreeEntry);
144  }
145 }
146 
147 void
148 Fib::erase(const fib::Entry& entry)
149 {
150  shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(entry);
151  if (static_cast<bool>(nameTreeEntry)) {
152  this->erase(nameTreeEntry);
153  }
154 }
155 
156 void
158 {
159  std::list<fib::Entry*> toErase;
160 
161  auto&& enumerable = m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry);
162  for (const name_tree::Entry& nte : enumerable) {
163  shared_ptr<fib::Entry> entry = nte.getFibEntry();
164  entry->removeNextHop(face);
165  if (!entry->hasNextHops()) {
166  toErase.push_back(entry.get());
167  // entry needs to be erased, but we must wait until the enumeration ends,
168  // because otherwise NameTree iterator would be invalidated
169  }
170  }
171 
172  for (fib::Entry* entry : toErase) {
173  this->erase(*entry);
174  }
175 }
176 
178 Fib::begin() const
179 {
181 }
182 
183 } // namespace nfd
shared_ptr< fib::Entry > getFibEntry() const
static bool predicate_NameTreeEntry_hasFibEntry(const name_tree::Entry &entry)
Definition: fib.cpp:60
const_iterator begin() const
returns an iterator pointing to the first FIB entry
Definition: fib.cpp:178
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:118
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:245
shared_ptr< fib::Entry > findLongestPrefixMatch(const Name &prefix) const
performs a longest prefix match
Definition: fib.cpp:66
shared_ptr< name_tree::Entry > get(const fib::Entry &fibEntry) const
get NameTree entry from FIB entry
Definition: name-tree.hpp:367
shared_ptr< fib::Entry > findExactMatch(const Name &prefix) const
Definition: fib.cpp:109
represents a Measurements entry
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:374
void removeNextHopFromAllEntries(shared_ptr< Face > face)
removes the NextHop record for face in all entrites
Definition: fib.cpp:157
void erase(const Name &prefix)
Definition: fib.cpp:139
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
represents a PIT entry
Definition: pit-entry.hpp:69
Class Name Tree.
Definition: name-tree.hpp:79
shared_ptr< name_tree::Entry > findExactMatch(const Name &prefix) const
Exact match lookup for the given name prefix.
Definition: name-tree.cpp:342
Name abstraction to represent an absolute name.
Definition: name.hpp:46
~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:207
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:461
Fib(NameTree &nameTree)
Definition: fib.cpp:49
Name Tree Entry Class.