blob: ddcb8edcf7b13707636f1533a0be3ba6dcd8f167 [file] [log] [blame]
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -07001/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
2/*
3 * Copyright (c) 2011 University of California, Los Angeles
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
19 */
20
21#ifndef NDN_CONTENT_STORE_IMPL_H_
22#define NDN_CONTENT_STORE_IMPL_H_
23
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -070024#include "ns3/ndnSIM/model/ndn-common.hpp"
25
Alexander Afanasyev0c395372014-12-20 15:54:02 -080026#include "ndn-content-store.hpp"
27
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070028#include "ns3/packet.h"
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070029#include <boost/foreach.hpp>
30
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -080031#include "ns3/log.h"
32#include "ns3/uinteger.h"
33#include "ns3/string.h"
34
Alexander Afanasyev0c395372014-12-20 15:54:02 -080035#include "../../utils/trie/trie-with-policy.hpp"
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070036
37namespace ns3 {
38namespace ndn {
39namespace cs {
40
Alexander Afanasyev79206512013-07-27 16:49:12 -070041/**
42 * @ingroup ndn-cs
43 * @brief Cache entry implementation with additional references to the base container
44 */
Alexander Afanasyev29c19b92012-09-03 23:46:41 -070045template<class CS>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080046class EntryImpl : public Entry {
Alexander Afanasyev29c19b92012-09-03 23:46:41 -070047public:
Alexander Afanasyev8566f452012-12-10 15:21:51 -080048 typedef Entry base_type;
Alexander Afanasyev25093a32013-02-01 13:00:13 -080049
Alexander Afanasyev8566f452012-12-10 15:21:51 -080050public:
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -070051 EntryImpl(Ptr<ContentStore> cs, shared_ptr<const Data> data)
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080052 : Entry(cs, data)
53 , item_(0)
Alexander Afanasyev29c19b92012-09-03 23:46:41 -070054 {
55 }
56
57 void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080058 SetTrie(typename CS::super::iterator item)
Alexander Afanasyev29c19b92012-09-03 23:46:41 -070059 {
60 item_ = item;
61 }
62
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080063 typename CS::super::iterator
64 to_iterator()
65 {
66 return item_;
67 }
68 typename CS::super::const_iterator
69 to_iterator() const
70 {
71 return item_;
72 }
Alexander Afanasyev25093a32013-02-01 13:00:13 -080073
Alexander Afanasyev29c19b92012-09-03 23:46:41 -070074private:
75 typename CS::super::iterator item_;
76};
77
Alexander Afanasyev79206512013-07-27 16:49:12 -070078/**
79 * @ingroup ndn-cs
80 * @brief Base implementation of NDN content store
81 */
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070082template<class Policy>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080083class ContentStoreImpl
84 : public ContentStore,
85 protected ndnSIM::
86 trie_with_policy<Name,
87 ndnSIM::smart_pointer_payload_traits<EntryImpl<ContentStoreImpl<Policy>>,
88 Entry>,
89 Policy> {
Alexander Afanasyev29c19b92012-09-03 23:46:41 -070090public:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080091 typedef ndnSIM::
92 trie_with_policy<Name, ndnSIM::smart_pointer_payload_traits<EntryImpl<ContentStoreImpl<Policy>>,
93 Entry>,
94 Policy> super;
Alexander Afanasyev25093a32013-02-01 13:00:13 -080095
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080096 typedef EntryImpl<ContentStoreImpl<Policy>> entry;
Alexander Afanasyev25093a32013-02-01 13:00:13 -080097
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070098 static TypeId
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -080099 GetTypeId();
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800100
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800101 ContentStoreImpl(){};
102 virtual ~ContentStoreImpl(){};
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800103
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700104 // from ContentStore
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800105
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -0700106 virtual inline shared_ptr<Data>
107 Lookup(shared_ptr<const Interest> interest);
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800108
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700109 virtual inline bool
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -0700110 Add(shared_ptr<const Data> data);
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700111
112 // virtual bool
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -0700113 // Remove (shared_ptr<Interest> header);
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800114
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700115 virtual inline void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800116 Print(std::ostream& os) const;
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700117
Alexander Afanasyev29c19b92012-09-03 23:46:41 -0700118 virtual uint32_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800119 GetSize() const;
Alexander Afanasyev29c19b92012-09-03 23:46:41 -0700120
121 virtual Ptr<Entry>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800122 Begin();
Alexander Afanasyev29c19b92012-09-03 23:46:41 -0700123
124 virtual Ptr<Entry>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800125 End();
Alexander Afanasyev29c19b92012-09-03 23:46:41 -0700126
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800127 virtual Ptr<Entry> Next(Ptr<Entry>);
Alexander Afanasyev29c19b92012-09-03 23:46:41 -0700128
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800129 const typename super::policy_container&
130 GetPolicy() const
131 {
132 return super::getPolicy();
133 }
Alexander Afanasyevf21bfc12013-11-17 11:58:33 -0800134
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800135 typename super::policy_container&
136 GetPolicy()
137 {
138 return super::getPolicy();
139 }
140
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700141private:
142 void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800143 SetMaxSize(uint32_t maxSize);
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700144
145 uint32_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800146 GetMaxSize() const;
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800147
148private:
149 static LogComponent g_log; ///< @brief Logging variable
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800150
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800151 /// @brief trace of for entry additions (fired every time entry is successfully added to the
152 /// cache): first parameter is pointer to the CS entry
153 TracedCallback<Ptr<const Entry>> m_didAddEntry;
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700154};
155
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800156//////////////////////////////////////////
157////////// Implementation ////////////////
158//////////////////////////////////////////
159
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800160template<class Policy>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800161LogComponent
162 ContentStoreImpl<Policy>::g_log = LogComponent(("ndn.cs." + Policy::GetName()).c_str());
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800163
164template<class Policy>
165TypeId
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800166ContentStoreImpl<Policy>::GetTypeId()
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800167{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800168 static TypeId tid =
169 TypeId(("ns3::ndn::cs::" + Policy::GetName()).c_str())
170 .SetGroupName("Ndn")
171 .SetParent<ContentStore>()
172 .AddConstructor<ContentStoreImpl<Policy>>()
173 .AddAttribute("MaxSize",
174 "Set maximum number of entries in ContentStore. If 0, limit is not enforced",
175 StringValue("100"), MakeUintegerAccessor(&ContentStoreImpl<Policy>::GetMaxSize,
176 &ContentStoreImpl<Policy>::SetMaxSize),
177 MakeUintegerChecker<uint32_t>())
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800178
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800179 .AddTraceSource("DidAddEntry",
180 "Trace fired every time entry is successfully added to the cache",
181 MakeTraceSourceAccessor(&ContentStoreImpl<Policy>::m_didAddEntry));
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800182
183 return tid;
184}
185
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800186struct isNotExcluded {
187 inline isNotExcluded(const Exclude& exclude)
188 : m_exclude(exclude)
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700189 {
190 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800191
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700192 bool
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800193 operator()(const name::Component& comp) const
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700194 {
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800195 return !m_exclude.isExcluded(comp);
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700196 }
197
198private:
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800199 const Exclude& m_exclude;
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700200};
201
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800202template<class Policy>
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -0700203shared_ptr<Data>
204ContentStoreImpl<Policy>::Lookup(shared_ptr<const Interest> interest)
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800205{
Spyridon Mastorakis1f1cd5e2014-12-04 11:12:40 -0800206 NS_LOG_FUNCTION(this << interest->getName());
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800207
Alexander Afanasyeveec89ba2013-07-19 16:34:30 -0700208 typename super::const_iterator node;
Spyridon Mastorakis1f1cd5e2014-12-04 11:12:40 -0800209 if (interest->getExclude().empty()) {
210 node = this->deepest_prefix_match(interest->getName());
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800211 }
212 else {
Spyridon Mastorakis1f1cd5e2014-12-04 11:12:40 -0800213 node = this->deepest_prefix_match_if_next_level(interest->getName(),
214 isNotExcluded(interest->getExclude()));
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800215 }
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800216
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800217 if (node != this->end()) {
218 this->m_cacheHitsTrace(interest, node->payload()->GetData());
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800219
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -0700220 shared_ptr<Data> copy = make_shared<Data>(*node->payload()->GetData());
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800221 return copy;
222 }
223 else {
224 this->m_cacheMissesTrace(interest);
225 return 0;
226 }
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800227}
228
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800229template<class Policy>
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800230bool
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -0700231ContentStoreImpl<Policy>::Add(shared_ptr<const Data> data)
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800232{
Spyridon Mastorakis1f1cd5e2014-12-04 11:12:40 -0800233 NS_LOG_FUNCTION(this << data->getName());
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800234
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800235 Ptr<entry> newEntry = Create<entry>(this, data);
Spyridon Mastorakis1f1cd5e2014-12-04 11:12:40 -0800236 std::pair<typename super::iterator, bool> result = super::insert(data->getName(), newEntry);
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800237
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800238 if (result.first != super::end()) {
239 if (result.second) {
240 newEntry->SetTrie(result.first);
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800241
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800242 m_didAddEntry(newEntry);
243 return true;
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800244 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800245 else {
246 // should we do anything?
247 // update payload? add new payload?
248 return false;
249 }
250 }
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800251 else
252 return false; // cannot insert entry
253}
254
255template<class Policy>
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800256void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800257ContentStoreImpl<Policy>::Print(std::ostream& os) const
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800258{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800259 for (typename super::policy_container::const_iterator item = this->getPolicy().begin();
260 item != this->getPolicy().end(); item++) {
Spyridon Mastorakis1f1cd5e2014-12-04 11:12:40 -0800261 os << item->payload ()->GetName () << std::endl;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800262 }
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800263}
264
265template<class Policy>
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800266void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800267ContentStoreImpl<Policy>::SetMaxSize(uint32_t maxSize)
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800268{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800269 this->getPolicy().set_max_size(maxSize);
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800270}
271
272template<class Policy>
273uint32_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800274ContentStoreImpl<Policy>::GetMaxSize() const
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800275{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800276 return this->getPolicy().get_max_size();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800277}
278
279template<class Policy>
280uint32_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800281ContentStoreImpl<Policy>::GetSize() const
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800282{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800283 return this->getPolicy().size();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800284}
285
286template<class Policy>
287Ptr<Entry>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800288ContentStoreImpl<Policy>::Begin()
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800289{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800290 typename super::parent_trie::recursive_iterator item(super::getTrie()), end(0);
291 for (; item != end; item++) {
292 if (item->payload() == 0)
293 continue;
294 break;
295 }
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800296
297 if (item == end)
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800298 return End();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800299 else
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800300 return item->payload();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800301}
302
303template<class Policy>
304Ptr<Entry>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800305ContentStoreImpl<Policy>::End()
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800306{
307 return 0;
308}
309
310template<class Policy>
311Ptr<Entry>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800312ContentStoreImpl<Policy>::Next(Ptr<Entry> from)
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800313{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800314 if (from == 0)
315 return 0;
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800316
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800317 typename super::parent_trie::recursive_iterator item(*StaticCast<entry>(from)->to_iterator()),
318 end(0);
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800319
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800320 for (item++; item != end; item++) {
321 if (item->payload() == 0)
322 continue;
323 break;
324 }
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800325
326 if (item == end)
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800327 return End();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800328 else
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800329 return item->payload();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800330}
331
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700332} // namespace cs
333} // namespace ndn
334} // namespace ns3
335
336#endif // NDN_CONTENT_STORE_IMPL_H_