blob: fd12c68fd83c4905a0eff5706562d428e84f05e5 [file] [log] [blame]
Alexander Afanasyev78057c32012-07-06 15:18:46 -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
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070021#include "ndn-fib-impl.h"
Alexander Afanasyev78057c32012-07-06 15:18:46 -070022
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070023#include "ns3/ndn-face.h"
24#include "ns3/ndn-interest-header.h"
Alexander Afanasyev78057c32012-07-06 15:18:46 -070025
26#include "ns3/node.h"
27#include "ns3/assert.h"
28#include "ns3/names.h"
29#include "ns3/log.h"
30
31#include <boost/ref.hpp>
32#include <boost/lambda/lambda.hpp>
33#include <boost/lambda/bind.hpp>
34namespace ll = boost::lambda;
35
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070036NS_LOG_COMPONENT_DEFINE ("ndn.fib.FibImpl");
Alexander Afanasyev78057c32012-07-06 15:18:46 -070037
38namespace ns3 {
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070039namespace ndn {
40namespace fib {
Alexander Afanasyev78057c32012-07-06 15:18:46 -070041
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070042NS_OBJECT_ENSURE_REGISTERED (FibImpl);
Alexander Afanasyev78057c32012-07-06 15:18:46 -070043
44TypeId
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070045FibImpl::GetTypeId (void)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070046{
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070047 static TypeId tid = TypeId ("ns3::ndn::fib::Default") // cheating ns3 object system
48 .SetParent<Fib> ()
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070049 .SetGroupName ("Ndn")
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070050 .AddConstructor<FibImpl> ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070051 ;
52 return tid;
53}
54
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070055FibImpl::FibImpl ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070056{
57}
58
59void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070060FibImpl::NotifyNewAggregate ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070061{
62 Object::NotifyNewAggregate ();
63}
64
65void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070066FibImpl::DoDispose (void)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070067{
68 clear ();
69 Object::DoDispose ();
70}
71
72
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070073Ptr<Entry>
74FibImpl::LongestPrefixMatch (const InterestHeader &interest)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070075{
Alexander Afanasyev30f60e32012-07-10 14:21:16 -070076 super::iterator item = super::longest_prefix_match (interest.GetName ());
Alexander Afanasyev78057c32012-07-06 15:18:46 -070077 // @todo use predicate to search with exclude filters
78
79 if (item == super::end ())
80 return 0;
81 else
82 return item->payload ();
83}
84
85
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070086Ptr<Entry>
87FibImpl::Add (const NameComponents &prefix, Ptr<Face> face, int32_t metric)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070088{
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070089 return Add (Create<NameComponents> (prefix), face, metric);
Alexander Afanasyev78057c32012-07-06 15:18:46 -070090}
91
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070092Ptr<Entry>
93FibImpl::Add (const Ptr<const NameComponents> &prefix, Ptr<Face> face, int32_t metric)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070094{
Alexander Afanasyev1ba09b82012-07-09 09:16:14 -070095 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric);
Alexander Afanasyev78057c32012-07-06 15:18:46 -070096
97 // will add entry if doesn't exists, or just return an iterator to the existing entry
Alexander Afanasyev30f60e32012-07-10 14:21:16 -070098 std::pair< super::iterator, bool > result = super::insert (*prefix, 0);
99 if (result.first != super::end ())
100 {
101 if (result.second)
102 {
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700103 Ptr<EntryImpl> newEntry = Create<EntryImpl> (prefix);
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700104 newEntry->SetTrie (result.first);
105 result.first->set_payload (newEntry);
106 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700107
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700108 super::modify (result.first,
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700109 ll::bind (&Entry::AddOrUpdateRoutingMetric, ll::_1, face, metric));
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700110
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700111 return result.first->payload ();
112 }
113 else
114 return 0;
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700115}
116
117void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700118FibImpl::Remove (const Ptr<const NameComponents> &prefix)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700119{
120 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
121
122 super::erase (*prefix);
123}
124
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700125// void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700126// FibImpl::Invalidate (const Ptr<const NameComponents> &prefix)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700127// {
128// NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700129
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700130// super::iterator foundItem, lastItem;
131// bool reachLast;
132// boost::tie (foundItem, reachLast, lastItem) = super::getTrie ().find (*prefix);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700133
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700134// if (!reachLast || lastItem->payload () == 0)
135// return; // nothing to invalidate
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700136
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700137// super::modify (lastItem,
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700138// ll::bind (&Entry::Invalidate, ll::_1));
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700139// }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700140
141void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700142FibImpl::InvalidateAll ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700143{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700144 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ());
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700145
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700146 super::parent_trie::recursive_iterator item (super::getTrie ());
147 super::parent_trie::recursive_iterator end (0);
148 for (; item != end; item++)
149 {
150 if (item->payload () == 0) continue;
151
152 super::modify (&(*item),
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700153 ll::bind (&Entry::Invalidate, ll::_1));
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700154 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700155}
156
157void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700158FibImpl::RemoveFace (super::parent_trie &item, Ptr<Face> face)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700159{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700160 if (item.payload () == 0) return;
161 NS_LOG_FUNCTION (this);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700162
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700163 super::modify (&item,
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700164 ll::bind (&Entry::RemoveFace, ll::_1, face));
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700165}
166
167void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700168FibImpl::RemoveFromAll (Ptr<Face> face)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700169{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700170 NS_LOG_FUNCTION (this);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700171
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700172 std::for_each (super::parent_trie::recursive_iterator (super::getTrie ()),
173 super::parent_trie::recursive_iterator (0),
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700174 ll::bind (&FibImpl::RemoveFace,
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700175 this, ll::_1, face));
176
177 super::parent_trie::recursive_iterator trieNode (super::getTrie ());
178 super::parent_trie::recursive_iterator end (0);
179 for (; trieNode != end; trieNode++)
180 {
181 if (trieNode->payload () == 0) continue;
182
183 if (trieNode->payload ()->m_faces.size () == 0)
184 {
185 trieNode = super::parent_trie::recursive_iterator (trieNode->erase ());
186 }
187 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700188}
189
190void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700191FibImpl::Print (std::ostream &os) const
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700192{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700193 // !!! unordered_set imposes "random" order of item in the same level !!!
194 super::parent_trie::const_recursive_iterator item (super::getTrie ());
195 super::parent_trie::const_recursive_iterator end (0);
196 for (; item != end; item++)
197 {
198 if (item->payload () == 0) continue;
199
200 os << item->payload ()->GetPrefix () << "\t" << *item->payload () << "\n";
201 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700202}
203
Alexander Afanasyevf1e013f2012-07-11 17:59:40 -0700204uint32_t
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700205FibImpl::GetSize () const
Alexander Afanasyevf1e013f2012-07-11 17:59:40 -0700206{
207 return super::getPolicy ().size ();
208}
209
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700210Ptr<const Entry>
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700211FibImpl::Begin () const
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700212{
213 super::parent_trie::const_recursive_iterator item (super::getTrie ());
214 super::parent_trie::const_recursive_iterator end (0);
215 for (; item != end; item++)
216 {
217 if (item->payload () == 0) continue;
218 break;
219 }
220
221 if (item == end)
222 return End ();
223 else
224 return item->payload ();
225}
226
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700227Ptr<const Entry>
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700228FibImpl::End () const
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700229{
230 return 0;
231}
232
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700233Ptr<const Entry>
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700234FibImpl::Next (Ptr<const Entry> from) const
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700235{
236 if (from == 0) return 0;
237
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700238 super::parent_trie::const_recursive_iterator item (*StaticCast<const EntryImpl> (from)->to_iterator ());
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700239 super::parent_trie::const_recursive_iterator end (0);
240 for (item++; item != end; item++)
241 {
242 if (item->payload () == 0) continue;
243 break;
244 }
245
246 if (item == end)
247 return End ();
248 else
249 return item->payload ();
250}
251
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700252Ptr<Entry>
253FibImpl::Begin ()
254{
255 super::parent_trie::recursive_iterator item (super::getTrie ());
256 super::parent_trie::recursive_iterator end (0);
257 for (; item != end; item++)
258 {
259 if (item->payload () == 0) continue;
260 break;
261 }
262
263 if (item == end)
264 return End ();
265 else
266 return item->payload ();
267}
268
269Ptr<Entry>
270FibImpl::End ()
271{
272 return 0;
273}
274
275Ptr<Entry>
276FibImpl::Next (Ptr<Entry> from)
277{
278 if (from == 0) return 0;
279
280 super::parent_trie::recursive_iterator item (*StaticCast<EntryImpl> (from)->to_iterator ());
281 super::parent_trie::recursive_iterator end (0);
282 for (item++; item != end; item++)
283 {
284 if (item->payload () == 0) continue;
285 break;
286 }
287
288 if (item == end)
289 return End ();
290 else
291 return item->payload ();
292}
293
294
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700295} // namespace fib
296} // namespace ndn
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700297} // namespace ns3