NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: NDN, CCN, CCNx, content centric networks
API Documentation
cs.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "cs.hpp"
28 #include "core/logger.hpp"
29 #include "core/algorithm.hpp"
30 
31 NFD_LOG_INIT("ContentStore");
32 
33 namespace nfd {
34 namespace cs {
35 
36 // http://en.cppreference.com/w/cpp/concept/ForwardIterator
37 BOOST_CONCEPT_ASSERT((boost::ForwardIterator<Cs::const_iterator>));
38 // boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
39 // which doesn't require DefaultConstructible
40 #ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
41 static_assert(std::is_default_constructible<Cs::const_iterator>::value,
42  "Cs::const_iterator must be default-constructible");
43 #else
44 BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Cs::const_iterator>));
45 #endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
46 
47 unique_ptr<Policy>
49 {
50  return unique_ptr<Policy>(new PriorityFifoPolicy());
51 }
52 
53 Cs::Cs(size_t nMaxPackets, unique_ptr<Policy> policy)
54 {
55  this->setPolicyImpl(policy);
56  m_policy->setLimit(nMaxPackets);
57 }
58 
59 void
60 Cs::setLimit(size_t nMaxPackets)
61 {
62  m_policy->setLimit(nMaxPackets);
63 }
64 
65 size_t
66 Cs::getLimit() const
67 {
68  return m_policy->getLimit();
69 }
70 
71 void
72 Cs::setPolicy(unique_ptr<Policy> policy)
73 {
74  BOOST_ASSERT(policy != nullptr);
75  BOOST_ASSERT(m_policy != nullptr);
76  size_t limit = m_policy->getLimit();
77  this->setPolicyImpl(policy);
78  m_policy->setLimit(limit);
79 }
80 
81 bool
82 Cs::insert(const Data& data, bool isUnsolicited)
83 {
84  NFD_LOG_DEBUG("insert " << data.getName());
85 
86  // recognize CachingPolicy
88  const LocalControlHeader& lch = data.getLocalControlHeader();
89  if (lch.hasCachingPolicy()) {
90  LocalControlHeader::CachingPolicy policy = lch.getCachingPolicy();
91  if (policy == LocalControlHeader::CachingPolicy::NO_CACHE) {
92  return false;
93  }
94  }
95 
96  bool isNewEntry = false;
97  iterator it;
98  // use .insert because gcc46 does not support .emplace
99  std::tie(it, isNewEntry) = m_table.insert(EntryImpl(data.shared_from_this(), isUnsolicited));
100  EntryImpl& entry = const_cast<EntryImpl&>(*it);
101 
102  entry.updateStaleTime();
103 
104  if (!isNewEntry) { // existing entry
105  // XXX This doesn't forbid unsolicited Data from refreshing a solicited entry.
106  if (entry.isUnsolicited() && !isUnsolicited) {
107  entry.unsetUnsolicited();
108  }
109 
110  m_policy->afterRefresh(it);
111  }
112  else {
113  m_policy->afterInsert(it);
114  }
115 
116  return true;
117 }
118 
119 void
120 Cs::find(const Interest& interest,
121  const HitCallback& hitCallback,
122  const MissCallback& missCallback) const
123 {
124  BOOST_ASSERT(static_cast<bool>(hitCallback));
125  BOOST_ASSERT(static_cast<bool>(missCallback));
126 
127  const Name& prefix = interest.getName();
128  bool isRightmost = interest.getChildSelector() == 1;
129  NFD_LOG_DEBUG("find " << prefix << (isRightmost ? " R" : " L"));
130 
131  iterator first = m_table.lower_bound(prefix);
132  iterator last = m_table.end();
133  if (prefix.size() > 0) {
134  last = m_table.lower_bound(prefix.getSuccessor());
135  }
136 
137  iterator match = last;
138  if (isRightmost) {
139  match = this->findRightmost(interest, first, last);
140  }
141  else {
142  match = this->findLeftmost(interest, first, last);
143  }
144 
145  if (match == last) {
146  NFD_LOG_DEBUG(" no-match");
147  missCallback(interest);
148  return;
149  }
150  NFD_LOG_DEBUG(" matching " << match->getName());
151  m_policy->beforeUse(match);
152  hitCallback(interest, match->getData());
153 }
154 
155 iterator
156 Cs::findLeftmost(const Interest& interest, iterator first, iterator last) const
157 {
158  return std::find_if(first, last, bind(&cs::EntryImpl::canSatisfy, _1, interest));
159 }
160 
161 iterator
162 Cs::findRightmost(const Interest& interest, iterator first, iterator last) const
163 {
164  // Each loop visits a sub-namespace under a prefix one component longer than Interest Name.
165  // If there is a match in that sub-namespace, the leftmost match is returned;
166  // otherwise, loop continues.
167 
168  size_t interestNameLength = interest.getName().size();
169  for (iterator right = last; right != first;) {
170  iterator prev = std::prev(right);
171 
172  // special case: [first,prev] have exact Names
173  if (prev->getName().size() == interestNameLength) {
174  NFD_LOG_TRACE(" find-among-exact " << prev->getName());
175  iterator matchExact = this->findRightmostAmongExact(interest, first, right);
176  return matchExact == right ? last : matchExact;
177  }
178 
179  Name prefix = prev->getName().getPrefix(interestNameLength + 1);
180  iterator left = m_table.lower_bound(prefix);
181 
182  // normal case: [left,right) are under one-component-longer prefix
183  NFD_LOG_TRACE(" find-under-prefix " << prefix);
184  iterator match = this->findLeftmost(interest, left, right);
185  if (match != right) {
186  return match;
187  }
188  right = left;
189  }
190  return last;
191 }
192 
193 iterator
194 Cs::findRightmostAmongExact(const Interest& interest, iterator first, iterator last) const
195 {
196  return find_last_if(first, last, bind(&EntryImpl::canSatisfy, _1, interest));
197 }
198 
199 void
200 Cs::setPolicyImpl(unique_ptr<Policy>& policy)
201 {
202  m_policy = std::move(policy);
203  m_beforeEvictConnection = m_policy->beforeEvict.connect([this] (iterator it) {
204  m_table.erase(it);
205  });
206 
207  m_policy->setCs(this);
208  BOOST_ASSERT(m_policy->getCs() == this);
209 }
210 
211 void
212 Cs::dump()
213 {
214  NFD_LOG_DEBUG("dump table");
215  for (const EntryImpl& entry : m_table) {
216  NFD_LOG_TRACE(entry.getFullName());
217  }
218 }
219 
220 } // namespace cs
221 } // namespace nfd
const Name & getName() const
Definition: interest.hpp:216
size_t getLimit() const
Definition: cs.cpp:66
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:36
bool canSatisfy(const Interest &interest) const
determines whether Interest can be satisified by the stored Data
Definition: cs-entry.cpp:60
Name getSuccessor() const
Get the successor of a name.
Definition: name.cpp:293
Cs(size_t nMaxPackets=10, unique_ptr< Policy > policy=makeDefaultPolicy())
Definition: cs.cpp:53
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
bool insert(const Data &data, bool isUnsolicited=false)
inserts a Data packet
Definition: cs.cpp:82
It find_last_if(It first, It last, Pred p)
Definition: algorithm.hpp:49
represents an Interest packet
Definition: interest.hpp:45
int getChildSelector() const
Definition: interest.hpp:398
an Entry in ContentStore implementation
const Name & getName() const
Get name of the Data packet.
Definition: data.hpp:343
Table::const_iterator iterator
Definition: cs-internal.hpp:41
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:38
unique_ptr< Policy > makeDefaultPolicy()
Definition: cs.cpp:48
void find(const Interest &interest, const HitCallback &hitCallback, const MissCallback &missCallback) const
finds the best matching Data packet
Definition: cs.cpp:120
void setPolicy(unique_ptr< Policy > policy)
changes cs replacement policy
Definition: cs.cpp:72
bool isUnsolicited() const
Definition: cs-entry.hpp:73
void setLimit(size_t nMaxPackets)
changes capacity (in number of packets)
Definition: cs.cpp:60
size_t size() const
Get the number of components.
Definition: name.hpp:408
Name abstraction to represent an absolute name.
Definition: name.hpp:46
std::function< void(const Interest &, const Data &data)> HitCallback
Definition: cs.hpp:77
std::function< void(const Interest &)> MissCallback
Definition: cs.hpp:78
void updateStaleTime()
refreshes stale time relative to current time
Definition: cs-entry.cpp:48
#define NFD_LOG_INIT(name)
Definition: logger.hpp:33
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:35
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix (PartialName) of the name, containing first nComponents components.
Definition: name.hpp:249
represents a Data packet
Definition: data.hpp:39
nfd::LocalControlHeader & getLocalControlHeader()
Definition: data.hpp:379