blob: 747c6896ec07342b44ff83f0a38dd787fb09be05 [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.h"
24#include "ns3/ndn-face.h"
25#include "ns3/ndn-interest-header.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 Afanasyev4aac5572012-08-09 10:49:55 -070037NS_LOG_COMPONENT_DEFINE ("NdnFibImpl");
Alexander Afanasyev78057c32012-07-06 15:18:46 -070038
39namespace ns3 {
40
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070041NS_OBJECT_ENSURE_REGISTERED (NdnFibImpl);
Alexander Afanasyev78057c32012-07-06 15:18:46 -070042
43TypeId
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070044NdnFibImpl::GetTypeId (void)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070045{
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070046 static TypeId tid = TypeId ("ns3::NdnFib") // cheating ns3 object system
47 .SetParent<NdnFib> ()
48 .SetGroupName ("Ndn")
49 .AddConstructor<NdnFibImpl> ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070050 ;
51 return tid;
52}
53
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070054NdnFibImpl::NdnFibImpl ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070055{
56}
57
58void
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070059NdnFibImpl::NotifyNewAggregate ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -070060{
61 Object::NotifyNewAggregate ();
62}
63
64void
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070065NdnFibImpl::DoDispose (void)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070066{
67 clear ();
68 Object::DoDispose ();
69}
70
71
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070072Ptr<NdnFibEntry>
73NdnFibImpl::LongestPrefixMatch (const NdnInterestHeader &interest)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070074{
Alexander Afanasyev30f60e32012-07-10 14:21:16 -070075 super::iterator item = super::longest_prefix_match (interest.GetName ());
Alexander Afanasyev78057c32012-07-06 15:18:46 -070076 // @todo use predicate to search with exclude filters
77
78 if (item == super::end ())
79 return 0;
80 else
81 return item->payload ();
82}
83
84
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070085Ptr<NdnFibEntry>
86NdnFibImpl::Add (const NdnNameComponents &prefix, Ptr<NdnFace> face, int32_t metric)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070087{
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070088 return Add (Create<NdnNameComponents> (prefix), face, metric);
Alexander Afanasyev78057c32012-07-06 15:18:46 -070089}
90
Alexander Afanasyev4aac5572012-08-09 10:49:55 -070091Ptr<NdnFibEntry>
92NdnFibImpl::Add (const Ptr<const NdnNameComponents> &prefix, Ptr<NdnFace> face, int32_t metric)
Alexander Afanasyev78057c32012-07-06 15:18:46 -070093{
Alexander Afanasyev1ba09b82012-07-09 09:16:14 -070094 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix) << boost::cref(*face) << metric);
Alexander Afanasyev78057c32012-07-06 15:18:46 -070095
96 // will add entry if doesn't exists, or just return an iterator to the existing entry
Alexander Afanasyev30f60e32012-07-10 14:21:16 -070097 std::pair< super::iterator, bool > result = super::insert (*prefix, 0);
98 if (result.first != super::end ())
99 {
100 if (result.second)
101 {
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700102 Ptr<NdnFibEntryImpl> newEntry = Create<NdnFibEntryImpl> (prefix);
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700103 newEntry->SetTrie (result.first);
104 result.first->set_payload (newEntry);
105 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700106
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700107 super::modify (result.first,
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700108 ll::bind (&NdnFibEntry::AddOrUpdateRoutingMetric, ll::_1, face, metric));
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700109
Alexander Afanasyev30f60e32012-07-10 14:21:16 -0700110 return result.first->payload ();
111 }
112 else
113 return 0;
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700114}
115
116void
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700117NdnFibImpl::Remove (const Ptr<const NdnNameComponents> &prefix)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700118{
119 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
120
121 super::erase (*prefix);
122}
123
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700124// void
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700125// NdnFibImpl::Invalidate (const Ptr<const NdnNameComponents> &prefix)
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700126// {
127// NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId () << boost::cref(*prefix));
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700128
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700129// super::iterator foundItem, lastItem;
130// bool reachLast;
131// boost::tie (foundItem, reachLast, lastItem) = super::getTrie ().find (*prefix);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700132
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700133// if (!reachLast || lastItem->payload () == 0)
134// return; // nothing to invalidate
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700135
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700136// super::modify (lastItem,
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700137// ll::bind (&NdnFibEntry::Invalidate, ll::_1));
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700138// }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700139
140void
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700141NdnFibImpl::InvalidateAll ()
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700142{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700143 NS_LOG_FUNCTION (this->GetObject<Node> ()->GetId ());
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700144
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700145 super::parent_trie::recursive_iterator item (super::getTrie ());
146 super::parent_trie::recursive_iterator end (0);
147 for (; item != end; item++)
148 {
149 if (item->payload () == 0) continue;
150
151 super::modify (&(*item),
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700152 ll::bind (&NdnFibEntry::Invalidate, ll::_1));
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700153 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700154}
155
156void
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700157NdnFibImpl::RemoveFace (super::parent_trie &item, Ptr<NdnFace> face)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700158{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700159 if (item.payload () == 0) return;
160 NS_LOG_FUNCTION (this);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700161
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700162 super::modify (&item,
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700163 ll::bind (&NdnFibEntry::RemoveFace, ll::_1, face));
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700164}
165
166void
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700167NdnFibImpl::RemoveFromAll (Ptr<NdnFace> face)
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700168{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700169 NS_LOG_FUNCTION (this);
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700170
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700171 std::for_each (super::parent_trie::recursive_iterator (super::getTrie ()),
172 super::parent_trie::recursive_iterator (0),
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700173 ll::bind (&NdnFibImpl::RemoveFace,
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700174 this, ll::_1, face));
175
176 super::parent_trie::recursive_iterator trieNode (super::getTrie ());
177 super::parent_trie::recursive_iterator end (0);
178 for (; trieNode != end; trieNode++)
179 {
180 if (trieNode->payload () == 0) continue;
181
182 if (trieNode->payload ()->m_faces.size () == 0)
183 {
184 trieNode = super::parent_trie::recursive_iterator (trieNode->erase ());
185 }
186 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700187}
188
189void
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700190NdnFibImpl::Print (std::ostream &os) const
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700191{
Alexander Afanasyev44bb6ea2012-07-09 08:44:41 -0700192 // !!! unordered_set imposes "random" order of item in the same level !!!
193 super::parent_trie::const_recursive_iterator item (super::getTrie ());
194 super::parent_trie::const_recursive_iterator end (0);
195 for (; item != end; item++)
196 {
197 if (item->payload () == 0) continue;
198
199 os << item->payload ()->GetPrefix () << "\t" << *item->payload () << "\n";
200 }
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700201}
202
Alexander Afanasyevf1e013f2012-07-11 17:59:40 -0700203uint32_t
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700204NdnFibImpl::GetSize () const
Alexander Afanasyevf1e013f2012-07-11 17:59:40 -0700205{
206 return super::getPolicy ().size ();
207}
208
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700209Ptr<const NdnFibEntry>
210NdnFibImpl::Begin ()
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700211{
212 super::parent_trie::const_recursive_iterator item (super::getTrie ());
213 super::parent_trie::const_recursive_iterator end (0);
214 for (; item != end; item++)
215 {
216 if (item->payload () == 0) continue;
217 break;
218 }
219
220 if (item == end)
221 return End ();
222 else
223 return item->payload ();
224}
225
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700226Ptr<const NdnFibEntry>
227NdnFibImpl::End ()
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700228{
229 return 0;
230}
231
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700232Ptr<const NdnFibEntry>
233NdnFibImpl::Next (Ptr<const NdnFibEntry> from)
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700234{
235 if (from == 0) return 0;
236
Alexander Afanasyev4aac5572012-08-09 10:49:55 -0700237 super::parent_trie::const_recursive_iterator item (*StaticCast<const NdnFibEntryImpl> (from)->to_iterator ());
Alexander Afanasyev95a4fa32012-07-09 15:23:59 -0700238 super::parent_trie::const_recursive_iterator end (0);
239 for (item++; item != end; item++)
240 {
241 if (item->payload () == 0) continue;
242 break;
243 }
244
245 if (item == end)
246 return End ();
247 else
248 return item->payload ();
249}
250
251
Alexander Afanasyev78057c32012-07-06 15:18:46 -0700252} // namespace ns3