blob: 740b70673ae654b7345696a5e45bdad9f9cf73c9 [file] [log] [blame]
Jiewen Tan99135962014-09-20 02:18:53 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Junxiao Shi13d85e02017-07-07 07:34:02 +00002/*
Davide Pesaventodb4da5e2018-06-15 11:37:52 -04003 * Copyright (c) 2013-2018 Regents of the University of California.
Jiewen Tan99135962014-09-20 02:18:53 -07004 *
5 * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
6 *
7 * ndn-cxx library is free software: you can redistribute it and/or modify it under the
8 * terms of the GNU Lesser General Public License as published by the Free Software
9 * Foundation, either version 3 of the License, or (at your option) any later version.
10 *
11 * ndn-cxx library is distributed in the hope that it will be useful, but WITHOUT ANY
12 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
13 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
14 *
15 * You should have received copies of the GNU General Public License and GNU Lesser
16 * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
17 * <http://www.gnu.org/licenses/>.
18 *
19 * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
20 */
21
Junxiao Shic542f632017-07-18 14:20:32 +000022#ifndef NDN_IMS_IN_MEMORY_STORAGE_HPP
23#define NDN_IMS_IN_MEMORY_STORAGE_HPP
Jiewen Tan99135962014-09-20 02:18:53 -070024
Jiewen Tan99135962014-09-20 02:18:53 -070025#include "in-memory-storage-entry.hpp"
26
Junxiao Shic542f632017-07-18 14:20:32 +000027#include <iterator>
28#include <stack>
29
Jiewen Tan99135962014-09-20 02:18:53 -070030#include <boost/multi_index_container.hpp>
Jiewen Tan99135962014-09-20 02:18:53 -070031#include <boost/multi_index/identity.hpp>
32#include <boost/multi_index/mem_fun.hpp>
Junxiao Shic542f632017-07-18 14:20:32 +000033#include <boost/multi_index/member.hpp>
34#include <boost/multi_index/ordered_index.hpp>
35#include <boost/multi_index/sequenced_index.hpp>
Jiewen Tan99135962014-09-20 02:18:53 -070036
37namespace ndn {
Jiewen Tan99135962014-09-20 02:18:53 -070038
39/** @brief Represents in-memory storage
40 */
41class InMemoryStorage : noncopyable
42{
43public:
Junxiao Shic542f632017-07-18 14:20:32 +000044 // multi_index_container to implement storage
Jiewen Tan99135962014-09-20 02:18:53 -070045 class byFullName;
46
47 typedef boost::multi_index_container<
48 InMemoryStorageEntry*,
49 boost::multi_index::indexed_by<
50
51 // by Full Name
52 boost::multi_index::ordered_unique<
53 boost::multi_index::tag<byFullName>,
54 boost::multi_index::const_mem_fun<InMemoryStorageEntry, const Name&,
55 &InMemoryStorageEntry::getFullName>,
56 std::less<Name>
57 >
58
59 >
60 > Cache;
61
62 /** @brief Represents a self-defined const_iterator for the in-memory storage
63 *
64 * @note Don't try to instantiate this class directly, use InMemoryStorage::begin() instead.
65 */
Davide Pesaventodb4da5e2018-06-15 11:37:52 -040066 class const_iterator
Jiewen Tan99135962014-09-20 02:18:53 -070067 {
68 public:
Davide Pesaventodb4da5e2018-06-15 11:37:52 -040069 using iterator_category = std::input_iterator_tag;
70 using value_type = const Data;
71 using difference_type = std::ptrdiff_t;
72 using pointer = value_type*;
73 using reference = value_type&;
74
Jiewen Tan99135962014-09-20 02:18:53 -070075 const_iterator(const Data* ptr, const Cache* cache,
76 Cache::index<byFullName>::type::iterator it);
77
78 const_iterator&
79 operator++();
80
81 const_iterator
82 operator++(int);
83
Davide Pesaventodb4da5e2018-06-15 11:37:52 -040084 reference
Jiewen Tan99135962014-09-20 02:18:53 -070085 operator*();
86
Davide Pesaventodb4da5e2018-06-15 11:37:52 -040087 pointer
Jiewen Tan99135962014-09-20 02:18:53 -070088 operator->();
89
90 bool
91 operator==(const const_iterator& rhs);
92
93 bool
94 operator!=(const const_iterator& rhs);
95
96 private:
97 const Data* m_ptr;
98 const Cache* m_cache;
99 Cache::index<byFullName>::type::iterator m_it;
100 };
101
102 /** @brief Represents an error might be thrown during reduce the current capacity of the
103 * in-memory storage through function setCapacity(size_t nMaxPackets).
104 */
105 class Error : public std::runtime_error
106 {
107 public:
Junxiao Shi13d85e02017-07-07 07:34:02 +0000108 Error()
109 : std::runtime_error("Cannot reduce the capacity of the in-memory storage!")
Jiewen Tan99135962014-09-20 02:18:53 -0700110 {
111 }
112 };
113
Yingdi Yu404eafd2016-03-06 14:54:25 -0800114 /** @brief Create a InMemoryStorage with up to @p limit entries
115 * The InMemoryStorage created through this method will ignore MustBeFresh in interest processing
116 */
Jiewen Tan99135962014-09-20 02:18:53 -0700117 explicit
118 InMemoryStorage(size_t limit = std::numeric_limits<size_t>::max());
119
Yingdi Yu404eafd2016-03-06 14:54:25 -0800120 /** @brief Create a InMemoryStorage with up to @p limit entries
121 * The InMemoryStorage created through this method will handle MustBeFresh in interest processing
122 */
123 explicit
124 InMemoryStorage(boost::asio::io_service& ioService,
125 size_t limit = std::numeric_limits<size_t>::max());
126
Jiewen Tan99135962014-09-20 02:18:53 -0700127 /** @note Please make sure to implement it to free m_freeEntries and evict
128 * all items in the derived class for anybody who wishes to inherit this class
129 */
130 virtual
131 ~InMemoryStorage();
132
133 /** @brief Inserts a Data packet
134 *
Junxiao Shi13d85e02017-07-07 07:34:02 +0000135 * @param data the packet to insert, must be signed and have wire encoding
Yingdi Yu404eafd2016-03-06 14:54:25 -0800136 * @param mustBeFreshProcessingWindow Beyond this time period after the data is inserted, the
137 * data can only be used to answer interest without MustBeFresh selector.
138 *
Jiewen Tan99135962014-09-20 02:18:53 -0700139 * @note Packets are considered duplicate if the name with implicit digest matches.
140 * The new Data packet with the identical name, but a different payload
141 * will be placed in the in-memory storage.
142 *
143 * @note It will invoke afterInsert(shared_ptr<InMemoryStorageEntry>).
144 */
145 void
Yingdi Yu404eafd2016-03-06 14:54:25 -0800146 insert(const Data& data, const time::milliseconds& mustBeFreshProcessingWindow = INFINITE_WINDOW);
Jiewen Tan99135962014-09-20 02:18:53 -0700147
148 /** @brief Finds the best match Data for an Interest
149 *
150 * @note It will invoke afterAccess(shared_ptr<InMemoryStorageEntry>).
151 * As currently it is impossible to determine whether a Name contains implicit digest or not,
152 * therefore this find function is not able to locate a packet according to an interest(
153 * including implicit digest) whose name is not the full name of the data matching the
154 * implicit digest.
155 *
156 * @return{ the best match, if any; otherwise a null shared_ptr }
157 */
158 shared_ptr<const Data>
159 find(const Interest& interest);
160
161 /** @brief Finds the best match Data for a Name with or without
162 * the implicit digest.
163 *
164 * If packets with the same name but different digests exist
165 * and the Name supplied is the one without implicit digest, a packet
166 * will be arbitrarily chosen to return.
167 *
168 * @note It will invoke afterAccess(shared_ptr<InMemoryStorageEntry>).
169 *
170 * @return{ the one matched the Name; otherwise a null shared_ptr }
171 */
172 shared_ptr<const Data>
173 find(const Name& name);
174
175 /** @brief Deletes in-memory storage entry by prefix by default.
Alexander Afanasyevf2a46222015-09-17 18:01:30 -0700176 * @param prefix Exact name of a prefix of the data to remove
177 * @param isPrefix If false, the function will only delete the
Jiewen Tan99135962014-09-20 02:18:53 -0700178 * entry completely matched with the prefix according to canonical ordering.
179 * For this case, user should substitute the prefix with full name.
180 *
Junxiao Shi4c45fd82018-07-13 13:53:24 -0400181 * @warning Please do not use this function directly in any derived class to erase
182 * an entry from the cache, use eraseImpl() instead.
Jiewen Tan99135962014-09-20 02:18:53 -0700183 * @note It will invoke beforeErase(shared_ptr<InMemoryStorageEntry>).
184 */
185 void
186 erase(const Name& prefix, const bool isPrefix = true);
187
188 /** @return{ maximum number of packets that can be allowed to store in in-memory storage }
189 */
190 size_t
191 getLimit() const
192 {
193 return m_limit;
194 }
195
196 /** @return{ number of packets stored in in-memory storage }
197 */
198 size_t
199 size() const
200 {
201 return m_nPackets;
202 }
203
204 /** @brief Returns begin iterator of the in-memory storage ordering by
205 * name with digest
206 *
207 * @return{ const_iterator pointing to the beginning of the m_cache }
208 */
209 InMemoryStorage::const_iterator
210 begin() const;
211
212 /** @brief Returns end iterator of the in-memory storage ordering by
213 * name with digest
214 *
215 * @return{ const_iterator pointing to the end of the m_cache }
216 */
217 InMemoryStorage::const_iterator
218 end() const;
219
Junxiao Shi99848502014-10-13 19:22:22 -0700220NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
Jiewen Tan99135962014-09-20 02:18:53 -0700221 /** @brief Update the entry when the entry is returned by the find() function
222 * according to derived class implemented replacement policy
223 */
224 virtual void
225 afterAccess(InMemoryStorageEntry* entry);
226
227 /** @brief Update the entry or other data structures
228 * after a entry is successfully inserted
229 * according to derived class implemented replacement policy
230 */
231 virtual void
232 afterInsert(InMemoryStorageEntry* entry);
233
234 /** @brief Update the entry or other data structures
235 * before a entry is successfully erased
236 * according to derived class implemented replacement policy
237 */
238 virtual void
239 beforeErase(InMemoryStorageEntry* entry);
240
241 /** @brief Removes one Data packet from in-memory storage based on
242 * derived class implemented replacement policy
Junxiao Shi4c45fd82018-07-13 13:53:24 -0400243 * @return whether a Data packet was removed
Jiewen Tan99135962014-09-20 02:18:53 -0700244 *
Junxiao Shi4c45fd82018-07-13 13:53:24 -0400245 * @warning Please do not use this function directly in any derived class to erase
246 * an entry from the cache, use eraseImpl() instead.
Jiewen Tan99135962014-09-20 02:18:53 -0700247 */
248 virtual bool
249 evictItem() = 0;
250
Junxiao Shi99848502014-10-13 19:22:22 -0700251NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
Jiewen Tan99135962014-09-20 02:18:53 -0700252 /** @brief sets current capacity of in-memory storage (in packets)
253 */
254 void
255 setCapacity(size_t nMaxPackets);
256
257 /** @brief returns current capacity of in-memory storage (in packets)
258 * @return{ number of packets that can be stored in application cache }
259 */
260 size_t
261 getCapacity() const
262 {
263 return m_capacity;
264 }
265
266 /** @brief returns true if the in-memory storage uses up the current capacity, false otherwise
267 */
268 bool
269 isFull() const
270 {
271 return size() >= m_capacity;
272 }
273
274 /** @brief deletes in-memory storage entries by the Name with implicit digest.
275 *
276 * This is the function one should use to erase entry in the cache
277 * in derived class.
278 * It won't invoke beforeErase(shared_ptr<Entry>).
279 */
280 void
281 eraseImpl(const Name& name);
282
283 /** @brief Prints contents of the in-memory storage
284 */
285 void
286 printCache(std::ostream& os) const;
287
Junxiao Shi99848502014-10-13 19:22:22 -0700288NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
Jiewen Tan99135962014-09-20 02:18:53 -0700289 /** @brief free in-memory storage entries by an iterator pointing to that entry.
Alexander Afanasyev8e131fd2014-12-15 21:31:50 -0800290 @return An iterator pointing to the element that followed the last element erased.
291 */
292 Cache::iterator
293 freeEntry(Cache::iterator it);
Jiewen Tan99135962014-09-20 02:18:53 -0700294
295 /** @brief Implements child selector (leftmost, rightmost, undeclared).
296 * Operates on the first layer of a skip list.
297 *
298 * startingPoint must be less than Interest Name.
299 * startingPoint can be equal to Interest Name only
300 * when the item is in the begin() position.
301 *
302 * Iterates toward greater Names, terminates when application cache entry falls out of Interest
303 * prefix. When childSelector = leftmost, returns first application cache entry that satisfies
304 * other selectors. When childSelector = rightmost, it goes till the end, and returns application
305 * cache entry that satisfies other selectors. Returned application cache entry is the leftmost
306 * child of the rightmost child.
307 * @return{ the best match, if any; otherwise 0 }
308 */
309 InMemoryStorageEntry*
310 selectChild(const Interest& interest,
311 Cache::index<byFullName>::type::iterator startingPoint) const;
312
Yingdi Yu404eafd2016-03-06 14:54:25 -0800313 /** @brief Get the next iterator (include startingPoint) that satisfies MustBeFresh requirement
314 *
315 * @param startingPoint The iterator to start with.
316 * @return The next qualified iterator
317 */
318 Cache::index<byFullName>::type::iterator
319 findNextFresh(Cache::index<byFullName>::type::iterator startingPoint) const;
320
321private:
322 void
323 init();
324
325public:
326 static const time::milliseconds INFINITE_WINDOW;
327
328private:
329 static const time::milliseconds ZERO_WINDOW;
330
Jiewen Tan99135962014-09-20 02:18:53 -0700331private:
332 Cache m_cache;
333 /// user defined maximum capacity of the in-memory storage in packets
334 size_t m_limit;
335 /// current capacity of the in-memory storage in packets
336 size_t m_capacity;
337 /// current number of packets in in-memory storage
338 size_t m_nPackets;
339 /// memory pool
340 std::stack<InMemoryStorageEntry*> m_freeEntries;
Yingdi Yu404eafd2016-03-06 14:54:25 -0800341 /// scheduler
342 unique_ptr<Scheduler> m_scheduler;
Jiewen Tan99135962014-09-20 02:18:53 -0700343};
344
Jiewen Tan99135962014-09-20 02:18:53 -0700345} // namespace ndn
346
Junxiao Shic542f632017-07-18 14:20:32 +0000347#endif // NDN_IMS_IN_MEMORY_STORAGE_HPP