blob: ccc4f10ddc7a87a2a47abee104f66b5dbb912b82 [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"
Alexander Afanasyevbd9c18e2012-11-19 15:23:41 -080024#include "ns3/ndn-interest.h"
Alexander Afanasyevadcccf42012-11-26 23:55:34 -080025#include "ns3/ndn-forwarding-strategy.h"
Alexander Afanasyev78057c32012-07-06 15:18:46 -070026
27#include "ns3/node.h"
28#include "ns3/assert.h"
29#include "ns3/names.h"
30#include "ns3/log.h"
31
32#include <boost/ref.hpp>
33#include <boost/lambda/lambda.hpp>
34#include <boost/lambda/bind.hpp>
35namespace ll = boost::lambda;
36
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070037NS_LOG_COMPONENT_DEFINE ("ndn.fib.FibImpl");
Alexander Afanasyev78057c32012-07-06 15:18:46 -070038
39namespace ns3 {
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070040namespace ndn {
41namespace fib {
Alexander Afanasyev78057c32012-07-06 15:18:46 -070042
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070043NS_OBJECT_ENSURE_REGISTERED (FibImpl);
Alexander Afanasyev78057c32012-07-06 15:18:46 -070044
45TypeId
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070046FibImpl::GetTypeId (void)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070047{
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070048 static TypeId tid = TypeId ("ns3::ndn::fib::Default") // cheating ns3 object system
49 .SetParent<Fib> ()
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070050 .SetGroupName ("Ndn")
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070051 .AddConstructor<FibImpl> ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070052 ;
53 return tid;
54}
55
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070056FibImpl::FibImpl ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070057{
58}
59
60void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070061FibImpl::NotifyNewAggregate ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070062{
63 Object::NotifyNewAggregate ();
64}
65
66void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070067FibImpl::DoDispose (void)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070068{
69 clear ();
70 Object::DoDispose ();
71}
72
73
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070074Ptr<Entry>
Alexander Afanasyeveae83ee2013-03-15 15:01:10 -070075FibImpl::LongestPrefixMatch (const Interest &interest)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070076{
Alexander Afanasyev30f60e32012-07-10 14:21:16 -070077 super::iterator item = super::longest_prefix_match (interest.GetName ());
Alexander Afanasyev78057c32012-07-06 15:18:46 -070078 // @todo use predicate to search with exclude filters
79
80 if (item == super::end ())
81 return 0;
82 else
83 return item->payload ();
84}
85
Alexander Afanasyeve5a8b5a2013-03-15 15:15:26 -070086Ptr<fib::Entry>
87FibImpl::Find (const Name &prefix)
88{
89 super::iterator item = super::find_exact (prefix);
90
91 if (item == super::end ())
92 return 0;
93 else
94 return item->payload ();
95}
96
Alexander Afanasyev78057c32012-07-06 15:18:46 -070097
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -070098Ptr<Entry>
Alexander Afanasyevcfdc14f2013-03-15 14:38:44 -070099FibImpl::Add (const Name &prefix, Ptr<Face> face, int32_t metric)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700100{
Alexander Afanasyevcfdc14f2013-03-15 14:38:44 -0700101 return Add (Create<Name> (prefix), face, metric);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700102}
103
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700104Ptr<Entry>
Alexander Afanasyevcfdc14f2013-03-15 14:38:44 -0700105FibImpl::Add (const Ptr<const Name> &prefix, Ptr<Face> face, int32_t metric)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700106{
Alexander Afanasyev1ba09b82012-07-09 09:16:14 -0700107 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700108
109 // will add entry if doesn't exists, or just return an iterator to the existing entry
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700110 std::pair< super::iterator, bool > result = super::insert (*prefix, 0);
111 if (result.first != super::end ())
112 {
113 if (result.second)
114 {
Alexander Afanasyevff0d9ca2013-04-14 23:13:46 -0700115 Ptr<EntryImpl> newEntry = Create<EntryImpl> (this, prefix);
116 newEntry->SetTrie (result.first);
117 result.first->set_payload (newEntry);
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700118 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700119
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700120 super::modify (result.first,
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700121 ll::bind (&Entry::AddOrUpdateRoutingMetric, ll::_1, face, metric));
Alexander Afanasyevadcccf42012-11-26 23:55:34 -0800122
123 if (result.second)
124 {
125 // notify forwarding strategy about new FIB entry
126 NS_ASSERT (this->GetObject<ForwardingStrategy> () != 0);
127 this->GetObject<ForwardingStrategy> ()->DidAddFibEntry (result.first->payload ());
128 }
129
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700130 return result.first->payload ();
131 }
132 else
133 return 0;
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700134}
135
136void
Alexander Afanasyevcfdc14f2013-03-15 14:38:44 -0700137FibImpl::Remove (const Ptr<const Name> &prefix)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700138{
139 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
140
Alexander Afanasyevadcccf42012-11-26 23:55:34 -0800141 super::iterator fibEntry = super::find_exact (*prefix);
142 if (fibEntry != super::end ())
143 {
144 // notify forwarding strategy about soon be removed FIB entry
145 NS_ASSERT (this->GetObject<ForwardingStrategy> () != 0);
146 this->GetObject<ForwardingStrategy> ()->WillRemoveFibEntry (fibEntry->payload ());
147
148 super::erase (fibEntry);
149 }
150 // else do nothing
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700151}
152
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700153// void
Alexander Afanasyevcfdc14f2013-03-15 14:38:44 -0700154// FibImpl::Invalidate (const Ptr<const Name> &prefix)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700155// {
156// NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700157
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700158// super::iterator foundItem, lastItem;
159// bool reachLast;
160// boost::tie (foundItem, reachLast, lastItem) = super::getTrie ().find (*prefix);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700161
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700162// if (!reachLast || lastItem->payload () == 0)
163// return; // nothing to invalidate
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700164
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700165// super::modify (lastItem,
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700166// ll::bind (&Entry::Invalidate, ll::_1));
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700167// }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700168
169void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700170FibImpl::InvalidateAll ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700171{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700172 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ());
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700173
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700174 super::parent_trie::recursive_iterator item (super::getTrie ());
175 super::parent_trie::recursive_iterator end (0);
176 for (; item != end; item++)
177 {
178 if (item->payload () == 0) continue;
179
180 super::modify (&(*item),
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700181 ll::bind (&Entry::Invalidate, ll::_1));
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700182 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700183}
184
185void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700186FibImpl::RemoveFace (super::parent_trie &item, Ptr<Face> face)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700187{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700188 if (item.payload () == 0) return;
189 NS_LOG_FUNCTION (this);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700190
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700191 super::modify (&item,
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700192 ll::bind (&Entry::RemoveFace, ll::_1, face));
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700193}
194
195void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700196FibImpl::RemoveFromAll (Ptr<Face> face)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700197{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700198 NS_LOG_FUNCTION (this);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700199
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700200 std::for_each (super::parent_trie::recursive_iterator (super::getTrie ()),
201 super::parent_trie::recursive_iterator (0),
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700202 ll::bind (&FibImpl::RemoveFace,
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700203 this, ll::_1, face));
204
205 super::parent_trie::recursive_iterator trieNode (super::getTrie ());
206 super::parent_trie::recursive_iterator end (0);
207 for (; trieNode != end; trieNode++)
208 {
209 if (trieNode->payload () == 0) continue;
210
211 if (trieNode->payload ()->m_faces.size () == 0)
212 {
Alexander Afanasyevadcccf42012-11-26 23:55:34 -0800213 // notify forwarding strategy about soon be removed FIB entry
214 NS_ASSERT (this->GetObject<ForwardingStrategy> () != 0);
215 this->GetObject<ForwardingStrategy> ()->WillRemoveFibEntry (trieNode->payload ());
216
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700217 trieNode = super::parent_trie::recursive_iterator (trieNode->erase ());
218 }
219 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700220}
221
222void
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700223FibImpl::Print (std::ostream &os) const
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700224{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700225 // !!! unordered_set imposes "random" order of item in the same level !!!
226 super::parent_trie::const_recursive_iterator item (super::getTrie ());
227 super::parent_trie::const_recursive_iterator end (0);
228 for (; item != end; item++)
229 {
230 if (item->payload () == 0) continue;
231
232 os << item->payload ()->GetPrefix () << "\t" << *item->payload () << "\n";
233 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700234}
235
Alexander Afanasyevf1e013f2012-07-11 17:59:40 -0700236uint32_t
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700237FibImpl::GetSize () const
Alexander Afanasyevf1e013f2012-07-11 17:59:40 -0700238{
239 return super::getPolicy ().size ();
240}
241
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700242Ptr<const Entry>
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700243FibImpl::Begin () const
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700244{
245 super::parent_trie::const_recursive_iterator item (super::getTrie ());
246 super::parent_trie::const_recursive_iterator end (0);
247 for (; item != end; item++)
248 {
249 if (item->payload () == 0) continue;
250 break;
251 }
252
253 if (item == end)
254 return End ();
255 else
256 return item->payload ();
257}
258
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700259Ptr<const Entry>
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700260FibImpl::End () const
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700261{
262 return 0;
263}
264
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700265Ptr<const Entry>
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700266FibImpl::Next (Ptr<const Entry> from) const
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700267{
268 if (from == 0) return 0;
269
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700270 super::parent_trie::const_recursive_iterator item (*StaticCast<const EntryImpl> (from)->to_iterator ());
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700271 super::parent_trie::const_recursive_iterator end (0);
272 for (item++; item != end; item++)
273 {
274 if (item->payload () == 0) continue;
275 break;
276 }
277
278 if (item == end)
279 return End ();
280 else
281 return item->payload ();
282}
283
Alexander Afanasyevea9b3e62012-08-13 19:02:54 -0700284Ptr<Entry>
285FibImpl::Begin ()
286{
287 super::parent_trie::recursive_iterator item (super::getTrie ());
288 super::parent_trie::recursive_iterator end (0);
289 for (; item != end; item++)
290 {
291 if (item->payload () == 0) continue;
292 break;
293 }
294
295 if (item == end)
296 return End ();
297 else
298 return item->payload ();
299}
300
301Ptr<Entry>
302FibImpl::End ()
303{
304 return 0;
305}
306
307Ptr<Entry>
308FibImpl::Next (Ptr<Entry> from)
309{
310 if (from == 0) return 0;
311
312 super::parent_trie::recursive_iterator item (*StaticCast<EntryImpl> (from)->to_iterator ());
313 super::parent_trie::recursive_iterator end (0);
314 for (item++; item != end; item++)
315 {
316 if (item->payload () == 0) continue;
317 break;
318 }
319
320 if (item == end)
321 return End ();
322 else
323 return item->payload ();
324}
325
326
Alexander Afanasyev2b4c9472012-08-09 15:00:38 -0700327} // namespace fib
328} // namespace ndn
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700329} // namespace ns3