blob: b9fb9da84c6a158a62253d82cd7292f2bcb0dd7d [file] [log] [blame]
Jiewen Tan99135962014-09-20 02:18:53 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
3 * Copyright (c) 2013-2014 Regents of the University of California.
4 *
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
22#ifndef NDN_UTIL_IN_MEMORY_STORAGE_HPP
23#define NDN_UTIL_IN_MEMORY_STORAGE_HPP
24
25#include "../common.hpp"
26#include "../interest.hpp"
27#include "../data.hpp"
28
29#include "in-memory-storage-entry.hpp"
30
31#include <boost/multi_index/member.hpp>
32#include <boost/multi_index_container.hpp>
33#include <boost/multi_index/ordered_index.hpp>
34#include <boost/multi_index/sequenced_index.hpp>
35#include <boost/multi_index/identity.hpp>
36#include <boost/multi_index/mem_fun.hpp>
37
38#include <stack>
39#include <iterator>
Jiewen Tan99135962014-09-20 02:18:53 -070040
41namespace ndn {
42namespace util {
43
44/** @brief Represents in-memory storage
45 */
46class InMemoryStorage : noncopyable
47{
48public:
49 //multi_index_container to implement storage
50 class byFullName;
51
52 typedef boost::multi_index_container<
53 InMemoryStorageEntry*,
54 boost::multi_index::indexed_by<
55
56 // by Full Name
57 boost::multi_index::ordered_unique<
58 boost::multi_index::tag<byFullName>,
59 boost::multi_index::const_mem_fun<InMemoryStorageEntry, const Name&,
60 &InMemoryStorageEntry::getFullName>,
61 std::less<Name>
62 >
63
64 >
65 > Cache;
66
67 /** @brief Represents a self-defined const_iterator for the in-memory storage
68 *
69 * @note Don't try to instantiate this class directly, use InMemoryStorage::begin() instead.
70 */
71 class const_iterator : public std::iterator<std::input_iterator_tag, const Data>
72 {
73 public:
74 const_iterator(const Data* ptr, const Cache* cache,
75 Cache::index<byFullName>::type::iterator it);
76
77 const_iterator&
78 operator++();
79
80 const_iterator
81 operator++(int);
82
83 const Data&
84 operator*();
85
86 const Data*
87 operator->();
88
89 bool
90 operator==(const const_iterator& rhs);
91
92 bool
93 operator!=(const const_iterator& rhs);
94
95 private:
96 const Data* m_ptr;
97 const Cache* m_cache;
98 Cache::index<byFullName>::type::iterator m_it;
99 };
100
101 /** @brief Represents an error might be thrown during reduce the current capacity of the
102 * in-memory storage through function setCapacity(size_t nMaxPackets).
103 */
104 class Error : public std::runtime_error
105 {
106 public:
107 Error() : std::runtime_error("Cannot reduce the capacity of the in-memory storage!")
108 {
109 }
110 };
111
112 explicit
113 InMemoryStorage(size_t limit = std::numeric_limits<size_t>::max());
114
115 /** @note Please make sure to implement it to free m_freeEntries and evict
116 * all items in the derived class for anybody who wishes to inherit this class
117 */
118 virtual
119 ~InMemoryStorage();
120
121 /** @brief Inserts a Data packet
122 *
123 * @note Packets are considered duplicate if the name with implicit digest matches.
124 * The new Data packet with the identical name, but a different payload
125 * will be placed in the in-memory storage.
126 *
127 * @note It will invoke afterInsert(shared_ptr<InMemoryStorageEntry>).
128 */
129 void
130 insert(const Data& data);
131
132 /** @brief Finds the best match Data for an Interest
133 *
134 * @note It will invoke afterAccess(shared_ptr<InMemoryStorageEntry>).
135 * As currently it is impossible to determine whether a Name contains implicit digest or not,
136 * therefore this find function is not able to locate a packet according to an interest(
137 * including implicit digest) whose name is not the full name of the data matching the
138 * implicit digest.
139 *
140 * @return{ the best match, if any; otherwise a null shared_ptr }
141 */
142 shared_ptr<const Data>
143 find(const Interest& interest);
144
145 /** @brief Finds the best match Data for a Name with or without
146 * the implicit digest.
147 *
148 * If packets with the same name but different digests exist
149 * and the Name supplied is the one without implicit digest, a packet
150 * will be arbitrarily chosen to return.
151 *
152 * @note It will invoke afterAccess(shared_ptr<InMemoryStorageEntry>).
153 *
154 * @return{ the one matched the Name; otherwise a null shared_ptr }
155 */
156 shared_ptr<const Data>
157 find(const Name& name);
158
159 /** @brief Deletes in-memory storage entry by prefix by default.
160 * @param[in] isPrefix If it is clear, the function will only delete the
161 * entry completely matched with the prefix according to canonical ordering.
162 * For this case, user should substitute the prefix with full name.
163 *
164 * @note Please do not use this function directly in any derived class to erase
165 * entry in the cache, use eraseHelper instead.
166 * @note It will invoke beforeErase(shared_ptr<InMemoryStorageEntry>).
167 */
168 void
169 erase(const Name& prefix, const bool isPrefix = true);
170
171 /** @return{ maximum number of packets that can be allowed to store in in-memory storage }
172 */
173 size_t
174 getLimit() const
175 {
176 return m_limit;
177 }
178
179 /** @return{ number of packets stored in in-memory storage }
180 */
181 size_t
182 size() const
183 {
184 return m_nPackets;
185 }
186
187 /** @brief Returns begin iterator of the in-memory storage ordering by
188 * name with digest
189 *
190 * @return{ const_iterator pointing to the beginning of the m_cache }
191 */
192 InMemoryStorage::const_iterator
193 begin() const;
194
195 /** @brief Returns end iterator of the in-memory storage ordering by
196 * name with digest
197 *
198 * @return{ const_iterator pointing to the end of the m_cache }
199 */
200 InMemoryStorage::const_iterator
201 end() const;
202
Junxiao Shi99848502014-10-13 19:22:22 -0700203NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
Jiewen Tan99135962014-09-20 02:18:53 -0700204 /** @brief Update the entry when the entry is returned by the find() function
205 * according to derived class implemented replacement policy
206 */
207 virtual void
208 afterAccess(InMemoryStorageEntry* entry);
209
210 /** @brief Update the entry or other data structures
211 * after a entry is successfully inserted
212 * according to derived class implemented replacement policy
213 */
214 virtual void
215 afterInsert(InMemoryStorageEntry* entry);
216
217 /** @brief Update the entry or other data structures
218 * before a entry is successfully erased
219 * according to derived class implemented replacement policy
220 */
221 virtual void
222 beforeErase(InMemoryStorageEntry* entry);
223
224 /** @brief Removes one Data packet from in-memory storage based on
225 * derived class implemented replacement policy
226 *
227 * Please do not use this function directly in any derived class to erase
228 * entry in the cache, use eraseHelper instead.
229 * @return{ whether the Data was removed }
230 */
231 virtual bool
232 evictItem() = 0;
233
Junxiao Shi99848502014-10-13 19:22:22 -0700234NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PROTECTED:
Jiewen Tan99135962014-09-20 02:18:53 -0700235 /** @brief sets current capacity of in-memory storage (in packets)
236 */
237 void
238 setCapacity(size_t nMaxPackets);
239
240 /** @brief returns current capacity of in-memory storage (in packets)
241 * @return{ number of packets that can be stored in application cache }
242 */
243 size_t
244 getCapacity() const
245 {
246 return m_capacity;
247 }
248
249 /** @brief returns true if the in-memory storage uses up the current capacity, false otherwise
250 */
251 bool
252 isFull() const
253 {
254 return size() >= m_capacity;
255 }
256
257 /** @brief deletes in-memory storage entries by the Name with implicit digest.
258 *
259 * This is the function one should use to erase entry in the cache
260 * in derived class.
261 * It won't invoke beforeErase(shared_ptr<Entry>).
262 */
263 void
264 eraseImpl(const Name& name);
265
266 /** @brief Prints contents of the in-memory storage
267 */
268 void
269 printCache(std::ostream& os) const;
270
Junxiao Shi99848502014-10-13 19:22:22 -0700271NDN_CXX_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
Jiewen Tan99135962014-09-20 02:18:53 -0700272 /** @brief free in-memory storage entries by an iterator pointing to that entry.
273 */
274 void
275 freeEntry(Cache::index<byFullName>::type::iterator it);
276
277 /** @brief Implements child selector (leftmost, rightmost, undeclared).
278 * Operates on the first layer of a skip list.
279 *
280 * startingPoint must be less than Interest Name.
281 * startingPoint can be equal to Interest Name only
282 * when the item is in the begin() position.
283 *
284 * Iterates toward greater Names, terminates when application cache entry falls out of Interest
285 * prefix. When childSelector = leftmost, returns first application cache entry that satisfies
286 * other selectors. When childSelector = rightmost, it goes till the end, and returns application
287 * cache entry that satisfies other selectors. Returned application cache entry is the leftmost
288 * child of the rightmost child.
289 * @return{ the best match, if any; otherwise 0 }
290 */
291 InMemoryStorageEntry*
292 selectChild(const Interest& interest,
293 Cache::index<byFullName>::type::iterator startingPoint) const;
294
295private:
296 Cache m_cache;
297 /// user defined maximum capacity of the in-memory storage in packets
298 size_t m_limit;
299 /// current capacity of the in-memory storage in packets
300 size_t m_capacity;
301 /// current number of packets in in-memory storage
302 size_t m_nPackets;
303 /// memory pool
304 std::stack<InMemoryStorageEntry*> m_freeEntries;
305};
306
307} // namespace util
308} // namespace ndn
309
310#endif // NDN_UTIL_IN_MEMORY_STORAGE_HPP