blob: 46924861ac29771f91be986f91a19cafe5adcf0c [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{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -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;
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800209 if (interest->GetExclude() == 0) {
210 node = this->deepest_prefix_match(interest->GetName());
211 }
212 else {
213 node = this->deepest_prefix_match_if_next_level(interest->GetName(),
214 isNotExcluded(*interest->GetExclude()));
215 }
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 ConstCast<Packet>(copy->GetPayload())->RemoveAllPacketTags();
222 return copy;
223 }
224 else {
225 this->m_cacheMissesTrace(interest);
226 return 0;
227 }
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800228}
229
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800230template<class Policy>
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800231bool
Spyridon Mastorakis53e922f2014-10-17 17:29:26 -0700232ContentStoreImpl<Policy>::Add(shared_ptr<const Data> data)
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800233{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800234 NS_LOG_FUNCTION(this << data->GetName());
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800235
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800236 Ptr<entry> newEntry = Create<entry>(this, data);
237 std::pair<typename super::iterator, bool> result = super::insert(data->GetName(), newEntry);
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800238
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800239 if (result.first != super::end()) {
240 if (result.second) {
241 newEntry->SetTrie(result.first);
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800242
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800243 m_didAddEntry(newEntry);
244 return true;
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800245 }
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800246 else {
247 // should we do anything?
248 // update payload? add new payload?
249 return false;
250 }
251 }
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800252 else
253 return false; // cannot insert entry
254}
255
256template<class Policy>
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800257void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800258ContentStoreImpl<Policy>::Print(std::ostream& os) const
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800259{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800260 for (typename super::policy_container::const_iterator item = this->getPolicy().begin();
261 item != this->getPolicy().end(); item++) {
262 os << item->payload()->GetName() << std::endl;
263 }
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800264}
265
266template<class Policy>
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800267void
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800268ContentStoreImpl<Policy>::SetMaxSize(uint32_t maxSize)
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800269{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800270 this->getPolicy().set_max_size(maxSize);
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800271}
272
273template<class Policy>
274uint32_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800275ContentStoreImpl<Policy>::GetMaxSize() const
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800276{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800277 return this->getPolicy().get_max_size();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800278}
279
280template<class Policy>
281uint32_t
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800282ContentStoreImpl<Policy>::GetSize() const
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800283{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800284 return this->getPolicy().size();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800285}
286
287template<class Policy>
288Ptr<Entry>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800289ContentStoreImpl<Policy>::Begin()
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800290{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800291 typename super::parent_trie::recursive_iterator item(super::getTrie()), end(0);
292 for (; item != end; item++) {
293 if (item->payload() == 0)
294 continue;
295 break;
296 }
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800297
298 if (item == end)
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800299 return End();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800300 else
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800301 return item->payload();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800302}
303
304template<class Policy>
305Ptr<Entry>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800306ContentStoreImpl<Policy>::End()
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800307{
308 return 0;
309}
310
311template<class Policy>
312Ptr<Entry>
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800313ContentStoreImpl<Policy>::Next(Ptr<Entry> from)
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800314{
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800315 if (from == 0)
316 return 0;
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800317
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800318 typename super::parent_trie::recursive_iterator item(*StaticCast<entry>(from)->to_iterator()),
319 end(0);
Alexander Afanasyev25093a32013-02-01 13:00:13 -0800320
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800321 for (item++; item != end; item++) {
322 if (item->payload() == 0)
323 continue;
324 break;
325 }
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800326
327 if (item == end)
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800328 return End();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800329 else
Alexander Afanasyevbe55cf62014-12-20 17:51:09 -0800330 return item->payload();
Alexander Afanasyev991a0cc2012-12-10 11:38:19 -0800331}
332
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700333} // namespace cs
334} // namespace ndn
335} // namespace ns3
336
337#endif // NDN_CONTENT_STORE_IMPL_H_