NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: NDN, CCN, CCNx, content centric networks
API Documentation
in-memory-storage.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
22 #include "in-memory-storage.hpp"
24 
25 #include "crypto.hpp"
26 
27 #include "../security/signature-sha256-with-rsa.hpp"
28 
29 namespace ndn {
30 namespace util {
31 
34  : m_ptr(ptr)
35  , m_cache(cache)
36  , m_it(it)
37 {
38 }
39 
42 {
43  m_it++;
44  if (m_it != m_cache->get<byFullName>().end()) {
45  m_ptr = &((*m_it)->getData());
46  }
47  else {
48  m_ptr = 0;
49  }
50 
51  return *this;
52 }
53 
56 {
58  this->operator++();
59  return i;
60 }
61 
62 const Data&
64 {
65  return *m_ptr;
66 }
67 
68 const Data*
70 {
71  return m_ptr;
72 }
73 
74 bool
76 {
77  return m_it == rhs.m_it;
78 }
79 
80 bool
82 {
83  return m_it != rhs.m_it;
84 }
85 
87  : m_limit(limit)
88  , m_nPackets(0)
89 {
90  // TODO consider a more suitable initial value
91  m_capacity = 10;
92 
93  if (limit != std::numeric_limits<size_t>::max() && m_capacity > m_limit) {
94  m_capacity = m_limit;
95  }
96 
97  for (size_t i = 0; i < m_capacity; i++) {
98  m_freeEntries.push(new InMemoryStorageEntry());
99  }
100 }
101 
103 {
104  // evict all items from cache
105  Cache::iterator it = m_cache.begin();
106  while (it != m_cache.end()) {
107  it = freeEntry(it);
108  }
109 
110  BOOST_ASSERT(m_freeEntries.size() == m_capacity);
111 
112  while (!m_freeEntries.empty()) {
113  delete m_freeEntries.top();
114  m_freeEntries.pop();
115  }
116 }
117 
118 void
119 InMemoryStorage::setCapacity(size_t capacity)
120 {
121  size_t oldCapacity = m_capacity;
122  m_capacity = capacity;
123 
124  if (size() > m_capacity) {
125  ssize_t nAllowedFailures = size() - m_capacity;
126  while (size() > m_capacity) {
127  if (!evictItem() && --nAllowedFailures < 0) {
128  BOOST_THROW_EXCEPTION(Error());
129  }
130  }
131  }
132 
133  if (m_capacity >= oldCapacity) {
134  for (size_t i = oldCapacity; i < m_capacity; i++) {
135  m_freeEntries.push(new InMemoryStorageEntry());
136  }
137  }
138  else {
139  for (size_t i = oldCapacity; i > m_capacity; i--) {
140  delete m_freeEntries.top();
141  m_freeEntries.pop();
142  }
143  }
144 
145  BOOST_ASSERT(size() + m_freeEntries.size() == m_capacity);
146 }
147 
148 void
150 {
151  //check if identical Data/Name already exists
152  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(data.getFullName());
153  if (it != m_cache.get<byFullName>().end())
154  return;
155 
156  //if full, double the capacity
157  bool doesReachLimit = (getLimit() == getCapacity());
158  if (isFull() && !doesReachLimit) {
159  // note: This is incorrect if 2*capacity overflows, but memory should run out before that
160  size_t newCapacity = std::min(2 * getCapacity(), getLimit());
161  setCapacity(newCapacity);
162  }
163 
164  //if full and reach limitation of the capacity, employ replacement policy
165  if (isFull() && doesReachLimit) {
166  evictItem();
167  }
168 
169  //insert to cache
170  BOOST_ASSERT(m_freeEntries.size() > 0);
171  // take entry for the memory pool
172  InMemoryStorageEntry* entry = m_freeEntries.top();
173  m_freeEntries.pop();
174  m_nPackets++;
175  entry->setData(data);
176  m_cache.insert(entry);
177 
178  //let derived class do something with the entry
179  afterInsert(entry);
180 }
181 
182 shared_ptr<const Data>
184 {
185  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(name);
186 
187  //if not found, return null
188  if (it == m_cache.get<byFullName>().end()) {
189  return shared_ptr<const Data>();
190  }
191 
192  //if the given name is not the prefix of the lower_bound, return null
193  if (!name.isPrefixOf((*it)->getFullName())) {
194  return shared_ptr<const Data>();
195  }
196 
197  afterAccess(*it);
198  return ((*it)->getData()).shared_from_this();
199 }
200 
201 shared_ptr<const Data>
203 {
204  //if the interest contains implicit digest, it is possible to directly locate a packet.
205  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>()
206  .find(interest.getName());
207 
208  //if a packet is located by its full name, it must be the packet to return.
209  if (it != m_cache.get<byFullName>().end()) {
210  return ((*it)->getData()).shared_from_this();
211  }
212 
213  //if the packet is not discovered by last step, either the packet is not in the storage or
214  //the interest doesn't contains implicit digest.
215  it = m_cache.get<byFullName>().lower_bound(interest.getName());
216 
217  if (it == m_cache.get<byFullName>().end()) {
218  return shared_ptr<const Data>();
219  }
220 
221 
222  //to locate the element that has a just smaller name than the interest's
223  if (it != m_cache.get<byFullName>().begin())
224  it--;
225 
226  InMemoryStorageEntry* ret = selectChild(interest, it);
227  if (ret != 0) {
228  //let derived class do something with the entry
229  afterAccess(ret);
230  return ret->getData().shared_from_this();
231  }
232  else {
233  return shared_ptr<const Data>();
234  }
235 }
236 
239  Cache::index<byFullName>::type::iterator startingPoint) const
240 {
241  BOOST_ASSERT(startingPoint != m_cache.get<byFullName>().end());
242 
243  if (startingPoint != m_cache.get<byFullName>().begin())
244  {
245  BOOST_ASSERT((*startingPoint)->getFullName() < interest.getName());
246  }
247 
248  bool hasLeftmostSelector = (interest.getChildSelector() <= 0);
249  bool hasRightmostSelector = !hasLeftmostSelector;
250 
251  if (hasLeftmostSelector)
252  {
253  if (interest.matchesData((*startingPoint)->getData()))
254  {
255  return *startingPoint;
256  }
257  }
258 
259  //iterate to the right
260  Cache::index<byFullName>::type::iterator rightmost = startingPoint;
261  if (startingPoint != m_cache.get<byFullName>().end())
262  {
263  Cache::index<byFullName>::type::iterator rightmostCandidate = startingPoint;
264  Name currentChildPrefix("");
265 
266  while (true)
267  {
268  ++rightmostCandidate;
269 
270  bool isInBoundaries = (rightmostCandidate != m_cache.get<byFullName>().end());
271  bool isInPrefix = false;
272  if (isInBoundaries)
273  {
274  isInPrefix = interest.getName().isPrefixOf((*rightmostCandidate)->getFullName());
275  }
276 
277  if (isInPrefix)
278  {
279  if (interest.matchesData((*rightmostCandidate)->getData()))
280  {
281  if (hasLeftmostSelector)
282  {
283  return *rightmostCandidate;
284  }
285 
286  if (hasRightmostSelector)
287  {
288  // get prefix which is one component longer than Interest name
289  const Name& childPrefix = (*rightmostCandidate)->getFullName()
290  .getPrefix(interest.getName().size() + 1);
291 
292  if (currentChildPrefix.empty() || (childPrefix != currentChildPrefix))
293  {
294  currentChildPrefix = childPrefix;
295  rightmost = rightmostCandidate;
296  }
297  }
298  }
299  }
300  else
301  break;
302  }
303  }
304 
305  if (rightmost != startingPoint)
306  {
307  return *rightmost;
308  }
309 
310  if (hasRightmostSelector) // if rightmost was not found, try starting point
311  {
312  if (interest.matchesData((*startingPoint)->getData()))
313  {
314  return *startingPoint;
315  }
316  }
317 
318  return 0;
319 }
320 
322 InMemoryStorage::freeEntry(Cache::iterator it)
323 {
324  //push the *empty* entry into mem pool
325  (*it)->release();
326  m_freeEntries.push(*it);
327  m_nPackets--;
328  return m_cache.erase(it);
329 }
330 
331 void
332 InMemoryStorage::erase(const Name& prefix, const bool isPrefix)
333 {
334  if (isPrefix) {
335  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().lower_bound(prefix);
336 
337  while (it != m_cache.get<byFullName>().end() && prefix.isPrefixOf((*it)->getName())) {
338  //let derived class do something with the entry
339  beforeErase(*it);
340  it = freeEntry(it);
341  }
342  }
343  else {
344  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(prefix);
345 
346  if (it == m_cache.get<byFullName>().end())
347  return;
348 
349  //let derived class do something with the entry
350  beforeErase(*it);
351  freeEntry(it);
352  }
353 
354  if (m_freeEntries.size() > (2 * size()))
355  setCapacity(getCapacity() / 2);
356 }
357 
358 void
360 {
361  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().find(name);
362 
363  if (it == m_cache.get<byFullName>().end())
364  return;
365 
366  freeEntry(it);
367 }
368 
371 {
372  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().begin();
373 
374  return const_iterator(&((*it)->getData()), &m_cache, it);
375 }
376 
379 {
380  Cache::index<byFullName>::type::iterator it = m_cache.get<byFullName>().end();
381 
382  const Data* ptr = NULL;
383 
384  return const_iterator(ptr, &m_cache, it);
385 }
386 
387 void
389 {
390 }
391 
392 void
394 {
395 }
396 
397 void
398 InMemoryStorage::afterAccess(InMemoryStorageEntry* entry)
399 {
400 }
401 
402 void
403 InMemoryStorage::printCache(std::ostream& os) const
404 {
405  //start from the upper layer towards bottom
406  const Cache::index<byFullName>::type& cacheIndex = m_cache.get<byFullName>();
407  for (Cache::index<byFullName>::type::iterator it = cacheIndex.begin();
408  it != cacheIndex.end(); it++)
409  os << (*it)->getFullName() << std::endl;
410 }
411 
412 } // namespace util
413 } // namespace ndn
const Name & getName() const
Definition: interest.hpp:216
Copyright (c) 2011-2015 Regents of the University of California.
void insert(const Data &data)
Inserts a Data packet.
bool isFull() const
returns true if the in-memory storage uses up the current capacity, false otherwise ...
InMemoryStorage(size_t limit=std::numeric_limits< size_t >::max())
shared_ptr< const Data > find(const Interest &interest)
Finds the best match Data for an Interest.
Represents a self-defined const_iterator for the in-memory storage.
const Data & getData() const
Returns the Data packet stored in the in-memory storage entry.
represents an Interest packet
Definition: interest.hpp:45
bool operator!=(const const_iterator &rhs)
InMemoryStorage::const_iterator end() const
Returns end iterator of the in-memory storage ordering by name with digest.
InMemoryStorage::const_iterator begin() const
Returns begin iterator of the in-memory storage ordering by name with digest.
virtual bool evictItem()=0
Removes one Data packet from in-memory storage based on derived class implemented replacement policy...
int getChildSelector() const
Definition: interest.hpp:398
virtual void beforeErase(InMemoryStorageEntry *entry)
Update the entry or other data structures before a entry is successfully erased according to derived ...
void eraseImpl(const Name &name)
deletes in-memory storage entries by the Name with implicit digest.
Table::const_iterator iterator
Definition: cs-internal.hpp:41
boost::multi_index_container< InMemoryStorageEntry *, boost::multi_index::indexed_by< boost::multi_index::ordered_unique< boost::multi_index::tag< byFullName >, boost::multi_index::const_mem_fun< InMemoryStorageEntry, const Name &,&InMemoryStorageEntry::getFullName >, std::less< Name > > > > Cache
size_t getCapacity() const
returns current capacity of in-memory storage (in packets)
size_t size() const
Get the number of components.
Definition: name.hpp:408
Represents an in-memory storage entry.
Name abstraction to represent an absolute name.
Definition: name.hpp:46
const_iterator(const Data *ptr, const Cache *cache, Cache::index< byFullName >::type::iterator it)
bool matchesData(const Data &data) const
Check if Interest can be satisfied by data.
Definition: interest.cpp:132
bool operator==(const const_iterator &rhs)
virtual void afterInsert(InMemoryStorageEntry *entry)
Update the entry or other data structures after a entry is successfully inserted according to derived...
bool empty() const
Check if name is emtpy.
Definition: name.hpp:398
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
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix (PartialName) of the name, containing first nComponents components.
Definition: name.hpp:249
InMemoryStorageEntry * selectChild(const Interest &interest, Cache::index< byFullName >::type::iterator startingPoint) const
Implements child selector (leftmost, rightmost, undeclared).
const Name & getFullName() const
Get full name of Data packet, including the implicit digest.
Definition: data.cpp:179
Represents an error might be thrown during reduce the current capacity of the in-memory storage throu...
represents a Data packet
Definition: data.hpp:39
void erase(const Name &prefix, const bool isPrefix=true)
Deletes in-memory storage entry by prefix by default.
void printCache(std::ostream &os) const
Prints contents of the in-memory storage.