NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: NDN, CCN, CCNx, content centric networks
API Documentation
strategy-choice.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "strategy-choice.hpp"
27 #include "core/logger.hpp"
28 #include "fw/strategy.hpp"
29 #include "pit-entry.hpp"
30 #include "measurements-entry.hpp"
31 
32 namespace nfd {
33 
34 using strategy_choice::Entry;
35 using fw::Strategy;
36 
37 NFD_LOG_INIT("StrategyChoice");
38 
39 StrategyChoice::StrategyChoice(NameTree& nameTree, shared_ptr<Strategy> defaultStrategy)
40  : m_nameTree(nameTree)
41  , m_nItems(0)
42 {
43  this->setDefaultStrategy(defaultStrategy);
44 }
45 
46 bool
47 StrategyChoice::hasStrategy(const Name& strategyName, bool isExact) const
48 {
49  if (isExact) {
50  return m_strategyInstances.count(strategyName) > 0;
51  }
52  else {
53  return static_cast<bool>(this->getStrategy(strategyName));
54  }
55 }
56 
57 bool
58 StrategyChoice::install(shared_ptr<Strategy> strategy)
59 {
60  BOOST_ASSERT(static_cast<bool>(strategy));
61  const Name& strategyName = strategy->getName();
62 
63  if (this->hasStrategy(strategyName, true)) {
64  NFD_LOG_ERROR("install(" << strategyName << ") duplicate strategyName");
65  return false;
66  }
67 
68  m_strategyInstances[strategyName] = strategy;
69  return true;
70 }
71 
73 StrategyChoice::getStrategy(const Name& strategyName) const
74 {
75  fw::Strategy* candidate = nullptr;
76  for (auto it = m_strategyInstances.lower_bound(strategyName);
77  it != m_strategyInstances.end() && strategyName.isPrefixOf(it->first); ++it) {
78  switch (it->first.size() - strategyName.size()) {
79  case 0: // exact match
80  return it->second.get();
81  case 1: // unversioned strategyName matches versioned strategy
82  candidate = it->second.get();
83  break;
84  }
85  }
86  return candidate;
87 }
88 
89 bool
90 StrategyChoice::insert(const Name& prefix, const Name& strategyName)
91 {
92  Strategy* strategy = this->getStrategy(strategyName);
93  if (strategy == nullptr) {
94  NFD_LOG_ERROR("insert(" << prefix << "," << strategyName << ") strategy not installed");
95  return false;
96  }
97 
98  shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(prefix);
99  shared_ptr<Entry> entry = nte->getStrategyChoiceEntry();
100  Strategy* oldStrategy = nullptr;
101  if (static_cast<bool>(entry)) {
102  if (entry->getStrategy().getName() == strategy->getName()) {
103  NFD_LOG_TRACE("insert(" << prefix << ") not changing " << strategy->getName());
104  return true;
105  }
106  oldStrategy = &entry->getStrategy();
107  NFD_LOG_TRACE("insert(" << prefix << ") changing from " << oldStrategy->getName() <<
108  " to " << strategy->getName());
109  }
110 
111  if (!static_cast<bool>(entry)) {
112  oldStrategy = &this->findEffectiveStrategy(prefix);
113  entry = make_shared<Entry>(prefix);
114  nte->setStrategyChoiceEntry(entry);
115  ++m_nItems;
116  NFD_LOG_TRACE("insert(" << prefix << ") new entry " << strategy->getName());
117  }
118 
119  this->changeStrategy(*entry, *oldStrategy, *strategy);
120  entry->setStrategy(*strategy);
121  return true;
122 }
123 
124 void
126 {
127  BOOST_ASSERT(prefix.size() > 0);
128 
129  shared_ptr<name_tree::Entry> nte = m_nameTree.findExactMatch(prefix);
130  if (!static_cast<bool>(nte)) {
131  return;
132  }
133 
134  shared_ptr<Entry> entry = nte->getStrategyChoiceEntry();
135  if (!static_cast<bool>(entry)) {
136  return;
137  }
138 
139  Strategy& oldStrategy = entry->getStrategy();
140 
141  Strategy& parentStrategy = this->findEffectiveStrategy(prefix.getPrefix(-1));
142  this->changeStrategy(*entry, oldStrategy, parentStrategy);
143 
144  nte->setStrategyChoiceEntry(shared_ptr<Entry>());
145  m_nameTree.eraseEntryIfEmpty(nte);
146  --m_nItems;
147 }
148 
149 std::pair<bool, Name>
150 StrategyChoice::get(const Name& prefix) const
151 {
152  shared_ptr<name_tree::Entry> nte = m_nameTree.findExactMatch(prefix);
153  if (!static_cast<bool>(nte)) {
154  return { false, Name() };
155  }
156 
157  shared_ptr<Entry> entry = nte->getStrategyChoiceEntry();
158  if (!static_cast<bool>(entry)) {
159  return { false, Name() };
160  }
161 
162  return { true, entry->getStrategy().getName() };
163 }
164 
165 Strategy&
167 {
168  shared_ptr<name_tree::Entry> nte = m_nameTree.findLongestPrefixMatch(prefix,
169  [] (const name_tree::Entry& entry) {
170  return static_cast<bool>(entry.getStrategyChoiceEntry());
171  });
172 
173  BOOST_ASSERT(static_cast<bool>(nte));
174  return nte->getStrategyChoiceEntry()->getStrategy();
175 }
176 
177 Strategy&
178 StrategyChoice::findEffectiveStrategy(shared_ptr<name_tree::Entry> nte) const
179 {
180  shared_ptr<strategy_choice::Entry> entry = nte->getStrategyChoiceEntry();
181  if (static_cast<bool>(entry))
182  return entry->getStrategy();
183 
184  nte = m_nameTree.findLongestPrefixMatch(nte,
185  [] (const name_tree::Entry& entry) {
186  return static_cast<bool>(entry.getStrategyChoiceEntry());
187  });
188 
189  BOOST_ASSERT(static_cast<bool>(nte));
190  return nte->getStrategyChoiceEntry()->getStrategy();
191 }
192 
193 Strategy&
195 {
196  shared_ptr<name_tree::Entry> nte = m_nameTree.get(pitEntry);
197 
198  BOOST_ASSERT(static_cast<bool>(nte));
199  return this->findEffectiveStrategy(nte);
200 }
201 
202 Strategy&
204 {
205  shared_ptr<name_tree::Entry> nte = m_nameTree.get(measurementsEntry);
206 
207  BOOST_ASSERT(static_cast<bool>(nte));
208  return this->findEffectiveStrategy(nte);
209 }
210 
211 void
212 StrategyChoice::setDefaultStrategy(shared_ptr<Strategy> strategy)
213 {
214  this->install(strategy);
215 
216  // don't use .insert here, because it will invoke findEffectiveStrategy
217  // which expects an existing root entry
218  shared_ptr<name_tree::Entry> nte = m_nameTree.lookup(Name());
219  shared_ptr<Entry> entry = make_shared<Entry>(Name());
220  nte->setStrategyChoiceEntry(entry);
221  ++m_nItems;
222  NFD_LOG_INFO("setDefaultStrategy " << strategy->getName());
223 
224  entry->setStrategy(*strategy);
225 }
226 
227 static inline void
229 {
230  NFD_LOG_TRACE("clearStrategyInfo " << nte.getPrefix());
231 
232  for (const shared_ptr<pit::Entry>& pitEntry : nte.getPitEntries()) {
233  pitEntry->clearStrategyInfo();
234  for (const pit::InRecord& inRecord : pitEntry->getInRecords()) {
235  const_cast<pit::InRecord&>(inRecord).clearStrategyInfo();
236  }
237  for (const pit::OutRecord& outRecord : pitEntry->getOutRecords()) {
238  const_cast<pit::OutRecord&>(outRecord).clearStrategyInfo();
239  }
240  }
241  if (static_cast<bool>(nte.getMeasurementsEntry())) {
242  nte.getMeasurementsEntry()->clearStrategyInfo();
243  }
244 }
245 
246 void
247 StrategyChoice::changeStrategy(strategy_choice::Entry& entry,
248  fw::Strategy& oldStrategy,
249  fw::Strategy& newStrategy)
250 {
251  if (&oldStrategy == &newStrategy) {
252  return;
253  }
254 
255  NFD_LOG_INFO("changeStrategy(" << entry.getPrefix() << ")"
256  << " from " << oldStrategy.getName()
257  << " to " << newStrategy.getName());
258 
259  // reset StrategyInfo on a portion of NameTree,
260  // where entry's effective strategy is covered by the changing StrategyChoice entry
261  const name_tree::Entry* rootNte = m_nameTree.get(entry).get();
262  auto&& ntChanged = m_nameTree.partialEnumerate(entry.getPrefix(),
263  [&rootNte] (const name_tree::Entry& nte) -> std::pair<bool, bool> {
264  if (&nte == rootNte) {
265  return {true, true};
266  }
267  if (static_cast<bool>(nte.getStrategyChoiceEntry())) {
268  return {false, false};
269  }
270  return {true, true};
271  });
272  for (const name_tree::Entry& nte : ntChanged) {
273  clearStrategyInfo(nte);
274  }
275 }
276 
279 {
280  auto&& enumerable = m_nameTree.fullEnumerate(
281  [] (const name_tree::Entry& entry) {
282  return static_cast<bool>(entry.getStrategyChoiceEntry());
283  });
284  return const_iterator(enumerable.begin());
285 }
286 
287 } // namespace nfd
fw::Strategy & findEffectiveStrategy(const Name &prefix) const
get effective strategy for prefix
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix (PartialName) of the name, containing first nComponents components.
Definition: name.hpp:249
bool hasStrategy(const Name &strategyName, bool isExact=false) const
determines if a strategy is installed
const Name & getName() const
a Name that represent the Strategy program
Definition: strategy.hpp:202
bool eraseEntryIfEmpty(shared_ptr< name_tree::Entry > entry)
Delete a Name Tree Entry if this entry is empty.
Definition: name-tree.cpp:245
StrategyChoice(NameTree &nameTree, shared_ptr< fw::Strategy > defaultStrategy)
bool insert(const Name &prefix, const Name &strategyName)
set strategy of prefix to be strategyName
contains information about an Interest from an incoming face
shared_ptr< name_tree::Entry > get(const fib::Entry &fibEntry) const
get NameTree entry from FIB entry
Definition: name-tree.hpp:367
std::pair< bool, Name > get(const Name &prefix) const
get strategy Name of prefix
#define NFD_LOG_ERROR(expression)
Definition: logger.hpp:57
const Name & getPrefix() const
shared_ptr< measurements::Entry > getMeasurementsEntry() const
const std::vector< shared_ptr< pit::Entry > > & getPitEntries() const
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
#define NFD_LOG_INFO(expression)
Definition: logger.hpp:56
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
represents a PIT entry
Definition: pit-entry.hpp:69
void erase(const Name &prefix)
make prefix to inherit strategy from its parent
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
bool isPrefixOf(const Name &name) const
Check if the N components of this name are the same as the first N components of the given name...
Definition: name.cpp:320
represents a Strategy Choice entry
bool install(shared_ptr< fw::Strategy > strategy)
install a strategy
const_iterator begin() const
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
size_t size() const
Get the number of components.
Definition: name.hpp:408
represents a forwarding strategy
Definition: strategy.hpp:38
#define NFD_LOG_INIT(name)
Definition: logger.hpp:34
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:54
contains information about an Interest toward an outgoing face
boost::iterator_range< const_iterator > partialEnumerate(const Name &prefix, const name_tree::EntrySubTreeSelector &entrySubTreeSelector=name_tree::AnyEntrySubTree()) const
Enumerate all entries under a prefix, optionally filtered by an EntrySubTreeSelector.
Definition: name-tree.cpp:480
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
static void clearStrategyInfo(const name_tree::Entry &nte)
shared_ptr< strategy_choice::Entry > getStrategyChoiceEntry() const
Name Tree Entry Class.