cs.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "cs.hpp"
27 #include "core/algorithm.hpp"
28 #include "core/asserts.hpp"
29 #include "core/logger.hpp"
30 #include <ndn-cxx/lp/tags.hpp>
31 
32 namespace nfd {
33 namespace cs {
34 
36 
37 NFD_LOG_INIT("ContentStore");
38 
39 unique_ptr<Policy>
41 {
42  const std::string DEFAULT_POLICY = "priority_fifo";
43  return Policy::create(DEFAULT_POLICY);
44 }
45 
46 Cs::Cs(size_t nMaxPackets)
47 {
48  this->setPolicyImpl(makeDefaultPolicy());
49  m_policy->setLimit(nMaxPackets);
50 }
51 
52 void
53 Cs::setLimit(size_t nMaxPackets)
54 {
55  m_policy->setLimit(nMaxPackets);
56 }
57 
58 size_t
59 Cs::getLimit() const
60 {
61  return m_policy->getLimit();
62 }
63 
64 void
65 Cs::setPolicy(unique_ptr<Policy> policy)
66 {
67  BOOST_ASSERT(policy != nullptr);
68  BOOST_ASSERT(m_policy != nullptr);
69  size_t limit = m_policy->getLimit();
70  this->setPolicyImpl(std::move(policy));
71  m_policy->setLimit(limit);
72 }
73 
74 void
75 Cs::insert(const Data& data, bool isUnsolicited)
76 {
77  NFD_LOG_DEBUG("insert " << data.getName());
78 
79  if (m_policy->getLimit() == 0) {
80  // shortcut for disabled CS
81  return;
82  }
83 
84  // recognize CachePolicy
85  shared_ptr<lp::CachePolicyTag> tag = data.getTag<lp::CachePolicyTag>();
86  if (tag != nullptr) {
87  lp::CachePolicyType policy = tag->get().getPolicy();
88  if (policy == lp::CachePolicyType::NO_CACHE) {
89  return;
90  }
91  }
92 
93  bool isNewEntry = false;
94  iterator it;
95  // use .insert because gcc46 does not support .emplace
96  std::tie(it, isNewEntry) = m_table.insert(EntryImpl(data.shared_from_this(), isUnsolicited));
97  EntryImpl& entry = const_cast<EntryImpl&>(*it);
98 
99  entry.updateStaleTime();
100 
101  if (!isNewEntry) { // existing entry
102  // XXX This doesn't forbid unsolicited Data from refreshing a solicited entry.
103  if (entry.isUnsolicited() && !isUnsolicited) {
104  entry.unsetUnsolicited();
105  }
106 
107  m_policy->afterRefresh(it);
108  }
109  else {
110  m_policy->afterInsert(it);
111  }
112 }
113 
114 void
115 Cs::find(const Interest& interest,
116  const HitCallback& hitCallback,
117  const MissCallback& missCallback) const
118 {
119  BOOST_ASSERT(static_cast<bool>(hitCallback));
120  BOOST_ASSERT(static_cast<bool>(missCallback));
121 
122  const Name& prefix = interest.getName();
123  bool isRightmost = interest.getChildSelector() == 1;
124  NFD_LOG_DEBUG("find " << prefix << (isRightmost ? " R" : " L"));
125 
126  iterator first = m_table.lower_bound(prefix);
127  iterator last = m_table.end();
128  if (prefix.size() > 0) {
129  last = m_table.lower_bound(prefix.getSuccessor());
130  }
131 
132  iterator match = last;
133  if (isRightmost) {
134  match = this->findRightmost(interest, first, last);
135  }
136  else {
137  match = this->findLeftmost(interest, first, last);
138  }
139 
140  if (match == last) {
141  NFD_LOG_DEBUG(" no-match");
142  missCallback(interest);
143  return;
144  }
145  NFD_LOG_DEBUG(" matching " << match->getName());
146  m_policy->beforeUse(match);
147  hitCallback(interest, match->getData());
148 }
149 
150 iterator
151 Cs::findLeftmost(const Interest& interest, iterator first, iterator last) const
152 {
153  return std::find_if(first, last, bind(&cs::EntryImpl::canSatisfy, _1, interest));
154 }
155 
156 iterator
157 Cs::findRightmost(const Interest& interest, iterator first, iterator last) const
158 {
159  // Each loop visits a sub-namespace under a prefix one component longer than Interest Name.
160  // If there is a match in that sub-namespace, the leftmost match is returned;
161  // otherwise, loop continues.
162 
163  size_t interestNameLength = interest.getName().size();
164  for (iterator right = last; right != first;) {
165  iterator prev = std::prev(right);
166 
167  // special case: [first,prev] have exact Names
168  if (prev->getName().size() == interestNameLength) {
169  NFD_LOG_TRACE(" find-among-exact " << prev->getName());
170  iterator matchExact = this->findRightmostAmongExact(interest, first, right);
171  return matchExact == right ? last : matchExact;
172  }
173 
174  Name prefix = prev->getName().getPrefix(interestNameLength + 1);
175  iterator left = m_table.lower_bound(prefix);
176 
177  // normal case: [left,right) are under one-component-longer prefix
178  NFD_LOG_TRACE(" find-under-prefix " << prefix);
179  iterator match = this->findLeftmost(interest, left, right);
180  if (match != right) {
181  return match;
182  }
183  right = left;
184  }
185  return last;
186 }
187 
188 iterator
189 Cs::findRightmostAmongExact(const Interest& interest, iterator first, iterator last) const
190 {
191  return find_last_if(first, last, bind(&EntryImpl::canSatisfy, _1, interest));
192 }
193 
194 void
195 Cs::setPolicyImpl(unique_ptr<Policy> policy)
196 {
197  NFD_LOG_DEBUG("set-policy " << policy->getName());
198  m_policy = std::move(policy);
199  m_beforeEvictConnection = m_policy->beforeEvict.connect([this] (iterator it) {
200  m_table.erase(it);
201  });
202 
203  m_policy->setCs(this);
204  BOOST_ASSERT(m_policy->getCs() == this);
205 }
206 
207 void
208 Cs::dump()
209 {
210  NFD_LOG_DEBUG("dump table");
211  for (const EntryImpl& entry : m_table) {
212  NFD_LOG_TRACE(entry.getFullName());
213  }
214 }
215 
216 } // namespace cs
217 } // namespace nfd
size_t getLimit() const
Definition: cs.cpp:59
void updateStaleTime()
refreshes stale time relative to current time
Definition: cs-entry.cpp:48
#define NFD_LOG_DEBUG(expression)
Definition: logger.hpp:161
std::function< void(const Interest &, const Data &data)> HitCallback
Definition: cs.hpp:73
It find_last_if(It first, It last, Pred p)
finds the last element satisfying a predicate
Definition: algorithm.hpp:49
implements the ContentStore
static unique_ptr< Policy > create(const std::string &policyName)
Definition: cs-policy.cpp:45
Table::const_iterator iterator
Definition: cs-internal.hpp:41
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
void insert(const Data &data, bool isUnsolicited=false)
inserts a Data packet
Definition: cs.cpp:75
boost::transform_iterator< EntryFromEntryImpl, iterator, const Entry & > const_iterator
ContentStore iterator (public API)
Definition: cs.hpp:144
void setLimit(size_t nMaxPackets)
changes capacity (in number of packets)
Definition: cs.cpp:53
unique_ptr< Policy > makeDefaultPolicy()
Definition: cs.cpp:40
void setPolicy(unique_ptr< Policy > policy)
changes cs replacement policy
Definition: cs.cpp:65
std::function< void(const Interest &)> MissCallback
Definition: cs.hpp:74
NFD_ASSERT_FORWARD_ITERATOR(Cs::const_iterator)
an Entry in ContentStore implementation
void unsetUnsolicited()
#define NFD_LOG_INIT(name)
Definition: logger.hpp:122
bool isUnsolicited() const
Definition: cs-entry.hpp:73
#define NFD_LOG_TRACE(expression)
Definition: logger.hpp:160
bool canSatisfy(const Interest &interest) const
determines whether Interest can be satisified by the stored Data
Definition: cs-entry.cpp:55
void find(const Interest &interest, const HitCallback &hitCallback, const MissCallback &missCallback) const
finds the best matching Data packet
Definition: cs.cpp:115
Cs(size_t nMaxPackets=10)
Definition: cs.cpp:46